Dimitri Watel

MODÈLES DE CALCULS

Autre(s) enseignant(es) : Renaud Rioboo

On se pose la question de savoir ce qu’est un programme, ce qu’est une fonction, bref ce qu’est un calcul, et de ce que sont les problèmes qu’on peut ou qu’on ne peut pas résoudre avec des programmes. On voit quelles sont les équivalences entre différentes philosophies et modèles de calcul, principalement : machines de Turing, fonctions récursives partielles, lambda-calcul.

Cours annotés

Définitions (Annotations : 2018) (Tableau : 2018)
Calculabilité et fonctions récursives (Annotations : 2018) (Tableau : 2018)
Classes de complexité (Annotations : 2018, 2019) (Tableau : 2018)
Réductions et complétude (Annotations : 2018, 2019) (Tableau : 2018, 2019)

Machines de Turing vues en cours:

Editeur de machine de Turing
Incrémenteur (déterministe) (.png, .tm)
Trouver une chaîne de taille 3 dans un graphe (déterministe)(.png, .tm)
Trouver une chaîne de taille 3 dans un graphe (non déterministe)(.png, .tm)
Découper une pizza (non déterministe)( .png(1), .png(2), .png(3), .png(4), .png(5), .png(6), .tm)

Changer de langue : Français English