TP19.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "70dba292",
   "metadata": {},
   "source": [
    "# ITC - MPSI\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e06d2bc3",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "0a62ea9d1e3183a3bdb61914bf799ec1",
     "grade": false,
     "grade_id": "cell-552b2ccc239be815",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "# TP19 : Complexité expérimentale\n",
    "Dans ce TP, on va essayer de mesurer des complexités de manière expérimentale.\n",
    "\n",
    "Pour cela, on a besoin de quelques outils pour:\n",
    "* mesurer le temps\n",
    "* représenter graphiquement des couples de valeurs\n",
    "\n",
    "### Exercice 0a : mesurer le temps\n",
    "Documentation de la fonction `time` du module `time`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d6f31713",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "3e00fd5b58ecbd40fde7bcce40c975cd",
     "grade": false,
     "grade_id": "cell-998e0fa5151cc04a",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "import time\n",
    "help(time.time)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "49703c44",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "4a60d0032b127f6ca2bb23f0b05bc619",
     "grade": false,
     "grade_id": "cell-11756b57f4c24f0a",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Afficher le temps mis pour calculer le produit d'un entier avec lui-même, pour les entiers inférieurs à 1000000 (on ne demande pas un affichage de ces entiers, contentez-vous d'affecter leur valeur à une variable, toujours la même)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b8f723b4",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "a530456a066352bb055eeedf7de8c3de",
     "grade": true,
     "grade_id": "cell-7da6576a80e38785",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4fb47866",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "a4e75897f1c6ce40d7de8d5b9ae43b9c",
     "grade": false,
     "grade_id": "cell-87f54272a8d7bbc2",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exercice 0b : tracer des courbes\n",
    "Si le module `matplotlib` n'est pas installé, vous devez décommenter la cellule suivante et l'exécuter, puis redémarrer le noyau."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ca4c44dd",
   "metadata": {},
   "outputs": [],
   "source": [
    "#!pip install matplotlib"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d89148cf",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "e3ac62f9abd0bac284d71b51790685c1",
     "grade": false,
     "grade_id": "cell-1efee63c18c7898a",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Le module `matplotlib` contient un sous module `pyplot` que nous allons importer :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b3b77f66",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "e26eaf812782b6bee60a08b37b290f43",
     "grade": false,
     "grade_id": "cell-7d8a486d9128b7cd",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa97824f",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "c3fc79f72e05d48d7b1907a98bb27afa",
     "grade": false,
     "grade_id": "cell-210ed22ab9d71785",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Ce sous module contient une fonction `plot` à laquelle on peut fournir deux listes de nombres de mêmes longueurs et qui renvoie un objet graphique représentant les couples de points dont l'abscisse se trouve dans la première liste et l'ordonnée dans la deuxième, dans les cases de même indice; et une fonction `show` qui permet d'afficher tous les objets graphiques créés après son appel précédent, voir par exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9b2b8d53",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "05248d46ea9de93d4551203ff08a5b36",
     "grade": false,
     "grade_id": "cell-aaba710b6e95ce9c",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "x = [1, 2, 3, 4, 5]\n",
    "y = [3, 7, 2, 10, 12]\n",
    "plt.plot(x, y)                # sans nom pour la courbe\n",
    "plt.show()\n",
    "\n",
    "x = [1, 2, 3, 4, 5]\n",
    "y = [3, 7, 2, 10, 12]\n",
    "plt.plot(x, y, label = 'a')   # avec un nom pour la courbe\n",
    "\n",
    "x = [5, 3, 2, 1]\n",
    "y = [1, 2, 3, 4]\n",
    "plt.plot(x, y, label = 'b')   # avec un nom pour la courbe\n",
    "plt.legend(loc='upper right') # pour placer la légende\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c4b51b9",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "209c792d9d54ae78f4b96d75e0383ce6",
     "grade": false,
     "grade_id": "cell-31b4222312ff0dd0",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Tracer sur un même graphique la courbe de $n\\mapsto n\\log_2 n$ et $n\\mapsto n^2$, pour les entiers $n$ entre 1 et 100000, avec une légende. (Le module `math` contient une fonction `log2`.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4ea543b2",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "595a381c38b252d17d76ce2578d7aa85",
     "grade": true,
     "grade_id": "cell-efccf27b1c7fca72",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c050368b",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "aee88f97d443cec0d06844b62c4b6fdb",
     "grade": false,
     "grade_id": "cell-552b2ccc239be816",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exercice 1 : tri bulle\n",
    "On rappelle le code du tri bulle donné en cours:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0ed3820d",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "cd15b6d8c99b20622d9e8db5dcd62c92",
     "grade": false,
     "grade_id": "cell-70f467087065f366",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def tri_bulle(liste) :\n",
    "    \"\"\"liste : liste de nombres\n",
    "    sortie : la liste est triée en place\"\"\"\n",
    "    permutation = True\n",
    "    n = len(liste)\n",
    "    while permutation :\n",
    "        permutation = False\n",
    "        for i in range(n-1):\n",
    "            if liste[i] > liste[i+1] : # si ce n'est pas dans le bon ordre, on permute\n",
    "                liste[i], liste[i+1] = liste[i+1], liste[i]\n",
    "                permutation = True\n",
    "        n = n - 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04241054",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "999ff3ad1873ea5170b4e2faf315e6cd",
     "grade": false,
     "grade_id": "cell-627cadcfa242aca1",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "On a montré en cours que la complexité dans le pire des cas de ce tri est en $O(n^2)$, où $n$ est la taille de l'entrée. Nous allons constaté expérimentalement que c'est également la complexité en moyenne.\n",
    "\n",
    "La fonction `randint` du module `random` permet d'obtenir un entier aléatoire (utilisez `help` pour avoir plus d'explications). On va utiliser cette fonction pour fabriquer des entrées aléatoires pour notre algorithmes.\n",
    "\n",
    "1. Écrire et documenter une fonction `liste_alea` qui prend en argument deux entiers `n` et `m` et renvoie une liste de `n` entiers aléatoires entre 0 et `m` compris."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "35648f60",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "3b1890cd126707d4321fa0b6dc7a0330",
     "grade": false,
     "grade_id": "cell-eb55a0669d60b218",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3ab6f942",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "a01d42a218d9ef18a06a41861fe1b92b",
     "grade": true,
     "grade_id": "cell-69a5652d51cd685f",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "assert ( len(liste_alea(50, 30)) == 50 ) "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "513b47c1",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "27be24795d06c14075caef4437c00e63",
     "grade": false,
     "grade_id": "cell-d271abd668fee5d8",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "2. En tirant 10 listes aléatoires par longueur, avec des entiers entre 0 et 1000, afficher la complexité expérimentale de `tri_bulle` pour les longueurs de 1 à 1000, par pas de 100 (c'est un peu long, c'est normal). Utiliser la variable `ord` pour la liste des ordonnées.\n",
    "\n",
    "_Nota_ : la fonction `range` peut prendre un troisième paramètre qui est le pas."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "af241684",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "bba11f48b211eba993719dbe5354e4c7",
     "grade": true,
     "grade_id": "cell-d131523dad32b8e0",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "abs = range(1, 1000, 100)\n",
    "ord = []\n",
    "\n",
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02ffb447",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "7937c3a30f97d7f41fbbc71b56209f67",
     "grade": false,
     "grade_id": "cell-e859b6885beeb265",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "3. La courbe ressemble (sauf erreur de votre part) à la courbe de $n\\mapsto n^2$. Nous allons essayer de le prouver expérimentalement en encadrant cette courbe par des courbes de multiples de $n\\mapsto n^2$.\n",
    "Essayez d'encadrer au plus près votre courbe:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6683b930",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ba2dccebd334bb26d76f631374ccd75c",
     "grade": true,
     "grade_id": "cell-604467efbb28258d",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "plt.plot(abs, ord, label='tri bulle')\n",
    "\n",
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit\n",
    "\n",
    "plt.legend(loc='upper right')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "775ffd73",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "4570329add8ccebf0eab73b935a53b8a",
     "grade": false,
     "grade_id": "cell-9596e2a75f8ba760",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exercice 2 : quicksort\n",
    "On reprend maintenant l'algorithme de quicksort. On a vu que dans le pire des cas, sa complexité est en $O(n^2)$. Qu'en est-il en pratique ?\n",
    "\n",
    "L'algorithme :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e3310f7c",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "081b304bf86cbbdc898cf3ae1c15fa8c",
     "grade": false,
     "grade_id": "cell-69b86c059467d2f8",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def quicksort(lst):\n",
    "    tri_rapide(lst, 0, len(lst)-1)\n",
    "\n",
    "def tri_rapide(lst, debut, fin):\n",
    "    \"\"\" lst : liste dde nombres\n",
    "    debut, fin : deux indices tq debut <= fin < longueur de la liste\n",
    "    action : liste triee en place entre debut et fin compris\"\"\"\n",
    "\n",
    "    if debut >= fin:\n",
    "        return\n",
    "    pivot = partitionner(lst, debut, fin)\n",
    "    tri_rapide(lst, debut, pivot-1)\n",
    "    tri_rapide(lst, pivot+1, fin)\n",
    "\n",
    "def partitionner(lst, debut, fin):\n",
    "    pivot = lst[debut] # à modifier pour que ce soit efficace\n",
    "    inf = debut + 1\n",
    "    sup = fin\n",
    "\n",
    "    while True:\n",
    "        while lst[sup] >= pivot and sup > debut:\n",
    "            sup -= 1\n",
    "        while lst[inf] < pivot and inf < fin:\n",
    "            inf += 1\n",
    "        if inf >= sup:\n",
    "            break\n",
    "        lst[inf], lst[sup] = lst[sup], lst[inf]\n",
    "\n",
    "    lst[debut], lst[sup] = lst[sup], lst[debut]\n",
    "\n",
    "    return sup\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7be240b4",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "feef601194b80660655c2f7a9ca056b7",
     "grade": false,
     "grade_id": "cell-21e1ef1b17be8a55",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "1. En tirant 30 listes aléatoires par longueur, avec des entiers entre 0 et 1000, afficher la complexité expérimentale de `quicksort` pour les longueurs de 1 à 4000, par pas de 200 (c'est un peu long, c'est normal). Utiliser la variable `ord2` pour la liste des ordonnées."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1dc74ad9",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "b88c7845ddd33895d7fd2d5c1a326f4a",
     "grade": true,
     "grade_id": "cell-1a5154f9d7a5d63e",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "abs2 = range(1, 4000, 200)\n",
    "ord2 = []\n",
    "\n",
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "36779fe0",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "c93debbc16bbcc89a2b1035810e4daaf",
     "grade": false,
     "grade_id": "cell-add60ded0cc9aadd",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "2. Tracer maintenant sur un même graphique les complexités expérimentale du tri bulle et du tri rapide."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "08ed2da3",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "b94f11f33189a5e8c1f27e761ac60d02",
     "grade": true,
     "grade_id": "cell-c0abfe48a46fa58b",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83697c8c",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "1aed3350f12e193eaa362e8ce8a93472",
     "grade": false,
     "grade_id": "cell-640fd608c7d0325c",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exercice 3 : mélange de tris\n",
    "En fait pour les petites listes, le tri bulle est souvent plus rapide que quicksort, car les petites listes sont presque triées.\n",
    "\n",
    "1. Écrivez une fonction `melange_tris` qui prend en argument une liste et trie la liste en place en agissant comme le tri rapide si la liste est de longueur strictement supérieur à 5, et comme le tri bulle sinon."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "933ada15",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "844deff2509a9381c2911b98fe031c3e",
     "grade": false,
     "grade_id": "cell-bf42b2367c868b6f",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4e51e484",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "c06dd1be319a556354beba277ac06fa0",
     "grade": true,
     "grade_id": "cell-b47099c737b0052a",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "import random\n",
    "random.seed(5)\n",
    "lst = [random.randint(1,100) for i in range(100)]\n",
    "copie = lst[:]\n",
    "melange_tris(lst)\n",
    "assert (lst == sorted(copie))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "abbdac6b",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "3d69e752bdc5381e463bd98a4226e6a5",
     "grade": false,
     "grade_id": "cell-763da3814cb5ac4e",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "2. En tirant 30 listes aléatoires par longueur, avec des entiers entre 0 et 1000, afficher la complexité expérimentale de `melange_tris` pour les longueurs de 1 à 4000, par pas de 200 (c'est un peu long, c'est normal). Utiliser la variable `ord3` pour la liste des ordonnées."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7d69244d",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "1a042c7d0698d834ce49d935a7edf1ef",
     "grade": true,
     "grade_id": "cell-550cbdb7829671ac",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "abs3 = range(1, 4000, 200)\n",
    "ord3 = []\n",
    "\n",
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b846f40c",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "f78385fd7dec82c406e37860af7c5732",
     "grade": false,
     "grade_id": "cell-f4d842492fa9e12c",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "3. Tracer maintenant sur un même graphique les complexités expérimentale du tri bulle, du tri rapide et du mélange des deux."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e9ce317d",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "f54bae43703c0f94ff60c2a6718c4ebc",
     "grade": true,
     "grade_id": "cell-61795e19d3349344",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "567fe1c1",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "d4b97b94ffb191857f60e284d662f948",
     "grade": false,
     "grade_id": "cell-cf7457e8bf18d6a9",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exercice 4 : ajout dans une liste `python`\n",
    "Le but de cet exercice est de constater que l'ajout d'un élément dans une liste python par la méthode `append` n'est pas toujours opération qui peut être considérée en temps constant.\n",
    "\n",
    "Pour celà, vous allez suivre les étapes suivantes:\n",
    "* créer une liste de 10 listes vides,\n",
    "* ajouter un à un les 500000 premiers entiers à chacune des listes précédente, en utilisant la méthode `append`, et en chronométrant le temps mis pour ajouter l'entier $i$ à l'ensemble des listes,\n",
    "* dessiner la courbe qui prend en abscisse les 500000 premiers entiers et en ordonnée le temps mis pour ajouter chacun de ces entiers aux dix listes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e20916e2",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "a2b5546cdb2bc82f149e7ee1252ed663",
     "grade": true,
     "grade_id": "cell-bd1853ba1045d5af",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}