{"id":1732,"date":"2016-02-08T13:07:14","date_gmt":"2016-02-08T12:07:14","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=1732"},"modified":"2022-12-03T22:58:52","modified_gmt":"2022-12-03T21:58:52","slug":"diviser-pour-regner","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-rule\/","title":{"rendered":"Divide and rule"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"1732\" class=\"elementor elementor-1732\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-fd226f2 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"fd226f2\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-2975a7d\" data-id=\"2975a7d\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5cea53d elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5cea53d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Algorithmic<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-48b46df\" data-id=\"48b46df\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-0ddbda5 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"0ddbda5\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Home page<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-84acb83\" data-id=\"84acb83\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a54ac62 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"a54ac62\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Diviser_pour_r%C3%A9gner_(informatique)\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-1d3efab0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1d3efab0\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-2894f838\" data-id=\"2894f838\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-3e1e785d elementor-widget elementor-widget-text-editor\" data-id=\"3e1e785d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-rule\/#Diviser-pour-regner\" >Divide and rule<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-rule\/#Principe\" >Principle<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-rule\/#Exemple\" >Example<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Diviser-pour-regner\"><\/span>Divide and rule<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">The method of divide and conquer is a method which allows, sometimes to find effective solutions to algorithmic problems. The idea is to cut out the initial problem, of size <strong>not<\/strong>, into several smaller sub-problems, then recombine the partial solutions until the final solution is obtained.<\/div>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Principe\"><\/span>Principle<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<figure class=\"wp-block-image size-large\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/progdyn.png\" alt=\"Divide and rule\" width=\"757\" height=\"246\" title=\"\"><\/figure>\n\n<p>Unlike the <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/dynamic-programming\/\">dynamic programming<\/a>, the results of the sub-problems are only useful for the result of the parent problem.<\/p>\n\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p>The divide and conquer algorithm can be broken down into three steps:<\/p>\n<ol style=\"text-align: justify;\">\n<li>Divide: the problem is split into size sub-problems <strong>b \/ w<\/strong>. These sub-problems are of the same nature as their parent. We are therefore in the presence of <strong>To<\/strong> identical subproblems. When <strong>b = 2<\/strong>, we are talking about dichotomy.<\/li>\n<li>To rule: the sub-problems are solved recursively.<\/li>\n<li>Recombine: the solutions of the subproblems are recombined to reconstruct the solution to the initial problem.<\/li>\n<\/ol>\n<\/div>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple\"><\/span>Example<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>In order to better understand the construction of the algorithm, we will take the example of fast exponentiation. The principle of this <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithm<\/a> is to calculate x<sup>not<\/sup>.<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">A naive method would be to loop where a*= x with a = 1 initially. The <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/complexity-in-time\/\">complexity<\/a> of the naive method is therefore linear 0(n).<\/div>\n\n<p>In order to use the divide and conquer method, we need to find a mathematical program that allows us to rewrite our problem into equivalent subproblems. Since this is a recursive method, don&#039;t forget to include a final state. We are therefore in the presence of the following mathematical program:<\/p>\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" class=\"alignnone wp-image-1754 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/exprapide.png\" alt=\"Divide and conquer rapid exponentiation\" width=\"492\" height=\"99\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/exprapide.png 492w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/exprapide-300x60.png 300w\" sizes=\"(max-width: 492px) 100vw, 492px\" \/><\/figure>\n\n<p>The algorithm is as follows:<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<pre>double power (double x, int n) {\n   <strong>yew<\/strong> (n == 0) return 1;\n   <strong>else<\/strong> {\n      <strong>yew<\/strong> (n%2 == 0) return power (x * x, n \/ 2);\n      <strong>else<\/strong> return x * power (x * x, (n-1) \/ 2);\n      <strong>end if<\/strong>\n   <strong>end if<\/strong>\n}<\/pre>\n<\/div>\n\n<p>Its complexity is 0 (log n) - size of the complete binary tree at <strong>not<\/strong> tops.<\/p>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Algorithmics Wiki home page Divide and conquer The method of divide and conquer is a method that sometimes allows to find effective solutions to \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":1062,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1732","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1732","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=1732"}],"version-history":[{"count":5,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1732\/revisions"}],"predecessor-version":[{"id":18343,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1732\/revisions\/18343"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1062"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=1732"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}