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.

 

Définitions

L’algorithme tire son nom du mathématicien et astronome perse al-Kharezmi, 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 » 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 et l’algorithme de Dijkstra en terminale ES (spé. maths). 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

Un 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 (variable alphanumérique, 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
  • Booléen (vrai ou faux)
  • Date (avec un format date prédéterminé)
  • Alphanumérique (un nombre avec lequel on ne peut pas faire de calcul, par exemple un matricule).
  • 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.

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 :

Entrée saisir X
Traitement X ← 2 × X
Sortie afficher X

É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é

saisir X
X ← 1,8 × X
XX + 32
afficher X

 

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).

 

programme du sandwich