L'algorithme ABC

Définition

Un algorithme est une méthode générale pour résoudre un type de problèmes. Il est dit correct lorsque, pour chaque instance du problème, il se termine en produisant la bonne sortie, c’est-à-dire qu’il résout le problème posé.

On mesure l’efficacité d’un algorithme notamment par sa durée de calcul, par sa consommation de mémoire vive (en partant du principe que chaque instruction a un temps d’exécution constant), par la précision des résultats obtenus (par exemple avec l’utilisation de méthodes probabilistes), sa scalabilité (son aptitude à être efficacement parallélisé), etc. L’algorithmique intervient dans la vie de tous les jours.

Une recette de cuisine peut être réduite à un algorithme si on peut réduire sa spécification aux éléments constitutifs :

    • des entrées (les ingrédients, le matériel utilisé).
    • des instructions élémentaires simples (frire, flamber, rissoler, braiser, blanchir, etc. ), dont les exécutions dans un ordre précis amènent au résultat voulu.
    • un résultat : le plat préparé.

Historique

On doit le début de l’algorithme aux mathématiciens qui ne sont pas contenté de résoudre des problèmes mathématiques mais donnent une recette qui donnent la possibilité à tous de résoudre ces mêmes problèmes. Euclide est un exemple très célèbre de mathématicien de ce type. Il ne sait pas contenté de démontré qu’il y avait une infinité de nombre premier mais nous a donné un certain nombre de recettes y compris par exemple une recette permettant de savoir si deux entiers était premier entre eux.

Cette catégorie de mathématicien est très importante pour les informaticiens et pour Monsieur et Madame tous le monde car ils leur permettent de pouvoir résoudre des problèmes compliqué par leurs propres moyens.

Ce principe de « recette » sera mise en avant quelques siècles plus tard à Bagdad où un jeune traducteur à la tâche de traduire pour la grande bibliothèque des œuvres dont celle d’Euclide.

Ce jeune traducteur compris l’essence du travail d’Euclide, ce jeune traducteur est  Al-Khwârizmî. Qui ce prononce Algorithmi en français.

Devenu professeur de mathématiques à la cour du grand Kaliff il a pour mission d’instruire le peuple de Bagdad il rédigea un livre de recette mathématique qui intitula Algèbre. Parmi ces recettes on trouve des recettes en lien avec les problématiques de son époque comme un calcul d’héritage très juste (très complexe à l’époque), en fonction de la religion du défunt, du nombre d’enfants, du nombre d’épouses, des impôts, de la taille du terrain, ect .. et des recettes connues encore aujourd’hui comme la résolution d’une équation du second degré.

Cette technique de recette mathématique permis au peuple de résoudre des problèmes dit complexe de manière très rapide, même si ils ne comprennent pas forcément ce qu’ils font.

Voici la Pascaline

Avec le temps on confia l’application de ces recettes simples à des machines comme le fit Blaise Pascal, voyant son père (comptable) prendre beaucoup de temps à faire toujours les même calculs, lui créa la Pascaline. Très efficace mais capable de faire uniquement les algorithmes prévu à la construction de la machine.

Il a fallu attendre plusieurs siècles pour que Allan Turing  créer sa célèbre machine dite « universelle » car on pouvait inclure dans celle-ci, l’algorithme de Pascal, d’Euclide, d’Al-Khwârizmî et toutes les algorithmes possibles et imaginables.

On peut lui entrer des données que la machine va exécuter en temps voulu, les bases de l’ordinateur était posées.

La Tour de Hanoi

Cette exercice est un petit puzzle inventé par le mathématicien français Edouard Lucas en 1883.

L’objectif est de transférer la totalité de la tour du premier axe au troisième : il ne faut déplacer qu’un disque à la fois, et ne jamais poser un disque sur un disque plus petit.

Le but de l’algorithme étant d’être le plus rapide et efficace la première question qui ce pose à nous est combien de mouvements minimums sont nécessaires pour réaliser cette tâche ?

Comment procéder ?

La résolution de cette exercice comprend une tour de 8 disques mais n’oublions pas que le principe même de l’algorithme est que le calcul ce doit d’être juste pour chaque cas. Dans notre exemple la seule variable de cette exercice est le nombre potentiellement variant du nombre de disques.

Le meilleurs moyen de répondre à un problème comme celui ci est de généraliser un peu, on va donc partir sur un nombre de disque = n et l’un des avantages de la généraliser et que l’ont peu partir du cas LE PLUS PETIT. Il est facile de savoir résoudre ce problème en utilisant une tour de 1,2 ou 3 disques seulement.

Admettons que le résultat de Tn est le nombre minimum de mouvement pour transférer n disques d’un axe à un l’autre.

T1 = 1.

Une tour de 1 disque à besoin de seulement 1 mouvement pour résoudre le problème.

T2 = 3.

Une tour de 2 disque à besoin de 3 mouvements pour résoudre le problème.

On peut encore prendre une donnée très simplement avec le cas le plus petit de T0 = 0.

Maintenant changeons de perspective et essayons avec un nombre n de disques gros.

Avec 3 disques, la stratégie gagnante consiste à déplacer les deux disques du haut vers l’axe du milieu, puis déplacer le troisième disque, enfin déplacer les deux autres dessus.

Ceci nous donne un indice pour déplacer n disques : nous allons d’abord transférer les n-1 plus petits disques vers l’axe du milieu, ce qui nécessitera Tn-1 déplacements ; puis transférer le plus grand disque ; enfin ré-empiler les n-1 plus petits disques sur le grand, en faisant de nouveau Tn-1 déplacements.

Ainsi nous pouvons transférer les n disques (n>0) en effectuant au plus 2Tn-1 +1 déplacements :

Il arrive un moment ou on doit déplacer le plus grand disque.

Pour ce faire, il faut que les n – 1 autres soient sur un seul axe, et il a fallu au moins Tn-1 déplacement pour les y mettre. Si nous ne sommes pas trop vigilant, il est possible que l’on déplace le plus grand disque plus d’une fois. Mais après son dernier déplacement, on doit derechef poser les n – 1 plus petits (qui sont nécessairement sur un seul axe) sur le plus grand.

Ceci nécessite encore Tn-1 déplacements. En conséquence,

On déduit que :

(Remarquez que ces formules sont cohérentes avec les valeurs déjà connues T1 = 1 et T2 = 3. Nos expériences sur des petits cas ne nous ont pas seulement aidés à trouver une formule générale ; elles nous ont aussi fourni un moyen pratique de vérifier que nous avons pas commis une erreur idiote.

Un ensemble d’égalité comme (1.1) est appelé une récurrence. Elle ce compose d’une valeur initiale et d’une équation générale permettant de calculer une valeur en fonction des précédentes.

La récurrence nous permet de calculer Tn, pour n’importe quelle valeur de n. Mais en vérité personne n’a envie d’utiliser une récurrence pour ce genre de calcul : ça dure trop longtemps si n est grand. Ce qui nous plairait davantage, ce serait une « formule close » pour le nombre Tn, qui nous permettrait de le calculer rapidement si n est grand.

Mais comment résoudre une récurrence ? Une méthode possible est de deviner la solution, puis de prouver que notre prévision est correcte. Et pour deviner la solution notre meilleure chance réside encore dans les petits cas. Calculons donc successivement

T3 = 2×3+1 = 7 ; T4 = 2×7+1 = 15 ; T5 = 2×15+1 = 31 ; T6 = 2x 31 +1 = 63 .

On dirait bien que :

En tout cas c’est vrai pour n =< 6.

L’induction mathématique est une méthode générale permettant de prouver qu’une assertion concernant un entier n est vraie pour tout n >= n0.

D’abord on prouve qu’elle est vraie lorsque n prend sa plus petite valeur, n0 c’est ce qu’on appelle la base. Puis on démontre qu’elle est vraie pour n > n0, en supposant qu’elle a déjà été prouvée pour toutes les valeurs comprises entre n0 et n – 1 ;  c’est ce qu’on appelle l’induction. Ce genre de preuve nous permet d’obtenir une infinité de résultats avec une quantité de travail finie.

Les récurrences sont des sujets idéaux pour appliquer l’induction mathématique. Dans notre cas, par exemple, (1.2) se déduit aisément de (1.1) : la base est triviale cat T0 = 20 – 1  = 0 ; et l’induction s’ensuit pour n > 0 si on suppose que (1.2) est vraie lorsqu’on replace n par n- 1 :

Ainsi (1.2) est vraie aussi pour n. Nos recherches sur Tn s’achèvent sur un succès.

La récurrence de la Tour d’Hanoi est un exemple typique des problèmes que l’on rencontre dans des applications de toutes sortes.

Pour trouver une expression explicite d’une quantité donnée comme Tn, on procède en 3 étapes :

1 – Etudier les petits cas. Cela nous permet d’avoir un aperçu du problème, de plus cela est utile pour les étapes suivantes.

2- Trouver et prouver une expression mathématique pour la quantité en question. Pour le problème de la Tour de Hanoi, c’est la récurrence (1.1) ; qui nous donne la possibilité de calculer Tn pour tous n.

3- Trouver et prouver une formule close pour l’expression mathématique de l’étape 2. Pour la Tour de Hanoi, la formule close est la formule (1.2), solution de la récurrence.

NB : Site d’entraînement d’algorithmes informatiques :

  • Codewars,
  • franceIOI,
  • codingGames, …

N’hésitez pas à aller faire un tour sur notre blog ou sur notre page Facebook pour découvrir l’intégralité de nos actualités ! Nous en sortons une par semaine !