Répondre à la discussion
Affichage des résultats 1 à 19 sur 19

probleme np



  1. #1
    sahdow

    probleme np


    ------

    salut all
    je voudrais juste savoir c'est quoi la différence entre un problème np complet et problème np difficile

    -----

  2. Publicité
  3. #2
    GuYem

    Re : probleme np

    Salut ...
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  4. #3
    sahdow

    Re : probleme np

    What?
    tu me cause de cois mecs

  5. #4
    nissart7831

    Re : probleme np

    Salut,

    je ne sais pas si ça te suffira, mais tu peux trouver quelques explications dans wikipedia :

    http://fr.wikipedia.org/wiki/Th%C3%A...omplexit%C3%A9

    Tu as beaucoup d'autres liens sur le web (Google avec NP complet difficile)

  6. A voir en vidéo sur Futura
  7. #5
    invite7863222222222
    Invité

    Re : probleme np

    Citation Envoyé par sahdow
    salut all
    je voudrais juste savoir c'est quoi la différence entre un problème np complet et problème np difficile
    D'après mes recherches, un problème NP complet est forcement dans NP, mais ce n'est pas nécessaire pour un problème NP difficile qui peut donc être dans une classe de compléxité plus élevée (que NP).

  8. #6
    sahdow

    Re : probleme np

    on effet c'est ce que je viens de trouve un probleme np-complet
    peux etre soluble par ne machine de turing nom deterministe en un temps polynomiale ce qui est pas le cas du probleme np-difficile

  9. Publicité
  10. #7
    invite7863222222222
    Invité

    Re : probleme np

    ce qui est pas le cas du probleme np-difficile

    (NP-complet est inclus dans NP-difficile quand même)

  11. #8
    GuYem

    Re : probleme np

    Citation Envoyé par sahdow
    What?
    tu me cause de cois mecs
    Salut mec, je te cause parce que j'aime bien ta question mais je la comprends pas. J'ai jamais entendu parler des "problèmes NP", tu pourrais expliquer un peu plus en détails histoire de voir si ça peut intéresser des gens.
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  12. #9
    Kelm

    Re : probleme np

    moi ca m'interesse parce que c un probleme du millenaire

    Demontrer que P=NP ou P different de NP
    Enfin si tu pouvais nous apporter quelque renseignement ca seré gentil car je comprend l'idée generale mais pas les subtilité
    merci d'avance

    PS: Qu'est ce qu'une machine de Turing ?==> beaucoup de personne en parle mais sans jamais la definir ...

  13. #10
    nissart7831

    Re : probleme np

    Citation Envoyé par GuYem
    Salut mec, je te cause parce que j'aime bien ta question mais je la comprends pas. J'ai jamais entendu parler des "problèmes NP", tu pourrais expliquer un peu plus en détails histoire de voir si ça peut intéresser des gens.
    Salut GuYem,

    ça touche à la complexité des algorithmes. Une petite introduction ici.

  14. #11
    invite7863222222222
    Invité

    Re : probleme np

    Un problème NP (Non déterministe Polynomial et non pas Non Polynomial !) est un problème que l'on sait résoudre en un temps exponentiel.

    Un exemple est le fameux problème du voyageur de commerce voulant minimiser la longueur parcourue lors de la visite de N villes.

    Aujourd'hui, les mathématiciens ne connaissent qu'une méthode permettant de trouver la solution exacte à ce problème pourtant très simple :

    Enumérer bêtement toutes les possibilités , puis choisir celle qui donne la plus petite longueur...

    Cette solution est envisageable N très petit, (pour N = 4, on a 4! = 24 possibilités), mais elle ne l'est plus dès que N est légèrement plus élevée.

    Par exemple, pour N = 25, il y a déjà 1.5 x 10^25 possibilités.

    Le nombre de possibilités augmente en N!, ce qui veut dire que même si la vitesse des ordinateurs augmentent (progression polynomiale), ce n'est pas suffisant pour rattraper la complexité de ces problèmes.

    Par exemple, l'algorithme de cryptage RSA est un problème NP, c'est ce qui fait sa réussite.

    Un ordinateur actuel devrait passer peut-être 20 ans à énumérer toutes les solutions possibles, pour choisir ensuite celle qui convient.

    Même si on avait un ordinateur super puissant pouvant faire le calcul en 2 minutes, il suffirait d'augmenter N de quelques unités pour que l'ordinateur soit à nouveau dépassé et obligé de repasser encore 20 ans à énumérer toutes les solutions.

    Voilà pour les problèmes NP.

    Les problèmes P, Polynomial, sont ceux dont le temps de calcul de la solution avec le nombre de paramètres n'évolue pas de manière exponentielle, mais polynomiale. Par exemple, un système d'équation linéaire à N variables, est un problème polynomial, P.

    En résumé avec un problème NP, sa résolution se fait en x^N et avec un problème P, elle se fait en N^x.

    Pendant des années (une trentaine), les plus grands mathématiciens ont essayé de trouver des méthodes efficaces (polynomiales) pour résoudre les problèmes NP mais n'en ont malheureusement jamais trouver.

    Il existe des méthodes qui donnent des solutions approchées mais aucune méthode en temps polynomial pour la solution exacte...

    Les deux ensembles de problèmes semblent ainsi bien différents, c'est à dire qu'un problème tel que celui du voyageur de commerce ne peut, par définition, pas se résoudre en un temps polynomial.

    Les mathématiciens ont donc commencé à essayer de prouver théoriquement qu'un problème NP ne peut pas se résoudre en un temps polynomial, on pensait que ca serait très facile...

    Malheureusement, comme vous vous en doutez, on a jamais réussi, impossible de le prouver, on a d'ailleurs jamais réussi à prouver le contraire non plus.

    Si bien qu'aujourd'hui, P = NP ? (comprendre l'ensemble des problèmes de classe P est il égal à l'ensemble des problèmes de classe NP ?) est une des 7 énigmes mathématiques encore non résolues du siecle...


    NB : personnellement, comme dit dans un autre sujet, je me dit que si on arrive pas à résoudre cette énigme, c'est peut-être que ce problème n'est pas prouvable. D'ailleurs, si vous connaissez des travaux qui vont dans ce sens, ca m'intéresse .

  15. #12
    GuYem

    Re : probleme np

    Ah, merci pour cette réponse détaillée Jreeman, me coucherai moins bète ce soir.

    En effet le sujet a l''air intéressant ; on reconnait bien là la folie des mathématiciens qui se disent : "si je n'arrive pas à le résoudre, c'est qu'il ne doit pas y avoir de solutions, alors je vais essayer de montrer qu'il n'y a pas de solutions ...".
    Et sur ce coup, pas de bol, on n'arrive même pas à montrer qu'il n'y a pas de solutions
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  16. Publicité
  17. #13
    invite7863222222222
    Invité

    Re : probleme np

    Oui mais c'est rageant quand même de pas avoir de solution pour un problème aussi simple que celui là.

    On arrive à trouver des résultats mathématiques dans d'autres domaines complexes mais on est tout con, devant l'un des plus vieux problèmes du monde...

    Ca calme quand même les prétentions des mathématiciens .

  18. #14
    rvz

    Re : probleme np

    Salut jreeman et autres,

    Je ne vois pas pourquoi tu as l'impression que c'est un problème tout con. En plus, je crois me souvenir qu'on a énuméré une liste de problèmes assez différents dont on a réussi à démontrer qu'ils étaient équivalents (au sens où, si on arrive à démontrer qu'un seul est P, alors, les autres le sont aussi).
    De plus, on a en aussi pris notre parti dans les problèmes de cryptographie (RSA et compagnie).
    Et puis, l'un des plus vieux problèmes du monde, faut peut-être pas poussé ! Les questions d'algorithme ont du être précisément mises en forme vers 1940, et la formulation mathématique P=NP doit dater des années 60, je pense...

    __
    rvz, que c'est pas parce que c'est dur que c'est indécidable, sinon ç simplifierait beaucoup la progression des maths (Soit un théorème. Preuve : indécidable )

  19. #15
    invite7863222222222
    Invité

    Re : probleme np

    Quand je dis que le problème est tout con, je veux dire que l'expression du problème est simple et facile à appréhender.

    Sinon pour l'indécidabilité, ce n'est qu'un avis personnel et c'est juste une idée que je lancais comme cela au cas où vous sauriez si des travaux ont été fait dans ce sens.

    Des problèmes indécidables, il y en a, je crois avoir lu par exemple, qu'on ne peut pas prouver qu'une équation diophantienne n'admet pas de solutions.

    Les questions d'algorithme ont du être précisément mises en forme vers 1940, et la formulation mathématique P=NP doit dater des années 60, je pense...
    On a formalisé le problème sous la forme P = NP que récemment, mais le problème existe dans la vie pratiques des Hommes depuis plus longtemps que cela.

  20. #16
    rvz

    Re : probleme np

    Citation Envoyé par jreeman
    Des problèmes indécidables, il y en a, je crois avoir lu par exemple, qu'on ne peut pas prouver qu'une équation diophantienne n'admet pas de solutions.
    Bon, on va dire _sauf pour le théorème de Fermat Wiles_
    Disons que je suis comme toi, et que je n'en sais rien. Mais bon, selon moi, des problèmes vraiment indécidables, il n'y en a pas tant que ça, mais je t'accorde que c'est quasiment un débat philosophique
    Disons qu'il y a des axiomes qui "doivent être moralement vrais", et, disons que tant qu'on n'a pas réduit le problème à un axiome de ce genre, pour moi, il y a tout un travail de preuves "standardes" (Orth ?) à faire.

    __
    rvz

  21. #17
    invite7863222222222
    Invité

    Re : probleme np

    D'ailleurs pour les équations diophantiennes, y'a quelque chose qui me chiffonne, on sait prouver qu'une équation diophantienne admet des solutions mais on ne sait pas prouver qu'elle n'en admet pas.

    C'est pas contradictoire ?

  22. #18
    invite986312212
    Invité

    Re : probleme np

    est-ce que tu ne fais pas allusion au dixième problème de Hilbert? si c'est ça je crois que la formulation est plutôt: il n'existe pas d'algorithme universel qui permette de décider si une équation diophantienne admet ou non des solutions.

  23. Publicité
  24. #19
    invite7863222222222
    Invité

    Re : probleme np

    Citation Envoyé par ambrosio
    est-ce que tu ne fais pas allusion au dixième problème de Hilbert? si c'est ça je crois que la formulation est plutôt: il n'existe pas d'algorithme universel qui permette de décider si une équation diophantienne admet ou non des solutions.
    Oui c'est surement ca alors. Je dois y aller. Donc surement @+

Discussions similaires

  1. Réponses: 11
    Dernier message: 26/05/2011, 13h27
  2. Un petit problème qui me pause problème lol
    Par Leonpolou dans le forum Mathématiques du supérieur
    Réponses: 13
    Dernier message: 31/03/2009, 16h28
  3. problème avec un lecteur mp4(le problème vient de l'ordinateur)
    Par mat_the_bad_boy dans le forum Matériel - Hardware
    Réponses: 3
    Dernier message: 29/10/2007, 17h53
  4. TPE : le problème de la problématique... pose problème
    Par grisgris dans le forum TPE / TIPE et autres travaux
    Réponses: 0
    Dernier message: 21/09/2006, 19h45