Il corso tratta le principali metodologie di progettazione di algoritmi (incrementale, ricorsiva, programmazione dinamica, algoritmi golosi), le tecniche per l'analisi di complessità, sia nel caso pessimo che nel caso medio, nonché gli strumenti per l'implementazione degli algoritmi e delle strutture dati trattate.Il linguaggio Python verrà usato come strumento principale per presentare le implementazioni delle strutture dati e degli algoritmi.

PROGRAMMA DETTAGLIATO

Introduzione
Algoritmi come tecnologia per risolvere problemi computazionali. Metodologia incrementale. Metodologia divide-et-impera.
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

Ordinamento in tempo lineare. Mediane e statistiche d'ordine.

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

Algoritmi elementari per grafi
Visita in ampiezza. Visita in profondità (classificazione degli archi). Ordinamento topologico. Componenti fortemente connesse.

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.

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.