SINA09B
EC Complexité
UE projet tutoré/mémoire
UE mener un projet de recherche avec une démarche scientifique
DESCRIPTION
ORGANISATION
FORMATIONS
Contenu
Mise à niveau : calculabilité et décidabilité : machines de Turing, thèse de Church, notion de réduction.
Les classes P, NP et au delà : P, NP, problèmes fortement NP-complets, hiérarchie polynomiale, complexité en espace, complexité descriptive.
Approximation et complexité : classes d'approximation, résultats de non approximabilité, réductions pour l'approximation et problèmes complets.
Complexité paramétrée : FPT et kernelisation.
Éventuellement : complexité du comptage.
Langue(s) d'enseignement
Français
Volume des enseignements
Cours magistraux: 9 heures
Travaux dirigés: 9 heures
Travaux pratiques: 9 heures
Volume total: 27 heures
Responsables pédagogiques:
LHOTE Nathan
Codes APOGÉE
SINA09BL [ELP]
Les formations qui utilisent cet enseignement
Rechercher...