Une initiation aux algorithmes

Introduction à l'algorithmique

Qu’est-ce qu’un algorithme ? C’est à cette simple question que nous nous proposons de répondre ici. Pas de présentation compliquée, même pas de schéma (logigramme). Juste une introduction qui s’inscrit dans un cours de mathématiques de classe de seconde. Cette introduction ne se limite d'ailleurs pas aux maths (voir par exemple les algorithmes en photo numérique, ressource du cours de SNT)

Définitions

L’algorithme tire son nom du mathématicien et astronome perse al-Khwarizmi, né dans les années 780 dans la région du Khwaresm (actuelle frontière entre l'Ouzbékistan et l'Iran). Dans notre alphabet son nom n’est pas fixé et vous trouverez de nombreuses orthographes au fil de vos lectures. Le mot algèbre est issu du titre de l'un de ses ouvrages.

C'est le mathématicien français Émile Borel qui a donné une définition proche de son sens actuel au terme algorithme, en 1912 : « une règle automatique formelle et précise ».

Enfin, selon le Larousse encyclopédique (2 vol.), un algorithme est « une suite finie d’opérations élémentaires constituant un schéma de calcul ou de résolution d’un problème ». C’est l’outil de base de la programmation informatique.

La science des algorithmes est l’algorithmique.

Langage

Un algorithme peut s’écrire dans un langage « naturel » (pseudo-code) ou être formulé dans un langage propre à un environnement logiciel (code).

Tout programme est donc la traduction d’un algorithme. Les langages de programmation sont nombreux (Java, Python…) et ne doivent pas être confondus avec des langages purement descriptifs (HTML…).

Exemples

De nombreuses activités de la vie courante sont des processus. Par exemple, les tâches que nous enchaînons chaque matin avant d’aller travailler, la réalisation d’une recette de cuisine ou encore le chemin à emprunter pour nous rendre d’un endroit à un autre peuvent être présentés comme des algorithmes.

En mathématiques, on étudie l’algorithme d’Euclide au collège. Mais toutes les techniques peuvent être présentées sous forme d’algorithmes. Les plus simples sont programmables sur calculatrice.

Voyons à présent de quoi se compose un algorithme simple.

Variables et affectations

Une variable est une sorte de boîte, repérée par un nom, qui contient une information. Ce peut être un nombre sur lequel on effectue des calculs (variable numérique), un nombre qui au contraire ne peut pas faire l'objet d'un calcul (par exemple un matricule), une date, un nom, etc.

L’affectation est le fait d’attribuer une valeur à une variable.

Si vous remplissez un formulaire, vous trouvez les variables nom et date de naissance auxquelles vous affectez vos propres coordonnées. L’important est de bien distinguer la VARIABLE de la VALEUR qu’elle prend.

La valeur d'une variable peut changer au cours du traitement.

Le type de la variable détermine la façon dont elle peut être traitée. On peut citer les types suivants :

• Nombre entier
• Nombre flottant (avec décimales)
• Chaîne de caractères (ou de chiffres avec lesquels on ne peut pas faire de calcul, par exemple un numéro de téléphone)
• Booléen (vrai ou faux, oui ou non...)
• Date (avec un format date prédéterminé)
• Liste (suite ordonnée d'objets).

Structure

- La déclaration de variable : par cette instruction on donne un nom à une variable et on précise sa qualité (nombre entier, nombre avec deux décimales, date de format JJ/MM/AA…). Comme cette étape n'existe pas avec tous les langages de programmation, elle ne sera pas reprise dans les algorithmes ci-dessous (ni dans ceux des autres pages).

- L’entrée : une instruction permet d’entrer une valeur pour la stocker dans une variable. En langage naturel, cette instruction peut être saisir, lire ou demander.

Lorsqu’une valeur figure dans le programme, on dit que la variable est initialisée. Au cours du traitement, elle peut changer de valeur.

Notez qu'avec certains langages de programmation, la déclaration et l'initialisation peuvent être simultanées (voir les variables avec Python).

- La sortie : un résultat est envoyé sur un périphérique de sortie (écran, imprimante, haut-parleur…). En langage naturel : afficher, imprimer…

- La structure : en langage naturel, un algorithme comporte trois phases : l’entrée ou l’initialisation, le traitement et la sortie.

Pour remplacer l'expression « prend la valeur », nous nous servirons d'une flèche orientée à gauche.

Exemple d’une multiplication par 2 :

Évidemment, ce traitement est un peu léger… On remarque qu’il n’a pas été nécessaire d’introduire deux variables X et Y, avec Y qui serait le double de X. Il est important de garder ce « sens de l’économie » lorsqu’on passe à des programmes lourds pour ne pas complexifier inutilement les algorithmes et allonger le temps de traitement.

Les processus moins basiques font intervenir des instructions conditionnelles, des boucles et des fonctions.

Note : dans l'algorithme ci-dessus les étapes ont été nommées par souci pédagogique. Mais depuis l'actuel programme de seconde, cette présentation ne vous est plus demandée.

Exercice

Écrire en langage naturel un algorithme qui demande une température en degrés Celsius (C) pour donner son équivalent en degrés Farenheit (F). Pour mémoire : F = 32 + 1,8C.

Corrigé

Avec calculatrice programmable

Si vous souhaitez vous initier à la programmation sur une TI-82 ou TI-83, rendez-vous en page initiation à la programmation sur TI (exemple d'un algorithme permettant de déterminer le volume d'un cône).