Descrizione generale del corso

Il corso presenta le principali metodologie di progettazione di algoritmi (incrementale, ricorsiva, programmazione dinamica, algoritmi golosi) e le tecniche per l'analisi di complessità, sia nel caso pessimo che nel caso medio.



PROGRAMMA PARTICOLAREGGIATO DEL CORSO

Introduzione
Problemi computazionali e algoritmi: il problema dell'ordinamento
Algoritmi come tecnologia
Metodologia incrementale: algoritmo Insertion-Sort (correttezza e complessità)
Metodologia divide-et-impera: algoritmo Merge-Sort (complessità)
Notazioni asintotiche e relazioni tra esse
Notazioni standard e funzioni comuni

Ricorrenze
Il metodo di sostituzione
Il metodo iterativo e dell'albero di ricorsione
Il teorema master

Ordinamento e statistiche d'ordine

Heap e procedura per la sua costruzione
L'algoritmo Heapsort
Code di priorità
L'algoritmo Quicksort e sua versione randomizzata
Analisi di Quicksort nel caso peggiore e nel caso medio
Limiti inferiori per l'ordinamento
Ordinamento in tempo lineare: algoritmi Counting-Sort, Radix-Sort, Bucket-Sort
Mediane e statistiche d'ordine

Hashing
Tabelle hash
Funzioni hash (metodo della divisione, metodo della moltiplicazione, hashing universale)
Indirizzamento aperto

Alberi rosso-neri
Rotazioni, inserimenti, cancellazioni
Analisi di complessità

Elementi della programmazione dinamica
Sottostruttura ottima, ripetizione dei sottoproblemi, ricostruzione di una soluzione ottima
Alcuni casi di studio: programmazione delle catene di montaggio, moltiplicazione di una sequenza di matrici, la più lunga sottosequenza comune, distanza di editing

Elementi della strategia golosa
Proprietà della scelta golosa, sottostruttura ottima
Alcuni casi di studio: problema della selezione di attività, costruzione di un codice di Huffman

Algoritmi elementari per grafi
Cammini minimi da sorgente unica: algoritmo di Bellman-Ford, cammini minimi da sorgente unica nei grafi orientati aciclici, algoritmo di Dijkstra
Cammini minimi tra tutte le coppie: algoritmo di Floyd-Warshall, chiusura transitiva di un grafo orientato

Il libro di testo consigliato è:

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts, 2009

disponibile anche nella traduzione italiana

1) T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati 3/ed, McGraw-Hill Italia, 2010.

Descrizione generale del corso

Il corso presenta le principali metodologie di progettazione di algoritmi (incrementale, ricorsiva, programmazione dinamica, algoritmi golosi) e le tecniche per l'analisi di complessità, sia nel caso pessimo che nel caso medio.



PROGRAMMA PARTICOLAREGGIATO DEL CORSO

Introduzione
Problemi computazionali e algoritmi: il problema dell'ordinamento
Algoritmi come tecnologia
Metodologia incrementale: algoritmo Insertion-Sort (correttezza e complessità)
Metodologia divide-et-impera: algoritmo Merge-Sort (complessità)
Notazioni asintotiche e relazioni tra esse
Notazioni standard e funzioni comuni

Ricorrenze
Il metodo di sostituzione
Il metodo iterativo e dell'albero di ricorsione
Il teorema master

Ordinamento e statistiche d'ordine

Heap e procedura per la sua costruzione
L'algoritmo Heapsort
Code di priorità
L'algoritmo Quicksort e sua versione randomizzata
Analisi di Quicksort nel caso peggiore e nel caso medio
Limiti inferiori per l'ordinamento
Ordinamento in tempo lineare: algoritmi Counting-Sort, Radix-Sort, Bucket-Sort
Mediane e statistiche d'ordine

Hashing
Tabelle hash
Funzioni hash (metodo della divisione, metodo della moltiplicazione, hashing universale)
Indirizzamento aperto

Alberi rosso-neri
Rotazioni, inserimenti, cancellazioni
Analisi di complessità

Elementi della programmazione dinamica
Sottostruttura ottima, ripetizione dei sottoproblemi, ricostruzione di una soluzione ottima
Alcuni casi di studio: programmazione delle catene di montaggio, moltiplicazione di una sequenza di matrici, la più lunga sottosequenza comune, distanza di editing

Elementi della strategia golosa
Proprietà della scelta golosa, sottostruttura ottima
Alcuni casi di studio: problema della selezione di attività, costruzione di un codice di Huffman

Algoritmi elementari per grafi
Cammini minimi da sorgente unica: algoritmo di Bellman-Ford, cammini minimi da sorgente unica nei grafi orientati aciclici, algoritmo di Dijkstra
Cammini minimi tra tutte le coppie: algoritmo di Floyd-Warshall, chiusura transitiva di un grafo orientato

Il libro di testo consigliato è:

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts, 2009

disponibile anche nella traduzione italiana

1) T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati 3/ed, McGraw-Hill Italia, 2010.

Il modulo di Laboratorio di Algoritmi ha lo scopo di fornire gli strumenti per l'implementazione degli algoritmi e delle strutture dati trattate nel corso di Algoritmi, attraverso l'utilizzo della programmazione ad oggetti. Il linguaggio C++ verrà usato come strumento principale per presentare le implementazioni delle strutture dati e degli algoritmi.

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts, 2009. La versione in lingua originale è obbligatoria.

Il modulo di Laboratorio di Algoritmi ha lo scopo di fornire gli strumenti per l'implementazione degli algoritmi e delle strutture dati trattate nel corso di Algoritmi, attraverso l'utilizzo della programmazione ad oggetti. Il linguaggio C++ verrà usato come strumento principale per presentare le implementazioni delle strutture dati e degli algoritmi.

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts, 2009. La versione in lingua originale è obbligatoria.