Aperçu
Le livre se compose de 11 chapitres, bien que le premier soit plutôt une introduction (intitulé "Introduction aux algorithmes"), et le dernier traite davantage de ce qu'on peut (et devrait idéalement) étudier ensuite, ainsi que des sujets que ce livre ne couvre pas complètement (comme MapReduce, le filtre de Bloom, SHA et autres). Alors, que couvre ce livre ? Voyons cela brièvement.
Tout d'abord, le livre aborde la complexité des algorithmes et la fameuse notation "Grand O". Et croyez-moi, la grande majorité des cours de programmation enseignent des compétences très spécifiques, mais mentionnent rarement la complexité temporelle des algorithmes ou l'optimisation du code.
Quant aux sujets abordés, je vais les énumérer rapidement dans ce paragraphe.
Le livre commence par un chapitre sur les tableaux et les listes chaînées, expliquant comment les manipuler (en termes de tri et de recherche). Il liste les avantages et inconvénients des listes (en termes de vitesse de lecture/écriture et de stockage des données).
Ensuite, il y a un court chapitre sur la récursivité, abordant la pile d'appels et son fonctionnement.
Puis, le livre plonge dans l'algorithme de tri rapide (en utilisant l'approche "diviser pour régner"). Pour renforcer la compréhension, l'auteur fournit trois exemples d'application. L'élément pivot est discuté, et des comparaisons de performance entre différentes méthodes de tri (y compris celles des chapitres précédents) sont illustrées par des graphiques.
La section suivante introduit une nouvelle structure de données - les tables de hachage. Elle décrit des scénarios où elles sont utiles (par exemple, déduplication, cache, modélisation de relations entre objets). Les cas de collision sont également expliqués.
Ensuite, le livre présente les graphes comme structure de données. Non, cela ne couvre pas tous les sujets que j'ai étudiés en "Modélisation Mathématique", mais au moins les bases sont abordées : définition d'un graphe, son utilité, ses applications, et la distinction entre graphes orientés et non orientés. Comme les graphes concernent les "chemins", les algorithmes couverts incluent la recherche en largeur (BFS) et la recherche du plus court chemin. Ce chapitre mentionne aussi les files d'attente et revient sur les piles, expliquant FIFO et LIFO - bien que, à mon avis, cela aurait dû être abordé plus tôt. À noter que deux chapitres sont consacrés aux graphes : le premier traite du plus court chemin dans les graphes non pondérés, le second utilise l'algorithme de Dijkstra pour les graphes pondérés. Là encore, plusieurs exemples sont fournis : d'abord théoriques, puis en code. L'algorithme Bellman-Ford (pour les graphes avec arêtes de poids négatif) n'est pas couvert et est laissé en lecture autonome.
Enfin, le livre aborde des algorithmes moins courants (en programmation quotidienne) : algorithmes gloutons, approches des problèmes "impossibles" sans solution algorithmique rapide (problèmes NP-complets), programmation dynamique (décomposition de problèmes complexes en sous-problèmes) et l'algorithme des k plus proches voisins (k-NN) utilisé en apprentissage automatique.
Caractéristiques
Le livre comprend des illustrations facilitant la compréhension. Chaque chapitre contient 5 à 7 questions pratiques (certaines avec exemples de code), avec des réponses en fin d'ouvrage. Chaque chapitre se termine par un "aide-mémoire" résumé en 4-5 phrases.
Avec environ 300 pages et des chapitres de longueur modérée, c'est un livre que les lecteurs ont de grandes chances de terminer. Le langage est accessible et la lecture fluide.
Conclusion
Un excellent ouvrage pour les programmeurs autodidactes sans formation technique. Il explique clairement diverses méthodes de tri et de recherche (recherche binaire, parcours en profondeur/largeur), met l'accent sur l'analyse de complexité (notation Grand O), et couvre même des bases essentielles comme la théorie des graphes, les algorithmes de plus court chemin, ou les k plus proches voisins - des connaissances que tout programmeur devrait maîtriser.
