Obiettivi formativi
Obiettivo del corso e' di fornire una panoramica di alcuni dei piu' importanti algoritmi
Prerequisiti
Algoritmi e strutture dati e Laboratorio di algoritmi e strutture dati
Contenuti dell'insegnamento
<br />
<br />
• tecnica greedy, programmazione dinamica, algoritmi branch-bound, ricerca <br />
locale, Metropolis, simulated annehaling; <br />
• geometria computazionale: inviluppo convesso, point location, triangolar- <br />
izzazione di un poligono, algoritmo sweeping, algoritmo closest pair; <br />
• DFT-IDFT: algoritmo FFT di Cooley -Tuckey, prodotto/divisione di poli- <br />
nomi, polinomio di interpolazione, teorema cinese dei resti, FFT in strut- <br />
ture finite, algoritmo di Schonhage-Strassen per il prodotto di interi; <br />
• calcolo di forme bilineari, problemi collegati al prodotto di matrici, algo- <br />
ritmi per il prodotto di matrici; <br />
• string matching esatto: automi, algoritmi di Knuth-Morris-Pratt, Boyer- <br />
Moore, Aho-Corasick; string matching approssimato: distanza di Ham- <br />
ming, distanza di edit, programmazione dinamica; trie, suffix tree, com- <br />
pressione di Ziv-Lempel; <br />
• classi di complessita P, NP, NPC e loro relazioni, riduzioni polinomiali, le <br />
classi LOGSPACE e PSPACE, le classi probabilistiche, algoritmi proba- <br />
bilistici, algoritmi approssimanti.
Bibliografia
<br />
<br />
[1] C. H. Papadimitriou, Computational Complexity, Addison Wesley, 1995. <br />
[2] A. Bernasconi, B. Codenotti, Introduzione alla Complessita Com- <br />
putazionale, McGraw-Hill, 1998. <br />
[3] D. Gusfield, Algorithms on String, Trees, and Sequences: Computer science <br />
and Computational Biology Cambridge University Press, 1997.
