{"id":253,"date":"2022-05-10T11:56:35","date_gmt":"2022-05-10T09:56:35","guid":{"rendered":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/?p=253"},"modified":"2022-05-10T11:56:35","modified_gmt":"2022-05-10T09:56:35","slug":"algorithmes-gloutons","status":"publish","type":"post","link":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/?p=253","title":{"rendered":"Algorithmes gloutons"},"content":{"rendered":"\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"852\" height=\"173\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-4.png\" alt=\"\" class=\"wp-image-254\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-4.png 852w, http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-4-300x61.png 300w, http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/wp-content\/uploads\/sites\/16\/2022\/05\/image-4-768x156.png 768w\" sizes=\"(max-width: 852px) 100vw, 852px\" \/><\/figure>\n\n\n\n<p>Un algorithme est qualifi\u00e9 de\u00a0<strong>glouton<\/strong>\u00a0si le probl\u00e8me qu&rsquo;il essaie de r\u00e9soudre est d\u00e9compos\u00e9 en une succession de probl\u00e8mes identiques pour lesquels l&rsquo;algorithme va chercher une solution optimale.<\/p>\n\n\n\n<p>Un algorithme glouton est donc un algorithme qui suivant le principe de faire, \u00e9tape par \u00e9tape, un choix optimum local, dans l&rsquo;objectif d&rsquo;obtenir un r\u00e9sultat optimum global.<\/p>\n\n\n\n<p>Ces algorithmes sont utilis\u00e9s principalement dans des probl\u00e8mes d&rsquo;optimisation.<\/p>\n\n\n\n<p>Un probl\u00e8me d&rsquo;optimisation consiste \u00e0 d\u00e9terminer les valeurs des param\u00e8tres permettant de :<\/p>\n\n\n\n<ul><li>Minimiser ou maximiser une fonction objectif.<\/li><li>Satisfaire une ou des fonctions contraintes (il existe des probl\u00e8mes avec ou sans contrainte).<\/li><\/ul>\n\n\n\n<p>Ces valeurs correspondent \u00e0 une solution optimale que l&rsquo;on obtient en effectuant une suite de meilleurs choix pour chaque \u00e9tape de l\u2019algorithme (\u00e0 chaque \u00e9tape, on fait le meilleur choix possible).<\/p>\n\n\n\n<p>Dans l&rsquo;algorithme, il n&rsquo;y pas de retour en arri\u00e8re : lorsqu&rsquo;un choix est fait \u00e0 une \u00e9tape, il n\u2019est pas modifi\u00e9 ult\u00e9rieurement et il ne modifie pas les choix pr\u00e9c\u00e9dents.<\/p>\n\n\n\n<p>Une autre caract\u00e9ristique des algorithmes gloutons : la progression descendante. Cette caract\u00e9ristique est traduite par le fait que lorsqu&rsquo;un choix est fait, on tente de r\u00e9soudre un probl\u00e8me plus petit.<\/p>\n\n\n\n<p>Exemple du rendu de monnaie.<\/p>\n\n\n\n<p>Le probl\u00e8me du rendu de monnaie est un probl\u00e8me d\u2019algorithmique qui s\u2019\u00e9nonce de la fa\u00e7on suivante : \u00e9tant donn\u00e9 un syst\u00e8me de monnaie, comment rendre une somme donn\u00e9e de fa\u00e7on optimale, c\u2019est-\u00e0-dire avec le nombre minimal de pi\u00e8ces et billets ?<\/p>\n\n\n\n<p>Dans la zone euro, le syst\u00e8me en vigueur, en mettant de c\u00f4t\u00e9 les centimes d\u2019euros, met \u00e0 disposition des pi\u00e8ces ou billets de : 1\u20ac, 2\u20ac, 5\u20ac, 10\u20ac, 20\u20ac, 50\u20ac, 100\u20ac, 200\u20ac, 500\u20ac.<\/p>\n\n\n\n<p>On suppose que nous avons \u00e0 notre disposition un nombre illimit\u00e9 de ces pi\u00e8ces ou billets.<\/p>\n\n\n\n<p>Voici un exemple de code permettant de r\u00e9soudre ce probl\u00e8me :<\/p>\n\n\n\n<p><a href=\"https:\/\/colab.research.google.com\/drive\/1X1Ed2Y26axXMSA_5TbvkjbmMPDBDUGjj?usp=sharing\">https:\/\/colab.research.google.com\/drive\/1X1Ed2Y26axXMSA_5TbvkjbmMPDBDUGjj?usp=sharing<\/a><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Un algorithme est qualifi\u00e9 de\u00a0glouton\u00a0si le probl\u00e8me qu&rsquo;il essaie de r\u00e9soudre est d\u00e9compos\u00e9 en une succession de probl\u00e8mes identiques pour lesquels l&rsquo;algorithme va chercher une solution optimale. Un algorithme glouton est donc un algorithme qui suivant le principe de faire, \u00e9tape par \u00e9tape, un choix optimum local, dans l&rsquo;objectif d&rsquo;obtenir un r\u00e9sultat optimum global. Ces [&hellip;]<\/p>\n","protected":false},"author":16,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=\/wp\/v2\/posts\/253"}],"collection":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=\/wp\/v2\/users\/16"}],"replies":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=253"}],"version-history":[{"count":1,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=\/wp\/v2\/posts\/253\/revisions"}],"predecessor-version":[{"id":255,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=\/wp\/v2\/posts\/253\/revisions\/255"}],"wp:attachment":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=253"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=253"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/lukas\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=253"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}