Fornire conoscenze avanzate, prevalentemente metodologiche, necessarie per rappresentare e trattare con strumenti informatici processi decisionali e modelli quantitativi.
Curriculum
scheda docente materiale didattico
Complessità: Problemi in forma di riconoscimento e di ottimizzazione. Classi P e NP. Riduzione fra problemi. Problemi NP-completi. Algoritmi pseudo-polinomiali.
Algoritmi di approssimazione. Classi di approssimazione (NPO, APX, PTAS, FPTAS, PO). Algoritmi di approssimazione per il Vertex Cover: algoritmi greedy, algoritmo DFS, algoritmi basati sulla PL (arrotondamento e primale duale). Problemi di Knapsack: NP-completezza. Algoritmi di programmazione dinamica. Algoritmo greedy per il knapsack 0-1. Schema di approssimazione per il knapsack 0-1. Schema di approssimazione completamente polinomiale per il knapsack 0-1. Il problema del commesso viaggiatore (TSP): NP-completezza. Non-approssimabilità del TSP. Esempi di applicazioni. Il D-TSP. Un algoritmo 2-approssimato per il D-TSP. Algoritmo di Christofides. Algoritmo 5/3-approssimato per il TSPP. Problemi di scheduling su macchine parallele.
Algoritmi euristici: algoritmi costruttivi (euristiche per il TSP: a inserimento con diversi criteri di scelta, algoritmi per istanze geometriche); ricerca locale (per il TSP: 2-opt exchange, 3-opt, k-opt, OR-opt) ricerca locale a profondità variabile (Alg. Lin-Kernigan), tabu search, simulated annealing, alg.genetici, cenni ad altre metaeuristiche.
Cenni agli algoritmi online: algoritmi online, analisi competitiva, esempi.
[2] Dispense del prof. Agnetis (complessità, il problema del commesso viaggiatore, algoritmi euristici ).
[3] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, "Complexity and Approximation,Combinatorial optimization problems and their approximability properties", Springer Verlag, 1999 (sito web del libro)
[4] Slide del docente disponibili sulla pagina web del corso.
Programma
Introduzione ai problemi di ottimizzazione combinatoria. Algoritmi di ottimizzazione. Analisi di complessità degli algoritmi.Complessità: Problemi in forma di riconoscimento e di ottimizzazione. Classi P e NP. Riduzione fra problemi. Problemi NP-completi. Algoritmi pseudo-polinomiali.
Algoritmi di approssimazione. Classi di approssimazione (NPO, APX, PTAS, FPTAS, PO). Algoritmi di approssimazione per il Vertex Cover: algoritmi greedy, algoritmo DFS, algoritmi basati sulla PL (arrotondamento e primale duale). Problemi di Knapsack: NP-completezza. Algoritmi di programmazione dinamica. Algoritmo greedy per il knapsack 0-1. Schema di approssimazione per il knapsack 0-1. Schema di approssimazione completamente polinomiale per il knapsack 0-1. Il problema del commesso viaggiatore (TSP): NP-completezza. Non-approssimabilità del TSP. Esempi di applicazioni. Il D-TSP. Un algoritmo 2-approssimato per il D-TSP. Algoritmo di Christofides. Algoritmo 5/3-approssimato per il TSPP. Problemi di scheduling su macchine parallele.
Algoritmi euristici: algoritmi costruttivi (euristiche per il TSP: a inserimento con diversi criteri di scelta, algoritmi per istanze geometriche); ricerca locale (per il TSP: 2-opt exchange, 3-opt, k-opt, OR-opt) ricerca locale a profondità variabile (Alg. Lin-Kernigan), tabu search, simulated annealing, alg.genetici, cenni ad altre metaeuristiche.
Cenni agli algoritmi online: algoritmi online, analisi competitiva, esempi.
Testi Adottati
[1] “Lecture Notes on Approximation Algorithms”, Volume I, R. Motwani.[2] Dispense del prof. Agnetis (complessità, il problema del commesso viaggiatore, algoritmi euristici ).
[3] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, "Complexity and Approximation,Combinatorial optimization problems and their approximability properties", Springer Verlag, 1999 (sito web del libro)
[4] Slide del docente disponibili sulla pagina web del corso.
Modalità Erogazione
lezioni frontali, esercitazioni, prove in laboratorio informaticoModalità Valutazione
nel periodo di emergenza COVID-19 l’esame di profitto sarà svolto secondo quanto previsto all’art.1 del Decreto Rettorale n°. 703 del 5 maggio 2020 Fino a febbraio 2020: La verifica dell’apprendimento avviene attraverso una prova scritta della durata di circa 2 ore e da una prova pratica con valutazione di un progetto. Lo scritto è organizzato attraverso un certo numero di esercizi (tipicamente 4), finalizzati a verificare il livello di comprensione effettiva dei concetti più teorici. Il progetto ha lo scopo di verificare la capacità degli studenti di applicare le tecniche spiegate a lezione. scheda docente materiale didattico
Complessità: Problemi in forma di riconoscimento e di ottimizzazione. Classi P e NP. Riduzione fra problemi. Problemi NP-completi. Algoritmi pseudo-polinomiali.
Algoritmi di approssimazione. Classi di approssimazione (NPO, APX, PTAS, FPTAS, PO). Algoritmi di approssimazione per il Vertex Cover: algoritmi greedy, algoritmo DFS, algoritmi basati sulla PL (arrotondamento e primale duale). Problemi di Knapsack: NP-completezza. Algoritmi di programmazione dinamica. Algoritmo greedy per il knapsack 0-1. Schema di approssimazione per il knapsack 0-1. Schema di approssimazione completamente polinomiale per il knapsack 0-1. Il problema del commesso viaggiatore (TSP): NP-completezza. Non-approssimabilità del TSP. Esempi di applicazioni. Il D-TSP. Un algoritmo 2-approssimato per il D-TSP. Algoritmo di Christofides. Algoritmo 5/3-approssimato per il TSPP. Problemi di scheduling su macchine parallele.
Algoritmi euristici: algoritmi costruttivi (euristiche per il TSP: a inserimento con diversi criteri di scelta, algoritmi per istanze geometriche); ricerca locale (per il TSP: 2-opt exchange, 3-opt, k-opt, OR-opt) ricerca locale a profondità variabile (Alg. Lin-Kernigan), tabu search, simulated annealing, alg.genetici, cenni ad altre metaeuristiche.
Cenni agli algoritmi online: algoritmi online, analisi competitiva, esempi.
[2] Dispense del prof. Agnetis (complessità, il problema del commesso viaggiatore, algoritmi euristici ).
[3] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, "Complexity and Approximation,Combinatorial optimization problems and their approximability properties", Springer Verlag, 1999 (sito web del libro)
[4] Slide del docente disponibili sulla pagina web del corso.
Programma
Introduzione ai problemi di ottimizzazione combinatoria. Algoritmi di ottimizzazione. Analisi di complessità degli algoritmi.Complessità: Problemi in forma di riconoscimento e di ottimizzazione. Classi P e NP. Riduzione fra problemi. Problemi NP-completi. Algoritmi pseudo-polinomiali.
Algoritmi di approssimazione. Classi di approssimazione (NPO, APX, PTAS, FPTAS, PO). Algoritmi di approssimazione per il Vertex Cover: algoritmi greedy, algoritmo DFS, algoritmi basati sulla PL (arrotondamento e primale duale). Problemi di Knapsack: NP-completezza. Algoritmi di programmazione dinamica. Algoritmo greedy per il knapsack 0-1. Schema di approssimazione per il knapsack 0-1. Schema di approssimazione completamente polinomiale per il knapsack 0-1. Il problema del commesso viaggiatore (TSP): NP-completezza. Non-approssimabilità del TSP. Esempi di applicazioni. Il D-TSP. Un algoritmo 2-approssimato per il D-TSP. Algoritmo di Christofides. Algoritmo 5/3-approssimato per il TSPP. Problemi di scheduling su macchine parallele.
Algoritmi euristici: algoritmi costruttivi (euristiche per il TSP: a inserimento con diversi criteri di scelta, algoritmi per istanze geometriche); ricerca locale (per il TSP: 2-opt exchange, 3-opt, k-opt, OR-opt) ricerca locale a profondità variabile (Alg. Lin-Kernigan), tabu search, simulated annealing, alg.genetici, cenni ad altre metaeuristiche.
Cenni agli algoritmi online: algoritmi online, analisi competitiva, esempi.
Testi Adottati
[1] “Lecture Notes on Approximation Algorithms”, Volume I, R. Motwani.[2] Dispense del prof. Agnetis (complessità, il problema del commesso viaggiatore, algoritmi euristici ).
[3] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, "Complexity and Approximation,Combinatorial optimization problems and their approximability properties", Springer Verlag, 1999 (sito web del libro)
[4] Slide del docente disponibili sulla pagina web del corso.
Modalità Erogazione
lezioni frontali, esercitazioni, prove in laboratorio informaticoModalità Valutazione
nel periodo di emergenza COVID-19 l’esame di profitto sarà svolto secondo quanto previsto all’art.1 del Decreto Rettorale n°. 703 del 5 maggio 2020 Fino a febbraio 2020: La verifica dell’apprendimento avviene attraverso una prova scritta della durata di circa 2 ore e da una prova pratica con valutazione di un progetto. Lo scritto è organizzato attraverso un certo numero di esercizi (tipicamente 4), finalizzati a verificare il livello di comprensione effettiva dei concetti più teorici. Il progetto ha lo scopo di verificare la capacità degli studenti di applicare le tecniche spiegate a lezione.