Version imprimable
Salut à tous et à toutes( on ne sais jamais),
Est ce que quelqu'un pourrait l'histoire des complexités.
Comment savoir si on est n-p complet
D'apres le site:
http://wwwsi.supelec.fr/yb/projets/algogen/NP-Complet.htm
le problème du voyageur de commerce serait du type E car etant n! on est superieur à a^n. Pourtant on dit toujours que c'est une problème de type n-p.
comprend pas... :oops:
a+
Vic
On en a deja un peu parle dans un thread precedent de la complexite.
D'une maniere generale lorsqu'on calcule la complexite d'un probleme, c'est-a-dire qu'on regarde l7evolution de la difficulte en fonction de la taille des donneeds, on dit que le probleme est de complexite n^p si la difficulte est en O(n^p), ou n caracterise la taille des donnees. (pour la definition de O(n^p), cf le thread http://www.developpez.net/forums/viewtopic.php?t=27243)
C'est la premiere categorie
Ceux de classe E ont une complexite qui ne peut pas etre exprimee par un polynome.Citation:
Les problèmes de classe P sont des "bons problèmes" dans le sens où le calcul de leur solution est faisable dans un temps raisonnable. Ceux sont des problèmes dits polynomiaux.
Pour le voyageur de commerce, le probleme est effectivement NP, une machine non deterministe pourrait le resoudre en un temps polynomial (si je ne me trompe pas) car elle explorerait plusieurs possibilite en meme temps. (cf les machines de turing http://dept-info.labri.u-bordeaux.fr/HBib/MachTur.html).
Pour completer ce que j'ai ecrit :
http://dept-info.labri.u-bordeaux.fr/HBib/Complex.html
Ah oui j'allais oublie
Voila j'espere t'avoir aide...Citation:
n! croit plus vite que k^n des que n est grand devant k donc le probleme du voyageur de commerce n'est pas de type E.
desolé d'avoir poster une question deja evoqué.
Mais je n'ai pas encore compris la difference entre un problème NP et un problème E...
PS merci pour les site
Bon j'essaie d'etre plus clair.
Le probleme E croit en k^n, alors que le probleme np serait de complexite polynomial pour une machine de turing non deterministe ce qui fait une une complexite encore plus grande pour une machine deterministe.
NB : on n'a pas de machines non deterministe sous la main a ma connaissance.
Je crois pas qu'il y ait plus a comprendre pour la base du principe
OK, quand ce n'est pas polynomiale pour la machine de turin non deterministe, alors on est en E
Non ! E est de complexite plus simple que les problemes polynomiaux pour la machine de Turing non deterministe. Il suffit de regarder le probleme du voyageur du commerce qui evolue en n!. Il peut tres bien y avoir des problemes encore plus complexes non polynomiaux pour une machine non deterministe. Les problemes de la categorie E sont tels qu'ils sont definis dans l'article.
je pensais que les E etait plus complexe que les NP
non lim en infini de n!/k^n=+infini
ouai je sais mais dans
http://wwwsi.supelec.fr/yb/projets/algogen/NP-Complet.htm
Maintenant je ne sais pas ce que vaut ce site.Citation:
Les problèmes de la classe E sont des problèmes dits exponentiels par nature. Ceux sont les problèmes dont la complexité est intrinsèquement en au moins k^n, où k est une constante et n la taille des données.
Supelec est une ecole correcte mais je n'avais jamais entendu parle de cette classe E seulement des problemes polynomiaux et np.
http://www.myoo.fr.st/algo/complexite.php
Une page que j'ai faite sur le sujet...
Merci d'apporter un avis critique.
c'est cool ce que tu as ecrit, les info sur ce sujet ne sont pas tres courantes sur l'internet...
par contre ce serait super si tu developpais un peu plus les exemples
et l'histoire du type decisionnel et del'optimisation
a++
Ben disons que je ai fait ca rapidement donc j'espere avoir du temps pour developper le sujet. Les sources sont des sites en anglais car je ne connais pas de site en francais qui fait ca. Probleme je en suis pas en vacance mais plongeur donc je n'ai pas enormement de temps.
Je crois que la classe E évoquée ci-dessous correspond aux problèmes de type EXPSPACE ou EXPTIME
On a PSpace c Expspace car Expspace = U(k) Space((2^n)^k)
C'est pas facile d'écrire des formules en mode texte ;-)
merci pour ce detail je vais regarder ca.
Ce document est assez bien fait :
www.ens-lyon.fr/~ebeffara/work/modeles.ps.gz
Tu n'as pas une version sous un autre format genre pdf parce que la je travaille pas sur ma machine donc je ne peux pas lire les ps.
J'ai trouvé un site sympa :
Télécharge le ps.gz et décompresse le dans un coin.
Ensuite, à l'adresse suivante, tu sélectionnes ton fichier et tu cliques sur convert
http://www.ps2pdf.com/convert/convert.htm
Enfin, tu télecharges le résultat
merci. :ccool:
il y a autre document qui est bien :
http://<br /> http://www.lix.polyte.../poly.ps<br />
il y a la demo que le problème du voyageur de commerce est np-complet.
lol, enfin je me comprends...
est ce que les ordinateurs quantiques (s'il existait) fonctionneraient comme des machines de turing non deterministes?
Je te conseille vivement de lire cet article si tu veux la reponse a ta question.
http://www.cagou.com/informatique/quantas.htm
:P
Citation:
Quantum computers can, in theory, make computations which are impossible to do exactly with classical computers or achieve exponential speedup. Since nobody has yet (as of November 2001) implemented more than a few bit operations, problems such as decoherence and measurement error may limit quantum computation to a few specialized roles.
ben c'est cool tout ça, il y aura du boulot en algorithmique qui ils arriveront... :yaisse1: :yaisse3: :yaisse2: :yaisse:
Ca sera moins cool quand on aura cassé l'algorithme clé publique-clé privée...
Ca va être un beau bazard ce jour là...
ça doit quand meme etre possible de trouver des algo de cryptage donc le decryptage soit exponencielle pour une machine de Turing non deterministe...
Evidemment, aucune raison que ca n'existe pas. D'ailleurs il y a des problemes plus difficiles que les problemes np-complet.
http://www.myoo.fr.st/algo/complexite.php
il ne marche plus ton site.
J'ai un probleme avec la base de donnee mysql dur free, je vais essayer de resoudre ca.
C'est repare, le lien fonctionne maintenant.