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:
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein (2009). Introduzione agli algoritmi, 3rd ed,
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, le idee fondamentali della matematica discreta (calcolo combinatorio, serie, sommatorie,
induzione matematica) e della teoria della probabilità (variabili aleatorie, distribuzioni, valori attesi).
Precedenze di esame: per affrontare l'esame è necessario aver superato gli esami di Fondamenti di informatica e di Analisi Matematica I (o Elementi di Analisi Matematica)
Metodi Didattici
lezioni, esercitazioni
Altre Informazioni
Nessuna
Modalità di verifica apprendimento
La verifica finale è basata su una prova scritta e una prova orale.
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.
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.
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 ottima 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.
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 dati per insiemi disgiunti. Analisi. Algoritmo di Kruskal. Analisi.