{"id":999,"date":"2022-01-17T17:38:20","date_gmt":"2022-01-17T16:38:20","guid":{"rendered":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/?p=999"},"modified":"2022-01-17T17:47:13","modified_gmt":"2022-01-17T16:47:13","slug":"quelques-algorithmes-simples","status":"publish","type":"post","link":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/2022\/01\/17\/quelques-algorithmes-simples\/","title":{"rendered":"Quelques algorithmes simples"},"content":{"rendered":"\n<p class=\"has-text-color has-background\" style=\"background-color:#ff8935;color:#ffc59c\"><strong>I &#8211; Introduction<\/strong><\/p>\n\n\n\n<p>Introduction \u00e0 l&rsquo;algorithmique : <a href=\"https:\/\/pixees.fr\/informatiquelycee\/n_site\/nsi_prem_intro_algo.html\">https:\/\/pixees.fr\/informatiquelycee\/n_site\/nsi_prem_intro_algo.html<\/a><\/p>\n\n\n\n<p>Qu&rsquo;est-ce qu&rsquo;un algorithme ?<\/p>\n\n\n\n<p>Voici deux d\u00e9finitions trouv\u00e9es dans la litt\u00e9rature :<\/p>\n\n\n\n<ul><li>Proc\u00e9dure de calcul bien d\u00e9finie qui prend en entr\u00e9e une valeur ou un ensemble de valeur, et qui donne en sortie une valeur ou un ensemble de valeur.<\/li><li>Un algorithme est la sp\u00e9cification d&rsquo;un sch\u00e9ma de calcul sous forme d&rsquo;une suite finie d&rsquo;op\u00e9rations \u00e9l\u00e9mentaires ob\u00e9issant \u00e0 un enchainement d\u00e9termin\u00e9.<\/li><\/ul>\n\n\n\n<p> <\/p>\n\n\n\n<p class=\"has-text-color has-background\" style=\"background-color:#ff8630;color:#ffc59b\"><strong>II &#8211; Tri par insertion, par s\u00e9lection<\/strong><\/p>\n\n\n\n<p>Les algorithmes de tri des \u00e9l\u00e9ments d&rsquo;un tableau ont une place \u00e0 part en algorithmique. En effet, ils sont souvent utilis\u00e9s pour mettre en \u00e9vidence certains concepts algorithmiques (concepts que l&rsquo;on retrouve dans d&rsquo;autres types d&rsquo;algorithmes).<\/p>\n\n\n\n<p class=\"has-text-color has-background\" style=\"background-color:#ffc8a1;color:#ff7817\">II &#8211; A Tri par insertion : tri par s\u00e9lection<\/p>\n\n\n\n<p>Voici l&rsquo;algorithme du tri par s\u00e9lection :<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\" data-enlighter-theme=\"godzilla\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">VARIABLE\nt : tableau d'entiers\ni : nombre entier\nj : nombre entier\nk : nombre entier\nDEBUT\nj\u21902\ntant que j&lt;=longueur(t):   \/\/boucle 1\n  i\u2190j-1\n  k\u2190t[j]\n  tant que i&gt;0 et que t[i]&gt;k:   \/\/boucle 2\n    t[i+1]\u2190t[i]\n    i\u2190i-1\n  fin tant que\n  t[i+1]\u2190k\n  j\u2190j+1\nfin tant que\nFIN\n\t<\/pre>\n\n\n\n<p><strong>Remarque<\/strong> : il est possible de mettre des commentaires \u00e0 l&rsquo;aide de \u00ab\u00a0\/\/\u00a0\u00bb afin de rendre la compr\u00e9hension des algorithmes plus ais\u00e9e<\/p>\n\n\n\n<p>Poursuivez le travail commenc\u00e9 ci-dessous (attention de bien donner l&rsquo;\u00e9tat du tableau \u00e0 chaque \u00e9tape) :<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"380\" height=\"752\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/nsi_prem_algo_tri_1.png\" alt=\"\" class=\"wp-image-1012\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/nsi_prem_algo_tri_1.png 380w, http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/nsi_prem_algo_tri_1-152x300.png 152w\" sizes=\"(max-width: 380px) 100vw, 380px\" \/><\/figure>\n\n\n\n<p class=\"has-text-color has-background\" style=\"background-color:#ffc9a2;color:#ff7919\">II &#8211; B Tri par s\u00e9lection<\/p>\n\n\n\n<p>Voici l&rsquo;algorithme du tri par s\u00e9lection :<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\" data-enlighter-theme=\"godzilla\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">VARIABLE\nt : tableau d'entiers\ni : nombre entier\nmin : nombre entier\nj : nombre entier\nDEBUT\ni\u21901\ntant que i&lt;longueur(t):   \/\/boucle 1\n  j\u2190i+1\n  min\u2190i\n  tant que j&lt;=longueur(t):   \/\/boucle 2\n    si t[j]&lt;t[min]:\n      min\u2190j\n    fin si\n    j\u2190j+1\n  fin tant que\n  si min\u2260i :\n    \u00e9changer t[i] et t[min]\n  fin si\n  i\u2190i+1\nfin tant que\nFIN\n<\/pre>\n\n\n\n<p>Poursuivez le travail commenc\u00e9 ci-dessous (attention de bien donner l&rsquo;\u00e9tat du tableau) :<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"664\" height=\"798\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/nsi_prem_algo_tri_5.png\" alt=\"\" class=\"wp-image-1017\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/nsi_prem_algo_tri_5.png 664w, http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/nsi_prem_algo_tri_5-250x300.png 250w\" sizes=\"(max-width: 664px) 100vw, 664px\" \/><\/figure>\n\n\n\n<p>On peut r\u00e9sumer le principe de fonctionnement de l&rsquo;algorithme de tri par s\u00e9lection avec le sch\u00e9ma suivant :<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"502\" height=\"509\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/nsi_prem_algo_tri_6.png\" alt=\"\" class=\"wp-image-1019\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/nsi_prem_algo_tri_6.png 502w, http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/nsi_prem_algo_tri_6-296x300.png 296w\" sizes=\"(max-width: 502px) 100vw, 502px\" \/><\/figure>\n\n\n\n<p class=\"has-text-color has-background\" style=\"background-color:#ff8630;color:#ffc398\"><strong>III &#8211; Exercices<\/strong><\/p>\n\n\n\n<p>Pour chacune des questions qui suivent, \u00e9crire un algorithme permettant de r\u00e9soudre le probl\u00e8me puis le coder en python.<\/p>\n\n\n\n<p> Lien des tests : <\/p>\n\n\n\n<p class=\"has-text-color has-background\" style=\"background-color:#ffc9a2;color:#ff7b1d\">III &#8211; A trouver l\u2019indice d\u2019une valeur donn\u00e9e dans un tableau<\/p>\n\n\n\n<p>La m\u00e9thode index permet de renvoyer l\u2019indice de l\u2019\u00e9l\u00e9ment dans la liste s\u2019il a \u00e9t\u00e9 trouv\u00e9.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"608\" height=\"749\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/image-18.png\" alt=\"\" class=\"wp-image-1031\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/image-18.png 608w, http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/image-18-244x300.png 244w\" sizes=\"(max-width: 608px) 100vw, 608px\" \/><figcaption>Corrig\u00e9<\/figcaption><\/figure>\n\n\n\n<p class=\"has-text-color has-background\" style=\"background-color:#ffc9a2;color:#ff7f23\">III &#8211; B \u00c9crire une fonction qui retourne le minimum d\u2019un tableau<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"126\" height=\"174\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/image-19.png\" alt=\"\" class=\"wp-image-1034\" \/><figcaption>Corrig\u00e9<\/figcaption><\/figure>\n\n\n\n<p class=\"has-text-color has-background\" style=\"background-color:#ffcaa4;color:#ff8126\">III &#8211; C \u00c9crire une fonction qui retourne le maximum d\u2019un tableau<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"288\" height=\"425\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/image-20.png\" alt=\"\" class=\"wp-image-1037\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/image-20.png 288w, http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/image-20-203x300.png 203w\" sizes=\"(max-width: 288px) 100vw, 288px\" \/><figcaption>Corrig\u00e9<\/figcaption><\/figure>\n\n\n\n<p class=\"has-text-color has-background\" style=\"background-color:#ffc7a0;color:#ff7919\">III &#8211; D \u00c9crire une fonction qui renvoi le min et le max d\u2019un tableau<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"282\" height=\"432\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/image-21.png\" alt=\"\" class=\"wp-image-1038\" srcset=\"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/image-21.png 282w, http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/image-21-196x300.png 196w\" sizes=\"(max-width: 282px) 100vw, 282px\" \/><figcaption>Corrig\u00e9<\/figcaption><\/figure>\n\n\n\n<p class=\"has-text-color has-background\" style=\"background-color:#ffc59b;color:#ff7919\">III &#8211; E \u00c9crire une fonction qui \u00e9change 2 valeurs d\u2019un tableau<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" width=\"160\" height=\"187\" src=\"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-content\/uploads\/sites\/4\/2022\/01\/image-22.png\" alt=\"\" class=\"wp-image-1040\" \/><figcaption>Corrig\u00e9<\/figcaption><\/figure>\n\n\n\n<p class=\"has-text-color has-background\" style=\"background-color:#ff7c1f;color:#ffc297\">IV &#8211; Efficacit\u00e9 des tris<\/p>\n\n\n\n<p>Pour comprendre le tri par insertion : <a href=\"http:\/\/lwh.free.fr\/pages\/algo\/tri\/tri_insertion.html\">http:\/\/lwh.free.fr\/pages\/algo\/tri\/tri_insertion.html<\/a><\/p>\n\n\n\n<p>Pour comprendre le tri par s\u00e9lection : <a href=\"http:\/\/lwh.free.fr\/pages\/algo\/tri\/tri_selection.html\">http:\/\/lwh.free.fr\/pages\/algo\/tri\/tri_selection.html<\/a><\/p>\n\n\n\n<p>Pour apprendre \u00e0 ex\u00e9cuter un script \u00ab\u00a0\u00e0 la main \u00a0\u00bb pour mieux le comprendre vous pouvez vous aider de python tutor.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I &#8211; Introduction Introduction \u00e0 l&rsquo;algorithmique : https:\/\/pixees.fr\/informatiquelycee\/n_site\/nsi_prem_intro_algo.html Qu&rsquo;est-ce qu&rsquo;un algorithme ? Voici deux d\u00e9finitions trouv\u00e9es dans la litt\u00e9rature : Proc\u00e9dure de calcul bien d\u00e9finie qui prend en entr\u00e9e une valeur ou un ensemble de valeur, et qui donne en sortie une valeur ou un ensemble de valeur. Un algorithme est la sp\u00e9cification d&rsquo;un sch\u00e9ma [&hellip;]<\/p>\n","protected":false},"author":4,"featured_media":1045,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/posts\/999"}],"collection":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/comments?post=999"}],"version-history":[{"count":38,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/posts\/999\/revisions"}],"predecessor-version":[{"id":1049,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/posts\/999\/revisions\/1049"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/media\/1045"}],"wp:attachment":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/media?parent=999"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/categories?post=999"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/raphaelle\/wp-json\/wp\/v2\/tags?post=999"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}