Heuristic algorithms

A.A. 2020/2021
6
Crediti massimi
48
Ore totali
SSD
INF/01
Lingua
Inglese
Obiettivi formativi
L'insegnamento si propone di
- illustrare i principali paradigmi per progettare algoritmi euristici per problemi decisionali complessi, con particolare riferimento ai problemi di ottimizzazione combinatoria
- discutere i metodi di valutazione a priori e a posteriori dell'efficacia e dell'efficienza degli algoritmi euristici
- svolgere attività sperimentale progettando algoritmi euristici in base allo studio del problema, realizzandoli su calcolatore in un linguaggio di programmazione, valutandone e confrontandone le prestazioni su dati di benchmark
Risultati apprendimento attesi
Lo studente apprenderà le principali tecniche di progetto di algoritmi euristici e di valutazione quantitativa delle loro prestazioni.
Imparerà a progettare e realizzare in un linguaggio di programmazione algoritmi euristici e a valutarne le prestazioni.
Programma e organizzazione didattica

Edizione unica

Responsabile
Periodo
Primo semestre
Verranno rese disponibili lezioni asincrone (videolezioni costituite da registrazione
del desktop del docente con commento audio), organizzate per coprire gli argomenti
in programma. Le lezioni previste dall'orario costituiranno un momento di revisione
e approfondimento di quanto proposto in modalità asincrona, e verranno svolte
utilizzando la piattaforma MS-Teams.
Le modalità e i criteri per partecipare alle lezioni in presenza saranno pubblicate
per tempo nelle pagine Ariel e sulla pagina ufficiale dell'insegnamento, come pure
tutto il materiale e gli avvisi relativi ad aggiornamenti legati all'evoluzione
della normativa imposta dal Covid-19.
Programma
L'insegnamento si propone di:
- presentare tecniche generali per il progetto, la realizzazione e la valutazione di algoritmi euristici
- fornire agli studenti una forte comprensione intuitiva delle idee generali che sottendono tali algoritmi
- fornire agli studenti l'abilità pratica di costruire algoritmi efficaci ed efficienti
L'insegnamento si concentra sui problemi di Ottimizzazione Combinatoria.

Introduzione
* Classificazione degli algoritmi euristici
* Alcuni problemi significativi di Ottimizzazione Combinatoria
* Complessita' computazionale: definizioni e complessita' parametrizzata
* Analisi teorica di prestazione: algoritmi approssimati
* Analisi sperimentale di prestazione

Euristiche e metaeuristiche costruttive
* Algoritmi greedy
* Algoritmi di roll-out
* GRASP
* Ant Colony Optimization

Euristiche e metaeuristiche di ricerca locale
* Intorno: definizione ed esplorazione efficiente
* Very Large Neighborhood Search
* Iterated local search e Variable Neighborhood Search
* Simulated Annealing
* Tabu search

Euristiche di ricombinazione
* Scatter search e Path Relinking
* Algoritmi genetici e strategie evoluzionistiche
Prerequisiti
Conoscere gli algoritmi e le strutture dati fondamentali.
Saperli implementare in un linguaggio di programmazione (preferibilmente il C).
Conoscere la notazione della complessità asintotica.
E' consigliato il superamento dell'esame di Algoritmi e Strutture Dati.
Metodi didattici
L'insegnamento è tenuto con lezioni frontali in aula.
Sono possibili saltuarie attività pratiche in laboratorio.
Materiale di riferimento
Lucidi, dispense e articoli di approfondimento sulla pagina web del corso
https://rcordoneha.ariel.ctu.unimi.it
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste in una prova scritta, della durata compresa fra due e tre ore,
che richiede di rispondere a domande aperte sui temi dell'insegnamento e risolvere problemi
applicando le tecniche presentate nell'insegnamento.
La valutazione della prova è espressa in trentesimi, tenendo conto dei seguenti parametri:
grado di conoscenza degli argomenti, capacità di applicare le conoscenze alla risoluzione
di problemi concreti, capacità di ragionamento critico, chiarezza espositiva e proprietà
di linguaggio.
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Docente: Cordone Roberto
Siti didattici
Docente/i
Ricevimento:
Su appuntamento
DI - Via Celoria 10, Milano