© TippaPatt/Shutterstock.com
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 débrouillerez en tant qu’ingénieur logiciel sans cela, mais la programmation dynamique a d’importantes applications dans le monde réel et vous pouvez être interrogé à ce sujet lors d’un entretien avec un développeur.
Si vous débutez avec la dynamique programmation ou 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 :
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. Sous-problèmes qui se chevauchent : 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é. Au lieu de cela, diviser pour régner est utilisé. De même, les algorithmes de tri comme le tri par fusion et le tri rapide ne sont pas DP.
La récursivité et la programmation dynamique
La récursivité est une clé propriété 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 résolvent le problème principal de manière récursive.
Un algorithme récursif dans DP ne génère pas de nouveaux sous-problèmes, en gardant la quantité d’espace repris par les sous-problèmes qui se chevauchent petits. Idéalement, les mêmes sous-problèmes devraient être résolus encore et encore.
Types clés 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.
Top-down
Dans l’approche top-down, 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 de bas en haut, également connue sous le nom de tabulation ou de 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 Fibonacci
Un exemple pratique de la programmation dynamique en action travaillant avec la série Fibonacci:
0, 1, 1, 2 , 3, 5, 8, 13, 21, 34, 55…
Avec les nombres de Fibonacci (Fn), tout nombre de la séquence est la somme des deux nombres précédents. À mesure que la valeur de « n » dans Fn 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 :
Le code pour calculer n’importe quel nombre de Fibonacci.
©”TNGD”.com
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 :
PythonJavaScriptRubyPHPPerlLua
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 réels 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 similitude 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 des documents texte.Mise en réseau : transfert séquentiel de données d’une source unique à plusieurs récepteurs différents.Vérificateurs orthographiques : l’algorithme de distance d’édition utilisé pour quantifier la différence entre deux mots sont 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 êtes à la recherche de 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 un élément important 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 décomposeront les tâches et trouveront 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 courantes d’entretien de 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émorisation ?
(Astuce : il s’agit d’une question sur les avantages et les inconvénients de l’approche descendante dans DP)
Réponse :
Les avantages de la mémorisation incluent :
le codage est facileUn 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 nombre grand ou profond de calculs, vous pouvez rapidement manquer d’espace de pile.
Question 2 : Vous montez st airs. Vous pouvez monter une ou deux marches à la fois. Combien y a-t-il de façons différentes de monter au sommet ?
(Indice : cette question est connue sous le nom de problème de”monter les escaliers”)
Réponse : Jetez un œil à l’approche pour 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 de suivre 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 !
Arrondi up
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 s’ils 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 désignant 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 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 demande-t-il aux candidats aux entretiens d’ingénierie logicielle des informations 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.