Algoritmi e Strutture Dati

Antonio Brogi

Diploma in Metodologie Fisiche
A.A. 1998/99

Programma del corso

Obiettivi del corso:
(a) definire formalmente la nozione di algoritmo e fornire gli 
    strumenti per analizzare l’efficienza di algoritmi;
(b) caratterizzare i dati da elaborare, organizzandoli e strutturandoli
    in modo da agevolare il loro utilizzo da parte degli algoritmi;
(c) descrivere la progettazione di algoritmi efficienti.

Le lezioni saranno integrate con esercitazioni dedicate alla
realizzazione ed alla sperimentazione di algoritmi in laboratorio.
Per la programmazione verra' utilizzato il linguaggio C, gia' 
introdotto nel corso di Informatica.

Argomenti principali del corso:
1. Analisi di algoritmi:
     definizione di algoritmo, progettazione di semplici algoritmi,
     analisi della complessita' di un algoritmo, notazione asintotica.
2. Strutture Dati:
     astrazione dei dati, specifica e realizzazione; array e strutture,
     liste, pile e code; alberi e visite, alberi binari e alberi di
     ricerca, grafi. 
3. Progetto di algoritmi:
     ordinamento per inserzione; algoritmi "divide-et-impera";
     ordinamento rapido (quick sort), per fusione (merge sort). 
     

Testo di riferimento:
 - E. Horowitz, S. Sahni, S. Anderson-Freed. 
   Strutture dati in C. 
   Mc-Graw Hill, 1993 (ISBN 88-386-0631-5). 

Testo di consultazione: 
 - Al Kelley, Ira Pohl.
   C: Didattica e programmazione.
   Addison-Wesley,  1996 (ISBN 88-7192-060-0).
 
 - G. Fiorentino, M.R. Lagana', F. Romani, F. Turini. 
   C e Java: laboratorio di programmazione. 
   Mc-Graw Hill, 1997 (ISBN 88-386-0739-7).

Modalita' d'esame: 
Per il superamento dell'esame gli studenti devono svolgere alcuni
esercizi in laboratorio durante il corso (verifiche periodiche) ed 
un progetto alla fine del corso. La presentazione del progetto da' 
accesso alla prova orale conclusiva.