Sillabo dell'insegnamento

• A - Fondamenti
COM - Complessità
Classi di complessità. Il teorema di gerarchia sulle classi di complessità. Il Gap theorem. Teorema di Savitch.
COM - Complessità
Il teorema di Immermann-Szelepscenyi e conseguenze. Riduzioni e completezza. Classi esterne ad NP.
* CAL - Calcolabilità
Quantum Computing. Classi di complessità quantistica. Algoritmi quantistici.
* ALF - Automi e Linguaggi Formali
DNA Computing. Il modello di Adleman e Lipton. Soluzione di SAT ed altri problemi NP-completi. Simulazione di macchine di Turing.
• B - Algoritmi
* A - Algoritmi fondamentali
Algoritmo di Hopcroft.
* A - Algoritmi fondamentali
Algoritmo di Paige-Tarjan
* A - Algoritmi fondamentali
Algoritmi di Knuth-Morris e Pratt, Rabin e Karp, Boyer e Moore
* A - Algoritmi fondamentali
Algoritmo di Harel e Tarjan per il calcolo del lowest common ancestor
* A - Algoritmi fondamentali
Algoritmo di Sellers, algoritmo di Landau e Vishkin, algoritmo di Chang e Lawler
SDA - Strutture di Dati Avanzate
Suffix trees, BDDs e applicazioni
TAA - Tecniche Algoritmiche Avanzate
Modelli e algoritmi per computers paralleli
TAA - Tecniche Algoritmiche Avanzate
Introduzione agli algoritmi randomizzati e algoritmi probabilistici su grafi