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.
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 Algorithme 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, 3e é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.
Français