Algorithm design
Insegnamento: Algorithm Design
Titolo insegnamento in inglese: Algorithm Design
Lingua: italiano
Anno di corso: 2
Semestre: 2
CFU: 6
Insegnamenti propedeutici previsti: Nessuno.
Docenti:
- Massimo Benerecetti
Obiettivi Formativi
Il corso intende fornire un’introduzione alle tecniche avanzate di progettazione degli algoritmi, alla complessità computazionale e alla trattabilità dei problemi. Vengono, in particolare, presentate le principali tecniche di dimostrazione di correttezza, esaminate le tecniche di progettazione greedy e di programmazione dinamica, con applicazioni alla soluzione di vari problemi di ottimizzazione (pianificazione di attività, problemi su grafi pesati, clustering, ecc.). Vengono introdotte le classi di complessità P e NP, il concetto di NP-completezza e di riduzione tra problemi. Vengono infine presentate tecniche di progettazione ed analisi di algoritmi approssimati e di ricerca locale per la soluzione di problemi computazionalmente difficili.
Programma
Il problema della correttezza degli algoritmi: dimostrazioni per induzione e dimostrazioni di correttezza di algoritmi ricorsivi. Tecniche di progettazione di algoritmi: tecnica divide et impera, algoritmi greedy e programmazione dinamica, applicati alla soluzione di problemi di ottimizzazione (problema dello zaino, percorsi minimi su grafi pesati, allineamento di sequenze, scheduling di attività). Algoritmi per il calcolo del flusso su reti e loro applicazioni: massimo flusso e segmentazione di immagini. Problemi trattabili e non trattabili: le principali classi di complessità (P e NP); riduzioni polinomiali tra problemi; il concetto di NP-completezza; esempi di problemi NP-completi; dimostrazioni di NP-completezza. Introduzione all'intrattabilità computazionale: algoritmi approssimati e fattore di approssimazione. Algoritmi di ricerca locale e applicazioni a problemi di machine learning.
Modalità didattiche
Lezioni frontali.
Materiale didattico
Jon Kleinberg e Eva Tardos: Algorithm Design, Addison-Wesley
Modalità di esame
L'esame si articola in prova scritta ed orale.
La prova scritta consta di quesiti a risposte libere (es: sviluppo progetti, prova al calcolatore ...).