Accueil
Connexion
DENIF –
Documents d’Enseignement Numériques en Informatique Fondamentale
Thèmes
Cursus
Enseignants
Décidabilité
Thème :
Languages, Automates & Calculabilité
–
Cursus :
ENS-Lyon - L3
2004 - 2005
TDs
Victor Poupet
,
Vincent Nesme
description des TDs et du partiel
TD 0 : Codages
TD 1 : Machines de Turing
TD 2 : Machines à compteurs
TD 3 : Fonctions récursives primitives
TD 4 : Castor affairé, graphes de fonctions récursives primitives
TD 5 : Partiel de l'année précédente
TD 6 : Récursivité, théorème de Rice
TD 7 : Approfondissement, problème de correspondance de Post
TD 8 : Théorème de Rice-Shapiro
TD 9 : Complexité de Kolmogoroff
TD 10 : Complexité de Kolmogoroff, aperçu du théorème d'incomplétude de Gödel
Corrigé rapide de l'exercice sur le théorème de Gödel