Qu'est-ce qu'un algorithme ?
Un algorithme, c'est une suite d'instructions précises pour arriver à un but. Une recette de cuisine est un algorithme : une liste d'étapes, dans l'ordre, qui se termine par un gâteau.
Le défi des instructions exactes
Dans cette vidéo, des enfants écrivent les instructions pour préparer un sandwich, et leur père les exécute au pied de la lettre, sans jamais rien deviner.
Résultat : la catastrophe. « Mets le beurre de cacahuète sur le pain » ? Le père pose le pot, fermé, sur le paquet de pain. À chaque instruction, il y a un sous-entendu (ouvrir le pot, sortir une tranche, étaler avec un couteau) que nous, humains, comblons tout seuls sans même y penser.
La leçon
Notre langage de tous les jours est plein d'implicites. Entre humains, ça passe : on se comprend à demi-mot. Mais une machine ne « comprend » pas, elle exécute. Elle ne devine jamais : si une consigne peut se comprendre de deux façons, elle prendra la mauvaise.
Conclusion : pour parler à une machine, notre langage naturel ne convient pas, il est trop ambigu. Il faut inventer des langages sans implicite, où chaque instruction ne veut dire qu'une seule chose. C'est tout l'enjeu de la programmation, et on va commencer par en fabriquer un nous-mêmes.
Un langage sans ambiguïté
On veut expliquer à quelqu'un comment tracer un dessin sur une grille, sans lui montrer le dessin. On va inventer un langage : une petite liste de mots-instructions.
Mais attention : même un mot comme droite ne dit pas tout. Est-ce tourner à droite, ou se déplacer vers la droite ? Et de combien : d'une case, de deux ? Tant qu'on ne l'a pas défini précisément, il reste un implicite. Chaque mot-instruction doit donc recevoir une définition qui ne laisse aucun doute.
Fixons deux mots et définissons-les exactement (une case, c'est une cellule de la grille) :
droite: trace un trait d'une case vers la droitebas: trace un trait d'une case vers le bas
Exercice 1 - Décoder un tracé
On part du coin en haut à gauche. On exécute :
Dessine sur une feuille le trait obtenu.
Correction
Un trait qui va deux cases à droite, puis une case en bas, puis encore une case à droite. Une sorte de marche d'escalier.
Le problème, c'est que ces deux mots ne suffisent pas à tout dessiner : impossible de remonter ou d'aller à gauche.
Exercice 2 - Compléter le langage
Propose deux nouveaux mots-instructions pour pouvoir dessiner n'importe quel trait sur la grille. Explique précisément ce que fait chacun.
Correction
Par exemple gauche (un trait d'une case vers la gauche) et haut (un trait d'une case vers le haut). Avec droite, gauche, haut, bas, on peut tracer tous les chemins de la grille.
Quand ça se répète
Regarde ce programme :
Cinq fois la même instruction, c'est long et pénible à écrire. Les langages de programmation offrent un raccourci pour dire « répète ceci N fois ». On l'apprendra bientôt en Python. Retiens l'idée : repérer une répétition, c'est un geste essentiel en informatique.
Exercice 3 - Repérer les répétitions
Dans le programme ci-dessous, repère les groupes d'instructions identiques qui se suivent, et réécris-le en français avec des « répète ... fois ».
Correction
Répète 3 fois droite, puis répète 2 fois bas, puis 1 fois droite.
Une instruction par ligne
Écrire « répète 3 fois droite » en français, c'est encore une phrase, et les phrases redeviennent vite ambiguës. On va donc se donner des règles d'écriture strictes, plus proches d'un vrai langage de machine :
- une seule instruction par ligne ;
- pour répéter, on écrit
répète N fois :puis, en dessous, les instructions à répéter décalées vers la droite. Ce décalage s'appelle l'indentation.
Par exemple :
Ce programme veut dire : droite, droite, droite, puis bas.
Le décalage n'est pas décoratif : il indique exactement ce qui est à l'intérieur de la répétition et ce qui est à l'extérieur. Ici droite est indenté, donc répété 3 fois ; bas ne l'est pas, donc il est fait une seule fois, après la répétition. Cette écriture en blocs indentés est précisément celle qu'on retrouvera en Python.
Exercice 4 - Lire un programme indenté
Quelle suite d'instructions simples ce programme représente-t-il ?
Correction
droite, bas, droite, bas, droite.
Le bloc indenté (droite puis bas) est répété 2 fois. Le dernier droite n'est pas indenté : il est donc exécuté une seule fois, à la fin.
Il nous manque des instructions
Jusqu'ici, chaque déplacement trace un trait : autrement dit, le crayon est toujours posé sur la feuille. Du coup, on ne peut dessiner que des figures d'un seul tenant.
Comment dessiner deux traits séparés ? Il faudrait pouvoir se déplacer sans tracer. Notre langage en est incapable : il lui manque des instructions. Ajoutons-les :
lève: lève le crayon (les déplacements suivants ne tracent plus rien)baisse: baisse le crayon (les déplacements tracent de nouveau)
Voici alors le langage complet. Au départ, le crayon est baissé.
| Instruction | Effet |
|---|---|
droite |
se déplacer d'une case vers la droite |
gauche |
se déplacer d'une case vers la gauche |
haut |
se déplacer d'une case vers le haut |
bas |
se déplacer d'une case vers le bas |
lève |
lever le crayon (se déplacer sans tracer) |
baisse |
baisser le crayon (tracer de nouveau) |
répète N fois : |
répéter le bloc indenté N fois |
Un déplacement trace un trait si le crayon est baissé.
Lire du code
On commence par le plus important : savoir lire un programme, c'est-à-dire dire ce qu'il dessine sans l'exécuter en vrai. Pour chaque exercice, on part du coin en haut à gauche.
Exercice 5 - Que dessine ce programme ?
Correction
Un escalier qui descend vers la droite, de 3 marches (à chaque tour : une case à droite, une case en bas).
Exercice 6 - Avec le crayon levé
Correction
Deux traits horizontaux de 2 cases chacun, séparés par un espace d'une case (le déplacement fait crayon levé ne trace rien).
Exercice 7 - Une figure fermée
Correction
Un rectangle de 2 cases de large et 1 case de haut. Le tracé revient à son point de départ.
Écrire du code
Maintenant, à toi d'écrire les programmes qui tracent les figures ci-dessous. Utilise répète dès que tu repères une répétition. On part toujours du point rouge (le coin en haut à gauche).
Exercice 8 - Un trait horizontal
Écris un programme qui trace ce trait.
Exercice 9 - Un carré
Écris un programme qui trace ce carré (3 cases de côté).
Exercice 10 - Un escalier
Écris un programme qui trace cet escalier (4 marches).
Exercice 11 - Deux traits séparés
Écris un programme qui trace ces deux traits verticaux (3 cases chacun, séparés par un espace d'une case).
Ce qu'on retient
- Un algorithme est une suite d'instructions précises et sans ambiguïté.
- Un langage est un ensemble de mots-instructions que la machine sait exécuter.
- Chaque instruction doit avoir une définition précise : un mot comme
droitene dit rien tant qu'on n'a pas fixé ce qu'il fait (tourner ? se déplacer ? de combien ?). - On écrit une instruction par ligne, et on indente (décale vers la droite) le bloc d'instructions à répéter.
- On apprend d'abord à lire un programme (dire ce qu'il dessine), avant de savoir en écrire un.
- Cette écriture en blocs indentés est celle du Python, qu'on retrouvera très vite.
Et ensuite
À la prochaine séance, on s'entraîne à exécuter un programme pas à pas, comme le ferait une machine, avec Compute It.