Problèmes, algorithmes et structures de données

Les algorithmes résolvent des problèmes. Voici quelques exemples de problèmes et leur solution algorithmique :

• un entier n ; n est-il premier ? L'algorithme stochastique de Miller-Rabin
• un système d'équations linéaires ; le système est-il régulier ? si oui, calculer sa solution. L'algorithme de triangulation de Gauss
• un n- uplet de nombres complexes ; calculer la transformée de Fourier discrète de ce n-uplet. La transformée de Fourier rapide
• une chaîne de caractères s ; s est-elle un programme Java correct ? L'analyse syntaxique par un automate à pile
• un ensemble de villes et de routes les reliant, la longueur de ces routes, et deux villes de cet ensemble ; calculer la longueur du chemin le plus court entre ces deux villes. L'algorithme du plus court chemin de Floyd, par programmation dynamique
• un ensemble de tâches, leurs durées et leurs contraintes de précédence ; ces tâches sont-elles réalisables ? si oui, calculer leurs dates de réalisation au plus tôt et au plus tard. Un algorithme glouton d'affectation de tâches
• un réseau de transport de marchandises, la capacité de chaque route, et un entrepôt ; quelle est la quantité maximale de marchandises que ce réseau peut écouler à partir de l'entrepôt ? L'algorithme de flot maximum de Ford-Fulkerson
• comment rétablir le réseau électrique après une tempête en réparant le minimum de lignes électriques ? L'algorithme glouton d'arbre couvrant minimum de Prim, ou celui de Kruskal

Il n'existe pas, hélas, de méthode universelle pour construire des algorithmes. Il y a cependant quelques grandes méthodes :

• la méthode incrémentale : c'est l'idée de résoudre un problème P(n) à partir d'une solution de P(n-1) ; c'est typiquement une méthode par récurrence, qui peut donner lieu aussi bien à des programmes itératifs qu'à des programmes récursifs ; dans le cas d'un problème d'optimisation, la méthode gloutonne consiste à construire une solution de P(n) en prolongeant une solution de P(n-1) par un choix localement optimal ;
•   la méthode << diviser pour régner >> : c'est une méthode descendante, qui conduit à décomposer un problème en sous-problèmes et à construire une solution du problème en composant les solutions de ces sous-problèmes, typiquement en transformant un problème P(n) en deux problèmes P(n/2) ;
•   la programmation dynamique : c'est une méthode ascendante, utilisable pour des problèmes d'optimisation, qui consiste à construire la solution d'un problème à partir des solutions de tous les sous-problèmes ; elle s'applique quand toute sous-solution d'une solution optimale est optimale pour le sous-problème correspondant.

La notion même d'algorithme suppose que les données d'un problème soient représentées de façon finie. Ceci marque la différence entre un entier et un nombre réel (élément de l'ensemble R) : un entier quelconque a une représentation finie, ce n'est pas le cas d'un nombre réel quelconque (mais certains nombres réels, aussi bien $\sqrt{2}$ que $\pi$, admettent une représentation finie par un programme qui les calcule). Il suffirait donc d'exiger que les données d'un problème soient représentées par une suite de 0 et de 1, ce qu'on appelle un mot binaire. Généralement, au terme d'une étape de modélisation, les données apparaissent sous une forme plus structurée : une matrice, un graphe, une table, etc.

La notion de structure de données est aussi importante en informatique que les structures des mathématiques (corps, espace vectoriel, espace de probabilités, variété différentielle, etc). En informatique comme en mathématiques, il s'agit d'un ensemble de données et de certaines opérations sur celles-ci. D'ailleurs certaines de ces structures sont autant étudiées de part et d'autre : les notions de monoïde, de graphe ou de matroïde figurent dans les cours de mathématiques discrètes. D'autres, les piles, files, tas ou tables sont plus particulièrement étudiées, et surtout utilisées, par les informaticiens. Les structures de données jouent un rôle central dans la conception et la formulation de certains algorithmes : les piles pour le parcours en profondeur d'un graphe, les files pour leur parcours en largeur, les tas pour le codage de Huffman, et les arbres pour le décodage.

En outre, certains problèmes ne peuvent pas être résolus par un algorithme. C'est le cas du problème consistant à déterminer si l'exécution d'un programme quelconque se termine : le plus simple est de l'exécuter, mais si elle ne termine pas, on ne saura jamais si elle termine ou non. Il existe d'autres problèmes, qui peuvent être résolus par des algorithmes, mais tels que tous les algorithmes connus à ce jour pour les résoudre ont un coût excessif (par exemple, un coût exponentiel) : on ne pourra donc les exécuter que sur des données de petite taille. Un exemple en est la détermination d'une tournée d'un voyageur de commerce de longueur minimale. On est donc amené à être moins exigeant : on cherchera un algorithme qui calcule des solutions approchées, ou alors on renoncera au caractère déterministe des algorithmes, et on introduira de l'aléa.