La programmation dynamique n’est pas de la magie noire

La programmation dynamique n’est pas de la magie noire

• La programmation dynamique est une technique utilisée pour résoudre des problèmes complexes en les découpant en petits sous-problèmes.
• Cette technique est naturelle, et beaucoup d’algorithmes courants ne sont rien d’autre que l’application de la programmation dynamique à certains problèmes.
• Pour faciliter la compréhension de la programmation dynamique, l’article propose une introduction plus accessible ainsi qu’une explication détaillée.

Réclamation

• Le software engineering est souvent catastrophique en matière de dénomination.
• Des termes comme « bootstrap », « daemon », « cascading style sheets », « cookie » ou « intelligence artificielle » sont vagues ou trompeurs.
• Le terme « programmation dynamique » non plus n’a rien de particulièrement « dynamique » en soi ; il désigne en réalité une idée utilisée dans la conception d’algorithmes.

Mise en cache de base

• Quand on essaie de résoudre un problème en le divisant en petits sous-problèmes similaires, il peut être nécessaire de résoudre plusieurs fois les mêmes petits sous-problèmes.
• Avec l’exemple de la suite de Fibonacci, une simple fonction récursive répète plusieurs fois les mêmes calculs.
• On peut éviter ces calculs redondants en mettant les résultats en cache (ou via la mémoïsation).

Mise en cache optimisée

• Avec la mémoïsation, on conserve la récursion tout en calculant uniquement ce qui est nécessaire, au moment où cela devient nécessaire.
• On peut aussi adopter une autre approche en calculant à l’avance tout ce dont on aura besoin.
• Cette méthode résout le problème sans appels récursifs, et c’est précisément cela, la programmation dynamique.

Distance d’édition

• La distance d’édition entre deux chaînes est le nombre minimal de modifications nécessaires pour transformer l’une en l’autre.
• Elle peut être calculée en tenant compte des remplacements, insertions et suppressions de caractères, et se résout efficacement grâce à la programmation dynamique.
• Il faut trouver comment déduire la solution complète à partir des solutions aux petits sous-problèmes.

Advent of Code, Day 12

• Dans le problème de l’Advent of Code du 12 décembre 2023, il faut résoudre un nonogramme 1D.
• On peut le résoudre par force brute, mais avec une complexité exponentielle.
• À la place, on peut appliquer la programmation dynamique pour obtenir une solution efficace.

Conclusion

• La programmation dynamique n’est pas facile, mais elle n’est pas hors de portée pour la plupart des programmeurs.
• Si l’on comprend comment décomposer un problème en sous-problèmes, on peut utiliser la mémoïsation dans des situations variées, avec des gains importants par rapport à une implémentation naïve.
• Maîtriser la programmation dynamique permet de comprendre toute une classe d’algorithmes, de mieux saisir les compromis, et d’ouvrir la voie à d’autres optimisations.

L’avis de GN⁺

• La programmation dynamique est une technique essentielle pour résoudre efficacement des problèmes complexes : en mettant en cache les solutions aux petits sous-problèmes au lieu de recalculer les mêmes résultats, on peut fortement améliorer les performances.
• Cet article est particulièrement utile pour les ingénieurs logiciel débutants qui souhaitent comprendre les concepts de base de la programmation dynamique.
• Les exemples de la suite de Fibonacci et de la distance d’édition aident à saisir le concept de programmation dynamique et offrent un bon point de départ pour l’appliquer à des problèmes réels.

[GN⁺]

Avis Hacker News

• L’article explique utilement les algorithmes de programmation dynamique (DP) comme une mise en cache de la récursion.

  • Trouver une solution récursive est un excellent point de départ pour trouver une solution en DP.
  • Ajouter de la mémoïsation (memoization) à une solution récursive peut grandement améliorer les performances.
  • L’important n’est pas qu’il y ait un grand nombre de sous-problèmes dans l’arbre des appels, mais qu’il y ait un nombre relativement faible de sous-problèmes distincts.

• J’aime l’approche de l’article qui traite d’abord le problème de manière récursive, puis ajoute progressivement du cache avant de le réduire à la taille réellement nécessaire.

  • Il m’est déjà arrivé de bloquer ou de devoir fournir un gros effort en essayant de trouver directement une solution de programmation dynamique.
  • À l’avenir, je vais m’imposer cette approche étape par étape.

• L’une des belles applications de la programmation dynamique est l’alignement par paires de séquences d’acides nucléiques ou de protéines.

  • Par exemple, sequence alignment, l’algorithme de Needleman-Wunsch et l’algorithme de Smith-Waterman.

• Partage d’une expérience avec un professeur d’algorithmique exceptionnel.

  • Le professeur avait étudié à UCLA, et son cours sur la programmation dynamique était remarquable.
  • Il partait d’un problème simple mais à complexité exponentielle, le découpait en petits sous-problèmes, réduisait la complexité à un niveau polynomial, puis appliquait la mémoïsation pour la faire tomber à une complexité linéaire.
  • J’aimerais me souvenir des problèmes utilisés.

• Partage d’un lien vers l’article Dynamic Programming is not Black Magic.

  • L’article est devenu difficile d’accès à cause d’un trop grand nombre de visites (hug of death).

• Une personne qui a surtout appris la programmation en autodidacte explique que si on lui avait demandé d’utiliser la programmation dynamique en entretien d’embauche, elle n’aurait pas su de quoi il s’agissait.

  • Heureusement, cela ne lui est jamais arrivé, et comme elle connaissait la technique, elle l’a utilisée dans plusieurs entretiens.

• Le nom « programmation dynamique » peut ne pas sembler venir du domaine de la programmation.

  • En réalité, cela relève de l’optimisation et correspond à une méthode pour résoudre des problèmes de décision en temps discret.
  • La programmation dynamique permet de réduire fortement la dimension d’un problème d’optimisation en définissant une fonction de valeur V*.

• Une interrogation est soulevée : est-ce une erreur de ne penser qu’à la « mémoïsation » quand on entend « programmation dynamique » ?

  • Ce qui manque peut-être, c’est la capacité à découper intelligemment le problème pour utiliser efficacement la mémoïsation.

• La programmation dynamique n’est pas de la magie noire ; ce qui est difficile, c’est de prouver qu’un problème peut être traité de cette façon et d’en démontrer la correction.

  • Comme pour les algorithmes gloutons, une preuve formelle est nécessaire, souvent à l’aide de l’induction mathématique.

• Pour maîtriser la programmation dynamique, recommandation du livre d’algorithmes DPV et du cours Udacity de Georgia Tech.

  • C’est en s’exerçant à résoudre des problèmes qu’on apprend vraiment la programmation dynamique.