Le catalogue des problèmes algorithmiques

La première moitié de The Algorithm Design Manual enseigne les techniques : analyse asymptotique, structures de données, parcours de graphes, programmation dynamique, réductions. La seconde moitié change complètement de registre. Skiena l'appelle The Hitchhiker's Guide to Algorithms — le guide du voyageur en algorithmique — et il s'agit d'un catalogue d'environ 75 problèmes algorithmiques qui surgissent réellement en pratique. Chaque entrée décrit ce que l'on sait du problème et donne des recommandations concrètes sur la marche à suivre lorsqu'il se présente dans votre application.

Le vrai message du livre tient dans ce catalogue. Pour un ingénieur, la compétence la plus rentable n'est presque jamais d'inventer un nouvel algorithme. C'est de reconnaître qu'un problème métier est, sous un déguisement, un problème classique déjà résolu, puis de savoir où trouver la meilleure solution connue et, idéalement, une implémentation éprouvée. Ce chapitre explique la philosophie du catalogue, comment l'utiliser, et dresse la carte de ses grandes catégories.

La philosophie : reconnaître plutôt qu'inventer

Skiena est explicite sur le statut de ce catalogue : « ce n'est pas un livre de cuisine ». Un livre de cuisine donnerait une recette unique et fermée ; or il y a trop de variantes de ce que les gens veulent réellement calculer. Le but est de vous orienter dans la bonne direction pour que vous résolviez votre propre problème, en identifiant au passage les écueils que vous rencontrerez et que vous devrez régler vous-même.

L'idée-force est qu'une immense proportion des besoins logiciels se ramène à un nombre fini de problèmes bien étudiés : trier, chercher le plus court chemin, apparier deux ensembles, trouver l'enveloppe convexe, détecter une sous-chaîne. Si vous savez nommer votre problème, vous savez le chercher. Et une fois trouvé, vous héritez de décennies de recherche : le meilleur algorithme connu, sa complexité, ses pièges, et des bibliothèques qui l'implémentent déjà.

Skiena ajoute une mise en garde franche sur ces implémentations : « supposez qu'elles contiennent toutes des bugs », certains sérieux, et respectez les conditions de licence avant tout usage commercial — beaucoup de ces codes ne sont pas open source.

Comment utiliser le catalogue

La méthode tient en quelques étapes simples, et elle est itérative.

1. Réfléchissez à votre problème et essayez de le nommer. Si le nom vous revient, allez directement à l'entrée correspondante dans l'index ou la table des matières.
2. Lisez l'entrée en entier. Chaque entrée contient des renvois vers d'autres problèmes voisins ; le bon problème est peut-être celui d'à côté.
3. Feuilletez le catalogue. Chaque problème est introduit par deux dessins — une instance d'entrée à gauche, le résultat à droite — pensés pour illustrer un comportement plus qu'une définition. L'exemple de l'arbre couvrant minimal, par exemple, montre comment regrouper des points en clusters. Une figure peut faire « tilt ».
4. Utilisez l'index sans crainte. Chaque problème y est listé sous plusieurs mots-clés et applications.
5. Si rien ne correspond, revenez à l'étape 1 : soit votre problème ne relève pas des algorithmes combinatoires, soit vous ne le comprenez pas encore assez bien.

L'anatomie d'une entrée

Chaque entrée du catalogue suit une structure fixe, qui est elle-même un mode d'emploi.

Champ	Ce qu'il vous donne
Input / Problem description	La définition formelle, pour lever l'ambiguïté des dessins.
Discussion	Les questions à se poser, un algorithme « vite fait » de départ, puis des pointeurs vers des méthodes plus puissantes si la première échoue.
Implementations	Les bibliothèques et codes disponibles, listés par utilité décroissante, avec une recommandation explicite quand un gagnant net existe.
Notes (en petits caractères)	L'histoire du problème et les résultats théoriques : meilleurs bornes connues, comparaisons empiriques, articles de synthèse.
Related Problems	Les renvois vers les problèmes voisins du catalogue.

Les sept grandes catégories

Le catalogue s'organise en sept familles. En voici la carte, avec pour chacune ses problèmes phares et les outils de référence.

1. Structures de données

Ce ne sont pas tant des algorithmes que les briques fondamentales autour desquelles on bâtit l'application. Skiena insiste sur deux conseils. D'abord, isolez l'implémentation derrière une interface (des appels explicites à initialiser, chercher, insérer) : cela rend le code plus propre et permet d'échanger une implémentation pour une autre sans douleur. Ensuite, en pratique, il est plus important d'éviter une mauvaise structure que de trouver la meilleure.

• Dictionnaires (dictionaries) — localiser, insérer, supprimer par clé. Pour 100 à 10 millions de clés, une table de hachage (hash table) bien réglée bat presque toujours un tableau trié. Au-delà de la mémoire vive (> 1 million d'éléments sur disque), un B-arbre (B-tree). Les arbres binaires de recherche équilibrés (balanced binary search trees), comme les arbres rouge-noir, restent le couteau suisse.
• Files de priorité (priority queues) — accès rapide au plus petit (ou plus grand) élément. Le tas binaire (binary heap) offre insertion et extraction du minimum en O(log n) et répond au besoin dans l'immense majorité des cas. Les tas de Fibonacci (Fibonacci heaps) accélèrent l'opération decrease-key, utile dans Dijkstra, mais leurs constantes sont lourdes ; les pairing heaps atteignent les mêmes bornes avec moins de surcoût.
• Arbres de suffixes et tableaux de suffixes (suffix trees and arrays) — trouver toutes les occurrences d'une requête q dans une chaîne de référence S. Souvent le héros caché qui fait passer un traitement de chaînes de O(n²) à du linéaire. Les tableaux de suffixes consomment environ quatre fois moins de mémoire et sont plus simples à implémenter.
• Structures pour graphes (graph data structures) — listes d'adjacence (adjacency lists) dans le cas général, matrices d'adjacence (adjacency matrices) seulement pour les petits graphes ou les graphes très denses.
• Structures d'ensembles et union-find (union-find) — maintenir une partition d'éléments en sous-ensembles disjoints, avec les requêtes « dans quel ensemble est x ? » et « x et y sont-ils ensemble ? ». Avec union par rang et compression de chemin (path compression), le coût est quasi constant. C'est le socle de l'algorithme de Kruskal.
• Kd-arbres (kd-trees) — partitionner l'espace en cellules pour des requêtes géométriques : recherche du plus proche voisin, recherche par plage (range search), localisation de point. Efficaces de 2 à ~20 dimensions ; au-delà, leur performance s'effondre (la fameuse malédiction de la dimension).

2. Problèmes numériques

Ils manipulent des nombres plutôt que des structures combinatoires, et c'est ici plus qu'ailleurs qu'il faut s'appuyer sur des bibliothèques mûres plutôt que recoder soi-même.

• Arithmétique en précision arbitraire (arbitrary-precision arithmetic) — additionner, multiplier, élever à la puissance de très grands entiers.
• Algèbre linéaire et résolution de systèmes (linear algebra) — élimination de Gauss et factorisations matricielles ; on s'en remet à des bibliothèques comme LAPACK.
• Programmation linéaire (linear programming) — optimiser une fonction objectif linéaire sous contraintes linéaires ; l'outil de modélisation général le plus puissant du chapitre.
• Génération de nombres aléatoires (random number generation) et factorisation / primalité (factoring and primality testing) — au cœur de la cryptographie.
• Transformée de Fourier rapide (FFT) — qui ramène la convolution et la multiplication de polynômes en O(n log n).

3. Problèmes combinatoires

Le cœur historique de l'algorithmique : trier, chercher, ordonnancer, énumérer.

• Tri (sorting) — l'opération la plus fondamentale ; non seulement elle ordonne, mais elle prépare le terrain pour quantité d'autres algorithmes.
• Recherche (searching) — recherche dichotomique dans des données triées.
• Ordonnancement (scheduling) — affecter des tâches à des ressources ou à des créneaux sous contraintes ; souvent facile dans sa version de base, NP-difficile dès qu'on ajoute des contraintes.
• Génération de permutations, sous-ensembles et partitions (permutations, subsets, partitions) — énumérer méthodiquement les objets combinatoires, par exemple pour une recherche exhaustive.

4. Graphes en temps polynomial

La famille la plus rentable : ces problèmes de graphes ont des solutions efficaces et bien comprises. Si vous parvenez à modéliser votre besoin comme l'un d'eux, vous avez gagné.

• Parcours (graph traversal) — BFS et DFS, brique de presque tout le reste.
• Composantes connexes (connected components) et tri topologique (topological sort) — ordonner les sommets d'un graphe acyclique orienté pour respecter les dépendances.
• Arbre couvrant minimal (minimum spanning tree) — algorithmes de Prim et Kruskal ; sert aussi au clustering.
• Plus courts chemins (shortest path) — Dijkstra pour les poids non négatifs (≥ 0), Bellman-Ford avec poids négatifs, Floyd-Warshall pour toutes les paires.
• Flot maximum (maximum flow) et couplage (matching) — dont le couplage biparti, sur lequel nous revenons plus bas.

5. Graphes difficiles (NP-difficiles)

Le miroir sombre de la catégorie précédente. Ces problèmes n'ont, sauf surprise, pas d'algorithme polynomial. Reconnaître qu'un problème tombe ici est en soi une victoire : cela vous évite de chercher une solution exacte rapide qui n'existe pas, et vous oriente vers les heuristiques, l'approximation ou la recherche exhaustive sur petites instances.

• Clique (clique), couverture par sommets (vertex cover), coloration de graphe (graph coloring).
• Voyageur de commerce (traveling salesman, TSP) et cycle hamiltonien (Hamiltonian cycle).
• Partition de graphe (graph partition) — découper un graphe en morceaux équilibrés, utile pour la décomposition hiérarchique des très grands graphes.

6. Géométrie algorithmique

Les problèmes où les données sont des points, des segments ou des polygones dans le plan ou l'espace.

• Enveloppe convexe (convex hull) — le plus petit polygone convexe englobant un nuage de points ; en quelque sorte le « tri » de la géométrie, en O(n log n).
• Triangulation (triangulation) — découper une région en triangles.
• Plus proche paire (closest pair) — les deux points les plus rapprochés, en O(n log n).
• Intersection de segments (segment intersection) et requêtes de plage (range search).

7. Ensembles et chaînes

Les problèmes sur des collections de sous-ensembles ou sur des séquences de caractères.

• Couverture et empaquetage d'ensembles (set cover, set packing) — choisir un nombre minimal de sous-ensembles couvrant l'univers ; NP-difficile, abondamment approché en pratique.
• Recherche de sous-chaîne (string matching) — localiser un motif exact dans un texte (Knuth-Morris-Pratt, Boyer-Moore).
• Appariement approché de chaînes (approximate string matching) — tolérer fautes et variations, via la distance d'édition.
• Plus longue sous-séquence commune (longest common subsequence) — par programmation dynamique ; au cœur de diff et de la bio-informatique.
• Compression de données (data compression) — Huffman, codages basés sur les dictionnaires.

Un tableau récapitulatif

Pour ancrer la carte, voici, par catégorie, un problème emblématique, l'outil de référence et sa complexité typique.

Catégorie	Problème emblématique	Algorithme / structure	Complexité
Structures de données	Dictionnaire	Table de hachage	O(1) amorti par opération
Structures de données	Partition disjointe	Union-find (rang + compression)	quasi O(1) amorti
Numérique	Optimisation sous contraintes	Programmation linéaire (simplexe)	exponentiel pire cas, rapide en pratique
Combinatoire	Tri	Mergesort / Quicksort	O(n log n)
Graphes faciles	Plus court chemin (poids ≥ 0)	Dijkstra + tas	O((n + m) log n)
Graphes faciles	Affectation optimale	Couplage biparti (flot)	polynomial
Graphes difficiles	Tournée optimale	TSP (heuristiques, B&B)	NP-difficile
Géométrie	Englober un nuage de points	Enveloppe convexe	O(n log n)
Chaînes	Comparer deux séquences	Plus longue sous-séquence commune	O(nm)

Modéliser : du besoin métier au problème du catalogue

Tout l'art consiste à reconnaître le problème classique caché sous un énoncé métier. Prenons un cas typique : vous devez affecter k employés à k postes, chaque employé ayant une compétence (un coût ou un score) variable selon le poste, et chaque poste ne pouvant recevoir qu'une personne. Comment maximiser le score total des affectations ?

Tâtonner avec des règles ad hoc (« on commence par les employés les plus polyvalents… ») mène à des heuristiques fragiles et sous-optimales. Le réflexe du catalogue est de dessiner le problème comme un graphe : un sommet par employé d'un côté, un sommet par poste de l'autre, une arête pondérée entre chaque employé et chaque poste qu'il peut occuper.

   Employés          Postes
   ┌───────┐  12     ┌───────┐
   │ Alice │─────────│ Front │
   │       │╲   8   ╱│       │
   └───────┘ ╲     ╱ └───────┘
   ┌───────┐  ╲   ╱  ┌───────┐
   │  Bob  │───╳─────│ Back  │
   │       │  9      │       │
   └───────┘         └───────┘

   But : choisir un sous-ensemble d'arêtes tel que
   chaque sommet est couvert au plus une fois,
   en maximisant la somme des poids.

Cette image est exactement celle du couplage biparti de poids maximal (maximum-weight bipartite matching), un problème du catalogue résolu en temps polynomial (via le flot maximum à coût minimum, ou l'algorithme hongrois). Vous n'avez rien à inventer : vous nommez le problème, vous prenez la bibliothèque qui l'implémente, et vous obtenez l'affectation optimale garantie.

La démarche est toujours la même : décrire l'entrée et la sortie en termes abstraits (ensembles, graphe, points, chaînes), feuilleter le catalogue jusqu'à reconnaître la forme, lire l'entrée pour connaître la complexité et les pièges, puis brancher une implémentation existante. Et si aucune forme ne colle, c'est le signal qu'il faut mieux comprendre — ou reformuler — son propre problème.

À retenir

• La seconde moitié du livre est un catalogue de ~75 problèmes classiques : son message central est que reconnaître un problème connu vaut bien plus que d'en inventer un nouveau.
• Méthode d'usage : nommer son problème, lire l'entrée en entier, feuilleter les figures et l'index, itérer ; chaque entrée donne discussion, implémentations (par utilité décroissante) et problèmes voisins.
• Le catalogue couvre sept familles : structures de données, numérique, combinatoire, graphes faciles (polynomiaux), graphes difficiles (NP-difficiles), géométrie, ensembles et chaînes.
• La frontière facile / difficile est cruciale : plus court chemin vs plus long chemin, arbre couvrant vs cycle hamiltonien. Savoir de quel côté on est évite de chercher l'impossible.
• Modéliser, c'est traduire : une affectation devient un couplage biparti, un planning une coloration, des dépendances un tri topologique. L'effort est dans la reconnaissance, pas dans le code.
• Ne réinventez pas la roue : préférez les bibliothèques éprouvées (LEDA, STL, Boost, Java Collections), mais vérifiez bugs et licences avant tout usage sérieux.