Accès plus rapide que le navigateur!
15 relations: Antécédent (mathématiques), Classe de complexité, Codage de l'information, Compilateur, Informatique théorique, Injection (mathématiques), Interprète (informatique), Langage formel, NP-difficile, Problème de décision, Problème de la clique, Problème NP-complet, Problème P ≟ NP, Réduction (complexité), Théorie de la complexité (informatique théorique).
Antécédent (mathématiques)
application, 1 et 4 sont des antécédents de b. En mathématiques, étant donné deux ensembles, et une application f:E\to F, on appelle antécédent (par) d'un élément de tout élément dont l'image par est, c'est-à-dire tout élément de tel que.
Nouveau!!: Réduction polynomiale et Antécédent (mathématiques) · 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!!: Réduction polynomiale et Classe de complexité · Voir plus »
Codage de l'information
Le codage de l’information concerne les moyens de formaliser l'information afin de pouvoir la manipuler, la stocker ou la transmettre.
Nouveau!!: Réduction polynomiale et Codage de l'information · Voir plus »
Compilateur
En informatique, un compilateur est un programme qui transforme un code source en un code objet.
Nouveau!!: Réduction polynomiale et Compilateur · 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!!: Réduction polynomiale et Informatique théorique · Voir plus »
Injection (mathématiques)
Une application f est dite injective ou est une injection si tout élément de son ensemble d'arrivée a au plus un antécédent par f, ce qui revient à dire que deux éléments distincts de son ensemble de départ ne peuvent pas avoir la même image par f. Lorsque les ensembles de départ et d'arrivée de f sont tous les deux égaux à la droite réelle ℝ, f est injective si et seulement si son graphe intersecte toute droite horizontale en au plus un point.
Nouveau!!: Réduction polynomiale et Injection (mathématiques) · Voir plus »
Interprète (informatique)
En informatique, un interprète, ou interpréteur, est un outil dont la tâche est d'analyser, de traduire et d'exécuter les programmes écrits dans un langage informatique.
Nouveau!!: Réduction polynomiale et Interprète (informatique) · Voir plus »
Langage formel
Un langage formel, en mathématiques, en informatique et en linguistique, est un ensemble de mots.
Nouveau!!: Réduction polynomiale et Langage formel · Voir plus »
NP-difficile
Mise en évidence d'un problème NP-difficile si Problème P ≟ NP. Un problème NP-difficile est, en théorie de la complexité, un problème appartenant à la classe NP-difficile, ce qui revient à dire qu'il est au moins aussi difficile que les problèmes les plus difficiles de la classe NP.
Nouveau!!: Réduction polynomiale et NP-difficile · 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!!: Réduction polynomiale et Problème de décision · Voir plus »
Problème de la clique
C(7,4).
Nouveau!!: Réduction polynomiale et Problème de la clique · Voir plus »
Problème NP-complet
En théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes.
Nouveau!!: Réduction polynomiale et Problème NP-complet · 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!!: Réduction polynomiale et Problème P ≟ NP · Voir plus »
Réduction (complexité)
En calculabilité et en théorie de la complexité, une réduction est un algorithme transformant une instance d'un problème algorithmique en une ou plusieurs instances d'un autre problème.
Nouveau!!: Réduction polynomiale et Réduction (complexité) · 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!!: Réduction polynomiale et Théorie de la complexité (informatique théorique) · Voir plus »
