LES ALGORITHMES ET LEUR COUT

Algorithmes

Un algorithme est un ensemble d’opérations de calcul élémentaires, organisé selon des règles précises dans le but de résoudre un problème donné. Pour chaque donnée du problème, l’algorithme retourne une réponse apres un nombre fini d’opérations. Les opérations élémentaires sont par exemple les opérations arithmétiques usuelles, les transferts de données, les comparaisons entre données, etc. Selon le niveau d’abstraction ou l’on se place, les opérations arithmétiques et les objets sur lesquels elles portent peuvent être plus ou moins compliquées. Il peut s’agir simplement d’additionner des entiers naturels, ou de multiplier des polynomes, ou encore de calculer les valeurs propres d’une matrice. Pour un système de calcul formel, il s’agit là d’opérations élémentaires, parce qu’elles ont été programmées et sont disponibles dans des bibliothèques, plus ou moins transparentes à l’utilisateur; dans un langage comme Pascal, ces opérations ne sont pas disponibles. Il apparait utile de ne considérer comme véritablement élémentaires que les opérations dont le temps de calcul est constant, c’est-à-dire ne dépend pas de la taille des opérandes. Par exemple, l’addition d’entiers de taille bornée a priori (les integer en Pascal) est une opération élémentaire; l’addition d’entiers de taille quelconque ne l’est pas. De même, le test d’appartenance d’un élément à un ensemble n’est pas une opération élémentaire en ce sens, parce que son temps d’exécution dépend de la taille de l’ensemble, et ceci même si dans certains langages de programmation, il existe des instructions de base qui permettent de réaliser cette opération. L’organisation des calculs, dans un algorithme, est souvent appelée sa structure de controle. Cette structure détermine l’ordre dans lequel il convient de tester des conditions, de répéter des opérations, de recommencer tout ou partie des calculs sur un sous-ensemble de données, etc. Là aussi, des conventions existent sur la facon de mesurer le cout des opérations; la richesse des structures de contrôle dépend fortement des langages de programmation. Le langage Pascal est peut être l’un des plus pauvres dans ce domaine parmi les langages modernes. En général, le coût des structures de controle peut être négligé, parce qu’il est pris en compte, asymptotiquement, par les opérations élémentaires. En fait, le surcout provenant par exemple d’une programmation récursive n’est vraiment sensible que lorsqu’elle entraine des recopies massives de données.

 Problèmes intraitables

Contrairement à une idée largement répandue, tout problème ne peut être résolu par un algorithme. Ce n’est pas une question de taille des données, mais une impossibilité fondamentale. On doit la preuve de ce fait aux logiciens des années 30 et 40. Pour en donner une démonstration rigoureuse, il convient évidemment de formuler tr` es précisément la notion d’algorithme. Il apparaˆ ıt que les possibilités des ordinateurs et des langages de programmation sont parfaitement couvertes par la définition mathématique de ce qui est résoluble algorithmiquement. On est donc en présence d’une première dichotomie, entre problèmes insolubles algorithmiquement et les autres. Parmi les problèmes qui sont algorithmiquement solubles, on peut encore distinguer une hiérarchie en fonction de la complexité des algorithmes, complexité mesurée en temps de calcul, c’est-à-dire en nombre d’opérations élémentaires, et exprimée en fonction de la taille du problème. La taille elle-même est un paramètre qui mesure le nombre de caractères nécessaires pour décrire une donnée du problème. Pour une matrice carrée à coefficients bornés par exemple, son ordre est un bon paramètre de la taille; pour un polynˆome, le degré peut être une indication de la taille, sauf si l’on sait par exemple que le polynˆome n’a que tr` es peu de coefficients non nuls, auquel cas le nombre de coefficients non nuls est un meilleur indicateur. Le temps de calcul d’un algorithme croˆ ıt en général en fonction de la taille des données, et la vitesse de la croissance est une mesure de la complexité du problème. Une croissance exponentielle ou plus rend un problème intraitable pour des données de grande taille. Même une croissance polynomiale, disons comme une puissance cinquième de la taille des données, rend la résolution pratiquement impossible pour des données d’une certaine taille. Evidemment, il existe de tr` es nombreux problèmes pour lesquels tout algorithme a une croissance au moins exponentielle. Dans cette catégorie, on trouve les algorithmes dont le résultat lui-même est constitué d’un nombre exponentiel ou plus de données. Par exemple, la génération de toutes les permutations de n éléments prend un temps plus qu’exponentiel, simplement parce qu’il y a n! permutations. Il existe toute une classe de problèmes, qui sont des problèmes d’optimisation combinatoire, o` u l’on cherche une solution optimale parmi un nombre exponentiel de solutions réalisables. Une bonne stratégie, si elle existe, permet de trouver une solution optimale sans énumérer l’ensemble des solutions réalisables; on peut alors résoudre le problème en temps disons polynomial. Bien entendu, on ne connaˆ ıt pas toujours une telle stratégie; mais on ne sait pas à l’heure actuelle si, pour tout problème de ce type, il existe un algorithme polynomial. La conjecture la plus problable est qu’un tr` es grand nombre de problèmes de ce type ne puissent pas ˆ etre résolus par un algorithme polynomial. On aurait ainsi une deuxième division des problèmes, entre ceux qui sont solubles, mais intraitables, et les autres, pour lesquels il existe des algorithmes efficaces. L’un des objectifs de l’algorithmique est l’étude de ces problèmes, pour lesquels on cherche les algorithmes les plus efficaces, tant du point de vue du temps de calcul que des besoins en place.

Sur la présentation d’algorithmes

Pour présenter les algorithmes de manière formelle, nous utilisons dans ce livre un langage proche de Pascal. Toutefois, en vue de ne pas alourdir inutilement la lecture, nous n’en suivons pas strictement la syntaxe; de plus, nous introduisons quelques ellipses, et quelques variantes sur les structures de contrˆole. La plupart parlent d’elles-mêmes.Ainsi, pour économiser l’écriture de parenthèses (début,fin), nous utilisons les mots finsi, finpour, et fintantque comme délimiteurs de portée, lorsqu’un tel délimiteur est utile. Nous écrivons donc : si test alors suite d’instructions sinon suite d’instructions finsi tantque test faire suite d’instructions fintantque pour ··· faire suite d’instructions finpourD’autres variantes concernent la structure de contrˆole. Ainsi, retourner, et plus rarement exit provoque (comme en C) la sortie de la procédure ou fonction courante, et le retour vers la procédure appelante.Enfin, nous utilisons largement la version séquentielle des opérateurs booléens et et ou (comme en Modula), baptisés etalors et oualors. Dans l’évaluation d’une expression de la forme a etalors b, on évalue d’abord a, et on n’évalue b que si a est vrai. Le même mécanisme vaut mutatis mutandis pour oualors. On économise ainsi beaucoup de programmation confuse.