En 2020, chaque mois, Charlotte Truchet et Serge Abiteboul nous racontent des histoires d’algorithmes. Des blockchains aux algorithmes de tri en passant par le web, retrouvez tous leurs textes, ainsi que des petits défis mathématiques, dans le Calendrier Mathématique 2020 et dans la série binaire associée… Antoine Rousseau

Avril : À la recherche du web perdu

Comment les moteurs de recherche du Web permettent-ils à leurs utilisateurs de trouver ce qu’ils cherchent parmi les volumes phénoménaux d’information disponibles ? 

Le Web, c’est d’abord un nombre impressionnant de pages de texte. Imaginons un moteur de recherche comme un index de ces pages, un peu comme l’index d’un très grand livre – vous lui donnez quelques mots, il vous dit quelles pages du web les contiennent. Le travail est énorme parce que le moteur de recherche le plus populaire aujourd’hui indexe des milliards de pages et répond chaque jour à des milliards de questions. Si on imprimait un tel index, il faudrait plus de pages de papier que n’en stocke la Bibliothèque Nationale de France. Alors comment un moteur de recherche du Web arrive-t-il à faire cela ?

L’astuce est de partager l’index entre un très grand nombre de serveurs. Par exemple, nous allons le partager entre un million de serveurs. Pour cela, construisons d’abord une fonction H, qui transforme, le plus aléatoirement possible, un mot en un entier entre un et un million. Si H(« Rodin ») = 250 853, alors le numéro de la machine qui conserve l’index du mot « Rodin » est 250853. Cela permet de partager le travail de l’index assez équitablement entre tous les serveurs. Pour obtenir l’entrée de l’index pour « Rodin », il suffit de calculer H(« Rodin ») et on sait à quel serveur demander cette entrée. 

La distribution aléatoire des mots entre tous les serveurs permet d’exploiter au mieux le parallélisme pour répondre à toutes vos questions.

Reste maintenant à choisir, parmi les millions de pages qui contiennent les mots d’une requête, les plus intéressantes. C’est essentiel car un utilisateur va rarement au-delà des dix ou vingt premiers résultats proposés. Ce qui a fait le succès de Google, c’est un algorithme, PageRank, qui basait le classement sur la popularité des pages sur le Web.  Les algorithmes de classement des moteurs de recherches utilisent aujourd’hui de nombreux critères pour classer les résultats. La formule précise est un secret industriel au moins aussi secret que la composition du Coca Cola. 

Ici, nous avons hyper-simplifié le problème. Le système traite plusieurs langues, il retrouve les pages qui contiennent des synonymes des mots que vous avez entrés, il fonctionne même quand des ordinateurs qui le composent tombent en panne, il s’adapte quand les pages changent, quand de nouvelles pages sont ajoutées , il accepte même vos fautes d’orthographe. Rien de magique, juste de super algorithmes.  

Serge Abiteboul et Charlotte Truchet

En 2020, chaque mois, Charlotte Truchet et Serge Abiteboul nous racontent des histoires d’algorithmes. Des blockchains aux algorithmes de tri en passant par le web, retrouvez tous leurs textes, ainsi que des petits défis mathématiques, dans le Calendrier Mathématique 2020 et dans la série binaire associée… Antoine Rousseau

Mars : Dessine-moi un mouton

Jusqu’à la fin du siècle dernier, le traitement d’images faisait appel à des lentilles, des filtres, des bancs de marbre, etc. Et puis les images sont devenues numériques, ouvrant la porte à les traitements algorithmiques de plus en plus puissants. Nous nous baladons avec des téléphones qui prennent des photos avec des millions de pixels et réalisent des traitements logiciels qui auraient fait pâlir d’envie les professionnels du traitement d’image de la fin du siècle dernier. Un téléphone intelligent offre une énorme gamme de fonctionnalités depuis la mise au point automatique jusqu’à la reconnaissance de visage. Ces mêmes téléphones vont bientôt nous ouvrir à des mondes nouveaux de réalités virtuelles ou augmentées. Tout cela s’appuie sur des algorithmes de géométrie.

Considérons une version très simplifiée d’un tel algorithme : le ray tracing. On dispose du modèle d’un monde en 3 dimensions et on aimerait construire une vue de ce monde depuis un point particulier, censé représenter un oeil, un appareil photo. Intuitivement, on lance un rayon depuis ce point de vue et on cherche quand et où ce rayon rencontrera un objet du modèle 3D. Le ray tracing permet de dessiner ce qu’on voit à partir de ce point de vue. Une balle devient un rond et un objet derrière la balle est représenté que partiellement, le point de vue ne voit pas la partie cachée par la balle.   

Dans le modèle 3D, on peut représenter un objet par un petit triangle, un carré, ou un parallélépipède. Pour calculer le point d’intersection d’une ligne droite avec de tels objets, il suffit de résoudre des équations vectorielles. Pour réaliser le ray tracing,  on a donc à effectuer un très grand nombre de calculs. Comme les calculs pour chaque point de l’image peuvent être faits indépendamment, on peut les réaliser en parallèle. Ces applications graphiques ont d’ailleurs conduit à de super avancées pour des processeurs massivement parallèles.  

Avec cet algorithme, on peut calculer l’objet visible en chaque point. On peut alors lancer des rayons depuis chaque point d’impact vers les sources de lumière pour déterminer sa luminosité. Observez que dans le monde réel, les rayons lumineux vont de la source de lumière vers le point de vue. Ici, on <<remonte>> le chemin des rayons jusqu’à la source de lumière.

Serge Abiteboul et Charlotte Truchet

En 2020, chaque mois, Charlotte Truchet et Serge Abiteboul nous racontent des histoires d’algorithmes. Des blockchains aux algorithmes de tri en passant par le web, retrouvez tous leurs textes, ainsi que des petits défis mathématiques, dans le Calendrier Mathématique 2020 et dans la série binaire associée… Antoine Rousseau

Février : Ça va être long ?

Si vous installez parfois des logiciels, vous avez forcément remarqué que la petite barre qui vous indique le temps restant est franchement mensongère. Elle semble avancer à sa guise, sans aucun rapport avec le temps écoulé, ou restant à écouler… Connaître le temps qu’un programme met à s’exécuter, ce n’est pourtant pas beaucoup demander ! En fait, si. Et en gros, à la louche, à peu près, en moyenne ? Même. Et même en faisant abstraction des performances des matériels utilisés, connaître le temps d’exécution d’un algorithme est un problème difficile – souvent insoluble en l’état actuel des connaissances. Bien souvent, on donne la complexité dans le pire des cas d’un algorithme, c’est-à-dire le temps de calcul théorique d’un algorithme sur la pire entrée possible, celle qui lui prendra le plus de temps à s’exécuter. On s’intéresse aussi beaucoup au temps de calcul en moyenne sur toutes les entrées possibles, qui est encore plus difficile à calculer. Et puis, pour résoudre un problème, il existe typiquement plusieurs algorithmes. Alors, savoir combien il faudrait de temps pour résoudre un problème particulier, c’est encore plus compliqué.

Parmi les algorithmes les plus étudiés, on trouve les algorithmes de tri, qui partent d’une suite d’objets non triés et s’occupent de la ranger dans un ordre bien défini. Il en existe de nombreux, aux noms poétiques : tri à bulles, tri par insertion, tri rapide… C’est une des rares familles d’algorithmes dont on connaît bien le temps théorique d’exécution, que ce soit dans le pire des cas ou en moyenne. Le tri par sélection, par exemple, fonctionne de manière très simple : on cherche la plus petite valeur à trier et on la met devant. Puis on cherche la deuxième plus petite dans ce qui reste, et on la met en deuxième, etc. Simple, mais pas terrible en complexité ! Pour n valeurs à trier, il faut lire une fois toutes les données pour trouver la plus petite valeur, ce qui coûte n opérations, pour la seconde, n-1, etc. Au total, on a de l’ordre de n2 opérations à faire dans le pire des cas comme en moyenne.

Le tri rapide, ou quicksort, est plus compliqué à comprendre mais plus efficace : on choisit arbitrairement une valeur dans les données à trier, et on met d’un côté toutes les valeurs plus petites, de l’autre toutes les plus grandes. Ça semble farfelu, c’est pourtant très astucieux : on se retrouve avec deux suites de données beaucoup plus petites à trier! Et on reprend sur ces deux suites. La complexité passe à n*log(n), ce qui représente un gain significatif en temps de calcul.

En général, on connaît la complexité dans le pire des cas de beaucoup d’algorithmes courants, beaucoup plus rarement la complexité en moyenne. Il reste beaucoup à apprendre.

Serge Abiteboul et Charlotte Truchet

En 2020, chaque mois, Charlotte Truchet et Serge Abiteboul nous racontent des histoires d’algorithmes. Des blockchains aux algorithmes de tri en passant par le web, retrouvez tous leurs textes, ainsi que des petits défis mathématiques, dans le Calendrier Mathématique 2020 et dans la série binaire associée… Antoine Rousseau

Janvier : D’al-Khuwārizmī à Gödel

Un algorithme est un procédé qui permet de résoudre un problème sans avoir besoin d’inventer une solution à chaque fois. Par exemple, quand on a appris un algorithme pour faire un nœud de cravate, on ne se pose plus de question quand il s’agit d’en faire un. Les mathématiciens s’intéressent aux algorithmes depuis toujours, en particulier quand ils traitent de symboles comme les nombres. D’ailleurs, le mot « algorithme » vient du mathématicien perse, de langue arabe, Muhammad Mūsā al-Khuwārizmī, qui vécut au IXe siècle.
Pour décrire abstraitement un algorithme, on utilise une mémoire, c’est-à-dire un endroit où stocker des symboles. On dispose aussi d’un jeu d’instructions étonnamment simples : (i) aller chercher des symboles déjà stockés dans la mémoire, les modifier et faire des opérations dessus (ii) tester le contenu d’un endroit particulier de la mémoire, ou (iii) répéter une séquence d’opérations tant que certaines conditions restent vraies. Un algorithme est constitué d’une suite de telles instructions.

Pour illustrer cette notion, considérons une méthode attribuée à Euclide (vers 300 avant notre ère) qui permet de calculer le plus grand diviseur commun de deux nombres entiers, leur PGCD. (Par exemple, le PGCD de 6 et 15 est 3, car 3 divise ces deux nombres, et aucun nombre plus grand que 3 ne le fait.)
On commence par regarder les deux nombres. Si l’un divise l’autre, c’est gagné : le plus petit est le PGCD. Sinon, l’algorithme préconise d’ôter au plus grand nombre, disons a, le plus petit, disons b. On se retrouve, comme au départ, avec deux nombres : b et le résultat de la soustraction a-b. On reproduit alors la même opération, encore et encore, jusqu’à ce que l’un des deux divise l’autre. Quels que soient les nombres de départ, un jour l’algorithme s’arrêtera avec un des deux nombres qui divise exactement l’autre. Alors, le PGCD des deux nombres de départ est ce nombre-là.
Pas besoin d’être Euclide ! Il suffit de suivre cet algorithme sans réfléchir pour obtenir le PGCD. Encore plus fort, on peut écrire un programme informatique qui réalise cet algorithme.
Si vous connaissez un minimum d’informatique, vous pouvez d’ailleurs programmer cet algorithme. Avec un peu de connaissances en maths, vous pouvez aussi vérifier qu’il calcule vraiment le PGCD de deux nombres.
Nous rencontrerons dans ce calendrier des exemples d’algorithmes qui permettent de résoudre un grand nombre de problèmes pratiques. Peut-on, quel que soit le problème, toujours trouver un algorithme qui le résolve ? Non ! Les travaux de mathématiciens des années 1930, notamment Kurt Gödel, ont montré que, pour certains problèmes, il n’existait pas d’algorithme pour les résoudre.

Serge Abiteboul et Charlotte Truchet