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

Code UE : RCP212

  • Cours
  • 3 crédits

Responsable national

Christophe PICOULEAU

Responsable opérationnel

Christophe PICOULEAU

Public et conditions d'accès

Acceptation M2 Master STIC -Informatique-MOCS

Objectifs pédagogiques

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.

Mots-clés

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

  • M. Garey and D. Johnson : Computers and Intractability: A Guide to the Theory of NP-completeness

Contact

EPN05 - Informatique
2 rue Conté
75003 Paris
Tel :01 40 27 22 58
Swathi Rajaselvam

Voir les dates et horaires, les lieux d'enseignement et les modes d'inscription sur les sites internet des centres régionaux qui proposent cette formation

Enseignement non programmé en 2017/2018