Logo
Unionpédia
Communication
Disponible sur Google Play
Nouveau! Téléchargez Unionpédia sur votre appareil Android™!
Installer
Accès plus rapide que le navigateur!
Et sans publicité!

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 un domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement la quantité de ressources (temps et/ou espace mémoire) nécessaire pour résoudre un problème algorithmique au moyen de l'exécution d'un algorithme.

49 relations: Alan Turing, Algorithme, Automate cellulaire, Calculabilité, Circuit booléen, Classe de complexité, Comparaison asymptotique, Complexité, Complexité de Kolmogorov, Complexité de la communication, Complexité descriptive, Complexité en temps, Constructivisme (mathématiques), Décidabilité, Explosion combinatoire, Fonction récursive, Informatique, Informatique théorique, International Business Machines, Lambda-calcul, Langage formel, Leonid Levin, Logique linéaire, Machine de Turing, Machine de Turing non déterministe, Mathématiques, Médaille Fields, Mémoire (informatique), Nombre premier, P (complexité), 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, Réduction polynomiale, Rolf Landauer, Scott Aaronson, Stephen Cole Kleene, Stephen Cook, Terence Tao, Théorème d'accélération linéaire, The New York Times, Timothy Gowers, Université technique d'Eindhoven, Wiki.

Alan Turing

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

Un algorithme est une suite finie et non ambiguë d’opérations ou d'instructions permettant de résoudre un problème ou d'obtenir un résultat.

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 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 »

Calculabilité

La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est une branche de la logique mathématique et de l'informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Calculabilité · Voir plus »

Circuit booléen

En théorie de la complexité, un circuit booléen est un modèle de calcul constitué de portes (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

En mathématiques, plus précisément en analyse, la comparaison asymptotique est une méthode consistant à étudier le comportement d'une fonction au voisinage d'un point (ou en l'infini), en regard du comportement d'une autre fonction réputée « simple » et « connue », souvent choisie sur une échelle de référence.

Nouveau!!: Théorie de la complexité (informatique théorique) et Comparaison asymptotique · Voir plus »

Complexité

La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri Atlan), en écologie, en sociologie, en ingénierie, en informatique ou en sciences de l’information.

Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité · Voir plus »

Complexité de Kolmogorov

La complexité de Kolmogorov (nommée d'après le mathématicien Andreï Kolmogorov), nommée aussi complexité aléatoire, ou complexité algorithmique, est une fonction permettant de quantifier la taille du plus petit algorithmeOu taille du plus petit programme mettant en œuvre cet algorithme dans un certain système formel ou langage de programmation.

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é 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 consiste à caractériser des classes de complexité par le type de logique dans laquelle les problèmes peuvent être décrits.

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 »

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 »

Fonction récursive

En informatique et en mathématiques, le terme fonction récursive désigne une classe de fonctions calculables, autrement dit de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Fonction récursive · Voir plus »

Informatique

L'informatique est un domaine d'activité scientifique, technique et industriel concernant le traitement automatique de l'information par l'exécution de programmes informatiques par des machines: des systèmes embarqués, des ordinateurs, des robots, des automates Ces champs d'application peuvent être séparés en deux branches, l'une, de nature théorique, qui concerne la définition de concepts et modèles, et l'autre, de nature pratique, qui s'intéresse aux techniques concrètes de mise en œuvre.

Nouveau!!: Théorie de la complexité (informatique théorique) et Informatique · Voir plus »

Informatique théorique

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 »

International Business Machines

International Business Machines Corporation, connue sous l’abréviation IBM, est une société 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 International Business Machines · 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

En mathématiques, en informatique et en linguistique, la théorie des langages a pour objectif de décrire les langages formels.

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 russo-ukraino-américain.

Nouveau!!: Théorie de la complexité (informatique théorique) et Leonid Levin · Voir plus »

Logique linéaire

En logique mathématique et plus précisément en théorie de la démonstration, la logique linéaire, inventée par le logicien Jean-Yves Girard en 1986, est un système formel qui, du point de vue logique, décompose et analyse les logiques classique et intuitionniste et, du point de vue calculatoire, est un système de type pour le lambda-calcul permettant de spécifier certains usages des ressources.

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 et sa mémoire.

Nouveau!!: Théorie de la complexité (informatique théorique) et Machine de Turing · 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 »

Mathématiques

Raisonnement mathématique sur un tableau. La mathématique ou les mathématiques sont un ensemble de connaissances abstraites résultant de raisonnements logiques appliqués à des objets divers tels que les nombres, les figures, les structures et les transformations.

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 pour la reconnaissance de travaux en mathématiques, souvent considérée comme un équivalent du prix Nobel car il n'en existe pas pour cette discipline.

Nouveau!!: Théorie de la complexité (informatique théorique) et Médaille Fields · Voir plus »

Mémoire (informatique)

Mémoire vive pour ordinateur VAX 8600 (1986). En informatique, la mémoire est un dispositif électronique qui sert à stocker des informations.

Nouveau!!: Théorie de la complexité (informatique théorique) et Mémoire (informatique) · Voir plus »

Nombre premier

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 (qui sont alors 1 et lui-même).

Nouveau!!: Théorie de la complexité (informatique théorique) et Nombre premier · Voir plus »

P (complexité)

La classe P 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 »

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

En informatique théorique, un problème est 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 ». Les logiciens s'y sont intéressés à cause de l'existence ou de la non-existence d'un algorithme répondant à la question posée.

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, étant donné une liste de villes, et des distances entre toutes les paires de villes, détermine un plus court chemin qui visite chaque ville une et une seule fois et qui termine dans la ville de départ.

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 2000.

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 collaboration pour résoudre des problèmes mathématiques.

Nouveau!!: Théorie de la complexité (informatique théorique) et Projet Polymath · 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 Chi-Shen Tao (sinogrammes traditionnels: 陶哲軒, sinogrammes simplifiés: 陶哲轩), né le à Adélaide en Australie, est un mathématicien médaillé Fields qui travaille principalement dans les domaines de l'analyse harmonique, des équations aux dérivées partielles, de la combinatoire, de la théorie analytique des nombres et de la théorie des représentations.

Nouveau!!: Théorie de la complexité (informatique théorique) et Terence Tao · 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 »

The New York Times

, abrégé en, NYT ou, est un quotidien new-yorkais distribué internationalement et l'un des plus prestigieux journaux américains.

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é technique d'Eindhoven

L’Université technique d'Eindhoven (en néerlandais: Technische Universiteit Eindhoven) est une école polytechnique fondée en 1956 et située à Eindhoven, aux Pays-Bas.

Nouveau!!: Théorie de la complexité (informatique théorique) et Université technique d'Eindhoven · Voir plus »

Wiki

Exemple de lien pour modifier la page d'un wiki, ici un article de 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 »

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.

SortantEntrants
Hey! Nous sommes sur Facebook maintenant! »