{"id":2,"date":"2020-08-10T23:31:57","date_gmt":"2020-08-10T21:31:57","guid":{"rendered":"http:\/\/maths-code.fr\/cours\/?page_id=2"},"modified":"2023-07-26T14:06:56","modified_gmt":"2023-07-26T12:06:56","slug":"algorithmes-gloutons","status":"publish","type":"page","link":"https:\/\/maths-code.fr\/cours\/algorithmes-gloutons\/","title":{"rendered":"Algorithmes gloutons"},"content":{"rendered":"\n<p> En programmation, pour r\u00e9soudre un probl\u00e8me, diverses techniques sont \u00e9videmment possibles.  En premi\u00e8re approche, et consid\u00e9rant la puissance de nos machines qui n&rsquo;a de cesse de cro\u00eetre, il est tentant de calculer toutes les solutions pour choisir la meilleure.   <\/p>\n\n\n<p>Cette technique dite par **force brute**, c\u2019est-\u00e0-dire en testant tous les cas possibles peut-\u00eatre utilis\u00e9e mais ce type de r\u00e9solution peut aussi pr\u00e9senter un probl\u00e8me d\u2019efficacit\u00e9 voire de mise en oeuvre.<\/p>\n<p>La technique glouton (*greedy* en anglais) propose une alternative:<\/p>\n<blockquote class=\"wp-block-quote\">\n<p>Un algorithme glouton est un algorithme qui suit le principe de faire, \u00e9tape par \u00e9tape, un choix optimum local dans l&rsquo;espoir d&rsquo;obtenir un r\u00e9sultat optimum global<\/p>\n<\/blockquote>\n<p>Cette technique s&rsquo;utilise pour r\u00e9soudre des probl\u00e8mes d&rsquo;optimisation comme le rendu de monnaie ou le voyageur de commerce. Certains probl\u00e8mes rencontr\u00e9s dans l\u2019industrie se mod\u00e9lisent sous la forme d\u2019un probl\u00e8me de voyageur de commerce, comme l\u2019optimisation de trajectoires de machines outils : comment percer plusieurs points sur une carte \u00e9lectronique le plus vite possible ?<\/p>\n<hr \/>\n<ul>\n<li>\n<p>Le cours en pdf: <a title=\"Algorithmes gloutons:Cours et Exercices\" href=\"http:\/\/maths-code.fr\/NSI\/1ere\/algorithmes-gloutons\/Cours_algo-glouton.pdf\">Algorithmes gloutons (cours et exercices)<\/a><\/p>\n<\/li>\n<li>\n<p>TP du <strong>voyageur de commerce<\/strong> pr\u00e9sent\u00e9 dans le cours:<br \/>-fichier <a title=\"exemple.txt\" href=\"http:\/\/maths-code.fr\/NSI\/1ere\/algorithmes-gloutons\/voyageur\/exemple.txt\">exemple.txt<\/a> contenant les positions des villes,<br \/>-fichier <a title=\"TSP_biblio.py\" href=\"http:\/\/maths-code.fr\/NSI\/1ere\/algorithmes-gloutons\/voyageur\/TSP_biblio.py\">TSP_biblio.py<\/a> contenant les fonctions utiles pour r\u00e9aliser ce TP.<\/p>\n<\/li>\n<\/ul>\n<hr \/>","protected":false},"excerpt":{"rendered":"<p>En programmation, pour r\u00e9soudre un probl\u00e8me, diverses techniques sont \u00e9videmment possibles. En premi\u00e8re approche, et consid\u00e9rant la puissance de nos machines qui n&rsquo;a de cesse de cro\u00eetre, il est tentant de calculer toutes les solutions pour choisir la meilleure. Cette technique dite par **force brute**, c\u2019est-\u00e0-dire en testant tous les cas possibles peut-\u00eatre utilis\u00e9e mais ce type de r\u00e9solution peut aussi pr\u00e9senter un probl\u00e8me d\u2019efficacit\u00e9 voire de mise en oeuvre. La technique glouton (*greedy* en anglais) propose une alternative: Un algorithme glouton est un algorithme qui suit le principe de faire, \u00e9tape par \u00e9tape, un choix optimum local dans l&rsquo;espoir d&rsquo;obtenir un r\u00e9sultat optimum global Cette technique s&rsquo;utilise pour r\u00e9soudre des probl\u00e8mes d&rsquo;optimisation comme le rendu de monnaie ou le voyageur de commerce. Certains probl\u00e8mes rencontr\u00e9s dans l\u2019industrie se mod\u00e9lisent sous la forme d\u2019un probl\u00e8me de voyageur de commerce, comme l\u2019optimisation de trajectoires de machines outils : comment percer plusieurs points sur une carte \u00e9lectronique le plus vite possible ? Le cours en pdf: Algorithmes gloutons (cours et exercices) TP du voyageur de commerce pr\u00e9sent\u00e9 dans le cours:-fichier exemple.txt contenant les positions des villes,-fichier TSP_biblio.py contenant les fonctions utiles pour r\u00e9aliser ce TP.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"open","template":"","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"class_list":["post-2","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/pages\/2","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/comments?post=2"}],"version-history":[{"count":26,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/pages\/2\/revisions"}],"predecessor-version":[{"id":4359,"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/pages\/2\/revisions\/4359"}],"wp:attachment":[{"href":"https:\/\/maths-code.fr\/cours\/wp-json\/wp\/v2\/media?parent=2"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}