ALGORITMI E STRUTTURE DATI - MOD.2

L'insegnamento è uno dei corsi fondamentali del corso di studio e fornisce un'introduzione agli algoritmi, ovvero alla formalizzazione dei problemi, all'individuazione di soluzioni computazionali, e all'analisi di tali soluzioni, dal punto di vista della correttezza e dell'efficienza nell'uso di risorse. Inoltre presenta varie strutture dati fondamentali e tecniche di base per la progettazione e l'analisi degli algoritmi.

Conoscenza e comprensione:
- conoscenza e comprensione dei principali algoritmi e strutture dati;
- comprensione e valutazione della complessità dei problemi informatici e capacità di selezionare metodi adeguati per la modellazione e risoluzione del problema.

Capacità di applicare conoscenza e comprensione:
- capacità logico-deduttive e di problem solving;
- capacità di formalizzare e implementare soluzioni per problemi reali e identificazione di pattern di soluzione appropriati;

Capacità di giudizio
- Sapere formulare ed argomentare soluzioni, sviluppando anche un approccio critico alla valutazione di soluzioni alternative.

Familiarità con i concetti di base della matematica discreta e dell'analisi matematica. Conoscenza del linguaggio C++ e dei rudimenti della programmazione.

Strutture dati elementari: Array, liste e alberi.

Alberi binari di ricerca.

Heap e code di priorità.

Tabelle Hash.

Ordinamento: Insertion sort, Merge sort, Heapsort, Quicksort.

Ordinamento in tempo lineare: counting sort, radix sort.

Programmazione dinamica.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati IV/ed. McGraw-Hill, 2023.

C. Demetrescu, I. Finocchi, G. F. Italiano. Algoritmi e strutture dati
(seconda edizione), McGraw-Hill, 2008.

La verifica dell'apprendimento avviene attraverso una prova scritta e una prova orale. La prova scritta ha durata di 3 ore ed è divisa in due parti. La prima parte consiste di 3 quesiti da svolgere in 30 minuti. Tali quesiti richiedono una risposta rapida su argomenti affrontati a lezione e mirano a verificare l'acquisizione dei concetti di base del corso. La seconda parte consiste di 4 esercizi, alcuni dei quali hanno lo scopo di accertare le abilità acquisite nel risolvere problemi computazionali tramite la progettazione di algoritmi efficienti, mentre altri mirano a verificare l'acquisizione delle conoscenze previste dal programma del corso. La prova scritta può essere sostituita dal superamento di due prove intermedie, ciascuna delle quali ha una durata di 2 ore e consiste di 3 esercizi, aventi le stesse tipologie degli esercizi della seconda parte della prova scritta. Durante la prova scritta non è ammesso l'uso di libri, appunti, supporti elettronici.

Durante la prova orale lo studente deve dimostrare di conoscere gli argomenti svolti durante il corso e di saperli esporre in modo formale.

scritto e orale

La gradazione del voto è stabilita come segue:

A. I punteggi nell'intervallo 18-22 verranno assegnati in presenza di:
- conoscenza sufficiente del programma
- limitata capacità di risolvere gli esercizi proposti all'esame
- sufficiente esposizione orale

B. I punteggi nell'intervallo 23-26 verranno assegnati in presenza di:
- buona conoscenza del programma
- discreta capacità di risolvere gli esercizi proposti all'esame
- adeguata esposizione orale

C. I punteggi nell'intervallo 27-30 verranno assegnati in presenza di:
- ottima conoscenza di tutte le tematiche del programma
- buona capacità di risolvere gli esercizi proposti all'esame
- esposizione orale pienamente appropriata

La lode verrà assegnata in presenza di un esame perfetto, in cui vengono fornite soluzioni ottimali per ciascun esercizio e a fronte di una esposizione orale brillante.

Insegnamento organizzato in lezioni frontali. Uso di Lavagna e tablet.