Si nous cherchons le mot algorithme dans le Petit Larousse nous trouvons la définition suivante : ” processus de calcul permettant d’arriver à un résultat final déterminé”. Le mot calcul doit être pris au sens large : tout ce que la machine ou la personne qui va devoir appliquer l’algorithme, est capable de faire de manière automatique (c’est-à-dire sans réflexion). L’expression principale est ici ”résultat final déterminé” : pourvu que l’algorithme soit exact, il conduit de manière certaine et en un temps fini au résultat escompté.
Une recette de cuisine est un algorithme : elle conduit (du moins en théorie) à un résultat certain pourvu que la cuisinière soit capable d’effectuer chacune des opérations élémentaires décrites dans la recette : casser un oeuf, mélanger la farine et le sucre, etc.
La méthode traditionnelle de multiplication de nombres de plusieurs chiffres est un algorithme : cette méthode conduit au bon résultat de manière certaine pourvu que l’exécutant connaisse les tables de multiplications pour tous les nombres de 1 à 9 et sache faire des additions.
Tout algorithme a des ingrédients (les produits alimentaires pour une recette de cuisine, chiffres pour la multiplication), une entrée (oeuf, farine, sucre et fruits pour la recette, les deux nombres à multiplier pour la multiplication), une sortie (la tarte pour la recette de cuisine, le résultat pour la multiplication) et des étapes ou sous-algorithmes (faire la pâte, garnir la pâte, faire cuire la tarte pour la recette de cuisine, multiplier le nombre du haut par chacun des chiffres du bas puis additionner tous les résultats pour la multiplication).
Notre but va donc être d’ expliquer à une machine qui au départ ne sait faire qu’un nombre d’opérations limité (opérations arithmétiques sur les nombres entiers ou réels, manipulations élémentaires de mots ou de caractères) ou à une personne sans connaissance préalable, effectuant sans discuter les ordres donnés dans la mesure de ses capacités, comment aboutir à des résultats complexes (brochet au beurre blanc, PGCD, polynômes, matrices, suites, fonctions, roman, texte scientifique, etc) ; pour cela, nous lui indiquerons toutes les étapes nécessaires.
Au passage, il faudra nous intéresser à la performance des algorithmes : combien de temps un algorithme met-il pour s’effectuer ? Entre une recette de cuisine qui prend un quart-d’heure et une recette de cuisine qui prend trois heures pour arriver au même résultat gustatif et diététique, laquelle doit-on préférer ?
La première structure fondamentale d’un algorithme est la séquence d’opérations. On effectue une première opération, puis une deuxième opération, puis une troisième opération, et ainsi de suite sans se poser de question. C’est ainsi que pour faire cuire un poisson au court-bouillon, on pourra écrire la séquence
Cette approche séquentielle des algorithmes a des limites évidentes : elle ne tient aucun compte de circonstances particulières et elle est incapable de s’adapter à des environnements différents. C’est ainsi que l’opération allumer la plaque doit se dérouler de manière tout à fait différente suivant que l’utilisateur de la recette dispose d’une cuisinière électrique ou d’une cuisinière à gaz. Si l’on veut que notre méthode s’adapte aux deux types d’utilisateurs, il va nous falloir introduire une structure conditionnelle à l’aide du mot SI. De cette manière, l’opération allumer la plaque pourra être détaillée en
En fait notre algorithme destiné à faire cuire notre poisson souffre encore de plusieurs insuffisances évidentes : il ne nous indique pas le réglage du bouton de la cuisinière (peut être ne faut-il pas brutaliser notre poisson par une hausse trop rapide de la température), il ne nous dit pas qu’il faudra baisser le feu dès que l’eau frémira (poisson bouillu, poisson foutu) et il ne nous indique pas le temps de cuisson. Ceci ni la structure séquentielle, ni la structure conditionnelle ne sont capables de le faire. Nous avons besoin pour effectuer ces diverses opérations de structures répétitives qui nous permettent d’effectuer une opération soit un certain nombre de fois (tourner par exemple le bouton de la plaque de 6 crans vers la droite pour atteindre le thermostat 6, attendre 10 fois une minute pour laisser cuire 10 minutes), soit jusqu’à ce qu’une certaine condition soit vérifiée (l’eau frémit). On distinguera donc les structures répétitives conditionnelles et les structures répétitives inconditionnelles.
L’algorithme de cuisson de notre poisson deviendra alors
Remarquons bien entendu que l’introduction d’un compteur (par exemple une minuterie pour l’attente des 10 minutes), permet de remplacer une structure répétitive inconditionnelle par une structure répétitive conditionnelle, c’est à dire de remplacer l’instruction attendre 10 fois une minute par attendre jusqu’à ce que la minuterie sonne. Par contre, il n’est pas question de remplacer en sens inverse une structure répétitive conditionnelle par une structure répétitive inconditionnelle : nul ne peut prévoir à l’avance combien de temps il faudra attendre jusqu’à ce que l’eau frémisse, cela dépend de la capacité de la casserole, de la température initiale de l’eau, de la puissance de la plaque.
La thèse de Church-Turing assure que tout algorithme peut être décrit à l’aide de ces trois structures : la séquence, la condition, la répétition conditionnelle. Autrement dit tout langage de description d’algorithme (et donc tout langage de programmation algorithmique) doit contenir ces trois structures et peut ne contenir qu’elles. Le langage de programmation retenu dans cet ouvrage (le langage Caml) est un parfait exemple de cette thèse.
Vous trouverez chez votre marchand de journaux habituel toute une gamme d’encyclopédies vendues au numéro dont le but avoué est de permettre à tout-un-chacun de passer pour un grand cuisinier, un spécialiste de la plomberie ou un jardinier-paysagiste, sans aucune connaissance préalable. La méthode utilisée est toujours la même : décomposer tout problème en (un grand nombre de) petits problèmes tout à fait élémentaires que toute personne sensée doit être capable de résoudre.
C’est ce qu’on appelle la méthode d’analyse descendante. On procède par raffinements successifs en partant d’un problème complexe que l’on décompose en sous-problèmes moins compliqués. On décompose alors ces problèmes en sous-problèmes de plus en plus simples, jusqu’à parvenir à des problèmes tellement élémentaires que la solution en est évidente.
Imaginons par exemple que dans une encyclopédie culinaire, nous voulions expliquer la recette du brochet au beurre blanc. Une première approche (de haut niveau) de notre recette est d’écrire
Cette recette s’adresse à un spécialiste de la cuisine qui sait faire cuire le poisson et faire un beurre blanc. Si nous voulons nous adresser simplement à un cuisinier expérimenté nous détaillerons chacune des opérations de la manière suivante
Pour un cuisinier débutant, nous serons amenés à détailler encore plus certaines opérations, par exemple en ce qui concerne la réduction d’échalotes
Si maintenant, nous nous adressons à un enfant qui fait pour la première fois la cuisine, nous devrons encore détailler certaines opérations : comment allumer et régler les plaques de cuisson, comment régler la minuterie, comment éplucher les échalotes sans trop pleurer, comment se servir du hachoir sans y laisser un doigt.
Si enfin, nous nous adressons à un robot ou à un ordinateur (le mien est maintenant un spécialiste du brochet au beurre blanc, mais ce fut très dur), il nous faudra encore détailler toutes les opérations : comment mettre le poisson à l’eau froide, comment baisser le feu, comment remuer au fouet. Nous décomposerons chaque opération en opérations tellement élémentaires qu’elles seront toutes à sa portée.
Cette méthode d’analyse descendante est une des techniques fondamentales de l’algorithmique. Elle demande un grand esprit d’analyse pour décomposer un problème en problèmes plus simples : certains cuisiniers de génie sont totalement incapables d’expliquer une de leurs recettes de même que certains grands chercheurs font des enseignants déplorables. Cette méthode demande aussi une bonne connaissance des capacités du public visé (ou du langage algorithmique utilisé) pour savoir jusqu’à quel point il est nécessaire de pousser la subdivision des problèmes : un livre de recettes sera complètement différent suivant qu’il s’adresse à des cuisiniers de restaurants, des cuisiniers expérimentés ou des cuisiniers débutants ; de la même façon, suivant qu’un algorithme informatique est destiné à être implémenté dans un langage de bas niveau comme l’assembleur ou dans un langage de très haut niveau comme un langage de requête pour une base de données, le niveau de raffinement de l’algorithme sera tout à fait différent.
Un autre avantage de la méthode d’analyse descendante découle de la modularité à laquelle celle-ci conduit naturellement. On est amené à décomposer une tâche en tâches beaucoup plus élémentaires ; mais il est clair qu’inversement, ces tâches élémentaires pourront le plus souvent servir à bien d’autre chose que le problème initial que l’on cherchait à résoudre.
C’est ainsi que si nous reprenons l’exemple de notre recette du brochet au beurre blanc, les modules que nous avons construits pourront servir dans d’autres recettes : le beurre blanc s’accommodera très bien de coquilles Saint-Jacques, la cuisson du brochet au court-bouillon pourra s’adapter à bien d’autres recettes.
La réutilisabilité des modules est un objectif qui doit être poursuivi le plus souvent possible en algorithmique : les efforts d’aujourd’hui doivent être encore utiles pour les tâches de demain, les problèmes d’aujourd’hui doivent être simplifiés par les travaux d’hier.
Pour illustrer notre propos, nous allons partir d’un problème relativement complexe, la résolution d’un système de Cramer par la méthode d’élimination, ou méthode du pivot de Gauss.
Rappelons d’abord ce dont il s’agit. Nous partons d’un système de n équations à n inconnues x1,…,xn qui peut s’écrire (1)
qui se résout de manière évidente à partir du bas : la dernière équation permet de calculer xn , on reporte alors dans les précédentes et ainsi de suite.
Pour passer du système général (1) au système triangulaire (2) on procède de la manière suivante. On choisit une équation telle que le coefficient de x1 (le pivot) soit non nul. On porte cette équation en première position. Alors en soustrayant à chacune des équations suivantes la première multipliée par un certain facteur (à savoir le quotient du coefficient de x1 dans l’équation par le pivot choisi) on éliminera x1 de toutes les équations à partir de la deuxième. Il suffira alors de recommencer avec x2 dans les n - 1 dernières équations et ainsi de suite pour aboutir au système (2).
Pour que l’algorithme fonctionne, il faut bien entendu que l’on puisse à chaque étape trouver un pivot non nul (c’est le cas si l’on a effectivement un système de Cramer). En fait on constate que, puisque l’on doit diviser par le pivot, il est préférable, pour minimiser les erreurs de calcul, de choisir le pivot le plus grand possible en valeur absolue.
Donnons un exemple (on a à chaque étape encadré le pivot choisi)
On élimine la première inconnue dans la seconde et la troisième équation
On permute les équations et on obtient
on élimine la seconde inconnue de la troisième équation
qui se résout facilement en x3 = 0, x2 = -1 puis x1 = 2.
Faisons une première analyse du problème en introduisant les matrices A = (aij)1≤i,j≤n et B = (bi)1≤i≤n.
Nous distinguons quatre grandes étapes dans notre méthode. L’ordinateur ne sait effectuer de lui même aucune de ces étapes. Fractionnons encore les problèmes
Bien que le problème soit nettement décomposé, la machine ne sait encore effectuer aucune de ces étapes, il faut encore lui détailler les opérations. Continuons donc notre analyse.
Remarque dans toute la suite nous noterons ← pour l’expression ”mettre dans le terme de gauche la valeur du terme de droite”. C’est ainsi que x ← 2 signifiera ”mettre dans x la valeur 2” , x ← y signifiera ”mettre dans x la valeur de y”.
Certaines des étapes deviennent ici suffisamment simples pour être effectuées par l’ordinateur. Entrer est simplement une lecture au clavier, sortir est simplement un affichage sur écran ; dans les deux cas il s’agit de nombres réels, et tout langage de programmation évolué est capable d’effectuer ces instructions. Les autres étapes sont encore trop complexes pour pouvoir être effectuées. Détaillons les de nouveau. Pour chercher un pivot maximum nous parcourons toute la i-ième colonne à partir de la i-ième ligne en retenant dans ’maximum’ la valeur maximum rencontrée jusqu’à un instant donné et dans ’ligne’, le numéro de la ligne dans laquelle ce candidat au pivot a été rencontré.
Remarque les phrases entre accolades ne font pas partie de l’algorithme, elles sont seulement là pour expliquer au lecteur pourquoi on travaille ainsi. Ce sont des commentaires.
Il ne reste plus qu’à détailler les derniers points encore trop complexes.
Notre analyse est achevée puisque nous travaillerons dans un langage qui est capable de faire toutes les opérations élémentaires (somme et produit de nombres réels, faire varier un indice dans un intervalle, exécuter une instruction si une condition est vérifiée et une autre sinon) dont nous avons besoin à ce stade. En assembleur, il faudrait continuer notre analyse pour expliquer à la machine comment additionner, multiplier ou diviser des nombres réels, faire varier un indice, tester une condition et exécuter des instructions différentes suivant que la condition est vérifiée ou non.
Ceci nous a permis au passage de voir certaines structures essentielles de beaucoup de langages de programmation