Obiettivi formativi L’insegnamento fornisce agli studenti i fondamenti teorici e pratici della progettazione e dell’analisi degli algoritmi. Il corso affronta le principali tecniche di progettazione algoritmica, tra…
Scheda dell'insegnamento
Obiettivi formativi
Obiettivi formativi
L’insegnamento fornisce agli studenti i fondamenti teorici e pratici della progettazione e dell’analisi degli algoritmi. Il corso affronta le principali tecniche di progettazione algoritmica, tra cui algoritmi greedy, divide et impera e algoritmi per grafi, introducendo inoltre concetti di complessità computazionale e di trattabilità dei problemi. Al termine del corso gli studenti saranno in grado di analizzare la correttezza e l’efficienza degli algoritmi, confrontare diverse strategie risolutive e progettare soluzioni algoritmiche per problemi di media complessità.
Conoscenza e capacità di comprensione
Gli studenti acquisiscono una solida conoscenza dei principali paradigmi di progettazione algoritmica, delle strutture dati fondamentali e degli algoritmi classici per problemi di ottimizzazione, codifica, scheduling e cammini minimi. Comprendono i metodi di analisi della complessità computazionale e i principi di correttezza degli algoritmi.
Capacità di applicare conoscenza e comprensione
Gli studenti sono in grado di modellare problemi computazionali, individuare la strategia algoritmica più appropriata, progettare algoritmi corretti ed efficienti, analizzarne la complessità temporale e spaziale e confrontare soluzioni alternative sulla base delle loro prestazioni.
Autonomia di giudizio
Gli studenti sviluppano la capacità di valutare criticamente algoritmi e strutture dati, individuandone punti di forza, limiti e ambiti di applicabilità. Sono inoltre in grado di motivare le proprie scelte progettuali considerando correttezza, efficienza e vincoli del problema.
Abilità comunicative
Gli studenti acquisiscono la capacità di descrivere algoritmi e dimostrarne la correttezza utilizzando un linguaggio tecnico appropriato, pseudocodice e notazione matematica. Sono inoltre in grado di presentare in modo chiaro il processo di progettazione e l’analisi della complessità delle soluzioni proposte.
Capacità di apprendimento
Gli studenti sviluppano un metodo di studio autonomo che consente loro di approfondire nuovi algoritmi, tecniche di progettazione e risultati teorici, applicando in modo critico le conoscenze acquisite anche a problemi non affrontati direttamente durante il corso.
Programma
Algoritmi
Gale-Shapley
Greedy: Interval Scheduling, Interval Partitioning, Codici di Huffman
Programmazione dinamica: Weighted Interval Scheduling, Segmentation, Subset-Sum
Introduzione agli Algoritmi di approssimazione e ad online learning (problema degli esperti)
- Introduzione agli algoritmi
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 1
- L’algoritmo di Gale-Shapley
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 1
- Limiti di tempo di esecuzione e notazione asintotica
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 2.1, 2.2
- Strutture dati
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 2.3, 2.4, 2.5
- Algoritmi greedy
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 4.1
- Interval Scheduling
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 4.1
- Interval Partitioning
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 4.1
- Posizionamento di trasmettitori radio
- Grafi
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 3
- Algoritmo di Dijkstra
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 4.4
- Heap
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 2.5
- Code di priorità e cammini minimi
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 2.5 , 4.4
- Codifica con prefisso
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 4.8
- Algoritmo di Huffman (1)
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 4.8
- Algoritmo di Huffman (2)
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 4.8
- Weighted Interval Scheduling
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 6.1, 6.2
- Segmentazione
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 6.3
- Subset Sum
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 6.4
- Bellman-Ford
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 6.8, 6.9
- Divide-and-Conquer
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 5
- Moltiplicazione di interi
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 5.5
- P e NP
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 8
- Vertex Cover
- Testi di riferimento: "Design of Algorithms", Jon Kleinberg and Eva Tardos - Capitolo 8
Modalità d'esame
Prova scritta
- Tipologia: test individuale composto da quesiti a risposta aperta e problemi pratici di analisi e progettazione di algoritmi.
- Obiettivi: verificare la conoscenza dei concetti teorici di base e la capacità di progettare e analizzare algoritmi.
- Criteri di valutazione: correttezza delle risposte, chiarezza e completezza delle spiegazioni, correttezza degli algoritmi proposti e capacità di analizzarne complessità e prestazioni.
Valutazione finale
- Il voto è espresso in trentesimi.
- Per superare l’esame (18/30), lo studente deve dimostrare di aver acquisito una conoscenza sufficiente dei concetti fondamentali di algoritmi e di saper risolvere problemi pratici con algoritmi corretti e analisi elementari della complessità.
- Per conseguire il punteggio massimo (30/30 e lode), lo studente deve dimostrare una conoscenza eccellente dei concetti trattati durante il corso, essere in grado di risolvere problemi complessi proponendo algoritmi corretti ed efficienti, in modo coerente e giustificare le scelte progettuali con spiegazioni rigorose e complete.
Testi di riferimento
"Algorithm Design", Kleinberg, Tardos
Dispense fornite dal docente
"Algorithm Design", Kleinberg, Tardos
"Introduction to Algorithms", Cormen, Leiserson, Rivest, Stein
"Automata and computatability", Kozen
Codice insegnamento 1049269