ALGORITMI E STRUTTURE DATI II
cod. 16827

Anno accademico 2008/09
1° anno di corso - Secondo semestre
Docente
Settore scientifico disciplinare
Informatica (INF/01)
Field
Discipline informatiche
Tipologia attività formativa
Caratterizzante
48 ore
di attività frontali
6 crediti
sede:
insegnamento
in - - -

Obiettivi formativi

<br />
<br />
Obiettivo del corso e' di fornire una panoramica di alcuni dei piu'  importanti algoritmi

Prerequisiti

<br />
<br />
Algoritmi e strutture dati e Laboratorio di Algoritmi e strutture dati

Contenuti dell'insegnamento

 <br />
<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.

Programma esteso

- - -

Bibliografia

<br />
<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. <br />

Metodi didattici

- - -

Modalità verifica apprendimento

- - -

Altre informazioni

- - -