Accès plus rapide que le navigateur!
42 relations: Algorithme de parcours en profondeur, BPP (complexité), BQP, Circuit booléen, Classe de complexité, Clause de Horn, Complet (complexité), Complexité en espace, EXPSPACE, EXPTIME, Grammaire non contextuelle, Hiérarchie polynomiale, Informatique théorique, Jin-Yi Cai, L (complexité), Langage creux, Logique modale, Logique temporelle, Machine de Turing, Mathématiques, Méthodes de points intérieurs, NC (complexité), NL (complexité), NP (complexité), Optimisation linéaire, P-complet, P/poly, Polynôme, Problème de décision, Problème de flot maximum, Problème de l'évaluation d'un circuit, Problème NP-complet, Problème P ≟ NP, Problème SAT, PSPACE, Richard E. Ladner, Test de primalité AKS, Thèse de Cobham, Théorème de hiérarchie en temps déterministe, Théorie de la complexité (informatique théorique), Vérification de modèles, ZPP (complexité).
Algorithme de parcours en profondeur
L'algorithme de parcours en profondeur (ou parcours en profondeur, ou DFS, pour) est un algorithme de parcours d'arbre, et plus généralement de parcours de graphe.
Nouveau!!: P (complexité) et Algorithme de parcours en profondeur · 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!!: P (complexité) et BPP (complexité) · Voir plus »
BQP
En théorie de la complexité des algorithmes BQP (bounded error quantum polynomial time) est la classe des problèmes de décision qui peuvent être résolus par un calculateur quantique en un temps polynomial, avec une probabilité d'erreur d'au plus 1/3 dans tous les cas.
Nouveau!!: P (complexité) et BQP · Voir plus »
Circuit booléen
Exemple circuit booléen à deux entrées et une sortie. Le circuit contient 3 portes logique. En théorie de la complexité, un circuit booléen est un modèle de calcul constitué de portes logiques (fonctions logiques) reliées entre elles.
Nouveau!!: P (complexité) et Circuit booléen · 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!!: P (complexité) et Classe de complexité · Voir plus »
Clause de Horn
En logique, en particulier en calcul propositionnel, une clause de Horn est une clause comportant au plus un ''littéral positif''.
Nouveau!!: P (complexité) et Clause de Horn · Voir plus »
Complet (complexité)
En informatique théorique, et notamment en théorie de la complexité, un problème complet pour une classe de complexité est un problème de décision qui fait partie des problèmes les plus difficiles à résoudre de cette classe.
Nouveau!!: P (complexité) et Complet (complexité) · Voir plus »
Complexité en espace
En algorithmique, la complexité en espace est une mesure de l'espace utilisé par un algorithme, en fonction de propriétés de ses entrées.
Nouveau!!: P (complexité) et Complexité en espace · Voir plus »
EXPSPACE
En théorie de la complexité, EXPSPACE est la classe des problèmes décidables en espace exponentiel par une machine de Turing déterministe.
Nouveau!!: P (complexité) et EXPSPACE · Voir plus »
EXPTIME
En théorie de la complexité, EXPTIME (ou EXP) est la classe de complexité qui est l'ensemble des problèmes de décision décidés par une machine de Turing déterministe en temps exponentiel.
Nouveau!!: P (complexité) et EXPTIME · Voir plus »
Grammaire non contextuelle
En linguistique et en informatique théorique, une grammaire algébrique, ou grammaire non contextuelle, aussi appelée grammaire hors-contexte ou grammaire « context-free » est une grammaire formelle dans laquelle chaque règle de production est de la forme où X est un symbole non terminal et \alpha est une chaîne composée de terminaux et/ou de non-terminaux.
Nouveau!!: P (complexité) et Grammaire non contextuelle · Voir plus »
Hiérarchie polynomiale
En théorie de la complexité, la hiérarchie polynomiale est une hiérarchie de classes de complexité qui étend la notion de classes P, NP, co-NP.
Nouveau!!: P (complexité) et Hiérarchie polynomiale · 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!!: P (complexité) et Informatique théorique · Voir plus »
Jin-Yi Cai
Jin-Yi Cai (en chinois: 蔡进), né le 23 janvier 1961 à Shanghai, est un mathématicien et informaticien sino-américain.
Nouveau!!: P (complexité) et Jin-Yi Cai · Voir plus »
L (complexité)
En informatique théorique, et notamment dans la théorie de la complexité, la classe L est la classe des problèmes de décision décidés par une machine de Turing déterministe qui utilise un espace de taille logarithmique en fonction de la taille de l'entrée,.
Nouveau!!: P (complexité) et L (complexité) · Voir plus »
Langage creux
En théorie de la complexité, un langage creux est un langage où le nombre de mots de longueur n est borné par un polynôme en n. Ils sont utiles dans l'étude de la classe NP.
Nouveau!!: P (complexité) et Langage creux · Voir plus »
Logique modale
En logique mathématique, une logique modale est un type de logique formelle qui étend la logique propositionnelle, la logique du premier ordre ou la logique d'ordre supérieur avec des modalités.
Nouveau!!: P (complexité) et Logique modale · Voir plus »
Logique temporelle
La logique temporelle est une branche de la logique mathématique et plus précisément de la logique modale, qui est formalisée de plusieurs manières.
Nouveau!!: P (complexité) et Logique temporelle · Voir plus »
Machine de Turing
En informatique théorique, une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur.
Nouveau!!: P (complexité) et Machine de Turing · Voir plus »
Mathématiques
Les mathématiques (ou la mathématique) sont un ensemble de connaissances abstraites résultant de raisonnements logiques appliqués à des objets divers tels que les ensembles mathématiques, les nombres, les formes, les structures, les transformations; ainsi qu'aux relations et opérations mathématiques qui existent entre ces objets.
Nouveau!!: P (complexité) et Mathématiques · Voir plus »
Méthodes de points intérieurs
Visualisation de la méthode des points intérieur : le chemin reste à l’intérieur du polyèdre. Visualisation de la méthode du simplexe : le chemin suit les arêtes du polyèdre Visualisation de la méthode par ellipsoïde : l’ellipse se rétrécit Les méthodes de points intérieurs forment une classe d’algorithmes qui permettent de résoudre des problèmes d’optimisation mathématique.
Nouveau!!: P (complexité) et Méthodes de points intérieurs · Voir plus »
NC (complexité)
En théorie de la complexité, un domaine de l'informatique théorique, NC (pour) est une classe de complexité faisant intervenir le parallélisme.
Nouveau!!: P (complexité) et NC (complexité) · Voir plus »
NL (complexité)
En informatique théorique, plus précisément en théorie de la complexité, NL est une classe de complexité.
Nouveau!!: P (complexité) et NL (complexité) · Voir plus »
NP (complexité)
La classe NP est une classe très importante de la théorie de la complexité.
Nouveau!!: P (complexité) et NP (complexité) · Voir plus »
Optimisation linéaire
Optimisation linéaire dans un espace à deux dimensions (''x''1, ''x''2). La fonction-coût ''f''c est représentée par les lignes de niveau bleues à gauche et par le plan bleu à droite. L'ensemble admissible E est le pentagone vert. En optimisation mathématique, un problème d'optimisation linéaire demande de minimiser une fonction linéaire sur un polyèdre convexe.
Nouveau!!: P (complexité) et Optimisation linéaire · Voir plus »
P-complet
En théorie de la complexité computationnelle, un problème de décision est P-complet (c.-à-d. complet pour la classe de complexité '''P''' des problèmes en temps polynomial) s'il est dans P et tout problème dans P peut y être réduit par une réduction en espace logarithmique (d'autres réductions sont aussi utilisées, comme NC).
Nouveau!!: P (complexité) et P-complet · Voir plus »
P/poly
En informatique théorique, plus précisément en théorie de la complexité, P/poly est la classe de problèmes de décision décidés par une famille de circuits booléens de tailles polynomiales.
Nouveau!!: P (complexité) et P/poly · 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!!: P (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!!: P (complexité) et Problème de décision · Voir plus »
Problème de flot maximum
Un exemple de graphe de flot avec un flot maximum. la source est s, et le puits t. Les nombres indiquent le flot et la capacité. Le problème de flot maximum consiste à trouver, dans un réseau de flot, un flot réalisable depuis une source unique et vers un puits unique qui soit maximum.
Nouveau!!: P (complexité) et Problème de flot maximum · Voir plus »
Problème de l'évaluation d'un circuit
Exemple d'un circuit avec deux entrées 1 et 0. La sortie vaut 1 (cliquer sur l'image pour voir l'animation qui calcule la sortie). En informatique théorique, plus précisément en théorie de la complexité, le problème de l'évaluation d'un circuit (appelé CIRCUIT VALUE PROBLEM, CVP, CIRCUIT EVALUATION PROBLEM ou CIRCUIT-EVAL en anglais) est le problème de décision qui consiste à calculer la sortie d'un circuit booléen sur des entrées données.
Nouveau!!: P (complexité) et Problème de l'évaluation d'un circuit · Voir plus »
Problème NP-complet
En théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes.
Nouveau!!: P (complexité) et Problème NP-complet · 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!!: P (complexité) et Problème P ≟ NP · Voir plus »
Problème SAT
consulté le.
Nouveau!!: P (complexité) et Problème SAT · Voir plus »
PSPACE
En informatique théorique, plus précisément en théorie de la complexité, PSPACE est la classe de complexité des problèmes de décision décidés par une machine de Turing déterministe avec un espace polynomial.
Nouveau!!: P (complexité) et PSPACE · Voir plus »
Richard E. Ladner
Richard Emil Ladner est un informaticien américain connu pour ses contributions à la fois à l'informatique théorique et aux.
Nouveau!!: P (complexité) et Richard E. Ladner · 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!!: P (complexité) et Test de primalité AKS · Voir plus »
Thèse de Cobham
Le graphique montre le temps en millisecondes pour résoudre des instances du problème du sac à dos en fonction de la taille d'entrée n. L'expérience a été réalisée sur un ordinateur Pentium III 933 MHz (les données proviennent d'une moyenne sur 100 instances à chaque foisD. Pisinger, 2003. "Where are the hard knapsack problems?" Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark, see http://www.diku.dk/forskning/Publikationer/tekniske_rapporter/2003/03-08.pdf, accessed 31 January 2015.). En informatique, la thèse de Cobham, aussi connue sous la thèse de Cobham–Edmonds (nommée d'après Alan Cobham et Jack Edmonds), postule que les problèmes calculables « facilement » sont les problèmes calculables en temps polynomial.
Nouveau!!: P (complexité) et Thèse de Cobham · Voir plus »
Théorème de hiérarchie en temps déterministe
Le théorème de hiérarchie en temps déterministe est un énoncé de la théorie de la complexité, un domaine de l'informatique théorique.
Nouveau!!: P (complexité) et Théorème de hiérarchie en temps déterministe · 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!!: P (complexité) et Théorie de la complexité (informatique théorique) · Voir plus »
Vérification de modèles
model checking''. En informatique, la vérification de modèles, ou en anglais, est le problème suivant: vérifier si le modèle d'un système (souvent informatique ou électronique) satisfait une propriété.
Nouveau!!: P (complexité) et Vérification de modèles · 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!!: P (complexité) et ZPP (complexité) · Voir plus »
