Modèles de calcul

Les ordinateurs incluent des algorithmes de base pour résoudre des problèmes comme l'addition, la soustraction ou la comparaison de deux nombres. Les ordinateurs, en raison de leurs racines dans les calculatrices, sont optimisés pour résoudre ces problèmes ; ces algorithmes de base sont des opérations à temps constant. Ce que la programmation (programming) offre est la capacité de définir nos propres algorithmes qui peuvent être utilisés pour résoudre des problèmes plus complexes, tels que la recherche, le tri et le hachage. Malheureusement, ces algorithmes programmés ne sont pas aussi rapides que les opérations de base. Nous avons même vu certains problèmes faire face à une explosion combinatoire (combinatorial explosion) du nombre de solutions potentielles. Pour beaucoup de ces problèmes, les meilleurs algorithmes connus ne font pas beaucoup mieux que la force brute, qui prend un temps exponentiel.

Dans une perspective plus large, l'informatique aborde la question centrale de la manière dont les humains peuvent encoder l'intelligence. Notre discussion sur la conception d'algorithmes a ancré l'activité dans la modélisation de problèmes, le processus d'encodage d'un phénomène ou d'un problème complexe du monde réel sous une forme plus abstraite ou simple. Comment la modélisation de problèmes est-elle contrainte par le modèle de calcul, ou les règles de l'ordinateur sous-jacent qui exécute un algorithme ? Pourquoi certains problèmes sont-ils difficiles à exécuter pour les ordinateurs ?

L'explosion combinatoire pose un problème pour les algorithmes informatiques car notre modèle de calcul suppose que les ordinateurs n'ont qu'un seul fil d'exécution et n'exécutent qu'une seule opération de base à chaque étape. Si nous renversons une partie de cette hypothèse, soit en créant des ordinateurs avec plusieurs processeurs, soit en créant des opérations plus sophistiquées, il pourrait alors être possible de gérer l'explosion combinatoire. Presque tout le matériel informatique actuel, allant des superordinateurs massifs aux smartphones portables, repose au moins dans une certaine mesure sur l'extension du modèle de calcul pour calculer des solutions aux problèmes plus efficacement. Même ainsi, une grande partie du matériel informatique actuel repose toujours sur les mêmes hypothèses de programmation fondamentales : qu'il existe des variables pour représenter les données et des opérations arithmétiques ou logiques.

Machines de Turing

Dans les années 1800, Charles Babbage a imaginé une machine mécanique – la machine analytique (Analytical Engine) – qui pouvait calculer automatiquement des formules mathématiques. Ada Lovelace a ensuite extrapolé que la machine analytique pouvait résoudre des algorithmes plus généraux en utilisant des boucles pour répéter des processus et des variables pour représenter des données. La vision des algorithmes de Lovelace représentait une synthèse entre l'intuition humaine et le raisonnement mathématique. Au milieu des années 1900, les idées de Lovelace ont inspiré Alan Turing à imaginer une notion plus générale d'algorithmes et de machines capables d'exécuter ces algorithmes. Une machine de Turing (Turing machine) est un modèle abstrait de calcul pour l'exécution de tout algorithme informatique. Une machine de Turing décrit les ordinateurs en termes de trois idées clés :

1. une banque de mémoire pour stocker des données.
2. une table d'instructions, où chaque instruction peut soit :
   1. stocker une valeur dans la banque de mémoire.
   2. récupérer une valeur de la banque de mémoire.
   3. effectuer une opération de base sur une valeur.
   4. définir quelle instruction sera exécutée ensuite en modifiant le compteur ordinal.
3. un compteur ordinal qui garde la trace de l'instruction actuelle dans la table d'instructions.

Une machine de Turing exécute un algorithme (algorithm) informatique en suivant chaque instruction spécifiée par le compteur ordinal. Un algorithme peut utiliser ces opérations de base pour calculer la somme de 1 et 1.

1. Stocker la valeur 1 à l'adresse A dans la banque de mémoire.
2. Stocker la valeur 1 à l'adresse B dans la banque de mémoire.
3. Additionner les valeurs aux adresses A et B, puis stocker le résultat à l'adresse A.

Ce qui rend les ordinateurs utiles n'est pas seulement le fait qu'ils peuvent calculer des nombres, mais qu'ils peuvent encoder de la logique dans les instructions. Au lieu de simplement calculer la somme de 1 et 1, ce programme continue d'ajouter 1 à une somme croissante stockée à l'adresse A.

1. Stocker la valeur 1 à l'adresse A dans la banque de mémoire.
2. Stocker la valeur 1 à l'adresse B dans la banque de mémoire.
3. Additionner les valeurs aux adresses A et B, puis stocker le résultat à l'adresse A.
4. Définir le compteur ordinal pour exécuter l'étape 3 ensuite.

Le modèle abstrait de calcul de la machine de Turing suppose un seul fil d'exécution suivant chaque instruction d'un algorithme. Bien que les ordinateurs actuels soient beaucoup plus efficaces que les premiers ordinateurs qui ont réalisé la machine de Turing, la plupart des ordinateurs reposent toujours sur les mêmes hypothèses fondamentales concernant l'exécution des algorithmes. L'algorithme de recherche séquentielle en temps O(N), bien qu'il puisse s'exécuter 1 000 fois plus vite sur les ordinateurs actuels, croît toujours linéairement par rapport à la taille de l'entrée. Un algorithme par force brute en temps O(2^N), bien qu'il puisse s'exécuter 1 000 fois plus vite sur les ordinateurs actuels, croît toujours exponentiellement par rapport à la taille de l'entrée. Même si les ordinateurs deviennent plus rapides avec le temps, les algorithmes inefficaces ne peuvent toujours pas être utilisés pour résoudre des problèmes de taille supérieure à quelques milliers d'éléments.

Classes de complexité

Un sous-domaine de l'informatique est l'informatique théorique, qui étudie les modèles de calcul, leur application aux algorithmes et la complexité des problèmes. La complexité d'un problème est la complexité (en termes de ressources de temps ou de mémoire requises) des algorithmes les plus efficaces pour résoudre le problème. Les informaticiens théoriciens s'intéressent à la compréhension de la difficulté d'un problème en termes de complexité temporelle, de complexité spatiale et d'autres mesures de complexité.

Dans ce chapitre, nous nous sommes concentrés sur la résolution de problèmes connus pour avoir des algorithmes en temps polynomial. La recherche, le tri, le hachage, le parcours, les arbres couvrants minimaux ou les plus courts chemins sont tous des exemples de problèmes de la classe de complexité en temps polynomial (P) (polynomial (P) time complexity class) car ce sont tous des problèmes dont les temps d'exécution ont une expression polynomiale telle que O(1), O(log N), O(N), O(N log N), O(N²), O(N³). En général, ces problèmes sont considérés comme traitables (tractable) car les ordinateurs peuvent les résoudre en un temps raisonnable. Mais il existe de nombreux problèmes qui sont considérés comme intraitable (intractable) car ils n'ont pas d'algorithmes efficaces en temps polynomial.

La classe de complexité en temps polynomial non déterministe (NP) (nondeterministic polynomial (NP) time complexity class) fait référence à tous les problèmes qui peuvent être résolus en temps polynomial par un algorithme non déterministe. Un algorithme non déterministe (nondeterministic algorithm) est un type spécial de machine de Turing qui, à chaque étape, peut choisir de manière non déterministe quelle instruction exécuter, et est considéré comme réussissant à trouver une solution si toute combinaison de ces choix non déterministes conduit finalement à une solution correcte. En d'autres termes, contrairement à un algorithme déterministe, tel qu'un algorithme glouton, qui doit appliquer à plusieurs reprises une règle simple pour sélectionner de manière déterministe l'élément suivant dans une solution, un algorithme non déterministe est capable d'explorer simultanément tous les choix possibles. Nous n'avons pas encore d'ordinateurs capables d'exécuter des algorithmes non déterministes, mais si nous en avions, nous serions en mesure de résoudre efficacement tout problème combinatoire en nous appuyant sur le pouvoir spécial du non-déterminisme.

Techniquement, tous les problèmes P sont aussi des problèmes NP car nous avons déjà des algorithmes déterministes pour les résoudre et n'avons donc pas besoin de nous appuyer sur le pouvoir spécial du non-déterminisme. Par exemple, l'algorithme de Dijkstra fournit une solution déterministe en temps polynomial au problème des plus courts chemins en construisant un arbre des plus courts chemins à partir du sommet de départ vers l'extérieur. Cette application du paradigme algorithmique glouton repose sur la structure de l'arbre des plus courts chemins, puisque le plus court chemin vers un point plus éloigné du départ doit s'appuyer sur le plus court chemin vers un point plus proche du départ.

Problèmes NP-complets

NP-complet (NP-complete) fait référence à tous les problèmes NP les plus difficiles – les problèmes combinatoires pour lesquels nous n'avons pas d'algorithmes déterministes en temps polynomial. Plus précisément, un problème PI est dit NP-complet si PI est dans NP et si pour chaque problème dans NP, il existe une réduction qui réduit le problème à PI. Par exemple, un plus long chemin (longest path), ou le problème de trouver le chemin de coût le plus élevé pour aller d'un sommet à un autre sans répéter les sommets, est un problème NP-complet opposé aux plus courts chemins (Figure 3.32). Qu'est-ce qui rend les plus longs chemins tellement plus difficiles à résoudre que les plus courts chemins ? D'une part, il n'y a pas de structure sous-jacente à la solution que nous puissions utiliser pour appliquer de manière répétée une règle simple comme dans un algorithme glouton. Avec le problème des plus courts chemins, nous pouvions nous appuyer sur l'arbre des plus courts chemins pour éclairer la solution. Mais dans les plus longs chemins, le but est de flâner dans le graphe. Le plus long chemin entre deux sommets quelconques impliquera probablement de parcourir autant d'arêtes que possible pour maximiser la distance, en visitant de nombreux sommets en cours de route. Pour certains graphes, les plus longs chemins pourraient même visiter tous les sommets du graphe. Dans cette situation, les plus longs chemins ne forment pas un arbre et impliquent plutôt d'ordonner tous les sommets du graphe pour chaque plus long chemin. L'identification du plus long chemin correct nécessite alors de lister tous les chemins possibles dans le graphe – une explosion combinatoire des combinaisons d'arêtes et de sommets qui peuvent être sélectionnés pour former une solution.

Figure 3.32 Le plus long chemin dans un graphe maximise la distance, ce qui implique souvent de visiter de nombreux sommets en cours de route. (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

Lié au problème des plus longs chemins est le problème du voyageur de commerce (TSP) (traveling salesperson problem (TSP)), qui est le problème de trouver, étant donné le coût du chemin de chaque paire de sommets, le parcours (tour) de coût le plus bas, ou chemin à partir d'un sommet de départ visitant chaque sommet du graphe une fois, y compris un retour au sommet de départ. Comparé au TSP, qui consiste à trouver le parcours de coût le plus bas, le problème des plus longs chemins est comme trouver le parcours de coût le plus élevé. Ce qui rend ces deux problèmes difficiles est que nous n'avons pas de règle simple pour sélectionner l'élément suivant à inclure dans la solution. À moins d'avoir le pouvoir spécial du non-déterminisme, il est difficile de savoir dès le début quelle arête est la bonne à inclure dans la solution finale. Appliquer une règle simple comme « Sélectionner l'arête avec le coût le plus bas » pourrait ne pas nécessairement conduire au parcours global de coût le plus bas. Même si cette règle simple a fonctionné pour le problème des arbres couvrants minimaux, la restriction supplémentaire d'un parcours plutôt qu'un arbre rend le TSP un problème beaucoup plus difficile à résoudre efficacement. Bien que nous ayons des algorithmes efficaces pour les plus courts chemins, nous n'avons pas d'algorithmes efficaces pour le plus court parcours.

Comment savoir si un problème est NP-complet ? Plus tôt, nous avons introduit la réduction comme un paradigme algorithmique qui est non seulement utile pour résoudre des problèmes, mais aussi pour relier la difficulté des problèmes. Une réduction (reduction) d'un problème difficile A à un autre problème B prouve que B est aussi difficile que A. Il s'avère que tous les problèmes NP-complets peuvent être réduits à tous les autres, de sorte qu'un algorithme pour résoudre n'importe quel problème NP-complet résout tous les problèmes NP-complets.

P versus NP

Les plus longs chemins et le TSP ne sont que deux parmi des milliers de problèmes NP-complets (NP-complete) pour lesquels nous n'avons pas d'algorithmes efficaces. La question de P versus NP demande s'il est possible de concevoir un algorithme déterministe en temps polynomial pour résoudre n'importe lequel – et donc tous – des problèmes NP-complets. Il y a deux réponses possibles à la question de P (P) versus NP (NP) :

• Si P = NP, alors il existe un algorithme déterministe en temps polynomial pour résoudre tous les problèmes NP-complets.
• Si P ≠ NP, alors il existe des problèmes NP-complets qui ne peuvent pas être résolus avec un algorithme déterministe en temps polynomial.

La plupart des informaticiens théoriciens croient que P ≠ NP ; en d'autres termes, il est impossible de concevoir un algorithme déterministe en temps polynomial pour les plus longs chemins, le TSP ou tout autre problème NP-complet. Cependant, ils n'ont aucune preuve définitive que P = NP ou P ≠ NP. Un algorithme efficace pour n'importe quel problème NP-complet ne résoudrait pas seulement directement les problèmes de routage et de logistique, mais permettrait également des avancées massives dans la découverte de médicaments grâce à la simulation scientifique, par exemple. Il briserait également essentiellement tous les systèmes modernes de sécurité Internet et de mots de passe – parmi des milliers d'autres problèmes.