Algoritmi euristici

A.A. 2018/2019
Insegnamento per
6
Crediti massimi
48
Ore totali
SSD
INF/01
Lingua
Italiano
Obiettivi formativi
Questo corso si propone di:
- presentare tecniche generali per il progetto, la realizzazione
e la valutazione di algoritmi euristici per problemi di Ottimizzazione Combinatoria
- fornire agli studenti una forte comprensione intuitiva delle idee generali che sottendono questi processi
- fornire agli studenti la capacità pratica di costruire algoritmi efficaci ed efficienti per problemi computazionalmente difficili

Struttura insegnamento e programma

Linea Milano
Edizione attiva
Responsabile
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Docente: Cordone Roberto
STUDENTI FREQUENTANTI
Informazioni sul programma
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 non adattivi e adattivi
* 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

Euristiche a convergenza
* Macchina di Boltzmann
* Mean-Field Annealing, Reti di Hopfield
* Reti elastiche per il TSP
Propedeuticità
Programmazione
Algoritmi e Strutture Dati
Prerequisiti e modalità di esame
Prerequisiti: programmazione

Modalità d'esame: l'esame si compone di un progetto pratico e di un esame orale.
Il progetto richiede lo sviluppo di un algoritmo per risolvere un problema di Ottimizzazione Combinatoria,
la realizzazione del relativo programma in linguaggio C standard,
la valutazione delle sue prestazioni su istanze di benchmark e la stesura di una relazione.
L'orale consiste in una discussione, in particolare su come applicare concretamente
le tecniche trattate nel corso a possibili problemi di esempio
Metodi didattici
Lezioni frontali e di laboratorio
STUDENTI NON FREQUENTANTI
Prerequisiti e modalità di esame
Prerequisiti: programmazione

Modalità d'esame: l'esame si compone di un progetto pratico e di un esame orale.
Il progetto richiede lo sviluppo di un algoritmo per risolvere un problema di Ottimizzazione Combinatoria,
la realizzazione del relativo programma in linguaggio C standard,
la valutazione delle sue prestazioni su istanze di benchmark e la stesura di una relazione.
L'orale consiste in una discussione, in particolare su come applicare concretamente
le tecniche trattate nel corso a possibili problemi di esempio
Periodo
Primo semestre
Periodo
Primo semestre
Modalità di valutazione
Esame
Giudizio di valutazione
voto verbalizzato in trentesimi
Docente/i
Ricevimento:
Su appuntamento
DI - Via Celoria 18, Milano