Complexité paramétrée et Approximation Polynomiale
Code UE : US331Q
- Cours
- 2 crédits
Responsable(s)
Safia KEDAD SIDHOUM
Public, conditions d’accès et prérequis
Cours de complexité de base (classes P et NP, algorithmes polynomiaux et pseudo-polynomiaux, etc.)
Présence et réussite aux examens
Pour l'année universitaire 2022-2023 :
- Nombre d'inscrits : 20
- Taux de présence à l'évaluation : 30%
- Taux de réussite parmi les présents : 83%
Objectifs pédagogiques
- Apprendre les notions de base en approximation polynomiale, et en conception d'algorithmes approchés.
- Apprendre à analyser le ratio d'approximation d'un algorithme approché.
- Apprendre les notions de base en complexité paramétrée, et en conception d'algorithmes FPT.
- Apprendre les notions de base en calcul de noyau pour les problèmes paramétrés, et en analyse de la taille des noyaux obtenus.
Compétences visées
Savoir concevoir des algorithmes approchés simples, combinatoires ou à l'aide de techniques de programmation mathématique, et analyser leur ratio d'approximation
Savoir établir des résultats d'inapproximabilité simples (sous certaines hypothèses de complexité).
Savoir concevoir des algorithmes FPT simples, et savoir montrer qu'un problème n'admet pas d'algorithmes FPT (sous certaines hypothèses de complexité).
Savoir calculer des noyaux à l'aide de règles de réduction simples.
Savoir établir des résultats d'inapproximabilité simples (sous certaines hypothèses de complexité).
Savoir concevoir des algorithmes FPT simples, et savoir montrer qu'un problème n'admet pas d'algorithmes FPT (sous certaines hypothèses de complexité).
Savoir calculer des noyaux à l'aide de règles de réduction simples.
Contenu
- Panel d'exemples d'algorithmes d'approximation polynomiale sur des problèmes classiques. Classes des problèmes d'optimisation et de leur approximabilité (en particulier PO, NPO, APX, PTAS, FPTAS, EPTAS, AAPX, APX$infty$, PTAS$infty$). Relation entre l'appartenance à la classe FPTAS et la NP-complétude au sens fort des problèmes d'optimisation.
- Approximabilité et programmation linéaire. Conception d'algorithmes d'approximation probabilistes. Technique d'arrondi, arrondi probabiliste, déterminisation, dual fitting et schéma primal-dual pour la conception d'algorithmes approchés.
- Inapproximabilité, et notion de rapport serré. Réductions préservant les rapports d'approximation, et réductions GAP. Notion et exemples de complétude. Introduction au théorème PCP.
- Paramétrisation de problèmes de NP. Définition des classes de base en complexité paramétrée : hiérarchie des classes W[t], classes FPT et XP. Notion de FPT-réduction, et conséquences basées sur la W[1]-difficulté du problème de clique. Conception d'algorithmes FPT via les arbres de recherche bornés. Liens avec l'approximation polynomiale, et notamment avec l'existence d'EPTAS.
- Notion de (calcul de) noyau en complexité paramétrée. Équivalence entre l'existence d'un noyau et celle d'un algorithme FPT. Exemples de calcul de noyaux, quadratiques ou linéaires, pour une sélection de problèmes (transversal minimum, $k$-MAX 3-SAT, $k$-MAX SAT, etc.), à l'aide de règles de réduction. Calcul de noyaux linéaires pour l'existence de certaines structures dans les graphes planaires (des stables, par exemple).
Modalité d'évaluation
- Examen final
Cette UE apparaît dans les diplômes et certificats suivants
Rechercher une formation
RECHERCHE MULTI-CRITERES
-
Vous pouvez sélectionner des formations grâce à un mot ou à une expression présent dans l’intitulé ou dans les index (discipline ou métier visé).
Des index vous sont suggérés à partir du 3e caractère saisi, mais vous pouvez aussi saisir librement tout autre mot . - Les différents items sélectionnés sont croisés.
ex: "Comptabilité" et "Région Grand Est" - Validez par le bouton « Rechercher » ou par la touche Entrée.
- Cette recherche affiche aussi les fiches UE et certificats régionales. Leurs codes les distinguent des fiches nationales par le suffixe de la région (ex : « -IDF » ).
Par défaut, les fiches régionales reprennent le contenu de la fiche nationale correspondante. Mais dans certains cas, des informations régionales ont pu être ajoutées. - Certains diplômes se déclinent selon plusieurs parcours. Pour afficher tous les parcours, tapez la racine du code (ex : « LG035 »).
- Certains stages ont un double code : leur code propre et le code de l’UE ou du certificat équivalent.
- Dans tous les cas, veillez à ne pas insérer d'espace ni de ponctuation supplémentaire.
- Validez par le bouton « OK » (et non pas par la touche Entrée).
Chargement du résultat...
Intitulé de la formation |
Type |
Modalité(s) |
Lieu(x) |
|
---|---|---|---|---|
Intitulé de la formation
Master Sciences, technologies, santé mention Informatique Parcours Recherche opérationnelle
|
Lieu(x)
Package
|
Lieu(x)
Paris
|
||
Intitulé de la formation | Type | Modalité(s) | Lieu(x) |
Contact
Recherche opérationnelle
2D4P20, 33-1-10, 2 rue Conté
75003 Paris
Tel :01 40 27 22 67
secretariat.ro@cnam.fr
2D4P20, 33-1-10, 2 rue Conté
75003 Paris
Tel :01 40 27 22 67
secretariat.ro@cnam.fr
Voir le site
Voir le calendrier, le tarif, les conditions d'accessibilité et les modalités d'inscription dans le(s) centre(s) d'enseignement qui propose(nt) cette formation.
Enseignement non encore programmé
Code UE : US331Q
- Cours
- 2 crédits
Responsable(s)
Safia KEDAD SIDHOUM