Obiettivi formativi
Obiettivo del corso e' di fornire una panoramica di alcuni dei piu' importanti
algoritmi
Prerequisiti
algoritmi e strutture dati 1
Contenuti dell'insegnamento
• tecnica greedy, programmazione dinamica, algoritmi branch-bound, ricerca
locale, Metropolis, simulated annehaling;
• geometria computazionale: inviluppo convesso, point location, triangolar-
izzazione di un poligono, algoritmo sweeping, algoritmo closest pair;
• DFT-IDFT: algoritmo FFT di Cooley -Tuckey, prodotto/divisione di poli-
nomi, polinomio di interpolazione, teorema cinese dei resti, FFT in strut-
ture nite, algoritmo di Schonhage-Strassen per il prodotto di interi;
• calcolo di forme bilineari, problemi collegati al prodotto di matrici, algo-
ritmi per il prodotto di matrici;
• string matching esatto: automi, algoritmi di Knuth-Morris-Pratt, Boyer-
Moore, Aho-Corasick; string matching approssimato: distanza di Ham-
ming, distanza di edit, programmazione dinamica; trie, suffix tree, suffix array;
• classi di complessita P, NP, NPC e loro relazioni, riduzioni polinomiali, le
classi LOGSPACE e PSPACE, le classi probabilistiche, algoritmi proba-
bilistici, algoritmi approssimanti.
Programma esteso
• tecnica greedy e programmazione dinamica: ulteriori applicazioni;
• algoritmi randomizzati, algoritmo di Miller-Rabin;
• calcolo parallelo, PRAM, algoritmi elementari, teorema di Brent;
• external memory model, k-way mergesort, distribution sorting;
• cache oblivious model, algoritmi elementari;
• algoritmi online, analisi competitiva; paging: LRU, Random, Marking; web caching: greedy dual, greedy dual size;
• geometria computazionale: inviluppo convesso, algoritmo sweeping;
• DFT-IDFT: 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, suffix tree, suffix array;
• classi di complessita P, NP, NPC e loro relazioni, riduzioni polinomiali,
algoritmi di approssimazione.
Bibliografia
[1] F.P.Preparata, M.I.Shamos, Computational Geometry, Springer-Verlag.
[2] J.Kleinberg, E.Tardos, Algorithm design, Addison Wesley.
[3] C. H. Papadimitriou, Computational Complexity, Addison Wesley.
[4] A. Bernasconi, B. Codenotti, Introduzione alla Complessita Com-
putazionale, McGraw-Hill.
[5] D. Guseld, Algorithms on String, Trees, and Sequences: Computer science
and Computational Biology ,Cambridge University Press.
Metodi didattici
lezioni in aula
Modalità verifica apprendimento
esame orale
Altre informazioni
- - -
