Description

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 requises

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

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

Disciplines

• Informatique