Operations Research (UGA)

Compétences:

1. Contexte théorique
   • savoir qu'un modèle de calcul appelé Machine de Turing existe, et que c'est le modèle de référence
2. Vocabulaire 
   • Savoir identifier un problème de décision et un problème d'optimisation
   • Savoir écrire le problème de décision associé à un problème d'optimisation et vice-versa
   • connaître les définitions des classes P et NP et leurs relations d'inclusion, la conjecture associée
3. NP-complétude
   • Savoir prouver qu'un problème est dans NP : algorithme vérifieur
   • Savoir prouver qu'un problème est NP-difficile : réduction
4. SAT et 3-SAT 
   • Connaître les définitions des problèmes SAT et 3-SAT
   • Savoir qu'ils sont NP-complets
5. Circuit Hamiltonien, cycle Hamiltonien et TSP  
   • Connaître les définitions des problèmes Circuit Hamiltonien, cycle Hamiltonien et TSP
   • Savoir qu'ils sont NP-complets et savoir refaire la preuve pour TSP
6. Clique, Coloration, 3-coloration
   • Connaître les définitions des problèmes 
   • Savoir qu'ils sont NP-complets et savorir refaire la preuve pour Clique
7. Classe co-NP
   • Connaître la définition de la classe de complexité
   • Savoir écrire un algorithme vérifieur pour un problème dans co-NP
   • Connaître un exemple de problème dans co-NP

Ressources

Vidéos

Readings

• Computers and Intractability: A Guide to the Theory of NP-Completeness, M.R. Garey, D.S. Johnson 
        (the reference book)
  
• Computational complexity, C.H. Papadimitriou
  
• A guide to algorithm design, A. Benoit, Y. Robert, F. Vivien
• The Algorithm design manual, S. S. Skiena
        chap 9: Intractable Problems and Approximation Algorithms
• Algorithms (Chap 8)  by Dasgupta, Papadimitriou and Vazirani
  

Web sites