{"id":4096,"date":"2016-06-30T16:14:12","date_gmt":"2016-06-30T15:14:12","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=4096"},"modified":"2022-12-03T22:59:07","modified_gmt":"2022-12-03T21:59:07","slug":"terminaison-et-correction","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/algorithmic\/termination-and-correction\/","title":{"rendered":"Termination and Correction"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"4096\" class=\"elementor elementor-4096\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-799470f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"799470f\" 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-9f8a013\" data-id=\"9f8a013\" 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-0fb28aa elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"0fb28aa\" 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-9a9a87b\" data-id=\"9a9a87b\" 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-5d23f2c elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5d23f2c\" 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-ab58394\" data-id=\"ab58394\" 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-96b3b89 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"96b3b89\" 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:\/\/en.wikipedia.org\/wiki\/Program_analysis\" 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-32a000eb elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"32a000eb\" 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-65311626\" data-id=\"65311626\" 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-7bd0b7d5 elementor-widget elementor-widget-text-editor\" data-id=\"7bd0b7d5\" 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<p><\/p>\n<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\/termination-and-correction\/#Terminaison-et-correction\" >Termination and correction<\/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\/termination-and-correction\/#Exemple\" >Example<\/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\/termination-and-correction\/#Exemple-difficile\" >Difficult example<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/termination-and-correction\/#Outil-pour-la-terminaison-et-la-correction\" >Tool for termination and correction<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Terminaison-et-correction\"><\/span>Termination and correction<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>When creating a <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithm<\/a>, the following three criteria must be taken into account: termination, correction and <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/complexity-in-time\/\">complexity<\/a>.<\/p>\n<p><\/p>\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;\">Termination guarantees that the algorithm terminates after a certain number of elementary operations. The correction ensures that the algorithm gives the expected result when it terminates.<\/div>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple\"><\/span>Example<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>A human being and a dog do not age the same. To determine the human equivalent of the age of a dog under 15kg, we use the table below, where x is the animal&#039;s actual age (in years), and y is the human equivalent in term of aging.<\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"alignnone wp-image-4104 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity5.png\" alt=\"termination and correction algorithm\" width=\"250\" height=\"152\" title=\"\"><\/figure>\n<p><\/p>\n<p>Consider the following algorithm:<\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-4109 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity6.png\" alt=\"termination and correction algorithm\" width=\"436\" height=\"401\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity6.png 436w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity6-300x276.png 300w\" sizes=\"(max-width: 436px) 100vw, 436px\" \/><\/figure>\n<p><\/p>\n<p>Let&#039;s check the termination. It is a conditioning suite with elementary calculations inside. Once all the conditions have been verified in order, the algorithm ends.<\/p>\n<p><\/p>\n<p>As regards the correction, the algorithm performs the operations described in the table.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple-difficile\"><\/span>Difficult example<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>In general, the termination is difficult to verify because we do not always know, a priori, the number of instructions carried out. The correction is complicated when one is in the presence of<a href=\"https:\/\/complex-systems-ai.com\/en\/help-with-the-decision\/\">help with the decision<\/a> or operations research. It is then necessary to use principles <a href=\"https:\/\/complex-systems-ai.com\/en\/logic-math-27\/\">math<\/a> to prove that the algorithm is correct.<\/p>\n<p><\/p>\n<p>Let us take the example of calculating the gcd in iterative mode.<\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"alignnone wp-image-4118 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity7.png\" alt=\"termination and correction algorithm\" width=\"415\" height=\"341\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity7.png 415w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity7-300x247.png 300w\" sizes=\"(max-width: 415px) 100vw, 415px\" \/><\/figure>\n<p><\/p>\n<p>The algorithm ends if the stop condition of the loop is fulfilled, ie if y is canceled. In the loop, y is replaced by a modulo y remainder. So with each passage, strictly decreases while remaining positive or zero. Therefore, y ends up reaching 0, then we exit the loop. The algorithm ends well after a certain number of iterations.<\/p>\n<p><\/p>\n<p>Initially, x = a and y = b. In the loop, we replace (x, y) by (y, x mod y). We know that pgcd (x, y) = pgcd (y, x mod y). So on each iteration, pgcd (x, y) = pgcd (a, b). At the end of the loop, we have ay = 0, or pgcd (x, 0) = x. By induction we deduce that we return pgcd (a, b). The algorithm correctly calculates the desired gcd.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Outil-pour-la-terminaison-et-la-correction\"><\/span>Tool for termination and correction<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\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;\">We call convergent a quantity which takes its values in a well-founded set and which strictly decreases with each passage in a loop. A well-founded set is a totally ordered set in which there is no strictly decreasing infinite sequence. The existence of a convergent for a loop guarantees that the algorithm ends up exiting it. For example, in the case of Euclid&#039;s algorithm, y is a convergent.<\/div>\n<p><\/p>\n<p>We call a loop invariant a property which, if it is true when entering a loop, remains true after each passage through that loop. It is therefore true at the exit of this loop. The loop invariant is analogous to the principle of induction. The demonstration of an adapted loop invariant makes it possible to prove the correctness of an algorithm. For example, pgcd (a, b) = pgcd (x, y) is a loop invariant.<\/p>\n<p><\/p>\n<p>We will take as an example an algorithm with randomness in order to test the notions of termination and correction.<\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-4139 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity8.png\" alt=\"termination and correction algorithm\" width=\"450\" height=\"442\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity8.png 450w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/06\/complexity8-300x295.png 300w\" sizes=\"(max-width: 450px) 100vw, 450px\" \/><\/figure>\n<p><\/p>\n<p>In computer science, randomness attributes a value in a range of values. The pseudo-random is either limited by the size of the container (int, double, etc.) or by the algorithm used (generation of a number modulo a very large number). In the algorithm, we assume that n and p are strictly positive integers. If these have an operation making it negative, then the value of 0 will be automatically assigned.<\/p>\n<p><\/p>\n<p>In the second part of the condition, x decreases while y has a random value (strictly bounded). x therefore tends towards the value 0. In the first part of the condition, y decreases towards 0 from its random value. We therefore conclude that the algorithm decreases y to 0, then decrements x before giving a value to y again.<\/p>\n<p>By induction we conclude that x will tend to 0 after a certain number of iterations, so that the second part will no longer be visited. And y also tends to 0, so we exit the loop. We have therefore proved that the algorithm terminates. It is not useful to talk about correction in this case since we had no specifications to check.<\/p>\n<p><\/p>\n<p>It is noted that some algorithm does not have proof of termination than the famous Syracuse function.<\/p>\n<p><\/p>\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>Algorithms Home page Wiki Termination and correction When creating an algorithm, the following three criteria must be taken into account: termination, correction, etc. <\/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-4096","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/4096","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=4096"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/4096\/revisions"}],"predecessor-version":[{"id":17936,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/4096\/revisions\/17936"}],"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=4096"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}