Algoritmi euristici
A.A. 2018/2019
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
- 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
Risultati apprendimento attesi
Non definiti
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
Linea Milano
Responsabile
Periodo
Primo semestre
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
* 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
Algoritmi e Strutture Dati
Prerequisiti
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
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
STUDENTI NON FREQUENTANTI
Lezioni frontali e di laboratorio
Prerequisiti
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
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
Docente/i