Qu’est-ce que la programmation dynamique, avec des exemples

La programmation dynamique (DP) est un domaine exigeant de la programmation informatique, avec des compétences et des techniques spécifiques pour résoudre des problèmes. Oui, vous vous en sortirez en tant qu’ingénieur logiciel sans cela, mais la programmation dynamique a des applications importantes dans le monde réel et vous pouvez être interrogé à ce sujet lors d’un entretien avec un développeur.

Si vous débutez dans la programmation dynamique ou si vous souhaitez rafraîchir vos compétences, ce court article explique ce qu’est la programmation dynamique, avec des exemples et où vous pouvez développer vos compétences DP en ligne.

Qu’est-ce que la programmation dynamique ?

En programmation informatique, la programmation dynamique (DP) est une méthode de résolution de problèmes qui structure et simplifie les problèmes complexes en les décomposant en une cascade de sous-problèmes qui se chevauchent. En appliquant DP, plusieurs classes de problèmes peuvent être résolues efficacement.

DP trouve son origine dans les mathématiques et s’applique à divers domaines, de la bioinformatique à l’ingénierie des ressources en eau en passant par l’économie.

Comment fonctionne la programmation dynamique en informatique ?

La programmation dynamique doit être appliquée de manière appropriée pour être utilisée dans la programmation informatique. Un problème doit avoir deux caractéristiques pour convenir à DP :

1. Une sous-structure optimale : Un problème spécifié a une propriété de sous-structure optimale si sa solution optimale peut être dérivée des solutions optimales de ses sous-problèmes.

2. Sous-problèmes superposés : Le problème en question doit pouvoir être décomposé en une cascade de sous-problèmes réutilisables ou en un algorithme récursif capable de résoudre de manière répétée des sous-problèmes sans en générer de nouveaux.

Ces deux propriétés sont essentielles à l’utilisation de DP. Si la solution optimale est trouvée en utilisant des sous-problèmes qui ne se chevauchent pas, DP ne peut pas être utilisé. Plutôt, diviser et conquérir est utilisé. De même, des algorithmes de tri comme tri par fusion et tri rapide ne sont pas DP.

Programmation récursive et dynamique

La récursivité est une propriété clé des sous-structures optimales utilisées dans DP. La récursivité est simplement un processus qui se répète, comme lorsque vous vous tenez entre deux miroirs et que votre réflexion se répète encore et encore (l’effet Droste).

Les sous-structures optimales ont des cascades de problèmes qui se résolvent continuellement et le problème principal récursivement.

Un algorithme récursif dans DP ne génère pas de nouveaux sous-problèmes, ce qui réduit l’espace occupé par les sous-problèmes individuels qui se chevauchent. Idéalement, les mêmes sous-problèmes devraient être résolus encore et encore.

Principaux types de programmation dynamique ?

Il existe deux types ou méthodes de DP qui dépendent de la façon dont vous abordez un problème. Les deux méthodes utilisent des solutions de mémorisation, de stockage et de tabulation afin qu’elles puissent être récupérées rapidement, ce qui évite de répéter le calcul.

De haut en bas

Dans l’approche descendante, la solution à un problème est récursive, permettant la mémorisation des solutions aux sous-problèmes qui se chevauchent. Les nouveaux sous-problèmes ultérieurs sont résolus en se référant au cache de données mémorisé pour voir si une solution est déjà présente. Si le sous-problème n’a pas été résolu auparavant, celui-ci et sa solution sont ajoutés au cache de mémorisation.

La DP descendante est simple à comprendre et à utiliser car elle facilite la résolution ciblée des sous-problèmes. Vous pouvez le déboguer facilement, mais cette approche de récursivité peut utiliser beaucoup de mémoire cache, ce qui peut entraîner des erreurs de débordement de pile.

De bas en haut

L’approche ascendante, également appelée tabulation ou remplissage de tableau, utilise la tabulation pour créer un enregistrement des sous-problèmes et des solutions stockés. Il utilise ensuite les sous-problèmes résolus tabulés pour une reformulation ascendante du problème. Les sous-problèmes plus petits sont résolus, les solutions étant exploitées pour résoudre des sous-problèmes plus importants. La boucle For peut être utilisée pour itérer les sous-problèmes.

Exemple : Programmation dynamique et série de Fibonacci

Un exemple pratique de programmation dynamique en action travaillant avec la série de Fibonacci :

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…

Avec les nombres de Fibonacci (F_n), tout nombre de la séquence est la somme des deux nombres précédents. Comme la valeur de ‘n’ dans F_n augmente, l’échelle et la complexité du calcul de ces nombres augmentent.

DP peut être utilisé pour calculer n’importe quel nombre de Fibonacci. En utilisant DP, vous n’avez pas besoin de générer un arbre récursif ou de résoudre des problèmes encore et encore. Utilisez simplement les valeurs précédemment calculées. Voici à quoi ressemble le code pour une implémentation de cette série en utilisant la méthode descendante :

Pourquoi la programmation dynamique est-elle importante ?

La programmation dynamique n’est pas une partie importante du paysage de la programmation moderne. En effet, il n’est généralement pas directement utilisé dans le développement contemporain au niveau de la production

De nombreux ingénieurs compétents se sont établis sans avoir plus qu’une connaissance passagère de DP, bien qu’il fasse partie des principaux langages de programmation tels que :

• Python
• Javascript
• Rubis
• PHP
• perle
• Lua

Une connaissance pratique de DP est précieuse pour les ingénieurs car elle peut aider les développeurs à créer des applications logicielles mieux structurées et plus efficaces.

L’architecture de services partagés moderne consiste en des applications indépendantes accédant aux ressources (mémoire, puissance de traitement, capacité du réseau, coûts) d’un pool partagé. Un code mal structuré avec une faible attention à la résolution de problèmes peut entraîner une consommation inutile de ressources, ce qui a un impact sur les performances des autres applications. DP aide à affiner le code logiciel pour éviter que cela ne se produise.

Exemples concrets de programmation dynamique

Il existe de nombreux exemples d’applications logicielles réelles qui utilisent DP pour rester agiles et efficaces et minimiser les exigences système pour les exécuter. Voici quelques exemples:

• Google Maps : Dans Google Maps, DP est utilisé pour identifier le chemin le plus court entre un point de départ unique et une variété de destinations.
• Moteurs de recherche : Pour calculer le degré de similarité entre deux éléments de contenu en ligne.
• Logiciel anti-plagiat : développement d’un algorithme de distance de document pour faciliter la détection du niveau de similarité entre les documents texte.
• Mise en réseau : Transfert séquentiel de données d’une source unique vers plusieurs récepteurs différents.
• Correcteurs orthographiques : algorithme de distance d’édition utilisé pour quantifier la différence entre deux mots et calculer le nombre d’opérations nécessaires pour changer un mot en un autre.

Bases de données/cache de la base de connaissances : stockage des requêtes/requêtes courantes dans la mémoire locale ou les caches accessibles. DP aide à empêcher la récupération répétée des données couramment utilisées à partir des serveurs, en faveur du stockage local.

Exemples de questions d’entretien sur la programmation dynamique

Si vous recherchez votre prochain emploi d’ingénieur logiciel ou de développeur, la connaissance de DP vous donnera l’avantage lors des entretiens d’embauche.

DP est une grande chose dans les entretiens techniques. Des entreprises technologiques de premier plan comme Google et Amazon défient régulièrement les candidats avec des questions de DP qui doivent être résolues sur place ! Il s’agit de tester la façon dont les développeurs pensent, et s’ils vont décomposer les tâches et trouver les moyens les plus économes en ressources pour résoudre les problèmes.

Voici quelques exemples de questions et réponses d’entretien de programmation dynamique

Outre l’équation de Fibonacci présentée ci-dessus, voici quelques questions d’entretien courantes sur la programmation dynamique, avec des exemples de réponses et de solutions :

Question 1 : Pouvez-vous expliquer les avantages et les inconvénients de la mémoïsation ?

(Indice : il s’agit d’une question sur les avantages et les inconvénients de l’approche descendante dans DP)

Répondre:

Les avantages de la mémorisation comprennent :

• Le codage est facile
• Un problème peut être abordé en écrivant un wrapper ou une annotation qui exécutera automatiquement la fonction récursive
• Les réponses peuvent être obtenues à partir d’un cache et utilisées pour plusieurs problèmes

Le principal inconvénient de la mémorisation est que si vous avez un grand nombre de calculs, vous risquez de manquer rapidement d’espace de pile.

Question 2 : Vous montez des escaliers. Vous pouvez monter une ou deux marches à la fois. Combien y a-t-il de façons différentes de grimper au sommet ?

(Indice : cette question est connue sous le nom de problème de « monter les escaliers »)

Réponse : Jetez un œil à l’approche de cette question d’entretien de codage courante dans cette vidéo :

Où puis-je pratiquer la programmation dynamique ?

L’acquisition de compétences en programmation dynamique renforce les capacités de réflexion et de résolution de problèmes des développeurs. DP peut également vous aider à réfléchir de manière plus globale aux problèmes et à développer des solutions inhabituelles mais efficaces. S’il est temps pour vous d’obtenir une formation ou des certifications en DP, voici 3 des meilleurs cours en ligne :

Une fois que vous êtes au courant, la pratique rend parfait!

Arrondir

La programmation dynamique ne fait peut-être pas partie de votre pile de développeurs, mais elle est importante pour les entreprises pour lesquelles vous souhaitez travailler. Comprendre et apprendre DP vous permettra non seulement de décrocher des emplois, mais aussi d’affiner vos compétences et de vous aider à écrire le code propre que votre développeur principal adorera !

Qu’est-ce que la programmation dynamique, avec des exemples FAQ (Foire aux questions)

Qu’est-ce que la mémorisation ?

En programmation, la mémorisation est une technique d’optimisation qui stocke les résultats des fonctions gourmandes en ressources dans un cache afin qu’elles puissent être appelées rapidement si elles sont à nouveau nécessaires. Cela augmente la vitesse et l’efficacité des programmes informatiques.

Qu’est-ce que la tabulation ?

La tabulation est un autre terme pour l’approche ascendante de la programmation dynamique. Un tableau est rempli de solutions des sous-problèmes les plus bas et utilisé pour calculer la réponse aux sous-problèmes de niveaux supérieurs jusqu’à ce que la solution d’origine soit trouvée.

Qu’est-ce que diviser pour mieux régner ?

Diviser pour régner est une autre technique de résolution de problèmes. Il prend le problème d’origine et le décompose en sous-problèmes connexes plus petits qui peuvent être résolus indépendamment.

L’entretien de codage Google est-il difficile ?

Oui. Cet entretien virtuel a la réputation d’être l’un des entretiens les plus difficiles du secteur tech. Les questions nécessitent des recherches et des exercices approfondis et couvrent généralement des sujets liés aux services Google. Les questions du DP sont souvent posées.

Amazon interroge-t-il les candidats aux entretiens d’ingénierie logicielle sur la programmation dynamique ?

Oui. Amazon n’hésite pas à poser des questions avancées de programmation dynamique aux candidats pour séparer les non préparés.