http://www.lirmm.fr/~poupet/
e-mail: victor.poupet [at] lirmm.fr

Enseignement : Evaluation théorique des problèmes (2e semestre 2005-2006)

Cours de Marianne Delorme en M1 à l'université Lyon 1.

Big Blue Sky - RozeChan

Travaux dirigés

TD n°1 [pdf]

Le problème de correspondance de Post, et d'autres exercices sur la récursivité.

TD n°2 [pdf]

Un exemple de problème NP-complet : le jeu Cubic.

TD n°3 [pdf]

Un exemple de problème PSPACE-complet : géographie, noyé dans un énoncé qui parle de tout à la fois.

TD n°4 [pdf]

Les bases de la complexité de Kolmogorov : définition, premières propriétés et quelques applications.

Partiel

Partiel de l'année 2005 - 2006 [pdf]

Quelques questions de cours pour montrer qu'une variante simple de SAT est NP-complète. Puis un problème où l'on prouve qu'il est NP-complet de déterminer s'il est possible de gagner en un coup à partir d'une configuration du jeu phutball inventé par John Conway par réduction au problème 3-SAT.
Un corrigé est disponible : [pdf]

Valid XHTML 1.0 Transitional Valid CSS! Valid Konami!