TrisSolutions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithmes de tri (solutions)\n",
    "\n",
    "Il existe un grand nombre d'algorithmes de tri, nous allons en voir deux et en comparer la vitesse d'exécution.\n",
    "\n",
    "# Tri par sélection\n",
    "\n",
    "Aussi appelé le tri à bulles, son principe est simple, on cherche le minimum de la liste que l'ont fait remmonter en première place et on recommence avec le reste de la liste.\n",
    "\n",
    "Autrement dit, le principe du tri par sélection d'une liste `T= (T[1],T[2],...,T[n])` est le suivant :\n",
    "\n",
    "Pour chaque entier $j$ ($1\\leqslant j \\leqslant n−1$)\n",
    "\n",
    "- parcourir les éléments $T[j],T[j+ 1], . . .,T[n]$, retenir l'indice `k` du plus petit.\n",
    "- placer au rang `j` le plus petit des éléments `T[j],T[j+ 1], . . .,T[n]` (en  ́echangeant `T[j]` et `T[k]`)\n",
    "\n",
    "En voici une illustration, la partie noire est la partie non triée dans lequelle on cherche le minimum. Une fois trouvé, il est placé au début de la liste par échange.\n",
    "\n",
    "<IMG SRC=\"triselection.png\">\n",
    "    \n",
    "## Exercice  : Programmer le tri par sélection\n",
    "\n",
    "**Entrée :** `T` liste de nombres.\n",
    "\n",
    "**Sortie :** liste `T` triée\n",
    "\n",
    "**Traitement :**\n",
    "\n",
    "**Pour** j allant de 1 à n−1<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;     indiceMin :=j<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;     **Pour** k allant de j+ 1 à n<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;           **si** T[k]<T[j] **alors**<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;                indiceMin:=k<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;           **finSi**<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;     **finPour**<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;     Echange de T[j] et T[indiceMin] **si** j $\\not=$ indiceMin<br>\n",
    "**finPour**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[9, 12, 31, 32, 46, 65, 81, 82]\n"
     ]
    }
   ],
   "source": [
    "# programmer le tri ici\n",
    "\n",
    "def selection(T,debut):\n",
    "    indiceDuMin = debut\n",
    "    for k in range(debut+1,len(T)) :\n",
    "        if T[k] < T[indiceDuMin] :\n",
    "            indiceDuMin = k\n",
    "    if indiceDuMin != debut:\n",
    "        (T[debut],T[indiceDuMin]) = (T[indiceDuMin],T[debut]) # utilisation des tuples\n",
    "        \n",
    "def triSelection(T):\n",
    "    for j in range(0,len(T)-1):\n",
    "        selection(T,j)\n",
    "\n",
    "\n",
    "# trier cette liste à l'aide de cet algorithme\n",
    "\n",
    "L = [65, 31, 9, 32, 81, 82, 46, 12]\n",
    "\n",
    "triSelection(L)\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tri par fusion\n",
    "\n",
    "## Avant de commencer\n",
    "\n",
    "Manipulons les listes avec le slicing.\n",
    "\n",
    "Le terme anglais de slice est associé à l'idée de découpage (*une part de gâteau ou de pizza*). En programmation, et en Python en particulier, un slice permet le découpage de structures de données séquentielles, typiquement les chaînes de caractères ou les listes.\n",
    "\n",
    "Les slices sont des expressions du langage Python qui vous permettent en une ligne de code d'extraire des éléments d'une liste ou d'une chaîne. \n",
    "\n",
    "Exemple : Vous avez une variable `date` qui référence une date sous le format **jj/mm/aaaa** et vous voulez extraire juste le mois de cette date. Avec un slice, vous l'obtiendrez juste avec ceci : `date[3:5]`.\n",
    "\n",
    "Mais bien évidemment, comme d'habitude, quelques pièges...\n",
    "\n",
    "## Slices avec deux indices\n",
    "\n",
    "Soit `S` une séquence, par exemple une chaîne ou une liste. Une expression de la forme `S[4:16]` est un slice dans sa syntaxe de base. Cette syntaxe utilise deux indices, ici les indices 4 (indice de début du slice) et 16 (indice de fin du slice).\n",
    "\n",
    "Voici un exemple typique de slice de base :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "EFGHIJKLMNOP\n"
     ]
    }
   ],
   "source": [
    "alpha = \"ABCDEFGHIJKLMNOPQRSTUVWXYZ\"\n",
    "print(alpha[4:16])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`alpha[4:16]` est un slice et désigne la chaîne extraite de la chaîne `alpha` dont les éléments sont situés :\n",
    "\n",
    "- à droite de l'élément d'indice 4,\n",
    "- strictement à gauche de l'élément d'indice 16, autrement dit jusqu'à l'indice 15 inclus\n",
    "\n",
    "ce qui graphiquement donne :\n",
    "\n",
    "<IMG SRC=\"trislice.png\">\n",
    "    \n",
    "Plus généralement,\n",
    "\n",
    "Si $i$ et $j$ sont des indices positifs, la syntaxe $S[i:j]$ désigne la séquence, de même nature que $S$, formée des éléments $S[k]$ où $k$ vérifie $i\\leqslant k\\leqslant j$.\n",
    "\n",
    "Noter l'intervalle entier semi-fermé : le terme d'indice de droite n'est jamais inclus dans le slice obtenu.\n",
    "\n",
    "Un slice peut être vide :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "alpha = \"ABCDEFGHIJKLMNOPQRSTUVWXYZ\"\n",
    "s = alpha[10:8]\n",
    "print(len(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "un slice `t` est construit à partir d'une séquence `s` alors `t` est de même type que `s`, autrement dit si `s` est une chaîne alors `t` est aussi une chaîne, si `s` est une liste alors `t` est une liste, etc.\n",
    "\n",
    "Voici justement un exemple de slice de base construit sur une liste :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[9, 32, 81, 82]\n"
     ]
    }
   ],
   "source": [
    "L = [65, 31, 9, 32, 81, 82, 46, 12]\n",
    "print(L[2:6])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Application : segmenter un numéro de téléphone\n",
    "\n",
    "Ecrire les commandes pour segmenter une chaîne de caractères à intervalles réguliers par un séparateur donné ; typiquement, pour un numéro de téléphone, 0942371804 devient 09-42-37-18-04."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "09-42-37-18-04\n"
     ]
    }
   ],
   "source": [
    "tel=\"0942371804\"\n",
    "\n",
    "# écrire le code ici\n",
    "\n",
    "NoTel = tel[0:2] + '-' + tel[2:4] + '-' + tel[4:6] + '-' + tel[6:8] + '-' + tel[8:10]\n",
    "print(NoTel)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Omission d'indice\n",
    "\n",
    "quand un slice se réfère à une des deux extrémités de la séquence, un raccourci syntaxique permet d'omettre l'indice de début ou de fin. Par exemple, le slice `s[:j]` est synonyme de `s[0:j]`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ABCDE\n",
      "FGHIJKLMNOPQRSTUVWXYZ\n"
     ]
    }
   ],
   "source": [
    "alpha = \"ABCDEFGHIJKLMNOPQRSTUVWXYZ\"\n",
    "\n",
    "# Les 5 premiers\n",
    "print(alpha[:5])\n",
    "\n",
    "# Tous sauf les 5 premiers\n",
    "print(alpha[5:])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Application : couper une liste en deux\n",
    "\n",
    "Dans le cadre de code suivant, couper la liste `L` en deux listes `L1` et `L2` de tailles égales (ou presque). Votre code doit fonctionner quelque soit la taille de la liste `L` donnée."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[43, 35, 72, 51, 9, 94, 84, 44, 23, 74, 26, 73, 99, 44, 62, 50, 5, 75, 70, 81, 83, 6, 18, 29, 12, 14, 81, 15, 23, 25, 11, 77, 11, 32, 23, 19, 29, 30, 10]\n",
      "[43, 35, 72, 51, 9, 94, 84, 44, 23, 74, 26, 73, 99, 44, 62, 50, 5, 75, 70]\n",
      "[81, 83, 6, 18, 29, 12, 14, 81, 15, 23, 25, 11, 77, 11, 32, 23, 19, 29, 30, 10]\n"
     ]
    }
   ],
   "source": [
    "from random import randint\n",
    "L = [randint(1,100) for k in range(randint(10,50))]\n",
    "print(L)\n",
    "\n",
    "# insérer votre code ici\n",
    "DemiTaille = len(L)//2\n",
    "L1 = L[:DemiTaille]\n",
    "L2 = L[DemiTaille:]\n",
    "print(L1)\n",
    "print(L2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tri par fusion enfin...\n",
    "\n",
    "Voici le principe en application\n",
    "\n",
    "\n",
    "<video width=\"640\" height=\"480\" controls src=\"Mergesort.mp4\" />\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On pose devant soi deux paquets de cartes triées, la plus petite carte au-dessus. Pour fusionner les deux paquets en un seul paquet trié : \n",
    "\n",
    "- on prend la plus petite carte que l'on voit sur les deux tas\n",
    "- puis on prend la plus petite carte que l’on voit sur les deux tas et on la glisse sur la carte que l’on a déjà dans la main \n",
    "- et on recommence au point précédent...\n",
    "\n",
    "### Exercice\n",
    "\n",
    "Soit la fonction `fusion(T1,T2)` qui prend en paramètres deux listes triées `T1` et `T2` et renvoyant la fusion triées des deux listes.\n",
    "\n",
    "En utilisant le slicing, comment écrire l'appel à fusion avec la liste `T1` privée de son premier terme et la liste `T2` entière ?\n",
    "\n",
    "**Solution :** `fusion(T1[1:],T2)`\n",
    "\n",
    "En utilisant le slicing, comment écrire l'appel à fusion avec la liste `T2` privée de son premier terme et la liste `T1` entière ?\n",
    "\n",
    "**Solution :** `fusion(T1,T2[1:])`\n",
    "\n",
    "Ecrire une fonction prenant en paramètres deux listes triées `T1` et `T2` et renvoyant la fusion des deux listes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 5, 7, 8, 9, 10]\n"
     ]
    }
   ],
   "source": [
    "# si T1 est vide, retourner T2\n",
    "# si T2 est vide, retourner T1\n",
    "# sinon retourner une liste contenant la plus petite des premières valeurs des listes et la fusion de ce qui reste. \n",
    "# On utilisera le slicing et on appelera fusion de manière récursive.\n",
    "    \n",
    "def fusion(T1,T2):\n",
    "    if T1 == [] : return T2\n",
    "    if T2 == [] : return T1\n",
    "    if T1[0]<T2[0]:\n",
    "        return [T1[0]]+fusion(T1[1:],T2)\n",
    "    else:\n",
    "        return [T2[0]]+fusion(T1,T2[1:])\n",
    "    \n",
    "    \n",
    "# fusionner ces deux listes\n",
    "\n",
    "L1 = [1,3,5,7,9]\n",
    "L2= [2,8,10]\n",
    "print(fusion(L1,L2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Principe du tri fusion d'une liste `T` :\n",
    "\n",
    "- Scinder la liste en deux listes `T1`, `T2` que l’on trie par tri fusion si elles ne le sont pas\n",
    "- fusionner `T1` et `T2`.\n",
    "\n",
    "Ecrire un programme triant une liste par ce principe."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[9, 12, 31, 32, 46, 65, 81, 82]\n"
     ]
    }
   ],
   "source": [
    "# Si la liste est vide ou ne contient qu'un seul élément, la retourner\n",
    "# sinon, fusionner le tri des deux moitiés de la liste T\n",
    "    \n",
    "def trifusion(T):\n",
    "    if len(T)<=1: return T\n",
    "    coupe=len(T)//2\n",
    "    return fusion(trifusion(T[0:coupe]),trifusion(T[coupe:]))   \n",
    "\n",
    "\n",
    "# trier cette liste à l'aide de cet algorithme\n",
    "\n",
    "L = [65, 31, 9, 32, 81, 82, 46, 12]\n",
    "print(trifusion(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Comparaison de la complexité de deux algorithmes de tri\n",
    "\n",
    "Objectif : comparaison les vitesses d’exécution des deux algorithmes de tri au programme de la partie informatique du module informatique du bac STAV.\n",
    "\n",
    "On souhaite représenter les vitesses d’exécution des deux algorithmes en fonction de la taille du tableau comme sur le graphique final ci-dessous\n",
    "\n",
    "<IMG SRC=\"tricomp.png\">\n",
    "\n",
    "## Exercice\n",
    "\n",
    "1.\tCréer une liste nommée « tailles » contenant tous les multiples de 100 compris entre 100 et 1400 inclus.\n",
    "\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a. Par extension\n",
    "\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b. Par ajouts successifs\n",
    "\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c. Par compréhension\n",
    "\n",
    "2.\tCréer une liste nommée « tableau » de 2000 nombres aléatoires choisis de manière uniforme dans l’intervalle $[0 ;1[$\n",
    "\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a. Par ajouts successifs\n",
    "\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b. Par compréhension\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution question 1.a\n",
    "\n",
    "tailles = [100,200,300,400,500,600,700,800,900,1000,1100,1200,1300,1400]\n",
    "\n",
    "# Solution question 1.b\n",
    "\n",
    "tailles = [ ]\n",
    "for k in range(1,15):\n",
    "    tailles = tailles + [100*k]\n",
    "\n",
    "# Autre solution question 1.b\n",
    "\n",
    "tailles = [ ]\n",
    "for k in range(1,15):\n",
    "    tailles.append(100*k)\n",
    "\n",
    "# Solution question 1.c\n",
    "\n",
    "tailles=[100*k for k in range(1,15)]\n",
    "\n",
    "# Pour les deux questions a et b de la question 2, il ne faut pas oublier d'inclure random\n",
    "\n",
    "from random import random\n",
    "\n",
    "# Solution question 2.a\n",
    "\n",
    "tableau = []\n",
    "for k in range(2000):\n",
    "    tableau.append(random())\n",
    "\n",
    "# Solution question 2.b\n",
    "\n",
    "tableau = [random() for k in range(2000)] "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## Chronométrage\n",
    "\n",
    "Pour chronométrer des actions en Python, grâce à la bibliothèque `time`, on récupère l'heure de départ et l'heure de fin des actions et on en fait la différence de cette manière :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "début = time.perf_counter()\n",
    "    # Actions à chronométrer\n",
    "fin = time.perf_counter()\n",
    "durée = fin - début"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice\n",
    "\n",
    "Ecrire un programme en Python permettant de chronométrer le tri par sélection des 100 premières valeurs du tableau `tableau` de l'exercice précédent.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0006526789998133609\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "début = time.perf_counter()\n",
    "triSelection(tableau[0:99])\n",
    "fin = time.perf_counter()\n",
    "durée = fin - début\n",
    "print(durée)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice\n",
    "\n",
    "1. A l’aide de la liste « tailles », écrire un programme en Python permettant de chronométrer le tri par sélection des 100 premières valeurs du tableau « tableau » et ranger les durées dans une liste nommé « yS ».\n",
    "3.\tFaire la même chose avec le tri par fusion et ranger les résultats dans une liste nommé « yF ».\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "yS=[]   \n",
    "for k in tailles:\n",
    "    début = time.perf_counter()\n",
    "    triSelection(tableau[0:k-1])\n",
    "    fin = time.perf_counter()\n",
    "    yS.append(fin-début)\n",
    "\n",
    "yF=[]\n",
    "for k in tailles:\n",
    "    début = time.perf_counter()\n",
    "    trifusion(tableau[0:k-1])\n",
    "    fin = time.perf_counter()\n",
    "    yF.append(fin-début)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice\n",
    "\n",
    "Afficher le graphique à l’aide du code suivant :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX0AAAEXCAYAAABBFpRtAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAIABJREFUeJzt3X+cXFV9//HXOwkEFhEkRAvkx4LBH0Et4grYovIQfwSrpLZQgvtVUNqIlq+21B9gtEWUWqwV9SuKqSCIi4D4oylqoxXxt5GNgBIxdQn5sQRhIQGEVBH4fP84Z8jdYWZnZnd2Z2bn/Xw89rFzzz1z75lz7/3MnXPvPUcRgZmZdYcZrS6AmZlNHQd9M7Mu4qBvZtZFHPTNzLqIg76ZWRdx0Dcz6yIO+nWQtEDSA5Jmtmj9T5d0g6TfSnrrBJZzoaT3NrNs1lkkvVPS5yTNyNO9kkLSrCavp6XHTD1qfXZJZ0v6/FSXa7J1fdCXtFHSS8fKExGbI+IJEfHIVJWrzDuB6yJiz4j4+HgXEhGnRcT7m1guyzohQEg6FjgMeENEPNrkZY86jtrgmLEquj7o19LsM6Aa61LpDKzMQmDdVJWjnbTzmWKrjLGfjCkivhERyxyIu1xEdO0fcBnwKPC/wAOkM+peIIBTgc3A9wpps6osZyNwFvBLYDvwWWC3PO9JwDXASJ53DTCv8N7rgHOBH+ZyLCpb9rXAI8Dvchmflt/z14U8pwA/yK8FnA/cBdwH/Bx4Vp53CfCBwvv+BhgCtgGrgP0L8wI4Dfh1LvcFgKp8/hnAmcCtwD3AVcA+eV6p7k7O9Xk3sGKMbXIJ8Cng68CDwEuBvYDP5TrcBLwHmJHznw18vvD+UdsKODBvw98C/50/RzH/kcCPgHuBm4Cjxyjb/sCXcjluA96a05cADwF/yNvopqneT3KedwG358+6Hjimge1Tqq+9gIuAO/KyPgDMLNtnbsnr+CXpl8NYx9GsQt2tIu1rQ8DfFJZ5di7T5/Jy1wF9Y2yHZwDfystaD/xV2f5zAfC1vKw1wFOrLKdUxuXA1vyZ/6GsXHXtK3nbvrTae9vpr+UFaPVfhY1V2hE+B+wB7F6+A1dZxs3AfGCffGB+IM+bA/wl0APsCXwR+GrhvdeRguEhwCxglwrLv47RQb58+hR2Bv1XAGuBvUlfAM8E9svzLimU6yWkAHwYMBv4f8D3CssMUuDZG1hACkZLqnz+vwN+AszLy/o08IWy+vz3XJd/DPweeGaVZV1C+rL6U1Kw2i1vi//I9dcL/A9was5ffmCO2lbAj4EPA7sCRwH3l/IDB5CC4Cvzul6Wp+dWKNeMXK//mJd1ELABeEWlckz1fgI8HdhC/uLO9fDUBrZPqb6+mufvATwZ+CnwpjzvBNIXwfNJ+9YiYGGN46i03O8Cn8zb81DS/nRMoe5+l7fDTOCDwE+q1OEe+XO+IdfDYaT9+JDC/rMNODzPHwCuqLKsUhm/kJf77Fyul5ZvU2rsKxU+f839oWUxr9UFaPXfGDvrQdV24CrLOK0w/Urg1ip5DwW2F6avA86pUcbrqD/ov4QUFI8knw0X8l3CziBzEfChwrwnkM5Ue/N0AEcV5l8FnFmlfLeUDuA8vV9e1qxC3RXPWn8KLKuyrEuAzxWmZ5K+JBYX0t5EusbxuIOruK1IX1YPAz2F+Z8vHMjvAi4rW/9q4OQK5ToC2FyWdhbw2UrlmOr9hBSA7yL9Mir/Qqhn+8wCnpLrevdC3pOA7xTq5m0NHkezSF9yjwB7FuZ/ELikUHf/XZi3GPjfKus5Efh+WdqngX8q7D+fKavjX1VZVqmMzyikfQi4qHyb1tpXKnz+mvtDq/6mrL26A22ZQP5NpJ+zSOohNbcsIf2EB9hT0szY2bba6LqqiohrJX2C9BN3gaSvAG+PiPvLsu4P/Kzwvgck3UM6o9mYk39TyL+D9MVQyULgK5KKFwcfIQWRknqXBaPrY1/SmfWmQtqmXM5a9ge2RcSOsmXPL5T7BEmvLszfBfhOhWUtBPaXdG8hbSbw/TrKUTQp+0lEDEn6O1KwOUTSauCMiNhKfduHnG8X4A5JpbQZhfXOJzURNaq0HX5bSNsE9BWmy/eP3STNioiHK5TxiLLtMIvUxFRtWWPta/D4bfLsCnka2Vfami/kpm/6RtKrmV94vYDURgjwD6Sf3kdExBOBF+V0FfI3uq4HSc0AJX9UnBkRH4+I55GaAp4GvKPCMkrBIBVG2oPUxHB7g2WBdNAcGxF7F/52i4jxLAtG18fdpLPShYW0BYVyjlUXdwD75IBaUtxOW0hnb8Vy7xER/1KhTFuA28ry7hkRr6xQ5rFM2n4SEZdHxFGkugrgvELZ69k+W0hn+vsW8j0xIg4pzH9qtdWPUbStpO2wZyGtuA0bsQX4btlneUJEvHkcyyqptk3K1zvWvjLmMdlOHPThTlL77ET9raR5kvYB3g1cmdP3JF3gujfP+6cmrOtG4C8k9UhaRLroDICk50s6QtIupB3xd6SzunKXA2+QdKik2cA/A2siYuM4ynMhcK6khbkMcyUtHcdyHief5V6Vl79nXscZpGYaSHXxonxf+F6kJpfSezcBg8DZknaV9AKgeKb2eeDVkl4haaak3SQdLWlehaL8FLhf0rsk7Z7zP0vS8/P8O4HeOu6qmZT9JD/L8ZK8LX+Xl1Xa7nVtn4i4A/gm8G+SnihphqSnSnpxzvIZ4O2SnpfvIFpUWiZjHEcRsYV0AfSDuY6fQ9pnBxr5jNk1wNMkvU7SLvnv+ZKeOY5llbw3H0uHkK4VXFkhT6195UZgWS5PH3D8BMozqRz0U9vieyTdK+ntE1jO5aQDZkP++0BO/yjpAubdpItp/zWBdZScT7pb5E7gUkYfPE8kXTTdTvqpeg/pQuYoEfFt4L2ku1HuIJ3BLRtneT5GujPjm5J+S/qcR4xzWZX8X9IX2AbgB6S6vhggIr5FOkh/TrrQek3Ze/uBF5Dq4QM57+/ze7cAS0nBd4R0NvcOKhwX+cvn1aS29ttI2/MzpLtdIF14BbhH0s/K318wWfvJbOBf8vt/Q7oI++48r5Ht83pSc1rpDqOrSdcAiIgvku4gupx0Z8xXSRekofZxdBKpDX0r8BVSG/y3GvyM5Cail5P21a35s56XP/94fZd0R9G3gQ9HxDcrrLfWvvJe0jG0HXgfqY7akvJFB5sASRtJF1b/u9VlsbFJupJ0Ya8Zv7gaXfdGvJ9Yi/lM36a1/NP/qbmpYgnpbO2rrS6XWav47h2b7v4I+DLpIvUw8OaIuKG1RTJrHTfvmJl1ETfvmJl1kY4L+pK+IenkVpejXrnr1kWTtOzdJf1I0itr5x7X8tu+K+ZcB/8p6T5JX6z9jqat94WS1k/Rumr2BFvlfUdLGp6MMlVY16j6KJZZTeyBVNIlkj5QO+eE1nGKpB9M5joqrHNUl9eTqeOCfkQcGxGXQms2zkTkHfaUJi7y06RbzL4+0QVVqsvojK6Yjyc9WTonIk6YrJWUf3lHxPcj4umTtb5WazRQT/f6mEyaxC6vK/GF3A4WEa9vdRnawELgfyo8rm/WESLiG8A3pmp9bXemL+lMSVeXpX1M0sfz6+sk/XV+Au9C4AVKI/Tcm+fPlvRhSZsl3ZmbKHbP8/aVdE1+gGSbpO9r5whC75J0u9LoVOslHZPTZ+Qy3SrpHklX5Scmq5X/HZLukLRV0htrfNY3SrpF0nZJqwtPTP6JpLslzc/Tf5zL/Iw8vb+kL0kakXSbCqNp5acF353L+1tJayXNV4VRguqoy1E/pSX9jaShXHerJO1fmBeSTpP06/x5LpBU7EKg+Lmr1mmhnCfnbXi3pBVVlvM+Uq+XJ+Zyn5qX/R5JmyTdlX8y71XPsseou+/lLDfl9ZyosqYTSc/M9XmvpHWSjivMuyTXx9fyctdIqtadAUpPm27KdbOibF5D+2PZe88sfLZfSnpNlXxLSA8hler1ppz+hry//lbSBklvKryn7qYkSUcqNUveK+kmSUePkfe5kn6W13klqZfO4vxXSboxL+tHSk/7luZVPKYrrGNO3p/vl/RTyrqaUDoer1dqQrxe0p8U5l0n6f2SfpjX801J++Z5tfa3MbflWPWk9Mt8Q17nbZL6a9d81uoe38r/SGduO4An5umZpCdGj8zT15F7mKTQu2Th/R8lPX24D+nR9v8EPhg7e/a7kNRR0i7AC0l9m4yrW9oKZV9Cekr2WaSuWi8n9UlSqe/zPyc9BfhM0i+u9wA/Ksw/l9SX/u6kp01Pz+m1uvh9B/CL/JlE6sp4DhV6Cq2jLi+h/btiPpvRvWy+MdfrQaSOtr5M7h2x1rKr1V3h8y0qrOdoYDi/3iWv8915m7yE9MTq0wv1WG93v4tJfdK/KNfNR0g9hb60Vt1VWNZjZczTJ5A6P5tB6q3yQXK327XqNaf9GSkgCngx6Tg9rMq6NjKOLorL1lfqaO/vcx0fT+qHqbRPHkbqWfQIUpw4Oa93NmMc0xXWcwWpq489SMfu7ezstXYf0lO2r8vb7qQ8XdovriN1Qvc00j51HfAvde5vYx0HVespl/N+du5f+5G7lq4rxk52EB/PH+lR+9fn1y+j0P0sYwSqvDM+WNy4pEfwb8uvzyH1y14+UMm4uqWtUO6LSxs8Tz+N6kH/G+Q+4fP0DNJBtLAQSNaSgtB/sfP22lpd/K4HllZYX2kHHG/Qb9eumM9mdND/NvCWwvTT6112tborfL5qQf+FpO4AZhTmfwE4u1CP9Xb3+48UvhBIB/hD7AygjeyPj5WxyrpuHOPzjqrXKnm+Su5quXxdVA/6jXRn/SJSVwsqpP2osE9+Cnh/2XvWk76Qqh7TZfln5vordq/8z+wM+q8Dflr2nh8DpxSOofcU5r0F+K+yY67a/jbWcVC1nvI+cS9p/IXdq322an9t17yTXU76RgV4LfX3YzGX1NPd2vyT6F5SwJyb5/8r6Yzsm/mn0ZmQuqUlfeueDdwl6QrtbLpYSOqWtrS8W6jcLS2ks6jyblqrWQh8rLDcbaQvrQNymf5AChbPAv4t8lan0MVv4b3vLpRnvN3f1rI/hc8TEQ+QzjyKXRw32hXzWHXaaPe4FcuZX5f6iq+17Il0HbwlRl+EK+/+ud7PM2ofiogHSfVc0sj+OIqk1xeaQu4l7Vv71npf4f3HSvqJUvPevaQvr7rfXyj/CWX771Hk/n3K7A/cXtj3YfS2XQj8Q9my5pPO7sc6povmkvaPasdt+f5Umt/Itq02f6xtWbWe8j5xImlkuztys+EzKny2ito16H8RKPVg9xqqB/0om76b1LvgIbGz+9O9IuIJkDprioh/iIiDSJ1nnVFq54uJd0sLqRmqvJvWaraQRiQqLnf3iPgRgKQDSD0tfpbU6+Hswvtui+pd/Fbr/vbB/L9a96/ldVmunbtirlpOdg6kcmed5ara1l5jnfM1+na78XYdPGofUuoWek5ZGRuuO6XrRf8OnE5qmtibNIpXxesulO0Pef/7Eqnzvqfk9399jPdX00h31ncAB0ijrg0Vj6ktwLlly+qJiC/AmMd00Qhp/6h23JbvT6X5zdhXx9qWY9ZTRKyOiJeRvix/Rdq2dWnLoB8RI6SfTZ8lBbhbqmS9E5gnadf8vkdJH/58SU+GFDwlvSK/fpVSd7AitYk9AjyiJnRLm10FnCJpcT5Y/2mMj3khcJZSd65I2kvSCfm1SGf5F5G6oL0DKN06WauL388A75d0sJLnSJqT6/R24P/k97yR0QFuVF1W0BFdMZOaVf5e0oGSnpDLeWXUd3dPxbrL88bqgnsN6Uv1nUpd6x5NOqm4Yhzlvxp4laSj8rY4h9HH6Xjrbg9S4BvJ73sD6Uy/mvKuoncltTuPAA8r3Wb48vo/1mMa6c76x6SA/FZJsyT9Bem6SMm/A6cpdSUuSXtI+jOlLrjHOqYfE6n31C+Tut/ukbSY1IRS8nVSV86vzWU4kXTdpbw31/EYa1tWrSdJT5F0XD7x+j3pGlDdg923ZdDPLie1x43VtHMtaRDl30i6O6e9i9SE8xNJ95MGwy7dP3xwnn6AtEN9MiKuo0nd0ka69eqjuVxD+X9FEfEV0pnHFbmcNwPH5tlvJf3Ee2/+afsGUsB9YdTu4vcjpC+fb5K+2C4iXUSCNKj1O0jNBYeQ2kfHqstieTulK+aLSaMofY9UP78jdc1cj7Hq7mzg0vxT+6+Kb4qIh4DjSNvvbtJYsK+PiF81WviIWAf8LWm/v4N00bB4V8y46i4ifgn8G2m/v5M0OtQPx3jLqK6iI3Vp/FZS/WwnNbuuqv+TPVaORrqzfgj4C9L1pu2kJo0vF+YPkvbpT+T5QzkvjH1Mlzud1OTyG9LJ1mcL67gHeBVpkJt7SIO+vyoiHneMjEPVbVmjnmbk8mwlNQu/mHQtoS7ue8fMrIu085m+mZk1mYO+mVkXcdA3M+siDvpmZl2k7Tpc23fffaO3t7fVxTAz6yhr1669OyLm1srXdkG/t7eXwcHBVhfDzKyjSBqrB4DHuHnHzKyLOOibmXURB30zsy7ioG9m1kXqCvqSliiNPDOk3B1x2fzZkq7M89dI6s3pu0i6VNIvlEbcOau5xTczs0bUDPqSZgIXkDqTWgyclHuiKzoV2B4Ri4Dz2dmF6QnA7Ih4NvA84E2lLwQzM0sGBqC3F2bMSP8HBiZvXfWc6R8ODEXEhtzr3RWk3t+KlgKX5tdXA8fk7oED2ENpXNbdSSMA3d+UkpuZTQMDA7B8OWzaBBHp//Llkxf46wn6BzB6VJlhRo8aMypP7rf8PtLAD1eT+hm/A9gMfDgitk2wzGZm08aKFbBjx+i0HTtS+mSoJ+hXGhmnvD/mankOJ3Xuvz9wIGlos8cNRCFpuaRBSYMjIyN1FMnMbHrYvLmx9ImqJ+gPM3oosXmkzvsr5slNOXuROvd/LWmQ4D9ExF2kQRv6ylcQESsjoi8i+ubOrfkUsZnZtLGgyqCq1dInqp6gfz1wcB5+blfSaEnlI+asYucQY8cD1+YRnzYDLykNZQYcSRrP0czMgHPPhZ6e0Wk9PSl9MtQM+rmN/nRgNWm09qsiYp2kcyQdl7NdBMyRNAScAZRu67yANAzZzaQvj89GxM+b/BnMzDpWfz+sXAkLF4KU/q9cmdInQ9sNl9jX1xfucM3MrDGS1kbE45rPy/mJXDOzLuKgb2bWRRz0zcy6iIO+mVkXcdA3M+siDvpmZl3EQd/MrIs46JuZdREHfTOzLuKgb2bWRRz0zcy6iIO+mVkXcdA3M+siDvpmZl3EQd/MrIs46JuZdZG6gr6kJZLWSxqSdGaF+bMlXZnnr5HUm9P7Jd1Y+HtU0qHN/QhmZlavmkFf0kzSsIfHAouBkyQtLst2KrA9IhYB5wPnAUTEQEQcGhGHAq8DNkbEjc38AGZmVr96zvQPB4YiYkNEPARcASwty7MUuDS/vho4RpLK8pwEfGEihTUzs4mpJ+gfAGwpTA/ntIp58kDq9wFzyvKciIO+mVlL1RP0y8/YAcpHUx8zj6QjgB0RcXPFFUjLJQ1KGhwZGamjSGZmNh71BP1hYH5heh6wtVoeSbOAvYBthfnLGOMsPyJWRkRfRPTNnTu3nnKbmdk41BP0rwcOlnSgpF1JAXxVWZ5VwMn59fHAtRERAJJmACeQrgWYmVkL1Qz6uY3+dGA1cAtwVUSsk3SOpONytouAOZKGgDOA4m2dLwKGI2JDc4tuZjY1BgagtxdmzEj/BwZaXaLxUz4hbxt9fX0xODjY6mKYmQEpwC9fDjt27Ezr6YGVK6G/v3XlKidpbUT01crnJ3LNzMawYsXogA9pesWK1pRnohz0zczGsHlzY+ntzkHfzGwMCxY0lt7uHPTNzMZw7rmpDb+opyeldyIHfTOzMfT3p4u2CxeClP6320XcRsxqdQHMzNpdf3/nBvlyPtM3M+siDvpmZl3EQd/MrIs46JuZdREHfTOzLuKgb2bWRRz0zcy6iIO+mVkXcdA3M+siDvpmZl2krqAvaYmk9ZKGJJ1ZYf5sSVfm+Wsk9RbmPUfSjyWtk/QLSbs1r/hmZtaImkFf0kzgAuBYYDFwkqTFZdlOBbZHxCLgfOC8/N5ZwOeB0yLiEOBo4A9NK72ZmTWknjP9w4GhiNgQEQ+RBjhfWpZnKXBpfn01cIwkAS8Hfh4RNwFExD0R8Uhzim5mZo2qJ+gfAGwpTA/ntIp58kDq9wFzgKcBIWm1pJ9JemelFUhaLmlQ0uDIyEijn8HMzOpUT9BXhbTy0dSr5ZkFHAX05/+vkXTM4zJGrIyIvojomzt3bh1FMjOz8agn6A8D8wvT84Ct1fLkdvy9gG05/bsRcXdE7AC+Dhw20UKbmdn41BP0rwcOlnSgpF2BZcCqsjyrgJPz6+OBayMigNXAcyT15C+DFwO/bE7Rzcx2GhiA3l6YMSP9HxhodYnaU82RsyLiYUmnkwL4TODiiFgn6RxgMCJWARcBl0kaIp3hL8vv3S7pI6QvjgC+HhFfm6TPYmZdamAAli+HHTvS9KZNaRqmz4hXzaJ0Qt4++vr6YnBwsNXFMLMO0tubAn25hQth48apLk1rSFobEX218vmJXDPreJs3N5bezRz0zazjLVjQWHo3c9A3s4537rnQ0zM6racnpdtoDvpm1vH6+2HlytSGL6X/K1f6Im4lNe/eMTPrBP39DvL18Jm+mVkXcdA3M+siDvpmZl3EQd/MrIs46JuZdREHfTOzLuKgb2bWRRz0zcy6iIO+mVkXcdA3M+siDvpmZl2krqAvaYmk9ZKGJJ1ZYf5sSVfm+Wsk9eb0Xkn/K+nG/Hdhc4tvZmaNqNnhmqSZwAXAy0gDnV8vaVVEFMe6PRXYHhGLJC0DzgNOzPNujYhDm1xuMzMbh3rO9A8HhiJiQ0Q8BFwBLC3LsxS4NL++GjhGkppXTDMza4Z6gv4BwJbC9HBOq5gnIh4G7gPm5HkHSrpB0nclvbDSCiQtlzQoaXBkZKShD2BmnWNgII1nO2NG+j8w0OoSdZ96+tOvdMZePpp6tTx3AAsi4h5JzwO+KumQiLh/VMaIlcBKSAOj11EmM+swAwOwfDns2JGmN21K0+B+8KdSPWf6w8D8wvQ8YGu1PJJmAXsB2yLi9xFxD0BErAVuBZ420UKbWedZsWJnwC/ZsSOl29SpJ+hfDxws6UBJuwLLgFVleVYBJ+fXxwPXRkRImpsvBCPpIOBgYENzim5mnWTz5sbSbXLUbN6JiIclnQ6sBmYCF0fEOknnAIMRsQq4CLhM0hCwjfTFAPAi4BxJDwOPAKdFxLbJ+CBm1t4WLEhNOpXSbeooor2a0Pv6+mJwcLDVxTCzJitv0wfo6fEA5s0iaW1E9NXK5ydyzWxK9PenAL9wIUjpvwP+1Kvn7h0zs6bo73eQbzWf6ZuZdREHfTOzLuKgb2bWRRz0zcy6iIO+mVkXcdA3M+siDvpmZl3EQd/MrIs46JuZdREHfTOzLuKgb2bWRRz0zcy6iIO+mVkXcdA3s8d44PLpr66gL2mJpPWShiSdWWH+bElX5vlrJPWWzV8g6QFJb29Osc2s2UqDnGzaBBE7By534J9eagb9PMbtBcCxwGLgJEmLy7KdCmyPiEXA+cB5ZfPPB74x8eKa2WTxwOXdoZ4z/cOBoYjYEBEPAVcAS8vyLAUuza+vBo6RJABJf04aDH1dc4psZpPBA5d3h3qC/gHAlsL0cE6rmCciHgbuA+ZI2gN4F/C+sVYgabmkQUmDIyMj9ZbdzJqo2gDlHrh8eqkn6KtCWvlo6tXyvA84PyIeGGsFEbEyIvoiom/u3Ll1FMnMmu3cc9NA5UU9PSndpo96xsgdBuYXpucBW6vkGZY0C9gL2AYcARwv6UPA3sCjkn4XEZ+YcMnNrKlKY9euWJGadBYsSAHfY9pOL/UE/euBgyUdCNwOLANeW5ZnFXAy8GPgeODaiAjghaUMks4GHnDAN2tfHrh8+qsZ9CPiYUmnA6uBmcDFEbFO0jnAYESsAi4CLpM0RDrDXzaZhTYzs/FROiFvH319fTE4ONjqYpiZdRRJayOir1Y+P5FrZtZFHPTNzLqIg76ZWRdx0Dcz6yIO+mZmXcRB38ysizjom5l1EQd9M7Mu4qBvZtZFHPTNOoyHNLSJqKfDNTNrE6UhDUsjXJWGNAR3lGb18Zm+WQfxkIY2UQ76Zh3EQxraRDnom3UQD2loE+Wgb9ZBPKShTZSDvlkH6e+HlSth4UKQ0v+VK30R1+pXV9CXtETSeklDks6sMH+2pCvz/DWSenP64ZJuzH83SXpNc4tv1n36+2HjRnj00fTfAd8aUTPoS5oJXAAcCywGTpK0uCzbqcD2iFgEnA+cl9NvBvoi4lBgCfDpPHC6mZm1QD1n+ocDQxGxISIeAq4AlpblWQpcml9fDRwjSRGxIyIezum7Ae01NqOZWZepJ+gfAGwpTA/ntIp5cpC/D5gDIOkISeuAXwCnFb4EHiNpuaRBSYMjIyONfwozM6tLPUFfFdLKz9ir5omINRFxCPB84CxJuz0uY8TKiOiLiL65c+fWUSQzMxuPeoL+MDC/MD0P2FotT26z3wvYVswQEbcADwLPGm9hzZrF/ddYt6on6F8PHCzpQEm7AsuAVWV5VgEn59fHA9dGROT3zAKQtBB4OrCxKSU3G6dS/zWbNkHEzv5rHPitG9QM+rkN/nRgNXALcFVErJN0jqTjcraLgDmShoAzgNJtnUcBN0m6EfgK8JaIuLvZH8KsEe6/xrqZItrrhpq+vr4YHBxsdTFsGpsxI53hl5PSve9mnUjS2ojoq5XPT+Ra15ns/mt8vcDamYO+dZ3J7L/G1wus3TnoW9eZzP5rfL3A2p3b9M2ayNcLrFXcpm/WAu7v3tqdg75ZE7m/e2t3DvpmTeT+7q3duZtjsybr73eQt/blM30zs1abwoc7fKZvZtZKpYc7Svf6lh7ugEn5yegzfTOzVprihzsc9M3MWmnz5sbSJ8hB38yslab44Q4HfTOzVprihzsc9K1tubdK6wpT/HCH796xtjTFNzSYtdYUPtxR15m+pCWS1ksaknRmhfmzJV2Z56+R1JvTXyZpraRf5P8vaW6P68W3AAAMTElEQVTxbbpyb5Vmk6Nm0Jc0E7gAOBZYDJwkaXFZtlOB7RGxCDgfOC+n3w28OiKeTRpD97JmFdymtym+ocFsbNOorbGeM/3DgaGI2BARDwFXAEvL8iwFLs2vrwaOkaSIuCEitub0dcBukmY3o+A2vbm3Smsb02xknHqC/gHAlsL0cE6rmCcPpH4fMKcsz18CN0TE78tXIGm5pEFJgyMjI/WW3aYx91ZpbWOatTXWE/RVIa18mIgx80g6hNTk86ZKK4iIlRHRFxF9c+fOraNINt25t0prG9OsrbGeu3eGgfmF6XnA1ip5hiXNAvYCtgFImgd8BXh9RNw64RJb13BvldYWFixITTqV0jtQPWf61wMHSzpQ0q7AMmBVWZ5VpAu1AMcD10ZESNob+BpwVkT8sFmFNjN7nMm62DrN2hprBv3cRn86sBq4BbgqItZJOkfScTnbRcAcSUPAGUDpts7TgUXAeyXdmP+e3PRPYWbdbTIvtk6ztkYPjG5mna+3t3ITzMKFsHHjVJemJTwwupl1j2l2sXUyOeibWefzgx11c9A3s6nji60t56BvZlPDF1vbgi/kmtnU8MXWSeULuTbpplEfVDYVfLG1LTjo27hMsz6obCr4YmtbcNC3cZlmfVDZVPDF1rbgoG/j4l/q1jBfbG0LHi7RxmWa9UFlU8W96LWcz/RtXPxLfZry1flpz0HfxsW/1KchX53vCr5P38wS30ff0Xyfvpk1xlfnu4KDvlmnmax2d99H3xUc9M06yWS2u/vqfFeoK+hLWiJpvaQhSWdWmD9b0pV5/hpJvTl9jqTvSHpA0ieaW3SzLjSZT8X56nxXqHmfvqSZwAXAy0gDoF8vaVVE/LKQ7VRge0QskrQMOA84Efgd8F7gWfnPzCZistvdfR/9tFfPmf7hwFBEbIiIh4ArgKVleZYCl+bXVwPHSFJEPBgRPyAFfzObKLe72wTVE/QPALYUpodzWsU8eSD1+4A59RZC0nJJg5IGR0ZG6n2b1cHP2rTAZFa6291tguoJ+qqQVn5zfz15qoqIlRHRFxF9c+fOrfdtVoOftWmBya50t7vbBNUT9IeB+YXpecDWankkzQL2ArY1o4A2fh3fE2Yn/kyZikrv708PSz36aPrvgG8NqCfoXw8cLOlASbsCy4BVZXlWASfn18cD10a7PerbhTr6WZtO/ZnS0ZVu3aBm0M9t9KcDq4FbgKsiYp2kcyQdl7NdBMyRNAScATx2W6ekjcBHgFMkDUta3OTPYFV09DW/yT5j9gNO1q0ioq3+nve854U1x+c/H9HTE5FOldNfT09Kb3vS6IKX/qSJL3syK6ajK906GTAYdcRYP5E7jXX0Nb/JPGP2A07WxdzLprWnUpt+MTj39DQngM6Ykc7By0np4qhZB3Ivmx2iE29QmRKTecbsdnfrYg76LdSpN6hMmcm6NdEPOFkXc9BvoY6/j75Tud3dupiDfgt1/C3dndw25QecrEs56LdQRzctu23KrCM56LdQRzctu23KrCM56LfQlDQtT1YTTMe3TZl1p5qDqNjkmtQxK8rvdS81wZRWPBELFqTlVUo3s7blM/3pbDKbYDq6bcqsezno12FSb1KZzIVPZhOMb3s060hu3qlhYACWv/FhdjyUqmrTpjQNsyYe3yaz+QUmvwnG46madRyf6dew4m0PPBbwS3Y8NIsVb3ugCQuf5Dtg3ARjZmUc9GvYfE9PQ+mNLXyS74BxE4yZlZk2QX/gLT+gd9YwM/QovbOGGXjLD5qy3AVUDsDV0htb+BQ8neUnT82soK6gL2mJpPWShiSdWWH+bElX5vlrJPUW5p2V09dLekXzir7TwFt+wPJPPZdNj8wjmMGmR+ax/FPPbUrgP3fOR+jhwVFpPTzIuXM+MuFlu/nFzKZazaAvaSZwAXAssBg4qcKQh6cC2yNiEXA+cF5+72LSmLqHAEuAT+blNdWKlb3sYI9RaTvYgxUreye87P6PHcHKXU5nIRsRj7KQjazc5XT6P3bEhJft5hczm2r13L1zODAUERsAJF0BLAV+WcizFDg7v74a+IQk5fQrIuL3wG15DN3DgR83p/jJ5kf2byi9If399AP9K45Obe0LFqQz8WYFZt8BY2ZTqJ7mnQOALYXp4ZxWMU+kgdTvA+bU+V4kLZc0KGlwZGSk/tJnC2ZubSi9YW4XN7Npop6grwpp5WPNVctTz3uJiJUR0RcRfXPnzq2jSKOdu3xj5Xb35RsbXpaZ2XRWT9AfBuYXpucB5afQj+WRNAvYC9hW53snrP+TR7HyzTewcOZwanefOczKN99A/yePavaqzMw6Wj1B/3rgYEkHStqVdGF2VVmeVcDJ+fXxwLWRRlxfBSzLd/ccCBwM/LQ5RR+t/5NHsfHheTwaM9j48DwHfDOzCmpeyI2IhyWdDqwGZgIXR8Q6SecAgxGxCrgIuCxfqN1G+mIg57uKdNH3YeBvI+KRSfosZmZWg9IJefvo6+uLwcHBVhfDzKyjSFobEX218k2bJ3LNzKw2B30zsy7ioG9m1kXark1f0ghQoRP4trAvcHerCzFOLvvU69Ryg8veKhMp+8KIqPmgU9sF/XYmabCeCyXtyGWfep1abnDZW2Uqyu7mHTOzLuKgb2bWRRz0G7Oy1QWYAJd96nVqucFlb5VJL7vb9M3MuojP9M3MuoiDvplZF3HQzyTNl/QdSbdIWifpbTl9H0nfkvTr/P9JOV2SPp7H//25pMNa+wnS0JaSbpB0TZ4+MI9Z/Os8hvGuOb3qmMYtKvfekq6W9Ktc/y/olHqX9Pd5f7lZ0hck7dau9S7pYkl3Sbq5kNZwPUs6Oef/taSTK61risr+r3mf+bmkr0jauzCv4tjcqjHe91SUuzDv7ZJC0r55emrqPCL8l65r7Accll/vCfwPaUzgDwFn5vQzgfPy61cC3yANFHMksKYNPsMZwOXANXn6KmBZfn0h8Ob8+i3Ahfn1MuDKFpf7UuCv8+tdgb07od5Jo8DdBuxeqO9T2rXegRcBhwE3F9IaqmdgH2BD/v+k/PpJLSr7y4FZ+fV5hbIvBm4CZgMHAreSegiemV8flPezm4DFU13unD6f1HPxJmDfqazzlhwsnfAH/AfwMmA9sF9O2w9Yn19/GjipkP+xfC0q7zzg28BLgGvyjnN34aB4AbA6v14NvCC/npXzqUXlfmIOnCpLb/t6Z+dwoPvkerwGeEU71zvQWxY4G6pn4CTg04X0Ufmmsuxl814DDOTXZwFnFeatztvhsW1RKd9Ulps0lvgfAxvZGfSnpM7dvFNB/tn9XGAN8JSIuAMg/39yzlbX+L9T6KPAO4FH8/Qc4N5IYxbD6PJVG9O4FQ4CRoDP5qapz0jagw6o94i4HfgwsBm4g1SPa+mMei9ptJ7bpv7LvJF0lgxtXnZJxwG3R8RNZbOmpNwO+mUkPQH4EvB3EXH/WFkrpLXk/ldJrwLuioi1xeQKWaOOeVNtFunn76ci4rnAg6Rmhmrapuy5/XspqQlhf2AP4NgKWdux3muZ0LjXU0nSCtIgTQOlpArZ2qLsknqAFcA/VppdIa3p5XbQL5C0CyngD0TEl3PynZL2y/P3A+7K6VMy/m+d/hQ4TtJG4ApSE89Hgb2VxiyG0eWrNqZxKwwDwxGxJk9fTfoS6IR6fylwW0SMRMQfgC8Df0Jn1HtJo/XcTvVPvqj5KqA/ctsH7V32p5JOEm7Kx+s84GeS/miM8jW13A76mSSRhn28JSI+UphVHP/3ZFJbfyn99fmK+5HAfaWfyVMtIs6KiHkR0Uu6QHhtRPQD3yGNWQyPL3ulMY2nXET8Btgi6ek56RjS8JptX++kZp0jJfXk/adU9rav94JG63k18HJJT8q/dF6e06acpCXAu4DjImJHYVa1sbnrGe97UkXELyLiyRHRm4/XYdINJL9hqup8Ki7AdMIfcBTpJ9PPgRvz3ytJba7fBn6d/++T8wu4gHQ3wC+AvlZ/hlyuo9l5985BpJ19CPgiMDun75anh/L8g1pc5kOBwVz3XyXdodAR9Q68D/gVcDNwGemOkbasd+ALpGsPfyAFm1PHU8+k9vOh/PeGFpZ9iNTWXTpeLyzkX5HLvh44tpD+StKdebcCK1pR7rL5G9l5IXdK6tzdMJiZdRE375iZdREHfTOzLuKgb2bWRRz0zcy6iIO+mVkXcdA3M+siDvpmZl3k/wNCuIqLQiNzQAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as graph\n",
    "graph.plot(tailles,yF,\"ro\")\n",
    "graph.plot(tailles,yS,\"bo\")\n",
    "graph.title(\"tri par fusion en rouge et par sélection en bleu\\n\"+\n",
    "                 \"vitesse d'exécution en fonction de la taille des données\")\n",
    "graph.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les points ne sont pas bien alignés car l’exécution des programmes se fait dans un environnement multitâche. Il se peut donc que le système fasse autre chose pendant la partie chronométrée (comme enregistrer ou scanner un fichier avec l’antivirus) pour que la mesure soit faussée. Il suffit alors de relancer le programme pour avoir une nouveau version en espérant que seul le programme soit exécuté.\n",
    "\n",
    "Pour la suite de l'exercice, on pourra chercher les équations de ces belles courbes (quadratiques)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}