Sillabo dell'insegnamento

• A - Fondamenti
COM - Complessita'
Problemi decisionali. Classi di complessita P, NP, NPC. Riduzioni polinomiali. Il teorema di Cook (cenni).
COM - Complessita'
Algoritmi di approssimazione: minimum vertex cover, commesso viaggiatore.
• B - Algoritmi
* ASC - Algoritmi su Strutture Combinatorie
Cammini minimi fra tutte le coppie: algoritmo di Floyd-Warshall, algoritmo di Johnson per grafi sparsi. Chiusura transitiva. Componenti fortemente connesse di un grafo.
* A - Algoritmi fondamentali
Algoritmi randomizzati, test di primalit`a di Miller-Rabin. Algoritmi di geometria computazionale: inviluppo convesso ( algoritmo di Gra- ham, algoritmo di Jarvis), algoritmo sweeping. External memory model, k-way mergesort. Algoritmi online, algoritmo MTF, algoritmi di paging.
SDA - Strutture di Dati Avanzate
B-alberi. Heap binomiali. Heap di Fibonacci. Trie, suffix tree, suffix array.
* A - Algoritmi fondamentali
Algoritmo FFT, algoritmo di Cooley-Tuckey, prodotto di polinomi. FFT in strutture finite, algoritmo di Schonhage-Strassen per il prodotto di interi (cenni). String matching esatto: algoritmo Knuth-Morris-Pratt, algoritmo Boyer- Moore.