Calculabilité

Objectif

  • Découvrir le concept de calculabilité.

Mise en situation

L'apparition de la théorie de l'Informatique est très étroitement liée à la théorie de la Calculabilité.

FondamentalFonction calculable

Une fonction f est calculable si, pour tout argument x, il est possible d'obtenir f(x) en un nombre fini d'étapes.

Algorithme et fonction calculable

On comprend très vite qu'un algorithme représente une fonction calculable car on peut faire un parallèle entre le nombre fini d'étape de la fonction et la suite finie d'instructions de l'algorithme. Ainsi, le travail de l'algorithme est assimilable à un calcul.

Les algorithmes et leurs problèmes

Un algorithme a toujours pour but de résoudre un problème donné, que ce dernier soit compliqué (plus court chemin dans un graphe) ou très simple (une division euclidienne). La théorie de la Calculabilité est essentielle pour caractériser la nature des problèmes.

Indécidabilité

Il existe des choses impossibles à calculer, c'est-à-dire des problèmes insolubles. Ainsi, il existe des problèmes dont il est possible de calculer la solution et d'autres non. L'exemple le plus classique de problème indécidable est le problème de l'arrêt : il n'existe pas d'algorithme déterminant si n'importe quel algorithme donné se termine.

Classe de problèmes

Les problèmes sont classiquement classés en fonction des algorithmes qui les résolvent :

  • P : il existe un algorithme qui résout le problème et se termine en temps polynomial, c'est-à-dire qui n'explose pas en fonction de la taille des données d'entrées.

  • NP : il existe un algorithme qui vérifie la solution d'un problème en temps polynomial mais il faudra un temps exponentiel pour trouver une solution.

  • Indécidables : Il n'existe pas d'algorithme pour résoudre le problème.

Les problèmes NP

Les problèmes NP sont considérés comme impossibles à résoudre dans un temps humain.

Pour une taille importante de données d'entrées, l'exécution de l'algorithme par un ordinateur moderne pourra prendre des années, des siècles, voire plus... Il existe de nombreux problèmes NP et il est nécessaire d'adopter des optimisations pour trouver une solution « sub-optimale » en un temps polynomial. Une solution « sub-optimale » est une solution qui s'approche de la solution idéale.

ExempleFaut-il déplacer ma reine ou mon fou ?

Un problème NP très connu est celui du calcul du meilleur coup dans le jeu d'échecs.

Pour chaque position aux échecs, il existe un nombre extrêmement grand de positions possibles. Ainsi, il est possible théoriquement de calculer toutes ces positions. En revanche, l'algorithme mettra des siècles à se terminer. Les intelligences artificielles telles que Deep Blue calculent toutes les positions possibles sur les x prochains tours et choisiront celui qui offre la meilleure position dans x tours. Ce qui rend les intelligences artificielles meilleures que les humains est leur capacité à se projeter plus loin que les humains. Les joueurs humains calculent également les potentielles positions futures mais peuvent calculer beaucoup moins de tours que les ordinateurs modernes.

ExempleRésoudre un Rubik's Cube

Trouver la solution d'un Rubik's Cube est un problème P. Il est très simple de le résoudre, en témoignent les records du monde de vitesse. Même avec des cubes un peu plus grands, le nombre de possibilités croît beaucoup moins que le nombre de coups aux échecs.

ExempleTrouver son chemin

Les applications GPS se sont largement démocratisées et résolvent toutes un même problème : trouver le plus court chemin entre A et B. Bien qu'il existe une infinité de chemins entre A et B, ce problème est P car il n'est pas nécessaire d'essayer tous les chemins contrairement aux échecs où il faut calculer l'ensemble des coups possibles. Il existe des algorithmes qui permettent d'exclure rapidement les solutions impossibles et d'arriver au plus court chemin en temps polynomial. On comprend donc que la grande différence entre P et NP réside dans la nature exponentielle du nombre de calculs à effectuer pour arriver à la solution.

ComplémentP = NP ?

Il existe un problème mathématique considéré comme un des sept problèmes du millénaire par les mathématiciens : « P=NP ? » Ce problème vise à affirmer ou infirmer formellement que les problèmes NP sont, ou pas, des problèmes P. La preuve de l'égalité impliquerait qu'il existe un algorithme en temps polynomial pour résoudre des problèmes tels que le cassage des chiffrements modernes sur lesquels est fondé le système de transaction bancaire.

À retenir

  • Un algorithme est assimilable à un calcul.

  • Il existe des problèmes impossibles à résoudre mais il existe également des problèmes possibles à résoudre en théorie, mais en pratique (pas en un temps limité).