Heuristics algorithms
A.A. 2025/2026
Learning objectives
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
Expected learning outcomes
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: Secondo quadrimestre
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.
Course syllabus and organization
Edizione unica
Responsabile
Periodo
Secondo quadrimestre
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 portale internet di ateneo Ariel
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.
Educational website(s)
Professor(s)