Page 2 sur 2 PremièrePremière 2
Affichage des résultats 31 à 32 sur 32

Actualité - En bref : un nouvel algorithme déjoue les systèmes de cryptographie



  1. #31
    Schrodies-cat

    Re : Actualité - En bref : un nouvel algorithme déjoue les systèmes de cryptographie

    Je vais essayer une fois de plus de remettre les choses d'aplomb:
    Considérons un "défi" de sudoku, qui consiste à compléter une grille particulière n2*n2.
    J'utilise "défi" car "problème" est polysémique.
    Si on vous propose une solution, il est facile de vérifier si c'est oui ou non une solution, le temps de calcul nécessaire ne croit pas beaucoup plus vite que la taille de la grille ou la taille des données nécessaires pour coder le défi. C'est pour cela que le problème du sudoku généralisé est un problème NP.

    Par contre si on n'a pas une solution, c'est beaucoup plus difficile d'en trouver une !
    Le problème du sudoku généralisé est NP-complet, ce qui laisse penser (c'est une grande conjecture), qu'il n'y pas d'algorithme permettant de le résoudre en un temps majoré par une fonction polynomiale de la taille des données, en tout cas à coup sur.
    Il n'est pire sot que qui ne veut pas comprendre .

  2. Publicité
  3. #32
    Noress

    Re : Actualité - En bref : un nouvel algorithme déjoue les systèmes de cryptographie

    Citation Envoyé par Schrodies-cat Voir le message
    Le problème du sudoku généralisé est NP-complet, ce qui laisse penser (c'est une grande conjecture), qu'il n'y pas d'algorithme permettant de le résoudre en un temps majoré par une fonction polynomiale de la taille des données, en tout cas à coup sur.
    Oui, pour ma part je ne répond que dans le cadre d'un ensemble de solutions incomplète. Selon Marcus du Sautoy ("Le mystère des nombres", page 254 chez folio) :
    "Trouver un programme efficace pour résoudre des sudokus arbitrairement grands est un problème NP-complet. Parfois lorsqu'il s'agit de sudokus difficiles, il vous faut émettre des suppositions en fonction des implications logiques qu'elles engendrent ; il ne semble pas exister de moyen de deviner astucieusement, il faut essayer des séries de suppositions jusqu'à ce que l'une d'entre elles vous oriente vers un réponse satisfaisante."

Page 2 sur 2 PremièrePremière 2