Les algorithmes

Point historique

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.

Lorsque nous faisons face à un problème, de n’importe quelle nature, nous effectuons toujours diverses actions, dans un ordre précis, pour parvenir à notre solution.

Ce cheminement est ce que l’on appelle un algorithme.

Donald Knuth (informaticien et mathématicien né en 1938) décrit un algorithme selon 5 grandes propriétés :

• finitude : un algorithme doit toujours se terminer après un nombre fini d’étapes ;
• définition précise : chaque étape d’un algorithme doit être définie précisément, les actions à transposer doivent être spécifiées rigoureusement et sans ambigu¨ıté pour chaque cas ;
• entrées : quantités qui lui sont données avant qu’un algorithme ne commence. Ces entrées sont prises dans un ensemble d’objets spécifié ;
• sorties : quantités ayant une relation spécifiée avec les entrées ;
• rendement : toutes les opérations que l’algorithme doit accomplir doivent être suffisamment basiques pour pouvoir être en principe réalisées dans une durée finie par un homme utilisant un papier et un crayon.

Écriture

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 commencé par un Début, et se finit par une Fin.

Langage Naturel et Pseudo-code

Un algorithme commence toujours par s’écrire en ce que l’on appelle le langage naturel, ou pseudo-code. Cela correspond à l’écriture des instructions élémentaires pour résoudre notre problème dans un langage compréhensible par un humain. Dans notre cas, cela consiste à écrire les instructions avec de courtes phrases en français.
Une fois les phrases écrites, il faut formaliser le pseudo-code en algorithme, avec les mot-clés et symboles du tableau suivant :

Mots et symboles	Opération réalisée
Début	Début de l’algorithme, permet de le nommer
Fin	Fin de l’algorithme
Faire	Exécution d’une opération
Entrer	Acquisition ou chargement d’une donnée
Sortir	Édition ou sauvegarde d’un résultat
Retourner	Retourner le résultat d’une fonction
←	Affectation d’une valeur à une variable
Symboles d’opérateur (+-*/ ET OU,...)	Opérations arithmétiques ou logiques
Si ... alors ... [sinon]	Branchement conditionnel
Tant que ... faire ...	Répétition conditionnelle
Pour ... allant de ... à ...	Répétition bornée

Exemple : Calculer la surface d'un disque

En pseudo-code, pour faire une fonction qui calcule la surface d'un disque de n'importe quel rayon, j'ai besoin de me définir un rayon (appelé rayon par exemple), d'enregistrer dans une variable le calcul de la formule pi * rayon * rayon, et enfin de retourner cette variable pour récupérer la valeur calculée.

En algorithmique, on traduirait ce pseudo-code en utilisant les informations du tableau, ce qui donnerait :

Vidéo