{"id":1062,"date":"2016-08-22T14:36:19","date_gmt":"2016-08-22T13:36:19","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=1062"},"modified":"2024-02-11T19:46:45","modified_gmt":"2024-02-11T18:46:45","slug":"algorithmique","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/algorithmic\/","title":{"rendered":"Algorithmics 101"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"1062\" class=\"elementor elementor-1062\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-2ac4cbe elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2ac4cbe\" 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-1baa7f4\" data-id=\"1baa7f4\" 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-dbcd0f1 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"dbcd0f1\" 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\/2020\/04\/03\/theories-and-algorithms-2\/\">\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\">Theories<\/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-33518ee\" data-id=\"33518ee\" 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-79d06a5 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"79d06a5\" 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-04853fc\" data-id=\"04853fc\" 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-21786ef elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"21786ef\" 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\/Algorithme\" 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-7427644 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7427644\" 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-fed0e3c\" data-id=\"fed0e3c\" 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-66a1e94 elementor-widget elementor-widget-toggle\" data-id=\"66a1e94\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1071\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1071\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">I. Writing and modeling an algorithm<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1071\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1071\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/pseudo-language-and-flowchart\/\">Pseudo-language and flowchart<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/termination-and-correction\/\">Termination and correction<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/complexity-in-time\/\">Time complexity<\/a><\/li>\n<li><a title=\"Algorithm approximation\" href=\"https:\/\/en.wikipedia.org\/wiki\/Approximation_algorithm\" target=\"_blank\" rel=\"noopener\">Algorithm approximation<\/a><\/li>\n<\/ul>\n<p>Analysis:<\/p>\n<ul>\n<li><a title=\"\" href=\"https:\/\/en.wikipedia.org\/wiki\/Adversary_model\" target=\"_blank\" rel=\"noopener\">Adversary model<\/a><\/li>\n<li><a title=\"Algorithmic efficiency\" href=\"https:\/\/en.wikipedia.org\/wiki\/Algorithmic_efficiency\" target=\"_blank\" rel=\"noopener\">Algorithmic efficiency<\/a><\/li>\n<li><a title=\"Amortized analysis\" href=\"https:\/\/en.wikipedia.org\/wiki\/Amortized_analysis\" target=\"_blank\" rel=\"noopener\">Amortized analysis<\/a><\/li>\n<li><a title=\"Path length statement\" href=\"https:\/\/en.wikipedia.org\/wiki\/Instruction_path_length\" target=\"_blank\" rel=\"noopener\">Path length statement<\/a><\/li>\n<li><a title=\"List update problem\" href=\"https:\/\/en.wikipedia.org\/wiki\/Master_theorem_(analysis_of_algorithms)\" target=\"_blank\" rel=\"noopener\">Master theorem<\/a><\/li>\n<li><a title=\"Polylogarithmic function\" href=\"https:\/\/en.wikipedia.org\/wiki\/Output-sensitive_algorithm\" target=\"_blank\" rel=\"noopener\">Output-sensitive algorithm<\/a><\/li>\n<li><a title=\"\" href=\"https:\/\/en.wikipedia.org\/wiki\/Polynomial_delay\" target=\"_blank\" rel=\"noopener\">Polynomial delay<\/a><\/li>\n<li><a title=\"\" href=\"https:\/\/en.wikipedia.org\/wiki\/Potential_method\" target=\"_blank\" rel=\"noopener\">Potential method<\/a><\/li>\n<li><a title=\"Best, worst and average case\" href=\"https:\/\/en.wikipedia.org\/wiki\/Probabilistic_analysis_of_algorithms\" target=\"_blank\" rel=\"noopener\">Probabilistic analysis of algorithms<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1072\" class=\"elementor-tab-title\" data-tab=\"2\" role=\"button\" aria-controls=\"elementor-tab-content-1072\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">II. Programming paradigms and strategies<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1072\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"2\" role=\"region\" aria-labelledby=\"elementor-tab-title-1072\"><ul>\n<li><a title=\"\" href=\"https:\/\/en.wikipedia.org\/wiki\/Imperative_programming\" target=\"_blank\" rel=\"noopener\">Imperative<\/a>\n<ul>\n<li><a title=\"Object oriented programming\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Programmation_orient%C3%A9e_objet\" target=\"_blank\" rel=\"noopener\">Object oriented programming<\/a><\/li>\n<li><a title=\"\" href=\"https:\/\/en.wikipedia.org\/wiki\/Procedural_programming\" target=\"_blank\" rel=\"noopener\">Procedural programming<\/a>\u00a0<\/li>\n<\/ul>\n<\/li>\n<li><a title=\"\" href=\"https:\/\/en.wikipedia.org\/wiki\/Declarative_programming\" target=\"_blank\" rel=\"noopener\">Declarative<\/a>\n<ul>\n<li><a title=\"Functional programming\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Programmation_fonctionnelle\" target=\"_blank\" rel=\"noopener\">Functional programming<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/logic-programming\/\">Logic programming<\/a><\/li>\n<li><a class=\"mw-redirect\" title=\"Mathematical programming\" href=\"https:\/\/en.wikipedia.org\/wiki\/Mathematical_programming\" target=\"_blank\" rel=\"noopener\">Mathematical programming<\/a><\/li>\n<li><a title=\"\" href=\"https:\/\/en.wikipedia.org\/wiki\/Reactive_programming\" target=\"_blank\" rel=\"noopener\">Reactive programming<\/a>\u00a0<\/li>\n<\/ul>\n<\/li>\n<li><a title=\"Structured programming\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Programmation_structur%C3%A9e\" target=\"_blank\" rel=\"noopener\">Structured programming<\/a><\/li>\n<li><a title=\"Declarative programming\" href=\"https:\/\/en.wikipedia.org\/wiki\/Symbolic_programming\" target=\"_blank\" rel=\"noopener\">Symbolic programming<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1073\" class=\"elementor-tab-title\" data-tab=\"3\" role=\"button\" aria-controls=\"elementor-tab-content-1073\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">III. Algorithmic paradigms<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1073\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"3\" role=\"region\" aria-labelledby=\"elementor-tab-title-1073\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/recursive-programming\/\">Recursive programming<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/dynamic-programming\/\">Dynamic programming<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-rule\/\">Divide and conquer and dichotomy<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/algorithm-naif-greedy-enumeration-2\/\">Naive method - greedy algorithm - brute force<\/a><\/li>\n<li><a title=\"Backtracking\" href=\"https:\/\/en.wikipedia.org\/wiki\/Backtracking\" target=\"_blank\" rel=\"noopener\">Backtracking<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/branch-and-bound\/\">Branch and bound<\/a><\/li>\n<li><a title=\"Plum and search\" href=\"https:\/\/en.wikipedia.org\/wiki\/Prune_and_search\" target=\"_blank\" rel=\"noopener\">Plum and search<\/a><\/li>\n<li><a title=\"\" href=\"https:\/\/en.wikipedia.org\/wiki\/Kernelization\" target=\"_blank\" rel=\"noopener\">Kernelization<\/a><\/li>\n<li><a title=\"Dynamic programming\" href=\"https:\/\/en.wikipedia.org\/wiki\/Iterative_compression\" target=\"_blank\" rel=\"noopener\">Iterative compression<\/a><\/li>\n<li><a title=\"Sweep line algorithm\" href=\"https:\/\/en.wikipedia.org\/wiki\/Sweep_line_algorithm\" target=\"_blank\" rel=\"noopener\">Sweep line algorithms<\/a><\/li>\n<li><a title=\"\" href=\"https:\/\/en.wikipedia.org\/wiki\/Rotating_calipers\" target=\"_blank\" rel=\"noopener\">Rotating calipers<\/a><\/li>\n<li><a title=\"Kernelization\" href=\"https:\/\/en.wikipedia.org\/wiki\/Randomized_algorithm#Randomized_incremental_constructions_in_geometry\" target=\"_blank\" rel=\"noopener\">Randomized incremental construction<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1074\" class=\"elementor-tab-title\" data-tab=\"4\" role=\"button\" aria-controls=\"elementor-tab-content-1074\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">IV. Multi-agent programming<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1074\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"4\" role=\"region\" aria-labelledby=\"elementor-tab-title-1074\">Toggle Content<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\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-4e7226ea elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4e7226ea\" 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-6f399206\" data-id=\"6f399206\" 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-1de956bb elementor-widget elementor-widget-text-editor\" data-id=\"1de956bb\" 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_84 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\/#Algorithmique\" >Algorithmic<\/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\/#Transcrire-un-algorithme\" >Transcribe an algorithm<\/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\/#Structure-de-controle-et-structure-de-donnees\" >Control structure and data structure<\/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\/#Notions-de-terminaison-de-correction-de-completude\" >Notions of termination, correction, completeness<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/#Complexite-algorithmique\" >Algorithmic complexity<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"has-text-align-left\"><span class=\"ez-toc-section\" id=\"Algorithmique\"><\/span>Algorithmic<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><!-- \/wp:heading --><\/p>\n<p><!-- wp:paragraph {\"align\":\"left\"} --><\/p>\n<p class=\"has-text-align-left\">Algorithmics have been around forever, it is a thought process that is described in a logical manner. Although this system seems essential to us today for many sciences, the systematization of algorithmic writing has evolved over time and through technology. It began in the time of the Babylonians, until it was concretely established by Ren\u00e9 Descartes in the general method proposed by the <em>Discourse on Method<\/em> in 1637.<\/p>\n<p><img decoding=\"async\" class=\"aligncenter wp-image-11096 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/cropped-Capture.png\" alt=\"algorithmic\" width=\"97\" height=\"97\" title=\"\"><\/p>\n<p><!-- \/wp:paragraph --><\/p>\n<p><!-- wp:paragraph {\"align\":\"left\"} --><\/p>\n<p class=\"has-text-align-left\">Modern algorithms, including a so-called \u201cprogram\u201d language, made its debut shortly afterwards in 1677. The term we use today, \u201calgorithm\u201d, appears two centuries later.<\/p>\n<p><!-- \/wp:paragraph --><\/p>\n<p><!-- wp:paragraph {\"align\":\"left\"} --><\/p>\n<p class=\"has-text-align-left\">The algorithm of <abbr class=\"abbr\" title=\"Twentieth\">XX<sup>e<\/sup><\/abbr> and <abbr class=\"abbr\" title=\"Twenty first\">XXI<sup>e<\/sup><\/abbr> century is often based on formalisms like that of Turing machines, which provides a scientific framework for studying the properties of algorithms.<\/p>\n<p><!-- \/wp:paragraph --><\/p>\n<p><!-- wp:paragraph {\"align\":\"left\"} --><\/p>\n<p class=\"has-text-align-left\">With computer science, algorithms developed a lot in the second half of the <abbr class=\"abbr\" title=\"Twentieth\">XX<sup>e<\/sup><\/abbr> century and Knuth (1969), author of The Art of Computer Programming defines 5 properties which constitute the prerequisites of an algorithm.<\/p>\n<p class=\"has-text-align-left\">1. Finiteness: an algorithm must terminate after a finite number of steps<\/p>\n<p class=\"has-text-align-left\">2. Precise definition: each step of an algorithm must be defined precisely without ambiguity<\/p>\n<p class=\"has-text-align-left\">3. Inputs: quantities that are defined before the algorithm begins<\/p>\n<p class=\"has-text-align-left\">4. Outputs: quantities that have a specified relationship to inputs<\/p>\n<p class=\"has-text-align-left\">5. Performance: all the operations that the algorithm must perform must be sufficiently basic to be able in principle to be carried out in a finite period of time by a man using paper and a pencil.<\/p>\n<p>Markov (1967) defines an algorithm as \u201cAn exact prescription defining a processing process which leads from initial data to the final result\u201d.<\/p>\n<p>Which implies the following characteristics:<br \/>\u2022 Precision of the prescription leaving no room for arbitrariness and universal understanding \u2022 Possibility of starting with initial data which can vary within given limits \u2022 The orientation of the algorithm in the search for a desired result which must be obtain at the end of the execution from the initial data: this is the conclusion property of the algorithm.<\/p>\n<p>For Minsky (1967) the definition is even more direct:<br \/>\u201cA set of rules that tell us, from moment to moment, precisely how to behave\u201d<\/p>\n<p>And finally for Stone (1972)<br \/>\u201cAn algorithm is a set of rules that precisely defines a sequence of operations such that each rule is effective and defined and the sequence completes in a finite time. \u00bb<\/p>\n<p>It further specifies that:<br \/>\u201cfor those who follow the rules of the algorithm, they must be formulated so that they are followed mechanically without having to think\u201d<\/p>\n<p>For example :<br \/>If the instructions require extracting a square root and are performed by someone who knows how to do arithmetic but does not know how to extract a square root, then one must provide a set of rules for extracting a square root, so to satisfy the definition of the algorithm<\/p>\n<p>Many formal or theoretical tools have been developed to describe algorithms, study them, express their qualities, and be able to compare them:<\/p>\n<ul>\n<li>algorithmic structures: control structures and data structures.<\/li>\n<li>the notions of correctness, completeness and <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/termination-and-correction\/\">termination<\/a>.<\/li>\n<li>the theory of <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/complexity-in-time\/\">complexity<\/a>.<\/li>\n<\/ul>\n<h2><span class=\"ez-toc-section\" id=\"Transcrire-un-algorithme\"><\/span>Transcribe an algorithm<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>THE<b>natural language <\/b>: verbose and ambiguous, rarely used for complex algorithms but not prohibited.<br \/><a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/pseudo-language-and-flowchart\/\">Pseudocode<\/a> : a structured language, but no strict rules defined; Independent of any implementation<br \/><b>Organizational chart<\/b> : no ambiguity, good readability, writing in the form of standardized symbols<br \/>THE<b>programming languages<\/b> : normally intended to transcribe flowcharts into a form understandable by computers; can also be used to describe algorithms<br \/>THE<b>algorithmic languages<\/b> : language using pseudo-code composed of fixed rules, understandable by a computer, allowing the description and execution of algorithms.<\/p>\n<h2 class=\"has-text-align-left\"><span class=\"ez-toc-section\" id=\"Structure-de-controle-et-structure-de-donnees\"><\/span>Control structure and data structure<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>A control structure is a command that controls the order in which the various instructions of an algorithm or a computer program are executed. The processor is responsible for memorizing the address of the next instruction to be executed, the blocks (loops, if, etc.) or the subroutines.<\/p>\n<p><!-- \/wp:heading --><\/p>\n<p><!-- wp:html --><\/p>\n<p><!-- \/wp:html --><\/p>\n<p><!-- wp:paragraph {\"align\":\"left\"} --><\/p>\n<p class=\"has-text-align-left\">This sequence of instructions is also called the execution flow of a program and it can be represented using a <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a> of control flow or a <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/\">automaton<\/a>. Certain programming paradigm calling on several processors is then exposed to the problem of assignment of tasks in the processors.<\/p>\n<p>A data structure is a logical structure intended to contain data, in order to give them an organization allowing their processing to be simplified. There are many types of data structure depending on the actions to be performed on them, we will not delay any further on this subject.<\/p>\n<p><!-- \/wp:paragraph --><\/p>\n<p><!-- wp:html --><\/p>\n<p><!-- \/wp:html --><\/p>\n<p><!-- wp:paragraph {\"align\":\"left\"} --><\/p>\n<p class=\"has-text-align-left\">Each computer language has a type of control structure and data structure. The writing of an algorithm is very often based on widely used languages such as C, java, etc.<\/p>\n<p><!-- \/wp:paragraph --><\/p>\n<p><!-- wp:heading {\"align\":\"left\"} --><\/p>\n<h2 class=\"has-text-align-left\"><span class=\"ez-toc-section\" id=\"Notions-de-terminaison-de-correction-de-completude\"><\/span>Notions of termination, correction, completeness<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><!-- \/wp:heading --><\/p>\n<p><!-- wp:paragraph {\"align\":\"left\"} --><\/p>\n<p class=\"has-text-align-left\">Termination is the assurance that the algorithm will terminate in a finite time. The proofs of termination usually involve a strictly decreasing positive integer function at each step \/ iteration of the algorithm.<\/p>\n<p><!-- \/wp:paragraph --><\/p>\n<p><!-- wp:paragraph {\"align\":\"left\"} --><\/p>\n<p class=\"has-text-align-left\">Given the guarantee that an algorithm will finish, the proof of correctness must provide the assurance that if the algorithm ends by giving a proposed solution, then this solution is correct (in the sense that it answers the problem posed).<\/p>\n<p><!-- \/wp:paragraph --><\/p>\n<p><!-- wp:paragraph {\"align\":\"left\"} --><\/p>\n<p class=\"has-text-align-left\">The proof of completeness guarantees that, for a given problem space, the algorithm, if it finishes, will give a solution for each of the inputs of the algorithm.<\/p>\n<p style=\"text-align: justify;\"><strong>Termination<\/strong> : the algorithm has time complexity.<\/p>\n<p style=\"text-align: justify;\"><strong>Correction<\/strong> : any computed answer of the algorithm is solution of the problem.<\/p>\n<p style=\"text-align: justify;\"><strong>Completeness<\/strong> : the algorithm can calculate a response for any instance of the problem.<\/p>\n<p><!-- \/wp:html --><\/p>\n<p><!-- wp:heading {\"align\":\"left\"} --><\/p>\n<h2 class=\"has-text-align-left\"><span class=\"ez-toc-section\" id=\"Complexite-algorithmique\"><\/span>Algorithmic complexity<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><!-- \/wp:heading --><\/p>\n<p><!-- wp:html --><\/p>\n<p style=\"text-align: left;\">The complexity of algorithms is an evaluation of the cost of running an algorithm in terms of time (temporal complexity) or memory space (spatial complexity). The efficiency of an algorithm therefore depends on these two criteria, which we will try to minimize.<\/p>\n<p><!-- \/wp:html --><\/p>\n<p><!-- wp:html --><\/p>\n<p><!-- \/wp:html --><\/p>\n<p><!-- wp:html --><\/p>\n<p style=\"text-align: left;\">Algorithmic complexity makes it possible to learn about the intrinsic efficiency of a<br \/>algorithm: the \u201cnatural\u201d performance of an algorithm outside the environment in which the latter will be implemented.<\/p>\n<p>There are several types of analysis of the performance of an algorithm:<\/p>\n<div style=\"text-align: justify;\">\n<ul>\n<li>Optimistic analysis (best-case analysis or best-case analysis).<\/li>\n<li>The average analysis is often a factor in the programming paradigm used.<\/li>\n<li>Pessimistic analysis (worst-case analysis or worst-case analysis).<\/li>\n<\/ul>\n<\/div>\n<p style=\"text-align: left;\">Complexity classes are sets of problems which all have the same complexity according to a certain criterion. The best-known classes are classes defined on Turing machines (deterministic or non-deterministic - see the course on automata) with time and space constraints. There is a relationship between algorithmic complexity and its energy cost of operation, called Landauer&#039;s principle.<\/p>\n<p><!-- \/wp:html --><\/p>\n<p><!-- wp:paragraph {\"align\":\"left\"} --><\/p>\n<p><!-- \/wp:paragraph --><\/p>\n<p><!-- wp:paragraph {\"align\":\"left\"} --><\/p>\n<p class=\"has-text-align-left\">Here is a list of the most commonly encountered complexities:<\/p>\n<p><!-- \/wp:paragraph --><\/p>\n<p><!-- wp:table {\"className\":\"wikitable alignleft\"} --><\/p>\n<figure class=\"wp-block-table wikitable alignleft\">\n<table>\n<tbody>\n<tr>\n<th>Rating<\/th>\n<th>Complexity type<\/th>\n<\/tr>\n<tr>\n<td><img decoding=\"async\" class=\"mwe-math-fallback-image-inline tex\" src=\"https:\/\/upload.wikimedia.org\/math\/5\/e\/0\/5e079a28737d5dd019a3b8f6133ee55e.png\" alt=\"O (1)\" title=\"\"><\/td>\n<td>constant complexity: an assignment, an elementary calculation, etc.<\/td>\n<\/tr>\n<tr>\n<td><img decoding=\"async\" class=\"mwe-math-fallback-image-inline tex\" src=\"https:\/\/upload.wikimedia.org\/math\/3\/8\/3\/383a25a930115d3db44612f10b08f52a.png\" alt=\"O (\\ log (n))\" title=\"\"><\/td>\n<td>logarithmic complexity: dichotomy, <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/trees-and-trees\/\">tree<\/a><\/td>\n<\/tr>\n<tr>\n<td><img decoding=\"async\" class=\"mwe-math-fallback-image-inline tex\" src=\"https:\/\/upload.wikimedia.org\/math\/7\/b\/a\/7ba55e7c64a9405a0b39a1107e90ca94.png\" alt=\"We)\" title=\"\"><\/td>\n<td>linear complexity: a loop<\/td>\n<\/tr>\n<tr>\n<td><img decoding=\"async\" class=\"mwe-math-fallback-image-inline tex\" src=\"https:\/\/upload.wikimedia.org\/math\/8\/f\/1\/8f1bbb5f5c8a76d0d83f0cdab5eb3bf8.png\" alt=\"O (n \\ log (n))\" title=\"\"><\/td>\n<td>quasi-linear complexity: <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/divide-and-rule\/\">divide and rule<\/a>, tree<\/td>\n<\/tr>\n<tr>\n<td><img decoding=\"async\" class=\"mwe-math-fallback-image-inline tex\" src=\"https:\/\/upload.wikimedia.org\/math\/c\/d\/6\/cd641c6cabc83e0f7ff510bf812feca1.png\" alt=\"O (n ^ {2})\" title=\"\"><\/td>\n<td>quadratic complexity: nesting two loops<\/td>\n<\/tr>\n<tr>\n<td><img decoding=\"async\" class=\"mwe-math-fallback-image-inline tex\" src=\"https:\/\/upload.wikimedia.org\/math\/c\/c\/6\/cc61dd95a6c89f84f5e3fa9e918e7d02.png\" alt=\"O (n ^ {3})\" title=\"\"><\/td>\n<td>cubic complexity: nesting of three loops<\/td>\n<\/tr>\n<tr>\n<td><img decoding=\"async\" class=\"mwe-math-fallback-image-inline tex\" src=\"https:\/\/upload.wikimedia.org\/math\/3\/e\/1\/3e1d906f81519ad85be3e8a8e7e9e0ca.png\" alt=\"O (n ^ p)\" title=\"\"><\/td>\n<td>polynomial complexity: nesting of loops without knowledge of states<\/td>\n<\/tr>\n<tr>\n<td><img decoding=\"async\" class=\"mwe-math-fallback-image-inline tex\" src=\"https:\/\/upload.wikimedia.org\/math\/2\/6\/9\/269075e9060240e928791b74b3a3c2e7.png\" alt=\"O (n ^ {\\ log (n)})\" title=\"\"><\/td>\n<td>quasi-polynomial complexity: divide and conquer<\/td>\n<\/tr>\n<tr>\n<td><img decoding=\"async\" class=\"mwe-math-fallback-image-inline tex\" src=\"https:\/\/upload.wikimedia.org\/math\/a\/5\/b\/a5bab29729331b95aeebc96eda2906ad.png\" alt=\"O (2 ^ {n})\" title=\"\"><\/td>\n<td>exponential complexity: tree, brute force<\/td>\n<\/tr>\n<tr>\n<td><img decoding=\"async\" class=\"mwe-math-fallback-image-inline tex\" src=\"https:\/\/upload.wikimedia.org\/math\/1\/d\/f\/1dfc0dc62ab0b72188128f273546f6b4.png\" alt=\"We!)\" title=\"\"><\/td>\n<td>factorial complexity: naive approach to combinatorial enumeration<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n<p><!-- \/wp:table --><\/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>Theories Home page Wiki I. Writing and modeling an algorithm Pseudo-language and flowchart Termination and correction Time complexity Approximation algorithm Analysis: Adversary model Algorithmic \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1062","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1062","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=1062"}],"version-history":[{"count":70,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1062\/revisions"}],"predecessor-version":[{"id":20394,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1062\/revisions\/20394"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=1062"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}