Vai al contenuto principale Vai al footer
Università degli Studi di Parma Università degli Studi di Parma
Laurea in
Informatica
Università degli Studi di Parma
Dipartimento di Scienze Matematiche, Fisiche e Informatiche

ALGORITMI E STRUTTURE DATI II
cod. 16827

Anno accademico 2011/12
2° anno di corso - Secondo semestre
Docente
Grazia LOTTI
Settore scientifico disciplinare
Informatica (INF/01)
Ambito
Discipline informatiche
Tipologia attività formativa
Caratterizzante
48 ore
di attività frontali
6 crediti
sede: PARMA
insegnamento
in - - -
orari del corso non disponibili
appelli d'esame
Stampa

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

- - -

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

- - -

Obiettivi agenda 2030 per lo sviluppo sostenibile

- - -