Les algorithmes
Au IXème siècle, Al-Khwârizmî est un mathématicien perse qui a écrit des oeuvres en arabe sur l'algèbre.
Au XIIème siècle, l'une de ses oeuvres, "Le calcul indien", a été "latinisé" sous le nom "Algoritmi de numero Indorum". Algoritmi viendrait de la latinisation de son nom de famille par différents traducteurs, qui aurait eu comme traduction Alchoarismi, puis Algorismi, Algorismo et enfin Algoritmi.
"Algorithme" est un terme issu de la transformation de son nom de famille.
Les premiers algorithmes datent cependant d'il y a bien plus longtemps. On trouverait les premiers chez les Babyloniens, en -3000 avant J.C.
Qu’est-ce qu’un algorithme ?
Dans la vie quotidienne, nous réalisons souvent des suites d’actions pour atteindre un objectif : préparer un gâteau, suivre un itinéraire, résoudre un problème de maths, etc.
Ces suites d’instructions organisées, précises et finies s’appellent des algorithmes.
Un algorithme est une suite ordonnée d'actions permettant de résoudre un problème.
Exemple simple :
Problème : acheter une baguette à la boulangerie.
Un algorithme simple pour faire l'achat serait :
- Prendre de l’argent.
- Aller à la boulangerie.
- Demander une baguette.
- Payer.
- Revenir chez soi.
Les 5 caractéristiques d’un algorithme
Selon Donald Knuth (informaticien et mathématicien né en 1938), un algorithme possède 5 propriétés :
| Propriété | Explication |
|---|---|
| Finitude | L’algorithme doit se terminer. |
| Précision | Chaque étape doit être décrite sans ambiguïté. |
| Entrées | Ce que l’algorithme reçoit. |
| Sorties | Ce qu’il produit. |
| Rendement | Les étapes doivent être simples à exécuter. |
Pourquoi écrit-on des algorithmes ?
Parce qu’un ordinateur ne devine rien.
Pour qu’il exécute une tâche, il faut décomposer un problème en petites actions simples.
Un algorithme est donc une méthode pour résoudre un problème, que l’on pourra ensuite traduire dans un langage comme Python.
Comment écrire un algorithme ?
Le langage naturel
On commence toujours par une description en français, simple et claire.
Exemple :
Calculer la surface d’un disque : multiplier π par le rayon au carré.
Le pseudo-code
Un algorithme a besoin d’une organisation spécifique lors de son écriture; plusieurs étapes sont nécessaires :
- Entête : On précise le nom de l’algorithme (nom de fonction etc...) ainsi qu’un descriptif du traitement de l’algorithme, les données en entrées (paramètres), et les données en sortie (résultats);
- Variables : La liste des variables utilisées par l’algorithme.
- Corps : Correspond à l’algorithme. Celui-ci doit commencer par un Début, et se terminer par une Fin.
On utilise également un vocabulaire standard :
| Mot-clé | Rôle |
|---|---|
| Début / Fin | Délimiter l’algorithme |
| Entrer | Acquisition ou chargement d’une donnée |
| Sortir | Édition ou sauvegarde d’un résultat |
| Retourner | Retourner le résultat d’une fonction |
| ← | Affecter une valeur |
| Si … alors … [sinon] | Condition |
| Pour … allant de … à … | Boucle bornée |
| Tant que … faire … | Boucle conditionnelle |
Le pseudo-code n’est pas un langage informatique : il sert d’étape intermédiaire avant d’écrire le code.
Exemple détaillé : surface d’un disque
Langage naturel
On demande un rayon, on calcule π × rayon², on renvoie le résultat.
Pseudo-code
Fonction SurfaceDisque
Calculer la surface d'un disque à partir d'un rayon donné
Paramètres :
rayon : réel
Sortie :
surface : réel
Début
Entrer rayon
surface ← 3,14 * rayon * rayon
Retourner surface
Fin
Version Python
def surface_disque(rayon):
return 3.14159 * rayon * rayon
Pourquoi formaliser avant de coder ?
Écrire l’algorithme permet :
- de clarifier l’objectif ;
- d'éviter les erreurs tôt ;
- d’apprendre à raisonner étape par étape ;
- de communiquer clairement une idée.
Un bon programme commence toujours par un bon algorithme.