Programmation dynamique<\/a>.<\/p>\n
\n","protected":false},"excerpt":{"rendered":"Diviser pour r\u00e9gner Lorsque vous avez appris \u00e0 effectuer une addition pos\u00e9e, vous avez appliqu\u00e9 un algorithme d\u00e9coupant les nombres en chiffres sur lesquels l’op\u00e9ration d’addition devenait \u00e9l\u00e9mentaire, puisqu’elle consistait \u00e0 additionner deux chiffres; la propagation de la retenue \u00e9ventuelle combinant alors les additions des sous-instances pour obtenir le r\u00e9sultat. Cet algorithme entre dans la cat\u00e9gorie des algorithmes de type diviser pour r\u00e9gner. Ce principe algorithmique dit diviser pour r\u00e9gner consiste \u00e0\u202f: diviser l’instance d’un probl\u00e8me en sous-instances, traiter ind\u00e9pendamment ces sous-instances, combiner les diff\u00e9rents r\u00e9sultats obtenus pour construire une solution au probl\u00e8me initial. Un exemple classique de probl\u00e8me \u00e9tudi\u00e9 d\u00e8s le lyc\u00e9e et dont la r\u00e9solution s’appuie sur ce principe algorithmique est la recherche dichotomique. En effet, la partition divise la zone de recherche en deux parts de tailles \u00e9gales et on se concentre uniquement sur la bonne moiti\u00e9 en reproduisant ce m\u00e9canisme sur une nouvelle moiti\u00e9 et ainsi de suite de mani\u00e8re \u00e0 ramener la zone de recherche \u00e0 une unit\u00e9. Notons que dans ce cas, la r\u00e9solution d’un des deux sous-probl\u00e8mes se r\u00e9sume \u00e0 ne rien faire. Les algorithmes qui s’appuient sur ce principe sont souvent r\u00e9cursifs et op\u00e8rent sur des instances de plus en plus petites jusqu’\u00e0 ce que la taille de l’instance \u00e0 traiter rende la r\u00e9solution du probl\u00e8me simple voire triviale. Bien que ce ne soit pas une obligation, beaucoup d’algorithmes reposant sur ce principe sont r\u00e9cursifs, en effet si les sous-probl\u00e8mes ne sont qu’une \u00ab\u00a0r\u00e9duction\u00a0\u00bb du probl\u00e8me initial, il est tentant de leur appliquer \u00e0 nouveau le principe et ainsi de suite. Diviser et r\u00e9gner: cours, exercices et TP (pdf) Programmation dynamique Le paradigme diviser pour r\u00e9gner, et plus g\u00e9n\u00e9ralement la r\u00e9cursivit\u00e9 peuvent poser des probl\u00e8mes de redondance dans l’appel des fonctions. La programmation dynamique en sauvegardant dans une m\u00e9moire cache les r\u00e9sultats d\u00e9j\u00e0 obtenus \u00e9vite de refaire ces calculs connus dans les instances des sous-probl\u00e8mes. On utilise -bien s\u00fbr par abus de langage- ce terme de m\u00e9moire cache car en informatique, un cache est une couche de stockage de donn\u00e9es grande vitesse qui stocke des informations, de sorte que les utilisations futures soient plus rapides. C’est bien le but de la variable de type tableau ou liste qui sera utilis\u00e9e pour stocker les r\u00e9sultats et \u00e9viter les appels r\u00e9cursifs redondants. Le cours: Programmation dynamique.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"class_list":["post-496","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/pages\/496","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/comments?post=496"}],"version-history":[{"count":21,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/pages\/496\/revisions"}],"predecessor-version":[{"id":5526,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/pages\/496\/revisions\/5526"}],"wp:attachment":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/media?parent=496"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}