Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Machine de Turing probabiliste
Résumé
En théorie de la complexité, une machine de Turing probabiliste (ou randomisée) est une machine de Turing qui peut utiliser du hasard. Ce genre de machine permet de définir des classes de complexité intéressantes et de donner un modèle de calcul pour les algorithmes probabilistes comme le test de primalité de Miller-Rabin.
Il existe différentes définitions équivalentes des machines de Turing probabilistes. Dans la suite tous les tirages sont indépendants et uniformes.
Un machine de Turing probabiliste, est une machine de Turing déterministe ayant deux bandes d'entrée : l'une qui contient la vraie entrée du problème et l'autre contient une série de bits aléatoires. Les transitions peuvent dépendre de cette seconde bande, ce qui équivaut à faire des choix aléatoires pendant une exécution de la machine.
Une machine de Turing probabiliste peut aussi être une machine non déterministe qui choisit à chaque étape les transitions selon une certaine loi de probabilité. On peut même restreindre cette définition à une machine choisissant à chaque pas entre deux transitions avec une probabilité 1/2 pour chacune.
Les conditions d'acceptation sont plus complexes que pour une machine de Turing classique : elles dépendent le plus souvent de la probabilité d'acceptation et de rejet sur une exécution. (Pour le formalisme avec bande d'aléas, ces probabilités sont celles d'acceptation alors que l'on n'a pas encore tiré les bits aléatoires.)
Par exemple, pour une machine traitant un problème de la classe RP, si le mot n'est pas dans le langage la machine le rejettera toujours et s'il est dans le langage, elle l'acceptera avec une probabilité d'au moins 1/2.
Les différentes conditions d'acceptation et de rejet, ainsi que des conditions sur le temps de calcul permettent de définir une grande famille de classes de complexité, dont les plus courantes sont celles en temps polynomial : RP, co-RP, BPP et ZPP.
On peut considérer que l'idée de faire des calculs basés sur du hasard a pour origine les méthodes de Monte-Carlo en analyse numérique et en statistiques.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.