| Titre : | Langages formels calculabilité et complexité |
| Auteurs : | Olivier Carton ; Dominique Perrin |
| Type de document : | texte imprimé |
| Editeur : | Paris : Vuibert, 2008 |
| ISBN/ISSN/EAN : | 978-2-7117-2077-4 |
| Format : | 1 vol. (237 p.) / ill., couv. ill. en coul. / 26 cm |
| Note générale : | Bibliogr. Index |
| Langues originales: | |
| Index. décimale : | 511.3 (Logique mathématique ) |
| Catégories : | |
| Mots-clés: | Langages formels Fonctions calculables Complexité de calcul (informatique) |
| Résumé : |
Cet Ouvrage correspond à un cours d’introduction à l’informatique théorique pour des étudiants de master. Il couvre aussi une grande partie du programme de l’option informatique de l’agrégation de mathématiques. Solidement structuré en chapitres, paragraphes et sous-paragraphes, il donne les définitions, puis les démonstrations des lemmes, propositions et théorèmes en les agrémentant, au fil du texte, de nombreux exemples et exercices corrigés. Divisé en deux parties, Langages formels et Calculabilité et complexité, il aborde successivement : 1) Les langages rationnels : premières définitions, opérations rationnelles, combinatoire des mots, ordres sur les mots et les arbres, automates, opérations booléennes, étoiles. 2) Les langages algébriques : grammaires algébriques, systèmes d’équations, arbres de dérivation, propriétés de clôture, automates à pile. 3) La calculabilité : notions de problème et de codage, machines de Turing, langages récursivement énumérables, langages décidables, problème de correspondance de Post, théorème de récursion, machines linéairement bornées, décidabilité de théories logiques, fonctions récursives. |
| Côte titre : | S8/75044-75047 |
Exemplaires (7)
| Cote | Support | Localisation | Disponibilité |
|---|---|---|---|
| S8/75044 | Livre | Bibliothèque centrale | Disponible |
| S8/75045 | Livre | Bibliothèque centrale | Disponible |
| S8/75046 | Livre | Bibliothèque centrale | Disponible |
| S8/75047 | Livre | Bibliothèque centrale | Disponible |
| S8/75356 | Livre | Bibliothèque centrale | Disponible |
| S8/75357 | Livre | Bibliothèque centrale | Disponible |
| S8/75358 | Livre | Bibliothèque centrale | Disponible |
Accueil
