PERIODO: GENNAIO 2017

Il Corso si propone di fornire le conoscenze di base sulla complessita’ computazionale e sugli algoritmi di approssimazione polinomiale per problemi di ottimizzazione combinatoria.Si esporrranno i concetti di base di complessita’ computazionale, verranno presentati le principali famiglie degli algoritmi esatti esponenziali con relativa analisi di complessità di caso peggiore e verranno introdotti i principali schemi di approssimazione polinomiale. Verranno dati esempi di algoritmi approssimati per problemi paradimatici di teoria dei grafi ed ottimizzazione combinatoria.


Aim of the course is to provide an introduction to computational complexity and approximation for combinatorial optimization problems. Basics on computational complexity will be presented together with the main families of exact exponential algorithms and related worst-case complexity analysis. Polynomial time approximation schemes will be introduced with examples of approximation algorithms for paradigmatic graph theory and combinatorial optimization problems.

Complessità computazionale:
• Algoritmi polinomiali
• Classi di complessità P e NP
• NP-completezza in senso forte ed in senso debole
• Riduzioni polinomiali
• Algoritmi esatti esponenziali

Approssimazione:
• Approssimazione polinomiale
• PTAS e FPTAS
• Inapprossimabilità



Computational complexity:
• polynomial time algorithms
• P and NP complexity classes
• Strong and Weak NP-completeness
• Polynomial time reductions
• Exact exponential algorithms

Approximation:
• Polynomial time approximation
• PTAS and FPTAS
• Inapproximability


All lectures will be in the Classroom denoted as "Aula C"

Timetable
WED 18/1/2017 9-13
WED 25/1/2017 9-13
WED 1/2/2017 9-13
WED 8/2/2017 9-13
WED 15/2/2017 9-13