LABORATORIO DI INFORMATICA (m)
2oMODULO
A. A. 1996-97
Prof. Alan A .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.
Argomenti effettivamente svolti
- 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.
Date dei prossimi appelli d'esame:
Scritto: 30.9.97 ore 15,00
Orale: 30.9.97 ore 15,00