Le langage des machines : introduction à la calculabilité et aux langages formels / Robert, Floyd / Richard, Beigel [ Livre]

Auteur principal: Floyd, Robert W.Co-auteur: Beigel, RichardLangue: Français ; de l'oeuvre originale, Français.Publication : Paris : International Thomson publ. France, 1995Description : XVII-594 p. ; 24 cmISBN: 2841800105.Classification: F 4 Langages formels, automates et calculabilitéRésumé: Dans cet ouvrage de référence, les auteurs proposent une redéfinition des bases classiques de l'enseignement de la théorie des langages formels et de celles de la calculabilité. Ils y définissent un modèle simple et unifié de machine qui leur permet de rendre compte de tous les modèles de calculabilité existants (automates finis, automates à piles, machines de Turing, machine RAM....). Ce modèle s'inspire largement de la réalité du monde des ordinateurs, permettant ainsi de pénétrer bien plus facilement dans celui de l'informatique théorique. Cet ouvrage compte désormais parmi les rares textes en français traitant à la fois des machines de Turing, de la théorie de la récursion et des problèmes de complexité. Outre les nombreux résultats que l'on s' attend naturellement à trouver sur ces thèmes, les auteurs abordent également des sujets originaux, présentés de manière simple et élégante, tels l'indécidabilité de la résolution des équations diophantiennes exponentielles ou la NP-complétude de la non-équivalence des expressions rationnelles. Tous les exemples fournis sont étudiés en profondeur, complétés par des preuves mathématiques et illustrés par de nombreux exercices, dont le niveau de difficulté est progressif. Sommaire 0. Préliminaires mathématiques 1. Introduction aux machines 2. Mécanismes, machines et programmes 3. Simulation 4. Automates finis et langages rationnels 5. Langages algébriques 6. Automates à pile et machines à compteur 7. Calculabilité 8. Théorie de la récursivité 9. Complexité 10. Appendice.Sujet - Nom commun: Machines séquentielles, Théorie des | Langages formels | Fonctions calculables | Complexité de calcul (informatique) | Automates mathématiques, Théorie des | Automates
Current location Call number Status Notes Date due Barcode
ENS Rennes - Bibliothèque
Informatique
F 4 FLO (Browse shelf) Available F 4 Langages formels, automates et calculabilité 00000967

Index

Dans cet ouvrage de référence, les auteurs proposent une redéfinition des bases classiques de l'enseignement de la théorie des langages formels et de celles de la calculabilité. Ils y définissent un modèle simple et unifié de machine qui leur permet de rendre compte de tous les modèles de calculabilité existants (automates finis, automates à piles, machines de Turing, machine RAM....). Ce modèle s'inspire largement de la réalité du monde des ordinateurs, permettant ainsi de pénétrer bien plus facilement dans celui de l'informatique théorique.
Cet ouvrage compte désormais parmi les rares textes en français traitant à la fois des machines de Turing, de la théorie de la récursion et des problèmes de complexité. Outre les nombreux résultats que l'on s' attend naturellement à trouver sur ces thèmes, les auteurs abordent également des sujets originaux, présentés de manière simple et élégante, tels l'indécidabilité de la résolution des équations diophantiennes exponentielles ou la NP-complétude de la non-équivalence des expressions rationnelles.
Tous les exemples fournis sont étudiés en profondeur, complétés par des preuves mathématiques et illustrés par de nombreux exercices, dont le niveau de difficulté est progressif.
Sommaire
0. Préliminaires mathématiques
1. Introduction aux machines
2. Mécanismes, machines et programmes
3. Simulation
4. Automates finis et langages rationnels
5. Langages algébriques
6. Automates à pile et machines à compteur
7. Calculabilité
8. Théorie de la récursivité
9. Complexité
10. Appendice

Powered by Koha