Programma
Il corso si propone di mettere lo studente a contatto con tecniche algoritmiche di base.
- Liste collegate.
- Alberi binari.
- Tabelle di hash.
- Algoritmi di ordinamento (ordinamento per selezione, ordinamento per inserimento, ordinamento per fusione, quicksort, le due versioni del radix sort).
- Grafi e rappresentazioni degli stessi.
- Visite in ampiezza e profondità.
- Ordinamento topologico.
- Mucchi (heap).
- Cammini minimi su grafi (come riferimento per l'algoritmo di Dijkstra e gli heap, potete leggere le dispense per le Olimpiadi di Informatica).
- Alberi di copertura minimi (algoritmo di Prim).
- Programmazione dinamica: affrancatura, distanza di Levenshtein, massima sottosequenza (come riferimento, potete leggere le dispense per le Olimpiadi di Informatica).
- Hashing minimale perfetto e filtri di Bloom (si vedano le dispense di algoritmica per il web; l'analisi dei filtri di Bloom è esclusa).
- Algoritmo di Boyer e Moore per la ricerca nei testi (euristica del carattere cattivo).
Per il corso avanzato, dalle dispense per il corso di informatica teorica:
- Teorema di Cantor (capitolo 2).
- La macchina RAM (cenni minimi, capitolo 3).
- Le funzioni ricorsive (capitolo 4, solo definizione).
- Indecidibilità (paragrafi 4.2 e 4.3).
- Teorema di Rice (Teorema 8).
- Definizione della macchine di Turing e codifica dei problemi di decisione (parti dei capitoli 5 e 6).
- Tempo e spazio, P e NP (paragrafo 6.2).
- Riduzione combinatoriale tra problemi (parti paragrafo 6.4 fino al Teorema 23, escluso il Teorema 22).
Dal materiale discusso a lezione sono esclusi: le funzioni di hash, le funzioni di hash perfetto monotone, l'algoritmo di Tarjan e le trie.
Per informazioni/chiarimenti, dopo avere letto alcune indicazioni di base potete scrivere al docente (Sebastiano Vigna).
Modalità d'esame
L'esame è orale. La data è fissata tramite appuntamento (gli appelli sono, di fatto, puramente nominali).
Testi consigliati
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduzione agli algoritmi e strutture dati. Seconda edizione, 2005.
Sebastiano Vigna. Dispense per il corso di informatica teorica (dispense). ISBN: 9788838662515.