Accès plus rapide que le navigateur!
24 relations: AC (complexité), AC0, Fonction booléenne, Fonction ET, Fonction logique, Fonction NON, Fonction OU, Fonction parité, Génie informatique, Graphe orienté acyclique, Informatique théorique, Langage formel, Machine de Turing, NC (complexité), Notices of the American Mathematical Society, P/poly, Polylogarithmique, Preuve naturelle, Problème de l'évaluation d'un circuit, Problème P ≟ NP, TC (complexité), Théorie de la calculabilité, Théorie de la complexité (informatique théorique), Unité arithmétique et logique.
AC (complexité)
En théorie de la complexité, AC est la classe de complexité définie comme l'union des ACi, où ACi est la classe de complexité des problèmes décidés par des circuits booléens de profondeur O(\log^i n), de taille polynomiale, dont les portes sont des ET et des OU, de degrés entrants non bornés (en fait, d'autres portes peuvent être autorisés comme des portes "OU exclusif" ou NON car elles sont exprimables, sans changer la complexité, par des ET et des OU).
Nouveau!!: Circuit booléen et AC (complexité) · Voir plus »
AC0
Calculer le ième bit de la somme de deux nombres a et b est dans AC0. L'image montre un circuit de taille polynomiale en la taille de l'entrée, ie. 2n et de profondeur constante (ici de profondeur 5 pour tout n). En théorie de la complexité, AC0 est une classe de complexité définie par des circuits booléens de profondeur constante.
Nouveau!!: Circuit booléen et AC0 · Voir plus »
Fonction booléenne
Arbre de décision binaire Une fonction booléenne est une fonction prenant en entrée une liste de bits et donnant en sortie un unique bit.
Nouveau!!: Circuit booléen et Fonction booléenne · Voir plus »
Fonction ET
La fonction ET (AND en anglais) est un opérateur logique de l'algèbre de Boole.
Nouveau!!: Circuit booléen et Fonction ET · Voir plus »
Fonction logique
Il existe deux grands types de fonctions logiques.
Nouveau!!: Circuit booléen et Fonction logique · Voir plus »
Fonction NON
La fonction NON (NOT en anglais) est un opérateur logique de l'algèbre de Boole et exprime un « état » en fonction de conditions.
Nouveau!!: Circuit booléen et Fonction NON · Voir plus »
Fonction OU
La fonction OU ou OU inclusif (OR en anglais) est un opérateur logique de l'algèbre de Boole.
Nouveau!!: Circuit booléen et Fonction OU · Voir plus »
Fonction parité
La fonction parité est une fonction booléenne.
Nouveau!!: Circuit booléen et Fonction parité · Voir plus »
Génie informatique
Le génie informatique, ou l'ingénierie informatique, est une discipline qui traite de la conception, du développement et de la fabrication de systèmes informatiques, aussi bien d'un point de vue matériels que logiciels.
Nouveau!!: Circuit booléen et Génie informatique · Voir plus »
Graphe orienté acyclique
En théorie des graphes, un graphe orienté acyclique (en anglais directed acyclic graph ou DAG), est un graphe orienté qui ne possède pas de circuit.
Nouveau!!: Circuit booléen et Graphe orienté acyclique · 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!!: Circuit booléen 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!!: Circuit booléen et Langage formel · 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!!: Circuit booléen et Machine de Turing · 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!!: Circuit booléen et NC (complexité) · Voir plus »
Notices of the American Mathematical Society
Les Notices of the American Mathematical Society sont l'une des publications périodiques de lAmerican Mathematical Society (AMS).
Nouveau!!: Circuit booléen et Notices of the American Mathematical Society · 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!!: Circuit booléen et P/poly · Voir plus »
Polylogarithmique
Une fonction polylogarithmique de n est une fonction polynomiale en le logarithme de sa variable.
Nouveau!!: Circuit booléen et Polylogarithmique · Voir plus »
Preuve naturelle
En théorie de la complexité, une preuve naturelle est une démonstration de borne inférieure sur des circuits booléens qui satisfait certaines propriétés.
Nouveau!!: Circuit booléen et Preuve naturelle · 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!!: Circuit booléen et Problème de l'évaluation d'un circuit · 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!!: Circuit booléen et Problème P ≟ NP · Voir plus »
TC (complexité)
En informatique théorique, et plus précisément en théorie de la complexité, TC est la classe de complexité des problèmes de décision reconnus par des circuits avec seuil.
Nouveau!!: Circuit booléen et TC (complexité) · Voir plus »
Théorie de la calculabilité
La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est un domaine de la logique mathématique et de l'informatique théorique.
Nouveau!!: Circuit booléen et Théorie de la calculabilité · 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!!: Circuit booléen et Théorie de la complexité (informatique théorique) · Voir plus »
Unité arithmétique et logique
L'unité arithmétique et logique (UAL, en anglais arithmetic logic unit, ALU), est l'organe de l'ordinateur chargé d'effectuer les calculs.
Nouveau!!: Circuit booléen et Unité arithmétique et logique · Voir plus »
