Heuristic algorithms
A.A. 2024/2025
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
- 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.
Imparerà a progettare e realizzare in un linguaggio di programmazione algoritmi euristici e a valutarne le prestazioni.
Periodo: Primo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
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
- 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.
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.
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
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.
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 RobertoDocente/i