Mathématiques de l'informatique : cours et exercices corrigés

Auteur(s) :

Dehornoy, Patrick (1952-2019) Découvrir l'auteur

Éditeur(s)
- Dunod
Date
- DL 2000
Notes
- La couv. porte en plus : "licence, maîtrise, agrégation"
- Bibliogr. p. 299-300. Index
- Autre tirage : 2001
Langues
- Français
Description matérielle
- 1 vol. (XIII-303 p.) : ill., couv. ill. en coul. ; 24 cm
Collections
- Sciences sup
Sujet(s)
ISBN
- 978-2-10-004446-7 ;
- 2-10-004446-X
Indice
- 51 Ouvrages généraux de mathématiques, ouvrages de vulgarisation
Tables des matières
- - Mathématiques de l'informatique
  - Cours et exercices corrigés
  - Patrick Dehornoy
  - Dunod
  - Avant-proposXI
  - Chapitre 1 Mots, langages et arbres1
  - 1.1 Le type mot1
  - 1.1.1 Mots2
  - 1.1.2 Concaténation3
  - 1.1.3 Monoïdes4
  - 1.1.4 Ordre préfixe6
  - 1.2 Le type langage7
  - 1.2.1 Opérations sur les langages8
  - 1.2.2 Homomorphismes10
  - 1.2.3 Notion de langage décidable11
  - 1.3 Le type arbre12
  - 1.3.1 Ordres et graphes12
  - 1.3.2 Arbres15
  - 1.3.3 Arbres et graphes17
  - 1.3.4 Niveaux et branches19
  - 1.3.5 Parcours d'arbres21
  - Chapitre 2 Monoïdes et groupes libres23
  - 2.1 Structures libres23
  - 2.1.1 Variétés équationnelles24
  - 2.1.2 Sous-structure engendrée par une partie25
  - 2.1.3 Familles libres26
  - 2.1.4 Bases27
  - 2.1.5 Congruences et quotients29
  - 2.2 Monoïdes libres32
  - 2.2.1 Familles génératrices32
  - 2.2.2 Familles libres33
  - 2.2.3 Bases33
  - 2.2.4 Congruences34
  - 2.2.5 Présentations35
  - 2.3 Groupes libres36
  - 2.3.1 Construction des groupes libres37
  - 2.3.2 Présentations de groupes40
  - Chapitre 3 Automates47
  - 3.1 Automates47
  - 3.1.1 La notion d'automate47
  - 3.1.2 Langages automatiques51
  - 3.2 Construction d'automates52
  - 3.2.1 Construction directe52
  - 3.2.2 Opérations booléennes54
  - 3.2.3 Homomorphismes56
  - 3.3 Extensions de la notion d'automate57
  - 3.3.1 Automates non déterministes57
  - 3.3.2 Epsilon-transitions62
  - Chapitre 4 Langages automatiques69
  - 4.1 L'automate minimal d'un langage69
  - 4.1.1 Minimalisation d'un automate69
  - 4.1.2 Classes à droite suivant un langage75
  - 4.1.3 Un exemple important79
  - 4.1.4 Applications80
  - 4.2 Expressions régulières82
  - 4.2.1 Propriétés de clôture82
  - 4.2.2 Le théorème de Kleene83
  - 4.2.3 Applications85
  - 4.2.4 Alphabet à un élément86
  - 4.3 Propriétés d'itération87
  - Chapitre 5 Grammaires formelles93
  - 5.1 Réécriture et productions93
  - 5.1.1 Règles de réécriture94
  - 5.1.2 Productions94
  - 5.2 Construction de grammaires97
  - 5.2.1 Grammaires régulières98
  - 5.2.2 Quelques exemples98
  - 5.2.3 Systèmes d'équations dans les langages100
  - 5.2.4 Grammaires formelles comme modèles103
  - 5.2.5 Opérations sur les langages algébriques104
  - 5.3 Grammaires de formes particulières105
  - 5.3.1 Suppression des epsilon-productions106
  - 5.3.2 Suppression des productions-unité108
  - 5.3.3 Forme normale de Chomsky110
  - 5.3.4 Forme normale de Greibach111
  - Chapitre 6 Arbres de dérivation et automates à pile117
  - 6.1 Arbres de dérivation117
  - 6.1.1 Arbres de dérivation117
  - 6.1.2 La propriété d'itération121
  - 6.1.3 Propriétés de non-clôture123
  - 6.2 Principe de l'analyse syntaxique124
  - 6.2.1 Analyse descendante124
  - 6.2.2 Tables d'analyse126
  - 6.3 Automates à pile128
  - 6.3.1 Automates à pile129
  - 6.3.2 Automates à pile déterministes134
  - Chapitre 7 Machines de Turing137
  - 7.1 Machines de Turing137
  - 7.1.1 Notion générale de calcul138
  - 7.1.2 Machines de Turing pour un ruban139
  - 7.1.3 Ensemble décidé par une machine de Turing142
  - 7.2 Simulation entre machines de Turing145
  - 7.2.1 Machines de Turing pour plusieurs rubans146
  - 7.2.2 Simulation150
  - 7.3 Construction de machines de Turing156
  - 7.3.1 Fonctions MT-calculables156
  - 7.3.2 Représentation des entiers159
  - 7.3.3 Quelques exemples160
  - 7.3.4 Indépendance du choix de la base163
  - 7.3.5 Propriétés de clôture164
  - 7.3.6 Réels MT-calculables165
  - Chapitre 8 Fonctions récursives171
  - 8.1 Notion de fonction récursive171
  - 8.1.1 Définitions de fonctions171
  - 8.1.2 Calculabilité175
  - 8.1.3 Ensembles récursifs176
  - 8.2 Récursivité des fonctions MT-calculables179
  - 8.2.1 Fonctions usuelles179
  - 8.2.2 Récurrence multiple180
  - 8.2.3 Contrôle d'une machine de Turing182
  - 8.3 Deux contre-exemples186
  - 8.3.1 Le castor affairé186
  - 8.3.2 La fonction d'Ackermann188
  - Chapitre 9 Complexité algorithmique197
  - 9.1 La thèse de Church197
  - 9.1.1 Modèle de calcul197
  - 9.1.2 Classes de complexité200
  - 9.2 Machines de Turing non déterministes203
  - 9.2.1 Résolution et vérification203
  - 9.2.2 Complexité non déterministe205
  - 9.2.3 Le problème P = NP206
  - 9.3 Évaluation d'algorithmes207
  - 9.3.1 Algorithmes de tri207
  - 9.3.2 Multiplication des entiers209
  - 9.3.3 Calcul du pgcd212
  - 9.3.4 Multiplication des matrices214
  - Chapitre 10 Logique Booléenne221
  - 10.1 Formules et réalisations221
  - 10.1.1 Formules booléennes222
  - 10.1.2 Valeurs de vérité223
  - 10.1.3 Le théorème de compacité227
  - 10.2 Notion de preuve228
  - 10.2.1 Preuves par coupure228
  - 10.2.2 La méthode de résolution231
  - 10.3 Complexité du problème de satisfaisabilité236
  - 10.3.1 Le problème SAT236
  - 10.3.2 Problèmes NP-complets239
  - Chapitre 11 Logique du premier ordre243
  - 11.1 Calcul des prédicats243
  - 11.1.1 Termes et formules243
  - 11.1.2 Réalisations et satisfaction246
  - 11.1.3 Pouvoir d'expression249
  - 11.2 Théorèmes de complétude252
  - 11.2.1 Preuves253
  - 11.2.2 Applications257
  - 11.2.3 La méthode de résolution259
  - 11.3 Logique et complexité262
  - 11.3.1 Semidécidabilité262
  - 11.3.2 Indécidabilité264
  - 11.3.3 Incomplétude265
  - 11.3.4 Suites de Goodstein266
  - Solutions des exercices272
  - Bibliographie299
  - Index301
Origine de la notice:
- Abes ;
- SF ;
- BN ;
- OCLC ;
- AUROC ;
- FR-751131015