Les Newsletters Interstices
Photo Steve Buissinne via Pixabay, CC0
    Niveau intermédiaire
    Niveau 2 : Intermédiaire

    Les ingrédients des algorithmes

    Algorithmes
    Culture & Société
    Pour programmer un ordinateur, le plus important ce sont les méthodes mises en œuvre. Découvrez les ingrédients à combiner pour créer ces 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, 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 à :

    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.

    Nous parlons ici de programmation impérative, c’est à dire un paradigme qui décrit les opérations en termes de séquences d’instructions exécutées par l’ordinateur pour modifier l’état du programme. Bien d’ autres paradigmes existent, mais ils sont tous, soit dérivés de la programmation impérative, soit nécessitent d’avoir tout d’abord bien compris celle-ci pour les appréhender.

    Pour chacune de ces fonctionnalités, nous allons décrire :

    • Sa syntaxe : la manière dont cette instruction s’écrit. Ne perdons pas de vue que la question importante est de savoir de quoi est constituée cette instruction, quels sont ses paramètres, etc. Le fait de savoir comment cela s’écrit dans le langage particulier que l’on utilise est accessoire. De même que lorsqu’on apprend à conduire une voiture, ce qui est important est de savoir ce que frein, levier de vitesse, etc. signifie et comment s’en servir ; que ces commandes aient tel ou tel aspect sur une Twingo ou une Mercedes, est accessoire.
    • Sa sémantique : ce qui se passe quand on l’exécute. Détaillons ce point.

    Sémantique d’un programme : définir l’effet d’une instruction

    Ce que fait une instruction ou un groupe d’instruction, c’est transformer un état, c’est-à-dire la valeur de chacune de ses variables.

    L’état indique donc la valeur de chaque variable à un instant donné. Par exemple, si le programme a trois variables x, y, z qui représentent trois « boîtes » dans lesquelles nous pouvons ranger des valeurs, une instruction va modifier les valeurs de ces boîtes lors de son exécution. De modification en modification, un programme fera passer l’état de sa valeur initiale à sa valeur finale.

    Un programme a bien sûr des entrées et des sorties, ce sont des boîtes particulières : les sorties sont des boîtes dont les valeurs sont visibles d’un dispositif externe, les entrées sont des variables dont les valeurs ont été prédéfinies par l’utilisateur ou un dispositif externe.

    Si les entrées du programme ne sont définies qu’une seule fois, alors elles peuvent être vues comme des variables dont les valeurs ont été prédéfinies par l’utilisateur ou un dispositif externe.

    Si les entrées du programme sont lues plusieurs fois au cours de l’exécution du programme, alors il faut considérer chaque lecture de l’entrée comme une variable différente. Le modèle à utiliser lorsque entrées et sorties changent tout le temps, c’est-à-dire lorsque le programme est enfoui dans un environnement qui interagit en permanence avec lui est différent, il faut utiliser un paradigme de programmation dit réactif, comme pour le langage Esterel.

    Pour formaliser la sémantique d’une instruction, nous avons l’habitude d’utiliser des notations mathématiques, que les informaticiens et les logiciens trouvent bien pratiques, car elles ont l’avantage d’être concises et sans ambiguïté. Nous vous les présentons ci-dessous, mais si elles ne vous plaisent pas, ne vous inquiétez pas, nous en donnons toujours une explication en mots :

    • L’état est représenté par une liste d’équations [x = 12, y = "Hi", z = 0] qui donnent la valeur des variables.
    • Pour une instruction p, la construction ∑(p, s) = s' signifie qu’elle transforme un état s en un état s'.

    Nous sommes maintenant en mesure de détailler chacun de nos ingrédients, chacune des instructions, en faisant appel à ces notations mathématiques.

    Affectation d’une valeur à une variable

    La première action est de donner des valeurs aux variables : c’est l’affectation.

    Manière d’écrire l’instruction

    • L’affectation est constituée d’une variable x et d’une valeur v.
    • Selon les langages, elle s’écrit x = v, x := v, x = v;, x , etc., par exemple x = 15.
    • Informellement : la variable x prend comme valeur v ; sa valeur précédente est effacée ; elle gardera toujours la valeur v tant qu’elle ne sera pas changée par une autre affectation de la variable x.

    L’affectation est donc une « action » : celle d’affecter à la variable x la valeur v.

    Il faut aussi bien distinguer l’affectation de l’égalité (souvent notée par un double signe ==). Écrire x == 15 revient à poser la question « est-ce que x est égal à 15 ? » x == 15 est vrai si x est égal à 15, faux sinon. Écrire x = 15 revient à donner l’ordre que « désormais x sera égal à 15 ! »

    Sens de l’instruction

    Il est facile de comprendre ce que fait cette instruction, elle change l’état en lui ajoutant le fait que désormais x = v. Avec nos notations mathématiques, nous pouvons le noter ainsi : ∑(x = v, s) = s + [x = v] Cela signifie qu’on ajoute à l’état la nouvelle équation qui définit la valeur de la variable affectée.

    Expressions et fonctions

    La valeur que nous donnons à une variable n’est pas forcément une constante, car nous voulons aussi évaluer des expressions : écrire par exemple x = 12 + z / 2 pour calculer x à partir de z.

    Manière d’écrire une expression

    • Une expression numérique (c’est-à-dire qui porte sur des nombres) se construit comme sur une calculette, avec des additions  + (par exemple 2 + 3), des soustractions -, des multiplications (en utilisant le symbole *) et des divisions (en utilisant le symbole /). Il y a d’autres symboles algébriques que nous n’utiliserons pas ici : il suffit de retenir que cela s’écrit comme pour une calculette.

    Par exemple, si nous écrivons 2 + x / 3 ou (2 + x) / 3, ce ne sont bien sûr pas les mêmes expressions, puisque le calcul se fait différemment selon les parenthèses.

    • Une expression logique (c’est-à-dire qui renvoie la valeur vrai ou faux) se construit avec :
      • Des comparaisons pour tester si deux valeurs sont égales ou non, si une valeur numérique est plus petite qu’une autre, etc.
      • Des opérateurs logiques comme et (souvent noté &&), ou (souvent noté ||), ainsi que la négation (souvent notée !).
    • On peut aussi manipuler des chaînes de caractères, notées entre guillemets, et les concaténer, par exemple "pa" et "py" se concatènent en écrivant "pa" + "py" ce qui donne "papy".
    • Une expression peut faire intervenir des fonctions. Pour appeler une fonction, il suffit de faire suivre son nom de la liste des arguments entre parenthèses. La valeur renvoyée résulte de l’application de la fonction aux valeurs des arguments spécifiées. Ainsi, pour comparer deux chaînes de caractères, il suffit d’appeler la fonction equal : l’expression equal ("pa", "py") vaudra faux, car les deux chaînes de caractères « pa » et « py » ne sont pas égales, tandis que equal("pa", "pa") renverra la valeur vrai, puisque ce sont les mêmes valeurs.

    De nombreuses fonctions sont généralement accessibles, dont les fonctions mathématiques : trigonométriques, logarithmiques, etc. Et surtout, il est possible de définir ses propres fonctions. Pour créer une fonction, il faut spécifier son nom, la liste de ses paramètres et les opérations à effectuer pour calculer sa valeur, en général sous la forme d’une ou plusieurs expressions impliquant ces paramètres.

    Sens d’une expression

    Pour une expression e (par exemple 12 + 6 / 2), nous utilisons une nouvelle notation Θ(e, s) = r pour signifier que la valeur du résultat de son évaluation est r (ici 15).

    Il faut donc bien distinguer une expression (ici, 12 + 6 / 2), une valeur (ici, 15) et une affectation (ici, x = 12 + 6 / 2).

    La valeur d’une expression dépend de l’état, par exemple l’expression 12 + z / 2 dépend de la valeur de z. Avec nos notations mathématiques, cela se note :

    Θ(12 + z / 2, [z = 0]) = 12 ou Θ(12 + z / 2, [z = 6]) = 15

    Nous pouvons alors définir l’affectation d’une expression à une variable, avec ces notations :

    ∑(x = e, s) = s + [x = Θ(e, s)]

    Cela signifie que la variable prend comme valeur le résultat de l’évaluation de l’expression.

    Séquence d’instructions

    Un programme, comme une recette de cuisine, doit indiquer dans quel ordre exécuter les différentes instructions élémentaires. Par exemple, il faut casser les œufs, puis incorporer le sucre. C’est aussi le cas pour un morceau de musique : il faut jouer un ré, puis jouer un do.

    La première construction qui permet d’assembler des instructions élémentaires en un programme est la notion de séquence. La séquence indique qu’il faut exécuter une instruction puis une autre. Pour cela, il suffit de juxtaposer les deux instructions.

    Manière d’écrire une séquence

    • La séquence est constituée de deux instructions p et q.
    • Selon les langages, elle s’écrit {p q}, p ; q, etc. Par exemple, x = 15; z = 2.
    • Informellement : la première instruction est exécutée, ce qui va changer l’état, puis la deuxième instruction est exécutée, ce qui va à nouveau changer l’état.

    Bien entendu, on peut combiner plus de deux instructions, puisque ces instructions peuvent être elles-mêmes des séquences plus ou moins complexes d’instructions.

    Cette combinaison est associative, c’est-à-dire que nous pouvons écrire pour cinq instructions p, q, r, s et t la séquence p ; q ; r ; s ; t.

    Mais attention, on ne peut pas commuter les instructions. Par exemple, p ; q ne donne pas toujours la même chose que q ; p. Prenons un exemple pour le montrer. Avec [x = 0, z = 0], si nous écrivons : x = 15; z = x + 2 nous obtiendrons [x = 15, z = 17], mais si nous écrivons z = x + 2; x = 15 nous obtiendrons [x = 15, z = 2]. Oups, ce n’est pas pareil !!

    Sens de la séquence d’instructions

    Avec nos notations mathématiques, cela se note : ∑(p ; q, s) = ∑(q, ∑(p, s))

    Cela signifie qu’on applique à l’état d’abord l’instruction p , puis l’instruction q.

    Instruction conditionnelle

    Un programme, comme une recette de cuisine (ce serait aussi le cas pour un plan d’action), a besoin d’inclure des tests pour modifier les instructions selon les conditions observées. Par exemple, il faut prendre de la margarine à la place du beurre, si celui-ci vient à manquer. La construction qui permet de faire ces tests s’appelle l’instruction conditionnelle.

    Manière d’écrire l’instruction

    • L’instruction conditionnelle est constituée d’une expression logique t, et de deux instructions p et q.
    • Selon les langages elle s’écrit if (t) p else q, if t then p else q, etc.
    • Informellement : si t a la valeur vraie alors exécuter p, sinon exécuter q.

    Bien entendu, on peut combiner plusieurs tests pour considérer plusieurs options, par exemple la construction if (t) p else if (s) q else r exécutera p si t est vrai, sinon q si s est vrai, sinon r.

    Lorsqu’il n’y a pas d’alternative, on peut omettre le else, par exemple la construction if (t) p exécutera p si t est vrai, sinon il ne se passera rien.

    Et là aussi, chaque instruction peut être elle-même une séquence d’instructions, pouvant éventuellement comprendre d’autres instructions conditionnelles.

    Sens de l’instruction

    Avec nos notations mathématiques, cela se note :
    si Θ(t, s) est vrai ∑(if (t) p else q, s) = ∑(p, s)
    si Θ(t, s) est faux ∑(if (t) p else q, s) = ∑(q, s)

    On applique à l’état soit l’instruction p, soit l’instruction q, selon la valeur prise par t.

    Boucle d’instruction

    Un programme, comme une recette de cuisine ou un plan d’action, a besoin de répéter plusieurs fois une instruction tant que nécessaire. Par exemple, il faut tourner la pâte tant que celle-ci n’est pas bien homogène. La construction qui permet de faire ces tests est la boucle d’instruction.

    Manière d’écrire l’instruction

    • La boucle est constituée d’une expression logique t, et d’une instruction p.
    • Selon les langages, elle s’écrit while (t) p, while t do p, etc.
    • Informellement : tant que t a la valeur vrai alors il faut exécuter p, et réévaluer t pour voir s’il faut recommencer.

    Bien entendu, là encore, l’instruction p peut être elle-même une séquence complexe d’instructions.

    Bien entendu, il existe beaucoup d’autres formes de boucles, qui permettent par exemple d’exécuter une instruction un nombre fixé de fois, etc. Mais toutes ces boucles s’écrivent à partir de cette instruction while.

    Et comme de bien entendu, c’est que les choses se compliquent ! Car nous risquons de créer un programme qui… boucle sans fin et ne s’arrête jamais !

    Sens de l’instruction

    Avec nos notations mathématiques, cela se note… mmm… de manière un peu plus compliquée :

    si Θ(t, s) est vrai ∑(while (t) p, s) = ∑(while (t) p, ∑(p, s))
    si Θ(t, s) est faux ∑(while (t) p, s) = s

    Si la condition est vraie, nous voyons que nous devons recommencer à évaluer la boucle d’instruction sur l’état modifié par p, tandis que si la condition est fausse, rien ne se passe, l’état est inchangé : l’instruction est « vide », c’est un « élément neutre » qui ne change rien.

    Une autre façon de formaliser cette instruction est de la réécrire avec une suite (infinie !) de tests :

    while (t) p = if (t) { p ; if (t) { p ; if (t) { p ; if (t) { p ; if (t) { p ; if (t) { p ; if (t) { p ; ... } } } } } } }

    Chaque fois que le test t est vrai, nous exécutons p, puis refaisons le test…

    Avec ces instructions de boucles, la fonction ∑(p, s) n’est plus une « vraie » fonction, mais une fonction partielle, c’est-à-dire qui n’est pas définie sur les états qui la conduisent à boucler indéfiniment. C’est ce phénomène qui est principalement à l’origine de beaucoup de bugs, et du fait qu’au niveau théorique, l’informatique est très compliquée. Par exemple, beaucoup de problèmes ne sont pas « décidables » automatiquement, car tous les programmes qui donnent une solution sont susceptibles de mettre un temps infini à calculer.

    C’est un problème passionnant et difficile…
    …mais qui ne nous empêchera pas d’écrire des programmes !

    Pour aller plus loin

    Nous voilà donc avec, en main, à la fois les aspects pratiques et théoriques qui nous permettent de programmer « pour de vrai » et de comprendre les abstractions qui correspondent à ces cinq ingrédients de base des algorithmes. Avons-nous ainsi fait le tour de toute la programmation ? Pas tout à fait !

    L’informatique est riche de beaucoup d’autres abstractions, par exemple les classes d’objets qui permettent de définir de manière rigoureuse des objets numériques, et de spécifier quel élément d’un tel objet peut être lu ou modifié, ou quelle action peut être effectuée avec cet objet. D’autres constructions servent, par exemple, à formaliser le fait d’exécuter des calculs en parallèle, ou des mécanismes liés à la communication entre des processus.

    Au-delà de valeurs numériques ou de chaînes de caractères, les structures de données de l’informatique forment un bestiaire presque sans limite : on y trouve des listes, des tableaux, des graphes, des containers correspondant aux images, aux sons, etc.

    Et puis, le paradigme de programmation que nous avons présenté ici, dit « impératif » puisque nous décrivons l’algorithme en donnant explicitement toutes les instructions à exécuter, est sûrement le premier paradigme à découvrir quand on apprend l’informatique, mais n’est pas le seul : on peut aussi décrire l’algorithme de manière plus abstraite, à partir de ses propriétés, ou bien en donnant les paramètres du système dynamique qui va en incarner le fonctionnement.

    Mais nos cinq ingrédients ont tout de même une place spéciale dans cet univers :

    • ils sont universels, au sens où ils permettent bien de programmer tous les algorithmes possibles. Les autres mécanismes seront peut-être plus pratiques, mieux adaptés à une classe de problèmes donnés, mais ils sont eux-mêmes construits directement ou indirectement avec nos ingrédients ;
    • ils nous semblent naturels, puisque nous avons pu les décrire à la fois de manière métaphorique et rigoureuse, et ils sont d’ailleurs à quelques détails près les ingrédients du premier langage informatique structuré proposé par Grace Hopper, qui donnera le langage COBOL (avant cela, il fallait programmer les algorithmes directement en langage machine, c’est-à-dire en spécifiant explicitement ce que devait faire chaque partie du circuit électronique du processeur !).

    Nous avons donc bien le bon trousseau de clés pour commencer à maîtriser l’algorithmique.

    Newsletter

    Le responsable de ce traitement est Inria. En saisissant votre adresse mail, vous consentez à recevoir chaque mois une sélection d'articles et à ce que vos données soient collectées et stockées comme décrit dans notre politique de confidentialité

    Niveau de lecture

    Aidez-nous à évaluer le niveau de lecture de ce document.

    Si vous souhaitez expliquer votre choix, vous pouvez ajouter un commentaire (Il ne sera pas publié).

    Votre choix a été pris en compte. Merci d'avoir estimé le niveau de ce document !

    Gilles Dowek

    Chercheur Inria, responsable de l'équipe Deducteam.

    Crédit Photo : Sébastien Dolidon.

    Voir le profil

    Thierry Viéville

    Directeur de recherche Inria dans l'équipe MNEMOSYNE.

    Voir le profil

    Jean-Pierre Archambault

    Président de l'association Enseignement Public & Informatique (EPI).

    Voir le profil

    Emmanuel Baccelli

    Chercheur Inria dans l'ancienne équipe HIPERCOM.

    Voir le profil

    Benjamin Wack

    Docteur en informatique, professeur de mathématiques à Villard-de-Lans.

    Voir le profil

    Découvrez le(s) dossier(s) associé(s) à cet article :

    DossierDonnées
    Algorithmes

    Données structurées et leur traitement