Vouloir écrire des programmes c’est bien, mais garantir qu’ils fourniront le service attendu c’est mieux. Un programme est l’implémentation d’un algorithme dans un langage donné. Ne reste plus qu’à savoir ce qu’est un algorithme (définition)…
Quelle est la définition d’un algorithme ?
Définition
La définition d’un algorithme correspond à une suite finie et non ambiguë d’opérations ou d’instructions permettant de résoudre un problème ou d’obtenir un résultat.
Le terme algorithme a été inventé très tardivement (au IXième siècle) par un mathématicien perse Al-Khwarizmi. Mais cela faisait bien longtemps que l’on en utilisait.
Ils sont partout
Bien que nous n’en ayons pas forcément conscience, les algorithmes sont partout autour de nous. Ils nous sont naturels. L’exemple le plus simple est la recette de cuisine pour illustrer la définition d’un algorithme :
Les étapes de la recette sont bien une suite finie et non-ambigües d’opérations dans le but d’obtenir des crêpes.
Lorsque qu’un passant vous demande son chemin, vous lui indiquer la route en lui donnant une suite d’instructions dans le style « Continuez tout droit sur 3 intersections, puis au feu prenez à droite. Avancez sur 50m, ce sera sur votre gauche ». C’est un algorithme !
Mais nous aurions tout aussi bien pu parler du plan de montage d’un meuble :
Les algorithmes mathématiques
La résolution de problèmes mathématiques se prête bien à la création d’algorithmes. D’ailleurs, les plus anciens algorithmes répertoriés sont issus des mathématiques :
L’algorithme de Héron
Cette méthode permet de calculer une approximation de la racine carrée d’un nombre. Elle est encore appelée méthode babylonienne et elle a été redécouverte en 1896 dans un livre d’Héron d’Alexandrie. Ce scientifique l’a lui-même recopié : on a retrouvé une tablette d’argile datant de 1800 à 1600 avant Jésus Christ comportant une approximation de racine carrée de 2.
Calcul du PGCD par Euclide
Euclide a défini en 300 avant JC environ un algorithme permettant de calculer le plus grand commun diviseur. Mais il semblerait que lui-même n’est que compilé les résultats de mathématiciens ayant vécus avant selon le mathématicien et historien B. L. van der Waerden.
Calcul de PI par Archimède
Archimède a créé, en 250 avant JC, une méthode simple qui permet de calculer une approximation de p grâce à l’aire de polygones inscrits et circonscrits d’un cercle.
Crible d’Eratosthène
Eratosthène de Cyrène, qui a vécu de -276 à -194, a mis en place une méthode très simple pour calculer tous les nombres premiers entre 1 et n en utilisant que des additions. Nous la mettrons en application dans les chapitres suivants.
La notion d’état
« Un algorithme est une suite finie et non ambiguë d’opérations ou d’instructions permettant de résoudre un problème ou d’obtenir un résultat. »
Si nous prenons l’exemple de la recette de cuisine, chaque instruction provoque un changement d’état des éléments initiaux : faire fondre le beurre au micro-onde transforme le beurre solide en beurre liquide. A chaque étape de la recette nous devons stocker le nouvel état du produit dans un contenant (bol, un saladier, etc…).
Par exemple, nous avons tous une boîte ou un pot sur lequel une étiquette est collée avec marqué dessus « farine ». Cette boîte contient une quantité définie de farine : 1kg au début puis à chaque prélèvement la quantité diminue….
L’état est variable 😉
Dans le cadre d’un programme informatique nous aurons exactement le même besoin : stocker le résultat de la transformation. Et pour se faire nous allons utiliser un outil qui nous viens du monde mathématique : une variable. La variable est un peu comme ce pot de farine : c’est une boîte ayant une étiquette avec le nom de la variable indiqué dessus, on y stocke une quantité de données typées (entier ou texte, etc…).
Supposons que l’on souhaite calculer 2 fois le contenu de la variable x plus 3 et stocker le résultat dans la variable y. En langage algorithmique, suivant les conventions, on peut écrire cela de différentes façons :
- 2*x+3ày
- y ß 2*x+3
- y = 2*x+3
- y := 2*x+3
La première de la liste étant celle qui est la plus usitée dans la présentation des algorithmes. Celle avec le ‘=’ est celle qui se rapproche de la plupart des langages de programmation (Python, C/C++, Java, C#, etc…). Si vous voulez en savoir plus sur ces langages, rapprochez-vous de notre expertise Design & Code !
Le langage algorithmique
Afin de pouvoir partager un algorithme, il faut avoir une méthode pour le représenter de façon claire et non ambigüe. Un langage textuel proche du langage parlé est très souvent utilisé : on le définit via des structures de contrôle qui ont chacune leur utilité.
Gestion de cas
La première des structures de contrôle correspond à la gestion de cas.
SI condition est vraie ALORS
Opération 1
SINON
Opération 2
FIN SI
Répétition potentiellement infinie
Répéter une action tant qu’un état n’est pas atteint est quelque chose que nous avons régulièrement besoin de faire. Par exemple, lorsque l’on fait la pâte à crêpes, tant qu’il reste des grumeaux il faut fouetter le mélange.
TANT QUE condition est vraie FAIRE
Opérations
FIN TANT QUE
Répétition finie
Lorsque l’on prépare une mousse au chocolat avec 8 œufs, il faut séparer les blancs des jaunes et on écrirait cela : « pour chaque œuf, séparer les blancs des jaunes et les réserver (les blancs dans un saladier et les jaunes dans un bol) ».
POUR CHAQUE ELEMENT e DE LA LISTE liste FAIRE
action( e )
FIN POUR
Une seconde variante est une itération sur des entiers (une incrémentation de 1 du compteur de boucle i est implicite) :
1 => s
POUR i DE 1 A n FAIRE
s * i -> s
FIN POUR
Ce qui est strictement équivalent à :
1 -> s
1 -> i
TANT QUE i <= n FAIRE
s * i -> s
i + 1 -> i
FIN TANT QUE
Fonctions
Afin de pouvoir réutiliser une suite d’actions sans avoir à la réécrire, il est utile de pouvoir isoler cet algorithme en le nommant. C’est le rôle de la fonction que de permettre d’isoler un sous-algorithme.
FONCTION nom_de_fonction( param_1, param_2, …, param_n )
Action1
Action2
…
Action n
RETOURNE résultat
FIN FONCTION
…
nom_de_fonction( 1, 2, 3, 4 ) -> x
Le principe de la fonction est que le résultat ne doit dépendre que des paramètres en entrée. Une fonction peut appeler d’autres fonctions ; elle peut même s’appeler elle-même auquel cas elle est dite récursive. Un bon exemple étant la fonction « n!=1*2*3*…*n » :
FONCTION factorielle( n )
SI n < 2 ALORS
RETOURNE 1
SINON
RETOURNE n * factorielle( n-1 )
FIN SI
FIN FONCTION
