Cours "Complexité de problèmes"

Références bibliographiques:

• Livre "Logique et Complexité", Richard Lassaigne et Michel de Rougement, Hermes, 1996.
• Livre "Structural Complexity I & II", José Luis Balcazar, Josep Diaz et Joaquim Gabarro, EATCS Monographs on Theoretical Computer Science , 1998.
• Livre "Computational Complexity", Christos Papadimitriou, Addison-Wesley, 1994.
• Différentes notes de cours: en particulier les notes du cours de Miklos Santha et les notes du cours de Mariane Delorme.

1ière partie: Maurice Margenstern

Transparents non-disponibles sur cette page.

2ième partie: Olivier Bournez

• Document complémentaire:
  • Introduction, Motivation de la théorie de la complexité
• Séance 1 de 2003/2004:
  • Machines de Turing, Définitions
  • Document complémentaire:
    • Thèse de Church, Exemple des machines RAM
• Séance 2 de 2003/2004:
  • Classes de Complexité Standards
• Séance 3 de 2003/2004:
  • Classes de Complexité Standards (suite)
  • Réductions, Problèmes Complets
• Séance 4 de 2003/2004:
  • Réductions, Problèmes Complets (suite)
• Séance 5 de 2003/2004:
  • Classes parallèles
  • Classes probabilistes

Partiels

• Sujet Janvier 2003 1ière session Partie1 et Partie2
• Sujet 2ième session Janvier 2003

Cours DEA 2003. Olivier Bournez
Pour toute remarque: Olivier.Bournez@loria.fr