Servizi per la didattica
PORTALE DELLA DIDATTICA

Computational complexity and approximation

01SZTRP

A.A. 2018/19

Course Language

Inglese

Course degree

Doctorate Research in Gestione, Produzione E Design - Torino

Course structure
Teaching Hours
Lezioni 20
Teachers
Teacher Status SSD h.Les h.Ex h.Lab h.Tut Years teaching
Della Croce Di Dojola Federico Professore Ordinario MAT/09 20 0 0 0 1
Teaching assistant
Espandi

Context
SSD CFU Activities Area context
*** N/A ***    
Valutazione CPD /
2018/19
PERIOD: MARCH 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 problems and combinatorial optimization problems with emphasis on sequencing and scheduling problems. The course is taught in English.
PERIOD: MARCH 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 problems and combinatorial optimization problems with emphasis on sequencing and scheduling problems. The course is taught in English.
• 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 • Introduction to sequencing and scheduling • Three-field classification • Polynomially solvable machine scheduling problems • Constant approximation ratios in scheduling
• 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 • Introduction to sequencing and scheduling • Three-field classification • Polynomially solvable machine scheduling problems • Constant approximation ratios in scheduling
le lezioni si terranno tutti in aula DIGEP B: 01/03/2018 09-12 08/03/2018 09-12 15/03/2018 09-12 22/03/2018 09-12 29/03/2018 09-12 05/04/2019 09-12 12/04/2019 09-11
le lezioni si terranno tutti in aula DIGEP B: 01/03/2018 09-12 08/03/2018 09-12 15/03/2018 09-12 22/03/2018 09-12 29/03/2018 09-12 05/04/2019 09-12 12/04/2019 09-11
Modalità di esame:
Exam:
Gli studenti e le studentesse con disabilità o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unità Special Needs, al fine di permettere al/la docente la declinazione più idonea in riferimento alla specifica tipologia di esame.
Exam:
In addition to the message sent by the online system, students with disabilities or Specific Learning Disorders (SLD) are invited to directly inform the professor in charge of the course about the special arrangements for the exam that have been agreed with the Special Needs Unit. The professor has to be informed at least one week before the beginning of the examination session in order to provide students with the most suitable arrangements for each specific type of exam.
Esporta Word


© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
Contatti