Sillabo dell'insegnamento

• A - Fondamenti
COM - Complessita'
La RAM con criterio di costo uniforme e logaritmico. Complessit`a di un algoritmo e di un problema. Ordini di grandezza delle funzioni. Limiti inferiori alla complessita'. Relazioni di ricorrenza e Lemma Fondamentale.
• B - Algoritmi
* ASC - Algoritmi su Strutture Combinatorie
Grafi, generalita' e rappresentazione in memoria. Visite di grafi, BFS e DFS. Alberi di copertura e componenti connesse. Classificazione degli archi. Grafi diretti aciclici e ordine topologico. Algoritmi per minimum spanning tree (Prim e Kruskal). Cammini minimi da sorgente unica: algorimi di Dijkstra, algoritmo di Bellman-Ford.
* SDF - Strutture di Dati Fondamentali
Strutture di dati: dati statici e dinamici. Arrays. Liste: realizzazione con puntatori e con cursori. Pile: realizzazione con puntatori e con arrays. Code: realizzazione con puntatori e con arrays.
* A - Algoritmi fondamentali
Algoritmi di ordinamento: selection-sort, insertion-sort, bubble-sort. Tecnica divide et impera: algoritmo di Karatsuba-Hofman, ricerca binaria, mergesort. Partition, quick-sort, quick-sort randomizzato. Analisi della complessita' e limiti inferiori alla complessita' del problema di ordinamento per confronti. Algoritmi lineari non basati sul confronto: counting-sort, radix-sort, bucket-sort.
* A - Algoritmi fondamentali
Ricerca del secondo minimo. Ricerca del minimo e del massimo in una sequenza. Selezione dell'i-esimo elemento, calcolo del mediano: algoritmo deterministico e randomizzato.
* SDF - Strutture di Dati Fondamentali
Tabelle con indirizzamento diretto. Tabelle hash. Funzioni hash. Gestione delle collisioni. Liste di trabocco, indirizzamento aperto.
* SDF - Strutture di Dati Fondamentali
Alberi ordinali, realizzazione. Alberi binari di ricerca. Ricerca di una chiave, minimo, massimo, successore, predecessore, inserimento e cancellazione. Problema del bilanciamento. Alberi AVL, rotazioni. Strutture dati per insiemi disgiunti. Alberi 2-3.
* SDF - Strutture di Dati Fondamentali
Heap. Costruzione di un heap,inserimento, cancellazione, mantenimento della proprieta' di heap. Heapsort. Coda a priorit`a
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
Programmazione dinamica: distanza di edit. Partizione, zaino 0-1. Parentesizzazione ottima. Algoritmi greedy: zaino reale.