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 .

Transparents non-disponibles sur cette page.

(Cette partie du cours se déroule au tableau. Les liens suivants donnent des sur-ensembles de ce qui est raconté).

Séance 1 de 2002/2003:
- Introduction. Motivation.
- Modèles de Calculs. Thèse de Church.
Séances 2 de 2002/2003:
- Classes de Complexité Standards. (jusqu'à inclusions).
Séances 3 de 2002/2003:
- Classes de Complexité Standards. (suite)
- Réductions et problèmes complets. (jusqu'à circuit-value)
Séances 4 de 2002/2003:
- Réductions et problèmes complets. (suite)
Séances 5 de 2002/2003:
- Classes de Complexité Parallèles.
- Classes de Complexité Probabilistes.

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