Cours :  Stéphan Thomassé

TD : Sebastian Barbieri & Timothée Pécatte

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 context-free / 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, Machines RAM, Grammaires type 0.

« Calculable » / « non-calculable » :

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

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

2 commentaires “FDI – Fondement de l’Informatique / Calculabilité (1er semestre, 6 ECTS)”

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *