Introduction à la conception d'algorithmes

Un algorithme (algorithm) est une procédure permettant d'accomplir une tâche précise. C'est l'idée qui se cache derrière tout programme informatique digne de ce nom. Mais pour être intéressant, un algorithme ne doit pas résoudre un cas isolé : il doit résoudre un problème général et bien spécifié. Là réside la première distinction fondamentale de tout le livre de Skiena, celle entre un problème et une instance de problème.

Ce chapitre d'ouverture pose les fondations conceptuelles : qu'attend-on d'un bon algorithme, pourquoi la correction est-elle si difficile à garantir, et comment des heuristiques « de bon sens » peuvent-elles être catégoriquement fausses. Nous verrons aussi pourquoi la modélisation — traduire un problème du monde réel en structure abstraite standard — est l'étape la plus rentable de tout le processus.

Problème, instance et premier algorithme

Un problème algorithmique se définit en décrivant l'ensemble complet des entrées (instances) qu'il doit traiter, et la sortie attendue pour chacune. Prenons le tri (sorting) :

Problème : Tri Entrée : une séquence de n clés a₁, …, aₙ. Sortie : la permutation de la séquence telle que a₁ ≤ a₂ ≤ … ≤ aₙ.

Une instance serait {Mike, Bob, Sally, Jill} ou {154, 245, 568, 324}. Reconnaître que l'on a affaire à un problème général — et non à un cas particulier — est le premier pas vers sa résolution.

Skiena ouvre avec le tri par insertion (insertion sort), qui part d'un seul élément (trivialement trié) puis insère les éléments restants un à un en maintenant la liste triée. Notez sa généralité : il fonctionne aussi bien sur des noms que sur des nombres, pourvu qu'on dispose d'une comparaison <.

// Tri par insertion : O(n^2) dans le pire cas.
function insertionSort(s: number[]): void {
	for (let i = 1; i < s.length; i++) {
		let j = i;
		// Remonte s[j] tant qu'il est plus petit que son voisin.
		while (j > 0 && s[j] < s[j - 1]) {
			[s[j], s[j - 1]] = [s[j - 1], s[j]];
			j = j - 1;
		}
	}
}

Trois qualités, rarement réunies

On recherche trois propriétés chez un bon algorithme. On veut qu'il soit correct et efficace, tout en restant facile à implémenter. Ces objectifs ne sont pas toujours simultanément atteignables.

Qualité	Ce qu'elle garantit	Tension fréquente
Correct	Produit toujours le bon résultat	Souvent au prix de la simplicité
Efficace	Reste rapide quand n grandit	Souvent au prix de la lisibilité
Facile	Vite écrit, vite débogué	Souvent au prix de l'efficacité

Dans l'industrie, un programme qui donne des réponses « assez bonnes » sans ralentir l'application est souvent accepté, qu'un meilleur algorithme existe ou non. La question de l'optimum ne se pose en général qu'après de sérieux ennuis de performance ou de droit. Ce chapitre se concentre sur la correction ; l'efficacité est traitée au chapitre suivant.

L'optimisation de la tournée du robot

Considérons un problème issu de la fabrication de circuits imprimés. Un bras robotisé muni d'un fer à souder doit visiter une série de points de contact, puis revenir au point de départ — formant un cycle fermé. Comme le robot coûte cher, on veut la tournée la plus courte possible.

Problème : Optimisation de la tournée du robot Entrée : un ensemble S de n points dans le plan. Sortie : le plus court cycle qui visite chaque point de S.

L'idée la plus populaire est l'heuristique du plus proche voisin (nearest-neighbor heuristic) : partir d'un point p₀, marcher vers son plus proche voisin non visité, et recommencer jusqu'à épuisement, puis refermer la boucle.

// Heuristique du plus proche voisin : INCORRECTE.
type Point = { x: number; y: number };

function nearestNeighborTour(points: Point[]): Point[] {
	const remaining = [...points];
	const tour: Point[] = [remaining.shift()!];
	while (remaining.length > 0) {
		const last = tour[tour.length - 1];
		let best = 0;
		for (let i = 1; i < remaining.length; i++) {
			if (dist(remaining[i], last) < dist(remaining[best], last)) {
				best = i;
			}
		}
		tour.push(remaining.splice(best, 1)[0]);
	}
	return tour; // referme implicitement vers tour[0]
}

function dist(a: Point, b: Point): number {
	return Math.hypot(a.x - b.x, a.y - b.y);
}

Cet algorithme a tout pour plaire : simple, efficace, intuitif. Il a un seul défaut : il est complètement faux. Il trouve toujours une tournée, mais pas nécessairement la plus courte — ni même une bonne.

Le contre-exemple de Skiena est limpide. Placez des points sur une ligne, à des distances -21, -5, -1, 0, 1, 3, 11 du point 0. En partant de 0, l'algorithme saute gauche-droite-gauche-droite autour du zéro, alors que la tournée optimale parcourt simplement la ligne de gauche à droite. « Mais commençons par le point le plus à gauche ! » Vrai — jusqu'à ce qu'on tourne l'exemple de 90 degrés. Quel que soit le point de départ choisi, le plus proche voisin est condamné à échouer sur certaines configurations.

Une deuxième heuristique, fausse elle aussi

Skiena propose alors l'heuristique de la paire la plus proche (closest-pair heuristic) : relier de façon répétée la paire d'extrémités la plus proche dont la connexion ne crée pas de cycle prématuré. Chaque point commence comme sa propre chaîne ; on fusionne jusqu'à obtenir une chaîne unique, qu'on referme.

Cette règle résout correctement le contre-exemple précédent. Mais elle échoue sur deux rangées de points où l'écart vertical (1 − e) est légèrement inférieur à l'espacement horizontal (1 + e) : les paires les plus proches traversent le vide au lieu de longer le bord, et la tournée dépasse l'optimum de plus de 20 %.

L'algorithme correct… et inutilisable

On peut écrire un algorithme correct : énumérer les n! permutations des points et garder la plus courte. C'est le problème du voyageur de commerce (traveling salesman problem, TSP).

// TSP par force brute : CORRECT mais O(n!) — inutilisable.
function optimalTSP(points: Point[]): Point[] {
	let best: Point[] = points;
	let bestCost = Infinity;
	for (const perm of permutations(points)) {
		const c = tourCost(perm);
		if (c < bestCost) {
			bestCost = c;
			best = perm;
		}
	}
	return best;
}

Cet algorithme est garanti correct — mais désespérément lent. L'ordinateur le plus rapide du monde ne pourrait pas énumérer les 20! = 2 432 902 008 176 640 000 ordres de 20 points en une journée. Pour un vrai circuit où n ≈ 1000, tous les ordinateurs de la planète n'auraient pas fini avant la fin de l'univers.

Sélectionner les bons films

Passons à un problème où, cette fois, il existe une solution à la fois correcte et efficace. Vous êtes un acteur très demandé avec n propositions de films. Chaque offre fixe un premier et un dernier jour de tournage, et vous ne pouvez pas accepter deux films dont les périodes se chevauchent. Tous paient le même cachet : vous voulez donc le plus grand nombre de films sans conflit.

Problème : Ordonnancement de films Entrée : un ensemble I de n intervalles sur la droite. Sortie : le plus grand sous-ensemble d'intervalles mutuellement disjoints.

Plusieurs idées gloutonnes (greedy) viennent à l'esprit. Examinons-les — et leurs contre-exemples.

Heuristique	Critère de choix	Pourquoi c'est faux
Le plus tôt	Job qui commence le plus tôt	Un long film (« Guerre et Paix ») bloque tous les autres
Le plus court	Job le plus court	Un petit film peut en bloquer deux autres
Le plus tôt fini	Job qui finit le plus tôt	Correct (voir ci-dessous)

L'heuristique « commencer le plus tôt » échoue dès qu'un premier film très long tue toutes les autres opportunités. « Prendre le plus court » corrige ce cas précis, mais un court-métrage placé à cheval sur deux autres films peut nous limiter à la moitié du gain optimal.

La bonne idée : le plus tôt terminé

L'algorithme correct repose sur une intuition forte. Considérez le premier job à se terminer : l'intervalle x dont l'extrémité droite est la plus à gauche. D'autres jobs ont pu commencer avant x, mais ils se chevauchent tous, donc on ne peut en prendre qu'un seul de ce groupe. En choisissant x, on libère le maximum de place à droite : on ne peut jamais perdre en sélectionnant x.

// Ordonnancement optimal : glouton, O(n log n) avec le tri.
type Interval = { start: number; end: number; label: string };

function optimalScheduling(intervals: Interval[]): Interval[] {
	// Trier par date de fin croissante. O(n log n)
	const sorted = [...intervals].sort((a, b) => a.end - b.end);
	const chosen: Interval[] = [];
	let lastEnd = -Infinity;
	for (const job of sorted) {
		// On accepte le job s'il ne chevauche pas le dernier pris.
		if (job.start > lastEnd) {
			chosen.push(job);
			lastEnd = job.end;
		}
	}
	return chosen; // taille maximale garantie
}

Raisonner sur la correction

Comment distinguer un algorithme correct d'un imposteur ? L'outil principal est la preuve (proof). Skiena n'insiste pas sur les preuves formelles — difficiles à faire bien, trompeuses quand on les fait mal — mais sur des arguments honnêtes et limpides expliquant pourquoi un algorithme satisfait une propriété de correction non triviale.

Bien spécifier le problème

On ne peut pas prouver la correction d'un algorithme pour un problème flou. Une spécification a deux parties : l'ensemble des instances autorisées et les propriétés requises de la sortie. Deux pièges guettent la sortie : poser une question mal définie (« la meilleure route » — la plus courte ? la plus rapide ? celle avec le moins de virages ?) et créer des objectifs composés (« la plus courte route qui n'a pas plus du double de virages nécessaires »), bien définis mais pénibles à résoudre. Choisissez un seul critère.

Démontrer l'incorrection par contre-exemple

La meilleure façon de prouver qu'un algorithme est faux est d'exhiber une instance où il échoue : un contre-exemple (counter-example). Un bon contre-exemple a deux propriétés :

• Vérifiabilité — on peut calculer la réponse de l'algorithme et exhiber une meilleure réponse.
• Simplicité — tous les détails superflus sont éliminés, rendant la faille évidente.

Skiena livre une boîte à outils pour les dénicher :

• Penser petit — les contre-exemples du robot tenaient en six points, ceux des films en trois intervalles. Quand un algorithme échoue, c'est presque toujours sur un cas minuscule.
• Penser exhaustivement — pour deux intervalles, il n'y a que trois configurations (disjoints, chevauchants, imbriqués). On construit tous les cas à trois en partant de là.
• Chercher la faiblesse — face à un glouton « prends toujours le plus gros », demandez-vous pourquoi ce serait une erreur.
• Viser l'égalité — donnez à un glouton des éléments tous de même taille : il n'a plus rien sur quoi décider et peut renvoyer n'importe quoi.
• Chercher les extrêmes — les mélanges d'énorme et minuscule, de proche et lointain, sont plus faciles à analyser.

Récursion et induction : les deux faces d'une même pièce

Ne pas trouver de contre-exemple ne prouve pas qu'un algorithme est correct ; il faut une démonstration, et la méthode de choix est souvent l'induction mathématique (mathematical induction). Skiena livre ici sa révélation : la récursion est l'induction mathématique. Dans les deux, on a une condition générale qui décompose le problème en morceaux plus petits, et un cas de base qui termine la descente. Comprendre l'une, c'est comprendre l'autre.

La correction du tri par insertion se montre ainsi par induction :

Base    : un tableau d'un seul élément est trié par définition.
Hypothèse : après n-1 itérations, les n-1 premiers éléments
            sont triés.
Pas     : insérer x à sa place — entre le plus grand élément ≤ x
          et le plus petit élément > x — en décalant les autres.

La modélisation : l'étape la plus rentable

La modélisation (modeling) est l'art de formuler votre application en termes de problèmes bien compris et précisément décrits. C'est la clé pour appliquer les techniques algorithmiques au monde réel — et parfois, une bonne modélisation élimine le besoin de concevoir quoi que ce soit, en rattachant votre problème à ce qui a déjà été résolu.

Les applications réelles manipulent des objets réels, mais les algorithmes travaillent sur des structures abstraites. Pour exploiter la littérature, apprenez à décrire votre problème via ces structures fondamentales :

Structure	Représente	Mots-clés déclencheurs
Permutations	Arrangements, ordres	« tournée », « ordonnancement », « séquence »
Sous-ensembles	Sélections d'items	« cluster », « groupe », « comité », « sélection »
Arbres	Relations hiérarchiques	« hiérarchie », « ancêtre », « taxonomie »
Graphes	Relations entre paires	« réseau », « circuit », « web », « relation »
Points	Positions géométriques	« sites », « positions », « localisations »
Polygones	Régions géométriques	« formes », « régions », « frontières »
Chaînes	Suites de caractères	« texte », « motifs », « étiquettes »

Penser récursivement aux objets

Penser récursivement, c'est chercher de grandes choses faites de petites choses exactement du même type. Chacune des structures ci-dessus se décompose ainsi : retirez le premier élément d'une permutation de n items, et vous obtenez une permutation de n−1 items. Supprimez la racine d'un arbre, et vous obtenez une forêt de sous-arbres plus petits. Un graphe privé d'un sommet reste un graphe. Toute description récursive demande des règles de décomposition et des cas de base (l'ensemble vide, le sommet unique, le triangle pour un polygone). Ces décompositions définiront beaucoup des algorithmes du livre.

War story : la modélisation des médiums

Le président de « Lotto Systems Group » appelle Skiena. Son produit entraîne les clients à « visualiser » 15 numéros parmi 44, certains qu'au moins 4 seront gagnants. Il faut le plus petit ensemble de tickets garantissant un lot. Skiena reconnaît une instance du problème de couverture par ensembles (set cover), NP-complet, donc abordé par heuristiques.

La morale n'est pas algorithmique mais méthodologique. L'équipe modélisa le problème comme « couvrir tous les sous-ensembles gagnants », produisit 28 tickets… et le client répondit que 5 tickets suffisaient. Le modèle était faux : on n'avait pas besoin de couvrir explicitement toutes les combinaisons. La structure générale de la solution tenait bon ; il suffit de corriger quels sous-ensembles comptent comme couverts.

À retenir

• Un algorithme résout un problème général et bien spécifié (entrées → sortie) ; ne confondez jamais le problème avec une instance.
• On vise trois qualités — correct, efficace, facile — rarement réunies ; ce chapitre privilégie la correction.
• Des heuristiques « de bon sens » (plus proche voisin, plus court film, film le plus tôt) sont souvent catégoriquement fausses ; la bonne idée pour l'ordonnancement est le film qui se termine le plus tôt.
• Prouvez l'incorrection par un contre-exemple simple et vérifiable ; prouvez la correction par induction, qui n'est rien d'autre que la récursion.
• La modélisation vers une structure standard (permutation, sous-ensemble, arbre, graphe, points, chaîne) est le pas le plus rentable ; validez-la sur un petit cas avant de coder.
• Un bon algorithme bat le matériel rapide : aucun ordinateur ne sauve un O(n!) là où un glouton en O(n log n) triomphe.