The Algorithm Design Manual

1. Les algorithmes sont des procédures destinées à résoudre des problèmes bien définis, avec pour objectifs la justesse, l’efficacité et la simplicité de mise en œuvre.

Pour être intéressant, un algorithme doit résoudre un problème général et précisément spécifié.

Définir la tâche. Un algorithme est avant tout une procédure conçue pour accomplir une tâche spécifique. Pour qu’un algorithme soit utile et pertinent, cette tâche doit être clairement définie, en précisant à la fois l’ensemble des entrées possibles qu’il doit traiter et la sortie attendue pour chaque cas d’entrée. La distinction entre un problème général et une instance particulière est essentielle.

Qualités souhaitables. Un bon algorithme vise trois propriétés fondamentales : la justesse, l’efficacité et la facilité d’implémentation.

• Justesse : il doit produire le résultat attendu pour toutes les entrées valides.
• Efficacité : il doit résoudre le problème rapidement tout en consommant un minimum de ressources.
• Facilité d’implémentation : il doit être simple à traduire en code fonctionnel.
  Ces objectifs peuvent parfois entrer en conflit, nécessitant des compromis selon les besoins de l’application.

Au-delà des opérations simples. Si les opérations élémentaires constituent les briques de base, un algorithme est une séquence de ces opérations, souvent agrémentée de boucles et de sous-programmes. Le temps d’exécution d’un algorithme se mesure en comptant ces étapes élémentaires, généralement selon le modèle RAM, qui suppose un coût uniforme pour les opérations simples et l’accès mémoire.

2. La justesse est primordiale et exige une démonstration rigoureuse, car les heuristiques intuitives échouent souvent.

Des algorithmes apparemment raisonnables peuvent facilement être incorrects.

L’intuition ne suffit pas. Il est rarement évident qu’un algorithme donné résout correctement un problème pour toutes les entrées possibles. Se fier à l’intuition ou tester quelques exemples est risqué, car des heuristiques logiques en apparence peuvent échouer de manière spectaculaire sur des contre-exemples souvent simples. L’heuristique du plus proche voisin pour le problème du voyageur de commerce ou celle du premier travail le plus tôt pour la planification de films illustrent bien ces approches intuitives produisant des résultats sous-optimaux ou erronés.

Algorithmes vs heuristiques. Il est crucial de distinguer algorithmes et heuristiques.

• Algorithmes : garantis de fournir un résultat correct pour chaque entrée valide.
• Heuristiques : souvent efficaces mais sans garantie de justesse ou d’optimalité.
  Pour les applications critiques, une heuristique est inacceptable à moins que ses limites soient parfaitement comprises et prises en compte.

Démontrer la justesse. Un algorithme correct nécessite une démonstration claire expliquant pourquoi il fonctionne pour toutes les entrées. Cela implique une formulation précise du problème, des hypothèses définies et un raisonnement logique rigoureux. Sans cette démonstration, on ne peut être certain de la fiabilité de l’algorithme.

3. Les outils mathématiques tels que l’induction et les contre-exemples sont essentiels pour raisonner sur la justesse des algorithmes.

Chercher des contre-exemples est la meilleure manière de réfuter la justesse d’une heuristique.

Détecter les failles. La façon la plus sûre de prouver qu’un algorithme est incorrect est de trouver un contre-exemple — une instance d’entrée spécifique pour laquelle l’algorithme ne produit pas le résultat attendu. Un bon contre-exemple doit être :

• Vérifiable : on peut calculer la sortie de l’algorithme et montrer une sortie meilleure ou correcte.
• Simple : il est petit et met en lumière la cause exacte de l’échec.
  Les techniques pour trouver des contre-exemples incluent penser petit, examiner exhaustivement les cas simples, chercher les faiblesses de l’algorithme (par exemple, les choix gloutons), viser les égalités dans les valeurs d’entrée et explorer les cas extrêmes.

Prouver la justesse. Pour les algorithmes supposés corrects, notamment récursifs ou incrémentaux, l’induction mathématique est une méthode de preuve puissante.

• Cas de base : montrer que l’algorithme est correct pour la plus petite taille d’entrée.
• Étape inductive : supposer la justesse pour une taille k-1 et démontrer la justesse pour la taille k en s’appuyant sur cette hypothèse.
  Il faut être vigilant aux conditions aux limites et s’assurer que l’hypothèse inductive s’applique bien aux sous-problèmes.

Sommes et analyses. La compréhension des sommes mathématiques est également cruciale, notamment pour analyser l’efficacité des algorithmes (abordée dans les chapitres suivants). Les formules des progressions arithmétiques et géométriques sont des outils fondamentaux pour exprimer et simplifier le travail effectué par les boucles.

4. La conception efficace d’algorithmes commence par la modélisation des problèmes réels à l’aide de structures combinatoires abstraites.

Modéliser votre application en termes de structures et d’algorithmes bien définis est l’étape la plus importante vers une solution.

Faire le lien entre réalité et théorie. Les problèmes du monde réel impliquent des objets et des relations complexes. Les algorithmes, eux, opèrent sur des structures abstraites rigoureusement définies. La modélisation est l’art de traduire votre application concrète et désordonnée en un problème clair exprimé à travers ces objets combinatoires fondamentaux.

Structures abstraites courantes :

• Permutations : ordres ou arrangements (ex. : parcours de robots, tri).
• Sous-ensembles : sélections ou collections (ex. : planification de films, sac à dos).
• Arbres : relations hiérarchiques (ex. : arbres généalogiques, systèmes de fichiers).
• Graphes : relations ou réseaux arbitraires (ex. : cartes routières, réseaux sociaux).
• Points : positions dans l’espace (ex. : localisation d’installations).
• Polygones : régions dans l’espace (ex. : frontières, obstacles).
• Chaînes de caractères : séquences de symboles (ex. : texte, ADN).

Nature récursive. Nombre de ces structures sont récursives — une grande instance peut se décomposer en plus petites instances du même type. Reconnaître cette structure récursive est la clé pour concevoir des algorithmes récursifs et des solutions par programmation dynamique. Une modélisation adéquate vous permet de tirer parti des algorithmes et structures de données bien connus issus d’une vaste littérature.

5. Ce livre met l’accent sur des techniques pratiques de conception d’algorithmes, incluant structures de données, programmation dynamique et algorithmes sur graphes.

Ce livre se veut un manuel de conception algorithmique, offrant un accès à la technologie des algorithmes combinatoires tant aux étudiants qu’aux professionnels de l’informatique.

Techniques fondamentales. La première partie du livre explore les techniques essentielles de conception d’algorithmes indispensables pour résoudre des problèmes concrets. Ces techniques constituent la boîte à outils algorithmique permettant de transformer des problèmes modélisés en solutions efficaces.

Domaines clés abordés :

• Structures de données : méthodes efficaces pour organiser et stocker les données afin d’en faciliter l’accès et la modification (ex. : tableaux, listes, arbres, tables de hachage).
• Programmation dynamique : technique pour résoudre des problèmes complexes en les décomposant en sous-problèmes qui se recoupent, en mémorisant les résultats pour éviter les recalculs.
• Parcours de graphes : méthodes systématiques pour visiter tous les sommets et arêtes d’un graphe (ex. : parcours en largeur, parcours en profondeur), base de nombreux algorithmes sur graphes.
• Retour sur trace (backtracking) : méthode de recherche systématique explorant toutes les solutions possibles aux problèmes combinatoires.
• Heuristiques : méthodes pratiques visant des solutions rapidement satisfaisantes, même si l’optimalité n’est pas garantie.

Accent pratique. Le livre privilégie l’application concrète et la conception plutôt que l’analyse purement théorique. Si la justesse est soulignée, les preuves mathématiques formelles sont souvent remplacées par des arguments informels, afin de mettre le lecteur sur la bonne voie le plus rapidement possible.

6. Le livre propose des ressources telles qu’un catalogue de problèmes, des implémentations et des récits d’expérience pour accompagner les concepteurs d’algorithmes.

Les bons concepteurs d’algorithmes s’appuient sur les épaules des géants.

Exploiter les connaissances existantes. Concevoir efficacement un algorithme ne signifie pas toujours inventer de zéro. Savoir quels problèmes ont déjà été étudiés et quelles solutions existent est une compétence cruciale. Le livre offre des ressources pour aider les concepteurs à bénéficier de l’expérience accumulée.

Ressources clés :

• Catalogue de problèmes algorithmiques : recueil de 75 problèmes importants rencontrés en pratique, avec descriptions, exemples d’entrées/sorties et solutions connues.
• Implémentations : accès à des codes solides pour de nombreux algorithmes, disponibles en ligne.
• Bibliographie étendue : références aux sources principales et lectures complémentaires.
• Composante électronique : site central (algorist.com) pour récupérer les codes et documents complémentaires.

Au-delà de la théorie. Ces ressources soulignent que la conception pratique d’algorithmes ne se limite pas à la compréhension des techniques, mais inclut aussi la connaissance des solutions et implémentations existantes. L’objectif est de modéliser correctement votre application puis d’accéder à la technologie algorithmique pertinente.

7. Les problèmes réels nécessitent souvent une modélisation et une validation rigoureuses, comme le montrent les récits d’expérience.

La leçon de ces histoires est que la conception et l’analyse d’algorithmes ne sont pas que théorie, mais des outils concrets à utiliser au moment opportun.

Contextualiser les algorithmes. Le livre comprend des « récits de guerre » — témoignages tirés de l’expérience de l’auteur avec des problèmes concrets. Ces histoires illustrent comment des problèmes algorithmiques surgissent en pratique, souvent comme sous-problèmes dans des projets plus vastes lorsque les solutions existantes s’avèrent insuffisantes.

Défis de la modélisation. Ces récits mettent en lumière le rôle crucial de la modélisation. L’histoire de la « modélisation psychique », par exemple, montre comment un modèle initial apparemment raisonnable d’un problème de loterie s’est révélé incorrect, conduisant à une solution erronée. Elle souligne la nécessité de :

• formuler soigneusement le problème en termes de structures abstraites,
• valider le modèle sur de petits exemples ou avec le client,
• être prêt à réviser le modèle s’il ne capture pas fidèlement l’essence du problème.

Les algorithmes comme outils. Ces récits renforcent l’idée que la conception et l’analyse d’algorithmes sont des outils pratiques à mobiliser au besoin. Ils illustrent la démarche de l’« algoriste » en action, montrant comment la maîtrise des concepts fondamentaux et des ressources disponibles permet de trouver des solutions efficaces à des défis complexes du monde réel.