Introduzione, analisi, divide et impera.
Ordinamento e code con priorità.
Dizionari: tabelle hash, alberi binari di ricerca.
Programmazione dinamica.
Algoritmi elementari sui grafi.
Alberi di copertura minimi.
Cammini minimi.
Esempi di implementazione ed applicazioni degli algoritmi trattati nel corso.
Libro di testo ufficiale:
[CLRS09] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein (2009). Introduzione agli algoritmi, 3rd ed,
Può essere utile la consultazione di:
[MR05] B. N. Miller and D. L. Ranum (2005). Problem Solving with Algorithms and Data Structures Using
Python, Franklin, Beedle & Associates Inc. Amazon link.
Obiettivi Formativi
Obiettivo del corso è quello di fornire le conoscenze sui principali algoritmi e strutture dati e sui metodi di analisi degli algoritmi.
- Conoscenza del concetto di complessità asintotica di algoritmi
- Conoscenza dei metodi di calcolo della complessità asintotica per algoritmi iterativi e ricorsivi
- Conoscenza delle principali strutture dati: liste concatenate, alberi binari di ricerca, alberi rosso-neri, tabelle hash, alberi B, grafi
- Conoscenza dei principali algoritmi operanti sulle precedenti strutture dati
- Conoscenza di tecniche avanzate di progettazione ed analisi: programmazione dinamica, analisi ammortizzata
Al termine del corso lo studente conoscerà i principali algoritmi e strutture dati e sarà in grado di comprendere ed applicare metodi per
analizzare il tempo di esecuzione degli algoritmi, mostrare la loro correttezza, utilizzare soluzioni algoritmiche adeguate per
risolvere problemi concreti.
Prerequisiti
I prerequisiti necessari includono una buona comprensione della programmazione procedurale e orientata
agli oggetti, le idee fondamentali della matematica discreta (calcolo combinatorio, serie, sommatorie,
induzione matematica) e della teoria della probabilità (variabili aleatorie, distribuzioni, valori attesi).
Normalmente dovete aver frequentato i corsi B003262 - (Fondamenti di informatica), B003271 -
(Geometria, algebra lineare e calcolo numerico), e B003426 (Laboratorio di tecnologie dell'informazione) e
superato i corrispondenti esami.
Metodi Didattici
lezioni, esercitazioni
Altre Informazioni
Nessuna
Modalità di verifica apprendimento
La verifica finale è basata su una prova scritta e una prova orale.
A metà corso ha luogo una prova intermedia. Se l'esito della prova intermedia è >= 18 è possibile svolgere la prova scritta finale solo sulla parte restante del programma,
La verifica finale (scritto e orale) è finalizzata a verificare le capacità di:
- Saper descrivere i principali algoritmi, anche tramite pseudo-codice, e il loro funzionamento
- Saper scegliere un algoritmo per risolvere un problema pratico confrontando aspetti positivi e negativi di algoritmi alternativi
- Saper verificare la correttezza di un algoritmo
- Saper analizzare un algoritmo (calcolare la complessità asintotica relativa al tempo di esecuzione e allo spazio di memoria utilizzato).
Maggiori dettagli su sito di e-learning del corso.
Programma del corso
Algoritmi: introduzione all'analisi e pseudocodice. Esempi: Insertion-Sort e
Merge-Sort. Correttezza. Applicazione del principio di induzione matematica. Ricorsione. Invarianti di
ciclo. Analisi degli algoritmi. Notazione asintotica e crescita delle funzioni. Significato pratico e
definizioni matematiche delle classi O, Theta e Omega.
Divide et Impera. Idee generali. Ricorrenze e tecniche risolutive: metodo della sostituzione. Esempi.
Teorema fondamentale. Esempi. Calcolo di potenze intere. Moltiplicazione di matrici e algoritmo di Strassen. Quicksort. Analisi del caso peggiore e
migliore. Analisi di quicksort randomizzato. Code con priorità loro e realizzazione con max-heaps.
Ordinamento in tempo lineare: confine asintotico inferiore per gli algoritmi basati su confronto.
Ordinamento per conteggio. Radix-Sort. Calcolo di statistiche. Selezione randomizzata. Analisi del caso
medio. Applicazioni.
Dizionari. Tabelle ad indirizzamento diretto. Tabelle hash. Collisioni. Chaining e relativa analisi. Metodo
della divisione e della moltiplicazione. Indirizzamento aperto. Sondaggio lineare e doppio hash. Analisi.
Tabelle dinamiche e analisi ammortizzata degli algoritmi. Alberi binari di ricerca. Definizioni. Visite.
Ricerca. Analisi. Massimo, minimo, successore e predecessore. Inserimento. Cancellazione.
Altezza attesa degli alberi binari construiti da una sequenza casuale di chiavi.
Alberi bilanciati. Alberi red-black. Definizione. Relazione tra altezza e numero di nodi. Inserimento.
Correttezza. Statistiche d'ordine dinamiche. Selezione e rango con alberi
RB. Generalità su strutture dati aumentate. Applicazioni.
Programmazione dinamica. Il problema della sottosequenza comune più lunga. Definizione. Algoritmo
per bruta forza. Sottostruttura ottimale di una sottosequenza comune più lunga. Algoritmo ricorsivo e
versione tabellare. Esempi. Distanza di Levenshtein.
Grafi. Definizioni fondamentali. Esempi. Matrici e liste di adiacenza. Visita in ampiezza. Analisi e
proprietà. Visita in profondità. Teorema delle parentesi e classificazione degli archi. Relazione tra BFS e
DFS. Iterative deepening. Ordinamento topologico nei DAG. Calcolo delle componenti fortemente
connesse nei grafi orientati. Alberi di copertura minimi. Definizioni. Ottimalità dei sottoproblemi.
Proprietà del taglio e scelta golosa. Algoritmi di Prim. Analisi. Cenni sull'analisi ammortizzata. Strutture
per insiemi disgiunti. Analisi. Algoritmo di Kruskal. Analisi.