ALGORITMI E STRUTTURE DATI 2 (corso di laurea in Informatica)
A. A. 1999/00
Prof. Alan Bertossi
Oggetto e obiettivi del corso
Il termine "algoritmo" indica la descrizione delle azioni che un esecutore
deve compiere per ricavare la soluzione di un problema computazionale.
Scopo del corso è fornire i fondamenti per:
-
Caratterizzare i dati da elaborare, organizzandoli e strutturandoli in
modo da agevolarne l'uso da parte degli algoritmi che li elaborano;
-
Progettare algoritmi corretti (cioè che risolvono sempre e solo
il problema cui si è interessati) ed efficienti (cioè che
lo risolvono il più velocemente possibile);
-
Studiare le inerenti limitazioni e difficoltà di classi di problemi
da risolvere;
-
Illustrare proprietà di linguaggi di programmazione atti a descrivere
algoritmi.
Programma
-
Strutture di dati
Dizionari e tabelle hash. Code con priorità e heap. Heapsort.
Alberi bilanciati di ricerca: AVL e 2-3-4. MFSET. Grafi orientati e non
orientati. Visite di un grafo: Depth-First-Search (DFS) e Breadth-First-Search
(BFS).
-
Progetto di algoritmi
Strutture di dati e progetto di algoritmi. Tecniche di progetto: divide-et-impera,
backtrack, greedy, programmazione dinamica, e ricerca locale. Algoritmi
per CAMMINI MINIMI, STRING-MATCHING, ORDINAMENTO, MINIMO ALBERO DI COPERTURA,
INVILUPPO CONVESSO, MOLTIPLICAZIONE DI POLINOMI, MOLTIPLICAZIONE DI MATRICI.
-
Complessità
Non determinismo ed enumerazione. Le classi P ed NP. Teorema di Cook-Levin.
NP-completezza per: DOMINO LIMITATO, CRICCA, SODDISFATTIBILITA', PROGRAMMAZIONE
LINEARE 0/1, COMMESSO VIAGGIATORE, PARTIZIONE, COLORAZIONE DI GRAFI. Gerarchia
di complessità. Algoritmi pseudo-polinomiali. Algoritmi di approssimazione.
Algoritmi branch-&-bound. Euristiche. Esempi di algoritmi per il COMMESSO
VIAGGIATORE.
Testi adottati
A.A. BERTOSSI, Strutture, Algoritmi, Complessità, Edizioni
Culturali Internazionali (ECIG), Genova, 1990
J. WELSH & J. ELDER, Introduzione al Pascal, ESA, Roma,
1987 (2a edizione)
Testi di consultazione
T.H. CORMEN, C.E. LEISERSON & R.L. RIVEST, Introduction to Algorithms,
The MIT Press/McGraw-Hill, 1991
H.R. LEWIS & C.H. PAPADIMITRIOU, Elements of the Theory of Computation,
Prentice-Hall, 1982
Modalità e svolgimento dell'esame
Per il Modulo I è prevista una prova scritta seguita da una verifica
pratica di programmazione su personal computer.
Per il Modulo II è invece prevista una prova orale.