Langages formels, calculabilité, complexité
TD donnés à
l'ENS, voir
la page du cours
-
Partiel
[Français]
[English]
[Correction]
-
Examen
[Français]
[English]
[Correction]
-
TD1 -- Automates et langages rationnels
[Exercices]
[Correction]
[Anglais]
[Sources]
-
TD2 -- Automates et langages rationnels (avancé) : lemme d'Arden,
lemme de pompage, monoïdes
[Exercices]
[Correction]
[Anglais]
[Sources]
-
TD3 -- Automates et langages rationnels (avancé) : non
équivalence des lemmes de pompage et Brzozowski
[Exercices]
[Correction]
[Anglais]
[Sources]
-
TD4 -- Grammaires de langages et Myhill-Nerode
[Exercices]
[Correction]
[Anglais]
[Sources]
-
TD5 -- Grammaires hors contexte, Forme Normale de Chomsky
[Exercices]
[Correction]
[Anglais]
[Sources]
-
TD6 -- Machines de Turing
[Exercices]
[Correction]
[Sources]
-
TD7 -- Langages P, NP et co-NP
[Exercices]
[Correction]
[Anglais]
[Sources]
-
TD8 -- Problèmes NP-complets
[Exercices]
[Correction]
[Anglais]
[Sources]
-
TD9 -- NPC, hiérarchie temporelle, EXPTIME et PSPACE complétudes
[Exercices]
[Correction]
[Anglais]
[Sources]
-
TD10 -- Classes de complexité définies par circuits (AC, NC, TC)
[Exercices]
[Correction]
[Anglais]
[Sources]
-
TD11 -- Classe de complexité BPP, théorème de Rice, Castors affairés
[Exercices]
[Correction]
[Anglais]
[Sources]