Al-Khawarizmismes

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-Khwarizmi 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 table 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 rafraîchir, et apprendre éventuellement des choses:

1. l'algorithme A* trouve le chemin « le plus court ou presque » entre deux nœuds 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, (l'celui du PGCD d’Euclide) et celui de l'élimination de Gauss-Jordan (connue des Chinois déjà 1700 ans plus tôt…)
6. La compression de données omniprésente 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 de 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 nœuds 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  a montré 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 l'algorithme de factorisation par crible sur les corps de 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 factorisation 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.