Dettagli sull'Insegnamento per l'A.A. 2010/2011

Prerequisiti

CONOSCENZE : fondamenti di programmazione, matematica discreta, algoritmi e strutture dati, architetture degli elaboratori, lettura e comprensione in lingua inglese CAPACITA' : capacità di integrazione dello studio in aula con lo studio personale, capacità di interazione con il docente in aula in modo da originare momenti comuni di confronto

Obiettivi

Conoscenza di tecniche algoritmiche avanzate, capacità di individuazione, formalizzazione e risoluzione di problemi di ottimizzazione, concetto di approssimazione, capacità di classificazione di problemi in base al loro grado di approssimabilità, capacità di collaborazione per la realizzazione progetti applicativi di gruppo

Sillabo

• Richiami di complessità ed intrattabilità. Problemi di ottimizzazione. Algoritmi di approssimazione.
• Tecniche algoritmiche: greedy.
• Tecniche algoritmiche: ricerca locale e programmazione dinamica.
• Tecniche di programmazione lineare: metodo dell'arrotondamento e metodo del primale-duale.
• Schemi di approssimazione polinomiali e pienamente polinomiali.
• Risultati negativi di approssimabilità e tecnica del Gap. Classi di complessità per problemi di ottimizzazione e loro contenimenti

Testi di riferimento

• Vijay V. Vazirani, Approximation Algorithms , Springer. 2001. ISBN: 3-540-65367-8    
• G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation , Springer. 1999. ISBN: 3-540-65431-3    

Risorse Internet

Aggiornamenti alla pagina del corso

• A.A. 2010/2011
• A.A. 2011/2012
• A.A. 2012/2013
• A.A. 2013/2014
• A.A. 2014/2015
• A.A. 2015/2016
• A.A. 2016/2017
• A.A. 2017/2018
• A.A. 2018/2019
• A.A. 2019/2020