Vous êtes ici :

Licence

Information importante

La page que vous consultez correspond à l'offre de formation 2023-2024.

Trouvez votre formation pour l'année universitaire 2024-2025

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.

Pré-requis obligatoires

À l'entrée de cette UE, une étudiante devrait comprendre la notion d'algorithme et calcul en informatique, et connaître la machine de Turing comme modèle de base d'un algorithme (cf. UE "Modèles de calcul" en S2).

LICENCE - Informatique

Partenaires

Logo du CNRS
Logo Établissement associé de l'Université de Strasbourg
Logo du réseau Epicur
Logo de EUCOR, Le Campus européen
Logo de l'Inserm Grand Est
Logo de l'Inria

Labels

Logo du label Bienvenue en France
Logo du programme HRS4R
Logo du programme France 2030
Logo de Service Public+

Réseaux

Logo de France Universités
Logo de la Ligue européenne des universités de recherche (LERU)
Logo du réseau Udice
Logo de l'Université franco-allemande