• # Re : Complexité d'algorithmes

    Posté par  . Évalué à 6.

    y'en a 5 ici, partant de la tu pourras ss doute en trouver d'autres :
    http://fr.wikipedia.org/wiki/NP-complet(...)

  • # Autre piste ...

    Posté par  . Évalué à 3.

    Profite en pour découvrir les classements des problèmes, beaucoup plus rigolo !

    Il s'agit de classer les problèmes selon la complexité des algorithmes pour les résoudre.

    http://wwwsi.supelec.fr/yb/projets/algogen/NP-Complet.htm(...)
    Cette page est un peu simpliste, mais explique bien les concepts.

    par exemple :
    Ces problèmes, n'appartenant ni à la classe P, ni à la classe E, sont dits de classe NP, non déterministe polynomiaux.
    C'est vrai mais le Hic c'est que l'on ne peu pas toujours démontrer à quelle classe appartient un problème (demandant un algorithme forcément exponentiel ou non), et c'est ca qui est intéressant.
    En effet certain problèmes de E sont des NP, mais on ne le sait pas, et certain NP sont polynomiaux - classe P - , et c'est pas sûr non plus.

    Les limites entre les problèmes sont floues (du point de vue humain), et théoriquement nettes - d'où le racourci de la page citée.

  • # nombres premiers

    Posté par  (site web personnel) . Évalué à 4.

    Bah, y'a le classique : Décomposition en facteurs premiers d'un entier. A priori, c'est exponentiel, mais on n'est pas sur (et on espère, pasque sinon, on peut dire adieu à la crypto telle qu'on la connait aujourd'hui !). Le truc rigolo, c'est que sur un ordinateur quantique (qui n'existe pour l'instant qu'en théorie), c'est polynomial, alors qu'on ne sait pas résoudre le voyageur de commerce en temps polynomial.

    Pour le test de primalité, par contre, on ne savait pas si c'était exponentiel ou pas, mais je crois que des indiens ont trouvé un algo polynomial récemment.

    Sinon, si tu veux un problème de complexité équivalente au voyageur de commerce, l'autre classique, c'est SAT. (satisfaisabilité d'un ensemble de clauses)

  • # simplexe

    Posté par  (site web personnel) . Évalué à 3.

    Le simplexe est un peu étrange :
    C'est un algo qui cherche des solution dans N^n à

    max f(x) tel que x est dans N^n et f linéaire
    et disons n contraintes linéaires

    alors la taille de l'ensemble des soluces est expo : de taille 2^n

    Mais l'algo donne très rapidement un résultat et je crois qu'on ne sait pas encore pourquoi !?

    • [^] # Re: simplexe

      Posté par  (site web personnel) . Évalué à 2.

      > C'est un algo qui cherche des solution dans N^n à

      Plutôt dans R+^n. Le simplex dans les entiers, c'est encore une autre paire de manches ...

      > alors la taille de l'ensemble des soluces est expo : de taille 2^n

      Non, en général, la solution est unique (c'est un sommet du polyedre). Ca peut aussi être une face du polyedre, et là, dans R, il y a une infinité de solutions.

      C'est la complexité dans le pire cas de l'algo du simplex qui est exponentiel.

      > Mais l'algo donne très rapidement un résultat et je crois qu'on ne sait pas encore pourquoi !?

      En effet, en pratique, c'est très rare qu'on soit dans le cas exponentiel, donc le simplex marche bien en pratique. Là ou ca devient rigolo, c'est qu'il y a quelqu'un qui a trouvé un algorithme polynomial pour faire la même chose, mais qu'il n'est prèsque jamais utilisé parce que finalement, l'algo "exponentiel" va plus vite !

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.