Les scientifiques montrent à quelle vitesse les algorithmes s’améliorent à travers un large éventail d’exemples

À quelle vitesse les algorithmes s'améliorent-ils ?

Les scientifiques du MIT présentent les premières preuves quantitatives systématiques que les algorithmes sont l’une des sources les plus importantes d’amélioration de l’informatique. Crédit : Degui Adil/EyeEm

Les algorithmes sont un peu comme un parent pour un ordinateur. Ils disent à l’ordinateur comment donner un sens aux informations afin qu’ils puissent, à leur tour, en faire quelque chose d’utile.

Plus l’algorithme est efficace, moins l’ordinateur a de travail à faire. Malgré tous les progrès technologiques dans le matériel informatique et la durée de vie très controversée de la loi de Moore, les performances de l’ordinateur ne sont qu’un côté du tableau.

Dans les coulisses, une deuxième tendance se dessine : les algorithmes sont améliorés, donc moins de puissance de calcul est nécessaire. Bien que l’efficacité algorithmique ait moins d’importance, vous remarquerez certainement si votre moteur de recherche de confiance devenait soudainement un dixième plus rapide, ou si vous déplacer dans de grands ensembles de données vous donnait l’impression de patauger dans de la boue.

Cela a conduit les scientifiques du Laboratoire d’informatique et d’intelligence artificielle (CSAIL) du MIT à se demander : à quelle vitesse les algorithmes s’améliorent-ils ?

Les données existantes sur cette question étaient en grande partie anecdotiques, consistant en des études de cas d’algorithmes particuliers qui étaient supposés être représentatifs de la portée plus large. Face à cette pénurie de preuves, l’équipe s’est mise à analyser les données de 57 manuels et plus de 1 110 articles de recherche, pour retracer l’histoire de l’amélioration des algorithmes. Certains des articles de recherche rapportaient directement à quel point les nouveaux algorithmes étaient bons, et d’autres devaient être reconstruits par les auteurs à l’aide de « pseudocodes », des versions abrégées de l’algorithme qui décrivent les détails de base.

Au total, l’équipe a examiné 113 « familles d’algorithmes », des ensembles d’algorithmes résolvant le même problème qui avait été souligné comme le plus important par les manuels d’informatique. Pour chacun des 113, l’équipe a reconstitué son historique, en suivant chaque fois qu’un nouvel algorithme était proposé pour le problème et en notant particulièrement ceux qui étaient les plus efficaces. Allant dans les performances et séparés par des décennies, à partir des années 1940 jusqu’à maintenant, l’équipe a trouvé une moyenne de huit algorithmes par famille, dont un couple a amélioré son efficacité. Pour partager cette base de données de connaissances assemblée, l’équipe a également créé Algorithm-Wiki.org.

Les scientifiques ont noté à quelle vitesse ces familles s’étaient améliorées, en se concentrant sur la caractéristique la plus analysée des algorithmes, à savoir à quelle vitesse ils pouvaient garantir la résolution du problème (en langage informatique : « complexité temporelle dans le pire des cas »). Ce qui a émergé était une énorme variabilité, mais aussi des informations importantes sur la façon dont l’amélioration algorithmique transformatrice a été pour l’informatique.

Pour les gros problèmes de calcul, 43 % des familles d’algorithmes présentaient des améliorations d’une année sur l’autre égales ou supérieures aux gains tant vantés de la loi de Moore. Dans 14 % des problèmes, l’amélioration des performances grâce aux algorithmes a largement dépassé celles résultant de l’amélioration du matériel. Les gains issus de l’amélioration des algorithmes ont été particulièrement importants pour les problèmes de mégadonnées, de sorte que l’importance de ces avancées a augmenté au cours des dernières décennies.

Le plus grand changement observé par les auteurs est survenu lorsqu’une famille d’algorithmes est passée d’une complexité exponentielle à une complexité polynomiale. La quantité d’efforts qu’il faut pour résoudre un problème exponentiel est comme une personne essayant de deviner une combinaison sur une serrure. Si vous n’avez qu’un seul numéro à 10 chiffres, la tâche est facile. Avec quatre cadrans comme un cadenas de vélo, il est déjà assez difficile que personne ne vole votre vélo, mais il est toujours concevable que vous puissiez essayer toutes les combinaisons. Avec 50, c’est presque impossible, ça prendrait trop de pas. Les problèmes qui ont une complexité exponentielle sont comme ceux des ordinateurs : à mesure qu’ils grossissent, ils dépassent rapidement la capacité de l’ordinateur à les gérer. Trouver un algorithme polynomial résout souvent cela, permettant de résoudre les problèmes d’une manière qu’aucune amélioration matérielle ne peut faire.

Alors que les rumeurs de la loi de Moore touchant à sa fin imprègnent rapidement les conversations mondiales, les chercheurs affirment que les utilisateurs informatiques devront de plus en plus se tourner vers des domaines tels que les algorithmes pour améliorer les performances. L’équipe affirme que les résultats confirment qu’historiquement, les gains des algorithmes ont été énormes, donc le potentiel est là. Mais si les gains proviennent des algorithmes au lieu du matériel, ils seront différents. L’amélioration du matériel à partir de la loi de Moore se produit sans à-coups au fil du temps, et pour les algorithmes, les gains se font par étapes qui sont généralement importantes mais peu fréquentes.

« C’est le premier article à montrer à quelle vitesse les algorithmes s’améliorent sur un large éventail d’exemples », déclare Neil Thompson, chercheur au MIT au CSAIL et à la Sloan School of Management et auteur principal du nouvel article. « Grâce à notre analyse, nous avons pu dire combien de tâches supplémentaires pouvaient être effectuées en utilisant la même quantité de puissance de calcul après l’amélioration d’un algorithme. À mesure que les problèmes atteignent des milliards ou des milliards de points de données, l’amélioration algorithmique devient considérablement plus importante que l’amélioration matérielle. À une époque où l’empreinte environnementale de l’informatique est de plus en plus préoccupante, c’est un moyen d’améliorer les entreprises et autres organisations sans inconvénient. »

Thompson a écrit l’article aux côtés de l’étudiant invité du MIT, Yash Sherry. L’article est publié dans le Actes de l’IEEE. Le travail a été financé par la fondation Tides et l’Initiative du MIT sur l’économie numérique.


Les progrès des algorithmes rendent viables les petits ordinateurs quantiques bruyants


Plus d’information:
Yash Sherry et al, À quelle vitesse les algorithmes s’améliorent-ils ?, Actes de l’IEEE (2021). DOI : 10.1109 / JPROC.2021.3107219

Fourni par le Massachusetts Institute of Technology

Citation: Les scientifiques montrent à quelle vitesse les algorithmes s’améliorent à travers un large éventail d’exemples (2021, 21 septembre) récupérés le 21 septembre 2021 à partir de https://techxplore.com/news/2021-09-scientists-fast-algorithms-broad-range.html

Ce document est soumis au droit d’auteur. En dehors de toute utilisation équitable à des fins d’étude ou de recherche privée, aucune partie ne peut être reproduite sans l’autorisation écrite. Le contenu est fourni seulement pour information.