Calculabilité et complexité
Parcours : DU Cursus master ingénierie (CMI) - Informatique, systèmes et réseaux

  • Cours (CM) 12h
  • Cours intégrés (CI) -
  • Travaux dirigés (TD) 14h
  • 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

On décrit les modèles les plus généraux de calcul et de décision en informatique (qui sont équivalents) : machine de Turing, grammaire, fonction mu-récursive (avec cas particulier des fonctions récursives primitives).
On précise la signification du non-déterminisme dans le calcul et la décision.
Ensuite on donne les limites de ces modèles en montrant l'impossibilité de décider généralement certaines questions, comme l'arrêt d'une machine de Turing.
Enfin on donne les classes fondamentales de complexité des algorithmes, P, NP et EXP, en particulier les problèmes NP-complets.

Compétences à acquérir

À l'issue de cette UE, un étudiant saura :
- Faire preuve d'esprit critique face à des « solutions » trop générales ;
- Comprendre l'équivalence des divers langages informatiques avec la machine de Turing ;
- Connaître les limites de l'informatique ;
- Maîtriser le non-déterminisme ;
- Être capable de classer des problèmes informatiques en : faisables en pratique ; possibles en principe mais infaisables en pratique ; impossibles en principe.

Bibliographie, lectures recommandées

P. Wolper, Introduction à la calculabilité : Cours et exercices corrigés, Edition Dunod
J.-F. Rey, Calculabilité, complexité et approximation, Edition Vuibert

Pré-requis obligatoires

Théorie des langages

Contact

UFR de Mathématique et Informatique

7 RUE RENE DESCARTES
67084 STRASBOURG
0368850123

Formulaire de contact


Parcours : DU Cursus master ingénierie (CMI) - Informatique, systèmes et réseaux