21 — Livres : résumés des ouvrages de référence

Ce chapitre résume les 5 livres majeurs d'algorithmique. Pour chacun : contexte, public visé, structure, chapitres prioritaires, points clés à retenir et méthodologie de lecture intégrée à cette formation.

---

Sommaire

1. Introduction to Algorithms (CLRS)
2. Algorithms (Sedgewick & Wayne)
3. Algorithm Design (Kleinberg & Tardos)
4. Cracking the Coding Interview (McDowell)
5. The Algorithm Design Manual (Skiena)
6. Comparaison et choix du livre
7. Plan de lecture intégré

---

1. Introduction to Algorithms (CLRS)

Auteurs : Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein — MIT Press.

Contexte et public

Publié pour la première fois en 1990 (4ᵉ édition en 2022), CLRS est le manuel de référence universitaire. Il couvre les algorithmes avec un niveau de rigueur mathématique élevé : chaque algorithme est présenté avec une preuve de correction et une analyse de complexité formelle. C'est le livre des cycles universitaires et des entretiens de recherche.

Structure (35 chapitres, 4ᵉ édition)

Le livre est découpé en 6 parties :

Points clés à retenir

• Notations asymptotiques : chapitre 3 — la définition formelle de O, Ω, Θ avec exemples.
• Master theorem : chapitre 4 — résolution des récurrences (lié au chapitre 12).
• Tris linéaires : chapitre 8 — counting sort, radix sort, bucket sort, bornes inférieures.
• Amortisation : chapitre 17 — la méthode du potentiel (push/pop amorti O(1)).
• DP et greedy : chapitres 15–16 — problèmes classiques et preuves de propriété du choix glouton.
• Graphes : chapitres 22–25 — BFS/DFS, MST, Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson.
• Max flow : chapitre 26 — Ford-Fulkerson, Edmonds-Karp, coupes min.

Méthodologie de lecture

• Ne pas lire en continu : CLRS est une encyclopédie, on y consulte les chapitres au besoin.
• Faire les exercices : la moitié de la valeur du livre. Les problèmes difficiles (exercices marqués ★) valent une session entière.
• Correspondance formation : pour chaque chapitre de la formation (00-16), lire le chapitre CLRS équivalent ci-dessus.
• Alternative gratuite : le MIT 6.006 (Introduction to Algorithms) est disponible en ligne, aligné sur la 3ᵉ édition.

---

2. Algorithms (Sedgewick & Wayne)

Auteurs : Robert Sedgewick, Kevin Wayne — Addison-Wesley. 4ᵉ édition (2011), implémentation Java.

Contexte et public

Sedgewick est le professeur de Princeton à l'origine des cours Coursera Algorithms I & II (les plus suivis de la plateforme). L'ouvrage est pédagogique avant d'être formel : chaque algorithme est illustré par du code Java réel, des visualisations et des expériences empiriques. Idéal pour les développeurs qui veulent comprendre sans le formalisme mathématique de CLRS.

Structure (6 parties)

Points clés à retenir

• Analyse empirique : Sedgewick compare toujours la théorie et les mesures réelles.
• Union-Find : chapitre 1 — implémentation complète, plus belle introduction au sujet de la littérature.
• Quicksort : chapitre 2 — l'analyse de la version 3-way est la référence.
• Arbres rouge-noir : chapitre 3 — la dérivation à partir des 2-3 trees est limpide.
• KMP, Boyer-Moore, Rabin-Karp : chapitre 5 — avec visualisations.
• NP-complétude : chapitre 6 — réduction et exemples classiques.

Méthodologie de lecture

• Coursera : suivre Algorithms, Part I (fondamentaux + tris + search) puis Part II (graphes + strings).
• Implémenter : retapez chaque algorithme en Java (ou Python) sans regarder.
• Complément idéal à CLRS : Sedgewick pour l'intuition, CLRS pour la rigueur.
• L'outil associé : le site officiel du livre propose les visualisations et le code complet.

---

3. Algorithm Design (Kleinberg & Tardos)

Auteurs : Jon Kleinberg, Éva Tardos — Pearson. 1ʳᵉ édition (2006).

Contexte et public

Kleinberg et Tardos enseignent à Cornell et ont conçu ce livre autour d'une idée : l'algorithmique est une discipline de conception, au même titre que l'architecture. Chaque chapitre part d'un problème motivé par une application réelle (réseaux, bioinformatique, économie) et construit l'algorithme comme on conçoit un système. Le ton est celui du cours de master ; le niveau mathématique est exigeant mais toujours motivé.

Structure (13 chapitres)

Points clés à retenir

• Greedy (chapitre 4) : le meilleur traitement de la propriété du choix glouton — preuves par échange et par intervalle.
• Network Flow (chapitre 7) : Ford-Fulkerson, coupe minimale, applications (bipartite matching, projection scheduling).
• NP-complétude (chapitres 8–9) : réductions intuitives, sans formalisme excessif.
• Algorithmes randomisés (chapitre 13) : hashing, Monte Carlo vs Las Vegas.
• Local search (chapitre 12) : souvent ignoré mais fondamental en optimisation moderne.

Méthodologie de lecture

• Problèmes d'ouverture de chapitre : toujours les résoudre avant de lire la solution (les auteurs ont conçu le chapitre pour cela).
• Public cible : à lire après Sedgewick, avant ou en parallèle de CLRS pour la complexité.
• Applications : chaque chapitre montre l'usage réel (routage, génomique, enchères) — utile pour les entretiens « system design » avec composante algorithmique.

---

4. Cracking the Coding Interview (McDowell)

Auteur : Gayle Laakmann McDowell — CareerCup. 6ᵉ édition (2015).

Contexte et public

Le manuel de préparation aux entretiens des grandes entreprises technologiques (Google, Facebook/Meta, Amazon, Apple, Microsoft). À mi-chemin entre la révision d'algorithmique et le guide de carrière : il explique le déroulement d'un entretien (ressenti du recruteur, ce qui est évalué, les erreurs de communication) et fournit 189 problèmes classiques commentés.

Structure

Points clés à retenir

• Approche des 5 étapes : écouter, dessiner, écrire du code brut, tester, optimiser (cf. méthodologie UMPIRE du chapitre 17).
• Sections par thème : arrays/strings, linked lists, stacks/queues, trees/graphs, recursion/DP, sorting/searching, math/logic.
• Questions comportementales : la méthode STAR (Situation, Task, Action, Result).
• Conseils de communication : parler en réfléchissant à voix haute est aussi important que le code.
• Les 7 secrets des entreprises : chapitres par entreprise (Google, Amazon, Apple, Microsoft, Facebook).

Méthodologie de lecture

• Ne pas faire les 189 problèmes en continu : choisir 60–80 couvrant les 10 thèmes du chapitre 17.
• Simulation chronométrée : 45 minutes par problème dans les conditions réelles.
• Complément indispensable : le chapitre 22 de cette formation (interviews) prolonge les questions de ce livre.
• Limite : certains problèmes sont datés (édition 2015) ; les problèmes récents se trouvent sur LeetCode.

---

5. The Algorithm Design Manual (Skiena)

Auteur : Steven S. Skiena — Springer. 3ᵉ édition (2020).

Contexte et public

Le livre de Skiena est le manuel pragmatique : l'auteur, professeur à Stony Brook, a participé à de nombreux projets industriels (compression, bioinformatique). Son credo : « Algorithm design is not just a body of theory, it's a practical art ». Le livre comporte deux parties : un cours de conception (partie I) et un catalogue de problèmes (partie II) où chaque problème classique est décrit avec ses variantes et références.

Structure

Points clés à retenir

• War Stories : récits réels d'application des algorithmes dans des projets — le meilleur argument « pourquoi les algorithmes servent ».
• Catalogue de problèmes : une entrée par problème classique (bipartite matching, longest path, TSP…) avec variantes et liens vers les implémentations (le site propose du code).
• Chapitres clés : structures de données (chapitre 3), tri (chapitre 4), graphes (chapitres 5–6), DP (chapitre 8).
• Approche de conception : commencer par brute force, puis améliorer — méthode très alignée avec les entretiens.
• Heuristiques pour NP-difficiles : simulated annealing, genetic algorithms (chapitre 12).

Méthodologie de lecture

• Partie I : lecture continue pour les fondations.
• Partie II : lecture par besoin — quand vous rencontrez un problème au travail, cherchez l'entrée correspondante dans le catalogue.
• Idéal comme référence professionnelle : c'est le livre à poser sur son bureau, plus que CLRS.

---

6. Comparaison et choix du livre

Conseils selon le profil :

• Développeur visant un entretien : Cracking the Coding Interview + Skiena (partie I) + LeetCode.
• Étudiant en master : Sedgewick (intuition) puis CLRS (rigueur) ; Kleinberg pour la conception.
• Ingénieur chercheur : CLRS complet + Kleinberg (randomisation, approximation).
• Ingénieur terrain : Skiena en référence de bureau.

---

7. Plan de lecture intégré

Parcours 6 mois (recommandé)

Règle d'or

Un chapitre lu sans problème résolu est un chapitre oublié. Chaque session de lecture doit être suivie de 1 à 2 exercices du chapitre 17 ou de la plateforme choisie (chapitre 20).

---

8. Lectures prioritaires détaillées

CLRS — les 12 chapitres indispensables

Sedgewick — la feuille de route Coursera

• Part I : chapitres 1 (fundamentals), 2 (sorting), 3 (searching).
• Part II : chapitres 4 (graphs), 5 (strings).
• Chaque chapitre correspond à une semaine de cours ; les quizz et programmes de programmation accompagnent la lecture.

Kleinberg — par objectif

• Comprendre greedy : chapitre 4 complet (avec les preuves par échange).
• Comprendre la DP avancée : chapitre 6.
• Flow : chapitre 7 (sans lui, la partie « applications » est inintelligible).
• NP-complétude : chapitres 8–9, puis approximation (10) et local search (12).

Cracking the Coding Interview — le parcours 6 semaines

Skiena — le catalogue au quotidien

1. Lire la partie I en continu (3-4 semaines).
2. Pour chaque problème rencontré au travail, chercher l'entrée du catalogue.
3. Les « war stories » se lisent comme des études de cas — une par semaine suffit.

---

9. Techniques de lecture active

Les livres techniques ne se lisent pas comme des romans. Ces méthodes maximisent la rétention :

1. SQ3R : Survey (survoler), Question (formuler des questions), Read, Recite (réciter de mémoire), Review.
2. Note-taking structurée : une page par algorithme — intuition, pseudo-code, complexité, 1 exemple.
3. Méthode Feynman : expliquer l'algorithme à voix haute comme à un débutant ; chaque flou = relecture.
4. Flashcards (chapitres flashcards/ de la formation) : les formules et complexités se mémorisent par répétition espacée.
5. Pomodoro : 25 min de lecture → 5 min de pause → 1 exercice associé.

Exemple de fiche par algorithme

# Dijkstra
- **Problème** : plus courts chemins depuis une source, poids ≥ 0.
- **Structure** : file prioritaire (tas min).
- **Pseudo-code** : relaxations itératives, tester d > dist[u].
- **Complexité** : O((V+E) log V), S = O(V+E).
- **Piège** : échoue sur poids négatifs → Bellman-Ford.
- **Exercice** : E17-81 (chapitre 19 pour le corrigé).

Prochaine étape : mettre ces connaissances à l'épreuve avec les simulations d'entretiens du chapitre 22.