Algoritmi greedy. Programmazione dinamica. Divide et impera. Algoritmi su grafi. Ricerca all'interno di testi. Algoritmi probabilistici. 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.
J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005
Obiettivi Formativi
Il corso intende fornire agli studenti una descrizione completa delle principali tecniche utilizzate nella progettazione e 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. In particolare, nel corso vengono trattati argomenti
matematici classici, come la matematica discreta e la combinatoria, cosÏ come argomenti di informatica che includono gli algoritmi e le strutture dati. Il corso è 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 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.
Prerequisiti
Nessuno
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. M.C. Verri
Previo appuntamento via e-mail.
Dipartimento di Statistica, Informatica, Applicazioni
Viale Morgagni, 65
50134 - Firenze (FI)
Tel: 055 4237439 Fax: 055 4237436
E-Mail: mariacecilia.verri@unifi.it
Prof. D. Merlini
Previo appuntamento via e-mail.
Dipartimento di Statistica, Informatica, Applicazioni
Viale Morgagni, 65
50134 - Firenze (FI)
Tel: 055 4237440 Fax: 055 4237436
E-Mail: donatella.merlini@unifi.it
Modalità di verifica apprendimento
Esame orale e progetto
Programma del corso
Algoritmi greedy esatti: il problema dello scheduling, il metodo di Huffman, il problema dei cammini minimi. Algoritmi greedy approssimati: distribuzione del carico di lavoro, il problema della selezione dei centri. Divide et impera: il teorema fondamentale delle ricorrenze, il problema della coppia di punti più vicini, il conteggio delle inversioni. Programmazione dinamica: scheduling di intervalli pesati, sottovettori di valore massimo. Algoritmi su grafi. Ricerca all'interno di testi. Algoritmi probabilistici.
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.