Programma del corso di Informatica II
Antonio Brogi
a.a. 2002/2003
Obiettivi:
- definire formalmente la nozione di algoritmo e fornire gli strumenti per
analizzare lâefficienza di algoritmi;
- caratterizzare i dati da elaborare, organizzandoli e strutturandoli in
modo da agevolare il loro utilizzo da parte degli algoritmi;
- 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:
- Analisi di algoritmi:
definizione di algoritmo, progettazione di semplici algoritmi, analisi
della complessita' di un algoritmo, notazioni asintotiche.
- Strutture Dati:
astrazione dei dati, specifica e realizzazione; array e strutture,
liste, pile e code; insiemi e tabelle hash.
- Progetto di algoritmi:
ordinamento per inserzione; algoritmi "divide-et-impera"; ordinamento
rapido (quick sort), per fusione (merge sort), ordinamento in tempo lineare
(counting sort).
Materiale didattico:
- A. Brogi. Appunti di algoritmi e strutture dati. Universita' di
Pisa, 2002.
Testi di consultazione:
- E. Horowitz, S. Sahni, S. Anderson-Freed. Strutture dati in C.
Mc-Graw Hill, 1993 (ISBN 88-386-0631-5).
- Al Kelley, Ira Pohl. C: Didattica e programmazione.
Addison-Wesley, 1996 (ISBN 88-7192-060-0).
Modalita' d'esame:
Realizzazione di un
progetto e
prova orale conclusiva.
ultimo aggiornamento: 14 novembre 2005