Licence

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 Informatique

7 RUE RENE DESCARTES
67084 STRASBOURG
0368850123

Formulaire de contact

Responsable

Christian Ronse

Pascal Schreck


LICENCE - Informatique

Fondation Université de Strasbourg
Investissements d'Avenir
Ligue européenne des universités de recherche (LERU)
EUCOR, Le Campus européen
CNRS
Inserm Grand Est
Logo HRS4R