Introdurre lo studente ai concetti fondamentali della progettazione di algoritmi efficienti, ad iniziare dalla complessità computazionale, e alla progettazione di strutture dati ottimizzate per la soluzione di specifici problemi.

Conoscenza e comprensione: conoscere i principali algoritmi e strutture dati e le principali tecniche di progettazione di algoritmi.

Capacità di applicare conoscenza e comprensione: essere in grado di individuare l’ algoritmo migliore tra quelli studiati ed eventualmente progettarne delle varianti efficienti per risolvere dei problemi di natura computazionale. Essere in grado di valutare la complessità di un algoritmo.

Capacità di giudizio: essere in grado di formalizzare un problema computazionale in modo adeguato ed identificare le metodologie algoritmiche necessarie per la sua soluzione.

Abilità comunicative: essere in grado di spiegare in modo chiaro la logica ed il funzionamento di un algoritmo, e di descriverne il funzionamento anche mediante pseudocodice

Abilità di apprendimento: capacità di apprendere nuove tecniche algoritmiche e nuove strutture dati oltre a quelle viste a lezione, motivati da specifici problemi da risolvere.

Programmazione in Python, nozioni di analisi (serie, integrali, successioni), nozioni di probabilità (variabili aleatore, valore atteso).

Introduzione alla progettazione di algoritmi e strutture dati, con focus su applicazioni in scienza dei dati ed intelligenza artificiale. Algoritmi di ordinamento e di ricerca, strutture dati fondamentali, alberi binari, tabelle di hash, algoritmi su grafi.

Thomas H. Cormen , Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduzione agli algoritmi e strutture dati, 4a Edizione, 2022.

Durante tutto il corso: analisi della complessità degli algoritmi iterativi e ricorsivi e tecniche di progettazione di algoritmi efficienti (analisi della complessità, ricorsione, uso di strutture dati, randomizzazione, analisi ammortizzata).


Algoritmi di ordinamento: insertion sort, merge sort, heap sort, quicksort

Algoritmi di selezione: selection sort e bisezione.

Strutture dati fondamentali: Pile, Code, Liste, Heap.

Alberi binari di ricerca: operazioni di base, rotazioni, alberi AVL, (RB tree, B tree, Kd tree).

Tabelle di hash

Analisi ammortizzata

Algoritmi su grafi: visita in ampiezza e profondità, ordinamento topologico, algoritmo di Tarjan componenti fortememte connesse, algoritmo di Bellman Ford e Dijkstra per cammini minini.

Programmazione dinamica: longest common subsequence, Algoritmo di Floyd-Varshall.

Il corso si svolgerà con una parte prevalente di lezioni frontali dove il docente introdurrà i concetti fondamentali. A queste attività si accompagneranno delle esercitazioni in aula, in cui si risolveranno degli esercizi tipo. Infine, saranno consegnati esercizi da fare a casa durante lo studio individuale, con delle scadenza di consegna mediamente in due settimane.

L’esame sarà scritto ed orale. L’esame scritto è obbligatorio e consiste di norma di una serie di domande elementari a scelta multipla di sbarramento (la cui risposta sbagliata preclude il superamento dell’esame) e di alcuni esercizi, tipicamente quattro, delle tipologia vista a lezione. Ogni esercizio vale un certo numero di punti, indicato chiaramente in ogni scritto, la cui somma è normalmente pari a 30. Per il superamento dello scritto è necessario ottenere almeno 18/30. L’esame orale è facoltativo in funzione del punteggio ottenuto, e permette di norma un variazione di ±5 punti. L’orale è obbligatorio per chi ha conseguito almeno 28/30 allo scritto. L’orale verterà su domande di teoria o di comprensione degli argomenti svolti. In aggiunta all’esame scritto, potranno essere previste due provette intermedie. In caso, se entrambe vengono superate, il voto medio conseguito conta come voto dell’esame scritto, ed esonera quindi dal sostenere l'esame scritto. Sarà sempre possibile per uno studente fare l’esame scritto per migliorare il voto.