Analisi degli algoritmi e complessità computazionale. Numeri speciali. Relazioni di ricorrenza. Funzioni generatrici. L'inversione di Lagrange. Metodi esatti e metodi approssimati. Il metodo simbolico. Espressioni regolari e grammatiche context-free: la metodologia di Chomsky-Schutzenberger. Simulazione di algoritmi e strutture dati e relativi test statistici.
- D. E. Knuth, The art of computer programming, Vol. 1-3, Addison-Wesley, 1973.
- R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996.
Obiettivi Formativi
Conoscenze - Il corso intende fornire agli studenti conoscenze sulle principali tecniche utilizzate nell'analisi degli algoritmi e delle strutture dati. Il corso si focalizza soprattutto sull'analisi del caso medio sebbene le tecniche matematiche illustrate siano le stesse utilizzate anche nell'analisi del caso peggiore ed è integrato con la presentazione di un sistema di manipolazione simbolica che viene utilizzato come strumento per l'approfondimento e la verifica degli argomenti trattati.
Competenze acquisite - Una volta sostenuto con successo l'esame relativo all'insegnamento, lo studente avrà acquisito le competenze e la capacità di manipolare strumenti matematici per risolvere problemi di analisi di algoritmi e strutture dati nonché a verificare i risultati teorici, o le ipotesi, tramite la simulazione al calcolatore e gli opportuni test statistici, utilizzando un sistema di calcolo simbolico.
Capacità acquisite alle fine del corso - Gli studenti saranno in grado di valutare in modo esatto o tramite l'uso di strumenti di calcolo simbolico la complessità di un algoritmo o di una strutture dati a partire dalla relazione matematica che ne descrive la caratteristica di interesse.
Prerequisiti
Concetti di base di algoritmi e strutture dati
Metodi Didattici
CFU: 6
Numero di ore totali del corso: 150
Numero di ore per studio personale e altre attività formative di tipo individuale: 102
Numero di ore relative alle attività in aula: 48
Altre Informazioni
Frequenza delle lezioni ed esercitazioni: raccomandata
Strumenti a supporto della didattica UniFi E-Learning: http://e-l.unifi.it
Orario di ricevimento
Prof. D. Merlini
Previo appuntamento via e-mail.
Dipartimento di Statistica, Informatica, Applicazioni
Viale Morgagni, 65
50134 - Firenze (FI)
Tel: 055 2751509
E-Mail: donatella.merlini@unifi.it
Modalità di verifica apprendimento
L'esame consiste nelle seguenti attività:
- Esame orale con esercizi e domande sulle tecniche per l'analisi di algoritmi e strutture dati presentate durante le lezioni.
- Un progetto (da svolgere in piccoli gruppi, massimo tre persone) che consiste in una verifica e/o simulazione nel contesto dell'analisi di algoritmi e strutture dati utilizzando un sistema di calcolo simbolico.
Il voto finale sarà calcolato come media del voto dell'esame orale e del progetto.
Programma del corso
Analisi degli algoritmi e complessità computazionale. Caso medio e caso pessimo. Numeri speciali. Relazioni di ricorrenza: metodi di risoluzione. Ricorrenze divide et impera. Funzioni generatrici ed estrazione dei loro coefficienti. L'inversione di Lagrange. Metodi esatti e metodi approssimati. Il metodo simbolico. Epressioni regolari e grammatiche context-free: la metodologia di Chomsky-Schutzenberger. Esempi di analisi di algoritmi classici, sugli alberi, sulle permutazioni e sulle parole. Simulazione di algoritmi e strutture dati e relativi test statistici.