Accès plus rapide que le navigateur!
72 relations: Alan Turing, Algorithme, Automate cellulaire, Circuit booléen, Classe de complexité, Comparaison asymptotique, Complexité, Complexité de Kolmogorov, Complexité de la communication, Complexité des preuves, Complexité descriptive, Complexité en temps, Constructivisme (mathématiques), Décidabilité, Entier naturel, Explosion combinatoire, EXPSPACE, EXPTIME, Factorisation, Fonction récursive, Gerhard Woeginger, Hiérarchie arithmétique, Hiérarchie de Grzegorczyk, IBM, Informatique, Informatique théorique, L (complexité), Lambda-calcul, Langage formel, Leonid Levin, Logique linéaire, Machine de Turing, Machine de Turing alternante, Machine de Turing non déterministe, Machine de Turing probabiliste, Mathématiques, Médaille Fields, Mémoire (informatique), NEXPTIME, NL (complexité), Nombre premier, NP (complexité), P (complexité), Précondition, Principe de Landauer, Problème algorithmique, Problème de décision, Problème du voyageur de commerce, Problème ouvert, Problèmes de Smale, ..., Problèmes du prix du millénaire, Projet Polymath, PSPACE, Réduction polynomiale, Rolf Landauer, Scott Aaronson, Stephen Cole Kleene, Stephen Cook, Terence Tao, Test de primalité AKS, Théorème d'accélération linéaire, Théorème d'Immerman-Szelepcsényi, Théorème de Cook, Théorème de Savitch, Théorème de Toda, Théorie de l'information, Théorie de la calculabilité, The New York Times, Timothy Gowers, Université de technologie d'Eindhoven, Wiki, 21 problèmes NP-complets de Karp. Développer l'indice (22 plus) »
Alan Turing
Alan Turing vers 1938. Alan Mathison Turing, né le à Londres et mort le à Wilmslow, est un mathématicien et cryptologue britannique, auteur de travaux qui fondent scientifiquement l'informatique.
Nouveau!!: Théorie de la complexité (informatique théorique) et Alan Turing · Voir plus »
Algorithme
triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes.
Nouveau!!: Théorie de la complexité (informatique théorique) et Algorithme · Voir plus »
Automate cellulaire
À gauche, une règle locale simple: une cellule passe d'un état (i) au suivant (i+1) dans le cycle d'états dès que i+1 est présent dans au moins 3 des 8 cellules voisines. À droite, le résultat (complexe) de l'application répétée de cette règle sur une grille de cellules. Ce type d'automates cellulaires a été découvert par D. Griffeath. Un automate cellulaire consiste en une grille régulière de « cellules » contenant chacune un « état » choisi parmi un ensemble fini et qui peut évoluer au cours du temps.
Nouveau!!: Théorie de la complexité (informatique théorique) et Automate cellulaire · 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!!: Théorie de la complexité (informatique théorique) 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!!: Théorie de la complexité (informatique théorique) et Classe de complexité · Voir plus »
Comparaison asymptotique
Comparaison asymptotique des fonctions utilisées en informatique plus précisément en algorithme. On voit par exemple que la fonction exponentielle (2^n) croit plus vite que la fonction linéaire (n). En mathématiques, plus précisément en analyse, la comparaison asymptotique est une méthode consistant à étudier la vitesse de croissance d'une fonction.
Nouveau!!: Théorie de la complexité (informatique théorique) et Comparaison asymptotique · Voir plus »
Complexité
La complexité caractérise le comportement d'un système dont les composants interagissent localement et de façon non linéaire, ce qui se traduit par un comportement difficilement prédictible.
Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité · Voir plus »
Complexité de Kolmogorov
En informatique théorique et en mathématiques, plus précisément en théorie de l'information, la complexité de Kolmogorov, ou complexité aléatoire, ou complexité algorithmique d'un objet — nombre, image numérique, chaîne de caractères — est la taille du plus petit algorithme (dans un certain langage de programmation fixé) qui engendre cet objet.
Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité de Kolmogorov · Voir plus »
Complexité de la communication
La complexité de la communication ou complexité de communication est une notion étudiée en informatique théorique.
Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité de la communication · Voir plus »
Complexité des preuves
En informatique théorique, la complexité des preuves ou complexité des démonstrations est le domaine qui étudie les ressources nécessaires pour prouver ou réfuter un énoncé mathématique.
Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité des preuves · 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!!: Théorie de la complexité (informatique théorique) et Complexité descriptive · Voir plus »
Complexité en temps
En algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée.
Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité en temps · Voir plus »
Constructivisme (mathématiques)
En philosophie des mathématiques, le constructivisme est une position vis-à-vis des mathématiques qui considère que l'on ne peut effectivement démontrer l'existence d'objets mathématiques qu'en donnant une construction de ceux-ci, une suite d'opérations mentales qui conduit à l'évidence de l'existence de ces objets.
Nouveau!!: Théorie de la complexité (informatique théorique) et Constructivisme (mathématiques) · 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!!: Théorie de la complexité (informatique théorique) et Décidabilité · Voir plus »
Entier naturel
En mathématiques, un entier naturel est un nombre permettant fondamentalement de compter des objets considérés comme des unités équivalentes: un jeton, deux jetons… une carte, deux cartes, trois cartes… Un tel nombre entier peut s'écrire avec une suite finie de chiffres en notation décimale positionnelle (sans signe et sans virgule).
Nouveau!!: Théorie de la complexité (informatique théorique) et Entier naturel · Voir plus »
Explosion combinatoire
L'explosion combinatoire en recherche opérationnelle, et en particulier dans le domaine de la programmation dynamique, est le fait qu'un petit changement du nombre de données à considérer dans un problème par ailleurs trivial peut suffire à rendre sa solution très difficile, voire impossible dans certains cas avec les ordinateurs actuels.
Nouveau!!: Théorie de la complexité (informatique théorique) et Explosion combinatoire · 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!!: Théorie de la complexité (informatique théorique) 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!!: Théorie de la complexité (informatique théorique) et EXPTIME · Voir plus »
Factorisation
En mathématiques, la factorisation consiste à écrire une expression algébrique (notamment une somme), un nombre, une matrice sous la forme d'un produit.
Nouveau!!: Théorie de la complexité (informatique théorique) et Factorisation · Voir plus »
Fonction récursive
En informatique et en mathématiques, le terme fonction récursive ou fonction calculable désigne la classe de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique fini.
Nouveau!!: Théorie de la complexité (informatique théorique) et Fonction récursive · Voir plus »
Gerhard Woeginger
Gerhard J. Woeginger, né le à Graz, en Autriche et mort le, est un mathématicien et informaticien autrichien.
Nouveau!!: Théorie de la complexité (informatique théorique) et Gerhard Woeginger · Voir plus »
Hiérarchie arithmétique
Theory of Computation'', Springer 2006.. En logique mathématique, plus particulièrement en théorie de la calculabilité, la hiérarchie arithmétique, définie par Stephen Cole Kleene, est une hiérarchie des sous-ensembles de l'ensemble N des entiers naturels définissables dans le langage du premier ordre de l'arithmétique de Peano.
Nouveau!!: Théorie de la complexité (informatique théorique) et Hiérarchie arithmétique · Voir plus »
Hiérarchie de Grzegorczyk
La hiérarchie de Grzegorczyk – du nom du logicien polonais Andrzej Grzegorczyk – est une hiérarchie de fonctions utilisée en théorie de la calculabilité.
Nouveau!!: Théorie de la complexité (informatique théorique) et Hiérarchie de Grzegorczyk · Voir plus »
IBM
International Business Machines Corporation, connue sous le sigle IBM, est une entreprise multinationale américaine présente dans les domaines du matériel informatique, du logiciel et des services informatiques.
Nouveau!!: Théorie de la complexité (informatique théorique) et IBM · Voir plus »
Informatique
bibliothèque d'Art et d'Archéologie de Genève (2017). L'informatique est un domaine d'activité scientifique, technique, et industriel concernant le traitement automatique de l'information numérique par l'exécution de programmes informatiques hébergés par des dispositifs électriques-électroniques: des systèmes embarqués, des ordinateurs, des robots, des automates Ces champs d'application peuvent être séparés en deux branches.
Nouveau!!: Théorie de la complexité (informatique théorique) et Informatique · 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!!: Théorie de la complexité (informatique théorique) et Informatique théorique · 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!!: Théorie de la complexité (informatique théorique) et L (complexité) · Voir plus »
Lambda-calcul
Le lambda-calcul (ou λ-calcul) est un système formel inventé par Alonzo Church dans les années 1930, qui fonde les concepts de fonction et d'application.
Nouveau!!: Théorie de la complexité (informatique théorique) et Lambda-calcul · Voir plus »
Langage formel
Un langage formel, en mathématiques, en informatique et en linguistique, est un ensemble de mots.
Nouveau!!: Théorie de la complexité (informatique théorique) et Langage formel · Voir plus »
Leonid Levin
Leonid Anatolievich Levin (Леонид Анатольевич Левин, né le à Dnipropetrovsk, RSS d'Ukraine) est un informaticien et logicien russo-ukraino-américain.
Nouveau!!: Théorie de la complexité (informatique théorique) et Leonid Levin · Voir plus »
Logique linéaire
date.
Nouveau!!: Théorie de la complexité (informatique théorique) et Logique linéaire · 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!!: Théorie de la complexité (informatique théorique) 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!!: Théorie de la complexité (informatique théorique) 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!!: Théorie de la complexité (informatique théorique) et Machine de Turing non déterministe · Voir plus »
Machine de Turing probabiliste
En théorie de la complexité, une machine de Turing probabiliste (ou randomisée) est une machine de Turing qui peut utiliser du hasard.
Nouveau!!: Théorie de la complexité (informatique théorique) et Machine de Turing probabiliste · 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!!: Théorie de la complexité (informatique théorique) et Mathématiques · Voir plus »
Médaille Fields
La médaille Fields est la plus prestigieuse récompense en mathématiques avec le prix Abel.
Nouveau!!: Théorie de la complexité (informatique théorique) et Médaille Fields · Voir plus »
Mémoire (informatique)
En informatique, la mémoire est un dispositif électronique numérique qui sert à stocker des données.
Nouveau!!: Théorie de la complexité (informatique théorique) et Mémoire (informatique) · 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!!: Théorie de la complexité (informatique théorique) et NEXPTIME · 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!!: Théorie de la complexité (informatique théorique) et NL (complexité) · Voir plus »
Nombre premier
Entiers naturels de zéro à cent. Les nombres premiers sont marqués en rouge. 7 est premier car il admet exactement deux diviseurs positifs distincts. Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs.
Nouveau!!: Théorie de la complexité (informatique théorique) et Nombre premier · Voir plus »
NP (complexité)
La classe NP est une classe très importante de la théorie de la complexité.
Nouveau!!: Théorie de la complexité (informatique théorique) 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!!: Théorie de la complexité (informatique théorique) et P (complexité) · Voir plus »
Précondition
Une précondition est une condition appliquée au début d'un calcul ou d'une fonction informatique, et permettant d'en valider le résultat.
Nouveau!!: Théorie de la complexité (informatique théorique) et Précondition · Voir plus »
Principe de Landauer
Le principe de Landauer, formulé pour la première fois en 1961 par Rolf Landauer d'IBM, est un principe physique relatif à la limite théorique basse de consommation d'énergie d'un système physique de calcul.
Nouveau!!: Théorie de la complexité (informatique théorique) et Principe de Landauer · Voir plus »
Problème algorithmique
Un problème algorithmique est, en informatique théorique, un objet mathématique qui représente une question ou un ensemble de questions auxquelles un ordinateur devrait être en mesure de répondre.
Nouveau!!: Théorie de la complexité (informatique théorique) et Problème algorithmique · 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!!: Théorie de la complexité (informatique théorique) et Problème de décision · Voir plus »
Problème du voyageur de commerce
Le problème de voyageur de commerce: calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes). En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui consiste à déterminer, étant donné un ensemble de villes, le plus court circuit passant par chaque ville une seule fois.
Nouveau!!: Théorie de la complexité (informatique théorique) et Problème du voyageur de commerce · Voir plus »
Problème ouvert
En mathématiques, un problème ouvert est une question qui n'a pas été résolue ou une conjecture qui n'a pas été prouvée.
Nouveau!!: Théorie de la complexité (informatique théorique) et Problème ouvert · Voir plus »
Problèmes de Smale
En mathématiques, les problèmes de Smale forment une liste de 18 problèmes non résolus en mathématiques, proposée par Steve Smale en 2000.
Nouveau!!: Théorie de la complexité (informatique théorique) et Problèmes de Smale · Voir plus »
Problèmes du prix du millénaire
Les problèmes du prix du millénaire sont un ensemble de sept défis mathématiques réputés insurmontables, posés par l'Institut de mathématiques Clay en.
Nouveau!!: Théorie de la complexité (informatique théorique) et Problèmes du prix du millénaire · Voir plus »
Projet Polymath
Le projet Polymath (Polymath project) est un projet de résolution collective de problèmes mathématiques.
Nouveau!!: Théorie de la complexité (informatique théorique) et Projet Polymath · 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!!: Théorie de la complexité (informatique théorique) et PSPACE · Voir plus »
Réduction polynomiale
Une réduction polynomiale est un outil d'informatique théorique, plus particulièrement de théorie de la complexité.
Nouveau!!: Théorie de la complexité (informatique théorique) et Réduction polynomiale · Voir plus »
Rolf Landauer
Rolf Landauer (1927 – 1999) était un physicien qui a travaillé pour IBM.
Nouveau!!: Théorie de la complexité (informatique théorique) et Rolf Landauer · Voir plus »
Scott Aaronson
Scott Joel Aaronson, est un chercheur, professeur et vulgarisateur en informatique théorique, notamment en informatique quantique.
Nouveau!!: Théorie de la complexité (informatique théorique) et Scott Aaronson · Voir plus »
Stephen Cole Kleene
Stephen Cole Kleene, né le à Hartford (Connecticut) et mort le à Madison (Wisconsin), est un mathématicien et logicien américain.
Nouveau!!: Théorie de la complexité (informatique théorique) et Stephen Cole Kleene · Voir plus »
Stephen Cook
Stephen Arthur Cook (né en 1939 à Buffalo dans l'État de New York) est un informaticien et mathématicien américano-canadien, qui a apporté plusieurs contributions majeures à la théorie de la complexité.
Nouveau!!: Théorie de la complexité (informatique théorique) et Stephen Cook · Voir plus »
Terence Tao
Terence Tao (sinogrammes traditionnels: 陶哲軒, sinogrammes simplifiés: 陶哲轩), né le à Adélaïde (Australie), est un mathématicien australien.
Nouveau!!: Théorie de la complexité (informatique théorique) et Terence Tao · 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!!: Théorie de la complexité (informatique théorique) et Test de primalité AKS · Voir plus »
Théorème d'accélération linéaire
Le théorème d'accélération linéaire ou de speedup linéaire est un théorème de théorie de la complexité, un domaine de l'informatique théorique.
Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème d'accélération linéaire · Voir plus »
Théorème d'Immerman-Szelepcsényi
Le théorème d'Immerman-Szelepcsényi est un théorème d'informatique théorique, et notamment de la théorie de la complexité, démontré en 1987 indépendamment par Neil Immerman et Róbert Szelepcsényi, et qui leur a valu d'obtenir conjointement le prix Gödel en 1995.
Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème d'Immerman-Szelepcsényi · Voir plus »
Théorème de Cook
En informatique théorique, plus précisément en théorie de la complexité, le théorème de Cook aussi appelé théorème de Cook-Levin est le théorème qui affirme que le problème SAT, c'est-à-dire le problème de satisfaisabilité d'une formule de la logique propositionnelle, est NP-complet.
Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème de Cook · Voir plus »
Théorème de Savitch
Le théorème de Savitch est un théorème de théorie de la complexité, un domaine de l'informatique théorique.
Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème de Savitch · Voir plus »
Théorème de Toda
Le théorème de Toda est un résultat en théorie de la complexité, démontré en 1991 par Seinosuke Toda dans son article PP is as Hard as the Polynomial-Time Hierarchy, et qui a valu à son auteur le prix Gödel en 1998.
Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème de Toda · Voir plus »
Théorie de l'information
La théorie de l'information, sans précision, est le nom usuel désignant la théorie de l'information de Shannon, qui est une théorie utilisant les probabilités pour quantifier le contenu moyen en information d'un ensemble de messages, dont le codage informatique satisfait une distribution statistique que l'on pense connaître.
Nouveau!!: Théorie de la complexité (informatique théorique) et Théorie de l'information · 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!!: Théorie de la complexité (informatique théorique) et Théorie de la calculabilité · Voir plus »
The New York Times
(prononcé en anglais), abrégé NYT, est un quotidien new-yorkais fondé en 1851, publié en anglais, espagnol, et chinois.
Nouveau!!: Théorie de la complexité (informatique théorique) et The New York Times · Voir plus »
Timothy Gowers
Sir William Timothy Gowers (ou plus simplement Tim Gowers), né le dans le Wiltshire en Angleterre, est un mathématicien anglais.
Nouveau!!: Théorie de la complexité (informatique théorique) et Timothy Gowers · Voir plus »
Université de technologie d'Eindhoven
L'université de technologie d'Eindhoven (Technische Universiteit Eindhoven, en néerlandais, souvent abrégé en TU Eindhoven ou TU/e), est un institut de technologie fondé en 1956 et situé à Eindhoven, aux Pays-Bas.
Nouveau!!: Théorie de la complexité (informatique théorique) et Université de technologie d'Eindhoven · Voir plus »
Wiki
Exemple de lien pour modifier la page d'un wiki, ici la page « Wikipédia » sur Wikipédia en français. Un wiki est une application web qui permet la création, la modification et l'illustration collaboratives de pages à l'intérieur d'un site web.
Nouveau!!: Théorie de la complexité (informatique théorique) et Wiki · Voir plus »
21 problèmes NP-complets de Karp
Les 21 problèmes NP-complets de Karp ont marqué une étape importante de l'histoire de la théorie de la complexité des algorithmes.
Nouveau!!: Théorie de la complexité (informatique théorique) et 21 problèmes NP-complets de Karp · Voir plus »
Redirections ici:
Classes de complexité P et NP, Complexité des classes P et NP, Complexité informatique, Optimisation difficile, Problème ouvert P = NP, Théorie de la complexité des algorithmes.
