Les ingrédients des algorithmes

 1. Des ingrédients à découvrir

Quelle différence entre une machine à café et un ordinateur ?

Un ordinateur peut effectuer des opérations très variées, sur des types de données très variés : des nombres, des lettres, des images, des sons, des textes, des vidéos, comme le montre le document Tout a un reflet numérique. Il peut être utilisé pour retoucher une photo, la mettre sur un blog ou un site web, la conserver dans un album… Un ordinateur est une machine polyvalente : tout ce qui s’automatise peut être programmé sur un ordinateur. À l’inverse des machines à café ou des aspirateurs, qui ne servent qu’à une seule chose : faire le café ou aspirer la poussière.

© Dessin : Paul Gendrot

Dès la sortie de l’usine, une machine à café est capable de faire le café, un aspirateur est capable d’aspirer la poussière. En revanche, un ordinateur ne « sait » quasiment rien faire. Il doit « être programmé » pour retoucher une photo, la mettre sur un blog ou un site web.

C’est pour cela que les ordinateurs ont besoin de programmes. Cette notion de programme est également ce qui distingue l’ordinateur de certaines machines comme la plupart des calculatrices par exemple, qui donnent une illusion de polyvalence dans la mesure où elles peuvent effectuer des opérations variées, mais sont non programmables. En effet, les tâches qu’effectue une telle calculatrice sont fixées une fois pour toutes : par exemple, on ne peut pas utiliser une calculatrice pour lire une vidéo, alors qu’inversement sur un ordinateur on peut utiliser un programme qui effectue tout ce que permet une calculatrice. Certaines calculatrices puissantes sont toutefois programmables et sont donc des ordinateurs miniatures.

Oui, mais comment fait-on pour programmer l’ordinateur ? Le plus important est de bien spécifier ce que l’on cherche à faire. Ce qui compte ici, c’est la méthode mise en œuvre, l’algorithme. Il faut ensuite l’écrire sous forme de programme, de façon à le transmettre à l’ordinateur. C’est pour cela qu’on utilise un langage de programmation.

Les documents Algorithmes, mode d’emploi et Demandez le programme offrent une introduction à ce sujet.

Algorithme… une recette de cuisine ?

On appelle algorithme la méthode, la façon systématique de procéder pour faire quelque chose : trier des objets, situer des villes sur une carte, multiplier deux nombres, extraire une racine carrée, chercher un mot dans le dictionnaire… Il se trouve que certaines actions mécaniques – peut-être toutes ! – se prêtent bien à cette décortication.

On peut les décrire de manière générale, identifier des procédures, des suites d’actions ou de manipulations précises à accomplir séquentiellement. C’est cela, un algorithme : le concept qui traduit la notion intuitive de procédé systématique, applicable mécaniquement, sans réfléchir, en suivant un mode d’emploi précis.

Un algorithme c’est donc « presque » comme une recette de cuisine. Attention, nous disons bien « presque ». Prenons un exemple : le quatre-quarts au citron ou au chocolat, un gâteau que tout le monde peut réussir. Il suffit de prendre deux œufs, le même poids de farine, de beurre et de sucre, ajouter le parfum, mélanger le tout et mettre au four une petite demi-heure, facile, non ?

Oui, mais… que se passerait-il si nous confiions cette recette à un dispositif mécanique dépourvu d’intelligence (robot, ordinateur, automate…) ? Eh bien, il réaliserait notre recette, exactement comme nous venons de le spécifier. Mais alors :

• Vas-y de mélanger les œufs avec le reste, ah ben oui, les œufs… avec leurs coquilles, qui a dit de les enlever ?
• Une « petite » demi-heure dans le four ? Petite ? Euh… voilà notre dispositif mécanique bloqué : petite ? Par rapport à quoi ? De combien ?
• Sans compter que personne n’a précisé de l’allumer, ce four, ni d’ailleurs de verser le mélange dans un moule !

En résumé, toute instruction ambiguë, incomplètement spécifiée, va échouer.

Disons alors qu’un algorithme c’est bien une recette de cuisine… mais alors, pire que pour Monsieur ou Madame Tout-le-monde, c’est une recette à définir, à spécifier, pour un inculte complet. En clair, un dispositif mécanique n’a aucune information contextuelle, aucune connaissance préalable, aucun de ces éléments qui font la richesse de notre intelligence humaine. Il faut donc que chaque étape soit entièrement et explicitement spécifiée, dans ses moindres détails.

De retour en cuisine

Retournons dans la cuisine. Nous voilà plus prudents. Nous allons donner à exécuter à notre machine la séquence de toutes les opérations (par exemple : ouvrir le vaisselier, sortir le grand compotier, ouvrir le frigo, compartiment supérieur de la porte, sortir le beurre, ouvrir le placard, 3^e étagère à droite, prendre la farine, etc.) Notre algorithme est donc un chemin à parcourir pas à pas, une séquence d’instructions.

Pour peu que chaque instruction, comme « ouvrir le frigo », ait été bien définie, bien « programmée » précédemment, nous commençons à voir apparaître la pâte du gâteau.

Euh… à condition que tout se passe exactement comme prévu ! Que faire si le compotier n’est pas à sa place, ou s’il ne reste plus de beurre ? « S’il n’y a plus de beurre, il suffit de prendre de la margarine, sinon il vaut mieux arrêter de faire le gâteau. » Bien.

Voilà que notre recette n’est plus une simple séquence d’instructions, ce n’est plus un simple chemin, mais un itinéraire avec des « carrefours », où le choix du chemin se fait en fonction d’une condition (pas de beurre, ou ni beurre ni margarine). Notre algorithme est donc un réseau d’instructions conditionnelles, à parcourir pas à pas, en bifurquant à chaque condition.

Notre quatre-quarts est en bonne voie, « prenons la cuillère et tournons les ingrédients dans le compotier, tournons les ingrédients dans le compotier, tournons les ingrédients dans le compotier, tournons les ingrédients dans le compotier, tournons les ingrédients dans le compotier, tournons les ingrédients dans le compotier, tournons les ingrédients dans le compotier, tourn… » Ah mince ! Comment expliquer qu’il faut tourner une bonne trentaine fois les ingrédients dans le compotier, sans devoir recopier une bonne trentaine de fois l’instruction ? D’autant plus que le but n’est pas de tourner trente fois, mais plutôt de tourner jusqu’à ce que la pâte soit bien homogène.

Nous avons alors besoin d’une autre construction, une boucle de la forme « tant que la pâte n’est pas bien homogène, tourner les ingrédients dans le compotier ». Avec cette boucle d’instruction, nous avons la possibilité de faire durer ou répéter une opération autant de fois que nécessaire. De même, nous pouvons écrire « cuire au four tant que la pâte reste liquide », ou « fabriquer 200 quatre-quarts pour tout le quartier », en l’exprimant de manière concise.

Enfin, nous voilà avec un quatre-quarts… au citron, ou bien au chocolat, ou encore à la vanille. Va-t-il donc falloir réécrire la recette complète pour chaque parfum ? Alors que seule l’étape « ajouter trois zestes de citron » ou « ajouter 50 grammes de poudre de chocolat » ou « ajouter 50 grammes de ketchup »… change d’une recette à l’autre ? Certes pas, mais pour l’éviter nous avons besoin d’introduire la notion de variable ou de paramètre. La recette doit être paramétrée par la variable « parfum » et en fonction de sa valeur (« citron », « chocolat »…), une instruction conditionnelle changera juste la ligne de la recette liée au parfum.

Nous obtenons ainsi, exprimée de manière concise, la recette de tous les quatre-quarts possibles, qui ne diffèrent que par leur parfum.

À présent, prenons un peu de recul. Nous avons utilisé des instructions comme « ouvrir le frigo » ou « tourner les ingrédients dans le compotier », qui ont sûrement dû être programmées par quelqu’un d’autre, et nous avons produit l’instruction « faire un quatre-quarts au goût de $parfum » (le signe $ indique qu’il s’agit d’une variable) où « $parfum » prend la valeur « citron » ou « chocolat ». Bref, nous avons utilisé des fonctionnalités prédéfinies, des « briques de base » pour créer une autre fonctionnalité, qui pourra à son tour être utilisée par quelqu’un qui prépare un autre menu (par exemple, « faire un quatre-quarts au ketchup », « faire de la viande aux patates »).

Cette dernière construction, qui consiste à regrouper un bloc d’instructions dans une fonction, va nous permettre de réutiliser différentes fonctionnalités, comme les briques d’un jeu de Lego, pour réaliser une construction logicielle.

N’oublions pas toutefois une autre différence importante entre les recettes de cuisine et les programmes, c’est que les programmes sont destinés à être lus, non seulement par des humains, mais aussi par des ordinateurs chargés de les exécuter, ce qui demande que ces programmes soient écrits dans des langages très particuliers : les langages de programmation.

Mais la bonne nouvelle à retenir, c’est que ces cinq ingrédients suffisent pour décrire tous les algorithmes. Par conséquent, il suffit d’avoir ces cinq ingrédients sous la main pour se lancer dans la programmation !

Commencer à programmer

En prolongement de cette présentation, nous vous proposons de vous initier concrètement à la programmation en découvrant comment utiliser chacun des cinq ingrédients des algorithmes.

Il existe de nombreux langages de programmation (C, C++ , Java, Caml, Prolog, Basic…). Cette initiation utilise Java’sCool, une forme simplifiée du langage Java. Cependant, elle ne fait appel à aucune particularité de ce langage, et les programmes que nous écrirons pourront être traduits sans peine dans un autre langage.

Les tutoriels de Java’sCool vous conduisent pas à pas à :

• définir des séquences d’instructions,
• vous servir de variables,
• découvrir l’instruction conditionnelle,
• vous familiariser avec les fonctions,
• utiliser des boucles.

Il reste toutefois encore bien des questions : Que se passe-t-il si on se trompe ? Comment savoir si on se trompe ? Oui, mais comment être sûr qu’on ne se trompe pas ? Les chercheurs ont des réponses à proposer, mais elles ne sont pas forcément très faciles à aborder. Pour cela, il ne faut pas avoir peur de tourner la page, et entrer dans leur « cuisine » mathématique pour manipuler les ingrédients des algorithmes.

2. Des ingrédients à manipuler

Que se passe-t-il en cas d’erreur ?

Reprenons notre « recette de cuisine », que se passe-t-il si on se trompe un tout petit peu ? Pour le gâteau, eh bien, il sera un peu trop mou ou un peu trop sucré, mais pour un algorithme, ce sera très probablement un tout petit peu… beaucoup… la catastrophe absolue !

Voici un exemple d’algorithme qui vous en donnera une idée. Il s’agit de calculer la factorielle d’un nombre n (ici comme souvent dans les notations informatiques, les instructions se placent entre des accolades et se terminent par un point-virgule, * représente la multiplication) :

factorielle(entier n) {
  si (n = 0) {
    renvoyer 1;
  } sinon {
    renvoyer n * factorielle(n - 1);
  }
}

Cette formule sert bien à calculer la factorielle, puisqu’elle implémente la définition par récurrence de la factorielle, telle qu’elle est présentée dans nos manuels scolaires, à savoir que :
factorielle(0) = 1 et factorielle(n) = n * factorielle(n – 1)

Donc si n = 0, le résultat renvoyé est 1, sinon le résultat renvoyé est calculé selon la formule de droite.

Avec les ingrédients précédents, on peut proposer une autre implémentation équivalente. Nous pouvons noter f la variable intermédiaire qui va prendre les valeurs du calcul, et écrire le code suivant :

factorielle(entier n) {
entier f = 1;        
  tantque (n n'est pas nul)  { 
      f = f * n;
      n = n - 1;
  }
renvoyer f 
}

Cette méthode va bien calculer :
factorielle(n) = n * (n-1) * etc. * 1
donc exactement la factorielle que nous connaissons, ceci en s’arrêtant lorsque n = 0, ce qui semble parfait.

D’ailleurs, c’est vraiment parfait ! Si si, tant que… tant que n est positif. Ah oui : si n est négatif, alors c’est dommage, parce que voilà l’un ou l’autre code se mettre à calculer factorielle(n) pour les valeurs suivantes, en partant de n = -1 :
n = -1, -2, -3, -4, etc., -beaucoup, …, -à-la-folie, …, -sans-s’arrêter-du-tout !

C’est alors au hasard des choses de décider de ce qui arrive : ordinateur bloqué, calcul qui dure jusqu’à ce que les piles soient vidées, etc.

Bienvenue devant ce qui s’appelle un bug. En effet, la fonction factorielle n’est que partiellement définie : pour n ≥ 0 tout est bien spécifié, mais pour n < 0 rien n’est dit. L’élève reçoit un 0 à sa copie s’il commet une telle étourderie, et le programme informatique, lui, boucle à l’infini. Dans ce cas précis, il y a plusieurs parades possibles, par exemple :

1. vérifier que n ≥ 0 avant de lancer le calcul, ou bien
2. modifier le code en écrivant :
   factorielle(entier n) : si n ≤ 0 alors renvoyer 1, sinon renvoyer n * factorielle(n – 1)
   Cette formule renvoie la valeur 1 pour tous les entiers n négatifs ou nul : en un sens, il s’agit d’étendre la fonction factorielle aux nombres négatifs.

Au-delà de cet exemple, comme nous l’explique Gérard Berry dans son cours au Collège de France sur les sciences numériques (disponible en vidéo), tout comme l’enseigne Gilles Dowek dans son cours d’informatique pour des professeurs de mathématiques de lycée (également en vidéo, avec transparents), il existe des méthodes formelles qui adoptent une méthodologie plus proche des mathématiques. Elles permettent ainsi d’effectuer de nombreux calculs sur ces programmes, devenus à leur tour l’objet de manipulations informatiques.

Une technique fondamentale, nommée interprétation abstraite, développée à l’Ecole normale supérieure par l’équipe de Patrick Cousot, permet de détecter automatiquement des bugs, comme celui d’Ariane, identifié par Gilles Kahn : lorsque le premier vol d’Ariane 5 en 1996 a explosé et détruit pour 500 millions de dollars de satellites, la faute était due à un morceau de programme qui convertissait une valeur. Créé pour Ariane 4, il a été réutilisé tel quel. Or la valeur à convertir, beaucoup plus grande dans le cas d’Ariane 5, a donné un résultat aberrant et des ordres de braquage maximum…

Et surtout, cette technique permet d’éviter que de tels bugs se produisent ; elle a été appliquée avec succès sur les logiciels de vol de l’Airbus A380.

D’autres techniques permettent d’aller jusqu’à la vérification mathématique de propriétés dites de sûreté, comme « l’ascenseur ne pourra jamais voyager la porte ouverte », ou de vivacité, comme « l’ascenseur finira par prendre tous les passagers qui l’attendent ». De telles vérifications formelles se font en calculant symboliquement le gigantesque ensemble des exécutions possibles, sans les effectuer explicitement.

Les méthodes formelles, que nous allons évoquer, permettent ainsi de diminuer sensiblement le nombre de bugs dès la conception, puis de trouver des bugs particulièrement sournois, hors de portée des tests manuels ou aléatoires. Même si elles ne suffiront pas à elles seules à assurer la sécurité requise pour tous les logiciels du commerce, à cause de leur taille et de leur nombre grandissants, puisque le problème est identifié comme étant indécidable mécaniquement.

Il s’agit donc d’exécuter des algorithmes, de vérification et de preuve, sur des données que sont les algorithmes à vérifier ou à prouver. Il est de ce fait nécessaire que ces derniers puissent être exprimés sous une forme interprétable sans ambiguïté. Comment donc définir formellement nos ingrédients ?

© Dessin : Paul Gendrot

De l’algorithme au programme… une notation rigoureuse ?

Les différents langages de programmation sont organisés autour d’un petit nombre de fonctionnalités, présentes dans de nombreux langages, relativement stables depuis des décennies, et que l’on peut décrire simplement avec les outils adéquats (affectation, séquence, test, boucle, fonction, récursivité, enregistrement, cellule, module, objet…). Et le noyau de la plupart des langages est justement constitué des cinq ingrédients que nous détaillons ici.