Calculabilité
2.7 Exercices – analyse de décidabilité de probl`emes . Introduction `a la calculabilité : Cours et exercices corrigés 2e édition
Calculabilité
Exercice 8.1 (corrigé page ??). Soit A le langage constitué de la seule chaine s où s = { 0 si Dieu n'existe pas. 1 si Dieu existe. Est-ce que A est décidable?
Complexité et calculabilité
Langages formels Calculabilité et Complexité. Vuibert
Polycopié
démonstration logique et de connaitre aussi la décidabilité et la calculabilité Wolper Pierre
Calculabilité et décidabilité : TD3
14 févr. 2012 La preuve se fait par induction sur la longueur d'une dérivation de. C ⊣ σ → σ ).) Exercice 4. Soit σ le store X ↦→ (nil.nil) et C la ...
Leçon 914 : Décidabilité et indécidabilité. Exemples.
— Définition : MT / langages décidables / fonction calculables. — Théorèmes : équivalence de ces modèles. — Thèse de Church. 1.2 Des problèmes de décision. Ce
Calculabilité et complexité
3.8 Décidabilité de théories logiques . Des exercices corrigés permettent une bonne as- similation. Aucune ...
Séance 6 : Décidabilité et Complexité
Plusieurs modèles de calcul sont utilisés en calculabilité: machines de Turing machine à compteurs lambda-calcul automates cellulaires fonctions récursives etc.
Kit de survie - Calculabilité
— B décidable implique A décidable. (le schéma donne un algorithme pour A) Mathématiques de l'informatique : cours et exercices corrigés. Dunod. [Garey ...
annexe i: fiches descriptives des unites denseignement (ue) et des
Saleri – Calcul scientifique Cours
Calculabilité
Exercice 8.7 (corrigé page ??). Soit E ? N un ensemble décidable. Montrer qu'il est énuméré par une fonction calculable f strictement croissante. Exercice 8.8
Calculabilité
2.7 Exercices – analyse de décidabilité de probl`emes . En préparant mon cours de la Calculabilité je me suis basé sur le cours fait `a l'UJF par.
Complexité et calculabilité
22 sept. 2021 Calculabilité et Décidabilité. ... (théorie de la calculabilité) ; ... Exercice : montrez que l'instruction (IF (x = 0) THEN P ELSE Q FI).
MAIN4 Année 2021/2022 Calculabilité - Décidabilité (ICC) TD n°2
Calculabilité - Décidabilité (ICC). TD n°2 - Automates à pile et grammaires hors-contexte. Exercice 1. Décrire des grammaires hors-contexte pour les
Calculabilité
Exercice 8.1. Soit A le langage constitué de la seule chaine s où s = { 0 si Dieu n'existe pas. 1 si Dieu existe. Est-ce que A est décidable? Pourquoi?
Langages formels calculabilité et complexité - Examen du 2 février
2 févr. 2012 Analyser la décidabilité/complexité de ce problème. ... Exercice 2 – Calculabilité : problème de Collatz et fonctions analytiques.
Leçon 914 : Décidabilité et indécidabilité. Exemples.
Exemples. Julie Parreaux. 2018 - 2019. [1] Carton Langages formels
Calculabilité et complexité
ours & exercices corrigés. LICENCE 3.8 Décidabilité de théories logiques . ... langages formels que la calculabilité et la complexité.
Cours Logique et Calculabilité
Cependant ils restent restreints à l'ensemble des fonctions calculables
Machine de Turing - Informatique Théorique 2 Licence 3 informatique
Exercice. L'ensemble des machines de Turing est-il dénombrable ? Existe-il un ensemble de fonctions non-dénombrables ? Existe-t-il des fonctions non calculables
[PDF] Calculabilité - Irif
Ce document contient les notes de cours et les exercices de TDs de la Calculabilité que j'ai faits en 2000-2003 pour la ma?trise d'informatique `a
[PDF] Complexité et calculabilité - LaBRI
Langages formels Calculabilité et Complexité Vuibert 2008 J M Autebert Calculabilité et Décidabilité Masson 1992
[PDF] Calculabilité et décidabilité : TD3 - LIPN
14 fév 2012 · Calculabilité et décidabilité : TD3 Exercice 1 correction des programmes développés dans les exercices 8 et 9 du TD2
[PDF] Calculabilité et complexité
ours exercices corrigés LICENCE 3 4 Langages décidables langages formels que la calculabilité et la complexité Il existe d'excellents ouvrages
Introduction à la calculabilité : Cours et exercices corrigés PDF
Introduction à la calculabilité : Cours et exercices corrigés By Pierre Wolper Pages ISBN: PDF/DJVU 102 MB Dans le Calculabilité et décidabilité : une
[PDF] Kit de survie - Calculabilité - Irisa
Supposons que Arrêt est décidable Il existe donc une machine de Turing A : — qui s'arrête sur toute entrée Mw ; — telle que
Exercices Calculabilité-2019 PDF Informatique - Scribd
2 Montrer que les fonctions suivantes sont primitives récursives : · 3 Montrer que les relations R1 et R2 définies comme suit sont décidables : · 14 Lesquelles
[PDF] Cours de calculabilité et complexité
Indécidabilité - Décidabilité • Complexité calculabilité et complexité (ii) vous avez suivi Exercices : établissez ces trois affirmations
[PDF] Leçon 914 : Décidabilité et indécidabilité Exemples
Leçon 914 : Décidabilité et indécidabilité Exemples Julie Parreaux 2018 - 2019 [1] Carton Langages formels calculabilité et complexité
[PDF] Examen Final Corrigé rédigé par Paul Brunet et Laure Gonnord
MIF15 Complexité et Calculabilité Examen Final Corrigé rédigé par Paul Brunet et Laure Gonnord Durée 1H30 Notes de cours et de TD autorisées
ISBN 978-2-311-01400-6
WWW.VUIBERT.FR
Langages formels. Calculabilité et complexitéCours & exercices corrigés9 782311 014006
LICENCE
3&MASTER
MATHÉMATIQUES
INFORMATIQUE
AGRÉGATION MATHÉMATIQUES
Olivier Carton
Langages formels
Calculabilité et complexité
Langages
formelsLICENCE3& MASTERMATHÉMATIQUES
& INFORMATIQUEAGRÉGATION
MATHÉMATIQUESOlivier Carton
Cours complet
Exercices d'application
Tous les corrigés détaillés
Calculabilité et complexité
Ce manuel est une
introduction à l'informatique fondamentaleprésentant tous les grands domaines de la théorie des langages formels aux notions de calculabilité et de complexité. Le coursest complété par de nombreux exercices dont les corrigés, très détaillés,assurent une mise en application efficace des différentes notions. Il s'adresse aux étudiants en Licence 3 et en Master de Mathématiques ou d'informatique ainsi qu'aux candidats à l'Agrégation de mathématiques, option informatique, dont il couvre l'essentiel du programme.Professeur d'informatique à l'université Paris Diderot (Paris 7), Olivier Cartonenseigne à tous les
niveaux, depuis le L1 jusqu'au M2, les différentes disciplines de l'informatique: programmation,algorithmique... Spécialiste des automates et des langages formels, il a également enseigné durant
plusieurs années à l'École normale supérieure de Paris (ENS Ulm).SommaireI. Langages formels
1. Langages rationnels
2. Langages algébriques
II. Calculabilité et complexité
3. Calculabilité4. Complexité
Au fil de chaque chapitre,
on trouvera des exercices suivis de leurs corrigés.CV_LangagesFormels:EP 20/05/14 11:24 Page 1
ii lfcc 2014/5/15 15:32 page 8 #6 ii i ii i ii lfcc 2014/5/15 15:32 page 3 #1 ii i ii iTable des matières P réface7Introduction9
Remerciements11
I Langages formels13
1 Langages rationnels15
1.1 Premières définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2 Opérations rationnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3 Combinatoire des mots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3.1 Périodicités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3.2 Mots infinis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.3.3 Motifs inévitables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.3.4 Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.4 Un peu d"ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.4.1 Quasi-ordres sur les mots . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.4.2 Ordres sur les mots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.4.3 Quasi-ordres sur les arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.5 Langages rationnels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.5.1 Expressions rationnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.5.2 Automates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.6 Automates déterministes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
1.7 Automate minimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
1.7.1 Quotients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
1.7.2 Congruence de Nerode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
1.7.3 Calcul de l"automate minimal . . . . . . . . . . . . . . . . . . . . . . . . . 54
1.8 Propriétés de clôture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
1.8.1 Opérations booléennes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
1.8.2 Morphisme et morphisme inverse . . . . . . . . . . . . . . . . . . . . . . . 58
1.9 Lemme de l"étoile et ses variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
1.10 Hauteur d"étoile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
1.11 Reconnaissance par morphisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
1.12 Langages sans étoile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
1.13 Compléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
1.13.2 Rationnels d"un monoïde quelconque . . . . . . . . . . . . . . . . . . . . . 80
ii lfcc 2014/5/15 15:32 page 4 #2 ii i ii i4Table des matières4Table des matières4Table des matières2 Langages algébriques83
2.1 Grammaires algébriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2.1.1 Définitions et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2.1.2 Grammaires réduites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
2.1.3 Grammaires propres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
2.1.4 Forme normale quadratique . . . . . . . . . . . . . . . . . . . . . . . . . . 90
2.2 Systèmes d"équations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
2.2.1 Substitutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
2.2.2 Système d"équations associé à une grammaire . . . . . . . . . . . . . . . . 92
2.2.3 Existence d"une solution pourS(G) . . . . . . . . . . . . . . . . . . . . . 93
2.2.4 Unicité des solutions propres . . . . . . . . . . . . . . . . . . . . . . . . . 94
2.2.5 Théorème de Parikh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
2.2.6 Systèmes d"équations en commutatifs . . . . . . . . . . . . . . . . . . . . 95
2.2.7 Solutions rationnelles des systèmes commutatifs . . . . . . . . . . . . . . . 96
2.3 Arbres de dérivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
2.3.1 Ambiguïté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
2.3.2 Lemme d"itération . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
2.3.3 Applications du lemme d"itération . . . . . . . . . . . . . . . . . . . . . . 103
2.3.4 Ambiguïté inhérente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
2.4 Propriétés de clôture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
2.4.1 Opérations rationnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
2.4.2 Substitution algébrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
2.4.3 Intersection avec un rationnel . . . . . . . . . . . . . . . . . . . . . . . . . 107
2.4.4 Morphisme inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
2.4.5 Théorème de Chomsky et Schützenberger . . . . . . . . . . . . . . . . . . 110
2.5 Forme normale de Greibach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
2.6 Automates à pile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
2.6.1 Définitions et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
2.6.2 Différents modes d"acceptation . . . . . . . . . . . . . . . . . . . . . . . . 116
2.6.3 Équivalence avec les grammaires . . . . . . . . . . . . . . . . . . . . . . . 119
2.6.4 Automates à pile déterministes . . . . . . . . . . . . . . . . . . . . . . . . 123
2.7 Compléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
2.7.1 Réécriture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
2.7.2 Contenus de pile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
2.7.3 Groupe libre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
II Calculabilité et complexité133
3 Calculabilité135
3.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
3.1.1 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
3.1.2 Logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
3.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
3.2.1 Notion de problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
3.2.2 Notion de codage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
3.2.3 Machines de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
3.2.4 Graphe des configurations . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
3.2.5 Normalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
3.2.6 Variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
3.3 Langages récursivement énumérables . . . . . . . . . . . . . . . . . . . . . . . . . 155
ii lfcc 2014/5/15 15:32 page 5 #3 ii i ii iTable des matières5Table des matières5Table des matières5 3 .4 Langages décidables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1583.5 Problème de correspondance de Post . . . . . . . . . . . . . . . . . . . . . . . . . 163
3.5.1 Présentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
3.5.2 Indécidabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
3.5.3 Application aux grammaires algébriques . . . . . . . . . . . . . . . . . . . 166
3.6 Théorème de récursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
3.7 Machines linéairement bornées . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
3.7.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
3.7.2 Grammaires contextuelles . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
3.7.3 Décidabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
3.7.4 Complémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
3.8 Décidabilité de théories logiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
3.9 Fonctions récursives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
3.9.1 Fonctions primitives récursives . . . . . . . . . . . . . . . . . . . . . . . . 180
3.9.2 Fonctions récursives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
3.9.3 Équivalence avec les machines de Turing . . . . . . . . . . . . . . . . . . . 185
3.9.4 Thèse de Church . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
3.10 Compléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
3.10.1 Écritures des entiers dans une base . . . . . . . . . . . . . . . . . . . . . . 187
3.10.2 Machines de Turing sans écriture sur l'entrée . . . . . . . . . . . . . . . . 189
4 Complexité193
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
4.1.1 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
4.1.2 Définition des complexités . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
4.2 Complexité en temps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
4.2.1 Théorème d'accélération . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
4.2.2 Changements de modèles . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
4.2.3 Classes de complexité en temps . . . . . . . . . . . . . . . . . . . . . . . . 196
4.2.4NP-complétude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
4.2.5NP-complétude deSatet3Sat. . . . . . . . . . . . . . . . . . . . . . . . 203
4.2.6 Exemples de problèmesNP-complets . . . . . . . . . . . . . . . . . . . . . 206
4.3 Complexité en espace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
4.3.1 Changement de modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
4.3.2 Classes de complexité en espace . . . . . . . . . . . . . . . . . . . . . . . . 221
4.3.3 Complexités en temps et en espace . . . . . . . . . . . . . . . . . . . . . . 221
4.3.4 Exemples de problèmes dansPSpace. . . . . . . . . . . . . . . . . . . . 222
4.3.5PSpace-complétude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
4.3.6 Espace logarithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
4.3.7NL-complétude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
4.4 Théorèmes de hiérarchie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
4.5 Machines alternantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
4.5.1 Définitions et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
4.5.2 Complémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
4.5.3 Automates alternants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
4.5.4 Classes de complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
4.6 Compléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
Bibliographie251
Index253
ii lfcc 2014/5/15 15:32 page 12 #10 ii i ii i ii lfcc 2014/5/15 15:32 page 7 #5 ii i ii iPréface V o iciun nouveau livre d'introduction à la théorie des langages, de la calculabilité et de la complexité. Un de plus? non, car il s'inscrit dans l'évolution et l'enrichissementcontinuel de ce ce sujet et qu'il témoigne de sa vitalité et de son mûrissement. Loin d'être
encore un domaine standardisé, il n'est plus non plus à ses débuts et son exposition s'estenrichie au fur et à mesure de l'expérience acquise en l'enseignant à des publics variés.
Il n'existe pas pour l'instant de présentation standardisée de cette théorie, au sens où le livre de Feller a pu en constituer une pour les probabilités. La tentative d'Eilenberg d'en constituer une s'est arrêtée en chemin puisque les deux premiers volumes (automates puis semigroupes) ne furent jamais suivis des deux autres prévus initialement (langages algébriques puis calculabilité). Ce livre représente un choix pragmatique fondé sur un enseignement réalisé en inter- action avec des étudiants. C'est un choix original de sujets et il dévoile au l des pages les prolongements des éléments de base vers des sujets plus spécialisés. En ce sens, il constitue une introduction stimulante, qui donne envie d'aller plus loin aux débutants et réserve des surprises aux spécialistes du domaine. Il plaira spécialement aux étudiants ayant le goût des mathématiques discrètes, mais aussi à ceux qui aiment les algorithmes. On y trouvera ainsi aussi bien un résultat peu connu de Guibas et Odlyzko sur les polynômes de corrélation qu'un programme en C s'écrivant lui même comme illustration du théorème de récursion. La présentation est exceptionnellement claire et les preuves sont données avec grand soin. Signe des temps de recherche de qualité, les exercices sont accompagnés de solutions qui sont la seule garantie que l'exercice est faisable (on se souvient d'un manuel proposant en exercice de résoudre le problème de correspondance de Post sur un alphabet de moins de quatre lettres...). Bon voyage donc au lecteur qui aborde ce sujet et auquel je souhaite autant de plaisir que j'en ai éprouvé à la lecture desNotions sur les grammaires formellesde Gross et Lentin qui m'a permis de le découvrir moi-même je crois bien que c'était en 1968.Dominique Perrin
ii lfcc 2014/5/15 15:32 page 14 #12 ii i ii i ii lfcc 2014/5/15 15:32 page 9 #7 ii i ii iIntroduction S 'il n'y pas de solution, c'est qu'il n'y a pas de problèmeDevise Shadoks
Cquotesdbs_dbs16.pdfusesText_22[PDF] fonction calculable
[PDF] langage récursif
[PDF] épaisseur atmosphère saturne
[PDF] fonction primitive récursive exercice corrigé
[PDF] théorème de godel démonstration
[PDF] codage de godel
[PDF] théorème de gödel pdf
[PDF] arithmétique de robinson
[PDF] nombre de godel
[PDF] godel dieu
[PDF] théorème d'incomplétude pour les nuls
[PDF] incomplétude définition
[PDF] introduction ? la calculabilité pdf
[PDF] indemnité prof principal 2017