Algoritmi e Complessità

Anno Accademico 2009-2010

• Lezione 1: Introduzione alla complessità e ai modelli di calcolo. Definizione di algoritmo, problema, istanza, complessità (in tempo e spazio) al caso pessimo e medio. Algoritmi polinomiali ed esponenziali. Problemi indecidibili: Fermata. Tecnica della diagonalizzazione.
• Lezione 2: Schemi di codifica e macchina di Turing. Tesi (estesa) di Church-Turing. Le classi P, NP e NPC. Riduzione polinomiale.
• Lezione 3: Il Teorema di Cook (con dimostrazione). Esempi di riduzione polinomiale: 3SAT, CLIQUE, MAX-2SAT. Algoritmo polinomiale per 2SAT. Un esempio di algoritmo pseudo-polinomiale: PARTITION.
• Lezione 4: La Classe RP e il problema della primalità. Algoritmi di approssimazione: APX, FPTAS, PTAS. L'algoritmo FPTAS per Knapsack e Partition. Il teorema del Gap e inapprossimabilità di TSP. Esempi di algoritmi di approssimazione: Vertex cover, TSP euclideo (e/o con disuguaglianza triangolare).
• Lezione 5: Approssimazione di Set Covering. Shortest Path: Algoritmo di Dijkstra, applicazione alla compressione. MST: Kruskal, Prin, Reverse deletion. Applicazione al Clustering.
• Lezione 6: Cammini minimi su grafi generali: Bellman-Ford. La struttura dati per Union-Find. Problema del Matching. Trasformata di Burrows-Wheeler.
• Lezione 7: Teorema dei cammini incrementanti, con dimostrazione. Algoritmo randomizzato per min-cut. Problema del sorting: limite inferiore (tecnica degli alberi di decisione), quicksort e merge-sort.
• Lezione 8: Analisi del Quicksort al caso medio. Problema della selezione, con analisi al caso medio e in alta probabilita'. Problema del sorting su "memoria esterna" e algoritmo Distribution Sort con analisi al caso medio.
• Lezione 9: Ordinamento su interi: Counting sort e Radix sort. Permuting vs Sorting su "memoria esterna": limiti inferiori.
• Lezione 10: Hashing: definizione, tabelle hash con liste di trabocco e loro analisi. Hash universale: definzione, esempio con dimostrazione. Generazione deterministica di m primo in tempo o(m).
• Lezione 11: Dimostrazione su media della lunghezza massima di una lista di trabocco. Hash Perfetto: definizione, progetto e dimostrazione. Applicazione di hash perfetto su problemi Web: gestione/confronto di oggetti (es. stringhe) molto complessi (lunghi). Sketch di Cuckoo Hashing.
• Lezione 12: Bloom Filter: definizione, proprietà, dimostrazione sull'errore commesso, applicazioni. Cenni su BloomFilter compresso.
• Lezione 13: Lower bound per il Bloom Filter. Introduzione alla compressione statistica: codici prefissi ed enunciato del Teorema di Shannon. Huffman e Arithmetic coding con teoremi e dimostrazioni sulle loro prestazioni.
• Lezione 14: Skip Lists: definizione, proprietà, dimostrazioni su prestazioni in tempo e spazio delle varie operazioni.
• Lezione 15: Discussione finale su vari argomenti.