cours_04_C.ipynb

{"cells":[{"metadata":{"hide_input":true,"hide_output":true,"init_cell":true,"run_control":{"marked":false},"trusted":true},"cell_type":"code","source":"# Permet de tout executer au lancement du notebook + conserver le notebook actif pendant 2h\nfrom IPython.display import Javascript\nfrom masquer import *\nJavascript(\"\"\"\nfunction repeter(){\nIPython.notebook.kernel.execute(\"a=1\");\n}\n// execute a = 1 en python toutes les 8 minutes pendant 2h\nlet timerId = setInterval(() => repeter(), 4800);\nsetTimeout(() => { clearInterval(timerId); alert('fin de cession'); }, 7200000);\n\n// Supprimer la taille limite pour la sortie d'une cellule\nIPython.OutputArea.prototype._should_scroll = function(lines) {\n    return false;\n};\nIPython.notebook.kernel.execute(\"url = '\" + window.location + \"'\");\n\n// Exécuter toutes les cellule du notebook\n    require(\n        ['base/js/namespace', 'jquery'], \n        function(jupyter, $) {\n            \n                \n                jupyter.actions.call('jupyter-notebook:run-all-cells-below');\n                jupyter.actions.call('jupyter-notebook:save-notebook');\n                Jupyter.actions.call('jupyter-notebook:hide-header')\n\n        }\n    );\"\"\")","execution_count":2,"outputs":[{"output_type":"execute_result","execution_count":2,"data":{"text/plain":"<IPython.core.display.Javascript object>","application/javascript":"\nfunction repeter(){\nIPython.notebook.kernel.execute(\"a=1\");\n}\n// execute a = 1 en python toutes les 8 minutes pendant 2h\nlet timerId = setInterval(() => repeter(), 4800);\nsetTimeout(() => { clearInterval(timerId); alert('fin de cession'); }, 7200000);\n\n// Supprimer la taille limite pour la sortie d'une cellule\nIPython.OutputArea.prototype._should_scroll = function(lines) {\n    return false;\n};\nIPython.notebook.kernel.execute(\"url = '\" + window.location + \"'\");\n\n// Exécuter toutes les cellule du notebook\n    require(\n        ['base/js/namespace', 'jquery'], \n        function(jupyter, $) {\n            \n                \n                jupyter.actions.call('jupyter-notebook:run-all-cells-below');\n                jupyter.actions.call('jupyter-notebook:save-notebook');\n                Jupyter.actions.call('jupyter-notebook:hide-header')\n\n        }\n    );"},"metadata":{}}]},{"metadata":{"slideshow":{"slide_type":"slide"}},"cell_type":"markdown","source":"# <span style=\"color:red;\"><center>Chapitre 4 : Algorithmique</center></span>"},{"metadata":{"slideshow":{"slide_type":"-"}},"cell_type":"markdown","source":"## C. Algorithmes de tri"},{"metadata":{"slideshow":{"slide_type":"slide"}},"cell_type":"markdown","source":"Comme nous l'avons vu précédemment, la recherche dichotomique est beaucoup plus rapide qu'une recherche séquentielle. Mais pour cela, le tableau doit être trié au préalable. Ainsi, **dès que l'on souhaite faire plusieurs recherches dans un tableau, il est très fortement conseillé de commencer par trier le tableau**, même si cela peut prendre du temps.\n\nNous allons voir ici deux algorithmes de tri qui ne sont pas parmi les plus efficaces mais qui sont les plus naturels : le tri par sélection et le tri par insertion.\n\nMais il en existe [beaucoup](https://youtu.be/kPRA0W1kECg) d'autres  :\n- Le tri à bulle,\n- Le tri à peigne,\n- Le tri Shaker,\n- Le tri Shell,\n- Le tri Gnome,\n- Le tri par tas,\n- Le tri fusion,\n- Le tri rapide,\n- ..."},{"metadata":{"slideshow":{"slide_type":"slide"}},"cell_type":"markdown","source":"### I. Le tri par sélection (*selection sort*)\n\n#### 1. Principe (enfantin)\n\n**On cherche la plus petite valeur du tableau et on la place en première position. On cherche à nouveau la plus petite valeur parmi les $n-1$ valeurs restantes et on la place en deuxième position. Et ainsi de suite jusqu'à la fin du tableau.**\n\nC'est le tri privilégié par les petits enfants lorsqu'ils jouent aux cartes : on cherche la plus petite carte de sa main et on la pose sur la table. Puis on recommence avec celles qu'il nous reste en posant la carte par dessus la première. Et ainsi de suite jusqu'à ce qu'on ait plus de carte en main. Le **nom** de tri par sélection vient de cette **nécessité à chaque étape de sélectionner la plus petite carte**.\n\n[Voici](https://youtu.be/92BfuxHn2XE) son fonctionnement illustré en image et en son.\n\n"},{"metadata":{},"cell_type":"markdown","source":"**Remarques** :\n- Cet algorithme utilise une **recherche de minimum** dont on a déjà vu l'implémentation dans la partie B de ce chapitre.\n- En pratique, au lieu de simplement insérer le plus petit élément au début du tableau, comme on le ferait avec des cartes à jouer, on procède à une permutation entre cet élément et le premier. En effet, l'insérer nécessiterait de réaffecter toutes les valeurs situées entre le premier élément et le minimum trouvé afin de les décaler d'un cran vers la droite. Ce qui prendrait du temps de calcul pour rien. Avec des cartes, le problème ne se pose pas."},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"#### 2. Pseudo-code\n\n**Fonction** tri_selection (tab)\n> *tab est un tableau de n valeurs numériques qui est trié en place (tab est modifié mais la fonction ne retourne rien).*  \n>\n> *float* : mini  *# La valeur minimale trouvée*  \n> *int* : i_mini *# L'indice de la valeur minimale trouvée*  \n> n $\\leftarrow$ taille(tab)  \n> *# i correspond au premier indice du tableau restant à trier, quand i=n-2 le tableau à trier correspond aux 2 derniers éléments de tab*  \n> **Pour** i allant de 0 à n-2 **faire**   \n>> i_mini $\\leftarrow$ i  *# On initialise avec le premier indice du tableau à trier.*  \n>> mini $\\leftarrow$ tab[i]  *# On initialise avec la première valeur du tableau à trier.*  \n>> **Pour** j allant de i+1 à n-1 **faire**  *# On parcourt le reste du tableau à trier.*\n>>> **Si** tab[j] < mini **alors**  *# Si on trouve une valeur plus petite on met à jour i_mini et mini.*  \n>>>> i_mini $\\leftarrow$ j  \n>>>> mini $\\leftarrow$ tab[j]  \n>>\n>> **Permuter** tab[i] et tab[i_mini]  *# On permute la première valeur du tableau non-trié avec le minimum trouvé*"},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"**Remarques :**\n- En Python la **permutation de 2 éléments d'une liste** s'écrit : `tab[i], tab[j] = tab[j], tab [i]`.\n- On pourrait aussi utiliser une fonction `mini(tab)` qui renvoie l'indice du mininum de `tab`.\n- Cette version effectue un **tri en place du tableau** ce qui a l'avantage de ne **pas consommer de mémoire supplémentaire** mais l'inconvénient de ne pas garder de trace du tableau non-trié initial. Si on ne **veut pas modifier le tableau passé en paramètre**, il faut **créer une copie** du tableau au début (avec `tab_copie=liste(tab)` en Python) et retourner cette copie triée à la fin (`Return tab_copie`).\n- Une **fonction** comme celle-ci **qui ne renvoie rien est souvent appelée procédure**.\n- On effectuera ici le **tri par ordre croissant** mais il suffit de **chercher un maximum** au lieu d'un minimum **pour trier en sens inverse**."},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"#### 3. Terminaison\n\nCet algorithme ne comporte que des boucles `Pour`, il se termine donc forcément."},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"#### 4. Correction\n\n**L'invariant de boucle** est : \"A la fin de l'itération $i$, le début du tableau $tab[0:i+1]$ est trié et ne contient que des valeurs inférieures ou égales à celles du reste du tableau $tab[i+1:n]$\".\n\nEn montrant que cet invariant est vrai pour $i=0$, puis, que si il est vrai pour $i=k$ alors il est encore vrai pour $i=k+1$, on démontre qu'il est vrai à la fin de la boucle pour $i=n-2$.\n\nOn en déduit que $tab[0:n-2+1]=tab[0:n-1]$ est trié et ne contient que des valeurs inférieures ou égales à $tab[n-1:n]=tab[n-1]$. Autrement dit, les $n-1$ premières valeurs sont triées et la dernière valeur est supérieure ou égale à toutes les autres. Donc le tableau est trié et l'algorithme est correct."},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"#### 5. Complexité\n\nOn a **deux boucles `Pour` imbriquées** où $i$ varie de $0$ à $n-2$ et $j$ varie de $i+1$ à $n-1$.\n\nDonc :\n- quand $i=0$, $j$ varie de $1$ à $n-1$, soit $n-1$ itérations.\n- quand $i=1$, $j$ varie de $2$ à $n-1$, soit $n-2$ itérations.\n- ...\n- quand $i=n-2$, $j$ varie de $n-1$ à $n-1$, soit $1$ itération.\n\nAu total, il y a $1+2+3+ ... +(n-2)+(n-1)$ itérations, ce qui est égal à $\\frac{n(n-1)}{2} = \\frac{n^2}{2} - \\frac{n}{2}$ d'où une complexité quadratique (en $O(n^2)$) car quand $n$ est grand, $n$ est négligeable devant $n^2$."},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"Ce n'est donc **pas un algorithme très efficace**. Il a cependant l'avantage (et l'inconvénient) d'effectuer le même nombre d'itérations quelle que soit l'état du tableau initial, qu'il soit déjà presque trié ou pas. Il n'a pas de pire ou de meilleur cas.\n\n**Remarque** : Soit $S = 1+2+3+ ... +(n-2)+(n-1)$ alors on peut aussi écrire $S=(n-1)+(n-2)+(n-3)+ ... +2+1$. Et en ajoutant ces deux écritures terme à terme, on obtient $ S+S=n+n+n+...+n+n$ soit $2S=n(n-1)$ puisque $S$ contient $n-1$ termes. On retrouve bien que $S=\\frac{n(n-1)}{2}$.\n"},{"metadata":{"slideshow":{"slide_type":"slide"}},"cell_type":"markdown","source":"### II. Le tri par insertion (*insertion sort*)\n\n#### 1. Principe\n\n**On commence par la deuxième valeur du tableau et on la place par rapport à la première (comparaison). Puis on continue avec la troisième qu'on insert au bon endroit parmi les deux premières (toujours par comparaison). Et ainsi de suite jusqu'à la fin du tableau.**\n\nC'est en général la méthode de tri adoptée aux cartes par les adultes. Cet algorithme est un peu plus efficace que le tri par sélection car sa complexité est la même seulement dans le pire des cas (tableau initial par ordre décroissant). Dans le meilleur des cas, pour un tableau déjà presque trié, le tri par insertion est plus rapide.\n\n[Voici](https://youtu.be/8oJS1BMKE64) son fonctionnement illustré en image et en son.\n\n"},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"**Remarques** :\n\nEn pratique, on peut :\n- soit **insérer la valeur à trier à sa place dans le début du tableau**, en décalant d'un cran vers la droite toutes les valeurs déjà triées qui lui sont supérieures (comme avec une carte),\n- soit faire des **permutations successives entre cette valeur et sa valeur de gauche**, tant que celle-ci lui est supérieure.\n\nLa deuxième méthode est un peu plus lente."},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"#### 2. Pseudo-code\n\n**Fonction** tri_insertion (tab)\n> *tab est un tableau de n valeurs numériques qui est trié en place (tab est modifié mais la fonction ne retourne rien).*  \n>\n> n $\\leftarrow$ taille(tab)  \n> *# i correspond au dernier indice du tableau déjà trié, quand i=n-2 il ne reste plus qu'à insérer au bon endroit le dernier élément du tableau, c'est donc bien la dernière itération.*  \n> **Pour** i allant de 0 à n-2 **faire**   \n>> j $\\leftarrow$ i+1  *# j est l'indice de la valeur à insérer dans le tableau déjà trié.*  \n>> **Tant que** j >0 **et** tab[j]<tab[j-1] **faire**  *# L'indice j de la valeur à insérer est décrémentée tant qu'on est pas au début du tableau et qu'on a pas trouvé une valeur supérieure à sa gauche.*\n>>> **Permuter** tab[j] et tab[j-1]  *# On permute la valeur à insérer avec celle qui est à sa gauche.*  \n>>> j $\\leftarrow$ j-1  *# On décrémente j puisque la valeur à insérer est décalée d'un cran vers la gauche.*"},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"**Remarques :**\n- On peut aussi, de façon équivalente, faire varier $i$ entre $1$ et $n-1$ puis affecter $i$ (au lieu de $i+1$) à $j$.\n- Comme précédemment, cette version effectue un **tri en place du tableau** et si on ne **veut pas modifier le tableau passé en paramètre**, il faut **créer une copie** du tableau au début puis retourner cette copie triée à la fin.\n- Pour effectuer le **tri par ordre décroissant**  il suffit de remplacer $<$ par $>$ dans la condition de sortie du `Tant que`."},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"#### 3. Terminaison\n\nLa première **boucle `Pour` se termine forcément**.\n\nLe **variant de boucle $j$** de la boucle `Tant que` est un entier partant de $i+1$ et décrémenté par pas de $1$. Ses valeurs forment donc une **suite strictement décroissante** qui atteindra $0$ au bout de $i+1$ itérations. **Dans le pire des cas**, la boucle `Tant que` est donc **exécutée $i+1$ fois** et, quelque soit la valeur de $i$, la boucle se termine.\n\nPuisque les **deux boucles se terminent**, **l'algorithme se termine aussi**."},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"#### 4. Correction\n\n**L'invariant de boucle** est : \"A la fin de l'itération $i$, le début du tableau $tab[0:i+2]$ est trié\".\n\nEn montrant que cet invariant est vrai pour $i=0$, puis, que si il est vrai pour $i=k$ alors il est encore vrai pour $i=k+1$, on démontre qu'il est vrai à la fin de la boucle pour $i=n-2$.\n\nOn en déduit que, à la fin, $tab[0:n-2+2]=tab[0:n]$ est trié et donc que l'algorithme est correct."},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"#### 5. Complexité\n\nDans le **meilleur des cas**, le **tableau est déjà trié**. Dans ce cas, on ne rentre jamais dans la boucle `Tant que` car $tab[j]\\geq tab[j-1]$. On effectue donc seulement les $n-1$ itérations de la boucle `Pour` et la **complexité est linéaire** ($O(n)$).\n\n\n\n"},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"Dans le **pire des cas**, le tableau est **trié par ordre décroissant** et à chaque itération de la boucle `Pour` on effectue $i+1$ itérations de la boucle `Tant que` pour diminuer $j$ de $i+1$ à $0$.\n\nDonc :\n- quand $i=0$, la boucle `Tant que` effectue $1$ itération.\n- quand $i=1$, la boucle `Tant que` effectue $2$ itérations.\n- ...\n- quand $i=n-2$, la boucle `Tant que` effectue $n-1$ itérations.\n\nAu total, il y a donc $1+2+3+ ... +(n-2)+(n-1)=n(n-1)/2$ itérations, **exactement comme pour le tri par sélection** et la **complexité** est donc aussi **quadratique** (en $O(n^2)$)."},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"**En moyenne**, on peut montrer que la **complexité du tri par insertion reste quadratique** et n'est donc pas tellement plus efficace que le tri par sélection. Mais **pour des listes déjà presque triées**, sa **complexité est presque linéaire** et donc bien meilleure que le tri par sélection qui reste tout le temps quadratique.\n\nLes **meilleurs algorithmes de tri** comme le **tri rapide** (quicksort) ont en moyenne une **complexité log-linéaire** ($O(nlog(n))$). Pour arriver à ce résultat, le **tri rapide** divise le tableau initial en **sous-tableaux** plus petits (principe du diviser pour mieux régner) dont les valeurs appartiennent à des intervalles croissants. Et lorsque ces **sous-tableaux sont assez petits**, il les **tri par insertion**."},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"Pour terminer, passons à la pratique avec le [TD](TD_04_1.ipynb) suivant ..."}],"metadata":{"celltoolbar":"none","kernelspec":{"name":"python3","display_name":"Python 3","language":"python"},"language_info":{"name":"python","version":"3.7.10","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"}},"nbformat":4,"nbformat_minor":4}