Calculabilité et décidabilité : une introduction / Jean-Michel, Autebert [ Livre]

Auteur principal: Autebert, Jean-MichelLangue: 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: F 4 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
F 4 AUT (Browse shelf) Exclu du prêt F 4 Langages formels, automates et calculabilité 00010868
ENS Rennes - Bibliothèque
Informatique
F 4 AUT (Browse shelf) Available F 4 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é

Powered by Koha