Calculabilité et complexité

  • 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

- Savoir 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.

Pré-requis obligatoires

Algorithmique et Programmation impérative de base (L1, L2) ; Théorie des Langages (L3 S6).

Contact

UFR de Mathématique et Informatique

7 RUE RENE DESCARTES
67084 STRASBOURG
0368850123


MASTER - Informatique