Le terme algorithme vient du nom de al-Khwārizmī, un mathématicien, astronome et géographe perse (env. 780 - env. 850), qui est notamment l’auteur de Abrégé du calcul par la restauration et la comparaison.
Un algorithme est une suite finie d’instructions logiques à appliquer dans un ordre déterminé à un nombre fini de données pour obtenir un certain résultat.
Affectation, calcul, entrées, sorties
Un algorithme peut être vu comme une « boîte » prenant en entrées certaines données et donnant en sortie le résultat à un problème donné.
La « boîte » peut être vue comme une recette de cuisine dont les étapes sont des instructions logiques interprétables par une machine.
La rédaction d’un algorithme est constituée des étapes suivantes :
- déclaration des variables : les variables sont des objets ayant un type (entier, réel…) auxquelles on peut affecter une valeur ;
- traitement : le traitement est la suite finie d’instructions.
Exemple
Un algorithme peut effectuer une division euclidienne en calculant le quotient $q$ et le reste $r$ de la division euclidienne de $x\in \mathbb{N}$ par $y\in \mathbb{N}$.
Structures principales
Un algorithme est constitué d’une suite instruction. Ces instructions peuvent correspondre à des structures types : structures alternatives ou itératives.
- Structure alternative
La structure alternative permet de réaliser différents traitements suivant si une condition est vraie ou non.
Si condition alors
traitement 1
Sinon
traitement 2
Fin Si
- Structure répétitive
La structure répétitive (ou boucle) permet de réaliser un calcul itératif.
On distingue :
- Le calcul itératif avec un nombre d’itérations donné :
Pour $I$ variant de $I_0$ à $N$
traitement
Fin Pour
- Le calcul itératif avec une fin de boucle conditionnelle :
Tant que condition
Faire traitement
Fin Tant que
Exemple
Pour effectuer une division euclidienne en calculant le quotient $q$ et le reste $r$ de la division euclidienne de $x\in \mathbb{N}$ par $y\in \mathbb{N}$, les instructions sont les suivantes :
