Ogni modulo equivale a 3 crediti ECTS. È possibile scegliere un totale di 10 moduli/30 ECTS nelle seguenti categorie:
- 12-15 crediti ECTS in moduli tecnico-scientifici (TSM)
I moduli TSM trasmettono competenze tecniche specifiche del profilo e si integrano ai moduli di approfondimento decentralizzati. - 9-12 crediti ECTS in basi teoriche ampliate (FTP)
I moduli FTP trattano principalmente basi teoriche come la matematica, la fisica, la teoria dell’informazione, la chimica ecc. I moduli ampliano la competenza scientifica dello studente e contribuiscono a creare un importante sinergia tra i concetti astratti e l’applicazione fondamentale per l’innovazione - 6-9 crediti ECTS in moduli di contesto (CM)
I moduli CM trasmettono competenze supplementari in settori quali gestione delle tecnologie, economia aziendale, comunicazione, gestione dei progetti, diritto dei brevetti, diritto contrattuale ecc.
La descrizione del modulo (scarica il pdf)riporta le informazioni linguistiche per ogni modulo, suddivise nelle seguenti categorie:
- Insegnamento
- Documentazione
- Esame
An algorithm is typically called efficient if its worst-case running time is polynomial in the size of the input. This course will focus on a huge and practically relevant family of problems, namely NP-hard ones, for which (most likely) no efficient algorithm exists. This family includes fundamental problems in computational biology, network design, systems, computer vision, data mining, online markets, etc.
The first goal of this course it to learn how to identify NP-hard problems.
For a given NP-hard optimization problem it might still be possible to compute efficiently a feasible solution whose cost is (in the worst-case) within a small multiplicative factor (approximation factor) from the optimum: this is the aim of approximation algorithms. The second goal of this course is to learn how to design accurate approximation algorithms, and how to (theoretically) bound their approximation factor.
Requisiti
Basics of theoretical analysis of algorithms.
Obiettivi di apprendimento
The main goal of this course is to learn how to identify NP-hard problems, and how to design and (theoretically) analyze approximation algorithms for fundamental NP-hard optimization problems.
Categoria modulo
A. Complexity Classes: polynomial Reductions; NP-completeness and NP-hardness.
B. NP-hard problems: SAT and Max-SAT; Vertex/Set Cover; Steiner Tree and generalizations; TSP; Max Cut; Knapsack and Bin Packing; k-Center and clustering; Scheduling; Facility Location; Item Pricing; etc.
C. Approximation Algorithms:
- Basic notions: approximation factor; hardness of approximation.
- Basic techniques: greedy; local search; randomization; dynamic programming.
LP-based techniques: randomized rounding; primal-dual; iterative rounding.
Metodologie di insegnamento e apprendimento
Interactive lectures both for theory and exercises.
Bibliografia
- V. V. Vazirani. Approximation Algorithms. Springer.
- D. P. Williamson, D. B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press.
Scarica il descrittivo completo del modulo
Indietro