Et ben

Par - Altair - le 25/10/2002 à 13:12:49 (#2404065)

on avait meme pas 10 ans et on "resolvait" deja des problemes NP complets :)
comme quoi on est des betes ;)

http://www.arxiv.org/abs/cs.CC/0210020

Par Pilou le 25/10/2002 à 13:15:13 (#2404088)

D'ou l'interet d'installer Tetris sur sa calculette ..... j'aurai enfin une escuse valable !
Merci pour ce lien :mdr:

Par Kelem Khâl La'Ri le 25/10/2002 à 13:42:21 (#2404368)

Les fourmis aussi resolvent très bien certains problèmes NP-complet (TSP entre autres).

Par Missmite le 25/10/2002 à 13:48:12 (#2404430)

faux, lorsque tu joues a tetris tu ne "resoud" pas le probleme NP complet, tu trouves une heuristique, autrement dit une methode d'appoximation qui essaie de s'approcher au mieux de la solution optimale :) en fait exactement comme ferait tout informatitien confronté a un probleme NP complet. Tu sais que tu ne peux pas trouver la solution dans un temps raisonable par nature meme du probleme, donc tu cherches une solution qui soit assez proche de la meilleure mais que tu sais calculer vite :)

Par - Altair - le 25/10/2002 à 14:21:43 (#2404726)

oui, c'est pour ca que resoudre était entre guillement :)

Par Screien le 25/10/2002 à 14:25:02 (#2404761)

c koi NP ?

Par Lisa Newark le 25/10/2002 à 14:29:51 (#2404799)

Provient du message de Screien
c koi NP ?

sais po. ca doit être un truc de matheux, et comme ils veulent pas qu'on comprenne ils font exprès d'utiliser des acronymes connus d'eux seuls. :D

viens, on va boire un pot au bar! *sort sans faire de bruit*

Par - Altair - le 25/10/2002 à 14:52:45 (#2404982)

Voici une définition :

On peut voir de façon intuitive les problèmes NP-Complets comme des problèmes pour lesquels la recherche d'une solution consiste à parcourir un arbre. Cet arbre "de recherche" contient l'ensemble des solutions possibles, une branche de cet arbre représente une éventuelle solution. La hauteur d'un tel arbre est polynomiale par contre son nombre de branches est exponentiel; Chaque noeud de l'arbre correspondant à un point de choix pour une variable.

source
En gros ce sont des problèmes très difficille à résoudre.

Par Lisa Newark le 25/10/2002 à 15:02:49 (#2405085)

Provient du message de - Altair -
Voici une définition :
source
En gros ce sont des problèmes très difficille à résoudre.

et donc les lettres N et P elles veulent rien dire de spécial? :doute:

Par Missmite le 25/10/2002 à 15:11:13 (#2405161)

ensemble des problemes non polynomiaux. Des problemes pour lesquels il n'existe pas d'algorithme permettant de trouver (ou calculer) la solution dans un temps qui soit une fonction polynomiale de la taille des données, mais ou l'on peut verifier qu'une solution est correcte en temps polynomial.

J'entend par temps polynomial une fonction du genre "le temps mis pour trouver un truc particulier parmis N trucs est N² x le temps de chaque opération elementaires". Ca c'est un probleme polynomial, un probleme NP complet est un probleme ou le meilleur algorithme prend un temps de la forme "K puissance N pour des données de taille N" (K est une constante dependante du probleme).

typiquement le probleme du voyageur de commerce est un probleme NP complet, il s'agit de trouver un chemin le plus court possible ne passant pas deux fois par une meme ville. Ce probleme est NP complet et on ne peut donc pas le resoudre dans un temps raisonable. Par contre, si on me fourni un parcours des villes, je peux facilement verifier qu'il est conforme et qu'il est de poids minimal tout en ne passant pas plusieurs fois par les villes, suffit de regarder.

Par Emvé Anovel le 25/10/2002 à 20:11:57 (#2407987)

Donner un moyen efficace de résoudre un problème NP serait une très grande avancée pour les sciences

d'ailleurs, une récompense de 1 Millions de dollars est offert pour résoudre chacun des grands problèmes mathématiques qui feraient avancer les sciences ( je crois qu'il y en a 12 je suis pas sûr - note j'entends récompensé par le même organisme hein ! )

( je sais plus quel organisme fait cette "généreuse" offre qui rapportera bien plus au monde en terme de billets verts...:rolleyes: ).

Moi je trouve ça passionant, mais dès que l'on dit ça, on passe pour un extraterrestre à poils piano.

Par Marnot Mensha le 25/10/2002 à 20:16:22 (#2408034)

tu peux donne un exemple de ces 12 problemes ?

Par Emvé Anovel le 25/10/2002 à 20:26:24 (#2408126)

La fondation "The Clay Mathematics Institute of Cambridge" a proposé en l'an 2000 une liste de 7 problèmes fondamentaux en mathématiques. La résolution de chacun de ces problèmes permettrait une avancée considérable dans le secteur de recherche auquels ils appartiennent respectivement. 7 millions de dollars accompagnent par ailleurs ce prix, soit un million par problème...Nous vous proposons une vulgarisation de la liste des problèmes.

je me suis trompé c'est 7 :

http://www.les-mathematiques.net/p/p/a/

qui peuvent s'appliquer forcément en science :

Les NP problèmes

L'hypothèse de Riemann ( prouver que l'approximation qu'on a fait du nombre de nombres premiers est vrai - > cryptographie )

Les équations de Navier-Stroke (y aurait une analogie avec le comportement de solide dans les fluides...

La théorie de Yang Mills ( concerne la physique quantique)

Les autres problèmes, le site n' est pas très clair sur leurs applications et moi-même, je ne les vois pas immédiatement :hardos: ( d'ailleurs le site s'en tient à une avancée considérable dans leurs secteurs de recherche, c'est à dire, toujours des mathématiques :monstre: )

Ce sont des maths très très très très ... très costauds que je ne peux pas du tout comprendre
:maboule:

Par - Altair - le 25/10/2002 à 20:26:43 (#2408131)

Au fait si je me rapelle bien de la théorie, si on trouve un moyen de résoudre un problème NP- dificille en un temps polynomial, alors on peut résoudre tous les problèmes problèmes NP en un temps polynomial.

Enormement de problèmes sont NP, par exemple les problèmes d'optimisation. Le jour ou on aura trouve un programme qui résout ce type de problème en un temps polynomial, ce sera une véritable révolution ! :)

Par Panzerjo le 25/10/2002 à 20:26:45 (#2408133)

Cet offre a dailleur attire les foudres de mathematiciens qui etaient honteux de voir des gens lancer une carrote pour trouver des solutions a des problemes Mathematiques.

Par Missmite le 25/10/2002 à 20:33:50 (#2408218)

exact Altair, si on en resoud un on les resoud tous et donc on est contents :) enfin meme si on n'a pas reussi a demontrer que P != NP, l'hypothese la plus probable reste que cela soit le cas. Si je devais chercher un truc sur le sujet j'essaierais de montrer que P != NP plutot que d'essayer de trouver un cas montrant que P = NP. Pour les problemes d'optimisation des heuristiques donnent de tres bon resultats, sans ces heristiques mathematiques les telecoms modernes n'existeraient pas ;) (pas un hasard si 200 ou 300 des machines du top 500 appartiennent a des operateurs telecoms, ils font tourner des heuristiques d'optimisation combinatoire sans arret pour savoir ou placer les fibres optiques ou les antenes GSM)

Par Screien le 25/10/2002 à 20:55:58 (#2408363)

Ca devient tres technique mas réelement interessant ... J'aime pas les maths mais sans rire je trouve ca génial ..

Enfin je me pose une question a quoi corresponde c'est valeur, je veux dire en chose réel et peut etre que ces arbres ( c'est ca non ) ne peuvent etre résolu !!!


Moi ca me dépasse la science !

Par Missmite le 25/10/2002 à 21:07:22 (#2408433)

bah imagines un probleme qui a une solution polynomiale. Tu as par exemple un ensemble de 1millier de données. ton probleme polynomial va prendre 1000 ^ k (ou k est une constante independante de la taille des données, disons dans notre exemple 2).

maitenant tu as un probleme non polynomial sur un jeu de 1 millier de données, ca va prendre k ^ 1000 unités de temps pour trouver la solution du probleme (meme chose pour ce k ici, constante independante de la taille des données).

bon bah 1000 ^ 2 unités de temps c'est tout a fait raisonable et un ordinateur standard te fais ca en quelques microsecondes. 2 ^ 1000 est un nombre gigantesque, ca depasse largement le nombre de mollecules dans l'univers, et evidement, meme avec une machine d'une puissance incroyable, tu n'arriveras jamais a faire assez d'operations pour terminer le calcul avant la fin des temps :)

et tu vois que deja pour 1000 données la difference est enorme, alors imagines pour des problemes reels qui travaillent sur des millions de données... NP complet est sinonyme d'impossible a resoudre en informatique (pas en mathematique puisque les mathematiques s'interessent a la preuve et a l'existence des choses, tandis que l'informatique se pose la question de savoir si c'est calculable, et si ca l'est en combien de temps)

Par Screien le 26/10/2002 à 0:17:08 (#2409672)

Mais alors si c impossible a quoi ca sert les NP ?

Par jio le 26/10/2002 à 3:37:19 (#2410399)

les Np ne servent pas a quelques chose, ils existent. Ce sont des problemes "impossibles" à resoudre de facon automatique.

voici un probleme resolvable par une machine rapidement :

500, 100, 38, 894. Quelle est la plus grande valeur ?
un ordinateur va regarder chacune des valeur, la comparer aux autres et garder la plus grande en mémoire pour donner le bon résultat à la fin. Cette méthode est infaillible. Quelque soit le nombre de valeurs a comparer, l'ordinateur le fera plus rapidement que n'importe quel cerveau humain.

voici un probleme NON polynomial complet :

Il s'agit de colorier les différentes régions d'une carte de sorte que si deux régions sont voisines alors elles sont de couleurs différentes. On peut montrer que 4 couleurs suffiront dans n'importe quel cas (faites l'essai), on essaye quelques cas différents et notre cerveau nous permet de comprendre que 4 couleurs suffiront.

Mais un ordinateur ne peut pas résoudre ce probleme, car le temps qu'il lui faudrait pour tester chaque cas de figure est "infini" (l'ordinateur n'interprete pas, il n'essaye pas de "deviner" le resultat).

Par Emvé Anovel le 26/10/2002 à 9:37:38 (#2410881)

Il s'agit de colorier les différentes régions d'une carte de sorte que si deux régions sont voisines alors elles sont de couleurs différentes. On peut montrer que 4 couleurs suffiront dans n'importe quel cas (faites l'essai), on essaye quelques cas différents et notre cerveau nous permet de comprendre que 4 couleurs suffiront.

Mais un ordinateur ne peut pas résoudre ce probleme, car le temps qu'il lui faudrait pour tester chaque cas de figure est "infini" (l'ordinateur n'interprete pas, il n'essaye pas de "deviner" le resultat).

pourtant d'après ce que je crois savoir, ce problème des 4 couleurs fut résolu à l'aide d'ordinateurs...

Par Le Playboy le 26/10/2002 à 10:18:16 (#2410972)

Provient du message de Missmite
faux, lorsque tu joues a tetris tu ne "resoud" pas le probleme NP complet, tu trouves une heuristique, autrement dit une methode d'appoximation qui essaie de s'approcher au mieux de la solution optimale :) en fait exactement comme ferait tout informatitien confronté a un probleme NP complet. Tu sais que tu ne peux pas trouver la solution dans un temps raisonable par nature meme du probleme, donc tu cherches une solution qui soit assez proche de la meilleure mais que tu sais calculer vite :)

ca s'appelle un balayage ou une dichotomie, de rien pour le renseignement. ;) :D

Par Screien le 26/10/2002 à 12:11:00 (#2411392)

Ouaa on en apprends tout les jours mais alors si il existent et qu'on peut pas les résoudre enfin deviner par ordinateur ! Pourquoi on cherche les solutions ?

Par jio le 26/10/2002 à 12:47:07 (#2411566)

bha avant on pensait que c'etait que c'etait impossible de faire passer des images et du son dans des fils. mais des keums ont cherché et on trouvé. merci les gars ;)

Par Kelem Khâl La'Ri le 26/10/2002 à 13:11:57 (#2411686)

Après un reparcours rapide du thread, j'ajoute un commentaire supplementaire qui n'a pas été donné concernant la complétude pour differencier un probleme NP d'un NP-complet : le dernier est une sous-classe du premier, et un probleme est NP-complet quand l'ensemble des problèmes NP lui sont reductibles en temps polynomial, c'est a dire que la résolution polynomiale d'un NP-complet permet en théorie la résolution automatique de tous les problemes de classe NP, l'inverse n'est bien sur pas exact.

Quant à dire que l'existence de ces problemes suffit a leur donner de l'interet n'est pas tout a fait juste. Il existe moult problemes NP-complets qui trouvent des applications tres concretes :
- TSP, le probleme du voyageur de commerce decrit par Missmite.
- Les problemes de satisfiabilité de contraintes en logique des propositions (a OU b ET c etc etc...).
- Les problèmes d'ordonnancement de taches, d'emploi du temps.
etc etc...

Ensuite, à nouveau comme le precisait la Mite, le parcours de l'arbre des solutions peut s'effectuer à l'aide d'heuristiques plus ou moins efficaces, l'interet est donc de decouvrir ces heuristiques et de les confronter les unes avec les autres. Le jour ou quelqu'un decouvrira une theorie pour resoudre de maniere polynomiale les problemes NP alors la, nous n'aurons plus besoin de nous casser la tete a trouver de "bonnes" heuristiques :p.

Quant à la dichotomie, ca n'a pas grand chose a voir avec le shmilblick :p.

Par LeProctophantasmiste le 26/10/2002 à 17:55:42 (#2413044)

Ce n'est pas vraiment mon domaine, moi je fais plutôt partie de cette classe là:

pas en mathématique puisque les mathématiques s'intéressent à la preuve et a l'existence des choses

(ce n'est pas tout à fait vrai Missmite:) , toute une partie des mathématiques traite de cela, de fait, ce problème, s'il était interne à l'informatique tel que nous la connaissons ne pourrait même pas être posé )
Et surtout je suis loin d'être arrivé au bout, mais:
NP ne veut pas dire non polynomial (la classe E est celle des problèmes exponentiels, et on a P inter E vide, par définition), mais polynomial non déterministe, c'est à dire des problèmes qu'une machine de Turing non déterministe peut résoudre en temps polynomial, mais pour lesquels il n'existe pas de solution polynomiale déterministe (connue c'est bien le problème je crois :)). L'important, et là ou la remarque de Missmite à un sens précis, c'est qu'une machine non déterministe ne peut pas résoudre plus de problème qu'une machine déterministe, la question est de savoir si elle peut les résoudre plus vite. Cela prend une importance cruciale dans l'informatique, puisque nos machines sont déterministes (à noter que les travaux sur l'informatique quantique, c'est sérieux, visent à changer cet état de fait), d'où l'importance aussi des problèmes NP-complet, pour lesquels je n'ai rien de plus à dire que ce qui a déjà été dit :).

"Machine non déterministe", est une expression qui peut paraître contradictoire, disons plutôt que si les étapes de l'algo ne sont pas singulièrement déterminées, bon c'est nul aussi, elles ne sont pas pour autant indéterminées, l'algo explore plusieurs voies à la fois.

Par Missmite le 28/10/2002 à 11:57:50 (#2423027)

Tient je ne connaissais pas cette definition parlant de machines nons deterministes :) Quelle difference y a t il d'un point de vu theorique entre utiliser une machine intrinsequement non deterministe et utiliser un algorithme non deterministe (comme la plupart des heuristiques qui sont probabilistes) ? Tu voudrais dire qu'une machine intrinsequement non deterministe serait capable de calculer une solution exacte d'un probleme NP complet ? Si on sait trouver une solution d'un probleme NP complet, vu qu'on sait verifier dans un temps polynomial qu'une solution est juste ou non, on sait resoudre le probleme. En gros si tu me trouves un las vegas (ou monte carlo, me souviens plus lequel est justifié ici, enfin celui qui donne toujours une solution, mais pas toujours vrai), tu as trouvé une facon de resoudre NP :eek: Interessante idée :)

Par LeProctophantasmiste le 30/10/2002 à 23:49:18 (#2445068)

Tient je ne connaissais pas cette definition parlant de machines nons deterministes Quelle difference y a t il d'un point de vu theorique entre utiliser une machine intrinsequement non deterministe et utiliser un algorithme non deterministe (comme la plupart des heuristiques qui sont probabilistes) ?

Je te sens septique donc voilà un lien pour te montrer que je ne dis pas n'importe quoi:).


Il est effectivement plus fréquent de dire qu'un problème est dans NP si une machine de Turing déterministe peut vérifier en temps polynômial qu'une solution donnée est correcte, mais c'est équivalent.
Oui il est toujours possible de "traduire" un algo non-déterministe en un algo déterministe, comme je le disais les machines de Turing non-déterministes ne résolvent pas plus de problème que les machines déterministes. Le problème c'est que ce faisant, dans le cas des problèmes NP-complets, tu va passer (a priori, sinon chapeau) d'un temps de résolution polynomial à un temps exponentiel. sinon P = NP.

En gros si tu me trouves un las vegas (ou monte carlo, me souviens plus lequel est justifié ici, enfin celui qui donne toujours une solution, mais pas toujours vrai), tu as trouvé une facon de resoudre NP Interessante idée.

Le problème c'est que si le LasVegas ou Monbte Carlo (jamais entendu parlé :)) demande un temps exponentiel, le fait que tu puisse vérifier la solution en temps polynomial après te fait une belle jambe :D.

Par Missmite le 30/10/2002 à 23:55:02 (#2445109)

Les algos de type las vegas et monte carlo sont des algos probabilistes. Tu trouves une solution en temps polynomial, mais tu ne sais pas si elle est juste ou pas, ou alors elle est approchée a un certain Delta pres, le Delta etant un des parametres de la complexité du probleme (et lorsqu'on dit Delta = 0 on retrouve un bon vieil algo exponentiel héhé).

Par LeProctophantasmiste le 31/10/2002 à 0:10:24 (#2445203)

Merci pour l'info :)

euh...

NP (...) des problèmes qu'une machine de Turing non déterministe peut résoudre en temps polynomial, mais pour lesquels il n'existe pas de solution polynomiale déterministe (connue c'est bien le problème je crois ).

Et dire que j'étudie la logique:o . Evidemment comme P est compris dans NP, c'est faux. C'est vrai des NP-complets par contre.

Par Kelem Khâl La'Ri le 31/10/2002 à 1:10:14 (#2445459)

Provient du message de LeProctophantasmiste
Evidemment comme P est compris dans NP, c'est faux.

* Jette un oeil dans un vieux bouquin d'algo théorique et de calculabilité *

P est bien inclus dans NP, mais il n'y a encore aucune preuve formelle de P NP, bien que cette hypothèse soit hautement probable elle n'est pas encore démontrée.

Et oui, cette définition de la NP-complétude existe bel et bien à partir de machines de Turing non-deterministes (equivalentes a des machines de Turing deterministes auxquelles est ajoutée l'instruction supplémentaire CHOIX qui consiste à construire des copies d'états courants, 2^n precisement, ou n=card(E) et E est l'ensemble des données).

Si c'est necessaire, je peux donner la ref du livre ;).