Programma Preliminare Algoritmi e Strutture Dati + Laboratorio (Corso A) a.a.2002/2003 Docente: Esposito Floriana 1. Algoritmi e programmi Lo sviluppo del software e la qualitą dei programmi. Principi di progettazione e tecniche di programmazione. Il ruolo delle tecniche di astrazione nel progetto di programmi: Astrazione dei dati e astrazione funzionale. 2. Algebre di dati Dati e rappresentazioni, requisiti delle astrazioni di dati, costrutti. Astrazioni di dati e dati primitivi. Specifica sintattica e semantica tramite pre- e post-condizioni sulle operazioni. La realizzazione. 3. Strutture lineari di dati Liste: specifiche, realizzazioni attraverso rappresentazioni sequenziali e collegate. Pile: specifiche e realizzazioni alternative, pile e procedure ricorsive. Code: specifiche e realizzazioni alternative. Scelta, implementazione e verifica di algoritmi per la ricerca, l'ordinamento e la fusione delle strutture dati proposte. 4. Insiemi e Dizionari Insiemi: specifiche e confronto tra realizzazioni alternative. Dizionari: realizzazioni con vettori ordinati e con tabelle Hash. 5. Strutture non lineari di dati I grafi: generalitą. Gli alberi come grafi: alberi ordinati, proprietą. Alberi binari: caratteristiche, la corrispondenza con le liste, specifiche e realizzazioni, visite. Alberi n-ari: specifiche, visita di alberi, realizzazioni alternative. Algoritmi su alberi binari ed n-ari: visite, inserimento di un valore e ricerca di un valore. Il tipo astratto GRAFO: specifiche sintattiche e semantiche. Realizzazioni mediante matrici di adiacenza e di incidenza, vettori di adiacenza, liste di adiacenza, realizzazione con puntatori. Algoritmi su grafi: visita di un grafo e generazione del minimo albero di copertura 6. Code con prioritą Generalitą. Specifiche e realizzazioni con liste, con alberi binari, con heap. 7. Alberi di ricerca Alberi bilanciati di ricerca. Alberi AVL: generalitą e specifiche. Algoritmi di inserimento, cancellazione e ricerca. 8. Le tecniche algoritmiche Classificazione dei problemi: problemi di ricerca, di decisione, di ottimizzazione. Lo spazio di ricerca: definizione e proprietą. Le tecniche algoritmiche: il paradigma selettivo e il paradigma generativo. Tecnica dell'enumerazione, del backtracking, la tecnica greedy, la tecnica divide- et-impera. Problemi e metodi solutivi: string matching (Knuth-Morris- Pratt), partizionamento di insiemi, problema delle N Regine, problema dello zaino, problema del commesso viaggiatore, ricerca del percorso pił breve in un grafo (Dijkstra), minimo albero di copertura (Kruskal), selezione di attivitą. Libri consigliati - A. A. Bertossi, ''Algoritmi e strutture dati'',UTET, 2000 - Dispense del corso Riferimenti - E. Lodi, G. Pacini,''Introduzione alle strutture di dati'', Bollati Boringhieri, 1990, cap. 3-4-5. - M. Cadoli, M. Lenzerini, P. Naggar, A. Schaerf,''Fondamenti della progettazione dei programmi'',Cittą studi Edizioni 1997, cap. 1-2-7-8-15.