Programme – contenu de l’UE
Tout est-il calculable par ordinateur, par algorithme ? Qu’est-ce qui est calculable par algorithme (ou ordinateur) ? Des réponses nécessitent l'introduction d'une notion formelle rendant compte de celle d'algorithme, par exemple celle de machine de Turing. Cela conduit à la thèse de Church-Turing et au développement de techniques et de résultats fondamentaux de calculabilité.
On donne alors sens à la notion de problème de décision décidable (et indécidable). Lorsqu’un problème est décidable, la quantité de ressource (temps ou espace) que nécessite le fait de le décider détermine sa complexité (en temps ou en espace). On définit alors des classes de complexité de problèmes décidables, comme par exemple les classes P et NP. Le cours se décline donc en deux parties.
Calculabilité :
- Modèles de calcul. Machines de Turing. Enumération des machines de Turing. Machine de Turing universelle. Exemples d’autres modèles de calcul : machines RAM, algorithmes de Markov.
- Théorèmes fondamentaux de calculabilité (Théorèmes de l'arrêt, s-n-m, Kleene (récursion) et Rice).
- Ensembles récursifs et récursivement énumérables.
Complexité (via les machines de Turing) :
- Rappels sur les complexités d’algorithmes. Complexité d’un problème. Classes de complexité.
- Classes de complexité classiques : Logspace, P, NP et Pspace.
- Structure de NP. Langages (problèmes) NP-complets. Théorème de Cook-Levin. Exemples de problèmes NP-complets. Exemples de problèmes P-complets.
Compétences acquises
Méthodologiques :
Algorithmiques / Capacité d’abstraction et de formalisation : nécessité, à un certain stade de connaissance et de pratique, de formaliser des notions comme celle d’algorithme par exemple / Passage de l’étude d’un objet singulier (un algorithme) à celle d'une classe d’objets (une classe d'algorithmes) / Distinction entre calculer et vérifier / Capacité de construire des représentations formelles d’objets comme le calcul / Compréhension de la notion d'universalité et de l’équivalence code-donnée / Codage / Recours au (et interprétation du) non déterminisme / Usage de notions de réductions (récursives, polynomiales ou logarithmiques) / Évaluation de la puissance et des limites de performances des algorithmes et des machines.
Techniques :
Énumérations, codages, réductions, techniques de décidabilité et d’indécidabilité.
Secteur d’activité concerné et compétences métier acquises : Informatique.
| 
