TD_04_1.ipynb

{"cells":[{"metadata":{"init_cell":true,"run_control":{"marked":false},"hide_output":true,"hide_input":true,"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> TD - Tri par sélection et par insertion</span>"},{"metadata":{"slideshow":{"slide_type":"slide"}},"cell_type":"markdown","source":"## 1. Implémentation des tris"},{"metadata":{},"cell_type":"markdown","source":"### 1.1 Tri par sélection\n\n**Fonction** tri_selection_en_place (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":"-"}},"cell_type":"markdown","source":"**Q1. A partir du pseudo-code ci-dessus, implémenter l'algorithme de tri par sélection en Python.**"},{"metadata":{"trusted":true},"cell_type":"code","source":"#Question 1\ndef tri_selection_en_place(tab):\n    \"\"\"tab est un tableau de n valeurs numériques qui est trié en place par sélection (tab est modifié mais la fonction ne retourne rien).\"\"\"","execution_count":42,"outputs":[]},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"### 1.2 Tri par insertion\n\n**Fonction** tri_insertion_en_place (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":"-"}},"cell_type":"markdown","source":"**Q2. A partir du pseudo-code ci-dessus, implémenter l'algorithme de tri par insertion en Python.**"},{"metadata":{"trusted":true},"cell_type":"code","source":"# Question 2\ndef tri_insertion_en_place(tab):\n    \"\"\"tab est un tableau de n valeurs numériques qui est trié en place par insertion (tab est modifié mais la fonction ne retourne rien).\"\"\"","execution_count":43,"outputs":[]},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"### 1.3 Test des tris\n\n**Utiliser le code ci-dessous pour tester vos algorithmes de tri sur une liste d'entiers aléatoires.** On pourra faire varier la taille $N$ de la liste et les bornes inférieures et supérieures `valMin` et `valMax` des valeurs aléatoires et on utlisera **les 2 fonctions de tri** précédentes. Dans tous les cas, **on vérifiera juste que les liste affichées après le tri sont bien triées par ordre croissant**."},{"metadata":{"trusted":true},"cell_type":"code","source":"from random import randint\n#Création d'une Liste de N entiers aléatoires tirés entre valMin et valMax\nN=10\nvalMin=0\nvalMax=10\n\nL = [randint(valMin,valMax) for i in range(N)]\n#Affichage de la liste aléatoire et du résultat du tri par sélection\nprint('Liste de départ :',L)\ntri_selection_en_place(L)\nprint('Liste triée :',L)\n\nL = [randint(valMin,valMax) for i in range(N)]\n#Affichage de la liste aléatoire et du résultat du tri par insertion\nprint('Liste de départ :',L)\ntri_insertion_en_place(L)\nprint('Liste triée :',L)","execution_count":44,"outputs":[{"output_type":"stream","text":"Liste de départ : [3, 2, 8, 0, 4, 6, 0, 6, 8, 5]\nListe triée : [0, 0, 2, 3, 4, 5, 6, 6, 8, 8]\nListe de départ : [4, 8, 6, 0, 3, 10, 8, 5, 5, 10]\nListe triée : [0, 3, 4, 5, 5, 6, 8, 8, 10, 10]\n","name":"stdout"}]},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"Pour le moment, le tri se fait **en place**, ce qui complique un peu les tests de comparaison entre nos deux algorithmes. En effet, si je lance les deux tris à la suite sur la même liste, le deuxième tri s'effectuera sur une liste déjà triée puisque la liste de départ est modifiée. Je ne peux donc **pas comparer les deux algorithmes** sur la même liste aléatoire de départ. C'est pour cela que dans le code précédent, il faut générer deux fois la liste aléatoire de départ.\n\nPour que le tri ne se face pas en place, il faut créer une copy du tableau donné en argument avec l'instruction `tabCopy=list(tab)` par exemple. Puis on trie `tabCopy` et on le retourne comme résultat une fois entièrement trié.\n\nDe plus, afin de vérifier que le tri par insertion a une complexité moindre (plus efficace) que le tri par sélection, on peut dans un premier temps ajouter dans leurs algorithme un *compteur d'itérations* que l'on incrémente de 1, à chaque fois que l'on passe dans la deuxième boucle.\n\n**Q3. A partir des deux premières fonctions, écrire les fonctions `tri_selection(tab)` et `tri_insertion(tab)` afin qu'elles retournent un résultat de la forme `[liste triée, nbIter]` et sans modifier la liste passée en argument (pas de tri en place).**"},{"metadata":{"trusted":true},"cell_type":"code","source":"# Question 3\ndef tri_selection(tab):\n    \"\"\"tab est un tableau de n valeurs numériques. On crée une copie tabCopy de tab, on la trie par sélection et on renvoie [tabCopy, compt] où compt est le nombre total d'itérations .\"\"\"\n\ndef tri_insertion(tab):\n    \"\"\"tab est un tableau de n valeurs numériques. On crée une copie tabCopy de tab, on la trie par insertion et on renvoie [tabCopy, compt] où compt est le nombre total d'itérations.\"\"\"\n","execution_count":45,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":" **Tester les fonctions de tri modifiées avec le code ci-dessous à compléter.**  \n Les deux tris devraient évidemment donner le même résultat (même liste triée) mais le tri par insertion devrait demander environ deux fois moins d'itérations que le tri par sélection."},{"metadata":{"trusted":true},"cell_type":"code","source":"from random import randint\n#Création d'une Liste de N entiers aléatoires tirés entre valMin et valMax\nN=10\nvalMin=0\nvalMax=10\nL = [randint(valMin,valMax) for i in range(N)]\n\n#Affichage de la liste aléatoire et du résultat du tri\nprint('Liste de départ :', L)\nL1=tri_selection(L)\nL2=tri_insertion(L)\nprint('Liste triée par sélection :',,\" Nombre d'itérations :\",) #Ligne à compléter\nprint('Liste triée par insertion :',,\" Nombre d'itérations :\",) #Ligne à compléter","execution_count":46,"outputs":[{"output_type":"stream","text":"Liste de départ : [9, 6, 0, 10, 5, 5, 6, 3, 9, 2]\nListe triée par sélection : [0, 2, 3, 5, 5, 6, 6, 9, 9, 10]  Nombre d'itérations : 45\nListe triée par insertion : [0, 2, 3, 5, 5, 6, 6, 9, 9, 10]  Nombre d'itérations : 26\n","name":"stdout"}]},{"metadata":{"slideshow":{"slide_type":"slide"}},"cell_type":"markdown","source":"## 2. Mesures de complexité"},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"### 2.1 Comparaison des algorithmes\n\nDans le code ci-dessous, la commande `timeit` permet de comparer le temps d'exécution des tris pas insertion et par sélection, ainsi que le tri intégré dans Python (fonction `sorted`) qui est basée sur l'algorithme *timsort* (association du tri fusion et du tri par insertion). Ce dernier est bien mieux optimisé et donc bien plus rapide que nos tris *faits maison*."},{"metadata":{"slideshow":{"slide_type":"-"},"trusted":true},"cell_type":"code","source":"from timeit import Timer\n\n#Création d'une Liste de N entiers aléatoires tirés entre valMin et valMax\nN=1000\nvalMin=0\nvalMax=N\nL = [randint(valMin,valMax) for i in range(N)]\n\nprint(\"Durée d'exécution pour le tri par sélection :\")\n%timeit tri_selection(L)\nprint(\"Durée d'exécution pour tri par insertion :\")\n%timeit tri_insertion(L)\nprint(\"Durée d'exécution pour timsort :\")\n%timeit sorted(L)","execution_count":47,"outputs":[{"output_type":"stream","text":"Durée d'exécution pour le tri par sélection :\n50.8 ms ± 679 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\nDurée d'exécution pour tri par insertion :\n80.9 ms ± 2.55 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\nDurée d'exécution pour timsort :\n114 µs ± 2.61 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n","name":"stdout"}]},{"metadata":{},"cell_type":"markdown","source":"**Remarque importante :**\n\nEn moyenne, le **tri par insertion devrait être environ 2 fois plus rapide que le tri par sélection** puisqu'il demande environ deux fois moins d'itérations mais ce n'est pas ce qu'on observe ci-dessus. D'après nos mesures, le tri par insertion se révèle même plus lent que pour le tri par sélection.  \nCeci montre que la réalité est toujours plus complexe que la théorie. En effet, même s'il fait moins d'itérations, un algorithme peut être plus long à s'exécuter si les opérations élémentaires exécutées lors d'une itération sont plus longues. Justement parce qu'en fait, ce ne sont **pas vraiment des opérations élémentaires** !\n\nPour l'illustrer, on peut tester un algorithme légèrement amélioré pour le tri par insertion."},{"metadata":{},"cell_type":"markdown","source":"**Tri par insertion amélioré**  \nComme indiqué dans la partie cours, on peut un peu améliorer le tri par insertion en insérant réellement la valeur qu'on est en train de trier au bon endroit au lieu de la faire descendre pas à pas jusqu'à la bonne place."},{"metadata":{"trusted":true},"cell_type":"code","source":"def tri_insertion_ameliore(tab):\n    \"\"\"tab est un tableau de n valeurs numériques. On crée une copie tabCopy de tab, on la trie par insertion et on renvoie [tabCopy, compt] où compt est le nombre total d'itérations.\"\"\"\n    n=len(tab)\n    compt=0\n    tabCopy=list(tab)\n    for i in range (n-1):\n        j=i+1\n        tmp=tabCopy[j]\n        while j>0 and tmp<tabCopy[j-1]:\n            tabCopy[j]=tabCopy[j-1]\n            j=j-1\n            compt=compt+1\n        tabCopy[j]=tmp\n    return [tabCopy,compt]","execution_count":48,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"**Nouvelle mesure des temps d'exécution :**"},{"metadata":{"slideshow":{"slide_type":"-"},"trusted":true},"cell_type":"code","source":"from timeit import Timer\n\n#Création d'une Liste de N entiers aléatoires tirés entre valMin et valMax\nN=1000\nvalMin=0\nvalMax=N\nL = [randint(valMin,valMax) for i in range(N)]\n\nprint(\"Durée d'exécution pour le tri par sélection :\")\n%timeit tri_selection(L)\nprint(\"Durée d'exécution pour tri par insertion :\")\n%timeit tri_insertion(L)\nprint(\"Durée d'exécution pour tri par insertion amélioré :\")\n%timeit tri_insertion_ameliore(L)\nprint(\"Durée d'exécution pour timsort :\")\n%timeit sorted(L)","execution_count":49,"outputs":[{"output_type":"stream","text":"Durée d'exécution pour le tri par sélection :\n67.6 ms ± 3.55 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\nDurée d'exécution pour tri par insertion :\n95.8 ms ± 5.68 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\nDurée d'exécution pour tri par insertion amélioré :\n67.7 ms ± 1.89 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\nDurée d'exécution pour timsort :\n135 µs ± 19.1 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n","name":"stdout"}]},{"metadata":{},"cell_type":"markdown","source":"**Résultat :**\nDans cette version améliorée, le tri par insertion devient à peu près aussi rapide que le tri par sélection mais il n'est toujours pas plus rapide. Ceci est du au **fonctionnement propre de Python qui est nettement plus lent pour écrire dans une liste que pour faire des comparaisons**. Or le tri par sélection fait beaucoup de comparaisons mais peu d'écriture alors que c'est plutôt l'inverse pour le tri par insertion. Ce dernier est donc défavorisé par Python."},{"metadata":{},"cell_type":"markdown","source":"### 2.2 Pire et meilleur des cas\n\nLe tri par sélection fonctionne de la même façon quelle que soit la liste fournie en entrée. Par contre, nous avons vu que que **le fonctionnement du tri par insertion pouvait varier selon les cas**. La comparaison précédente donne-t-elle le même résultat dans le pire et le meilleur cas pour le tri par insertion ?\n\n**En théorie**, les 2 algorithmes sont **équivalents dans le pire des cas** (liste triée en sens inverse) mais le **tri par insertion devient linéaire** et donc beaucoup plus rapide que le tri par sélection **dans le meilleur des cas** (liste déjà triée).\n\n**Q4. Dans le programme précédent, modifier la liste L fournie en entrée afin de renouveler la comparaison, mais cette fois dans le pire et le meilleur des cas (pour l'agorithme de tri par insertion).**"},{"metadata":{"slideshow":{"slide_type":"-"},"trusted":true},"cell_type":"code","source":"# Question 4\nN=1000\n#Création d'une Liste de N entiers dans le pire des cas\nL = [randint(0,N) for i in range(N)]\nprint(\"PIRE DES CAS :\")\nprint(\"Durée d'exécution pour le tri par sélection :\")\n%timeit tri_selection(L)\nprint(\"Durée d'exécution pour tri par insertion :\")\n%timeit tri_insertion(L)\nprint(\"Durée d'exécution pour timsort :\")\n%timeit sorted(L)\n\n#Création d'une Liste de N entiers dans le meilleur des cas\nL = [randint(0,N) for i in range(N)]\n\nprint(\"MEILLEUR DES CAS :\")\nprint(\"Durée d'exécution pour le tri par sélection :\")\n%timeit tri_selection(L)\nprint(\"Durée d'exécution pour tri par insertion :\")\n%timeit tri_insertion(L)\nprint(\"Durée d'exécution pour timsort :\")\n%timeit sorted(L)","execution_count":50,"outputs":[{"output_type":"stream","text":"PIRE DES CAS :\nDurée d'exécution pour le tri par sélection :\n75.1 ms ± 6.24 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\nDurée d'exécution pour tri par insertion :\n198 ms ± 12.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\nDurée d'exécution pour timsort :\n51.6 µs ± 2.27 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\nMEILLEUR DES CAS :\nDurée d'exécution pour le tri par sélection :\n63.7 ms ± 4.67 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\nDurée d'exécution pour tri par insertion :\n236 µs ± 11.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\nDurée d'exécution pour timsort :\n10.8 µs ± 1.42 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n","name":"stdout"}]},{"metadata":{},"cell_type":"markdown","source":"**COMMENTAIRES :**\n\n> Dans le **pire des cas (liste initiale triée par ordre décroissant)**, les tris par sélection et par insertion sont **normalement équivalents** car ils font le **même nombre d'itérations**, mais, pour les raisons évoquées précédemment, on observe ici que le **tri par insertion s'avère environ 3 fois plus lent**.  \n> Dans le **meilleur des cas (liste déjà triée)**, par contre, le **tri par insertion se montre bien beaucoup plus rapide que le tri par sélection**.  \n> Dans tous les cas, **l'algorithme de tri intégré dans Python reste bien plus rapide que les deux autres**."},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"### 2.3 Vérification de la complexité\n\nOn veut à présent vérifier que la **complexité moyenne des algorithmes de tri par sélection et insertion sont quadratiques**.\n\nLe code ci-dessous permet de tracer les **courbes donnant le nombre d'itération de nos deux algorithmes de tri en fonction de la taille n du tableau à trier**. Une courbe de modélisation quadratique est ajoutée sur le graphique.\n\n**Q5. Faire varier la valeur de la variable `cas` (1, 2 ou 3) pour observer ce que l'on obtient dans le pire et le meilleur des cas.**\n\nOn remarquera en particulier que :\n- dans le cas moyen, le nombre d'itérations varie bien comme $y=N^2/2$ pour le tri par sélection et $y=N^2/4$ pour le tri par insertion,\n- dans le meilleur des cas, le tri par insertion est extrêmement rapide alors que le tri par sélection n'est pas modifié,\n- dans le pire des cas, les deux tris sont équivalents."},{"metadata":{"slideshow":{"slide_type":"-"},"trusted":true},"cell_type":"code","source":"from matplotlib import pyplot as plt\nfrom scipy.optimize import curve_fit\n\ndef quadratique (x,a): # fonction quadratique de la forme y=f(a*x²) pour la modélisation\n    return a*x*x\n\n# Faire une boucle sur les valeurs de n pour calculer les temps d'exécution sur chacun des 2 algorithme\n# La liste abscisse contiendra les valeurs de n, les listes ordonnee1 et ordonnee2 contiendront les nombres d'itération des 2 algorihtmes. \nabscisse=[]\nordonnee1=[]\nordonnee2=[]\nmodele1=[]\nmodele2=[]\n\ninc=1000 # incrément de N\ndebut=1000 # première valeur de N\nfin=11000 # valeur de fin pour N (non atteinte)\ncas=2 #cas = 1 pour meilleur des cas (dejà trié), cas = 2 pour pire des cas (trié à l'envers) et cas = 3 pour cas moyen (aléatoire)\nfor N in range(debut,fin,inc): # la taille N du tableau varie de debut à fin par pas de inc\n    print('N = ',N)\n    abscisse.append(N) # N sera en abscisse\n    if cas == 1 :\n        L=sorted([randint(0,N) for k in range(N)]) # meilleur cas\n    elif cas == 2 :\n        L=sorted([randint(0,N) for k in range(N)], reverse=True) # pire cas\n    elif cas == 3 :\n        L=[randint(0,N) for k in range(N)] # cas moyen\n    L1=tri_selection(L)\n    ordonnee1.append(L1[1])\n    L2=tri_insertion(L)\n    ordonnee2.append(L2[1])\n \n#calcul des paramètres de modélisation pour ordonnee1 et ordonnee2\nparametres1, covariance = curve_fit(quadratique, abscisse, ordonnee1) \nparametres2, covariance = curve_fit(quadratique, abscisse, ordonnee2)\n\nfor i in range(len(abscisse)) : #construction des ordonnées pour les 2 modèles\n    modele1.append(quadratique(abscisse[i],*parametres1))\n    modele2.append(quadratique(abscisse[i],*parametres2))\n    \n# courbes pour les modèles avec légende    \nplt.plot(abscisse,modele1)\nplt.plot(abscisse,modele2)\nprint('Modele 1 : y = {:.2E}*N²'.format(*parametres1))\nprint('Modele 2 : y = {:.2E}*N²'.format(*parametres2))\n\n# nom des axes    \nplt.xlabel('Longueur N de la liste')\nplt.ylabel(\"Nombre d'itérations\")\n# definition des courbes\nplt.scatter(abscisse,ordonnee1,color='red', label='Tri par sélection')\nplt.scatter(abscisse,ordonnee2,color='blue', label='Tri par insertion')\nplt.legend()\n#tracé du graphique\nplt.show()","execution_count":55,"outputs":[{"output_type":"stream","text":"N =  1000\nN =  2000\nN =  3000\nN =  4000\nN =  5000\nN =  6000\nN =  7000\nN =  8000\nN =  9000\nN =  10000\nModele 1 : y = 5.00E-01*N²\nModele 2 : y = 5.00E-01*N²\n","name":"stdout"},{"output_type":"display_data","data":{"text/plain":"<Figure size 432x288 with 1 Axes>","image/png":"iVBORw0KGgoAAAANSUhEUgAAAXkAAAERCAYAAACepNcKAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAA1RElEQVR4nO3dd3xUZfb48c9JgRB6R2oQKQIJBAKEomtF6aKoIIq6alSwf9VVcdeysr9dd1dXpQmigEZwRRE7rgoqSkuk9xZCCCW0AKEmc35/zE0MSJIBMrmTyXm/XvPKzK1nLpeTm+c+9zyiqhhjjAlOIW4HYIwxxn8syRtjTBCzJG+MMUHMkrwxxgQxS/LGGBPELMkbY0wQC7gkLyJvi8huEVnpw7KvishS57VeRA6UQIjGGFNqSKD1kxeRS4HDwFRVbXsW6z0IxKrqH/0WnDHGlDIBdyWvqj8C+/JPE5FmIvK1iCSLyE8i0uoMqw4BppVIkMYYU0qEuR2AjyYA96nqBhHpAowFrsidKSJNgKbA9y7FZ4wxASngk7yIVAK6AR+KSO7k8qctNhiYoao5JRmbMcYEuoBP8niblA6oavtClhkMjCiZcIwxpvQIuDb506nqQWCLiNwIIF7tcuc77fPVgfkuhWiMMQEr4JK8iEzDm7BbikiaiNwFDAXuEpFlwCpgQL5VBgPTNdC6CRljTAAIuC6Uxhhjik/AXckbY4wpPgF147VWrVoaFRXldhjGGFNqJCcn71HV2gXND6gkHxUVRVJSktthGGNMqSEiWwubb801xhgTxCzJG2NMELMkb4wxQSyg2uTP5OTJk6SlpXHs2DG3QzHnISIigoYNGxIeHu52KMaUKQGf5NPS0qhcuTJRUVHkq11jShFVZe/evaSlpdG0aVO3wzGmTPFrc42IpIjICmdQj3PqNnPs2DFq1qxpCb4UExFq1qxpf40Zc5rE4fOICksjRDxEhaWROHxese+jJK7kL1fVPeezAUvwpZ/9GxpzqsTh80gYF8sRKgKwNachCeOqA/MYOrZHse3HbrwaY4wLRk6I4ggV6dZuDv836G+AcoSKjJwQVaz78XeSV+AbZ0SnhDMtICIJIpIkIkkZGRl+Dic4ZWdnM3r0aI4fP+52KMYYH6Xm1Kdl0xV82v82Hmw5mUqRmXnTi5O/k3wPVe0A9AJGOOO3nkJVJ6hqnKrG1a5d4JO5rti7dy/t27enffv21KtXjwYNGuR9PnHiBACffvopf//7312LUVV55JFHiImJoXx571gqkydP5oEHHjin7f3tb3875XO3bt3OO0ZjzO91qPcrX99yAyBcm/gRh49UA6BxaHqx7sevSV5Vtzs/dwMzgc7+3B8AiYkQFQUhId6fiYnnvKmaNWuydOlSli5dyn333cejjz6a97lcuXJkZ2fTv39/nnrqqWILH7yJ2+Px+LSsiDB69GguvfR3vz/PyelJ/pdffimW7RpjfnPo4H6m3n0PdUP3M2DWVNamRAMQSRajElKKdV9+S/IiUlFEKue+B3oCK/21P8Cb0BMSYOtWUPX+TEg4r0R/ujvuuIP77ruPLl268OSTTxZ41fz8889z22230bVrV5o3b87EiRMBOHz4MFdeeSUdOnQgOjqaWbNmAZCSkkLLli0ZNmwYbdu2Zdu2bads76mnnqJ169bExMTw+OOPA5CRkcENN9xAp06d6NSpEz///PPv4ihomcOHD3PnnXcSHR1NTEwMH330EU899RRHjx6lffv2DB06FIBKlSoB3l88TzzxBG3btiU6OpoPPvgAgLlz53LZZZcxaNAgWrVqxdChQ7Hy1cYU7MTx42weM4iWIVv4+NATpK1qjuChSWgaE+5fUqw3XQHvf15/vIALgWXOaxUwsqh1OnbsqKdbvXr176YVqEkTVW96P/XVpInv2yjAc889p//85z/19ttv1z59+mh2draqqr7zzjs6YsSIMy4fExOjR44c0YyMDG3YsKFu375dT548qZmZmaqqmpGRoc2aNVOPx6NbtmxREdH58+f/blt79uzRFi1aqMfjUVXV/fv3q6rqkCFD9KefflJV1a1bt2qrVq1+F1NByzz55JP68MMP5+1j3759qqpasWLFU/ad+3nGjBl61VVXaXZ2tu7cuVMbNWqk6enpOmfOHK1SpYpu27ZNc3JyND4+Pm9/pzurf0tjglBOdo4ueOUm1eeq6OKPXi2WbQJJWkhe9VsXSlXdDLQrcsHilJp6dtPP0Y033khoaGiRyw0YMIAKFSpQoUIFLr/8chYtWkSfPn145pln+PHHHwkJCWH79u3s2rULgCZNmhAfH/+77VStWpWIiAjuuusu+vbtS9++fQH49ttvWb16dd5yBw8e5PDhw6esW9Ay3377LdOnT8+bXr169UK/y7x58xgyZAihoaHUrVuXP/zhDyxevJgqVarQuXNnGjZsCED79u1JSUmhR49ivhoxJgjMn/QY3TO/ZlGTe+l8/SMlss+Af+L1rDRu7G2iOdP0YlSxYkWflju9b7iIkJiYSEZGBsnJyYSHhxMVFZX3kFBB2w0LC2PRokV89913zJgxg9GjR/P999/j8XhYsGABERERBcbgyzLnK/eGL0BoaCjZ2dl+25cxpdX86S/TPf0dkmr0o9PtJddZI7j6yY8aBZGRp06LjPROd8GsWbM4duwYe/fuZe7cuXTq1InMzEzq1KlDeHg4c+bMYeuZfimd5vDhw2RmZtK7d29effVVli1bBkDPnj1544038pZbunTp79YtaJmrr76aMWPG5E3fv38/AOHh4Zw8efJ327nkkkv44IMPyMnJISMjgx9//JHOnf1/H92YYJD89bt0XvM3lkd2IXb4O0hIyaXe4EryQ4fChAnQpAmIeH9OmOCd7oKYmBguv/xy4uPj+fOf/0z9+vUZOnQoSUlJREdHM3XqVFq1alXkdg4dOkTfvn2JiYmhR48evPLKKwC8/vrrJCUlERMTQ+vWrRk/fvzv1i1omWeffZb9+/fTtm1b2rVrx5w5cwBISEggJiYm78ZrroEDBxITE0O7du244oorePnll6lXr975HiJjgt6qBd/QZv6jbApvQYsRMwgNK9kifQE1kHdcXJyePjLUmjVruPjii12K6Nw9//zzVKpUKa8njCm9/5bGnKsta5dQfXpfDksVKg3/jmq1i/dBJwARSVbVuILmB9eVvDHGBIhd21OImH4jOYQSevvHfknwvgiuG68B5Pnnn3c7BGOMSzIP7OPwpOu4QA+y4/qPaBbl3l+wdiVvjDHF6Pjxo6SOHUjjnFS2XDmOZu0ucTUeS/LGGFNMPDk5LBt9K9EnlrKi419pc+kNbodkSd4YY4rLgokP0fnQtyy68AE69B/hdjiAJXljjCkW899/iW4732Nx7evpdOtf3Q4njyX5QgRSqeG77777lPIExe3AgQOMHTs273N6ejqDBg3y2/6MCSaLv5hEl3X/YmnFHnS8d2KJPuxUlKDrJ5+YCCNHesvVNG7sfdi1OJ6FOlO/9+zsbMLCir+DUm5hoZASOlGys7NJS0ujb9++rFzpv0Kh1k/eBKOVP39Bi2+GsblcC6Ie/R8RkZVKdP9lqp98CVQadq3U8GWXXUbuL8BKlSoxcuRI2rVrR3x8fF6Bsw8//DDvCdbc+vI5OTk88cQTdOrUiZiYGN58803AWyL4kksuoX///rRu3ZqnnnqKTZs20b59e5544glSUlJo27Yt4B1MPbcscWxsbN7TsZMnT+b666/n2muvpXnz5jz55JPFd6CNKQU2rVxE42/uZmdoPerfP6vEE7wvgqqf/MiRcOTIqdOOHPFOL87KBmlpafzyyy+EhoYyefLkApdbvnw5CxYsICsri9jYWPr06UOdOnWYOXMmVapUYc+ePcTHx9O/f38ANmzYwJQpU85YiTK/rKws4uPjGTVqFE8++SQTJ07k2Wef5cUXX2T27Nk0aNCAAwcOADBp0iSqVq3K4sWLOX78ON27d6dnz54A/Prrr6xcuZKmTZuSkpLCypUr82rbpKSk5O1vzJgxiAgrVqxg7dq19OzZk/Xr1wPeWjhLliyhfPnytGzZkgcffJBGjRqd24E1phTZkbqRSjMGc1zKE3HnTKrUqON2SGcUVFfyJVRp+KxLDdeqVSuv1LCq8swzzxATE8NVV13lU6nh05UrVy6v3HDHjh3zEnL37t254447mDhxIjk5OQB88803TJ06lfbt29OlSxf27t3Lhg0bAOjcuTNNmzYtcn/z5s3j1ltvBaBVq1Y0adIkL8lfeeWVeaWQW7du7VPBNWNKu8x9GRybfD0VOULWoA+o06iF2yEVKKiu5Euo0nCJlxo+XXh4eN6285f2HT9+PAsXLuSLL76gY8eOJCcno6q88cYbXHPNNadsY+7cuT7vrzBWZtiUNceOZpE2biDNc9LY2HMKrdt2cTukQgXVlXyAVRoutlLDvtq0aRNdunThxRdfpHbt2mzbto1rrrmGcePG5ZUPXr9+PVlZWb9bt3Llyhw6dOiM273kkktIdG5srF+/ntTUVFq2bFlscRtTWuTk5LBy9BDanFzBqs7/oHX3fm6HVKSgupLPbXf3R++ac5FbanjPnj2nlBru168f0dHRxMXF+VRq2FdPPPEEGzZsQFW58soradeuHTExMaSkpNChQwdUldq1a/PJJ5/8bt2aNWvSvXt32rZtS69evRgx4rcHOYYPH879999PdHQ0YWFhTJ48+ZQreGPKAvV4WDjuXrpl/cCi5o/Ruc89bofkk6DrQhkorNTw75XWf0tjAH6Z+he6bX6NRXUH0/m+8d4xKwJAmepCaYwx/rBo1ni6bX6NXytfTlzC2IBJ8L4IquaaQGKlho0JDst+nEX7X59hdUQMbUdMI8SHnnWBpFRcyQdSk5I5N/ZvaEqjDcvm0+y7e9ke2pBG98+kXEQFt0M6awGf5CMiIti7d68liVJMVdm7dy8RERFuh2KMz7ZvWUe1mUPIkkgq3fUJlavVcjukcxLwzTUNGzYkLS2NjIwMt0Mx5yEiIoKGDRu6HYYxPtmXsYOcqQMpzwkODP6Mxg0udDukcxbwST48PNynpzKNMaY4HMk6xK43B3KhZzdber9Hq1Yd3Q7pvAR8c40xxpSU7JMnWTvmZlqeXMuabv+iVZdr3Q7pvFmSN8YYvA87JY2/mw5Hfia59Z9of80dbodULCzJG2MMMH/KSOL3fsKi+rfR6ean3Q6n2FiSN8aUeQs/fp1uW8eSXPVqOt39mtvhFCtL8saYMidx+DyiwtIIEQ+3/2ESHZc9x8qIDsSMeA8JKV0POxUl4HvXGGNMcUocPo+EcbEcoSLx0T8w9rKnWXuiCUv2PEXbcsH3LIffk7yIhAJJwHZV7evv/RljTGFGTojiCBVpGbWCT6+7jX05Vbhm0qeE7wvhtjFuR1f8SuJK/mFgDVClBPZljDGFSs2pT4uoVXx/6wBC8dBr2gzSMxojeNwOzS/82iYvIg2BPsBb/tyPMcb4qnvTn/j+1v5EyAl6/vcjVm1uD0Dj0HR3A/MTf994/Q/wJBT8K1JEEkQkSUSSrHSBMcaf0jat5r+33kmkHKPnfz8ieZ136L5IshiVkOJucH7ityQvIn2B3aqaXNhyqjpBVeNUNa527dr+CscYU8albVpN2Lv9qBBynM8yX2LPxgYIHpqEpjHh/iUMHdvD7RD9wp9t8t2B/iLSG4gAqojIe6p6qx/3aYwxv5O2eQ2h7/YjgmPsu2EGw6K7MiyvO3xD5xWc/HYlr6pPq2pDVY0CBgPfW4I3xpS07ZvXEDq1L5EcZd8NH3JhdFe3QypR9jCUMSZopW1ZS8jUfkRylL03zODC6G5uh1TiSuRhKFWdC8wtiX0ZYwx4B/0IndKXSI6w9/oPy2SCB7uSN8YEoe1b1iFT+lIxN8HHdHc7JNdYkjfGBJX0lHXI1L5UIouMgR+U6QQPluSNMUEkfet6dEo/KmkWu6+bTrN2l7gdkuusQJkxJiikb12PTu5LZT3E7us+4KL2l7odUkCwK3ljTKmXP8FnWII/hSV5Y0yptiN1Azq5L1X0IBkDptPMEvwpikzyInKjiFR23j8rIh+LSAf/h2aMMYXbkboBzzt9qKIH2dX/A5rF/sHtkAKOL1fyf1bVQyLSA7gKmASM829YxhhTuB2pG8l5x3sFv7P/NC7qYAn+THxJ8jnOzz7ABFX9Aijnv5CMMaZwO7ZtIuedPlTVTHb2n0bzDpe7HVLA8iXJbxeRN4GbgS9FpLyP6xljTLHbkbaZ7Lf7UE0z2dnvfUvwRfAlWd8EzAauUdUDQA3gCX8GZYwxZ7IzbTM5k3pT3XOA9H7v07zjFW6HFPCKTPKqegSYBWSJSGMgHFjr78CMMSa/nWmbOTmpD9U8B0jvl0gLS/A+KfJhKBF5EHgO2MVvIzwpEOPHuIwxJs+u7d4EX8Ozj+19E2kRd6XbIZUavjzx+jDQUlX3+jsYY4w53a7tWzjxljfBp/VNpGWnq9wOqVTxpU1+G5Dp70CMMeZ0u7encPyt3k6Cf88S/Dnw5Up+MzBXRL4AjudOVNVX/BaVMabM2719K8fe6kUtz15S+7xHq05Xux1SqeRLkk91XuWw/vHGmBLwuwTfuafbIZVaRSZ5VX0BQEQqOZ8P+zsoY0zZlbEjlaNv9aa2Zw/bek+1BH+efKld01ZElgCrgFUikiwibfwfmjGmrMnYkcqRCb2o7clgW+8ptOxyrdshlXq+3HidADymqk1UtQnwf8BE/4ZljClrMnakkuUk+NReU2jZpZfbIQUFX5J8RVWdk/vBGZS7ot8iMsaUObkJvo4ng629ptAq3hJ8cfGpd42I/Bl41/l8K94eN8YYc94ydqSSNdGb4FN7TeZiS/DFypcr+T8CtYGPnVdtZ5oxxpyXjJ2pZE3sTZ2cDLZeO5lW8b3dDino+NK7Zj/wUAnEYowpAxKHz2PkhCiO1/Dwwz29aBS2my3XTKZ1V0vw/lBgkheR/6jqIyLyGd5aNadQ1f5+jcwYE3QSh88jYVwslWvtZ+49fWgUtpubvnqTwRlVad3N7eiCU2FX8rlt8P8qiUCMMcFv5IQoqtXZy7d396VJ2E4Gfv02sxf3Y8WvaQwd63Z0wanAJK+qyc7b9qr6Wv55IvIw8IM/AzPGBJ9KUbv5csjN1ArJ5PqvJzF7UT8AUnPquxxZ8PLlxuvtZ5h2RzHHYYwJcqsXfsNPt/QjUo5x1ccz+HrRby2+jUPTXYwsuBXWJj8EuAVoKiKf5ptVGdjn78CMMcEj6auptF3wGLuoSb8p77MitWPevEiyGJWQAjR0Lb5gVlib/C/ADqAW8O980w8By/0ZlDEmePwy7f8Rv/YfbCzXgjoJn/CnPZsZOSGN1Jz6NA5NZ1RCCkPH9nA7zKAlqr/rOOOauLg4TUpKcjsMY0wx8OTksGDiQ3Tb+R5LI7vR6oH/EhFZ2e2wgo6IJKtqXEHzfSlQFi8ii0XksIicEJEcETnow3oRIrJIRJaJyCoReeFsgzfGlE7Hjh4h+T830m3neyyuNZDoxz61BO8SX8oajAYGAx8CccAwoIUP6x0HrlDVwyISDswTka9UdcE5R2uMCXiZ+/eybdxAOp1YxsILH6TzrS8iIb708TD+4NORV9WNQKiq5qjqO0CR9T/VK7f2fLjzCpy2IWNMsduxbRN737iclsdXktzh73QZ9pIleJf5ciV/RETKAUtF5GW8N2N9+lcTkVAgGbgIGKOqC8+wTAKQANC4cWNf4zbGBJhNKxdRacZg6ugR1l/9Dh17DHA7JINvyfo2Z7kHgCygEXCDLxt3rvzb4+0b1VlE2p5hmQmqGqeqcbVr1/Y5cGNM4Fgx73NqfziAEDxk3DiTNpbgA0ahV/LOlfjfVHUocAw4p5unqnpARObgbeZZeS7bMMYEpsWfTaRd0lPsCL2AiDtm0rRxc7dDMvkUeiWvqjlAE6e55qyISG0Rqea8rwBcDaw9lyCNMYFHPR5+mfoXOiU/zqbyraj24BzqWoIPOD4NGgL87Dz1mpU7UVVfKWK9C4Apzl8DIcB/VfXzc47UGBMwcrKzWTT+Prrt+ZBfK19GmxHvUz7CBowLRL4k+U3OKwRvSQOfqOpyIPYc4zLGBKhjRw6zasxgumb9xKK6g4lLGEtIaKjbYZkC+DJoyAsAIhKpqkf8H5IxJlDt37OLnW9eR+yJNSxq+X90vuUvbodkinDGNnnn4aXc911FZDVOe7qItBMRq/xsTBmzfcs6Do65gmYn1rMs/lVL8KVEQTdeE0Qkt2LQf4BrgL0AqroMuNT/oRljAsWGpT9TfkpPqut+Nvd6j9hed7odkvFRQUl+PHBT7gdV3Xba/By/RWSMCShL535E/ZnXk00YBwZ/Rqv4Xm6HZM7CGdvkna6TuYN3bxORboA6zTgPA2tKKD5jjIsWzhxNh6V/YVtYI6rcNYt69aPcDsmcJV9619wHvAY0ALYD3wDD/RmUMcZd6vHwy5Rn6L51HCsjYoka8TGVqtRwOyxzDnxJ8i2dJ17ziEh34Gf/hGSMcVP2yRMkjbub7vtmkVS1J+1GvEt4uQi3wzLnyJfaNW/4OM0YU8plHcpkxSv9iN83i4UNbqfjwx9Ygi/lChvjtSvQDagtIo/lm1UFsCcfjAkye3ZtZ+/E64g5uYFFbZ6hy01/cjskUwwKa64pB1Rylsn/pOtBYJA/gzLGlKzUjSsJSRxEY89eVvYYQ+erhxa9kikVCkzyqvoD8IOITFbVrSUYkzGmBK1NnkOdz4YhKNv6f0C7jle4HZIpRoU11/xHVR8BRovI70Z0UtX+/gzMGON/S76dTsufHuJASDU8t8ygRfMYt0Myxayw5pp3nZ//KolAjDEla8GH/6bTyr+yOfwiat4zkxp1G7kdkvGDwpprkp2fP5RcOMYYf0kcPo+RE6JIzanHf25/iIeiElke2ZmLRnxIZKVqbodn/KSw5po5eAfe3qeqdqPVmFIscfg8EsbFciIsjMQRQxlS62sSd/XGI/cSYwk+qBXWXHOH89Pq1BhTyo2cEEWFaof5/K4hXF4pmVEb7+XZxL/TJDSd26ymbFArrLnGetQYEyTqt97I9AH3UC9kL/cn/ZXxX3hLU6Xm1Hc5MuNvhTXXHMLbXHNGqlrFLxEZY4qNejwsnPFv5gz8Oxme6lw+82N+WXFZ3vzGoelAQ9fiM/5X2JV8ZQAR+SuwA29vGwGG4h2/1RgTwLIOZbJ64l3EH/wfi3JiGTTmHbYdaJo3P5IsRiWkYEk+uPlSu6a/qo5V1UOqelBVxwED/B2YMebcbV23lN2v9qBj5rcsiLqfuBe+4/8N2U6T0DQED01C05hw/xKGju1R9MZMqeZLFcosERkKTMfbfDMEyPJrVMaYc7b4i7dovWgkJ6Qca66aQvwl3muyoWN7MDTvJmtD7Aq+bPAlyd+Ct578a3iT/M/ONGNMADl+/Ci/vvUgXTM+ZG251tS8I5E2DS50OyzjsiKTvKqmYM0zxgS0HakbyJx6K12z17Kw7mA63PU64eXKux2WCQC+XMkbYwLYsrkf0Xjuw1TWbJZ0fZ0u197udkgmgFiSN6aUysnOZtHkP9Fl2yS2hjUhfPC7xFqBMXMaS/LGlEL7dqeTNulWuh5PJqnaNbS9dxIRkZWLXtGUOUV2oRSRuiIySUS+cj63FpG7/B+aMeZM1i7+jpNje9Dy2HKSop8n7pEPLMGbAvnST34yMBvIff55PfCIn+IxxhRAPR7mv/8SzT6/kRwJI+2GT4i74VEQcTs0E8B8SfK1VPW/gAdAVbOxomXGlKhDmftIfmUgXdf/k1UVu1DxoZ9pFmMPMpmi+fowVE2cOjYiEg9k+jUqY0yezasXEfbhHcR60ll40UN0Hvo8EhLqdlimlPAlyT8GfAo0E5GfgdrYQN7GlIhFs8bR9tfnOCoVWH/t+3Tp2tvtkEwpU2iSF5FQ4A/OqyXeAmXrVPVkURsWkUbAVKAu3r8CJqjqa+cdsTFlwLGjWSybeD9d9s1idflo6tyZyMUXNHE7LFMKFZrkVTVHRIao6qvAqrPcdjbwf6r6q4hUBpJF5H+quvpcgzWmLNi+eS1HEofSJWcjC+oPI+7OfxMWXs7tsEwp5Utzzc8iMhr4gHyFyVT118JWUtUdeEsUo6qHRGQN0ACwJG9MAZZ8O50L5z1GZZRlPcYRf5WViTLnx5ck3975+WK+aQpc4etORCQKiAUWnmFeApAA0LhxY183aUxQyT55gkXvPE639ClsDG1G5K2JtGt6sdthmSDgS4Gyy89nByJSCfgIeERVD55h+xOACQBxcXEFjkRlTLDK2JnKrrdvpduJZSyq0Y+Ye94kokJFt8MyQaLIJO90n3wO6IH3Cn4e8KKq7vVh3XC8CT5RVT8+z1iNCTqr5n9Fndn300yzSIodRefrHnA7JBNkfHkYajqQAdyAt+tkBt72+UKJiACTgDWq+sr5BGlMsFGPh1+mPkfLr2/hmFRg102fE2cJ3viBL23yF6jqX/N9fklEbvZhve7AbcAKEVnqTHtGVb88yxiNCSqZ+/ewaeIwuh35mSWVL+Wie6ZQuWoNt8MyQcqXK/lvRGSwiIQ4r5vw1rIplKrOU1VR1RhVbe+8LMGbMidx+DyiwtIIEQ+9oz8j89VuRGctYEGLx2n/2CxL8MavCrySF5FDeNvgBW9BsvecWSHAYeBxfwdnTGmXOHweCeNiOUIkw/u9xr9jX+KApzLTDo1i2C33ux2eKQMKTPKqarVLjTlPIydEUb7KUSbddieDa83mx6xYbnrnPSIOwLBX3Y7OlAU+DRoiIjFAVP7lrbeMMUXrcun3vNb9L9QKyeTlzXfxdOLLeDxhiLeoqzF+50sXyreBGLxlDXLPTAUsyRtTgIydqaS+9wAfXPoDq040ZcDH77Jo9SV58xuHpgMN3QvQlBm+XMnHq2prv0diTBBQj4fFn46nxdJRROsxZh67hTteGcXB7N9urkaSxaiEFCzJm5LgS5KfLyKtrbCYMYVL37qejGn30/lYEuvCLybihnEMbBXLkUPzGDkhitSc+jQOTWdUQgpDx9qAH6ZkiGrhlQRE5A9468nvBI7j7W2jqlrsw8LHxcVpUlJScW/WGL/y5OSw6MOXiV7zHwRlxcWP0GnQk4SE+XTLy5jzIiLJqhpX0HxfzsJJOA81gd0tMia/reuWcmTGcOJPrmJFhQ7UGjKeLk1auh2WMXl8SfIZqvqp3yMxphQ5eeI4SdNepMPmNzku5Uhq/xId+49AQnx5vtCYkuNLkl8iIu8Dn+FtrgGsC6UpuzYu+xk+fZCuOZtYUukSGt02lrh6VibbBCZfknwFvMm9Z75p1oXSlDnHjmbx67vP0Hn7VDKlCkviXyP22jvcDsuYQvlST/7OkgjEmEC2ZuE3VPz6EbrpdpKqX0uL294gtmYdt8Mypki+PAzVEHgDb1VJgJ+Ah1U1zZ+BGRMIDh86wMqp/0fn3R+xK6QWKy5/m7g/3OB2WMb4zJe7RO/g7UJZ33l95kwzJqgtm/sRh/8dR+fdH7G4zg1UeSyJaEvwppTxpU2+tqrmT+qTReQRP8VjjOsO7NnF+ncfonPm16SGNGD9tR/SpfPVbodlzDnxJcnvFZFbgWnO5yFAkUP/GVPaqCpLZk+h8YLn6KAHWdDwDmJv+xvlI2y8VVN6+ZLk/4i3Tf5VvL1qfgHsZqwJKnvSt5KaOIIOWT+xKbQZmQOmEx/T1e2wjDlvvvSu2Qr0L4FYjClx6vGw+JMxtFr+/2ijJ1jQ7CHiBj9LWLnybodmTLEobGSovxSynp427qsxpU56yjr2TruPzsd/ZU14GyrdOJb4Fu3dDsuYYlXYlXzWGaZVBO4CagKW5E2plJOdzeL//oPoda9RFWFRm2eIu+FxQkJD3Q7NmGJX2PB//859LyKVgYfxtsVPB/5d0HrGBLKUtb9y7KPhxJ9cw/IKnah7y1g6N27hdljG+E2h/eRFpIaIvAQsx/sLoYOq/klVd5dIdMach8Th84gKSyNEPFwUsZmZf7qP+tOupt7JbSR3+DvRT35DXUvwJsgV1ib/T+B6YAIQraqHSywqY85T4vB5JIyL5QgV6dLmJyb1f4A25VL46WRXWj80kY51G7kdojElosBBQ0TEg7cwWTberpN5s/DeeK1S3MHYoCGmuESFpXGkaggvXP8899T/kL2eKjw0bxQLf7qMlGwbds8Ej3MeNERVrTC2KZUOH9xPwpDXePDCd4nkGO/t7suj77/K/oO1ERv3xpQxNj6ZCRrHjx1hycxXabFuPM80O8jnB3rwzOd/ZcWmDnnLNA5NxwbQNmWJJXlT6uVkZ5P8+QQaLnuVeN3NqnIxfLb7Voa/ditH+K0kQSRZjEpIwZK8KUssyZtSSz0eln43jWrz/0Fnz1Y2hTZj5R9epu0l19FGhLAT8xg5IYrUnPo0Dk1nVEIKQ8f2cDtsY0pUgTde3WA3Xo2vVs//ipDvXqBV9hq2SX0yOj9B7DW3IyH2QJMpW875xqsxgWjjivlkffFn2h1bzG5qsLjtX4jt/wCNrNaMMWdkSd6UCmmbVrHzk78Qd+hbDlKRhc0eot0NT9IpsrLboRkT0PyW5EXkbaAvsFtV2/prPya47UnfysaPn6NjxqfUJJQFDe/g4kHP0qV6bbdDM6ZU8OeV/GRgNDDVj/swQSpz/x5Wf/hX2m2fRkeyWVK7Pxfe8ALxFzRxOzRjShW/JXlV/VFEovy1fROcjmYdZunHL9N601t0JYvkqldSb8CLdG5mfwwacy5cb5MXkQQgAaBx48YuR2PccvLkCX6dNZqmK9+gK/tYHtGJir1fpGNMN7dDM6ZUcz3Jq+oEvEXQiIuLC5z+nKZEeHJyWDJ7CrUX/5Mums7a8IvZc/kYYrr1djs0Y4KC60nelE2qyoofP6HCjy/RMWcjKSGNWdptHO2uHIyEWNkkY4qLJXlT4tYlz+Hk7OeJObGUHVKbpNi/EdvnXqLC7HQ0prj5swvlNOAyoJaIpAHPqeokf+3PBL6ta39l72d/oUPWT+yjCgtbPkn7gY9yQUSk26EZE7T82btmiL+2bQJb4vBTa8a8cP9CLm42g477v6ImESxoci9tBz1NlyrV3Q7VmKBnfx+bYpV/RKZa1XfyxPUvcXONGYTsVxbXu5mWg54jvnZ9t8M0psywJG+K1cgJUTRovJURV47hzkYfUZFjTN/TizGfPcAvqd3dDs+YMseSvCkWOdnZrJg7g7cefosrKiXhQfjiwCX8+cvnWLGxo43IZIxLLMmb87JnVxobvh5H1JYPaE8GuyKr8/KWuxn7vxFs29k0bzkbkckYd1iSN2dNPR7WLv6WrHlvEnNwDl0lh5Xl27Mz9llWftqEv77b2UZkMiZAWJI3Pjt8cD8rv36LOmvf42JPCoeowJK611PvihG0bRULQOy1EIKNyGRMoLCRoUyRtqxOYtf3Y2ib8RWV5CibQi9kX+thtLnmj0RWqup2eMaUaTYylDknJ44fY/m371Fh2WTanFhBAw1jWbUrqHLJfbTocDnNrPSAMaWCJXlzip3bNrLl6zE03/4xcRwgXeqyoNnDtLr2fjrVvsDt8IwxZ8mSvMGTk8PKebPIWTiRmKz51AFWRHYhvfPdtL30euqH2uDYxpRWluTLsAN7drH26/E03DSNGN3BPqqwuOEwmvQcQbsmLd0OzxhTDCzJlzGqyvolP5L5wzhiDnxLvJxkbXhrkmIeJfrq24i3YmHGBBVL8mXE0axDrJj9NtVXvUvLnA0c0fIsq9WHOlcMp1WbLm6HZ4zxE0vyQeT06o+jElK49NHKbP/fWFrv/ozOZJES0oiFFz9N62sT6FK1htshG2P8zJJ8kMhf/TE05ARdLp1Dw4qTaJS4hHoayvIqlxLZ7V5adbmGKOv+aEyZYUk+SLwwuR6Xd5tNvzZf0r/ud1wQuo/0nJr8a+Od3PGvx+hYzwZJN6YssiRfimWkb2XL/JmEb/qGJU8kUVGOc0zD+eFQRx5echsf/3gTHk8Yj79nV+7GlFWW5EsRT04OG5bNY9+ST6mVPpfmORupDeykFh/vupqPVg3gm6TeHD1WKW+dJqFpWGEwY8ouS/IB7lDmPjbM/4zstV9z4YFfaMkBclRYX+5iFjQeQd24AURd3ImQB37hf/NiOWrVH40x+ViSD0DbNq4kbeFMKqV+R8tjy+kgORykIhsqdyGleU8u6nodF59WYsBb5dGqPxpjTmVVKAPAiePHWL/4Gw6t+JKGu3+gkaYDkBLSiJ11L6VKTD9axF1JWHg5lyM1xgQaq0IZoPbuSmPz/E8I3Tib5ocW01aOckLDWFuhPelRt9Goy0Ciml5MlNuBGmNKNUvyJUQ9HjatmE/Gr59SY/scmp9cTydRMqjOmppXEt6qFy269iWmcjW3QzXGBBFL8sXkTE+bDnw5mvXzv+DEmi+J2vczF7GPi4D1YS1Y1CSBWh370yy6K7VDrMqjMcY/LMkXg/xPmzZrtI7rOn3MBZHfEvrPZbSXkxzWCqyv3ImUZj25sOt1tKjXyO2QjTFlhCX5c6QeD7u2b2bXhiTSDixmygOv0q7KWpqHpwGwJfsC3kvvS/ywgTTvfA0dyke4HLExpiyyJO+DQ5n72L42icyty2D3aqpkrqPByS3U4wj1gHYtYHtOLVZlNePtDTczK2kAa7a0Q/DgmWhPmxpj3GNJPp+TJ46zfdMK9mxewsn0lVTYt5a6RzdxARm0cpY5rBVIK9eUNTV7Qt3WVGnSjpt7NWDF/ujfba9xaDr2IJIxxk1lMsmrx0PGjq3sXJ/MkbTlhGWspnrWRhplbyNKsokCsjWEtNCGpFeOZmvNi4loFEO95h2o2/AiWp1WxfFPg+eRMC6LI/a0qTEmwJT6JH+mXi35n/LMOnSAbeuSOZiyDN21ikqZ62hwYgt1OEwdZ5nd1GBnRDN+rdONsAuiqd40lobNY4iKiPSpn7o9bWqMCVSl+onX02uot2q6mrimCxnYcRGNa6RT5+gmGuiuvOWzNIK08CgyqzRH67ShUuN2NGzZkao16/rj6xhjjN+5+sSriFwLvAaEAm+p6t+Lc/sjJ0RxIiyMJY/H0apcChFyEoAcFdKONWBXxVak1hxIRINo6jbvSL3GLWgZan3SjTFlh9+SvIiEAmOAq4E0YLGIfKqqq4trH6k59VFCWHeoKT8djWPFzrYsTYllxcYYjh6vTJPi2pExxpRS/ryS7wxsVNXNACIyHRgAFFuSbxyaztachgwe8+Ep07011CsX126MMabU8mcn7gbAtnyf05xppxCRBBFJEpGkjIyMs9rBqIQUIsk6ZdpvvVqMMca4/qSOqk5Q1ThVjatdu/ZZrTt0bA8m3L+EJqFpCB6ahKYx4f4l1qvFGGMc/myu2Q7kL9LS0JlWrIaO7cHQsfl3Yf3SjTEmlz+v5BcDzUWkqYiUAwYDn/pxf8YYY07jtyt5Vc0WkQeA2Xi7UL6tqqv8tT9jjDG/59d+8qr6JfClP/dhjDGmYK7feDXGGOM/luSNMSaIBVTtGhHJALa6Hcd5qgXscTuIAGHH4lR2PE5lx+M353Msmqhqgf3PAyrJBwMRSSqsWFBZYsfiVHY8TmXH4zf+PBbWXGOMMUHMkrwxxgQxS/LFb4LbAQQQOxansuNxKjsev/HbsbA2eWOMCWJ2JW+MMUHMkrwxxgQxS/JFEJFGIjJHRFaLyCoRediZXkNE/iciG5yf1Z3pIiKvi8hGEVkuIh3ybet2Z/kNInK7W9/pfIlIqIgsEZHPnc9NRWSh850/cArSISLlnc8bnflR+bbxtDN9nYhc49JXOW8iUk1EZojIWhFZIyJdy/i58ajz/2SliEwTkYiydH6IyNsisltEVuabVmzng4h0FJEVzjqvi4gUGZSq2quQF3AB0MF5XxlYD7QGXgaecqY/BfzDed8b+AoQIB5Y6EyvAWx2flZ33ld3+/ud4zF5DHgf+Nz5/F9gsPN+PHC/8344MN55Pxj4wHnfGlgGlAeaApuAULe/1zkeiynA3c77ckC1snpu4B0UaAtQId95cUdZOj+AS4EOwMp804rtfAAWOcuKs26vImNy+6CUthcwC++4teuAC5xpFwDrnPdvAkPyLb/OmT8EeDPf9FOWKy0vvAX7vwOuAD53TrY9QJgzvysw23k/G+jqvA9zlhPgaeDpfNvMW640vYCqTlKT06aX1XMjdzS4Gs6/9+fANWXt/ACiTkvyxXI+OPPW5pt+ynIFvay55iw4f07GAguBuqq6w5m1E6jrvC9o2EOfhkMsBf4DPAl4nM81gQOqmu18zv+98r6zMz/TWT5YjkVTIAN4x2m+ektEKlJGzw1V3Q78C0gFduD9906m7J4fuYrrfGjgvD99eqEsyftIRCoBHwGPqOrB/PPU+2s16PuiikhfYLeqJrsdS4AIw/un+ThVjQWy8P45nqesnBsATlvzALy//OoDFYFrXQ0qwLhxPliS94GIhONN8Imq+rEzeZeIXODMvwDY7UwvaNjDEhkO0c+6A/1FJAWYjrfJ5jWgmojkjk2Q/3vlfWdnflVgL8FxLMB7JZWmqgudzzPwJv2yeG4AXAVsUdUMVT0JfIz3nCmr50eu4joftnPq+KY+HRdL8kVw7l5PAtao6iv5Zn0K5N71vh1vW33u9GHOnfN4INP5U2020FNEqjtXPD2daaWGqj6tqg1VNQrvjbLvVXUoMAcY5Cx2+rHIPUaDnOXVmT7Y6V3RFGiO94ZSqaKqO4FtItLSmXQlsJoyeG44UoF4EYl0/t/kHo8yeX7kUyzngzPvoIjEO8d3WL5tFcztmxSB/gJ64P3zajmw1Hn1xtt2+B2wAfgWqOEsL8AYvD0CVgBx+bb1R2Cj87rT7e92nsflMn7rXXMh3v+EG4EPgfLO9Ajn80Zn/oX51h/pHKN1+NBDIFBfQHsgyTk/PsHbG6LMnhvAC8BaYCXwLt4eMmXm/ACm4b0fcRLvX3p3Fef5AMQ5x3YTMJrTbvqf6WVlDYwxJohZc40xxgQxS/LGGBPELMkbY0wQsyRvjDFBzJK8McYEMUvypliJyGG3YygOIjJXRJLyfY4Tkbk+rDdZRAYVtVy+5Z8XkcfPYvk7RGS08/4+ERlWyLKXiUg3X7dtglNY0YsYE9ycB0tEVT2nzaojIr1U9Ss34iqKqo4vYpHLgMPAL/6PxgQqu5I3fici7UVkgVMze2a+etpzReQfIrJIRNaLyCXO9EgR+a94a/jPdGqNxznzDufb7iARmey8ry0iH4nIYufV3Zl+ypWyeOucRzmvdSIyFe/DJfkfI8/1T7wP5RT23URERjvb+haok29eRxH5QUSSRWR27qPthWzrHif2Zc53iSxi+bzvJiIPOcdruYhMF28xvfuAR0VkqYhcUtAxMsHNkrwpCVOBP6lqDN4n+57LNy9MVTsDj+SbPhzYr6qtgT8DHX3Yx2vAq6raCbgBeMuHdZoDY1W1japuPcP8+cAJEbm8kG0MBFrirYE+DOgGefWO3gAGqWpH4G1gVBHxfKyqnVS1HbAG79OSvnoKiHWO8X2qmoK3dvurqtpeVX/i3I6RKeWsucb4lYhUBaqp6g/OpCl4H2XPlVvwLRlvHW7wlpJ4DUBVV4rIch92dRXQWn4bKKeKeCuHFmarqi4oYpmXgGeBPxUw/1JgmqrmAOki8r0zvSXQFvifE1Mo3sfdC9NWRF7CO/BIJc6ufs1yIFFEPsFbXuFMzniMVDUo7qOYM7Mkb9x23PmZg2/nY/46HBH53ocA8ap6LP/CIpLNqX+x5l8nq8idqX7vJN54H2I7ZdfAKlXtehbrTAauU9VlInIH3jZ1X/XB+wunHzBSRKLPsMwZj5EJbtZcY/xKVTOB/bnt7cBtwA+FrALwM3ATgIi0BvInrF0icrGIhOBtKsn1DfBg7gcRae+8TcFb/hfxjqHZ9By+xkt4B0o5kx+Bm8U77u0FQG7Tzjqgtoh0dfYdLiJtithPZWCH09Qz1NfgnGPRSFXn4P2LoyrevwQOOdvMVdAxMkHMruRNcYsUkfyj17yCt7zqeOdG4mbgziK2MRaYIiKr8VY0XIV31CDwtj1/jndEpiS8yQzgIWCM07QThjf53od3HIBhIrIK74he68/2C6nqlyKSUcDsmXjr6q/GW2p3vrPOCacr5etOk1UY3lG1VhWyqz87MWY4PysXsmx+ocB7zn4EeF1VD4jIZ8AMERmAN7kXdIxMELMqlCbgiEgoEK6qx0SkGd7yrC1V9YTLoRlT6tiVvAlEkcAcp9lCgOGW4I05N3Ylb4wxQcxuvBpjTBCzJG+MMUHMkrwxxgQxS/LGGBPELMkbY0wQ+/9gOq/Q51HCfwAAAABJRU5ErkJggg==\n"},"metadata":{"needs_background":"light"}}]},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"## 3. Preuve de la correction\n\n### 3.1 Tri par sélection\n\n**L'invariant de boucle** est :  \n> \"A la fin de l'itération $i$, les $i+1$ premiers éléments du tableau sont triés par ordre croissant et le reste du tableau (non trié) ne contient que des valeurs supérieures ou égales à celles déjà triées\".\n\n**Q6. Montrer que cette propriété est vraie pour $i=0$, puis, que si elle est vraie pour $i=k$ alors elle est encore vraie pour $i=k+1$.**"},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"**Réponse :**\n\n*A compléter ...*"},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"### 3.2 Tri par insertion\n\n**L'invariant de boucle** est :  \n> \"A la fin de l'itération $i$, les $i+2$ premiers éléments du tableau sont triés par ordre croissant\".\n\n**Q7. Montrer que cette propriété est vraie pour $i=0$, puis, que si elle est vraie pour $i=k$ alors elle est encore vraie pour $i=k+1$.**"},{"metadata":{"slideshow":{"slide_type":"subslide"}},"cell_type":"markdown","source":"**Réponse :** \n\n*A compléter ...*"}],"metadata":{"kernelspec":{"name":"python3","display_name":"Python 3 (ipykernel)","language":"python"},"language_info":{"name":"python","version":"3.7.12","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"},"celltoolbar":"none"},"nbformat":4,"nbformat_minor":4}