Cours : Guillaume Hanrot

TD : Marc De Visme & Pierre Pradic

Cours d’introduction aux modèles de calcul en informatique, indispensables pour formaliser la notion de calcul et d’algorithme et par conséquent au fondement de toute la science informatique. Présentation de la thèse de Church-Turing (« toutes les tentatives de formalisation de la notion intuitive d’algorithme sont équivalentes ») qui permet de définir formellement et précisément tout ce qui est calculable, et présentation des limites du calcul (fonction « non-calculable », problèmes ne pouvant pas être résolus par un algorithme).

Contenu indicatif du cours :

Premiers modèles de calcul :

  • Automates finis / langages rationnels : déterministe vs non déterministe, équivalence automates / expressions rationnelles, minimisation, limites du rationnel avec pompage.
  • Grammaires : hiérarchie de Chomski, équivalence hors contexte / automates à pile, limites du context-free avec pompage.

Thèse de Church-Turing :

  • Machines de Turing : illustration avec robustesse par rapport aux variations (simulation des variantes par modèle standard), machines universelles.
  • Illustration avec équivalence aux : Fonctions récursives, Lambda-calcul.

« Calculable » / « non-calculable » :

  • Problèmes indécidables, dont l’arrêt.
  • Théorème de Rice, théorème de point fixe de Kleene.

Introduction à la théorie de la complexité:

  • Classes en temps, classes en espace, déterministes et non-déterministes.
  • Résultats élémentaires d’inclusion et de séparation.
  • Classes P et NP ; caractérisation de NP par certificats, théorème de Cook.

Prérequis : même si toutes les définitions et résultats seront donnés en cours, quelques connaissances de base sur les automates finis sont recommandées (cf programme de L1/L2/CPGE sur les automates).