Paradigmes de conception d'algorithmes
Les paradigmes de conception d'algorithmes sont les stratégies récurrentes de haut niveau — diviser pour régner, programmation dynamique, choix glouton et recherche exhaustive avec élagage — utilisées pour construire des algorithmes corrects et efficaces pour des problèmes computationnels.
Definition
Un paradigme de conception d'algorithmes est un modèle ou une stratégie générale pour résoudre une classe de problèmes, caractérisé par une manière de décomposer le problème et de combiner les sous-solutions, ainsi que par les propriétés structurelles qu'un problème doit posséder pour que le paradigme s'applique.
Scope
Ce domaine couvre les techniques génériques de construction d'algorithmes indépendantes de tout domaine de problème spécifique. Il aborde la manière dont la structure d'un problème (sous-structure optimale, sous-problèmes chevauchants, propriété de choix glouton, décomposabilité) suggère une stratégie correspondante, et comment chaque paradigme est raisonné pour sa correction et analysé pour son temps d'exécution. Il exclut les structures de données qui implémentent ces algorithmes (couvertes dans les structures de données fondamentales) et les limites théoriques de la complexité de ce que tout algorithme peut accomplir (couvertes dans la complexité et l'analyse des algorithmes).
Sub-topics
Core questions
- Quelle propriété structurelle d'un problème rend un paradigme donné applicable et correct ?
- Comment une décomposition récursive est-elle transformée en un algorithme efficace via la mémoïsation ou la tabulation ?
- Quand un choix localement optimal (glouton) conduit-il à une solution globalement optimale ?
- Comment le temps d'exécution d'un algorithme basé sur un paradigme est-il dérivé, par exemple via des récurrences ?
- Comment les paradigmes de recherche exhaustive élaguent-ils l'espace de recherche pour rester traitables sur des instances typiques ?
Key concepts
- diviser pour régner
- relations de récurrence
- programmation dynamique
- mémoïsation et tabulation
- choix glouton et arguments d'échange
- retour sur trace (backtracking)
- séparation et évaluation (branch and bound)
- sous-structure optimale
- recherche exhaustive et élagage
Key theories
- Optimal substructure
- Un problème possède une sous-structure optimale lorsqu'une solution optimale peut être assemblée à partir de solutions optimales à ses sous-problèmes ; cette propriété sous-tend à la fois la programmation dynamique et de nombreux algorithmes gloutons.
- Overlapping subproblems and memoization
- Lorsqu'une décomposition récursive revisite les mêmes sous-problèmes de manière répétée, le stockage de la solution de chaque sous-problème (mémoïsation ou tabulation ascendante) réduit la re-computation exponentielle à un temps polynomial — la base de la programmation dynamique.
- Greedy-choice property
- Certains problèmes admettent une solution globalement optimale construite en faisant de manière répétée le choix qui semble le meilleur à l'instant T ; la correction est généralement prouvée par un argument d'échange ou via la théorie des matroïdes.
Clinical relevance
Les paradigmes de conception constituent le vocabulaire de travail des logiciels pratiques : diviser pour régner sous-tend le tri rapide et le traitement du signal, la programmation dynamique alimente l'alignement de séquences en bioinformatique et les sous-routines de chemin le plus court, les méthodes gloutonnes sont à la base de l'ordonnancement et de la compression de données (codage de Huffman), et la méthode de séparation et d'évaluation (branch-and-bound) est centrale pour l'optimisation combinatoire et la recherche opérationnelle.
History
Le raisonnement diviser pour régner est antérieur aux ordinateurs mais est devenu central avec des algorithmes rapides tels que le tri fusion (mergesort) et la multiplication de Karatsuba dans les années 1960. Richard Bellman a introduit la programmation dynamique dans les années 1950. Le traitement systématique des paradigmes en tant que lentille unificatrice dans les manuels a mûri à travers des ouvrages tels que le texte de conception et d'analyse d'Aho, Hopcroft et Ullman, puis CLRS et Kleinberg-Tardos.
Key figures
- Richard Bellman
- Thomas H. Cormen
- Jon Kleinberg
- Éva Tardos
- Robert Sedgewick
Related topics
Seminal works
- cormen2009
- kleinberg2006
- sedgewick2011
Frequently asked questions
- Quelle est la différence entre la programmation dynamique et les algorithmes gloutons ?
- Les deux exploitent la sous-structure optimale, mais un algorithme glouton s'engage sur un choix localement optimal à chaque étape et ne le reconsidère jamais, tandis que la programmation dynamique considère et combine les solutions de tous les sous-problèmes pertinents. Les algorithmes gloutons sont plus rapides lorsqu'ils s'appliquent, mais sont corrects pour moins de problèmes.
- Comment savoir quel paradigme utiliser ?
- Examinez la structure du problème : décomposable en sous-problèmes indépendants suggère diviser pour régner ; des sous-problèmes chevauchants avec une sous-structure optimale suggèrent la programmation dynamique ; une propriété de choix glouton prouvable suggère un algorithme glouton ; et sinon, une recherche systématique avec élagage (retour sur trace ou séparation et évaluation) peut être nécessaire.