Semaine 1 · Jour 5 · 420-SN1

LES ALGORITHMES

→
→
→
Une recette d'étapes : séquence, décision, répétition
🧑‍🚀 EN SAVOIR PLUS · D'OÙ VIENT LE MOT

« Algorithme » : un nom, une idée vieille de 12 siècles

Al-Khwârizmî · vers 820

al-jabr

▸ Ce savant perse écrit un traité de méthodes de calcul. Traduit en latin, son nom devient « Algoritmi » : c'est de là que vient le mot algorithme.

▸ Son livre al-jabr a aussi donné le mot algèbre. Un algorithme = une suite finie d'étapes pour résoudre un problème.

Ada Lovelace · 1843

▸ Elle INVENTE la programmation en adaptant le premier algorithme pour une machine. Visionnaire, elle a IMAGINÉ ce qu'une machine pourrait faire un jour :

Ada Lovelace

🎵 « La machine pourrait composer des morceaux de musique de n'importe quel degré de complexité. »

Du problème à l'algorithme

Un algorithme, c'est comme une recette : une suite d'étapes claires et ordonnées qui mènent au résultat. Avant de coder, on suit toujours le même chemin :

1Comprendre
Que demande le problème ? Quelles données en entrée, quel résultat en sortie ?
2Décomposer
Couper en petites étapes simples, une à la fois.
3Écrire les étapes
En français ou en pseudocode, sans se soucier de la syntaxe.
4Traduire en code
Chaque étape devient du Python.

La machine est obéissante mais bête : elle fait exactement ce qu'on écrit, dans l'ordre où on l'écrit. Tout l'art de l'algorithme est de lui donner les bonnes étapes, dans le bon ordre.

Entrée → Traitement → Sortie

Presque tout programme suit le même plan en trois temps : il reçoit des données, les transforme, puis rend un résultat. C'est le squelette de l'énoncé du Projet 1 (les mesures du volcan de Maya).

📋
ENTRÉE

les données de départ

10 mesures : 12.1, 12.4, …
→
⚙️
TRAITEMENT

moyenne, étendue,
détecter l'aberrante

→
🖥️
SORTIE

le rapport affiché
+ le fichier .csv

Moyenne : 411.4 °C

Avant de coder, repère toujours ces trois blocs dans l'énoncé : « qu'est-ce qui entre ? », « que faut-il calculer ? », « qu'est-ce qui sort ? ». Le reste du programme remplit le bloc du milieu.

Chaque fonction : le même plan, en miniature

Tu as déjà appelé des fonctions Python (print, len, round, input…). Chacune est un petit Entrée → Traitement → Sortie : on lui donne quelque chose, elle le transforme, elle rend un résultat.

len(mesures)
[12, 19, 7] → len → 3
round(3.14159, 2)
3.14159, 2 → round → 3.14
input("Nom ?")
"Nom ?" → input → ce que tape l'usager

Ton programme entier est un grand Entrée-Traitement-Sortie ; chaque fonction qu'il appelle est un petit Entrée-Traitement-Sortie à l'intérieur. Des plans dans des plans - presque une fractale. 🌀

Premier principe : la séquence

# exécuté dans CET ordre a = 3 b = 4 somme = a + b print(somme)
↓
une instruction
après l'autre
↓

Par défaut, un programme s'exécute ligne par ligne, de haut en bas. Chaque ligne se termine avant que la suivante commence. somme = a + b n'a de sens que parce que a et b existent déjà au-dessus.

L'ordre change tout : x = y puis y = x

x = 4 y = 7 x = y y = x
#
x
y
Instruction
1
4
x = 4
2
4
7
y = 7
3
7
7
x = y ← 4 écrasé !
4
7
7
y = x

On voulait peut-être échanger x et y ? Raté : les deux valent 7. Dès la ligne 3, x = y écrase le 4 ; à la ligne 4, y = x ne fait que recopier 7. La valeur 4 est perdue.

On inverse les deux dernières lignes

x = 4 y = 7 y = x x = y
#
x
y
Instruction
1
4
x = 4
2
4
7
y = 7
3
4
4
y = x ← 7 écrasé !
4
4
4
x = y

Exactement le même 4 instructions, juste 2 lignes inversées - et le résultat est tout autre : les deux valent 4. En séquence, l'ordre n'est pas un détail. (Pour vraiment échanger x et y, il faudra une astuce : on la verra dans les patrons. 😉)

Le super-pouvoir : tracer à la main

Pour comprendre (et réussir un examen !), joue à l'ordinateur : prends une feuille, fais une colonne par variable, et exécute chaque ligne une à une en mettant à jour les valeurs.

1Une colonne par variable
Dessine une boîte (ou un verre) pour chaque variable du programme.
2Ligne par ligne
Exécute la 1re instruction, écris la valeur. Puis la 2e, etc.
3Barre l'ancienne valeur
Quand une variable change, raie l'ancienne et écris la nouvelle à côté.
4Lis la dernière ligne
L'état final = ce que vaut chaque variable à la fin.

C'est exactement ce que font les tableaux ci-dessus. Tracer à la main ne ment jamais : si tu hésites sur ce que fait un code, trace-le plutôt que de deviner.

Avec un if, certaines lignes sautent

note = 72 if note >= 90: print("A") elif note >= 70: print("B") else: print("C")
Ligne
Ce que fait la machine
Test
Affichage
1
note = 72
—
2
if note >= 90 ?
FAUX
print("A") sauté
3
elif note >= 70 ?
VRAI
→ on exécute son bloc
3
print("B")
—
B
4
else: print("C")
JAMAIS
ignoré

Dès qu'un test est vrai, on exécute son bloc et on saute tout le reste de l'alternative. Certaines lignes ne s'exécutent jamais - c'est le principe même de la condition.

Dessiner le chemin : l'organigramme

Un organigramme (ou diagramme de flux) dessine le chemin que suit la machine. Trois formes suffisent :

une action
Rectangle = une instruction
vrai ?
Losange = une décision (oui / non)
↓
Flèche = le sens du flux
début / fin
Stade = entrée et sortie

On suit les flèches : à chaque losange, on prend la sortie vrai ou faux. C'est la même logique que le code - en image.

Organigramme : si et si / sinon

si agir seulement si vrai
DÉBUT froid? vrai manteau faux SORTIR
if froid: print("manteau")
si / sinon un chemin OU l'autre
DÉBUT pair? vrai afficher"pair" faux afficher"impair" FIN

À gauche, le bloc ne s'exécute que si c'est vrai. À droite, on prend toujours un des deux chemins - jamais les deux, jamais aucun.

Organigramme : si / sinon si / sinon

DÉBUT ≥ 90 ? vrai note "A" faux ≥ 70 ? vrai note "B" faux sinonnote "C" FIN
if note >= 90: mention = "A" elif note >= 70: mention = "B" else: mention = "C"
On descend les losanges l'un après l'autre. Au premier vrai, on agit et on file vers la FIN.

Chaque elif = un nouveau losange testé seulement si tous les précédents étaient faux. Le else est le chemin « faux partout » : il n'a pas de losange.

Organigramme : les boucles while et for

while répéter TANT QUE vrai
DÉBUT compteur≤ 5 ? vrai afficher,compteur += 1 on recommence faux FIN
for répéter POUR chaque élément
DÉBUT encore unélément ? vrai traiterl'élément élément suivant faux FIN

La flèche violette de retour, c'est ça « boucler » : on revient tester la condition. while teste une condition ; for teste s'il reste un élément. Dès que c'est faux, on sort.

Comparer une variable à plusieurs valeurs : match

if / elif / else la cascade
if jour == "lun": print("Cours") elif jour == "sam": print("Repos") else: print("Étude")
match / case Python 3.10+
match jour: case "lun": print("Cours") case "sam": print("Repos") case _: print("Étude")

Même résultat. match brille quand on compare toujours la même variable à des valeurs : plus lisible qu'une longue chaîne de elif jour == .... case _ est le « sinon ». Sous le capot, c'est la même sélection.

Patron nº1 : l'accumulateur

Un patron est un squelette de code qu'on réutilise tout le temps. L'accumulateur cumule un résultat tour après tour : initialiser (effet nul) → parcourir → accumuler.

total = 0 # 1. initialiser (effet nul) for valeur in mesures: # 2. parcourir total = total + valeur # 3. accumuler print(total)
Somme → on part de 0
Produit → on part de 1
(l'effet nul de chaque opération)

La variable accumulateur vit en dehors de la boucle (sinon elle se remettrait à zéro à chaque tour). On la lit après la boucle. Même squelette pour une moyenne, un compte, un maximum…

Patron nº2 : chercher dans un tableau

mesures = [12, 19, 7, 22, 15] cible = 7 trouve = False # drapeau baissé 🚩 for valeur in mesures: if valeur == cible: trouve = True # on lève le drapeau break # inutile de continuer print(trouve)
True
Le drapeau trouve démarre à False. Dès qu'on rencontre la cible, on le lève (True).

Patron parcours + condition. Le break est un bonus d'efficacité : trouvé une fois, pas besoin de finir le tableau. Variante utile : garder à quelle position on l'a trouvé.

Patron nº3 : trouver le maximum

mesures = [12, 19, 7, 22, 15] maximum = mesures[0] # on parie sur le 1er for valeur in mesures: if valeur > maximum: maximum = valeur # un nouveau champion print(maximum)
22
On parie sur le 1er élément, puis on garde le plus grand vu jusqu'ici.

Un accumulateur déguisé : maximum cumule « le meilleur jusqu'ici ». Pour le minimum, on change juste > en <. Idéal en sciences : la température la plus haute, la mesure la plus forte…

Patron nº4 : compter sous condition

mesures = [12, 19, 7, 22, 15] seuil = 15 compte = 0 # on n'a rien compté for valeur in mesures: if valeur > seuil: compte = compte + 1 # un de plus print(compte)
2
Seules 19 et 22 dépassent 15 : le compteur monte deux fois.

Encore un accumulateur : il part de 0 et grimpe de 1 seulement si la condition est vraie. Combien de mesures hors-norme ? Combien d'élèves ont la note de passage ? Même squelette.

Rappel : pourquoi x = y ne suffit pas

x = 4 y = 7 x = y
On voulait échanger... mais on vient d'écraser le 4. Il n'existe plus nulle part.
#
x
y
Instruction
1
4
x = 4
2
4
7
y = 7
3
7
7
x = y ← 4 écrasé !

Comme tout s'exécute séquentiellement (vu au tout début), x = y remplace le contenu du verre x avant qu'on ait pu sauver le 4. Il faut donc un verre vide de côté pour le garder : c'est le rôle de temp dans le patron qui suit. →

Patron nº5 : échanger x et y (la variable temporaire)

temp = x # x de côté x = y # x prend y y = temp # y reprend l'ancien x
Pour échanger deux verres pleins, il faut un 3e verre vide : temp.
#
x
y
temp
Instruction
0
4
7
départ
1
4
7
4
temp = x
2
7
7
4
x = y
3
7
4
4
y = temp ✅

Cette fois c'est vraiment échangé : x = 7, y = 4. Sans temp, x = y écraserait le 4 (vu en séquentialité !). Raccourci Python une fois compris : x, y = y, x.

Planifier en pseudocode avant de coder

Le pseudocode décrit les étapes en langage presque naturel, sans la syntaxe exacte d'un langage. On réfléchit à l'algorithme, puis on le traduit en Python.

PSEUDOCODE la logique
maximum ← le premier élément POUR chaque valeur de la liste SI la valeur est plus grande que le maximum ALORS maximum ← la valeur AFFICHER le maximum
PYTHON la traduction
maximum = mesures[0] for valeur in mesures: if valeur > maximum: maximum = valeur print(maximum)

Le pseudocode est indépendant du langage : la flèche ← dit « reçoit », les mots POUR / SI / ALORS sont en français. C'est le plan ; le code n'est que la traduction. Concevoir d'abord, coder ensuite.

Tout algorithme tient en 3 structures

SÉQUENCE

↓ ↓ ↓

Une instruction après l'autre, dans l'ordre.
Jour 1

SÉLECTION

if / else

Choisir un chemin selon une condition.
Jour 2

ITÉRATION

for / while ↻

Répéter tant qu'il le faut.
Jour 3

Avec seulement ces trois briques - et les variables (Jour 1) et les listes (Jour 4) pour ranger les données - on peut écrire n'importe quel programme. C'est un résultat prouvé (théorème de Böhm-Jacopini). La semaine 1, c'est exactement ça. 🎉

À TOI DE JOUER

Trace à la main (colonne par variable) avant d'exécuter :

a=2; b=5
a=b; b=a → ?
temp=a
a=b; b=temp → ?
note=70
A / B / C → ?
code.experimentations.xyz/calepins/semaine-1-jour-5-algorithmes/

AU TRAVAIL !

→
↻
Séance 1-5 : séquence, décision, répétition - tu sais déjà penser en algorithmes
⤺ Refermer le diaporama