Heuristic algorithms

A.A. 2024/2025
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.
Corso singolo

Questo insegnamento può essere seguito come corso singolo.

Programma e organizzazione didattica

Edizione unica

Responsabile
Periodo
Primo semestre

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 sul sito web
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
Turni:
Turno
Docente: Cordone Roberto
Docente/i
Ricevimento:
Su appuntamento
DI - Via Celoria 18, Milano