Al-Khawarizmismes 17


statue d'Al-Khawarizmi en Ousbekistan, par Heathen Dawn sur Flickr

Dans les années 800, le mathématicien perse Abou Jafar Muhammad Ibn Mūsa al-Khuwārizmī introduit le zéro (indien) dans les chiffres arabes, décrit comment résoudre les équations du second degré, et propose de résoudre certains problèmes mathématiques en répétant une séquence d’opérations jusqu’à ce qu’un « critère d’arrêt » soit satisfait. Au XIIème siècle, les moines latins nomment « algorismus » cette méthode d’Al Khuwarizmi, qui devient « algorithme » en français en 1554.

Pour cette idée fondamentale des mathématiques et indispensable en informatique, Al Khuwarizmi a reçu à titre posthume un cratère lunaire à son nom, et environ 165’000 fautes d’orthographe commises par des ignares qui mettent un y grec à la place d’un  ī persan…

Après que des fous aient passé leur vie à calculer à la main des tables de logarithmes ou des décimales de pi, c’est évidemment l’arrivée des ordinateurs qui a donné à l’algorithmique son importance actuelle. Aujourd’hui, vous utilisez des algorithmes tous les jours, sans le savoir. Par exemple lorsque vous cliquez sur le titre d’une colonne sur votre ordinateur, et que les lignes sont triées en un clin d’oeil. Ou lorsque vous demandez votre route à un GPS. A chaque fois que vous téléphonez ou utilisez votre carte de crédit, vous utilisez des algorithmes de cryptographie qui étaient de la science-fiction il y a 50 ans.

Bon, ça c’était l’introduction. En fait cet article est motivé par la coïncidence de trois événements survenus la semaine passée :

  • Mes collègues ont (enfin) réussi à faire fonctionner un algo que j’avais pondu pour optimiser les mouvements d’une machine. Un algo assez simple (optimisation gloutonne, évidemment…), bien testé, mais pas suffisamment documenté, donc pas bien utilisé, donc inspirant une certaine méfiance… Mais là ça marche! Vidéo bientôt.
  • La découverte de l’existence du Prix J.H. Wilkinson attribué tous les 4 ans aux auteurs d’un logiciel de calcul numérique particulièrement efficace, dont certains que je connaissais depuis peu (FFTW et Triangle) et d’autres à découvrir (deal.II)
  • Enfin, sur les liens du jeudi de Neamar, un lien vers la page d’un chercheur listant les algorithmes considérés comme les plus importants par ses collègues et lui. Il y en a 32, assez pour évaluer vos connaissances en la matière ou les rafraichir, et apprendre éventuellement des choses:
  1. l’algorithme A* trouve le chemin « le plus court ou presque » entre deux noeuds d’ un graphe. Il est utilisé dans les GPS et dans les jeux vidéo pour  les déplacements des personnages par « intelligence artificielle »
  2. Beam Search peut dans certains cas trouver un chemin meilleur qu’A*, mais nécessite plus de calculs.
  3. La dichotomie est la technique que les enfants utilisent pour chercher un mot dans le dictionnaire : on l’ouvre à la moitié, puis à la moitié de la moitié où se trouve le mot et ainsi de suite jusqu’à trouver la bonne page.
  4. « Branch and bound » : Séparation et évaluation est une méthode générique d’optmisation combinatoire permettant d’éviter d’évaluer toutes les possibilités.
  5. L’ algorithme_de_Buchberger est un truc de matheux datant de 1976, qui généralise à la fois le plus ancien algorithme connu, celui du PGCD d’Euclide et celui de l’élimination gaussienne (connue des Chinois dàjà 1700 ans plus tôt…)
  6. La compression des données omniprésentes dans nos fichiers informatiques. Il existe de nombreux algorithmes spécifiques, parmi lesquels la transformée_de_Burrows-Wheeler me parait particulièrement géniale.
  7. L’échange des clés Diffie-Hellman permet à deux personnes qui ne se connaissent pas d’échanger des informations confidentielles sur un canal non sécurisé. Indispensable en télécommunications.
  8. L’algorithme de Dijkstra détermine le chemin le plus court entre deux neouds d’un graphe, sous certaines contraintes expliquées dans l’article sur le  GPS encore.
  9. Les différences finies permettent d’approximer des dérivées, comme dans la formule f'(x) = (f(x+h) – f(x-h)) / 2h. (Je les utilise tous les jours, mais est-ce vraiment des algorithmes ?)
  10. La Programmation Dynamique est une méthode d’optimisation sous contrainte. Elle permet d’obtenir une solution optimale à partir des solutions optimales de sous-problèmes. Curieusement, en 1976, on  amontré que les algorithmes de programmation dynamique sont équivalents à ceux de recherche d’un chemin optimal dans un graphe…
  11. L’algorithme d’Euclide pour déterminer le plus grand diviseur commun (PGCD) de deux entiers est le plus ancien algorithme connu. Il est paru dans les « Eléments » d’Euclide autour de 300 av J.C et ne nécessite pas de factorisation des nombres.
  12. L’algorithme « espérance maximisation » est très utilisé en traitement d’images.
  13. La transformée de Fourier rapide (FFT) est extrêmement utilisée en traitement du signal, et plein d’autres domaines, jusque dans l’étude des succès Hollywoodiens.
  14. La descente de gradient est l’algorithme le plus connu pour obtenir le minimum d’une fonction à plusieurs variables.
  15. Les fonctions de hachage permettent de manipuler plus facilement de grosses données en les réduisant à des empreintes. Shazam utilise cette idée de manière spectaculairement efficace. Mais ici aussi, j’hésiterais à parler d’algorithme pour une « simple » fonction…
  16. Le Tas est une structure de données exploitée dans beaucoup d’algorithmes informatiques très efficaces comme le tri par tas. ( Il faut absolument que je trouve le temps d’étudier le « soft heap« , une structure de données « miraculeuse » découverte en 2000 )
  17. L‘algorithme de Karatsuba permet de multiplier 2 (grands) nombres plus vite qu’avec la méthode que vous avez apprise à l’école.
  18. L’algorithme LLL détermine des vecteurs de base « presque » orthogonaux à partir d’un grand nombre de vecteurs. Il est utilisé en cryptographie.
  19. l’algorithme_de_Ford-Fulkerson permet de résoudre le problème de flot maximum
  20. Le Tri fusion permet de réarranger rapidement une liste dans un ordre spécifique
  21. La Méthode_de_Newton permet de trouver une  approximation des zéros d’une fonction, des solutions d’une équation à plusieurs variables, ou les minima/maxima.
  22. Q-learning est une technique d' »apprentissage renforcé »
  23. le Crible quadratique est la meilleure méthode de factorisation d’un nombre, à part le crible sur le corps des nombres généralisés qui est à peine meilleur mais beaucoup plus compliqué. Si vous voulez casser une clé RSA, c’est ce qu’il vous faut, en plus de beaucoup de gros ordinateurs…
  24. RANSAC, pour « RANdom SAmple Consensus » est un algorithme d’ajustement de paramètres à des données qui ignore les données « visiblement complètement fausses »
  25. RSA, pour Rivest_Shamir_Adleman, est le génial algorithme de cryptographie a clé révélée utilisé dans la plupart des systèmes de sécurité actuels : carte bancaire, commerce électronique etc.
  26. l’algorithme_de_Schönhage-Strassen effectue des multiplications de grands entiers en utilisant la FFT. Sacrés mathématiciens…
  27. l’ algorithme_du_simplexe permet de résoudre les problèmes dits de programmation linéaire, dans lesquels on cherche à optimiser la valeurs d’une fonction de plusieurs variables devant satisfaire des contraintes d’inégalités.
  28. La décomposition_en_valeurs_singulières permet de factoriser des matrices rectangulaires, donc de résoudre des systèmes linéaires surdéterminés (avec plus d’équations que d’inconnues). Elle est utilisée dans de nombreux domaines, de la robotique aux prévisions météo.
  29. Résoudre des systèmes d’équations linéaires par élimination de Gauss-Jordan ou décomposition de_Cholesky est l’une des opérations les plus communes en analyse numérique, utilisée dans pratiquement tous les domaines de l’ingénierie.
  30. les « tenseurs de structure » (Structure_tensor en anglais) sont très utilisées en traitement d’image : ils permettent de quantifier l’appartenance d’un pixel à une région homogène. Méritent-ils de figurer dans les algorithmes ? la question est ouverte.
  31. Union-Find est une structure de données permettant de partitionner des données dans des ensembles disjoints, et de trouver rapidement à quel ensemble appartient une donnée ainsi que de réunir rapidement des ensembles.
  32. L’algorithme de Viterbi, une retombée de la conquête spatiale permettant de corriger les erreurs de transmission en télécommunication. Il est bien caché dans vos téléphones portables, mais il est là.

Connaissez-vous d’autres algorithmes dignes de figurer dans la liste ? les commentaires sont là pour les proposer.

  • Avatar

    Je rajouterai bien les Algorithmes récursifs, je ne crois pas les avoir vus dans la liste

    • http://drgoulu.com Dr. Goulu

      La récursivité, c’est génial. Je me souviens encore du flash lumineux éprouvé en voyant ça la première fois. Mais je ne sais pas s’il existe des algos fondamentalement récursifs, qui ne peuvent pas être « dérécursifiés » sans utiliser une pile. Il me semble que la récursivité est plutôt une technique mathématico-informatique pour implanter des algos simplement (d’ailleurs mon optimisation de mouvements de machine est récursive). Avis contraires ?

      • Arghz

        un algo sous forme récursive est toujours implémentable sous une forme classique, ce n’est jamais qu’une boucle et on sauve / restaure les variables adéquates à chaque passage dans la boucle (état)
        En pratique on utilise un pile pour stocker les variables par commodité, mais on pourrait les stocker en mémoire de la facon qu’on veut:
        dans une pile les adresses mémoires utilisés sont contigues pour les retrouver, mais on pourrait utiliser une autre fonction mathématique pour générer les adresses ;-)

  • herve

    Algorismus est en fait le nom latinisé d’Al Khawarizmi.

    Ce qu’on a tout d’abord appelé algorithme c’est le calcul avec les « chiffres arabes » utilisant (à keke chose près) les méthodes que nous connaissons tous ; avant cela, on utilisait des abaques.

    La chasse au kangourou de Pollard ?

    • http://drgoulu.com Dr. Goulu

      Al Khawarizmi est aussi considéré comme ayant introduit l’algèbre (mot dérivé du titre d’un de ses livres) en Occident. Il est probable qu’à l’époque on ne faisait pas de distinction calcul/algorithme, d’autant qu’il n’existait que très peu d’algos, mais formaliser le calcul itératif en définissant un critère d’arrêt, donc la notion de convergence semble bien être un apport d’Abou Jafar.

      C’est quoi le « kangourou de Pollard »? pas trouvé de lien…

  • herve

    Erreur : j’aurais du dire : « ce qu’on a appelé algorithmique » (ou sans doute « algorismique »), etc.

  • herve

    Ça manque un peu d’algorithmes modulaires cette liste. Hensel lifting !

  • vpo

    L’algorithme de Monte-Carlo doit son nom au casino, et pourtant on peut l’utiliser pour plein de choses différentes (calcul de risque financier – ok on en revient au casino :-) -, calcul de la superficie d’un lac, détermination des décimales de Pi, application en électromagnétisme au modèle d’Ising, etc…)

    http://fr.wikipedia.org/wiki/M%C3%A9thode_de_Monte-Carlo

    • http://drgoulu.com Dr. Goulu

      Ah oui, la méthode de Monte-Carlo devrait même être bombardée « mère de tous les algos »…

  • http://zythom.blogspot.com Zythom

    J’aurais bien proposé d’ajouter à votre très intéressante liste l’algorithme de rétropropagation du gradient très utilisé dans l’univers des réseaux de neurones formels. Cet algorithme permet de calculer d’une manière simple le gradient d’une fonction de coût (calculée sur les sorties d’un réseau de neurones utilisé sur un ensemble d’apprentissage;) que l’on peut ensuite optimiser avec une méthode de descente de gradient, ou plus efficacement avec une méthode de quasi-newton (par exemple le calcul approché de l’inverse de la matrice Hessienne).

    http://fr.wikipedia.org/wiki/R%C3%A9tropropagation_du_gradient

    Quand la fonction de coût est minimale, le réseau de neurones est ensuite utilisé sur un ensemble de données non vues lors de la phase d’apprentissage et, si l’ensemble d’apprentissage a bien été choisi pour être représentatif, le résultat est surprenant.

  • Hervé

    Oh, oui, la méthode de Monte-Carlo. J’ai écrit dans mon cours de proba/stats qu’elle devrait s’appeler « méthode de Buffon » et même, en fait, « méthode du Chevalier de Méré »… comprend qui peut :)

    J’aurais envie d’ajouter à cette liste quelques RNG. Le Mersenne Twister, j’aime pas. Je préfère de loin les sobres et élégantes créations de Georges Marsaglia ; le xorshift de Marsaglia ?

    Sinon, je ne vois nulle part dans cette liste les mots « ondelettes » ou « wavelets ». Oh là !

    Autre suggestion : le compressed sensing…

  • Hervé

    En ce qui concerne l’al-jabr et al-muqabala, oui, je sais, mais *ça n’est pas ça qui a été d’abord appelé algorithmique*, mais simplement les opérations avec les chiffres arabes ; je suis formel.

  • Hervé
  • http://eric.cabrol.free.fr/dotclear/ Eric C.

    A propos du simplexe, j’imagine que tu n’as pas raté cette « info »
    http://www.bulletins-electroniques.com/actualites/63922.htm

    • http://drgoulu.com Dr. Goulu

      A ma grande honte, si, ça m’avait échappé ;-)
      La page de la wikipédia http://en.wikipedia.org/wiki/Hirsch_conjecture donne plus de détails. Ca n’a pas l’air trop grave. Intéressant tout même de voir que la complexité de cet algo très courant n’est pas encore élucidée…

  • http://drgoulu.com Dr. Goulu

    La liste du SIAM des 10 algos considérés comme les plus importants du XXème siècle mentionne ceux-ci (avec des liens pour ceux qui ne figurent pas plus haut):

    1. Monte-Carlo
    2. le simplexe
    3. Krylov subspace iteration methods
    4. la décomposition (LU) des matrices
    5. le compilateur FORTRAN (c’est vrai ça… un compilateur, c’est un algo !)
    6. l’algorithme QR
    7. Quicksort
    8. la FFT
    9. l’ integer relation detection algorithm de Ferguson et Forcade
    10. la Fast Multipole Method. et celui là, faut que je regarde de près…