Accès plus rapide que le navigateur!
18 relations: Algorithme probabiliste, BPP (complexité), Classe de complexité, Indépendance (probabilités), Informatique théorique, Langage formel, Lemme de Schwartz-Zippel, Machine de Turing probabiliste, NP (complexité), Oracle (machine de Turing), P (complexité), Polynôme, Problème de décision, Problème P ≟ NP, Test de primalité AKS, Test de primalité de Miller-Rabin, Théorie de la complexité (informatique théorique), ZPP (complexité).
Algorithme probabiliste
En algorithmique, un algorithme probabiliste, ou algorithme randomisé, est un algorithme qui utilise une source de hasard.
Nouveau!!: RP (complexité) et Algorithme probabiliste · Voir plus »
BPP (complexité)
En informatique théorique, plus précisément en théorie de la complexité, la classe BPP (bounded-error probabilistic polynomial time) est la classe de problèmes de décision décidés par une machine de Turing probabiliste en temps polynomial, avec une probabilité d'erreur dans la réponse inférieure à 1/3.
Nouveau!!: RP (complexité) et BPP (complexité) · Voir plus »
Classe de complexité
En informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource.
Nouveau!!: RP (complexité) et Classe de complexité · Voir plus »
Indépendance (probabilités)
Paire de dés: les résultats de chacun des dés sont indépendants. L'indépendance est une notion probabiliste qualifiant de manière intuitive des événements aléatoires n'ayant aucune influence l'un sur l'autre.
Nouveau!!: RP (complexité) et Indépendance (probabilités) · Voir plus »
Informatique théorique
Une représentation artistique d'une machine de Turing. Les machines de Turing sont un modèle de calcul. L'informatique théorique est l'étude des fondements logiques et mathématiques de l'informatique.
Nouveau!!: RP (complexité) et Informatique théorique · Voir plus »
Langage formel
Un langage formel, en mathématiques, en informatique et en linguistique, est un ensemble de mots.
Nouveau!!: RP (complexité) et Langage formel · Voir plus »
Lemme de Schwartz-Zippel
En mathématiques, le lemme de Schwartz-Zippel est un résultat important pour évaluer l'égalité entre deux polynômes multivariés.
Nouveau!!: RP (complexité) et Lemme de Schwartz-Zippel · Voir plus »
Machine de Turing probabiliste
En théorie de la complexité, une machine de Turing probabiliste (ou randomisée) est une machine de Turing qui peut utiliser du hasard.
Nouveau!!: RP (complexité) et Machine de Turing probabiliste · Voir plus »
NP (complexité)
La classe NP est une classe très importante de la théorie de la complexité.
Nouveau!!: RP (complexité) et NP (complexité) · Voir plus »
Oracle (machine de Turing)
Une machine de Turing avec oracle peut faire appel à une boîte noire (oracle). En théorie de la complexité ou de la calculabilité, les machines de Turing avec oracle sont une variante des machines de Turing disposant d'une boîte noire, un oracle, capable de résoudre un problème de décision en une seule opération élémentaire.
Nouveau!!: RP (complexité) et Oracle (machine de Turing) · Voir plus »
P (complexité)
La classe P, aussi noté parfois PTIME ou DTIME(nO(1)), est une classe très importante de la théorie de la complexité, un domaine de l'informatique théorique et des mathématiques.
Nouveau!!: RP (complexité) et P (complexité) · Voir plus »
Polynôme
Courbe représentative d'une fonction cubique. En mathématiques, un polynôme est une expression formée uniquement de produits et de sommes de constantes et d'indéterminées (aussi appelées variables), habituellement notées X, Y, Z, etc.
Nouveau!!: RP (complexité) et Polynôme · Voir plus »
Problème de décision
En informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ».
Nouveau!!: RP (complexité) et Problème de décision · Voir plus »
Problème P ≟ NP
Représentation visuelle des deux configurations possibles. Le problème est une conjecture en mathématiques, et plus précisément en informatique théorique, considérée par de nombreux chercheurs comme une des plus importantes conjectures du domaine, et même des mathématiques en général.
Nouveau!!: RP (complexité) et Problème P ≟ NP · Voir plus »
Test de primalité AKS
Le test de primalité AKS (aussi connu comme le test de primalité Agrawal-Kayal-Saxena et le test cyclotomique AKS) est un algorithme de preuve de primalité déterministe et généraliste (fonctionne pour tous les nombres) publié le par trois scientifiques indiens nommés Manindra Agrawal, Neeraj Kayal et Nitin Saxena (A.K.S).
Nouveau!!: RP (complexité) et Test de primalité AKS · Voir plus »
Test de primalité de Miller-Rabin
En mathématiques, le test de primalité de Miller-Rabin est un test de primalité probabiliste, de type Monte Carlo: étant donné un nombre entier, il donne une réponse oui/non pour conclure soit de façon certaine que celui-ci est composé, soit qu'il est probablement premier.
Nouveau!!: RP (complexité) et Test de primalité de Miller-Rabin · Voir plus »
Théorie de la complexité (informatique théorique)
P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée…) requis par un algorithme pour résoudre un problème algorithmique.
Nouveau!!: RP (complexité) et Théorie de la complexité (informatique théorique) · Voir plus »
ZPP (complexité)
ZPP et la relation avec d'autres classes de complexité probabilistes. La classe ZPP, est un objet de la théorie de la complexité, en informatique théorique.
Nouveau!!: RP (complexité) et ZPP (complexité) · Voir plus »
