Il corso intende fornire agli studenti una descrizione delle principali tecniche matematiche utilizzate nell'analisi degli algoritmi, in particolare quelle che utilizzano il concetto di funzione generatrice, e si focalizza sull'analisi del caso medio sebbene le tecniche illustrate siano le stesse utilizzate nell'analisi del caso peggiore. Il corso è integrato con la presentazione di un sistema di calcolo simbolico per l'approfondimento e la verifica degli argomenti trattati.
R. H. Greene and D. E. Knuth, “Mathematics for the Analysis of Algorithms”, Second Edition, Birkhauser, 1982.
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:
Lo studente acquisisce conoscenze sulle principali tecniche matematiche utilizzate nell’analisi degli algoritmi e delle strutture dati.
Competenze acquisite
Lo studente acquisisce le competenze per ottenere previsioni precise e matematicamente rigorose circa le prestazioni degli algoritmi e delle strutture dati. Le tecniche acquisite si applicano soprattutto all’analisi del caso medio ma possono essere utilizzate anche nell’analisi del caso peggiore. Acquisisce inoltre la conoscenza di un sistema di manipolazione simbolica che viene utilizzato come strumento di approfondimento e verifica degli argomenti trattati nel corso.
Capacità acquisite al termine del corso:
Lo studente acquisisce 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
Corsi raccomandati: Programmazione, Algoritmi e Strutture Dati, Analisi I: Calcolo Differenziale e Integrale, Calcolo delle Probabilità e Statistica.
Metodi Didattici
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
Orario di ricevimento
Su appuntamento tramite e-mail
Modalità di verifica apprendimento
Esame orale e progetto in Maple oppure, in alternativa, studio e simulazione con Maple di articoli scientifici della letteratura recente sull'analisi degli algoritmi.
Programma del corso
Analisi di un algoritmo e di una struttura dati: caso medio e caso pessimo. Numeri speciali. Funzioni generatrici. Estrazione del coefficiente di una funzione generatrice. Il metodo di inversione di Lagrange. Il metodo simbolico per lo studio di proprietà di strutture dati. Manipolazione simbolica con il sistema Maple. Simulazione al calcolatore per la verifica dei risultati. Applicazioni: algoritmi classici di ricerca e ordinamento, strutture ad albero, linguaggi regolari e liberi dal contesto, ecc.