17 relations: Algorithme, Décidabilité, Dernier théorème de Fermat, Ensemble récursif, Entier naturel, Informatique théorique, Mathématiques, Nombre premier, NP (complexité), Problème algorithmique, Problème de correspondance de Post, Problème de l'arrêt, Problème de la décision, Récursivement énumérable, Test de primalité, Théorie de la calculabilité, Théorie de la complexité (informatique théorique).
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!!: Problème de décision et Algorithme · 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!!: Problème de décision et Décidabilité · Voir plus »
Dernier théorème de Fermat
En mathématiques, et plus précisément en théorie des nombres, le dernier théorème de Fermat, ou grand théorème de Fermat, ou depuis sa démonstration théorème de Fermat-Wiles, s'énonce comme suit: Énoncé par Pierre de Fermat d'une manière similaire dans une note marginale de son exemplaire d'un livre de Diophante, il a cependant attendu plus de trois siècles une preuve publiée et validée, établie par le mathématicien britannique Andrew Wiles en 1994.
Nouveau!!: Problème de décision et Dernier théorème de Fermat · Voir plus »
Ensemble récursif
En théorie de la calculabilité, un ensemble récursif ou ensemble décidable est un ensemble d'entiers (ou d'éléments facilement codables dans les entiers) dont la fonction caractéristique est une fonction récursive au sens de la logique mathématique.
Nouveau!!: Problème de décision et Ensemble récursif · 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!!: Problème de décision et Entier naturel · 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!!: Problème de décision et Informatique théorique · 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!!: Problème de décision et Mathématiques · 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!!: Problème de décision et Nombre premier · Voir plus »
NP (complexité)
La classe NP est une classe très importante de la théorie de la complexité.
Nouveau!!: Problème de décision et NP (complexité) · 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!!: Problème de décision et Problème algorithmique · Voir plus »
Problème de correspondance de Post
En mathématiques et en informatique théorique, et plus précisément en théorie de la calculabilité, le problème de correspondance de Post (PCP) est un problème de décision indécidable qui fut introduit par Emil Post en 1946.
Nouveau!!: Problème de décision et Problème de correspondance de Post · 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!!: Problème de décision et Problème de l'arrêt · Voir plus »
Problème de la décision
En logique mathématique, on appelle problème de la décision ou, sous son nom d'origine en allemand, Entscheidungsproblem, le fait de déterminer de façon mécanique (par un algorithme) si un énoncé est un théorème de la logique égalitaire du premier ordre, c’est-à-dire s'il se dérive dans un système de déduction sans autres axiomes que ceux de l'égalité (exemples: système à la Hilbert, calcul des séquents, déduction naturelle).
Nouveau!!: Problème de décision et Problème de la décision · Voir plus »
Récursivement énumérable
En théorie de la calculabilité, un ensemble d'entiers naturels est récursivement énumérable ou semi-décidable si.
Nouveau!!: Problème de décision et Récursivement énumérable · Voir plus »
Test de primalité
date.
Nouveau!!: Problème de décision et Test de primalité · 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!!: Problème de décision et Théorie de la calculabilité · 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!!: Problème de décision et Théorie de la complexité (informatique théorique) · Voir plus »