Accès plus rapide que le navigateur!
20 relations: Christos Papadimitriou, Classe de complexité, Complexité en espace, Graphe non orienté, Graphe orienté, Informatique théorique, Journal of the ACM, Machine de Turing, Machine de Turing symétrique, NC (complexité), NL (complexité), NP (complexité), Omer Reingold, P (complexité), Prix Gödel, Problème de décision, PSPACE, Réduction en espace logarithmique, Taux d'expansion (théorie des graphes), Théorie de la complexité (informatique théorique).
Christos Papadimitriou
Christos Harilaos Papadimitriou (en Χρήστος Χαρίλαος Παπαδημητρίου), né le à Athènes, est un professeur et chercheur en informatique grec.
Nouveau!!: L (complexité) et Christos Papadimitriou · 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!!: L (complexité) et Classe de 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!!: L (complexité) et Complexité en espace · Voir plus »
Graphe non orienté
Exemple de graphe non orienté à 5 sommets. En théorie des graphes, un graphe non orienté G.
Nouveau!!: L (complexité) et Graphe non orienté · Voir plus »
Graphe orienté
Un graphe orienté G.
Nouveau!!: L (complexité) et Graphe orienté · 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!!: L (complexité) et Informatique théorique · 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!!: L (complexité) et Journal of the ACM · 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!!: L (complexité) et Machine de Turing · Voir plus »
Machine de Turing symétrique
En informatique théorique, une machine de Turing symétrique est une machine de Turing dont le graphe des configurations est non-orienté, c'est-à-dire qu'il est possible de passer d'une configuration A à une configuration B, si et seulement si l'opération inverse est possible.
Nouveau!!: L (complexité) et Machine de Turing symétrique · 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!!: L (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!!: L (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!!: L (complexité) et NP (complexité) · Voir plus »
Omer Reingold
Omer Reingold (עומר ריינגולד), spécialiste en théorie de la complexité des algorithmes, est chercheur principal (Principal Researcher Engineer) au Samsung Research America depuis février 2015, après avoir été chercheur principal (Principal Researcher) au centre de recherche Microsoft à Silicon Valley.
Nouveau!!: L (complexité) et Omer Reingold · 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!!: L (complexité) et P (complexité) · Voir plus »
Prix Gödel
Le prix Gödel est une distinction créée en 1992 par l'European Association for Theoretical Computer Science (EATCS) et le Special Interest Group on Algorithms and Computation Theory (SIGACT) de l'Association for Computing Machinery (ACM) pour honorer des travaux remarquables d'informatique théorique.
Nouveau!!: L (complexité) et Prix Gödel · 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!!: L (complexité) et Problème de décision · 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!!: L (complexité) et PSPACE · Voir plus »
Réduction en espace logarithmique
En théorie de la complexité, une réduction en espace logarithmique est une réduction calculable par une machine de Turing disposant d'un espace de travail logarithmique.
Nouveau!!: L (complexité) et Réduction en espace logarithmique · Voir plus »
Taux d'expansion (théorie des graphes)
En mathématiques, et plus particulièrement en théorie des graphes, le taux d'expansion d'un graphe est une mesure de connectivité de ce graphe Shlomo Hoory, Nathan Linial et Avi Widgerson.
Nouveau!!: L (complexité) et Taux d'expansion (théorie des graphes) · 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!!: L (complexité) et Théorie de la complexité (informatique théorique) · Voir plus »
