Comprends ça pour savoir faire un algorithme !

A quoi penses-tu quand tu entends le mot « algorithme » ? Perso, je pense plus à de l'informatique qu'aux Maths. Pourtant depuis quelques années, savoir faire un algorithme fait partie du programme de Maths...

Et c'est une très bonne chose ! Parce que quand on veut utiliser les Maths pour résoudre des problèmes du monde réel grâce à l'informatique, il faut passer par les algorithmes. Comme tu le sais sûrement, dans un ordinateur tout se fait sous forme de suites d'instructions ou d'opérations, c'est à dire d'algorithmes.

Dans cet article, je te rappelle les 2-3 trucs que tu dois bien comprendre sur les algorithmes pour ne pas être perdu au Lycée. Tout au long, j'illustre mes propos d'exemples simples et je finis l'article par une application niveau lycée sur les suites. Si tu veux d'autres exemples, télécharge la Fiche Récap !

Avant d'être un programme informatique, un algorithme est une suite d'instructions ordonnées qui a pour but de trouver un résultat à partir de données connues. Et si tu veux pouvoir faire un algorithme qui fonctionne, tu dois bien connaitre les 2 outils principaux. Pour cela, tu dois savoir répondre à ces questions :

✪ Les variables et leurs types.

Stocker de l'information, l'art de la variable.

Comme son nom l'indique plutôt bien, une variable est quelque chose qui va pouvoir varier tout au long de l'algorithme ! Si ça t'aide, tu peux les voir comme des boites distinctes dans lesquelles tu vas pouvoir stocker de l'information. Voici deux exemples qui devraient te parler : 

Des types de variables variés...

Rien que dans les 2 exemples que je viens de prendre, tu vois qu'on peut avoir différents types de variables. D'un côté, un nombre décimal pour la note, et de l'autre une liste de caractères pour le message Twitter !

Même si je crois que ça aide à comprendre ce qu'est une variable, tu peux oublier les variables de type chaîne de caractères car tu ne vas pas les utiliser au lycée. Par contre, tu dois connaitre les différents types de variables numériques !

Et comme tu le sais, il existe plusieurs ensembles possibles pour les chiffres : les naturels, les entiers, les décimaux, les réels, les complexes. Informatiquement parlant, on ne fait généralement la distinction qu'entre les entiers (relatifs) et les réels. Pour les complexes, les calculettes les acceptent, même si c'est un peu différent dans la vraie vie.

...mais seulement 3 à savoir distinguer !

Par conséquent, quand on te demande de faire un algorithme, tu dois être capable de dire pour chaque variable si elle est de type entier, réel ou complexe. 

Pour être bien clair, tu n'as pas besoin de faire la distinction pour programmer un algorithme dans ta calculette. En effet, elle va le faire pour toi. Mais on peut te demander d'écrire l'algorithme sur ta copie, et pas seulement de le programmer. Dans ce cas, tu devras savoir donner le type des variables que tu utilises 🙂

✪ Les 3 Instructions à bien comprendre.

Condition Si/Alors/Sinon : Appliquer une opération selon la situation.

Comme dans la vie, il arrive qu'au sein d'un algorithme tu aies besoin de faire une opération différente suivant les conditions dans lesquelles tu es. Par exemple, pense à l'algorithme qui s'applique quand tu veux traverser à un passage piéton : Si il n'y a pas de voiture, alors tu peux traverser, sinon tu attends.

C'est l'instruction de condition Si/Alors/Sinon, ou en anglais If/Then/Else (les langages de programmation sont généralement en anglais...). Quand tu veux décrire dans un algorithme le fait qu'une opération se fait dans un cas et qu'une autre se fait dans le cas contraire, c'est la condition Si/Alors/Sinon que tu dois utiliser.

Dans la dernière partie de cet article, je te donne un exemple concret en termes de Maths !

Boucle Pour : Répéter des opérations un nombre de fois donné.

La deuxième instruction correspond à une situation qui se répète un nombre de fois connu et fixé. Par exemple, tu sais que ton réveil doit sonner à 7h lundi, mardi, mercredi, jeudi, vendredi. Eh bien au lieu de les énumérer un par un, tu vas compacter tout ça en disant que pour tous les jours de lundi à vendredi, ton réveil sonne à 7h.

Si tu veux un exemple plus mathématique, en voilà un. On te demande de tracer un cercle centré en (0,0) de rayon 1. Puis un cercle centré en (0,0) de rayon 2. Puis encore un cercle centré en (0,0) de rayon 3... etc jusqu'à un rayon 100. Tu pourrais décider de faire un algorithme de 100 lignes dans lequel chaque ligne correspond à "tracer un cercle de rayon N". Mais il y a beaucoup plus simple, il suffit de dire que pour les valeurs entières n de 1 à 100, tu traces un cercle centré en (0, 0) de rayon n.

Autrement dit, tu vas utiliser une boucle pour un nombre de valeurs données et appliquer la même opération pour chacune des itérations de cette boucle. C'est la boucle Pour ou boucle For en anglais. Note bien que l'opération est la même mais que ses paramètres peuvent changer (comme le rayon dans mon exemple.).

Boucle Tant Que : Répéter jusqu'à ce qu'une condition soit vérifiée.

Enfin la dernière instruction est pour le cas où tu veux répéter une opération tant que qu'une condition n'est pas vérifiée. Par exemple, tant que le contrôle n'est pas demain, tu repousses les révisions. Ou encore, tant que tu n'atteins pas 16 de moyenne en Maths, tu révises 2h par soir.

Cette instruction est la boucle Tant que ou boucle While en anglais. Si tu veux un exemple mathématique, je t'en donne un dans la Fiche Récap. Tu y verras comment on peut estimer la limite d'une fonction avec un algorithme.

A chaque fois, que tu vas devoir répéter une opération sans savoir à l'avance le nombre de répétitions, tu vas devoir utiliser une boucle Tant que. Cependant fais attention à deux choses ! Premièrement, tu dois bien définir la condition d'arrêt de la boucle. Autrement dit, trouver ce qui fait que tu vas arrêter de répéter l'opération.

Et deuxièmement, il y a toujours un risque de créer une boucle infini si ta condition n'est jamais vérifiée... Il faudra forcer l'arrêt de ton programme si c'est le cas !

Les Suites : exemple parfait pour apprendre à faire un algorithme !

Quand tu as découvert les suites, tu as aussi découvert la récurrence. Et la récurrence n'est rien d'autre que l'art de répéter ! C'est la raison pour laquelle les suites sont un support parfait pour apprendre à faire un algorithme. J'ai donc choisi de te présenter un court exemple qui les utilisent.

Algorithme de calcul de la somme partielle d'une suite.

Dans cet exemple, le but est simple : calculer la somme des termes d'une suite jusqu'à un certain rang N. Pour compliquer un peu l'exercice, je prends la suite définie comme ceci :

Ce que l'on sait.

On connait une définition de la suite u_n donnée par u_0 et par la formule de récurrence qui donne le terme u_{n+1} en fonction du terme u_n. Par contre, on ne connait pas N, il faudra donc demander au début de l'algo une valeur pour N.

Ce que l'on veut.

On a dit qu'on voulait calculer la somme des premiers termes jusqu'au rang N. C'est à dire des N+1 premiers termes puisque le premier rang est 0. En termes de Maths, on veut donc calculer u_0 + u_1 + u_2 + ... + u_N.

Les variables en jeu.

Pour écrire cet algorithme, de quelles variables a-t-on besoin ? Au minimum, on veut stocker la valeur de la somme partielle s, le rang n du terme actuel et le dernier rang N de la somme ainsi que la valeur du terme précédent de la suite qu'on appellera u.

En effet, la suite est définie par récurrence, il faut donc connaitre le terme précédent pour calculer le terme courant. Comme toujours avec les suites, les rangs n et N sont des entiers et les valeurs de la suite u_n ainsi que leur somme s sont des réels.

Faire un algorithme pour cet exemple.

Décrivons les étapes qui nous permettent de calculer cette somme partielle :

Étape 0.   Je définis une valeur de N.
Étape 0.   J'affecte les valeurs initiales : s = u_0 et u = u_0.
Étape 1.   Je calcule u_1 à partir de u_0 et je l'ajoute à s.
Étape 2.   Je calcule u_2 à partir de u_1 et je l'ajoute à s.
[...]
Étape N.   Je calcule u_N à partir de u_{N-1} et je l'ajoute à s.
Étape N+1.   J'affiche la valeur de la somme partielle s.

Là, je ne doute pas que tu as remarqué que l'on répète N fois la même chose ! Par conséquent, il faut faire une boucle Pour sur le rang n de la suite, commençant à 1 et allant jusqu'à N. Dans cette boucle, il faut calculer la valeur de la suite pour le rang n à partir du terme précédent u et ajouter sa valeur à la somme s. Au final, on obtient l'algorithme suivant :

Une seule remarque sur cet algorithme : tu vois que j'ai remplacé la condition "n est pair" par "le reste de la division de n par 2 est nul". Si ce n'est pas clair pour toi, prends le temps d'y réfléchir...

Allez, il ne te reste plus qu'à le programmer avec n'importe quel langage de programmation (je te conseille Python, si tu n'y connais rien et que ça t'intéresse...) et à vérifier que ça donne le bon résultat 🙂 !

Qu'est-ce qui te pose le plus de problèmes avec les algorithmes ? Réponds-moi dans les commentaires et je ferai ce qu'il faut pour t'aider !