Théorie de la complexité (informatique théorique)vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, 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.
Computational complexityIn computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.
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. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.
Loi uniforme continueEn théorie des probabilités et en statistiques, les lois uniformes continues forment une famille de lois de probabilité à densité. Une telle loi est caractérisée par la propriété suivante : tous les intervalles de même longueur inclus dans le support de la loi ont la même probabilité. Cela se traduit par le fait que la densité de probabilité d'une loi uniforme continue est constante sur son support. Elles constituent donc une généralisation de la notion d'équiprobabilité dans le cas continu pour des variables aléatoires à densité ; le cas discret étant couvert par les lois uniformes discrètes.
Quantum complexity theoryQuantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical (i.e., non-quantum) complexity classes. Two important quantum complexity classes are BQP and QMA.
Hasardvignette|Les jeux de dés sont des symboles du hasard (jeux de hasard). vignette|Tyché ou Fortuna et sa corne d'abondance (fortune, hasard, en grec ancien, sort en latin) déesse allégorique gréco-romaine de la chance, des coïncidences, de la fortune, de la prospérité, de la destinée...|alt= Le hasard est le principe déclencheur d'événements non liés à une cause connue. Il peut être synonyme de l'« imprévisibilité », de l'« imprédictibilité », de fortune ou de destin.
Complexité paramétréeEn algorithmique, la complexité paramétrée (ou complexité paramétrique) est une branche de la théorie de la complexité qui classifie les problèmes algorithmiques selon leur difficulté intrinsèque en fonction de plusieurs paramètres sur les données en entrée ou sur la sortie. Ce domaine est étudié depuis les années 90 comme approche pour la résolution exacte de problèmes NP-complets. Cette approche est utilisée en optimisation combinatoire, notamment en algorithmique des graphes, en intelligence artificielle, en théorie des bases de données et en bio-informatique.
NP-difficilevignette|300px|Mise en évidence d'un problème NP-difficile si Problème P ≟ NP. Un problème NP-difficile est, en théorie de la complexité, un problème appartenant à la classe NP-difficile, ce qui revient à dire qu'il est au moins aussi difficile que les problèmes les plus difficiles de la classe NP. Ainsi, un problème H est NP-difficile, si tout problème L de la classe NP peut être réduit en temps polynomial à H. Si un problème NP-difficile est dans NP, alors c'est un problème NP-complet.
Conseil (informatique théorique)En théorie de la complexité, un conseil est une entrée supplémentaire passée à une machine de Turing qui dépend de la taille de l'entrée, afin d'aider la machine à reconnaître un langage. Cette notion est introduite par Richard Karp et Richard J. Lipton en 1982. Étant donnés une fonction et une classe de complexité , la classe est l'ensemble des langages tels qu'il existe un langage et une suite de conseils de taille tels que pour toute entrée de taille , si et seulement si .
Relationships among probability distributionsIn probability theory and statistics, there are several relationships among probability distributions. These relations can be categorized in the following groups: One distribution is a special case of another with a broader parameter space Transforms (function of a random variable); Combinations (function of several variables); Approximation (limit) relationships; Compound relationships (useful for Bayesian inference); Duality; Conjugate priors. A binomial distribution with parameters n = 1 and p is a Bernoulli distribution with parameter p.
