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
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. 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.
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
Esame orale sulle tecniche per l'analisi di algoritmi e strutture dati.
Progetto di verifica e/o simulazione nel contesto dell'analisi di algoritmi e strutture dati, utilizzando un sistema di calcolo simbolico.
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.