Calculabilité et complexité
ours & exercices corrigés. LICENCE Tous les corrigés détaillés. Calculabilité et complexité ... langages formels que la calculabilité et la complexité.
Quelques exercices de calculabilité et complexité
Quelques exercices de calculabilité et complexité. Exercice 1 – Fonction d'Ackerman. La fonction d'Ackerman est la fonction ? ?2 ? ? telle que.
Calculabilité
Ce chapitre présente les principaux résultats de la calculabilité. Exercice 8.1 (corrigé page ??) ... Langages formels calculabilité et complexité.
Calculabilité
Calculabilité vs Complexité . 1.2.1 Exercices – des fonctions RP plus compliquées . ... 2.7 Exercices – analyse de décidabilité de probl`emes .
Complexité et calculabilité
22 sept. 2021 LOOP-calculables sont totales (c-à-d définies partout). Exercice : montrez que l'instruction (IF (x = 0) THEN P ELSE Q FI) est LOOP-calculable.
Langages formels calculabilité et complexité I. Automates et langages
26 sept. 2013 Langages formels calculabilité et complexité ... Exercice : prouver la cloture par h?1. ... On corrige la définition de µ. g(x) =.
Examen Final Corrigé rédigé par Paul Brunet et Laure Gonnord 1
Solution: Aucun de ces deux mots n'est accepté le premier mot bloque la machine en q3
Langages formels Calculabilité et Complexité
parties : les langages formels d'une part calculabilité et complexité d'autre L'exercice suivant introduit une extension du théorème de Ramsey (théo-.
Examen Final Corrigé rédigé par Paul Brunet et Laure Gonnord 1
2. 3. MIF15 Complexité et Calculabilité Master Info - 2015-2016. 4/7. Page 5. Le probl`eme Clique s'énonce de la mani`ere suivante : Clique : entrée : un
Lyon 1 2015 – 2016 MIF15 – Calculabilité et complexité Support de
MIF15 – Calculabilité et complexité. Support de cours. 1 / 22. Calculabilité et complexité. Support de cours. MACHINES DE TURING .
[PDF] Calculabilité et complexité
AGRÉGATION MATHÉMATIQUES Olivier Carton • Cours complet • Exercices d'application • Tous les corrigés détaillés Calculabilité et complexité
[PDF] Complexité et calculabilité - LaBRI
LOOP-calculables sont totales (c-à-d définies partout) Exercice : montrez que l'instruction (IF (x = 0) THEN P ELSE Q FI) est LOOP-calculable
[PDF] Calculabilité - Irif
Calculabilité vs Complexité 1 2 1 Exercices – des fonctions RP plus compliquées 2 7 Exercices – analyse de décidabilité de probl`emes
[PDF] Langages formels calculabilité et complexité - Examen du 2 février
2 fév 2012 · Langages formels calculabilité et complexité Examen du 2 février 2012 Corrigé version ?1 Exercice 1 – Grammaires : un petit exercice
[PDF] Calculabilité / Complexité (L3) Examen “Complexité” ´Enoncés et
Calculabilité / Complexité (L3) Examen “Complexité” ´Enoncés et solutions? Exercice (6 points) Pour un entier k > 0 et un alphabet fini A une fonction
[PDF] Langages formels Calculabilité et Complexité - ENS Lyon
parties : les langages formels d'une part calculabilité et complexité d'autre L'exercice suivant introduit une extension du théorème de Ramsey (théo-
[PDF] Cours de calculabilité et complexité
Donc `a une pair (q b) correspond un ensemble de triples (q b X) o`u X ? {L R} la machine peut choisir n'importe lequel de ces triplets Exercice :
Master 1 Informatique et Mathématiques Complexité et calculabilité
Soit A = {a b } un alphabet On note · l'opérateur de concaténation des mots Si E1 et E2 sont deux ensembles de exercices corriges pdf
[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
[PDF] Exercice 1 : Complexité des algorithmes (8 points) DIU Enseigner l
4 juil 2019 · L'algorithme n'a pas produit une solution optimale Exercice 3 : Correction des algorithmes (6 points) Question 3 1 : Ecrire une version naïve
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
C e livreest une introduction à l'informatique théorique qui couvre aussi bien les langages formels que la calculabilité et la complexité. Il existe d'excellents ouvrages en anglais couvrant ces diérents sujets mais très peu en français. Celui-ci tente hum- blement de combler cette lacune. L'objectif est d'appréhender les limites des ordinateurs et de comprendre ce qu'il est possible ou impossible de faire avec eux. Cette question est délicate mais fondamentale puisqu'elle touche à l'essence de la notion de calculable. Elle est considérée tout au long de cet ouvrage à travers diérents modèles de calculs : automates, automates à pile et machines de Turing. Les questions de calculabilité et de complexité ne sont abordées que dans la secondepartie de l'ouvrage. La première partie est consacrée à la théorie des automates qui est un
préambule indispensable. La théorie des automates s'est développée dès la naissance de
l'informatique théorique. Elle en est maintenant le socle sur lequel s'appuie le reste. Bien que les automates soient un modèle très simple, ils jouissent de remarquables propriétés et leur étude est encore très active aujourd'hui. La théorie des automates a des liensétroits avec l'arithmétique, la combinatoire, l'algèbre, la topologie, la logique, la théorie
des jeux et l'algorithmique. Les automates sont aussi au c÷ur de nombreuses applications en informatique du génome, en traitement des langues naturelles et en arithmétique des ordinateurs. La théorie de la complexité s'est épanouie plus récemment que la théorie des automates mais c'est maintenant un domaine très dynamique. La seconde partie de cet ouvrage couvre les thématiques centrales de ce vaste sujet. Quelques thématiques plus spécialisées comme les approximations et les algorithmes randomisés ne sont pas abordées.La première partie est consacrée à la théorie des langages formels. Des éléments de
combinatoire des mots et des ordres font oce d'introduction. Ces sujets sont trop ra- rement abordés dans ce type d'ouvrages. Les automates nis et les langages rationnels forment la trame de ce chapitre. Le théorème de Kleene, les automates déterministes et la minimisation sont incontournables et occupent une place importante. Viennent ensuite des prolongements dans des sujets moins classiques. La théorie algébrique des langages et en particulier l'étude des langages sans étoile terminent le premier chapitre. Le second chapitre est consacré aux grammaires et aux langages algébriques. Les liens ii lfcc 2014/5/15 15:32 page 10 #8 ii i iiavec les systèmes d'équations y sont particulièrement développés pour obtenir le théo-
rème de Parikh. Après les propriétés principales de clôture des langages algébriques, les
automates à pile sont introduits et étudiés. Cette étude passe par l'équivalence avec les
grammaires et les automates déterministes. Des compléments sur les contenus de pile et le groupe libre concluent cette première partie. La seconde partie est consacrée à la calculabilité et à la complexité. Ces deux no- tions fondamentales sont introduites à travers les machines de Turing mais les fonctionsrécursives sont également abordées. L'équivalence entre ces deux dénitions de la notion
de calculable est démontrée. Le problème de Post et son indécidabilité permettent en- suite d'exhiber des questions plus naturelles, sur les grammaires par exemple, auxquelles les réponses ne sont pas calculables. Un détour par les machines linéairement bornées conduit au théorème d'Immerman et Szelepcsényi. La NP-complétude constitue le c÷ur du second chapitre mais la complexité en espace est aussi largement développée. L'es-pace logarithmique et l'espace polynomial sont l'un et l'autre étudiés en détail à travers
la notion de complétude. Ce chapitre se termine par une introduction aux machines alternantes et par la preuve du théorème d'Hartmanis sur les machines à une bande en tempsO(nlogn). Ce livre s'adresse aux étudiants en master d'informatique ou de mathématiques. Tout master d'informatique comporte un cours sur les automates nis, la compilation et lesautomates à pile. La calculabilité et la complexité sont indispensables à tout étudiant
désireux d'avoir une base solide en informatique fondamentale. L'approche rigoureuse conviendra parfaitement aux étudiants en mathématiques ayant une inclination vers l'informatique. Cet ouvrage couvre une grande part du programme de l'option informa- tique de l'agrégation de mathématiques. Il sera sans nul doute propice à de nombreux développements pour les leçons d'oral. Des exercices corrigés permettent une bonne as- similation. Aucune connaissance préalable n'est requise. Il est seulement supposé que le lecteurmaîtrise quelques éléments de mathématiques enseignés en première année universi-
taire. Le premier objectif de cet ouvrage est d'introduire et d'expliquer les premières notions d'informatique fondamentale. De nombreux exemples illustrent les dénitions. Les diérentes notions sont mises en perspective et des connexions entre des concepts en apparence éloignés sont établies. Le second objectif est de permettre d'aller plus loin. Chacun des chapitres comprend des compléments. Ces compléments ont souvent étéchoisis parce qu'ils permettent d'aborder des résultats élégants sans toutefois nécessiter
la mise en place d'une machinerie lourde. Le prix à payer est la technicité de quelquespassages. Les choix ont aussi été guidés par des préférences personnelles assumées. Ces
compléments sont l'occasion de montrer quelques joyaux parmi lesquels, le théorème de Schüzenberger, le théorème de Parikh et le théorème d'Immerman et Szelepcsényi. Outre la correction de quelques coquilles, cette seconde édition se distingue de la première par l'ajout d'un certain nombre d'exercices et de leurs corrections.Internet
Une page WEB contenant une liste d'errata et d'autres informations se trouve à l'adresse suivante : ii lfcc 2014/5/15 15:32 page 15 #13 iiquotesdbs_dbs45.pdfusesText_45[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
[PDF] isoe prof principal