Chaque module vaut 3 ECTS. Vous sélectionnez 10 modules/30 ECTS parmi les catégories suivantes:
- 12-15 crédits ECTS en Modules technico-scientifiques (TSM)
Les modules TSM vous transmettent une compétence technique spécifique à votre orientation et complètent les modules de spécialisation décentralisés. - 9-12 crédits ECTS en Bases théoriques élargies (FTP)
Les modules FTP traitent de bases théoriques telles que les mathématiques élevées, la physique, la théorie de l’information, la chimie, etc., vous permettant d’étendre votre profondeur scientifique abstraite et de contribuer à créer le lien important entre l’abstraction et l’application dans le domaine de l’innovation. - 6-9 crédits ECTS en Modules contextuels (CM)
Les modules CM vous transmettent des compétences supplémentaires dans des domaines tels que la gestion des technologies, la gestion d’entreprise, la communication, la gestion de projets, le droit des brevets et des contrats, etc.
Le descriptif de module (download pdf) contient le détail des langues pour chaque module selon les catégories suivantes:
- leçons
- documentation
- examen
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.
Compétences préalables
Basics of theoretical analysis of algorithms.
Objectifs d'apprentissage
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.
Contenu des modules
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.
Méthodes d'enseignement et d'apprentissage
Interactive lectures both for theory and exercises.
Bibliographie
- V. V. Vazirani. Approximation Algorithms. Springer.
- D. P. Williamson, D. B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press.
Télécharger le descriptif complet
Retour