{"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\/es\/algoritmico\/terminacion-y-correccion-2\/","title":{"rendered":"Terminaci\u00f3n y correcci\u00f3n"},"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\/es\/algoritmico\/\">\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\">Algor\u00edtmico<\/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\/es\/\">\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\">Pagina de inicio<\/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\">Contenido<\/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=\"Tabla de contenido alternativo\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Palanca<\/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\/es\/algoritmico\/terminacion-y-correccion-2\/#Terminaison-et-correction\" >Terminaci\u00f3n y correcci\u00f3n<\/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\/es\/algoritmico\/terminacion-y-correccion-2\/#Exemple\" >Ejemplo<\/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\/es\/algoritmico\/terminacion-y-correccion-2\/#Exemple-difficile\" >Dif\u00edcil ejemplo<\/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\/es\/algoritmico\/terminacion-y-correccion-2\/#Outil-pour-la-terminaison-et-la-correction\" >Herramienta de terminaci\u00f3n y correcci\u00f3n<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Terminaison-et-correction\"><\/span>Terminaci\u00f3n y correcci\u00f3n<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Al crear un <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/\">algoritmo<\/a>, se deben tener en cuenta los siguientes tres criterios: terminaci\u00f3n, correcci\u00f3n y <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/complejidad-en-el-tiempo\/\">complejidad<\/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;\">La terminaci\u00f3n garantiza que el algoritmo termina despu\u00e9s de un cierto n\u00famero de operaciones elementales. La correcci\u00f3n asegura que el algoritmo d\u00e9 el resultado esperado cuando finalice.<\/div>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple\"><\/span>Ejemplo<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>Un ser humano y un perro no envejecen igual. Para determinar el equivalente humano de la edad de un perro de menos de 15 kg, utilizamos la siguiente tabla, donde x es la edad real del animal (en a\u00f1os) e y es el equivalente humano en t\u00e9rminos de envejecimiento.<\/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=\"algoritmo de terminaci\u00f3n y correcci\u00f3n\" width=\"250\" height=\"152\" title=\"\"><\/figure>\n<p><\/p>\n<p>Considere el siguiente algoritmo:<\/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=\"algoritmo de terminaci\u00f3n y correcci\u00f3n\" 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>Revisemos la terminaci\u00f3n. Es una suite de acondicionamiento con c\u00e1lculos elementales en su interior. Una vez que se han verificado todas las condiciones en orden, el algoritmo finaliza.<\/p>\n<p><\/p>\n<p>En cuanto a la correcci\u00f3n, el algoritmo realiza las operaciones descritas en la tabla.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple-difficile\"><\/span>Dif\u00edcil ejemplo<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>En general, la terminaci\u00f3n es dif\u00edcil de verificar porque no siempre sabemos, a priori, el n\u00famero de instrucciones realizadas. La correcci\u00f3n es complicada cuando uno est\u00e1 en presencia de<a href=\"https:\/\/complex-systems-ai.com\/es\/ayuda-con-la-decision\/\">ayuda con la decisi\u00f3n<\/a> o investigaci\u00f3n de operaciones. Entonces es necesario usar principios <a href=\"https:\/\/complex-systems-ai.com\/es\/logica-matematica-27\/\">Matem\u00e1ticas<\/a> para probar que el algoritmo es correcto.<\/p>\n<p><\/p>\n<p>Tomemos el ejemplo del c\u00e1lculo del mcd en modo iterativo.<\/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=\"algoritmo de terminaci\u00f3n y correcci\u00f3n\" 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>El algoritmo finaliza si se cumple la condici\u00f3n de parada del bucle, es decir, si se cancela y. En el bucle, y se reemplaza por un resto de m\u00f3dulo y. Entonces, con cada pasaje, disminuye estrictamente mientras permanece positivo o cero. Por lo tanto, y termina llegando a 0, luego salimos del ciclo. El algoritmo termina bien despu\u00e9s de un cierto n\u00famero de iteraciones.<\/p>\n<p><\/p>\n<p>Inicialmente, x = ay y = b. En el ciclo, reemplazamos (x, y) por (y, x mod y). Sabemos que pgcd (x, y) = pgcd (y, x mod y). Entonces, en cada iteraci\u00f3n, pgcd (x, y) = pgcd (a, b). Al final del ciclo, tenemos ay = 0, o pgcd (x, 0) = x. Por inducci\u00f3n deducimos que devolvemos pgcd (a, b). El algoritmo calcula correctamente el mcd deseado.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Outil-pour-la-terminaison-et-la-correction\"><\/span>Herramienta de terminaci\u00f3n y correcci\u00f3n<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;\">Llamamos convergente a una cantidad que toma sus valores en un conjunto bien fundado y que estrictamente disminuye con cada paso en un bucle. Un conjunto bien fundado es un conjunto totalmente ordenado en el que no hay una secuencia infinita estrictamente decreciente. La existencia de un bucle convergente para un bucle garantiza que el algoritmo termine saliendo de \u00e9l. Por ejemplo, en el caso del algoritmo de Euclides, y es un convergente.<\/div>\n<p><\/p>\n<p>Llamamos invariante a un bucle a una propiedad que, si es verdadera al entrar en un bucle, permanece verdadera despu\u00e9s de cada paso a trav\u00e9s de ese bucle. Por tanto, es cierto a la salida de este bucle. El invariante de bucle es an\u00e1logo al principio de inducci\u00f3n. La demostraci\u00f3n de un invariante de bucle adaptado permite probar la exactitud de un algoritmo. Por ejemplo, pgcd (a, b) = pgcd (x, y) es un ciclo invariante.<\/p>\n<p><\/p>\n<p>Tomaremos como ejemplo un algoritmo con aleatoriedad para probar las nociones de terminaci\u00f3n y correcci\u00f3n.<\/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=\"algoritmo de terminaci\u00f3n y correcci\u00f3n\" 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>En inform\u00e1tica, la aleatoriedad atribuye un valor en un rango de valores. El pseudoaleatorio est\u00e1 limitado por el tama\u00f1o del contenedor (int, double, etc.) o por el algoritmo utilizado (generaci\u00f3n de un n\u00famero m\u00f3dulo un n\u00famero muy grande). En el algoritmo, asumimos que nyp son enteros estrictamente positivos. Si estos tienen una operaci\u00f3n que lo hace negativo, entonces se asignar\u00e1 autom\u00e1ticamente el valor de 0.<\/p>\n<p><\/p>\n<p>En la segunda parte de la condici\u00f3n, x decrece mientras que y tiene un valor aleatorio (estrictamente acotado). x por lo tanto tiende hacia el valor 0. En la primera parte de la condici\u00f3n, y decrece hacia 0 desde su valor aleatorio. Por lo tanto, concluimos que el algoritmo reduce y a 0, luego reduce x antes de volver a dar un valor a y.<\/p>\n<p>Por inducci\u00f3n concluimos que x tender\u00e1 a 0 despu\u00e9s de un cierto n\u00famero de iteraciones, por lo que ya no se visitar\u00e1 la segunda parte. Y y tambi\u00e9n tiende a 0, por lo que salimos del bucle. Por lo tanto, hemos probado que el algoritmo termina. No es \u00fatil hablar de correcci\u00f3n en este caso ya que no ten\u00edamos especificaciones para comprobar.<\/p>\n<p><\/p>\n<p>Se observa que alg\u00fan algoritmo no tiene prueba de terminaci\u00f3n que la famosa funci\u00f3n Syracuse.<\/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 Wiki home page Terminaci\u00f3n y correcci\u00f3n A la hora de crear un algoritmo se deben tener en cuenta los siguientes tres criterios: terminaci\u00f3n, correcci\u00f3n, 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\/es\/wp-json\/wp\/v2\/pages\/4096","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=4096"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/4096\/revisions"}],"predecessor-version":[{"id":17936,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/4096\/revisions\/17936"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1062"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=4096"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}