Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Catégorie
Théorie de la complexité (informatique théorique)
Résumé
vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, 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. Il s'agit donc d'étudier la difficulté intrinsèque des problèmes, de les organiser par classes de complexité et d'étudier les relations entre les classes de complexité.
vignette|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).
Considérons l'exemple du problème du voyageur de commerce. La donnée du problème est un ensemble de villes et de distances séparant ces villes. L'objectif du problème est de trouver un plus court circuit qui passe une et une seule fois par toutes les villes. Il existe un problème de décision associé : étant donné un ensemble de villes, les distances entre villes et un entier k, déterminer s'il existe un circuit qui passe une et une seule fois par toutes les villes de longueur inférieure à k. Ainsi, on distingue deux types de problèmes.
Les problèmes de décision posent une question dont la réponse est oui ou non ; dans le cas du problème du voyageur de commerce : existe-il oui ou non un circuit de longueur inférieure à k ?
Les problèmes de recherche d'une solution comportent une question ou plutôt une injonction de la forme « renvoyer un élément tel que... » dont la réponse consiste à fournir un tel élément; dans le cas du problème du voyageur de commerce, exhiber un circuit de longueur minimale. Il s'agit donc d'un problème fonctionnel, et il sera donc catégorisé dans une classe fonctionnelle, par exemple FP si la solution est calculée en temps polynomial.
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.