Théorie de la complexité et algorithmes approchés

Unité d'enseignement de type cours

Télécharger la fiche au format PDF Prendre contact par courriel

Réf. : RCP212

Sessions de formation

(Fuseau horaire : Europe/Paris)

Aucune session n'est visible pour le moment

Présentation

Public, conditions d'accès et prérequis

Acceptation M2 Master STIC - Informatique - MOCS

Objectifs

présenter les différentes classes de complexité des problèmes d'optimisation combinatoire,
les différents types d'algorithmes approchés pour résoudre les problèmes ainsi que les liens
entre complexité et approximation.

Contenu

Classe P et NP - Réduction polynomiale - théorème de Cook - problème NP-complet -
Performance d'un algorithme approché, algorithmes gourmands, schémas d'approximation,
Classes de problèmes.

Bibliographie