{"id":279,"date":"2022-05-12T02:47:48","date_gmt":"2022-05-12T00:47:48","guid":{"rendered":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/?p=279"},"modified":"2022-05-12T02:47:48","modified_gmt":"2022-05-12T00:47:48","slug":"algorithmes-gloutons","status":"publish","type":"post","link":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/2022\/05\/12\/algorithmes-gloutons\/","title":{"rendered":"Algorithmes Gloutons"},"content":{"rendered":"\n<p class=\"has-light-green-cyan-background-color has-background\">Un algorithme glouton est utilis\u00e9 dans un probl\u00e8me d&rsquo;optimisation, on l&rsquo;utilise pour effectuer chaque \u00e9tape du programme donn\u00e9 et ainsi choisir la meilleure option disponible pour ex\u00e9cuter l&rsquo;\u00e9tape d&rsquo;un programme.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"719\" height=\"148\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-content\/uploads\/sites\/15\/2022\/05\/image-8.png\" alt=\"\" class=\"wp-image-285\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-content\/uploads\/sites\/15\/2022\/05\/image-8.png 719w, http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-content\/uploads\/sites\/15\/2022\/05\/image-8-300x62.png 300w\" sizes=\"(max-width: 719px) 100vw, 719px\" \/><\/figure>\n\n\n\n<p>Apr\u00e8s l&rsquo;avoir cit\u00e9 ci-dessus, nous savons que les algorithmes gloutons sont utilis\u00e9 pour des probl\u00e8mes d&rsquo;optimisation. Sachant qu&rsquo;un probl\u00e8me d\u2019optimisation consiste \u00e0 d\u00e9terminer les valeurs des param\u00e8tres permettant de :<\/p>\n\n\n\n<ul class=\"has-vivid-red-color has-text-color\"><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 class=\"has-light-green-cyan-background-color has-background\">A noter qu&rsquo;un algorithme glouton ne fait point machine arri\u00e8re, une fois que la meilleure option pour une \u00e9tape est appliqu\u00e9e alors cette derni\u00e8re ne peut \u00eatre chang\u00e9e. Les algorithmes gloutons ont une autre option, lorsqu\u2019un choix est fait, on tente de r\u00e9soudre un probl\u00e8me plus petit. On appelle cela la progression descendante.<\/p>\n\n\n\n<p>Nous allons \u00e9tudier cela en prenant un exemple pr\u00e9cis qui est le suivant : On a une somme de 423 \u20ac et on souhaite donner le moins de billet possible. 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<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">system_euro=[500,200,100,50,20,10,5,2,1]\n\ndef rendu_monnaie(somme,systeme):\n    liste_pieces=[]\n    for valeur in systeme:\n        while somme&gt;=valeur:\n            liste_pieces.append(valeur)\n            somme=somme-valeur\n    return liste_pieces<\/pre>\n\n\n\n<p class=\"has-light-green-cyan-background-color has-background\">Nous d\u00e9finissons la somme qui est de 423 \u20ac mais aussi on cr\u00e9e une liste qu&rsquo;on nomme \u00ab\u00a0liste_pieces\u00a0\u00bb o\u00f9 chaque valeur trouv\u00e9e sera plac\u00e9es dans cette derni\u00e8re. Nous allons trouv\u00e9 ses valeurs gr\u00e2ce \u00e0 une boucle qu&rsquo;on va \u00e9tablir \u00ab\u00a0for valeur in syst\u00e8me\u00a0\u00bb o\u00f9 syst\u00e8me = system euro. Nous disons tant que la somme est  strictement sup\u00e9rieur aux valeurs alors nous les ajoutons dans la liste\u00a0\u00bbliste_pieces\u00a0\u00bb et nous retirons \u00e0 la somme la valeur prise derni\u00e8rement. <\/p>\n\n\n\n<p class=\"has-vivid-red-color has-text-color\">Vous pourrez retrouver sur le lien ci-dessous une application num\u00e9rique o\u00f9 le code sera ex\u00e9cutable :<\/p>\n\n\n\n<p><a href=\"https:\/\/pythontutor.com\/visualize.html#code=system_euro%3D%5B500,200,100,50,20,10,5,2,1%5D%0Adef%20rendu_monnaie%28somme,systeme%29%3A%0A%20%20%20%20liste_pieces%3D%5B%5D%0A%20%20%20%20for%20valeur%20in%20systeme%3A%0A%20%20%20%20%20%20%20%20while%20somme%3E%3Dvaleur%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20liste_pieces.append%28valeur%29%0A%20%20%20%20%20%20%20%20%20%20%20%20somme%3Dsomme-valeur%0A%20%20%20%20return%20liste_pieces%0A%0Arendu_monnaie%28423,system_euro%29&amp;cumulative=false&amp;curInstr=0&amp;heapPrimitives=nevernest&amp;mode=display&amp;origin=opt-frontend.js&amp;py=3&amp;rawInputLstJSON=%5B%5D&amp;textReferences=false\">https:\/\/pythontutor.com\/visualize.html#code=system_euro%3D%5B500,200,100,50,20,10,5,2,1%5D%0Adef%20rendu_monnaie%28somme,systeme%29%3A%0A%20%20%20%20liste_pieces%3D%5B%5D%0A%20%20%20%20for%20valeur%20in%20systeme%3A%0A%20%20%20%20%20%20%20%20while%20somme%3E%3Dvaleur%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20liste_pieces.append%28valeur%29%0A%20%20%20%20%20%20%20%20%20%20%20%20somme%3Dsomme-valeur%0A%20%20%20%20return%20liste_pieces%0A%0Arendu_monnaie%28423,system_euro%29&amp;cumulative=false&amp;curInstr=0&amp;heapPrimitives=nevernest&amp;mode=display&amp;origin=opt-frontend.js&amp;py=3&amp;rawInputLstJSON=%5B%5D&amp;textReferences=false<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Un algorithme glouton est utilis\u00e9 dans un probl\u00e8me d&rsquo;optimisation, on l&rsquo;utilise pour effectuer chaque \u00e9tape du programme donn\u00e9 et ainsi choisir la meilleure option disponible pour ex\u00e9cuter l&rsquo;\u00e9tape d&rsquo;un programme. Apr\u00e8s l&rsquo;avoir cit\u00e9 ci-dessus, nous savons que les algorithmes gloutons sont utilis\u00e9 pour des probl\u00e8mes d&rsquo;optimisation. Sachant qu&rsquo;un probl\u00e8me d\u2019optimisation consiste \u00e0 d\u00e9terminer les valeurs [&hellip;]<\/p>\n","protected":false},"author":13,"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\/maxence\/wp-json\/wp\/v2\/posts\/279"}],"collection":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-json\/wp\/v2\/users\/13"}],"replies":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-json\/wp\/v2\/comments?post=279"}],"version-history":[{"count":2,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-json\/wp\/v2\/posts\/279\/revisions"}],"predecessor-version":[{"id":286,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-json\/wp\/v2\/posts\/279\/revisions\/286"}],"wp:attachment":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-json\/wp\/v2\/media?parent=279"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-json\/wp\/v2\/categories?post=279"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/maxence\/wp-json\/wp\/v2\/tags?post=279"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}