Kala te souhaite la bienvenueKalaMaths

Algorithme

6ᵉ

Algorithmique

Définition

Une suite d'instructions précises, exécutées dans l'ordre, pour réaliser une tâche.

Pour bien comprendre

Un algorithme n'a rien d'informatique en soi : la division posée en est un, et elle est plus vieille que les ordinateurs. Ce qui le définit, c'est que chaque étape soit exécutable sans hésitation, et que le procédé s'arrête.

Exemple

Une recette de cuisine ou un itinéraire GPS est un algorithme.

Ce qu'il faut savoir

  • Chaque instruction doit être exécutable sans ambiguïté : deux personnes qui le suivent obtiennent le même résultat.
  • Le nombre d'étapes est fini : un procédé qui ne s'arrête jamais n'est pas un algorithme.
  • Il part de données et produit un résultat.
  • Trois structures suffisent à tout écrire : enchaîner des instructions, choisir entre deux chemins, répéter tant qu'une condition est vraie.
  • Deux algorithmes peuvent donner le même résultat en demandant des nombres d'opérations très différents.

Exemples résolus

Écris un algorithme qui calcule la somme des entiers de 1 à 10.

On initialise une somme à 0.
Pour chaque entier de 1 à 10, on l'ajoute à la somme.
À la fin, on affiche la somme, qui vaut 55\mathbf{55}.
La variable initialisée avant la boucle s'appelle un accumulateur : c'est le schéma le plus courant de toute la programmation.

Un algorithme répète « n = n + 1 » tant que n est inférieur à 5, en partant de n = 0. Combien de tours fait-il ?

On déroule : nn vaut 0, le test est vrai, nn devient 1. Puis 2, 3, 4, et enfin 5.
Au cinquième tour, nn vaut 5 : le test « 5 inférieur à 5 » est faux, on sort.
Il y a eu 5\mathbf{5} tours, et nn vaut 5 à la sortie.

Pourquoi l'algorithme d'Euclide s'arrête-t-il toujours ?

À chaque étape, il remplace la paire de nombres par une paire plus petite, et les nombres restent des entiers positifs.
Une suite d'entiers positifs qui décroît strictement ne peut pas être infinie.
L'algorithme atteint donc nécessairement son cas d'arrêt. Exhiber une quantité entière positive qui décroît est la façon standard de prouver qu'un algorithme se termine.

Les erreurs fréquentes

  • Écrire une répétition dont rien ne rapproche la condition d'arrêt : le programme tourne alors indéfiniment.
  • Oublier d'initialiser une variable avant de l'utiliser : la machine ne part pas de 0 toute seule.
  • Croire qu'un algorithme juste est forcément utilisable : il peut demander plus d'opérations qu'une machine n'en fera jamais.
  • Confondre algorithme et programme. L'algorithme est la méthode ; le programme en est une écriture dans un langage donné.

Questions fréquentes

Un algorithme, c'est forcément de l'informatique ?

Non. La division posée, une recette de cuisine ou un protocole de montage en sont. L'informatique n'a fait que donner des machines capables de les exécuter très vite.

Combien de structures faut-il pour écrire n'importe quel algorithme ?

Trois, et c'est un théorème démontré en 1966 par Böhm et Jacopini : enchaîner des instructions, choisir entre deux chemins, et répéter tant qu'une condition est vraie. Aucune quatrième n'est nécessaire.

Comment savoir si un algorithme s'arrête ?

En exhibant une quantité entière positive qui décroît strictement à chaque tour. Une telle suite ne peut pas descendre indéfiniment, donc la répétition finit par s'arrêter.

S'entraîner sur cette notion

Algorithme s'emploie dans la notion « Lire et exécuter un programme », du CM1 à la 2de.

À découvrir aussi

Le pack de révision, gratuit

L'essentiel des dix premiers chapitres du programme, en PDF : ce qu'il faut retenir et les questions qui vérifient que c'est acquis. Puis 5 e-mails sur 14 jours, et c'est tout.

Si tu as moins de 15 ans, demande à un parent de remplir ce formulaire avec son adresse.