Calculabilité et décidabilité : une introduction / Jean-Michel, Autebert [ Livre]
Langue: Français ; de l'oeuvre originale, Français.Publication : Paris, Milan, Barcelone : Masson, 1992Description : 118 p. ; 24 cmISBN: 2225826323.Collection: Manuels informatiques Masson, 0249-6992Classification: 004.15 Langages formels, automates et calculabilitéRésumé: L'auteur présente plusieurs modèles de calcul parmi les plus répandus (machines RAM, machines de Turing, fonctions récursives) et montre leur équivalence comme argument de la thèse de Church. Il insiste sur la notion cruciale de problème indécidable, l'expose aussi didactiquement que possible et présente de manière progressive les concepts-clefs. Enfin, il esquisse les problèmes de complexité en introduisant en particulier le notion de problème NP-complet. Conçu comme un manuel de cours, l'exposé est suivi d'exercices. Sommaire Introduction Le modèle des machines RAM Le modèle des machines de Turing Thèse de Church Les problèmes indécidables Aperçu sur la complexité.Sujet - Nom commun: Logique symbolique et mathématique | Fonctions calculables | Décidabilité (logique mathématique) | Complexité de calcul (informatique) | Calcul formel | Automates mathématiques, Théorie des| Current location | Call number | Status | Notes | Date due | Barcode |
|---|---|---|---|---|---|
| ENS Rennes - Bibliothèque Informatique | 004.15 AUT (Browse shelf) | Exclu du prêt | 004.15 Langages formels, automates et calculabilité | 00010868 | |
| ENS Rennes - Bibliothèque Informatique | 004.15 AUT (Browse shelf) | Available | 004.15 Langages formels, automates et calculabilité | 000108681 |
Bibliogr. p. 115. Index
L'auteur présente plusieurs modèles de calcul parmi les plus répandus (machines RAM, machines de Turing, fonctions récursives) et montre leur équivalence comme argument de la thèse de Church. Il insiste sur la notion cruciale de problème indécidable, l'expose aussi didactiquement que possible et présente de manière progressive les concepts-clefs. Enfin, il esquisse les problèmes de complexité en introduisant en particulier le notion de problème NP-complet. Conçu comme un manuel de cours, l'exposé est suivi d'exercices.
Sommaire
Introduction
Le modèle des machines RAM
Le modèle des machines de Turing
Thèse de Church
Les problèmes indécidables
Aperçu sur la complexité