Couverture du résumé de « Algorithmes illustrés »

Technologie & avenir · 15 min

Algorithmes illustrés

Aditya Bhargava · 2016

À qui s’adresse ce livre ?

Pour les étudiants, les débutants en programmation et les curieux qui veulent comprendre comment fonctionnent les recherches, les itinéraires et les recommandations, sans trop de mathématiques. C'est un livre d'initiation, illustré et léger.

Gratuit à télécharger · iPhone et Android

Ce résumé existe aussi en version audio dans l’appli.

3 idées clés à retenir

  1. La recherche en largeur explique pourquoi une demande d'ami pour l'ami d'un ami est facile à suggérer.

  2. Attribuer un poids aux liaisons change la réponse : le chemin avec le moins d'arrêts n'est pas forcément le plus rapide.

  3. Pour les problèmes très difficiles, une règle pratique qui donne un bon résultat rapidement vaut souvent plus que la solution parfaite qui prend trop de temps.

Ranger les données une seule fois peut vous épargner des milliers de recherches ensuite.
Une idée tirée de « Algorithmes illustrés », dans les mots de 15 Minutes

Aperçu

Les premières sections

Un guide illustré, sans peur des mathématiques

Entendendo Algoritmos, d'Aditya Bhargava, publié en 2016, est un livre d'introduction à l'informatique destiné à celles et ceux qui redoutent ce sujet. Au lieu de pages de formules, il utilise des dessins à la main, des exemples du quotidien et peu de mathématiques. Le sous-titre de l'original promet un guide illustré pour les programmeurs et les curieux, et tient cette promesse.

Un algorithme n'est qu'une recette : une suite d'étapes pour résoudre un problème. Le livre présente les plus classiques, les problèmes que chacun résout et le raisonnement qui les sous-tend. Les exemples de code, en Python, sont courts, et celles et ceux qui ne programment pas peuvent suivre les idées grâce aux figures.

L'idée de fond est que connaître quelques algorithmes de base aide à choisir le bon outil. Entre deux façons de résoudre un problème, savoir laquelle est la plus rapide et pourquoi fait toute la différence dans les systèmes qui servent des milliers de personnes.

Recherche binaire : deviner avec méthode

Le premier algorithme est la recherche binaire. L'image utilisée est celle du jeu où l'on devine un nombre entre 1 et 100. Si vous essayez 1, puis 2, puis 3, cela peut prendre cent tentatives. Si vous commencez par le milieu et que chaque réponse indique si le nombre est plus grand ou plus petit, vous éliminez la moitié des possibilités à chaque essai et trouvez en quelques coups.

La recherche binaire ne fonctionne que si la liste est triée, et c'est pourquoi les dictionnaires et les annuaires sont classés par ordre alphabétique. Personne ne lit tous les noms pour en trouver un : on ouvre au milieu et on ajuste. Dans une liste d'un million d'éléments, la méthode trouve la cible en une vingtaine d'étapes environ.

La leçon est qu'organiser les données avant de chercher peut rapporter énormément. Souvent, le travail de ranger une fois économise des milliers de recherches ensuite.

Big O : mesurer la croissance du coût

Le livre présente la notation Big O, le langage pour parler de la vitesse des algorithmes. Elle ne mesure pas des secondes, mais la façon dont le nombre d'étapes augmente lorsque la quantité de données grandit. C'est un moyen de comparer des méthodes sans dépendre de l'ordinateur.

Parcourir une liste entière pour trouver un élément croît dans la même proportion que la taille de la liste, ce qu'on appelle un temps linéaire. La recherche binaire croît très lentement, c'est le temps logarithmique. Trier de la manière la plus simple croît beaucoup plus vite. Et il existe des problèmes dont le coût explose, comme tester toutes les routes possibles entre de nombreuses villes.

La morale est qu'avec peu de données, n'importe quelle méthode convient, mais avec beaucoup, la différence est abyssale. Un tableur qui tourne bien avec cent lignes peut bloquer avec cent mille, et la raison se trouve dans la façon dont le coût croît.

11 sections de plus dans l’appli

Continuez dans l’appli

Lisez le résumé en entier ou écoutez-le et testez-vous à la fin avec le quiz du livre. L’appli est gratuite à télécharger, et une lecture gratuite vous attend chaque jour.

À propos de Aditya Bhargava

Aditya Bhargava est ingénieur logiciel et auteur d'Entendendo Algoritmos (Grokking Algorithms), publié en 2016. Il a également réalisé les illustrations du livre, ce qui aide à expliquer le style visuel de l'ouvrage. Il tient un blog avec des textes illustrés sur la programmation, parmi lesquels le guide visuel bien connu sur les functors, applicatives et monads.