ValidationCC+examen
EnseignantFrançois Le Maître
Horaires hebdomadaires 2 h CM , 3 h TD
Années

Syllabus

L'objectif de ce cours est d’abord de présenter les notions logiques de décidabilité et d'indécidabilité. On définit ensuite la notion de réduction entre problèmes. On présente enfin la notion de complexité qui prend en compte les ressources (temps de calcul, espace mémoire) nécessaires à la résolution d’un problème sur machine.

Sommaire

  • Fonctions récursives partielles. Fonctions calculables sur machine de Turing Equivalence.
  • Ensembles récursifs et récursivement énumérables.
  • Problèmes décidables. Problèmes indécidables
  • Réduction d’un problème à un autre. Problème complet pour une classe.
  • Indécidabilité du problème de l’arrêt d’une machine de Turing.
  • Fonctions définissables dans l’arithmétique de Peano.
  • Mesures de complexité (temps, espace). Classes de complexité en temps polynomial P et NP.
  • Hiérarchie de complexité.
  • Réduction en temps polynomial. Problèmes NP-complets.