Introduction aux grandes catégories de problèmes

  • Cours (CM) 12h
  • Cours intégrés (CI) -
  • Travaux dirigés (TD) 12h
  • Travaux pratiques (TP) -
  • Travail étudiant (TE) -

Langue de l'enseignement : Français

Niveau de l'enseignement : B2-Avancé - Utilisateur indépendant

Description du contenu de l'enseignement

Cette UE vise à initier les étudiantes aux divers niveaux de complexité d'un calcul ou une décision, ainsi qu'aux différentes modalités de décision (décision ou semi-décision, déterministe ou non). Cela se fait de plusieurs manières : d'abord par la distinction entre fonction récursive primitive et fonction mu-récursive (illustrée par la fonction d'Ackermann-Péter et le problème de l'hydre), ensuite par les différents niveaux de généralité de langages (régulier, algébrique, récursif, récursivement énumérable) et les outils correspondants (automate fini, grammaire algébrique, machine de Turing). Enfin on introduira le non-déterminisme et la complexité au sens de la machine de Turing, en particulier la décision non-déterministe, les classes P, NP et EXP.

Compétences à acquérir

À l'issue de cette UE un étudiant devrait savoir :
- distinguer récursion primitive et mu-récursion ;
- manipuler les expressions régulières, automates finis, grammaires algébriques et machines de Turing ;
- ce que signifie la décision non-déterministe ;
- reconnaître des problèmes de classe P, NP ou EXP.

Contact

UFR de mathématique et d'informatique

7, rue René Descartes
67084 STRASBOURG CEDEX
0368850200

Formulaire de contact