Séance 0 — Qu’est-ce qu’un algorithme

Problème, instruction, exécution à la main

Séance 0 d’Algorithmique : problème, instruction, exécution à la main.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

NoteNavigation conceptuelle

Amont. Aucun prérequis : chacun suit déjà des procédures écrites ou apprises, une recette, un itinéraire, un paiement par téléphone. La séance en dégage les exigences, puis les écrit dans le pseudo-code du cours.

Aval. Les variables et l’affectation (Séance 1) donnent une mémoire à l’algorithme ; les conditions (Séance 2) lui permettent de choisir, les boucles (Séance 3) de répéter ; les tableaux (Séance 4) et les fonctions (Séance 5) organisent les données et les traitements.

ImportantObjectifs
  • Énoncer un problème par ses données et son résultat ; choisir un cas ordinaire et un cas limite.
  • Dire si une suite d’étapes est un algorithme : finie, faite d’instructions non ambiguës, exécutées dans l’ordre, et qui se termine.
  • Réécrire une consigne ambiguë en instruction précise ; repérer une étape qui peut ne pas finir.
  • Distinguer algorithme, langage de programmation et programme.
  • Lire la structure d’un algorithme écrit en pseudo-code : en-tête, partie Variables, Début, Fin, lignes numérotées ; prévoir ce qu’écrit Écrire.
  • Exécuter un algorithme à la main et en écrire la trace : pas, ligne, instruction, ce qui est écrit, arrêt éventuel.

Problème et algorithme

Des procédures de la vie courante

Préparer l’attaya, aller de Colobane à l’université en car rapide, payer un marchand avec son téléphone : chacune de ces tâches se fait en suivant des étapes, dans un certain ordre. Celui qui les connaît les suit sans y penser ; celui qui les découvre a besoin qu’on les lui écrive, et l’écriture doit alors être assez précise pour qu’il n’ait rien à deviner. L’algorithmique étudie ces suites d’étapes : comment les écrire sans ambiguïté, comment vérifier qu’elles donnent le bon résultat et qu’elles finissent. Celui qui suit les étapes s’appelle l’exécutant ; ce peut être une personne, ou une machine, qui ne comprend rien et exécute tout à la lettre.

Le problème : des données, un résultat

Avant d’écrire une méthode, on dit ce qu’elle reçoit et ce qu’elle doit produire.

NoteProblème, données, résultat, cas

Un problème est décrit par ses données, ce que l’on connaît au départ, et par le résultat attendu, ce que l’on veut obtenir. Un cas est un choix de valeurs des données. Le problème dit aussi quelles données sont permises : un montant à payer est un nombre positif, un nombre d’invités vaut au moins 1.

Payer un marchand par mobile money part d’un solde et d’un montant pour arriver à un nouveau solde ; avec un solde de 10000 F et un montant de 2500 F (valeurs illustratives), le nouveau solde est 7500 F. Le même schéma décrit bien d’autres tâches :

Problème Données Résultat
payer un marchand solde, montant nouveau solde
aller à la FST en car rapide point de départ, point d’arrivée la suite des trajets
préparer un thiéboudienne nombre de personnes, ingrédients le plat
servir l’attaya nombre d’invités un verre par invité

Distinguer le problème de ses cas est essentiel : une méthode n’est utile que si elle convient à tous les cas permis, et pas seulement à celui que l’on avait en tête en l’écrivant.

L’algorithme

NoteAlgorithme, instruction

Un algorithme est une suite finie d’instructions, chacune non ambiguë, qui, exécutées dans l’ordre, donnent le résultat du problème pour chacun de ses cas permis, et se terminent.

Une instruction est un ordre que l’exécutant accomplit sans rien deviner : une seule action, avec ce qu’elle concerne, en quelle quantité, à quel moment.

Chaque mot de la définition écarte un défaut. Finie : on doit pouvoir écrire l’algorithme en entier. Non ambiguë : deux exécutants qui suivent les mêmes instructions sur le même cas font la même chose et obtiennent le même résultat. Dans l’ordre : l’ordre des instructions fait partie de l’algorithme. Se terminent : l’exécution atteint la fin après un nombre fini d’étapes. Pour chacun de ses cas : l’algorithme résout le problème, pas un exemple. Le mot « algorithme » vient du nom d’al-Khwârizmî, mathématicien du IXe siècle, dont les traités ont fait connaître en Europe le calcul avec les chiffres indo-arabes ; ses méthodes de calcul étaient déjà des suites d’étapes précises.

L’ambiguïté d’une consigne

Une recette de thiéboudienne dit « ajoute du sel ». Une cuisinière expérimentée sait combien et quand ; un autre exécutant met une pincée, un troisième une poignée, au début ou à la fin de la cuisson. La consigne n’est pas fausse, elle est incomplète : elle compte sur un savoir que l’exécutant n’a pas.

AvertissementAmbiguïté

Une consigne est ambiguë quand deux exécutants peuvent la suivre de deux façons différentes. Les mots « assez », « un peu », « un moment », « à son goût », « bien » supposent un jugement ; une instruction dit ce qu’elle concerne, combien et quand.

Consigne Ce qui manque Instruction précise (quantités illustratives)
ajouter du sel combien, quand ajouter 1 cuillère à soupe de sel dans la sauce, après les légumes
laisser cuire un moment combien de temps laisser cuire 20 minutes à feu doux
mettre assez d’eau quelle quantité verser 2 litres d’eau dans la marmite
ajouter les légumes lesquels, dans quel ordre ajouter le manioc et le chou, puis, 10 minutes plus tard, l’aubergine

Lever une ambiguïté oblige souvent à faire un choix que la consigne laissait ouvert : une quantité, une durée. Les valeurs de ce tableau sont illustratives ; ce qui compte est qu’une fois écrites, elles ne laissent plus de choix à l’exécutant.

La terminaison

Un algorithme doit finir. Chaque étape doit donc finir, et la suite des étapes doit avoir une dernière étape. Le danger vient surtout des étapes qui attendent un événement : « attendre que… », « recommencer jusqu’à ce que… ».

NoteTerminaison

Un algorithme se termine sur un cas quand son exécution atteint sa dernière étape après un nombre fini d’étapes. Une étape « jusqu’à ce que … » ne finit que si l’événement attendu finit par arriver, et que l’exécutant sait constater qu’il est arrivé.

Sur un itinéraire en car rapide de Colobane à l’université (itinéraire illustratif), trois étapes posent problème :

Étape Ce qui peut arriver Étape qui se termine
attendre un car rapide vide aux heures de pointe, aucun n’arrive vide : l’attente ne finit pas monter dans le premier car rapide qui va à l’université
descendre quand on est près de l’université « près » ne dit pas quand s’arrêter : l’exécutant ne sait pas constater l’événement descendre à l’arrêt Université
chercher la pièce exacte jusqu’à la trouver si elle manque, la recherche ne finit pas donner la plus petite pièce ou le plus petit billet qui couvre le prix

La première étape peut ne jamais finir ; la deuxième finit peut-être, mais à un moment que l’exécutant ne sait pas déterminer : elle est à la fois ambiguë et mal terminée. La correction remplace l’attente d’un événement incertain par un événement qui arrive sûrement et se constate (un arrêt nommé, le premier car qui passe). La troisième est une recherche « jusqu’à » : elle finit si la pièce exacte se trouve dans la poche, et ne finit pas sinon ; la correction la remplace par un choix qui se fait toujours, puisqu’il porte sur ce que l’on a.

L’ordre des étapes : payer par mobile money

Un paiement par Wave ou Orange Money suit une suite d’étapes. Les voici, simplifiées (frais non comptés) :

  1. Ouvrir l’application de mobile money.
  2. Choisir « Payer », puis le marchand (code QR scanné ou numéro saisi).
  3. Saisir le montant à payer.
  4. Vérifier le nom du marchand et le montant affichés.
  5. Valider avec le code secret.
  6. Lire le message de confirmation, qui donne le nouveau solde.

Chaque étape fait une seule chose, et l’exécutant passe à la suivante quand elle est faite. L’étape 3 apporte une donnée, le montant ; l’étape 5 change le solde. Si l’on échange les étapes 4 et 5, la vérification vient après la validation : une erreur de montant n’est vue qu’une fois le compte débité. Les mêmes étapes, dans un autre ordre, forment un autre algorithme, qui ne résout plus le problème de la même façon. Le tableau suivant exécute les deux ordres sur un cas où le payeur voulait payer 2500 F et a saisi 5000 F par erreur, avec un solde de 10000 F :

Pas Ordre de départ Solde Étapes 4 et 5 échangées Solde
1 application ouverte 10000 F application ouverte 10000 F
2 marchand choisi 10000 F marchand choisi 10000 F
3 montant saisi : 5000 F 10000 F montant saisi : 5000 F 10000 F
4 5000 F affiché, 2500 F voulu : annulé 10000 F compte débité de 5000 F 5000 F
5 — 5000 F affiché : erreur vue trop tard 5000 F
6 — message lu 5000 F

Dans l’ordre de départ, l’erreur est vue à l’étape 4, avant que le compte ne soit touché : le paiement est annulé et le solde reste 10000 F. Avec les étapes échangées, le compte est débité de 5000 F à l’étape 4, et la vérification de l’étape 5 ne peut plus que constater l’erreur. L’annulation de l’ordre de départ est un choix, fait par l’exécutant au vu de ce qu’affiche l’application ; écrire ce choix en pseudo-code demande Si (Séance 2).

L’exécution à la main d’un algorithme de la vie courante

Exécuter un algorithme à la main, c’est suivre ses étapes dans l’ordre, sur un cas, en notant après chaque étape ce qui a changé. Le tableau suivant exécute le paiement pour un montant de 2500 F, avec un solde de départ de 10000 F (cas 1) puis de 2500 F (cas 2) ; chaque ligne est un pas de l’exécution, et le solde modifié est en gras.

Pas Ce qui est fait (étape du même numéro) Solde, cas 1 Solde, cas 2
1 application ouverte 10000 F 2500 F
2 marchand choisi 10000 F 2500 F
3 montant saisi : 2500 F 10000 F 2500 F
4 affiché : marchand, 2500 F 10000 F 2500 F
5 compte débité de 2500 F 7500 F 0 F
6 message lu 7500 F 0 F

Le solde ne change qu’au pas 5. Dans le cas 1, il passe de 10000 F à 7500 F. Dans le cas 2, le montant est égal au solde : le paiement est accepté et le solde devient nul. Ce second cas n’a pas été choisi au hasard.

NoteCas limite

Un cas limite est un cas à la frontière des données permises : la plus petite valeur permise, une égalité entre deux données, une valeur nulle. Un algorithme se vérifie sur un cas ordinaire et sur au moins un cas limite ; les erreurs se cachent le plus souvent aux frontières.

Un montant supérieur au solde n’est pas une donnée permise de cet algorithme : l’application refuse le paiement. Traiter ce cas demande un choix entre deux suites d’étapes, que le pseudo-code écrit avec l’instruction Si (Séance 2).

La reconnaissance d’un algorithme

Les exigences de la définition permettent de juger une suite d’étapes avant de l’exécuter : on vérifie, l’une après l’autre, qu’elle est finie, que chaque étape est non ambiguë, que l’ordre est juste, que l’exécution se termine et qu’elle donne le résultat pour chaque cas permis. Quatre textes, jugés ainsi :

Texte Algorithme ? Raison
« Pour aller à Thiès, prendre la route et demander son chemin. » non « la route » et « demander » ne disent ni laquelle ni à qui : deux exécutants font deux trajets différents
« Écrire la liste de tous les multiples de 5. » non la liste n’a pas de dernier élément : l’exécution ne se termine pas
« Chercher un nom dans le répertoire du téléphone jusqu’à le trouver. » non si le nom n’y est pas, la recherche ne finit pas ; il faut prévoir le cas où l’on arrive à la fin du répertoire
les six étapes du paiement par mobile money (§ 1.6) oui six étapes, chacune précise, dans un ordre qui protège le payeur ; l’exécution finit à l’étape 6, pour tout montant permis

Le troisième texte montre une faute que l’on commet souvent : penser au cas où tout se passe bien (le nom est dans le répertoire) et oublier l’autre. Un algorithme doit se terminer sur chaque cas permis, y compris celui où ce que l’on cherche n’existe pas.

Plusieurs algorithmes pour un même problème

Un problème a souvent plusieurs algorithmes. Pour aller de Colobane à la FST (itinéraires illustratifs), voici deux suites d’étapes :

En car rapide

  1. Aller à l’arrêt de car rapide de Colobane.
  2. Monter dans le premier car rapide qui va à l’université.
  3. Payer sa place au receveur.
  4. Descendre à l’arrêt Université.
  5. Marcher jusqu’à la FST.

En taxi

  1. Héler un taxi à Colobane.
  2. Annoncer la destination : la FST, à l’université.
  3. Convenir du prix avec le chauffeur avant de monter.
  4. Monter et rester à bord jusqu’à l’arrêt devant la FST.
  5. Payer le prix convenu et descendre.

Les deux suites sont finies, chaque étape est précise, l’ordre est imposé (on paie le receveur une fois monté, on convient du prix du taxi avant de monter), et chacune mène à la FST : ce sont deux algorithmes justes pour le même problème. L’algorithme n’est donc pas le problème ; c’est une méthode pour le résoudre.

Entre deux algorithmes justes, on choisit selon d’autres critères : le nombre d’étapes, le temps qu’elles prennent, ce qu’elles coûtent, ce qu’elles demandent à l’exécutant.

Critère En car rapide En taxi
nombre d’étapes 5 5
coût le prix d’une place, fixé un prix négocié, plus élevé
ce qui est demandé à l’exécutant reconnaître le bon car, repérer l’arrêt s’accorder sur un prix
cas à prévoir le car est plein aucun accord sur le prix

Le même nombre d’étapes ne veut pas dire le même coût : une étape de négociation prend plus de temps qu’une étape de paiement à prix fixé. La dernière ligne du tableau montre aussi que chaque algorithme a ses propres cas à prévoir : si aucun accord n’est trouvé, l’étape 3 du taxi n’aboutit pas, et il faut une autre suite d’étapes (héler un autre taxi) : un choix, que la Séance 2 écrira avec Si. Comparer ainsi deux méthodes est une partie importante de l’algorithmique ; il faut d’abord savoir les écrire et les exécuter sans erreur, ce qui est l’objet de ce cours.

Algorithme, programme, langage

Un algorithme est une méthode ; il ne dépend d’aucune machine. Pour qu’une machine l’exécute, il faut l’écrire dans un langage qu’elle sait traiter.

NoteLangage de programmation, programme

Un langage de programmation est un ensemble de règles d’écriture strictes, que la machine sait traduire en actions : Python, C et Java en sont des exemples. Un programme est un algorithme écrit dans un langage de programmation ; la machine exécute le programme.

Une recette s’écrit en français ou en wolof : une méthode, deux textes. De même, un algorithme se traduit en plusieurs programmes, un par langage, qui font tous la même chose. La traduction ajoute des détails propres au langage (la ponctuation, la façon de nommer les choses), mais elle ne change pas la méthode : une erreur dans l’algorithme se retrouve dans chacun de ses programmes. C’est pourquoi le cours écrit et vérifie les algorithmes avant toute programmation, et les exécute à la main : l’exécutant joue alors lui-même le rôle de la machine, et la trace de son exécution montre ce que ferait le programme.

L’exécutant change ce que l’on peut attendre d’un algorithme. Une personne comprend souvent le sens des étapes, et peut compenser une consigne imprécise ; une machine n’a que les instructions.

Situation Exécutant humain Machine
une consigne ambiguë devine, parfois mal ne devine rien : l’instruction n’est pas acceptée
deux étapes dans un ordre absurde s’en aperçoit, parfois les exécute dans l’ordre écrit
une étape impossible s’arrête et demande s’arrête : arrêt de l’exécution
mille étapes à exécuter lent, risque d’erreur rapide, sans fatigue

Écrire pour une machine oblige donc à tout dire : c’est ce qui rend l’algorithme vérifiable, puisque deux exécutions sur le même cas donnent toujours la même trace.

Le français courant laisse place à l’interprétation ; un langage de programmation impose les détails d’une machine. Le cours écrit ses algorithmes entre les deux, dans un pseudo-code : un français réduit et réglé, avec un vocabulaire fixe de mots-clés (Algorithme, Début, Fin, Écrire…), chacun d’un seul sens, une instruction par ligne et des lignes numérotées. Il se lit sans machine et se traduit dans tout langage. Un mot-clé s’écrit toujours de la même façon : Écrire, avec sa majuscule et son accent. Dans les algorithmes de ce document, les mots-clés sont en gras ; le reste (les noms, les textes entre guillemets) est choisi par l’auteur.

Le pseudo-code du cours

Les conventions

Le tableau ci-dessous rassemble les conventions fixées par la séance ; les séances suivantes les complètent sans les changer.

Écriture Sens
Algorithme Nom l’en-tête : le nom de l’algorithme, qui commence par une majuscule, sans accent ni espace (Annonce, Itineraire, MonGuide)
Variables la partie des déclarations des variables (Séance 1) ; un algorithme sans variable n’a pas de partie Variables
Début … Fin les instructions, une par ligne, exécutées dans l’ordre, de haut en bas ; aucune instruction après Fin
Écrire "texte" écrit le texte, sans les guillemets, puis passe à la ligne
numéros de ligne de 1 (l’en-tête) à la ligne Fin ; chaque ligne compte, Début et Fin compris
retrait de deux espaces sous Variables, et pour les instructions entre Début et Fin
Lire n ; \(x\leftarrow e\) aperçu de la Séance 1 : Lire range dans n la valeur tapée au clavier ; \(x\leftarrow e\) range dans \(x\) le résultat de l’expression \(e\)
trace une ligne par pas : numéro du pas, numéro de la ligne exécutée, instruction, valeurs des variables après le pas (Séance 1), ce qu’écrit Écrire ; l’en-tête, la partie Variables, Début et Fin ne produisent aucun pas

La structure d’un algorithme

À la gare routière des Baux maraîchers, à Pikine, un écran annonce les départs. L’algorithme suivant écrit une annonce de trois lignes (le quai est illustratif).

Algorithme Annonce
Début
  Écrire "Gare des Baux maraîchers"
  Écrire "Car pour Thiès : quai 3"
  Écrire "Bon voyage"
Fin

L’algorithme a trois parties. La ligne 1 est l’en-tête : le mot-clé Algorithme suivi du nom, Annonce. La partie Variables, qui déclare les cases de mémoire nommées dont l’algorithme a besoin, est absente : cet algorithme n’a rien à retenir. Les lignes 2 et 6, Début et Fin, encadrent les instructions, lignes 3 à 5, écrites une par ligne et en retrait de deux espaces. Après Fin, rien : toute instruction de l’algorithme se trouve entre Début et Fin.

Les lignes sont numérotées de 1 à la ligne Fin, en-tête compris. Ces numéros servent à désigner une ligne sans ambiguïté (« la ligne 4 ») et à suivre l’exécution : insérer une ligne décale les numéros de toutes celles qui suivent. Le nom de l’algorithme commence par une majuscule et ne contient ni accent ni espace : Itineraire et non Itinéraire, MonGuide et non Mon guide ; ces noms se traduisent ainsi sans changement dans la plupart des langages.

L’instruction Écrire

NoteÉcrire "texte"

L’instruction Écrire "texte" écrit le texte placé entre les guillemets, sans les guillemets, puis passe à la ligne : chaque Écrire exécuté écrit une ligne, à la suite des précédentes. Le texte est écrit tel quel, espaces et ponctuation compris.

L’algorithme Annonce écrit donc trois lignes, dans l’ordre de ses instructions : Gare des Baux maraîchers, puis Car pour Thiès : quai 3, puis Bon voyage. Les guillemets délimitent le texte ; ils ne sont pas écrits.

AvertissementLes guillemets

Sans guillemets, un mot n’est plus un texte : Écrire merci demande la valeur d’une variable nommée merci (les variables sont l’objet de la Séance 1). merci n’est pas une variable de l’algorithme : l’instruction ne peut pas s’exécuter, et l’exécution s’arrête à cette ligne.

La relecture d’un algorithme

Avant d’exécuter un algorithme, on le relit selon les conventions, dans cet ordre :

  1. L’en-tête. La ligne 1 est-elle Algorithme suivi d’un nom à initiale majuscule, sans accent ni espace ?
  2. Les parties. Y a-t-il une partie Variables si, et seulement si, l’algorithme utilise des variables ? Début et Fin sont-ils présents, et rien n’est-il écrit après Fin ?
  3. Les instructions. Chaque ligne entre Début et Fin porte-t-elle une seule instruction, en retrait de deux espaces, avec ses mots-clés bien écrits (Écrire, avec sa majuscule et son accent) ?
  4. Les textes. Chaque texte à écrire est-il entre guillemets ?
  5. Les numéros. Les lignes sont-elles numérotées de 1 à Fin, en-tête compris ?

Pour l’algorithme Annonce, les cinq réponses sont oui : on peut l’exécuter. Une réponse non à la question 4 annonce un arrêt à l’exécution ; une réponse non aux autres questions signale un algorithme qui ne respecte pas les conventions, à corriger avant de l’exécuter. Les exercices corrigés 2 et 3 appliquent cette relecture.

L’exécution d’un algorithme à la main : la trace

La trace d’exécution

Exécuter à la main un algorithme écrit en pseudo-code, c’est faire ce que ferait la machine : suivre ses lignes dans l’ordre et noter chaque étape. On note cette exécution dans un tableau.

NoteTrace, pas

Une trace d’exécution est un tableau qui suit l’exécution d’un algorithme sur un cas : une ligne par pas, c’est-à-dire par instruction exécutée, avec le numéro du pas, le numéro de la ligne exécutée, l’instruction et ce qu’écrit Écrire. L’en-tête, la partie Variables, Début et Fin ne produisent aucun pas : ils décrivent l’algorithme, ils ne s’exécutent pas.

Les algorithmes de cette séance n’ont ni condition, ni répétition, ni appel (Séances 2, 3 et 5) : chaque instruction s’exécute une fois, de haut en bas, sauf arrêt (§ 4.3). Deux conséquences en découlent. Sans arrêt, la trace a autant de pas que l’algorithme a d’instructions entre Début et Fin ; et l’exécution se termine toujours, après au plus ce nombre de pas. La terminaison, qui demandait de l’attention pour les étapes de la vie courante, est ici assurée par la forme même de l’algorithme.

Remplir une trace est lui-même une suite d’étapes précises, que l’on applique à tout algorithme de la séance :

  1. Repérer la première instruction après Début ; c’est la ligne du pas 1.
  2. Exécuter l’instruction de la ligne courante et ajouter une ligne au tableau : numéro du pas, numéro de la ligne, instruction, ce qu’elle écrit.
  3. Si l’instruction ne peut pas s’exécuter, écrire « arrêt » et sa cause dans la colonne « Écrit », et s’arrêter.
  4. Sinon, passer à la ligne suivante ; si c’est Fin, l’exécution est terminée ; sinon, reprendre à l’étape 2.

Chaque étape est non ambiguë, et la méthode se termine : à chaque reprise, la ligne courante descend d’une ligne, et l’algorithme n’a qu’un nombre fini de lignes.

Exemple pas à pas : l’annonce

Pas Ligne Instruction Écrit
1 3 Écrire “Gare des Baux maraîchers” Gare des Baux maraîchers
2 4 Écrire “Car pour Thiès : quai 3” Car pour Thiès : quai 3
3 5 Écrire “Bon voyage” Bon voyage

La trace commence à la ligne 3 : les lignes 1 et 2, l’en-tête et Début, ne s’exécutent pas. Le pas 1 exécute la ligne 3 et écrit Gare des Baux maraîchers ; le pas 2 exécute la ligne 4, le pas 3 la ligne 5. La ligne 6, Fin, termine l’algorithme sans produire de pas. Trois instructions, trois pas. La figure montre le pas 3 tel qu’il se suit à la main : la ligne exécutée est surlignée, la ligne du tableau qui vient d’être ajoutée est encadrée en orange, et la case qui vient d’être remplie, en rouge.

Au pas 1, la même figure n’avait qu’une ligne de tableau, et la colonne « écrit » ne contenait que Gare des Baux maraîchers : à chaque pas, le tableau grandit d’une ligne, et la sortie, d’au plus une ligne. Suivre une trace à la main, c’est refaire ce dessin pas après pas, sans jamais anticiper une ligne qui n’a pas encore été exécutée.

Une instruction impossible : l’arrêt

AvertissementArrêt de l’exécution

Une instruction qui ne peut pas s’exécuter arrête l’exécution à sa ligne : la trace s’arrête à ce pas, avec la mention « arrêt » et sa cause ; les lignes suivantes ne s’exécutent pas, et ce qui a été écrit avant l’arrêt reste écrit. L’exécution ne saute pas la ligne fautive.

L’exercice corrigé 3 suit un tel arrêt pas à pas. Les autres fautes d’écriture n’arrêtent pas une exécution : elles empêchent de lire l’algorithme selon les conventions, et il faut les corriger avant de l’exécuter.

Écriture fautive Ce qui ne va pas
Écrire merci sans guillemets, merci est lu comme le nom d’une variable ; merci n’est pas une variable de l’algorithme : arrêt à cette ligne
Ecrire "merci" ; debut un mot-clé mal écrit n’est pas une instruction du pseudo-code
Algorithme Itinéraire ; Algorithme Mon guide le nom contient un accent ou une espace : Itineraire, MonGuide
une instruction après Fin elle est hors de l’algorithme : les instructions sont entre Début et Fin
deux instructions sur une ligne une instruction par ligne, pour que chaque pas désigne une ligne

Aperçu de la Séance 1 : une donnée lue, un résultat calculé

L’annonce écrit toujours la même chose : elle n’a pas de données. Le paiement, lui, dépend du montant. Pour l’écrire en pseudo-code, il faut deux instructions que la Séance 1 étudiera en détail : Lire, qui range une valeur tapée au clavier, et l’affectation \(\leftarrow\), qui range le résultat d’un calcul. Les deux rangent leur valeur dans une variable, une case de mémoire nommée, déclarée dans la partie Variables. Le solde de départ est fixé à 10000 F (valeur illustrative).

Algorithme Paiement
Variables
  montant, solde : entier
Début
  Lire montant
  solde ← 10000 - montant
  Écrire "nouveau solde :", solde
Fin

Les lignes 2 et 3 déclarent deux variables entières, montant et solde. La ligne 5 range dans montant la valeur tapée au clavier. La ligne 6 calcule \(10000-\texttt{montant}\) et range le résultat dans solde ; la flèche se lit « solde reçoit… ». Les calculs s’écrivent avec les signes \(+\), \(-\), \(\times\) (multiplication) et \(/\), dont la Séance 1 fixe les règles. La ligne 7 écrit le texte nouveau solde :, une espace, puis la valeur de solde. Pour l’entrée 2500, la trace a une colonne par variable, qui montre la valeur rangée après chaque pas (en gras, la variable qui vient de recevoir une valeur ; une case vide, une variable qui n’en a pas encore) :

Pas Ligne Instruction montant solde Écrit
1 5 Lire montant 2500
2 6 solde ← 10000 - montant 2500 7500
3 7 Écrire “nouveau solde :”, solde 2500 7500 nouveau solde : 7500

La figure montre le pas 2 : la ligne 6 est surlignée, et solde reçoit 7500 (case rouge). La ligne du tableau qui vient d’être ajoutée est encadrée en orange ; la colonne de montant garde la valeur rangée au pas 1, et la case de solde, vide au pas 1, est remplie au pas 2. C’est ainsi qu’une trace se lit : une ligne par pas, et, d’une ligne à la suivante, seule change la case de la variable qui vient de recevoir une valeur.

Le passage de la vie courante au pseudo-code se lit ligne à ligne. Les étapes du paiement qui consistent à manipuler l’application (l’ouvrir, choisir le marchand, vérifier) n’ont pas d’équivalent : elles concernent l’exécutant humain. Les trois étapes qui portent sur les données et le résultat deviennent chacune une instruction.

Étape de la vie courante Ligne du pseudo-code Ce qui est fait
3. Saisir le montant à payer. 5 : Lire montant une donnée entre dans l’algorithme
5. Valider avec le code secret. 6 : solde \(\leftarrow\) 10000 - montant le solde est calculé et rangé
6. Lire le message de confirmation. 7 : Écrire "nouveau solde :", solde le résultat est montré

Trois instructions, trois pas, comme pour l’annonce ; les lignes 1 à 4 et la ligne 8 n’en produisent aucun. L’algorithme écrit nouveau solde : 7500, le résultat de l’exécution à la main du cas 1. Le même algorithme résout le problème pour chaque montant permis ; pour le cas limite d’un montant égal au solde, 10000, il écrit nouveau solde : 0 :

Pas Ligne Instruction montant solde Écrit
1 5 Lire montant 10000
2 6 solde ← 10000 - montant 10000 0
3 7 Écrire “nouveau solde :”, solde 10000 0 nouveau solde : 0

L’algorithme ne vérifie rien : pour un montant négatif tapé par erreur, \(-500\), il s’exécute et écrit nouveau solde : 10500, un résultat sans signification :

Pas Ligne Instruction montant solde Écrit
1 5 Lire montant \(-500\)
2 6 solde ← 10000 - montant \(-500\) 10500
3 7 Écrire “nouveau solde :”, solde \(-500\) 10500 nouveau solde : 10500

Rien dans la trace ne signale l’erreur : chaque pas s’exécute normalement. C’est le problème qui dit quelles données sont permises ; refuser une donnée non permise est un choix, que la Séance 2 écrira avec Si.

Exercices corrigés

Les trois exercices suivants reprennent les gestes de la séance : rendre une recette non ambiguë puis l’exécuter à la main sur un cas ordinaire et sur un cas limite ; suivre l’ordre des lignes dans une trace et compter ses pas ; suivre une exécution jusqu’à un arrêt et la corriger. Chaque correction énonce la règle appliquée, donne la trace ou le tableau complet, conclut et signale l’erreur la plus répandue.

Exercice 1 : une recette ambiguë

Un cahier de recettes donne les étapes suivantes pour l’attaya. La donnée du problème est le nombre \(n\) d’invités (\(n\geq1\)).

  1. Mettre de l’eau dans la théière.
  2. Ajouter du thé vert.
  3. Faire chauffer un moment.
  4. Ajouter du sucre.
  5. Verser d’un verre à l’autre jusqu’à ce que la mousse soit belle.
  6. Servir les invités.
  1. Quelles étapes sont ambiguës ? Que manque-t-il à chacune ?
  2. Quelle étape peut ne pas se terminer ? Pourquoi ?
  3. Réécrire les six étapes, sans ambiguïté, pour \(n\) invités.
  4. Exécuter la version réécrite à la main pour 4 invités, puis pour le cas limite d’un seul invité : donner les quantités et le nombre de verres utilisés.
AstuceCorrection

(a) Règle appliquée : une instruction dit ce qu’elle concerne, combien et quand. L’étape 1 ne dit pas combien d’eau, l’étape 2 combien de thé, l’étape 4 combien de sucre ; l’étape 3 ne dit pas combien de temps chauffer (« un moment ») ; l’étape 6 ne dit pas combien de verres remplir. Deux exécutants obtiendraient deux thés différents.

(b) Règle appliquée : une étape « jusqu’à ce que » ne finit que si l’événement arrive et se constate. L’étape 5 attend que la mousse soit « belle », un jugement : un exécutant s’arrête après trois versements, un autre après vingt, un troisième ne s’arrête pas. L’étape est ambiguë et peut ne pas se terminer.

(c) Chaque quantité est fixée, ou calculée à partir de \(n\) ; l’attente de l’étape 3 porte sur un événement qui se constate ; l’étape 5 compte ses versements. Une version possible (quantités illustratives) :

  1. Verser dans la théière \(n\) petits verres d’eau.
  2. Ajouter 2 cuillères à café de thé vert.
  3. Poser la théière sur le feu ; l’en retirer quand l’eau bout.
  4. Ajouter 2 morceaux de sucre par invité.
  5. Verser le thé d’un verre dans un autre, de haut, 6 fois.
  6. Remplir un verre par invité et servir.

(d) Règle appliquée : exécuter, c’est suivre les étapes dans l’ordre sur un cas et noter ce que chacune produit. Pour \(n=4\), l’exécution à la main donne la trace suivante, un pas par étape :

Pas Étape exécutée Ce qui est fait
1 1. Verser dans la théière \(n\) petits verres d’eau. 4 verres d’eau
2 2. Ajouter 2 cuillères à café de thé vert. 2 cuillères de thé
3 3. Poser la théière sur le feu ; l’en retirer quand l’eau bout. eau bouillie, théière retirée
4 4. Ajouter 2 morceaux de sucre par invité. 8 morceaux de sucre
5 5. Verser le thé d’un verre dans un autre, de haut, 6 fois. 6 versements, 2 verres
6 6. Remplir un verre par invité et servir. 4 verres servis

Pour le cas limite \(n=1\) :

Pas Étape exécutée Ce qui est fait
1 1. Verser dans la théière \(n\) petits verres d’eau. 1 verre d’eau
2 2. Ajouter 2 cuillères à café de thé vert. 2 cuillères de thé
3 3. Poser la théière sur le feu ; l’en retirer quand l’eau bout. eau bouillie, théière retirée
4 4. Ajouter 2 morceaux de sucre par invité. 2 morceaux de sucre
5 5. Verser le thé d’un verre dans un autre, de haut, 6 fois. 6 versements, 2 verres
6 6. Remplir un verre par invité et servir. 1 verre servi

Le résumé des deux exécutions :

Étape Grandeur \(n=4\) \(n=1\) (cas limite)
1 eau versée (petits verres) 4 1
2 thé vert (cuillères à café) 2 2
4 sucre (morceaux) 8 2
5 versements d’un verre à l’autre 6 6
6 verres servis 4 1
5, 6 verres utilisés 4 2

Pour 4 invités : 4 petits verres d’eau, 2 cuillères de thé, \(2\times4=8\) morceaux de sucre, 6 versements, 4 verres servis. L’étape 5 verse d’un verre dans un autre : elle utilise deux des quatre verres. Pour un seul invité, l’étape 5 demande quand même deux verres, alors qu’un seul est servi : le cas limite fait apparaître une exigence que le cas ordinaire cachait. La version réécrite reste juste, mais l’exécutant doit disposer d’au moins deux verres, ce que l’on peut ajouter à l’étape 1.

Conclusion. Rendre une consigne non ambiguë, c’est remplacer chaque jugement par une quantité, une durée ou un événement constatable ; vérifier l’algorithme obtenu, c’est l’exécuter sur un cas ordinaire et sur un cas limite.

AvertissementErreur fréquente

Ne vérifier que le cas ordinaire. Pour 4 invités, l’algorithme utilise 4 verres, autant que d’invités, et rien ne signale de problème ; seule l’exécution pour 1 invité montre qu’il faut 2 verres. Un cas limite se choisit à la frontière des données permises (ici \(n=1\)), pas au hasard.

Exercice 2 : un itinéraire écrit par un algorithme

L’algorithme suivant écrit, pour un nouvel étudiant qui vient en car rapide, l’itinéraire de Colobane à la FST (itinéraire illustratif).

Algorithme Itineraire
Début
  Écrire "Prendre un car à Colobane"
  Écrire "Descendre à l'arrêt UCAD"
  Écrire "Marcher jusqu'à la FST"
Fin
  1. Quelles lignes produisent un pas ? Combien de pas compte la trace ?
  2. Qu’écrit l’algorithme ?
  3. On échange les lignes 3 et 5. Qu’écrit l’algorithme ? Résout-il encore le problème ?
  4. On insère Écrire "Montrer sa carte d'étudiant" après la ligne 4. Quel est le numéro de la ligne Fin ? Combien de pas compte la trace ?
AstuceCorrection

Relecture (§ 3.4). En-tête Algorithme Itineraire, nom sans accent ; pas de partie Variables, et l’algorithme n’utilise aucune variable ; Début ligne 2, Fin ligne 6, rien après ; une instruction Écrire par ligne, en retrait ; chaque texte entre guillemets ; lignes numérotées de 1 à 6. Les cinq réponses sont oui : l’algorithme s’exécute sans arrêt.

(a) Règle appliquée : seules les instructions entre Début et Fin produisent un pas ; sans condition ni répétition ni appel, et sans arrêt, chacune en produit un. Les lignes 1 (en-tête), 2 (Début) et 6 (Fin) n’en produisent pas. Les lignes 3, 4 et 5 en produisent un chacune : la trace a 3 pas.

(b) Règle appliquée : chaque Écrire écrit son texte, sans guillemets, sur une nouvelle ligne, dans l’ordre des pas.

Pas Ligne Instruction Écrit
1 3 Écrire “Prendre un car à Colobane” Prendre un car à Colobane
2 4 Écrire “Descendre à lárrêt UCAD” Descendre à l'arrêt UCAD
3 5 Écrire “Marcher jusqu'à la FST” Marcher jusqu'à la FST

L’algorithme écrit trois lignes, dans l’ordre des lignes 3, 4 et 5.

(c) Règle appliquée : les instructions s’exécutent dans l’ordre où elles sont écrites.

Algorithme Itineraire
Début
  Écrire "Marcher jusqu'à la FST"
  Écrire "Descendre à l'arrêt UCAD"
  Écrire "Prendre un car à Colobane"
Fin
Pas Ligne Instruction Écrit
1 3 Écrire “Marcher jusqu'à la FST” Marcher jusqu'à la FST
2 4 Écrire “Descendre à lárrêt UCAD” Descendre à l'arrêt UCAD
3 5 Écrire “Prendre un car à Colobane” Prendre un car à Colobane
Ligne écrite Algorithme de départ Lignes 3 et 5 échangées
1 Prendre un car à Colobane Marcher jusqu'à la FST
2 Descendre à l'arrêt UCAD Descendre à l'arrêt UCAD
3 Marcher jusqu'à la FST Prendre un car à Colobane

L’algorithme s’exécute sans arrêt et écrit les mêmes lignes dans l’ordre inverse : marcher jusqu’à la FST avant d’avoir pris le car. L’exécutant ne juge pas le sens de ce qu’il écrit ; l’itinéraire écrit est faux, et l’algorithme ne résout plus le problème.

(d) Règle appliquée : insérer une ligne décale les numéros des lignes qui suivent.

Algorithme Itineraire
Début
  Écrire "Prendre un car à Colobane"
  Écrire "Descendre à l'arrêt UCAD"
  Écrire "Montrer sa carte d'étudiant"
  Écrire "Marcher jusqu'à la FST"
Fin

La nouvelle ligne devient la ligne 5 ; l’ancienne ligne 5 passe à la ligne 6 et Fin à la ligne 7. L’algorithme compte 4 instructions, donc 4 pas :

Pas Ligne Instruction Écrit
1 3 Écrire “Prendre un car à Colobane” Prendre un car à Colobane
2 4 Écrire “Descendre à lárrêt UCAD” Descendre à l'arrêt UCAD
3 5 Écrire “Montrer sa carte d'étudiant” Montrer sa carte d'étudiant
4 6 Écrire “Marcher jusqu'à la FST” Marcher jusqu'à la FST

Conclusion. L’ordre des lignes est l’ordre d’exécution ; une trace sans condition, ni répétition, ni appel, ni arrêt a un pas par instruction, et les numéros de ligne changent dès qu’une ligne est insérée.

AvertissementErreur fréquente

Compter un pas pour l’en-tête, Début ou Fin : on trouverait 6 pas au lieu de 3 en (a), et 7 au lieu de 4 en (d). Ces lignes encadrent l’algorithme sans s’exécuter ; la trace commence à la première instruction, ici la ligne 3.

Exercice 3 : une instruction mal écrite

Une boutique de Kaolack affiche un message d’accueil.

Algorithme Accueil
Début
  Écrire "Bienvenue"
  Écrire "Chez Fatou"
  Écrire merci
  Écrire "À bientôt"
Fin
  1. Dérouler l’algorithme dans une trace : pas, ligne, instruction, écrit.
  2. Qu’est-il écrit au moment de l’arrêt ? La ligne 6 est-elle exécutée ?
  3. Corriger la ligne 5 pour que l’algorithme écrive le mot merci. Qu’écrit alors l’algorithme ?
  4. Combien de pas compte la trace de la version corrigée ?
AstuceCorrection

Relecture (§ 3.4). Les questions 1, 2, 3 et 5 reçoivent un oui. La question 4 reçoit un non : à la ligne 5, merci n’est pas entre guillemets. La relecture annonce donc un arrêt à la ligne 5, que la trace confirme.

(a) Règle appliquée : un texte s’écrit entre guillemets ; sans guillemets, un mot est lu comme le nom d’une variable ; un nom qui n’est pas une variable de l’algorithme rend l’instruction impossible, et une instruction impossible arrête l’exécution à sa ligne.

Pas Ligne Instruction Écrit
1 3 Écrire “Bienvenue” Bienvenue
2 4 Écrire “Chez Fatou” Chez Fatou
3 5 Écrire merci arrêt : merci n’est pas une variable de l’algorithme

Les pas 1 et 2 exécutent les lignes 3 et 4. Au pas 3, la ligne 5 demande la valeur de merci, qui n’est pas une variable de l’algorithme : l’exécution s’arrête.

(b) Au moment de l’arrêt, deux lignes sont écrites, Bienvenue et Chez Fatou ; elles restent écrites. La ligne 6 n’est pas exécutée : À bientôt n’est pas écrit.

(c) La ligne 5 devient Écrire "merci" :

Algorithme Accueil
Début
  Écrire "Bienvenue"
  Écrire "Chez Fatou"
  Écrire "merci"
  Écrire "À bientôt"
Fin
Pas Ligne Instruction Écrit
1 3 Écrire “Bienvenue” Bienvenue
2 4 Écrire “Chez Fatou” Chez Fatou
3 5 Écrire “merci” merci
4 6 Écrire “À bientôt” À bientôt

L’algorithme écrit quatre lignes : Bienvenue, Chez Fatou, merci et À bientôt.

(d) 4 pas, un par instruction, lignes 3 à 6.

Conclusion. Une trace s’arrête au pas de l’instruction impossible ; ce qui précède reste fait, ce qui suit n’est pas exécuté.

AvertissementErreur fréquente

Croire que l’exécution saute la ligne fautive et continue, et annoncer trois lignes écrites (Bienvenue, Chez Fatou, À bientôt). L’exécution s’arrête à la ligne 5 : seules deux lignes sont écrites.

À retenir

Notion Ce que c’est Ce qui la met en défaut
problème des données, permises ou non, et un résultat attendu un cas oublié, souvent un cas limite
instruction un ordre exécuté sans rien deviner « un peu », « assez », « un moment »
algorithme suite finie d’instructions non ambiguës, exécutées dans l’ordre, qui se termine et résout chaque cas une étape sans fin, deux étapes inversées
trace une ligne par pas : pas, ligne, instruction, écrit un pas compté pour l’en-tête, Début ou Fin ; une ligne exécutée après un arrêt
  • Un algorithme se vérifie à la main, sur un cas ordinaire et sur un cas limite.
  • Algorithme : la méthode ; langage de programmation : des règles d’écriture ; programme : l’algorithme écrit dans un langage, que la machine exécute.
  • Algorithme Nom, Variables, Début, Fin ; une instruction par ligne, lignes numérotées de l’en-tête à Fin.
  • Écrire "texte" écrit le texte sans les guillemets, puis passe à la ligne.
  • Sans condition ni répétition ni appel (Séances 2, 3 et 5), et sans arrêt, chaque instruction s’exécute une fois : autant de pas que d’instructions. L’exécution se termine toujours.

Prochaine séance

La Séance 1 donne une mémoire à l’algorithme : la variable, case nommée qui garde une valeur d’un type donné (entier, réel, booléen, caractère, chaîne) ; l’affectation \(\leftarrow\), qui y range le résultat d’un calcul ; Lire et Écrire, qui relient l’algorithme au clavier et à l’écran ; et la trace qui montre, à chaque pas, la valeur de chaque variable.

Références

  • Cormen — Algorithms Unlocked, MIT Press, 2013 (ch. 1, « What Are Algorithms and Why Should You Care? » : algorithme, correction, terminaison).
  • Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, 4e éd., MIT Press, 2022 (ch. 1, « The Role of Algorithms in Computing », § 1.1 : problème, instance, algorithme).
  • Bhargava — Grokking Algorithms, 2e éd., Manning, 2024 (ch. 1, « Introduction to Algorithms »).
  • Notes de cours en ligne : CS50 (Harvard), 6.100A (MIT), CS106A (Stanford), premières séances sur l’algorithme et le pseudo-code.

Pour cette séance

Les slides

À lire en ligne

Retour au sommet