Sillabo dell'insegnamento

• A - Fondamenti
COM - Complessita'
Modelli di calcolo e relative misure. La MdT. La RAM con criterio di costo uniforme e logaritmico. Relazioni tra MdT e RAM.
• B - Algoritmi
* ASC - Algoritmi su Strutture Combinatorie
Algoritmi di base su grafi. Chiusura transitiva. Calcolo delle componenti fortemente connesse (Tarjan). Algoritmi per minimum spanning tree (Prim e Kruskal). Algoritmi per cammino minimo da una sorgente (Dijkstra, Bellmann-Ford). Algoritmi per cammini minimi da sorgenti multiple (Floyd-Warshall, Johnson).
* SDF - Strutture di Dati Fondamentali
Grafi e visite di grafi.Tecniche di rappresentazione di grafi orientati e non orientati. Algoritmi di visita in ampiezza e profondita'; algoritmi di visita su alberi. Classificazione degli archi. Calcolo delle componenti connesse. Algoritmo per il topological-sort di un grafo diretto aciclico.
TAA - Tecniche Algoritmiche Avanzate
Introduzione alla programmazione dinamica e alla tecnica greedy. Parentesizzazione ottima. Codici di Huffman.
* A - Algoritmi fondamentali
Algoritmi elementari di ordinamento. Algoritmi efficienti basati sul confronto: heap-sort, quick-sort. Quick-sort randomizzato. Analisi della complessita? e limiti inferiori al numero di confronti. Algoritmi lineari non basati sul confronto. Selezione e statistiche d'ordine.
SDA - Strutture di Dati Avanzate
B-alberi. heap binomiali, heap di Fibonacci.
* ASC - Algoritmi su Strutture Combinatorie
Alberi binari di ricerca, alberi AVL. Operazioni di rotazione. Alberi red-black, alberi 2-3.
* SDF - Strutture di Dati Fondamentali
Tabelle hash: funzioni hash, liste di concatenazione, indirizzamento aperto. Metodi di scansione, hashing doppio. Operazioni Union-Find: algoritmi basati su liste; algoritmi basati su alberi con bilanciamento e compressione.
* SDF - Strutture di Dati Fondamentali
Strutture dati fondamentali. liste, code, pile e procedure ricorsive. Heap, code a priorita'. Alberi.
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
Analisi di algoritmi e complessita'. Introduzione al progetto di algoritmi e alla complessita' di calcolo. Complessita' di un algoritmo e di un problema. Ordini di grandezza delle funzioni. Limiti inferiori alla complessita'. Tecnica divide et impera: algoritmo di Karatsuba-Hoffman, ricerca binaria, mergesort. Relazioni di ricorrenza e Lemma Fondamentale.