Problème du voyageur de commerce et Théorie de la complexité (informatique théorique)

Raccourcis: Différences, Similitudes, Jaccard similarité Coefficient, Références.

Différence entre Problème du voyageur de commerce et Théorie de la complexité (informatique théorique)

Problème du voyageur de commerce vs. Théorie de la complexité (informatique théorique)

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

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.

Complexité en temps et Problème du voyageur de commerce · Complexité en temps et Théorie de la complexité (informatique théorique) · 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.

Explosion combinatoire et Problème du voyageur de commerce · Explosion combinatoire et Théorie de la complexité (informatique théorique) · 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.

Informatique et Problème du voyageur de commerce · Informatique et Théorie de la complexité (informatique théorique) · 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.

P (complexité) et Problème du voyageur de commerce · P (complexité) et Théorie de la complexité (informatique théorique) · 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.

Problème algorithmique et Problème du voyageur de commerce · Problème algorithmique et Théorie de la complexité (informatique théorique) · 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 ».

Problème de décision et Problème du voyageur de commerce · Problème de décision et Théorie de la complexité (informatique théorique) · 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.

Problème du voyageur de commerce et Timothy Gowers · Théorie de la complexité (informatique théorique) et Timothy Gowers · 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.

21 problèmes NP-complets de Karp et Problème du voyageur de commerce · 21 problèmes NP-complets de Karp et Théorie de la complexité (informatique théorique) · Voir plus »