chrono.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chronométrer une fonction : notion de complexité"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lorsqu'on écrit un algorithme puis qu'on le programme, on se pose plusieurs questions :\n",
    "    * la terminaison, est-ce que le programme a s'arrêter ?\n",
    "    * la correction, le programme donnera-t-il le résultat attendu ?\n",
    "    * la complexité en temps et en espace : de combien de temps, de combien de mémoire le programme a-t-il besoin pour terminer ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'objectif de ce notebook est d'observer le temps d'exécution des algorithmes au programme de la classe de première, et surtout de voir comment elle évolue en fonction de la taille de l'entrée."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [],
   "source": [
    "# la fonction randint(a,b) renvoie un nombre entier au hasard entre a inclus et b inclus\n",
    "from random import randint\n",
    "\n",
    "# on construit une liste de dix nombres, choisis entre 1 et 1000000\n",
    "liste=[randint(1,1000000) for k in range(10)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recherchesequentielle(x,l):\n",
    "    for elt in l:\n",
    "        if elt==x:\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The slowest run took 9.19 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "100000 loops, best of 5: 3.62 µs per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "# on cherche chacun des éléments de la liste, afin de faire une moyenne sur la position\n",
    "# de l'élément cherché, qui sera trouvé plus rapidement en début de liste qu'en fin de liste\n",
    "for k in liste:\n",
    "    recherchesequentielle(k,liste)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'instruction jupyter magique `%%timeit` va exécuter plusieurs fois le contenu de la cellule et calculer le temps moyen d'exécution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The slowest run took 6.89 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "1000000 loops, best of 5: 481 ns per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "recherchesequentielle(0,liste)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Attention, dans ce exemple on travaille avec une liste de $n=10$ éléments, le premier temps correspond donc à 10 recherches, alors que le deuxième temps ne correspons qu'à une seule recherche, il faut en tenir compte lorsqu'on  complète le tableau ci-dessous.\n",
    "\n",
    "Rappelons aussi que $1\\mu s=10^{-6}s = 1000 ns$, $1ns=10^{-9}s$. Les temps sont donnés en $ns$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| n | 10 |20|50|100|200|500|1000|\n",
    "|---|---|---|---|---|---|---|---|\n",
    "|Trouvé|362|491|1018|1870|3675|9180|17400|\n",
    "|Pas trouvé|481|810|1760|3400|6680|17700|33900|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous allons utiliser la librairie `matplotlib.pyplot` pour visualiser la façon dont le temps de calcul augmente avec la taille de la liste dans laquelle on recherche un élément."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=[10,20,50,100,200,500,1000]\n",
    "et=[362,491,1018,1870,3675,9180,17400]\n",
    "pt=[481,810,1760,3400,6680,17700,33900]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZEAAAEYCAYAAACdnstHAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAAgAElEQVR4nO3deZwV1Z3H/c9XQBoUBJEoggoaoiIoCCIOMbgiLnEbE1AmEmOCuEQdE6ImmUjEPKNPjDHmQSKJUYyO4hgX4mjQEFAxQQU1LrghoKLN4gKCiLL8nj/qdHNpm+7bl769ft+vV71u1alTVadu9at/99SpOkcRgZmZWSG2qe8CmJlZ4+UgYmZmBXMQMTOzgjmImJlZwRxEzMysYA4iZmZWMAcRazIkHSZpcR0dKyR9uY6OtY2kBySNrovj1ZSkkZIeyTPvrZKuSvN1dr2seBxErF5IWiTpU0mrJS1J/1y2r+9yNVBXAX+PiEn1XRBJ3VMAbVmWFhF3RMTQ+iyX1R8HEatPX4+I7YG+QD/g8nouT7ncf5L1LSJ+HBG/qe9ymFXGQcTqXUQsAaaRBRMAJA2S9A9JKyT9S9JhOet2lHSLpPckfSTp/tz9SfqBpGWSSiWdlZPeWtK1kt6WtFTS7yS1SesOk7RY0qWSlgC3SGoh6ceS3pS0StJcSbvlHOooSW+kMk6QpJxjfUfSK6l80yTtUdm5SyqRdLukD9J+npG0c1q3g6Sb03m8K+kqSS3SuhbpXN6XtEDS+bk1hFTTOyrnOOMk3Z7n9ztT0nhJT6bzfkTSTmn14+lzRapFHiLp25Jm5Wy/j6RHJX0o6TVJ36z8yn/hu9hV0p8lLZe0UNKF+Wxn9ctBxOqdpG7AscD8tNwV+D+y2zg7Aj8E/iypc9rkT0BbYD/gS8Cvc3a3C7AD0BU4G5ggqWNadzXwFbJg9eWU52cVtt0R2AMYDVwCnA4cB7QHvgOsycl/AnAQsD/wTeCYVP6TgB8DpwKdgSeAO7dw+qNSeXcDOgFjgE/TuluB9ams/YChwHfTuu+l4/cDBgCnbWH/X5DH9wtwBnAW2fe7bcoD8LX02SEito+If1bY93bAo8D/pG1HADdK6lVNmbYB/gL8i+y6HAlcLOmYfM/L6klEePJU5xOwCFgNrAICmE72jwngUuBPFfJPI/uH2wXYCHSsZJ+Hkf0DbpmTtgwYBAj4BNgrZ90hwMKcbT8HSnLWvwactIXyB/DVnOW7gcvS/MPA2TnrtiELPntUsp/vAP8A9q+QvjPwGdAmJ+10YEaa/zswJmfd0FSmljnf71E568cBt1f3/ab5mcBPc9adB/w1zXfPPU5K+zYwK80PB56osO+bgCvS/K3AVTnf+eI0fzDwdoXtLgduqe+/VU9VTw3mvq81SydHxN8kDSH75boTsIKsJvANSV/PydsKmEH2i/3DiPhoC/v8ICLW5yyvAbYnqxG0Bebm3nUCWuTkXR4Ra3OWdwPerKL8Syo5Dqn8v5H0q5z1IvuF/VaFffwpHecuSR2A24GfpH20AkpzyrsN8E6a3zVnnkr2W5Wqvt8yWzq3fPZ9sKQVOWktyc6zuu12rbBdC7JanDVgDiJW7yLiMUm3AtcCJ5P9c/xTRHyvYl5JXYAdJXWIiBUV11fhfbJayn4R8e6WilJh+R1gL+ClGhynbLtfRMQd1WWMiHXAz4GfS+oOPERWA3qIrCayU4WgWKaULPiU2b3C+k/IgmaZXSqUr9LvNw/Vdfv9DvBYRBxdw/2+Q1Yr7FlAmaweuU3EGorrgaMlHUD2a/zrko5JDcglqeG7W0SUkt0uulFSR0mtJH2tyj0DEbER+D3wa0lfgqxtoJp77n8Axkvqqcz+kjrlcS6/Ay6XtF86zg6SvlFZRkmHS+qTGsw/BtYBG9N5PgL8SlJ7Ze+K7JVqbZDdPrtQUrfU5nNZhV0/D4xI30/FNpMtfr95nNtystuJe25h/YPAVyR9Kx27laSDJO1bzX6fBlYpe7ChTSpXb0kH5VEmq0cOItYgRMRy4DbgZxHxDlDWOL2c7FfqWDb9vX6L7J/tq2RtHhfneZhLyRrvZ0v6GPgbsHcV+a8j+2f9CNk/+JuBNnmcy33ANWS3qD4mq8kcu4XsuwD3pP2/AjzGpls/Z5I1as8DPkr5uqR1vydrx/gX8Cxwb4X9/hdZLeojsprO/+SUr7rvt6pzWwP8AngyPdk1qML6VWTtMyOA98hui10DtK5mvxvIHhToCywkqzn+geyhA2vAFOFBqcwau3QrbCHQagu3v8yKwjURMzMrmIOImZkVzLezzMysYK6JmJlZwZrdeyI77bRTdO/evb6LYWbWqMydO/f9iOhcMb1oQURSCVlnba3Tce6JiCvSS2VDgJUp67cj4nllr+X+hqyfojUp/dm0r1HAT1P+qyJickrvT9aNQhuyl7Muimruz3Xv3p05c+bU2nmamTUHkirtFaGYNZHPgCMiYrWkVsAsSQ+ndWMj4p4K+Y8FeqbpYGAiWfcJOwJXkHUyF2TdVkxN3V5MJOuI7imyIDKM7EU0MzOrA0VrE4nM6rTYKk1V1RJOAm5L280GOqQuLo4BHo2Isv6SHgWGpXXtI2J2qn3cRtZlhpmZ1ZGiNqynrgueJ3ur+NGIeCqt+oWkFyT9WlLZm6xd2bxDucUprar0xZWkV1aO0ZLmSJqzfPnyrT4vMzPLFLVhPXVl0Df1TnqfpN5k3TsvIevOYRJZVxRXFrkck9KxGDBgwBdqQ+vWrWPx4sWsXbv2C9ta81NSUkK3bt1o1apVfRfFrMGrk6ezImKFpBnAsIi4NiV/JukWNg128y6b90raLaW9SzbuQG76zJTerZL8NbZ48WLatWtH9+7dyel225qhiOCDDz5g8eLF9OjRo76LY9bgFe12lqTOqQaCsiFIjwZeTW0ZpKexTmZTN9tTgTNTb6mDgJWpJ9NpwNDUY2tHss7dpqV1Hysb5lNkndU9UEhZ165dS6dOnRxADEl06tTJtVJrWkpLYcgQWLKk+rw1VMyaSBdgcuriehvg7oh4UNLf0zCcIuuuekzK/xDZ473zyR7xPQsgIj6UNB54JuW7MiI+TPPnsekR34fZiiezHECsjP8WrMkZPx5mzYIrr4Qbb6zVXTe7bk8GDBgQFd8TeeWVV9h33+qGO6gbTz75JBs2bOBrX9vyEBn55Glq3nvvPaZPn863vvWtOjleQ/qbMCtYmzZQWa26pAQ+/bRGu5I0NyIGVEx3tycNyHPPPcctt9zCIYccUp7WvXt33n///SrzFMv111/PmjVraryutq1YsYJLLrmEI488sk6OZ9ZkLFgAZ5wBbdMgl23bwsiRsHBhrR3CQaRApatKGXLrEJasrr17jP369eMPf/hDlU8F5ZOnthQaRDZs2FCr5ejQoQN33XUXu+66a63u16zJ69IF2rfPaiMlJdln+/awyy7Vb5snB5ECjX98PLPensWVj9XO08m33347AwcOpG/fvpxzzjmV/iPeUp7tt9+esWPHst9++3HUUUfx9NNPc9hhh7HnnnsydepUIPvHPnbsWA466CD2339/brrpJgBmzpzJYYcdxmmnncY+++zDyJEjiQhuuOEG3nvvPQ4//HAOP/zwzcpR2brtt9+eH/zgBxxwwAH885//5LrrrqN379707t2b66+/HoBFixbRu3fv8v1ce+21jBs3jldffZWBAweWpy9atIg+ffoAMHfuXIYMGUL//v055phjKC0trZXv26zZWLoUxoyB2bOzz9puXI+IZjX1798/Kpo3b94X0rak5KqSYBxfmEquKsl7H5Ud/4QTTojPP/88IiLOPffcmDx5ckRE7LHHHrF8+fIq8wDx0EMPRUTEySefHEcffXR8/vnn8fzzz8cBBxwQERE33XRTjB8/PiIi1q5dG/37948FCxbEjBkzon379vHOO+/Ehg0bYtCgQfHEE09sduzKVFwHxJQpUyIiYs6cOdG7d+9YvXp1rFq1Knr16hXPPvtsLFy4MPbbb7/ybX75y1/GFVdcERERBxxwQCxYsCAiIq6++uoYP358fP7553HIIYfEsmXLIiLirrvuirPOOqvg77kmavI3YdYcAHOikv+pza4X36214MIF/PCRH3L/q/ezZv0a2rZsyyn7nsK1Q6+tfuMtmD59OnPnzuWggw4C4NNPP+VLX/pS3nm23XZbhg0bBkCfPn1o3bo1rVq1ok+fPixatAiARx55hBdeeIF77sm6LFu5ciVvvPEG2267LQMHDqRbt+yVm759+7Jo0SK++tWv1ugcWrRowb//+78DMGvWLE455RS22247AE499VSeeOIJTjzxxC1u/81vfpMpU6Zw2WWXMWXKFKZMmcJrr73GSy+9xNFHHw1ktakuXbpscR9mVvccRGqoS7sutG/dnrUb1lLSsoS1G9bSvnV7dtm+8HuMEcGoUaP47//+74LytGrVqvyx1G222YbWrVuXz69fv758+9/+9rccc8wxm207c+bM8vyQBYOybWqipKSEFi1aVJmnZcuWbNy4sXw5912M4cOH841vfINTTz0VSfTs2ZMXX3yR/fbbj3/+8581Lo+Z1Q23iRRg6SdLGdN/DLPPns2Y/mO2unH9yCOP5J577mHZsmUAfPjhh7z11ls1zlOVY445hokTJ7Ju3ToAXn/9dT755JMqt2nXrh2rVq2q8bpDDz2U+++/nzVr1vDJJ59w3333ceihh7LzzjuzbNkyPvjgAz777DMefPDB8m322msvWrRowfjx4xk+fDgAe++9N8uXLy8PIuvWrePll1/O+5zNrPhcEynAvcPvLZ+fcPyErd5fr169uOqqqxg6dCgbN26kVatWTJgwgT322KNGeary3e9+l0WLFnHggQcSEXTu3Jn777+/ym1Gjx7NsGHD2HXXXZkxY0be6w488EC+/e1vlzeWf/e736Vfv34A/OxnP2PgwIF07dqVffbZZ7Pthg8fztixY1mYHj/cdtttueeee7jwwgtZuXIl69ev5+KLL2a//fbL65zNrPj8siF+scy+yH8TZpvzy4ZmZlbrHETMzKxgDiJmZlYwBxEzMyuYg4iZmRXMQcTMzArmINLAPPnkkzz++ONbnceq5+/RbOs5iBSqCMNNNqbxRGrbihUruLGWR1yrSl1+j2ZNmYNIoXKHm6wljWk8kdpWVRAppC+v6tTl92jWlDmI1FSbNiDBxImwcWP2KWXpW6ExjScCWQ3pRz/6EX369GHgwIHMnz8fgL/85S8cfPDB9OvXj6OOOoqlS5cC8Nhjj9G3b1/69u1Lv379vtDv1mWXXcabb75J3759GTt2LDNnzuTQQw/lxBNPpFevXqxdu5azzjqLPn360K9fv/KuVm699VYuuOCC8v2ccMIJzJw5k9/97neMHTu2PD03Xz7ftZnlqbL+4ZvytLXjicR770WccUZE27YRkH2OHBlRWpr/Pio5fmMcT+Sqq66KiIjJkyfH8ccfHxERH374YWzcuDEiIn7/+9/HJZdcEhERJ5xwQsyaNSsiIlatWhXr1q3bbH8VxxqZMWNGtG3btnyMkWuvvbZ8LJFXXnkldtttt/j000/jlltuifPPP798u+OPPz5mzJgRy5Yti7322qs8fdiwYfHEE09U+T1WvCZmtgl1PZ6IpBLgcaA1WUeP90TEFZJ6AHcBnYC5wLci4nNJrYHbgP7AB8DwiFiU9nU5cDawAbgwIqal9GHAb4AWwB8i4upinU+5Igw32VjHEzn99NPLP//zP/8TgMWLFzN8+HBKS0v5/PPP6dGjBwCDBw/mkksuYeTIkZx66qnlx6vKwIEDy7efNWsW3//+9wHYZ5992GOPPXj99de3uG3nzp3Zc889mT17Nj179uTVV19l8ODBTJgwodrv2szyV8xefD8DjoiI1ZJaAbMkPQxcAvw6Iu6S9Duy4DAxfX4UEV+WNAK4BhguqRcwAtgP2BX4m6SvpGNMAI4GFgPPSJoaEfOKeE6ZsuEmR4+GSZOyRvatEI10PJGyY+bOf//73+eSSy7hxBNPZObMmYwbNw7Iblcdf/zxPPTQQwwePJhp06Z9oRffisoGtapKVWOUjBgxgrvvvpt99tmHU045BUl5fddmlr+itYmkGtDqtNgqTQEcAdyT0icDJ6f5k9Iyaf2Ryv4znQTcFRGfRcRCYD4wME3zI2JBRHxOVrs5qVjns5l774UJE+CAA7LPe++tfpsqNMbxRACmTJlS/ln2lNPKlSvp2rUrAJMnTy7P++abb9KnTx8uvfRSDjroIF599dUaHevQQw/ljjvuKC/722+/zd5770337t15/vnn2bhxI++88w5PP/10+TannHIKDzzwAHfeeScjRowAtv57NLPNFXU8EUktyG5ZfZms1vAmsCIiyn7qLga6pvmuwDsAEbFe0kqyW15dgdk5u83d5p0K6QdvoRyjgdEAu++++9adVBE0xvFEAD766CP2339/WrduzZ133gnAuHHj+MY3vkHHjh054ogjyscGuf7665kxYwbbbLMN++23H8cee+xm++rUqRODBw+md+/eHHvssRx//PGbrT/vvPM499xz6dOnDy1btuTWW2+ldevWDB48mB49etCrVy/23XdfDjzwwPJtOnbsyL777su8efPKxzbZ2u/RzDZXJ+OJSOoA3Af8F3BrRHw5pe8GPBwRvSW9BAyLiMVp3ZtkQWEcMDsibk/pNwMPp10Pi4jvpvRvAQdHxKZHdSrh8URqR/fu3ZkzZw477bRTfRelKPw3Yba5eh1PJCJWADOAQ4AOkspqQN2Ad9P8u8BuAGn9DmQN7OXpFbbZUrqZmdWRogURSZ1TDQRJbcgawF8hCyanpWyjgAfS/NS0TFr/9/RY2VRghKTW6cmunsDTwDNAT0k9JG1L1vg+tVjnY5tbtGhRk62FmFn+itkm0gWYnNpFtgHujogHJc0D7pJ0FfAccHPKfzPwJ0nzgQ/JggIR8bKku4F5wHrg/IjYACDpAmAa2SO+f4yIlwstbERs9rSRNV91cYvXrKnwGOvAwoULadeuHZ06dXIgaeYigg8++IBVq1aVv6NiZltuEynq01mNRbdu3Vi8eDHLly+v76JYA1BSUpLXy5Bm5iACZC/r+VenmVnNuQNGMzMrmIOImZkVzEHEzMwK5iBiZmYFcxAxM7OCOYiYmVnBHETMzKxgDiJmZlYwBxEzMytYtUFE0mBJ26X5/5B0nSSP4GNmZnnVRCYCayQdAPyAbHTC24paKjMzaxTyCSLr07geJwH/X0RMANoVt1hmZtYY5NMB4ypJlwPfAg6VtA3QqrjFMjOzxiCfmshw4DPgOxGxhGwY2l8WtVRmZtYoVBtEUuD4M9A6Jb0P3FfMQpmZWeOQz9NZ3wPuAW5KSV2B+4tZKDMzaxzyuZ11PjAY+BggIt4AvlTMQpmZWeOQTxD5LCI+L1uQ1BJoXgOzm5lZpfIJIo9J+jHQRtLRwP8CfylusczMrDHIJ4hcBiwHXgTOAR4CflrdRpJ2kzRD0jxJL0u6KKWPk/SupOfTdFzONpdLmi/pNUnH5KQPS2nzJV2Wk95D0lMpfYqkbfM/dTMz21rK3iMswo6lLkCXiHhWUjtgLnAy8E1gdURcWyF/L+BOYCCwK/A34Ctp9evA0cBi4Bng9IiYJ+lu4N6IuEvS74B/RcTEqso1YMCAmDNnTq2dp5lZcyBpbkQMqJi+xZcNJb1IFW0fEbF/VQeMiFKgNM2vkvQK2ZNdW3IScFdEfAYslDSfLKAAzI+IBalcdwEnpf0dAZyR8kwGxpF102JmZnWgqjfWT0if56fPP6XP/6CGDeuSugP9gKfInvS6QNKZwBzgBxHxEVmAmZ2z2WI2BZ13KqQfDHQCVkTE+kryVzz+aGA0wO67716TopuZWRW22CYSEW9FxFvA0RHxo4h4MU2XAkPzPYCk7cleVrw4Ij4mqynsBfQlq6n8aqvOIA8RMSkiBkTEgM6dOxf7cGZmzUY+DeuSNDhn4d/y3A5JrcgCyB0RcS9ARCyNiA0RsRH4PZtuWb0L7JazebeUtqX0D4AO6ZHj3HQzM6sj+QSDs4EbJS2S9BZwI/Cd6jaSJOBm4JWIuC4nvUtOtlOAl9L8VGCEpNaSegA9gafJGtJ7piextgVGAFNTz8IzgNPS9qOAB/I4HzMzqyXV9uIbEXOBAyTtkJZX5rnvwWQ9/74o6fmU9mPgdEl9ydpVFpE9NkxEvJyetpoHrAfOj4gNAJIuAKYBLYA/RsTLaX+XAndJugp4jixomZlZHan2EV9JrYF/B7qTE3Qi4sqilqxI/IivmVnN1fgR3xwPACvJ3vP4rLYLZmZmjVc+QaRbRAwreknMzKzRyadh/R+S+hS9JGZm1ujkUxP5KvBtSQvJbmcJiOreWDczs6YvnyBybNFLYWZmjVI+w+O+BXQAvp6mDinNzMyauXyGx70IuINsNMMvAbdL+n6xC2ZmZg1fPrezzgYOjohPACRdA/wT+G0xC2ZmZg1fXn1nARtyljekNDMza+byqYncAjwl6b60fDLuXsTMzMiv76zrJM0ke9QX4KyIeK6opTIzs0ah2iAiaRDwckQ8m5bbSzo4Ip4qeunMzKxBy6dNZCKwOmd5NR6C1szMyLNhPXK6+k2DSeXTlmJmZk1cPkFkgaQLJbVK00XAgmIXzMzMGr58gsgY4N/Ihp5dDBwMjC5moczMrHHI5+msZWRD0pqZmW0mn25PviJpuqSX0vL+kn5a/KKZmVlDl8/trN8DlwPrACLiBVwzMTMz8gsibSPi6Qpp64tRGDMza1zyCSLvS9oLCABJpwGl1W0kaTdJMyTNk/RyeqoLSTtKelTSG+mzY0qXpBskzZf0gqQDc/Y1KuV/Q9KonPT+kl5M29wgyX16mZnVoXyCyPnATcA+kt4FLgbOzWO79cAPIqIXMAg4X1Iv4DJgekT0BKanZcgGv+qZptGkFxol7QhcQfZU2EDgirLAk/J8L2c7jwVvZlaH8hmUakFEHAV0BvaJiK9GxKI8tist6yolIlYBrwBdgZOAySnbZLIOHUnpt0VmNtBBUhfgGODRiPgwIj4CHgWGpXXtI2J2ehnytpx9mZlZHchrUCpJ7YE1wK8lPStpaE0OIqk70A94Ctg5Ispuhy0Bdk7zXYF3cjZbnNKqSl9cSXplxx8taY6kOcuXL69J0c3MrAr53M76TkR8DAwFOgHfAq7O9wCStgf+DFyc9lMu1SCi0g1rUURMiogBETGgc+fOxT6cmVmzke+gVADHkd1uepk8B6WS1IosgNwREfem5KXpVhTpc1lKfxfYLWfzbimtqvRulaSbmVkdySeIzJX0CFkQmSapHbCxuo3Sk1I3A69ExHU5q6YCZU9YjQIeyEk/Mz2lNQhYmW57TQOGSuqYGtSHAtPSuo8lDUrHOjNnX2ZmVgfyHWO9L7AgItZI6gSclcd2g8lufb0o6fmU9mOyW2F3SzobeAv4Zlr3EFmgmk/W/nIWQER8KGk88EzKd2VEfJjmzwNuBdoAD6fJzMzqiHJ6ed9yJulE4Gtp8bGI+EtRS1VEAwYMiDlz5tR3MczMGhVJcyNiQMX0fJ7Ouhq4CJiXpgsl/T+1X0QzM2ts8rmddRzQNw1GhaTJwHNkt6bMzKwZy6dhHaBDzvwOxSiImZk1PvnURP4beE7SDLJHe7/Gpq5KzMysGctnUKo7Jc0EDkpJl0bEkqKWyszMGoV8b2dtA7wPrAC+Iulr1eQ3s3yVlsKQIbDEv82s8cnn6axrgCeBnwBj0/TDIpfLrPkYPx5mzYIrr6zvklgTVbqqlCG3DmHJ6tr/oVLteyKSXgP2j4jPav3o9cDviViD0aYNrF37xfSSEvj007ovjzVZ5/3fedw09ybO6X8ONx5/Y0H7KPg9EWAB0Kqgo5rZli1YAGecAW3bZstt28LIkbBwYf2Wy5qMNr9og34uJs6ZyMbYyMQ5E9HPRZtftKm1Y+QTRNYAz0u6KY0eeIOkG2qtBGbNVZcu0L59VhspKck+27eHXXap75JZE7HgwgWc0fsM2rbMfqi0bdmWkX1GsvCi2vuhks8jvlPTZGa1belSGDMGRo+GSZOyRnazWtKlXRfat27P2g1rKWlZwtoNa2nfuj27bF97P1TyecR3cnV5zKxA9967aX7ChPorhzVZSz9Zypj+YxjdfzST5k6idHXt/lDJp2G9J9kLh72AkrL0iNizVktSR9ywbmZWc1vTsH4LMBFYDxxONpb57bVbPDMza4zyCSJtImI6Wa3lrYgYBxxf3GKZmVljkE/D+meStgHekHQB2RC02xe3WGZm1hjkUxO5CGgLXAj0JxutcFSVW5iZWbOQz9NZZcPSria/YXHNzKyZqDaISPoKWX9Ze+Tmj4gjilguMzNrBPJpE/lf4HfA74ENxS2OmZk1Jvm0iayPiIkR8XREzC2bqttI0h8lLZP0Uk7aOEnvSno+TcflrLtc0nxJr0k6Jid9WEqbL+mynPQekp5K6VMkbVuD8zYzs1qQTxD5i6TzJHWRtGPZlMd2twLDKkn/dUT0TdNDAJJ6ASOA/dI2N0pqIakFMAE4luxlx9NTXoBr0r6+DHwEnJ1HmczMrBblczur7EmssTlpAVT5xnpEPC6pe57lOAm4K3U3v1DSfGBgWjc/IhYASLoLOEnSK8ARwBkpz2RgHNlLkWZmVkfyeTqrRy0f8wJJZwJzgB9ExEdAV2B2Tp7FKQ3gnQrpBwOdgBURsb6S/GZmVkfyHR63tkwE9gL6AqXAr+rioJJGS5ojac7y5cvr4pBmZs1CnQaRiFgaERsiYiPZ015lt6zeBXbLydotpW0p/QOgg6SWFdK3dNxJETEgIgZ07ty5dk7GzMzqNohI6pKzeApQ9uTWVGCEpNaSegA9gaeBZ4Ce6Umsbcka36dG1vXwDOC0tP0o4IG6OAczM9skn4Z1JHXliy8bPl7NNncChwE7SVoMXAEcJqkvWcP8IuCctK+XJd0NzCPrLfj8iNiQ9nMBMA1oAfwxIl5Oh7gUuEvSVcBzwM35nIuZmdWefMYTuQYYTvYPvuxlw4iIE4tctqLweCJmZjW3pfFE8qmJnAzsnR6/NTMzK5dPm8gCoAU+X68AABELSURBVFWxC2JmZo1PPjWRNcDzkqYD5bWRiLiwaKUyM7NGIZ8gMjVNZmZmm8nnjfXJktoAu0fEa3VQJjMzaySqbROR9HXgeeCvabmvJNdMzMwsr4b1cWRvlq8AiIjnqabzRTMzax7yCSLrImJlhbSNxSiMmZk1Lvk0rL8s6QyghaSewIXAP4pbLDMzawzyqYl8n2ywqM+A/wFWAhcXs1BmZtY45PN01hrgJ2kyMzMrV9fjiZiZWRPiIGJmZgVzEDEzs4Ll87Lh/yupvaRWkqZLWi7pP+qicGZm1rDlUxMZGhEfAyeQDST1ZWBsMQtlZmaNQz5BpOwJruOB/63kxUMzM2um8nnZ8EFJrwKfAudK6gysLW6xzMysMai2JhIRlwH/BgyIiHXAJ8BJxS6YmZk1fNXWRCSVAN8GviopgFnAxCKXy8zMGoF8bmfdBqwCfpuWzwD+BHyjWIUyM7PGIZ+G9d4RcXZEzEjT98j60qqSpD9KWibppZy0HSU9KumN9NkxpUvSDZLmS3pB0oE524xK+d+QNConvb+kF9M2N0hSzU7dzMy2Vj5B5FlJg8oWJB0MzMlju1uBYRXSLgOmR0RPYHpaBjgW6Jmm0aTbZZJ2BK4ADiYb0+SKssCT8nwvZ7uKxzIzsyLLJ4j0B/4haZGkRcA/gYNSLeCFLW0UEY8DH1ZIPgmYnOYnAyfnpN8WmdlAB0ldgGOARyPiw4j4CHgUGJbWtY+I2RERZLfcTsbMzOpUPm0itfkLf+eIKE3zS4Cd03xX4J2cfItTWlXpiytJr5Sk0WQ1HHbfffetKL6ZmeXK5xHft4CPgR2ATmVTRLyV1hUk1SCi0O1reKxJETEgIgZ07ty5Lg5pZtYs5NN31njgBeAG4FdpurbA4y1Nt6JIn8tS+rvAbjn5uqW0qtK7VZJu1uiUriplyK1DWLJ6SX0XxazG8mkT+SawV0QcFhGHp+mIAo83FSh7wmoU8EBO+pnpKa1BwMp022saMFRSx9SgPhSYltZ9LGlQeirrzJx9mTUq4x8fz6y3Z3HlY1fWd1HMaiyfNpGXgA5sqjXkRdKdwGHATpIWkz1ldTVwt6SzgbfIAhTAQ8BxwHxgDXAWQER8mGpCz6R8V0ZEWWP9eWRPgLUBHk6TWaPR5hdtWLt+Uw9CE+dMZOKciZS0LOHTn3xajyUzy5+ypokqMkgDyH7lv0Q2zjoAEXFicYtWHAMGDIg5c/J5QtmsuEpXlfLDR37I/a/ez5r1a2jbsi2n7HsK1w69ll2236W+i2e2GUlzI2JAxfR8aiKTgWuAF4GNtV0ws+aqS7sutG/dnrUb1lLSsoS1G9bSvnV7BxBrVPIJImsi4oail8SsGVr6yVLG9B/D6P6jmTR3EqWrS6vfyKwByed21nVkt7GmsvntrGeLW7Ti8O0sM7Oa25rbWf3S56CctAAKfULLzMyaiGqDSEQcXhcFMTOzxieflw13lnSzpIfTcq/0iK6ZmTVz+bxseCvZS3+7puXXgYuLVSAzM2s8thhEJJXd6topIu4mPd4bEeuBDXVQNjMza+Cqqok8nT4/kdSJ1FliWbckxS6YmZk1fFU1rJeNFHgJ2eO9e0l6EugMnFbsgpmZWcNXVRDpLOmSNH8fWf9WIntX5Ciynn3NzKwZq+p2Vgtge6AdsB1ZwGkBtE1p1hSVlsKQIbDE3ZKbWfWqqomURoT7pm5uxo+HWbPgyivhxhvruzRm1sBVVRNRFeusqWnTBiSYOBE2bsw+pSzdzGwLqgoiR9ZZKaz+LVgAZ5wBbdtmy23bwsiRsHBh/ZbLzBq0LQaRnMGfrDno0gXat4e1a6GkJPts3x52cbfkZrZl+byxbs3F0qUwZgzMnp19unHdzKqRTy++1lzce++m+QkT6q8cZtZouCZiZmYFcxAxM7OC1UsQkbRI0ouSnpc0J6XtKOlRSW+kz44pXZJukDRf0guSDszZz6iU/w1Jo+rjXMzMmrP6rIkcHhF9c4ZbvAyYHhE9gelpGeBYoGeaRgMTIQs6wBXAwcBA4IqywGNmZnWjId3OOgmYnOYnAyfnpN8WmdlAB0ldgGOARyPiw4j4CHgUGFbXhTYza87qK4gE8IikuZJGp7SdI6I0zS8Bdk7zXYF3crZdnNK2lG5mZnWkvh7x/WpEvCvpS8Cjkl7NXRkRISlq62ApUI0G2H333Wtrt2ZmzV691EQi4t30uYysm/mBwNJ0m4r0uSxlfxfYLWfzbiltS+mVHW9SRAyIiAGdO3euzVMxM2vW6jyISNpOUruyeWAo8BLZwFdlT1iNAh5I81OBM9NTWoOAlem21zRgqKSOqUF9aEozM7M6Uh+3s3YG7pNUdvz/iYi/SnoGuFvS2cBbwDdT/oeA44D5wBrgLMj69pI0Hngm5bvS/X2ZmdUtRdRa00OjMGDAgJgzZ059F6PBKl1Vyog/j2DKaVPYZXt3vmhmGUlzc17JKNeQHvG1BmD84+OZ9fYsrnzM45GZWfVcE2moSkthxAiYMqVOumNv84s2rF2/9gvpJS1L+PQnnxb9+GbWsLkm0tjkDlNbBxZcuIAzep9B25bZoFRtW7ZlZJ+RLLzIg1KZ2ZY5iDQ09TRMbZd2XWjfuj1rN6ylpGUJazespX3r9m4XMbMqOYg0NPU4TO3ST5Yypv8YZp89mzH9x7BktQelMrOqeVCqhqYeh6m9d/imQakmHO9Bqcyseq6JNEQeptbMGgnXRBoiD1NrZo2EayJmZlYwBxEzMyuYg0gDVbqqlCG3DvETUmbWoDmIFEtpKQwZUnCjuLsfMbPGwN2eFMt558FNN8E558CNN+a9mbsfMbOGyN2e1JWtfOPc3Y+YWWPiIFLbtvKNc3c/YmaNiYNIbUtvnMfaT/ms1TbE2k9r/Ma5ux8xs8bCLxsWorpu2pcu5fFhvbh4j3lc/1YvhtSwcd3dj5hZY+EgUojcbtorNJq3+UUb1h6wqWH8sJ1fBl6m5Bdt3DBuZk2Ob2flq7QUWrSottHcDeNm1pw4iOTpk/+6jI0bN7Juzx581jqrwH3WuuUXGs3dMG5mzYmDSHXSI7vb3Xwb2wCtFiyk9WfrCaDl5+u58bU7aHNzj802ccO4mTUXjf5lQ0nDgN8ALYA/RMTVVeWv6cuGPS4r4ar/+4yTX4Xt1sN6wZsd4dzjYfhrLThQXdjtb8+4pmFmTVqTfNlQUgtgAnAs0As4XVKv2jzGP36ykJ13/TIlG+DTliBg+p7wj6+05rzjg1v+6+sOIGbWbDXqIAIMBOZHxIKI+By4CzipNg/QpV0XOq1az00DYMg52/K7/tBzXTue+u5TvlVlZs1eY3/EtyvwTs7yYuDgipkkjQZGA+y+++41Psj4i/rRZfvj+H3/0UyaO4npq0u5d5cD/A6HmTV7jT2I5CUiJgGTIGsTqen2fvnPzKxyjf121rvAbjnL3VKamZnVgcYeRJ4BekrqIWlbYAQwtZ7LZGbWbDTq21kRsV7SBcA0skd8/xgRL9dzsczMmo1GHUQAIuIh4KH6LoeZWXPU2G9nmZlZPXIQMTOzgjX6bk9qStJy4K0abLIT8H6RitNQNcdzhuZ53s3xnKF5nvfWnvMeEdG5YmKzCyI1JWlOZf3FNGXN8ZyheZ53czxnaJ7nXaxz9u0sMzMrmIOImZkVzEGkepPquwD1oDmeMzTP826O5wzN87yLcs5uEzEzs4K5JmJmZgVzEDEzs4I5iGyBpGGSXpM0X9Jl9V2e2iRpN0kzJM2T9LKki1L6jpIelfRG+uyY0iXphvRdvCDpwPo9g8JJaiHpOUkPpuUekp5K5zYldeSJpNZpeX5a370+y701JHWQdI+kVyW9IumQpn6tJf1n+tt+SdKdkkqa4rWW9EdJyyS9lJNW42sraVTK/4akUTUpg4NIJepi2N16th74QUT0AgYB56fzuwyYHhE9gelpGbLvoWeaRgMT677IteYi4JWc5WuAX0fEl4GPgLNT+tnARyn91ylfY/Ub4K8RsQ9wANn5N9lrLakrcCEwICJ6k3XOOoKmea1vBYZVSKvRtZW0I3AF2YB+A4ErygJPXiLCU4UJOASYlrN8OXB5fZeriOf7AHA08BrQJaV1AV5L8zcBp+fkL8/XmCay8WamA0cADwIie4O3ZcXrTtYz9CFpvmXKp/o+hwLOeQdgYcWyN+VrzaYRT3dM1+5B4Jimeq2B7sBLhV5b4HTgppz0zfJVN7kmUrnKht3tWk9lKapUde8HPAXsHBGladUSYOc031S+j+uBHwEb03InYEVErE/LuedVfs5p/cqUv7HpASwHbkm38f4gaTua8LWOiHeBa4G3gVKyazeXpn+ty9T02m7VNXcQacYkbQ/8Gbg4Ij7OXRfZT5Im8/y3pBOAZRExt77LUsdaAgcCEyOiH/AJm25vAE3yWncETiILoLsC2/HFWz7NQl1cWweRyjX5YXcltSILIHdERNkg8ksldUnruwDLUnpT+D4GAydKWgTcRXZL6zdAB0ll4+rknlf5Oaf1OwAf1GWBa8liYHFEPJWW7yELKk35Wh8FLIyI5RGxDriX7Po39WtdpqbXdquuuYNI5Zr0sLuSBNwMvBIR1+WsmgqUPZkxiqytpCz9zPR0xyBgZU51uVGIiMsjoltEdCe7nn+PiJHADOC0lK3iOZd9F6el/I3u13pELAHekbR3SjoSmEcTvtZkt7EGSWqb/tbLzrlJX+scNb2204ChkjqmWtzQlJaf+m4UaqgTcBzwOvAm8JP6Lk8tn9tXyaq4LwDPp+k4svvA04E3gL8BO6b8Inta7U3gRbKnXur9PLbi/A8DHkzzewJPA/OB/wVap/SStDw/rd+zvsu9FefbF5iTrvf9QMemfq2BnwOvAi8BfwJaN8VrDdxJ1u6zjqzWeXYh1xb4Tjr/+cBZNSmDuz0xM7OC+XaWmZkVzEHEzMwK5iBiZmYFcxAxM7OCOYiYmVnBHETMzKxgDiJmZlYwBxFrkiR1kvR8mpZIejdnedsqtvtHzvzq3M8il3ecpB/WcJsalSs3f+55VpKvg6TzarJva75aVp/FrPGJiA/I3tRG0jhgdURcm8d2/1bkojUI1ZxnB+A84MY6Ko41Yq6JWLMk6X5Jc9Pod6Nz0qv8dS/pPyQ9nWo0N6UBzCrmuVfSVZIel/S2pKO2sK+fSHpd0ixg75z0ao+Rz7lUs81qSdtJ+j9J/1I2AuDwtPpqYK90/F/WtDzWvDiIWHP1nYjoDwwALpRU7fgRkvYFhgODI6IvsAEYWUnWPmRjV3yNbCTFL+SR1J+sI8i+ZP2WHVTDY2zVuSTDgPci4oDIRgD8a0q/DHgzHf+PBZTHmhHfzrLm6kJJp6T53ciGDK2u++8jgf7AM1nnsLRhUzfbAEhqS9aV+K9TUitgRSX7OhS4LyLWpO3Keomu9hi1dC6QdcL3K0nXkHVI+UQleQopjzUjDiLW7Eg6jGzMiUMiYo2kmWQ9uVa7KTA5Ii6vIk8vYG5EbEjL+5P1JJt38fI4xqbMhZ8LEfG6pAPJakJXSZoeEVduTXms+fHtLGuOdgA+Sv909wEG5bnddOA0SV8CkLSjpD0q5OlD1rV+mf3JumCv6HHgZEltJLUDvl6DY9TGuSBpV2BNRNwO/JJssCqAVUC7AstjzYxrItYc/RUYI+kV4DVgdj4bRcQ8ST8FHpG0DdkYDucDb+Vk60M2Xn2Z3lRSE4mIZyVNAf5FdnvomRocY6vPJaesv5S0MR3n3FSGDyQ9Kekl4GGgJuWxZsbjiZiZWcF8O8vMzArmIGJmZgVzEDEzs4I5iJiZWcEcRMzMrGAOImZmVjAHETMzK9j/DzrGwOVoIWMYAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(n,et,'g*',label='élément trouvé')\n",
    "plt.plot(n,pt,'r*',label='élément pas trouvé')\n",
    "plt.title('Recherche séquentielle')\n",
    "plt.xlabel('Taille $n$ de la liste')\n",
    "plt.ylabel('Temps en nanosecondes')\n",
    "plt.legend()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question** Comment qualifier la complexité en temps de cet algorithme ?\n",
    "\n",
    "*Indice* piocher dans le vocabulaire suivant : linéaire, quadratique, logarithmique, exponentiel, quasi-linéaire."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question** Comment caractériser le lien entre les temps pour les deux cas examinés, élément dans la liste vs élément pas dans la liste ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Ex1** Refaire les manipulations, remplir le tableau, refaire le graphique."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Utilisation de la bibliothèque `time`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un problème avec l'utilisation de `%%timeit`, instruction liée à Jupyter, est que les manipulations pour modifier la taille $n$ de l'entrés sont fastidieuses alors qu'on voudrait les automatiser.\n",
    "\n",
    "La fonction `time` de la librairie du même nom va nous servir à chronométrer des instructions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1589147946.5354512"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1589147953.3629844"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [],
   "source": [
    "t0=time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5.630523681640625"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "time.time()-t0 # à exécuter plusieurs fois"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "La liste de taille 10000 a été triée en 0.0021970272064208984 secondes.\n"
     ]
    }
   ],
   "source": [
    "liste=[randint(1,10000000) for k in range(10000)]\n",
    "t0=time.time()\n",
    "liste.sort()\n",
    "t1=time.time()\n",
    "print(f\"La liste de taille {len(liste)} a été triée en {t1-t0} secondes.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A vous de jouer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On attend le même type de travail pour chacun des algortihmes proposés ci-dessous ; on a précisé la façon dont on définissait la taille $n$ d'une instance du problème."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recherche dichotomique\n",
    "La taille $n$ de l'instance est la taille du tableau trié dans lequel on recherche un élément ;\n",
    "comme pour la recherche séquentielle, on traitera les deux cas, élément présent dans la liste, et élément absent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tri par insertion\n",
    "La taille $n$ de l'instance est la taille de la liste à trier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Somme des éléments d'une liste\n",
    "La taille $n$ est le nombre d'éléments de la liste ; on construira des listes d'entiers pris au hasard entre 1 et 1000, si on autorisait des nombres plus grands cela aurait une influence sur la durée d'exécution. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tri par sélection\n",
    "La taille $n$ de l'instance est la taille de la liste à trier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Un algorithme glouton\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Plus longue sous-suite croissante\n",
    "La taille $n$ de l'instance est la longueur de la suite dans laquelle on cherche la plus longue sous-suite croissante."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plssc(l):\n",
    "    if len(l)<2:\n",
    "        return(l)\n",
    "    else:\n",
    "        avec=[l[0]]+plssc([k for k in l[1:] if k>=l[0]])\n",
    "        sans=plssc(l[1:])\n",
    "    if len(avec)>=len(sans):\n",
    "        return avec\n",
    "    else:\n",
    "        return sans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plscc([12,8,10,17,11,13,15])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}