Résumé du livre
The Algorithm Design Manual
Concevoir, analyser et reconnaître les algorithmes
Le guide pragmatique des algorithmes : analyse de complexité, structures de données, graphes, programmation dynamique et NP-complétude — avec l'art de reconnaître le bon outil pour un problème.
Commencer 11 chapitres · ~159 min de lecture
Sommaire
- 01 Introduction à la conception d'algorithmes Ce qu'est un algorithme, l'importance de la modélisation et de la correction, et pourquoi un bon algorithme bat une machine plus rapide. 13 min
- 02 L'analyse d'algorithmes (Big O) Mesurer l'efficacité sans chronomètre : notations O, Ω, Θ, modèle RAM, classes de croissance et analyse de boucles. 13 min
- 03 Les structures de données Tableaux, listes, piles, files, tables de hachage, arbres équilibrés et tas : choisir la bonne structure change tout. 17 min
- 04 Le tri et la recherche Pourquoi (et comment) trier : heapsort, mergesort, quicksort, recherche dichotomique, et la puissance du tri comme outil. 15 min
- 05 Le parcours de graphes Représenter et explorer un graphe : listes vs matrices d'adjacence, BFS, DFS, composantes connexes et tri topologique. 16 min
- 06 Les graphes pondérés Arbres couvrants minimaux (Prim, Kruskal), plus courts chemins (Dijkstra, Bellman-Ford, Floyd) et flots de réseau. 17 min
- 07 La recherche combinatoire & le backtracking Explorer méthodiquement un espace de solutions : backtracking, élagage, et heuristiques quand l'exhaustif est hors de portée. 17 min
- 08 La programmation dynamique Casser un problème en sous-problèmes qui se recouvrent : récurrences, mémoïsation, distance d'édition et sous-structure optimale. 14 min
- 09 Problèmes difficiles & approximation (NP) P vs NP, réductions et NP-complétude : reconnaître un problème difficile et s'en sortir par l'approximation. 14 min
- 10 Comment concevoir un algorithme Une méthode pour aborder n'importe quel problème : les bonnes questions à se poser avant d'écrire la moindre ligne. 11 min
- 11 Le catalogue des problèmes algorithmiques La seconde moitié du livre : un catalogue de ~75 problèmes classiques et comment l'utiliser pour modéliser le vôtre. 12 min