Complexités

**victorracine** · 26/08/2002, 15h09

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

a+
Vic

**mio** · 26/08/2002, 16h46

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

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.

Ceux de classe E ont une complexite qui ne peut pas etre exprimee par un polynome.
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

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.

Voila j'espere t'avoir aide...

**victorracine** · 26/08/2002, 17h07

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

**mio** · 26/08/2002, 17h13

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

**victorracine** · 26/08/2002, 17h21

OK, quand ce n'est pas polynomiale pour la machine de turin non deterministe, alors on est en E

**mio** · 26/08/2002, 17h30

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.

**victorracine** · 26/08/2002, 17h51

je pensais que les E etait plus complexe que les NP

**mio** · 26/08/2002, 17h56

non lim en infini de n!/k^n=+infini

**victorracine** · 26/08/2002, 18h11

ouai je sais mais dans
http://wwwsi.supelec.fr/yb/projets/algogen/NP-Complet.htm

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.

Maintenant je ne sais pas ce que vaut ce site.

**mio** · 26/08/2002, 18h47

Supelec est une ecole correcte mais je n'avais jamais entendu parle de cette classe E seulement des problemes polynomiaux et np.

**mio** · 30/08/2002, 14h37

http://www.myoo.fr.st/algo/complexite.php
Une page que j'ai faite sur le sujet...
Merci d'apporter un avis critique.

**victorracine** · 30/08/2002, 16h59

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

**mio** · 31/08/2002, 15h34

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.

**btavernier** · 03/09/2002, 14h13

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 ;-)

**mio** · 03/09/2002, 15h25

merci pour ce detail je vais regarder ca.

**btavernier** · 03/09/2002, 15h27

Ce document est assez bien fait :

www.ens-lyon.fr/~ebeffara/work/modeles.ps.gz

**mio** · 03/09/2002, 15h29

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.

**btavernier** · 03/09/2002, 15h36

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

**mio** · 03/09/2002, 15h39

merci.

**victorracine** · 05/09/2002, 16h51

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.

Complexités

Algorithmes et structures de données

Discussions similaires

Partager

Partager