Version imprimable
Bonjour,
Je débute en matière d'algorithme
Par simple curiosité, je recherchais sur le web des algorithmes non-résolus. Je suis arrivé sur le plus célèbre (du moins, c'est ce qu'il est dit), celui du P et NP.
Je ne comprend que vaguement en quoi il consiste, mais ce qui m’intéresse vraiment c'est son utilité ''réelle''..
Concrètement, que pourrait découler de la résolution d'un algorithme irrésolu (comme ce dernier) ?
Merci
Un algorithme est une suite d'opération permettant de résoudre un problème. Il n' y a donc pas "d'algorithmes non-résolus", puisque l'algorithme est une solution au problème. :D
Par contre il y a des "problèmes non-résolus".
Si P=NP alors un problème dont on peut "rapidement" vérifier qu'une solution donnée est correcte, dispose d'une méthode pour trouver "rapidement" cette solution.Citation:
Je suis arrivé sur le plus célèbre (du moins, c'est ce qu'il est dit), celui du P et NP. Je ne comprend que vaguement en quoi il consiste, mais ce qui m’intéresse vraiment c'est son utilité ''réelle''..
Exemple: il serait aussi "rapide" de vérifier une clé de chiffrement/déchiffrement que de cracker cette clé. :aie:
En fait, on cherche souvent à classer les algorithmes (donc les méthodes de résolution de problèmes), selon le temps qu'elles prennent. Ce temps dépend généralement de la taille des données. On parle aussi de calcul de complexité, et tu verras des notations du style O(une formule).
Par exemple : addition n nombres, c'est proportionnel au nombre de nombres (évident, yes), donc c'est en O(n). Multiplier deux matrices, cela prends 3 boucles imbriquées, sur la taille n : c'est en O(n^3).^Il y a beauuuuucoup plus complexe comme exemples.
Bref, ta formule entre les parenthèses du O peut se ramener à un polynome (P pour Polynomial) ou pas (NP pour Non Polynomial). Tu le retrouveras ici.
Dans le premier cas (P), ce n'est qu'une histoire de mettre la force de travail sur le taf (µP, cores, GPU, machines), car si on connait la taille des données, on sait d'avance le temps max pour avoir le résultat. D'où le commentaire de la réponse précédente.
Dans le second cas (NP), ben… on sait plus trop si ça va prendre quelques heures ou quelques millons d'années (dans un cas optimiste).
On cherche donc à classer les algorithmes : pour certains on sait qu'ils sont en P, d'autres en NP, et d'autres on ne sait pas alors en attendant on les classe généralement en NP (avec un post-it dessus pour dire qu'en fait on ne sait pas encore trancher).
Une série de problèmes non résolus :Citation:
Envoyé par gabbf29
The Open Problems Project
:D
C'est pas plutôt "Déterministe Polynomial" et "Non déterministe Polynomial" ?Citation:
Envoyé par AdmChiMay
P = problème qui peut être résolu en utilisant un algorithme (1) ayant une complexité polynomiale (2).Citation:
Envoyé par davcha
NP = problème qui peut être résolu en utilisant un algorithme (1) ayant une complexité non-polynomiale (2).
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
(1): algorithme exécuté par une machine de Turing déterministe
(2): complexité en temps de traitement par rapport à la taille des données d'entrée
:arrow: Ce n'est pas le polynome qui est déterministe. C'est la machine de turing. ;)