Il Corso ha lo scopo di illustrare le principali tecniche di progettazione di algoritmi e di descrivere ed analizzare gli algoritmi di base più diffusi e le strutture dati in essi utilizzate, con particolare riferimento agli aspetti di complessità computazionale e di correttezza.

01. Introduzione agli algoritmi e alle strutture dati: 01.01 Algoritmi e loro tipologie. 01.02 Correttezza di un algoritmo rispetto ad un problema. 01.03 Complessit? di un algoritmo rispetto all'uso di risorse. 01.04 Strutture dati e loro tipologie. 02. Classi di problemi: 02.01 Problemi decidibili e indecidibili. 02.02 Classi P ed NP. 02.03 Teorema di Cook. 02.04 NP-completezza. 03. Complessit? degli algoritmi: 03.01 Notazioni per esprimere la complessit? asintotica. 03.02 Calcolo della complessit? di algoritmi non ricorsivi. 03.03 Calcolo della complessit? di algoritmi ricorsivi. 04. Algoritmi per array: 04.01 Il problema della ricerca. 04.02 Algoritmo di ricerca lineare. 04.03 Algoritmo di ricerca binaria. 04.04 Il problema dell'ordinamento. 04.05 Insertsort. 04.06 Selectsort. 04.07 Bubblesort. 04.08 Mergesort. 04.09 Quicksort. 04.10 Heapsort. 05. Algoritmi per liste, code e pile: 05.01 Algoritmi di visita, ricerca, inserimento e rimozione per liste. 05.02 Algoritmi di inserimento e rimozione per code. 05.03 Algoritmi di inserimento e rimozione per pile. 06. Algoritmi per alberi: 06.01 Trasformazione di alberi generali in alberi binari. 06.02 Algoritmi di visita e ricerca per alberi binari. 06.03 Algoritmi di ricerca, inserimento e rimozione per alberi binari di ricerca. 06.04 Criteri di bilanciamento per alberi binari di ricerca. 06.05 Algoritmi di ricerca, inserimento e rimozione per alberi binari di ricerca rosso-nero. 07. Algoritmi per grafi: 07.01 Rappresentazione di grafi con liste e matrici di adiacenza. 07.02 Algoritmi di visita e ricerca per grafi. 07.03 Il problema dell'ordinamento topologico. 07.04 Il problema delle componenti fortemente connesse. 07.05 Il problema dell'albero ricoprente minimo. 07.06 Algoritmo di Kruskal. 07.07 Algoritmo di Prim. 07.08 Il problema del percorso pi? breve. 07.09 Algoritmo di Bellman-Ford. 07.10 Algoritmo di Dijkstra. 07.11 Algoritmo di Floyd-Warshall. 08. Tecniche algoritmiche: 08.01 Tecnica del divide et impera. 08.02 Programmazione dinamica. 08.03 Tecnica golosa. 08.04 Tecnica per tentativi e revoche. 09. Correttezza degli algoritmi: 09.01 Triple di Hoare. 09.02 Determinazione della precondizione pi? debole. 09.03 Verifica della correttezza di algoritmi iterativi. 09.04 Verifica della correttezza di algoritmi ricorsivi. 10. Attivit? di laboratorio: 10.01 Valutazione sperimentale della complessit? degli algoritmi. 10.02 Confronto sperimentale degli algoritmi di ordinamento per array. 10.03 Confronto sperimentale degli algoritmi di ricerca per alberi binari.

Modalità didattiche

Lezioni frontali ed esercitazioni di laboratorio

Obblighi

Nessuno

Testi di studio

Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", MIT Press, 2001 (Cormen, Leiserson, Rivest, Stein, "Introduzione agli Algoritmi e alle Strutture Dati", McGraw-Hill, 2005). Demetrescu, Finocchi, Italiano, "Algoritmi e Strutture Dati", McGraw-Hill, 2004. Crescenzi, Gambosi, Grossi, "Strutture di Dati e Algoritmi", Pearson/Addison-Wesley, 2006. Sedgewick, "Algorithms in C", Addison-Wesley, 1997 (Sedgewick, "Algoritmi in C", Pearson/Prentice Hall, 2002).

Modalità di
accertamento

Progetto individuale di laboratorio, prova scritta e prova orale (prove d'esame).

Disabilità e DSA

Le studentesse e gli studenti che hanno registrato la certificazione di disabilità o la certificazione di DSA presso l'Ufficio Inclusione e diritto allo studio, possono chiedere di utilizzare le mappe concettuali (per parole chiave) durante la prova di esame.

A tal fine, è necessario inviare le mappe, due settimane prima dell’appello di esame, alla o al docente del corso, che ne verificherà la coerenza con le indicazioni delle linee guida di ateneo e potrà chiederne la modifica.