Discussion :

[gabbf29]

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

[pseudocode]

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.

Par contre il y a des "problèmes 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''..

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.

Exemple: il serait aussi "rapide" de vérifier une clé de chiffrement/déchiffrement que de cracker cette clé.

[AdmChiMay]

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).

[souviron34]

Concrètement, que pourrait découler de la résolution d'un algorithme irrésolu (comme ce dernier) ?

Une série de problèmes non résolus :

The Open Problems Project

[davcha]

Bref, ta formule entre les parenthèses du O peut se ramener à un polynome (P pour Polynomial) ou pas (NP pour Non Polynomial).

C'est pas plutôt "Déterministe Polynomial" et "Non déterministe Polynomial" ?

[pseudocode]

C'est pas plutôt "Déterministe Polynomial" et "Non déterministe Polynomial" ?

P = problème qui peut être résolu en utilisant un algorithme (1) ayant une complexité polynomiale (2).

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

Ce n'est pas le polynome qui est déterministe. C'est la machine de turing.