Accès plus rapide que le navigateur!
32 relations: Ashok K. Chandra, Aviezri Fraenkel, California Institute of Technology, Classe de complexité, Complet (complexité), Complexité descriptive, Complexité en espace, Croissance exponentielle, Dames, Décidabilité, Dexter Kozen, E (complexité), EXPSPACE, Forme normale disjonctive, Go (jeu), Journal of the ACM, Larry J. Stockmeyer, Logique contrainte, Logique d'ordre supérieur, Machine de Turing, Machine de Turing alternante, Machine de Turing non déterministe, NEXPTIME, NP (complexité), P (complexité), Planification (intelligence artificielle), Problème de décision, Problème de l'arrêt, Problème P ≟ NP, PSPACE, Théorème de hiérarchie en temps déterministe, Théorie de la complexité (informatique théorique).
Ashok K. Chandra
Ashok Kumar Chandra (né le en Inde, et mort le en Californie) est un informaticien qui a travaillé notamment chez Microsoft Research à Mountain View, en Californie, où il était directeur général du Internet Services Research Center.
Nouveau!!: EXPTIME et Ashok K. Chandra · Voir plus »
Aviezri Fraenkel
Aviezri Siegmund Fraenkel (en אביעזרי פרנקל), né le à Munich, en Allemagne, est un mathématicien et informaticien théoricien israélien qui travaille notamment en théorie des jeux combinatoires.
Nouveau!!: EXPTIME et Aviezri Fraenkel · Voir plus »
California Institute of Technology
Le (« Institut de technologie de Californie »), en abrégé Caltech ou plus rarement CIT, est une université privée américaine créée en 1891.
Nouveau!!: EXPTIME et California Institute of Technology · 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!!: EXPTIME et Classe de complexité · 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!!: EXPTIME et Complet (complexité) · Voir plus »
Complexité descriptive
En informatique théorique, la complexité descriptive est une branche de la théorie de la complexité et de la théorie des modèles, qui caractérise les classes de complexité en termes de logique qui permet de décrire les problèmes.
Nouveau!!: EXPTIME et Complexité descriptive · 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!!: EXPTIME et Complexité en espace · Voir plus »
Croissance exponentielle
300x300px La croissance exponentielle d'une quantité est son augmentation au fil du temps selon une loi exponentielle.
Nouveau!!: EXPTIME et Croissance exponentielle · Voir plus »
Dames
Les dames ou le jeu de dames est un jeu de société combinatoire abstrait pour deux joueurs.
Nouveau!!: EXPTIME et Dames · Voir plus »
Décidabilité
En logique mathématique, le terme décidabilité recouvre deux concepts liés: la décidabilité logique et la décidabilité ''algorithmique''.
Nouveau!!: EXPTIME et Décidabilité · Voir plus »
Dexter Kozen
Dexter Campbell Kozen (né le) est un informaticien théoricien américain.
Nouveau!!: EXPTIME et Dexter Kozen · Voir plus »
E (complexité)
En informatique théorique et notamment en théorie de la complexité, la classe E est une classe de complexité; c'est l'ensemble des problèmes de décision qui peuvent être décidés par une machine de Turing déterministe en temps exponentiel avec un exposant linéaire.
Nouveau!!: EXPTIME et E (complexité) · 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!!: EXPTIME et EXPSPACE · Voir plus »
Forme normale disjonctive
En logique booléenne ou en calcul des propositions, une forme normale disjonctive ou FND (en anglais, disjunctive normal form ou DNF) est une normalisation d'une expression logique qui est une disjonction de clauses conjonctives.
Nouveau!!: EXPTIME et Forme normale disjonctive · Voir plus »
Go (jeu)
Le go, également appelé jeu de go, appelé en japonais, ou dans certaines expressions, en chinois, en hanyu pinyin wéiqí(prononciation shanghaïenne wedji) et en coréen baduk (바둑), est un jeu de société originaire de Chine.
Nouveau!!: EXPTIME et Go (jeu) · Voir plus »
Journal of the ACM
Journal of the ACM (Journal de l'ACM) est la revue scientifique majeure de l'Association for Computing Machinery (ACM).
Nouveau!!: EXPTIME et Journal of the ACM · Voir plus »
Larry J. Stockmeyer
Larry Joseph Stockmeyer (né en 1948 à Evansville, en Indiana, et mort le) est un informaticien théoricien américain.
Nouveau!!: EXPTIME et Larry J. Stockmeyer · Voir plus »
Logique contrainte
En informatique théorique et en théorie des jeux, la logique contrainte (nom original en anglais: constraint logic) est un formalisme proposé par Robert A. Hearn et Erik D. Demaine.
Nouveau!!: EXPTIME et Logique contrainte · Voir plus »
Logique d'ordre supérieur
Les logiques d'ordre supérieur (en anglais, higher-order logic ou HOL) sont des logiques formelles permettant d'utiliser des variables qui réfèrent à des fonctions ou à des prédicats.
Nouveau!!: EXPTIME et Logique d'ordre supérieur · 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!!: EXPTIME et Machine de Turing · Voir plus »
Machine de Turing alternante
En informatique théorique, et notamment en théorie de la complexité, les machines de Turing alternantes sont une généralisation des machines de Turing non déterministes.
Nouveau!!: EXPTIME et Machine de Turing alternante · Voir plus »
Machine de Turing non déterministe
Une machine de Turing non déterministe est similaire à une machine de Turing habituelle, qui, elle, est déterministe, mais s'en différencie dans le fait qu'étant non déterministe elle peut avoir plusieurs transitions activables, pour un état donné.
Nouveau!!: EXPTIME et Machine de Turing non déterministe · Voir plus »
NEXPTIME
En théorie de la complexité, NEXPTIME, ou NEXP, est une classe de complexité, c'est-à-dire un ensemble de problèmes de décision.
Nouveau!!: EXPTIME et NEXPTIME · Voir plus »
NP (complexité)
La classe NP est une classe très importante de la théorie de la complexité.
Nouveau!!: EXPTIME et NP (complexité) · 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!!: EXPTIME et P (complexité) · Voir plus »
Planification (intelligence artificielle)
257x257px En intelligence artificielle, la planification automatique (automated planning en anglais) ou plus simplement planification, vise à développer des algorithmes pour produire des plans typiquement pour l'exécution par un robot ou tout autre agent.
Nouveau!!: EXPTIME et Planification (intelligence artificielle) · 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!!: EXPTIME et Problème de décision · Voir plus »
Problème de l'arrêt
L'animation illustre une machine impossible: il n'y a pas de machine qui lit n'importe quel code source d'un programme et dit si son exécution termine ou non. En théorie de la calculabilité, le problème de l'arrêt est le problème de décision qui détermine, à partir d'une description d'un programme informatique, et d'une entrée, si le programme s'arrête avec cette entrée ou non.
Nouveau!!: EXPTIME et Problème de l'arrêt · 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!!: EXPTIME et Problème P ≟ NP · 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!!: EXPTIME et PSPACE · 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!!: EXPTIME 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!!: EXPTIME et Théorie de la complexité (informatique théorique) · Voir plus »
