Cet ouvrage aborde les machines de Turing déterministes et non déterministes par leur aspect pratique : leur programmation pour résoudre un problème et produire des graphiques visualisant la complexité de ce problème. Ainsi, ce livre s'adresse à un public très large : les théoriciens trouveront une représentation graphique des théorèmes, les programmeurs découvriront les effets des programmes sur les ressources disponibles (temps et mémoire de calcul), les premiers pas des débutants seront facilités par le parti pris pratique de ce livre et les exemples, exercices et notes bibliographiques aideront à illustrer les cours.
Ce livre utilise le langage Mathematica car ses diverses fonctionnalités graphiques et symboliques facilitent l'écriture d'un simulateur de machine de Turing. Vous pourrez bien sûr réutiliser les exemples de ce livre dans un simulateur glané sur internet, mais la lecture de ce livre vous incitera à écrire votre propre simulateur.
Commande avant 16h,
expédié le jour même (lu. - ve.)
Livraison express sous 48h.
Rubrique :
Données - Informatique - I.A. - IHM
ISBN :
9782854288650
Référence :
865
Année de parution :
2008
Surtout, ne la cherchez pas dans un musée : aucune machine de Turing n'a jamais été construite. Inventée par Alan Turing au début des années 1930 pour résoudre un problème posé par le mathématicien David Hilbert au seuil du 20e siècle, une machine de Turing est un outil fondamental pour étudier la complexité des problèmes.
Cet ouvrage vous propose d'aborder les machines de Turing déterministes et non déterministes par leur aspect pratique : leur programmation pour résoudre un problème et produire des graphiques visualisant la complexité de ce problème.
Ainsi, ce livre s'adresse à un public très large: les théoriciens trouveront une représentation graphique des théorèmes, les programmeurs découvriront les effets des programmes sur les ressources disponibles (temps et mémoire de calcul), les premiers pas des débutants seront facilités par le parti pris pratique de ce livre et les exemples, exercices et notes bibliographiques aideront à illustrer les cours.
Ce livre utilise le langage Mathematica car ses diverses fonctionnalités graphiques et symboliques facilitent l'écriture d'un simulateur de machine de Turing. Vous pourrez bien sûr réutiliser les exemples de ce livre dans un simulateur glané sur internet, mais la lecture de ce livre vous incitera à écrire votre propre simulateur.
Éric Jacopin enseigne les machines de Turing à l'École Spéciale Militaire de Saint-Cyr depuis plusieurs années tandis que ses recherches portent sur la planification d'actions dans le domaine des jeux vidéo.
Cet ouvrage vous propose d'aborder les machines de Turing déterministes et non déterministes par leur aspect pratique : leur programmation pour résoudre un problème et produire des graphiques visualisant la complexité de ce problème.
Ainsi, ce livre s'adresse à un public très large: les théoriciens trouveront une représentation graphique des théorèmes, les programmeurs découvriront les effets des programmes sur les ressources disponibles (temps et mémoire de calcul), les premiers pas des débutants seront facilités par le parti pris pratique de ce livre et les exemples, exercices et notes bibliographiques aideront à illustrer les cours.
Ce livre utilise le langage Mathematica car ses diverses fonctionnalités graphiques et symboliques facilitent l'écriture d'un simulateur de machine de Turing. Vous pourrez bien sûr réutiliser les exemples de ce livre dans un simulateur glané sur internet, mais la lecture de ce livre vous incitera à écrire votre propre simulateur.
Éric Jacopin enseigne les machines de Turing à l'École Spéciale Militaire de Saint-Cyr depuis plusieurs années tandis que ses recherches portent sur la planification d'actions dans le domaine des jeux vidéo.
| Référence : | 865 |
| Niveau : | étudiants, programmeurs, théoriciens |
| Nombre de pages : | 264 |
| Format : | 15,5x23,5 |
| Reliure : | Broché |
| Rôle | |
|---|---|
| Jacopin Éric | Auteur |
Introduction
Quelques questions avant de commencer ?
Quels objectifs ?
Pourquoi Mathematica ?
Quelle version de Mathematica ?
Organisation du manuscrit
Pourquoi lire ce qui suit ?
Typographie
Lexique
Machine(s) de Turing
Problème(s) et résolution
Notations
Définitions et déclarations pour les machines déterministes
Définition d’une machine de Turing déterministe
Complexités déterministes en temps et en espace
Encodage informatique d’une machine de Turing
Encodage d’une fonction de transition déterministe
Exécution d’une fonction de transition déterministe
Exemples de caractérisations de la complexité déterministe
Reconnaître un mot du Langage L = {m¦m = 0i 1j 2k avec i = j = k et i = 1}
Reconnaître un mot du Langage L = {m¦m = 0i 1j 2k avec i ? j ? k, i = 1 et k = 1} Copier un nombre écrit en base 2
Divisibilité entière par 4 d’un nombre écrit en base 2
Division entière par 4 d’un nombre écrit en base 2
Le complément à 2 d’un nombre écrit en base 2
Multiplication additive de deux nombres écrits en base 1
Multiplication additive de deux nombres écrits en base 2
Multiplication par décalage de deux nombres écrits en base 2
Existence d’un chemin entre deux nœuds d’un graphe
Définitions et déclarations pour les machines non déterministes
Définition d’une machine non déterministe
Complexité non déterministe en temps
Complexité non déterministe en espace
Encodage informatique d’une machine non déterministe
Exécution d’une fonction de transition non déterministe
Exemples de caractérisations de la complexité non déterministe
Écrire et ne pas écrire sur le ruban de la machine
Satisfiabilité d’une formule booléenne
Emprunter tous les chemins possibles pour sortir d’un labyrinthe
Placer une reine sur une case d’un échiquier et ne pas la placer
Les puits déplacements d’un cavalier sur un échiquier
Conclusion
Références et notes bibliographiques
Alan Turing
Vulgarisation
D’autres simulateurs de machines de Turing
Problèmes et complexité
Manuels de cours
Pour aller plus loin...
Annexes
Annexe 1 : Le code Mathematica pour simuler l’exécution de machines
Annexe 2 : Notations mathématiques pour la comparaison de fonctions
Annexe 3 : Résumé de quelques machines
Vous aimerez aussi
