Comment concevoir un algorithme

Concevoir le bon algorithme pour une application donnée est un acte créatif majeur : prendre un problème et en extraire une solution sortie du néant. L'espace des choix possibles est immense — assez vaste pour vous laisser toute latitude de vous pendre. Ce chapitre est court, mais c'est l'un des plus précieux du livre, car il ne parle ni de tri ni de graphes : il parle de méthode.

Skiena part d'un constat lucide : la connaissance livresque ne suffit pas. Devenir un bon concepteur d'algorithmes exige une certaine attitude — la bonne approche de résolution de problème. Et cette attitude tient en une idée centrale : reconnaître un problème déjà résolu vaut presque toujours mieux que d'en inventer un nouveau. Le reste est une affaire de questions, posées dans le bon ordre, et d'honnêteté avec soi-même.

Procéder par questions

La clé de la conception d'algorithmes — comme de toute résolution de problème — est d'avancer en se posant des questions pour guider sa pensée. Et si on faisait ceci ? Et si on faisait cela ? Lorsqu'on bloque, la meilleure chose à faire est de passer à la question suivante. Dans une séance de remue-méninges, la personne la plus utile n'est pas celle qui explique pourquoi une idée ne marchera pas, mais celle qui répète : « Pourquoi ne pourrait-on pas faire comme ça ? » — car elle finira par tomber sur une approche imparable.

Mais poser les questions ne suffit pas : il faut y répondre, et de préférence par écrit, dans un journal. La bonne réponse à « Puis-je faire ainsi ? » n'est jamais « non », mais « non, parce que… ».

Stratégie et tactique

Gardez aussi à l'esprit la distinction entre stratégie et tactique. La stratégie, c'est la quête de la vue d'ensemble : le cadre autour duquel on construit le chemin vers le but. La tactique sert à gagner les petites batailles en chemin. Vérifiez en permanence que vous raisonnez au bon niveau : tant qu'on n'a pas de stratégie globale pour attaquer un problème, il est inutile de se soucier de tactique.

Niveau	Exemple de question	Quand s'en occuper
Stratégie	« Puis-je modéliser mon application comme un problème de graphe ? »	D'abord.
Tactique	« Liste ou matrice d'adjacence pour représenter le graphe ? »	Ensuite, à la lumière de la stratégie.

Les décisions tactiques sont critiques pour la qualité finale, mais elles ne s'évaluent correctement qu'une fois la stratégie arrêtée.

La checklist de conception

Voici la séquence de questions à dérouler avant d'écrire la moindre ligne de code. Les plus précoces — et les plus importantes — portent sur la compréhension du problème et ne réclament aucune expertise particulière.

1. Ai-je vraiment compris le problème ?

C'est l'étape la plus négligée, et la plus rentable. Avant tout, clarifiez les entrées et les sorties exactes.

• En quoi consiste précisément l'entrée ?
• Quels sont exactement les résultats ou la sortie attendus ?
• Puis-je construire un exemple assez petit pour le résoudre à la main ? Que se passe-t-il quand j'essaie ?
• L'optimalité est-elle indispensable ? Puis-je me contenter d'une réponse proche de l'optimum ?
• Quelle est la taille typique d'une instance ? 10 éléments ? 1 000 ? 1 000 000 ? La réponse change tout : un algorithme en O(n²) acceptable pour mille éléments devient impraticable pour un million.
• La vitesse est-elle critique ? Une seconde ? Une minute ? Une heure ? Un jour ?
• Quel budget d'implémentation ai-je ? Suis-je limité à un algorithme codable en une journée, ou puis-je expérimenter plusieurs approches et comparer ?
• Quelle formulation paraît la plus simple ? Problème numérique ? De graphe ? Géométrique ? De chaînes de caractères ? D'ensembles ?

2. Existe-t-il un algorithme simple ou une heuristique ?

Avant de sortir l'artillerie lourde, demandez-vous si une approche élémentaire suffit.

• La force brute (brute force) résout-elle correctement le problème en parcourant tous les sous-ensembles ou arrangements pour garder le meilleur ?
  • Si oui, pourquoi suis-je sûr qu'elle donne toujours la bonne réponse ?
  • Comment mesurer la qualité d'une solution une fois construite ?
  • Cette solution lente tourne-t-elle en temps polynomial ou exponentiel ? Mon instance est-elle assez petite pour s'en contenter ?
• Puis-je résoudre par une règle simple répétée — prendre le plus gros élément d'abord ? Le plus petit ? Un élément au hasard ?
  • Sur quels types d'entrées cette heuristique marche-t-elle bien ? Correspondent-ils aux données réelles de mon application ?
  • Sur quels types d'entrées échoue-t-elle ? Si je ne trouve aucun contre-exemple, puis-je prouver qu'elle marche toujours ?

La force brute n'est pas une honte : c'est souvent la référence de correction contre laquelle valider un algorithme plus malin, et parfois la réponse définitive quand n est petit.

3. Mon problème est-il au catalogue ?

C'est ici que se loge la grande leçon de Skiena : ne réinventez pas la roue. La Partie II du livre est un catalogue de problèmes classiques — tri, plus courts chemins, couverture, appariement, sac à dos… — avec, pour chacun, ce qui est connu et quelles implémentations existent.

• Que sait-on déjà du problème ? Une implémentation est-elle disponible ?
• Ai-je cherché au bon endroit ? Ai-je parcouru toutes les illustrations du catalogue, cherché tous les mots-clés à l'index ?
• Existe-t-il des ressources sur le Web ? Ai-je fait une recherche Google et Google Scholar ?

4. Y a-t-il des cas particuliers que je sais résoudre ?

Quand le cas général résiste, attaquez par les bords.

• Puis-je résoudre efficacement en ignorant certains paramètres de l'entrée ?
• Le problème devient-il facile si je fixe certains paramètres à des valeurs triviales (0 ou 1) ?
• Puis-je le simplifier au point de le résoudre efficacement ?
• Pourquoi cet algorithme de cas particulier ne se généralise-t-il pas à une classe plus large d'entrées ? La réponse éclaire souvent la difficulté réelle.
• Mon problème est-il un cas particulier d'un problème plus général du catalogue ?

5. Quel paradigme de conception s'applique ?

C'est le cœur technique. Chaque grande technique correspond à une question à se poser.

• Y a-t-il un ensemble d'éléments à trier (sorting) par taille ou par clé ? Cet ordre trié facilite-t-il la recherche de la réponse ?
• Puis-je scinder le problème en deux sous-problèmes plus petits, par exemple via une recherche dichotomique (binary search), ou en partitionnant « grands/petits » ou « gauche/droite » ? Cela suggère-t-il un diviser-pour-régner (divide-and-conquer) ?
• Les objets ou la solution ont-ils un ordre naturel de gauche à droite — caractères d'une chaîne, éléments d'une permutation, feuilles d'un arbre ? Puis-je exploiter cet ordre par programmation dynamique (dynamic programming) ?
• Certaines opérations reviennent-elles sans cesse — rechercher, trouver le plus grand/petit élément ? Une structure de données peut-elle accélérer ces requêtes ? Un dictionnaire / table de hachage (hash table) ? Un tas / file de priorité (priority queue) ?
• Puis-je utiliser de l'aléatoire — échantillonnage, ou tirage de nombreuses configurations dont on garde la meilleure ? Une forme d'aléatoire dirigé comme le recuit simulé (simulated annealing) ?
• Puis-je formuler le problème comme un programme linéaire (linear program), voire en nombres entiers ?
• Mon problème ressemble-t-il à SAT, au voyageur de commerce (traveling salesman), ou à un autre problème NP-complet ? Risque-t-il d'être NP-complet, donc sans algorithme efficace connu ?

Indice dans l'énoncé	Paradigme à tester
Un ordre trié simplifierait la réponse	Tri, recherche dichotomique
On peut couper le problème en deux	Diviser-pour-régner
Ordre naturel gauche-droite (chaîne, permutation)	Programmation dynamique
Mêmes requêtes répétées (min, recherche)	Tas, table de hachage
« Le meilleur choix local semble bon »	Glouton (greedy) — à prouver !
Énumérer toutes les configurations valides	Retour sur trace (backtracking)
Ressemble à TSP, SAT, coloration	Réduction, NP-complétude

6. Toujours bloqué ?

Si rien n'a fonctionné :

• Suis-je prêt à payer un expert ? Le livre renvoie vers des services de consultation.
• Et si je reprenais la liste depuis le début ? Certaines de mes réponses ont-elles changé lors du dernier passage ? Très souvent, la deuxième lecture débloque ce que la première avait laissé en suspens.

Correction et efficacité

Deux questions transversales doivent accompagner tout le processus, et trancher en dernier ressort. Un algorithme n'a de valeur que s'il est correct et assez efficace.

• Correction : disposez-vous d'une preuve que l'algorithme renvoie toujours la bonne réponse, ou d'un contre-exemple qui l'invalide ? Skiena insiste : ne faites jamais confiance à un algorithme « qui semble marcher ». Cherchez activement à le casser sur un petit cas avant qu'un utilisateur ne le fasse en production.
• Efficacité : l'analyse asymptotique confirme-t-elle qu'il tient dans le temps et la mémoire imposés par la question 1 ? Un O(2ⁿ) impeccable est inutile sur un million d'éléments.

Ces deux exigences forment le filtre final : une idée qui ne passe ni la preuve ni l'analyse retourne à la checklist.

Un mini-exemple de la démarche

Appliquons la méthode à un problème jouet. Étant donné un tableau d'entiers et une cible t, existe-t-il deux éléments dont la somme vaut t ?

Question 1 — Comprendre. Entrée : un tableau nums et un entier t. Sortie : un booléen. Cas limites : tableau vide, un seul élément, doublons, valeurs négatives. Taille typique : disons jusqu'à un million d'éléments, réponse attendue en quelques millisecondes.

Question 2 — Force brute. Tester toutes les paires donne immédiatement une solution correcte de référence.

// Force brute — correct mais O(n^2).
function aDeuxSommeBrute(nums: number[], t: number): boolean {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === t) return true;
    }
  }
  return false;
}

Pour un million d'éléments, O(n²) signifie ~10¹² opérations : inacceptable au regard de notre contrainte de temps (question 1). La force brute valide la correction, mais ne suffira pas.

Question 5 — Quel paradigme ? L'énoncé suggère une requête répétée : pour chaque élément x, « ai-je déjà vu t − x ? ». C'est exactement ce qu'accélère une table de hachage.

// Avec une table de hachage — O(n) en temps, O(n) en espace.
function aDeuxSomme(nums: number[], t: number): boolean {
  const vus = new Set<number>();
  for (const x of nums) {
    if (vus.has(t - x)) return true; // complément déjà rencontré
    vus.add(x);
  }
  return false;
}

Filtre final — Correction et efficacité. Correction : si une paire (a, b) existe avec a avant b, alors au moment où l'on traite b, a = t − b est déjà dans l'ensemble ; on renvoie true. Réciproquement, on ne renvoie true que sur un complément réellement vu. Efficacité : un seul passage, O(n) en temps et en mémoire — largement dans les clous.

On valide ensuite la version rapide contre la force brute sur de petites instances aléatoires : si les deux divergent une seule fois, c'est qu'un bug se cache. C'est tout l'intérêt d'avoir gardé la solution naïve.

nums = [3, 1, 4, 2], t = 6
  x=3 : vu(3)=∅ ? non → vus={3}
  x=1 : 6-1=5 ∈ vus ? non → vus={3,1}
  x=4 : 6-4=2 ∈ vus ? non → vus={3,1,4}
  x=2 : 6-2=4 ∈ vus ? OUI → true   (la paire 4+2)

En une demi-page, la checklist nous a fait passer d'un brouillard à une solution prouvée correcte, analysée, et un million de fois plus rapide que la première idée — sans éclair de génie, juste en déroulant les bonnes questions.

À retenir

• Reconnaître plutôt qu'inventer : avant de coder, cherchez votre problème au catalogue, dans la littérature et les bibliothèques. Le vrai travail est de l'identifier sous son nom standard.
• Comprendre d'abord : entrées, sorties exactes, cas limites, taille des données, contraintes de temps et d'optimalité. Ces questions ne demandent aucune expertise et débloquent l'essentiel.
• Procéder par questions, par écrit : la bonne réponse n'est jamais « non » mais « non, parce que… ». Distinguez stratégie (le cadre) et tactique (les détails).
• Essayez d'abord le simple : la force brute valide la correction et sert de référence ; une heuristique peut suffire — mais prouvez-la ou trouvez-lui un contre-exemple.
• Faites correspondre indice et paradigme : ordre trié → tri/dichotomie ; découpe → diviser-pour-régner ; ordre gauche-droite → programmation dynamique ; requêtes répétées → tas / table de hachage.
• Tranchez sur correction et efficacité : exigez une preuve (ou un contre-exemple) et une analyse asymptotique compatible avec vos contraintes. Bloqué ? Reprenez la liste depuis le début.