Correction_examen_ALGO1_2019.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": "true"
   },
   "source": [
    "# Table of Contents\n",
    " <p><div class=\"lev1 toc-item\"><a href=\"#Correction-examen-ALGO1---Décembre-2019\" data-toc-modified-id=\"Correction-examen-ALGO1---Décembre-2019-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Correction examen ALGO1 - Décembre 2019</a></div><div class=\"lev1 toc-item\"><a href=\"#Problème-1-:-Programmation-dynamique\" data-toc-modified-id=\"Problème-1-:-Programmation-dynamique-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>Problème 1 : Programmation dynamique</a></div><div class=\"lev2 toc-item\"><a href=\"#Question-2.\" data-toc-modified-id=\"Question-2.-21\"><span class=\"toc-item-num\">2.1&nbsp;&nbsp;</span>Question 2.</a></div><div class=\"lev2 toc-item\"><a href=\"#Question-3.\" data-toc-modified-id=\"Question-3.-22\"><span class=\"toc-item-num\">2.2&nbsp;&nbsp;</span>Question 3.</a></div><div class=\"lev2 toc-item\"><a href=\"#Question-4.\" data-toc-modified-id=\"Question-4.-23\"><span class=\"toc-item-num\">2.3&nbsp;&nbsp;</span>Question 4.</a></div><div class=\"lev2 toc-item\"><a href=\"#Question-5.\" data-toc-modified-id=\"Question-5.-24\"><span class=\"toc-item-num\">2.4&nbsp;&nbsp;</span>Question 5.</a></div><div class=\"lev1 toc-item\"><a href=\"#Problème-3-:-Morito\" data-toc-modified-id=\"Problème-3-:-Morito-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span>Problème 3 : Morito</a></div><div class=\"lev2 toc-item\"><a href=\"#Question-1.-echanger\" data-toc-modified-id=\"Question-1.-echanger-31\"><span class=\"toc-item-num\">3.1&nbsp;&nbsp;</span>Question 1. <code>echanger</code></a></div><div class=\"lev2 toc-item\"><a href=\"#Question-2.-morito\" data-toc-modified-id=\"Question-2.-morito-32\"><span class=\"toc-item-num\">3.2&nbsp;&nbsp;</span>Question 2. <code>morito</code></a></div><div class=\"lev3 toc-item\"><a href=\"#Question-3.-Exemple\" data-toc-modified-id=\"Question-3.-Exemple-321\"><span class=\"toc-item-num\">3.2.1&nbsp;&nbsp;</span>Question 3. Exemple</a></div><div class=\"lev3 toc-item\"><a href=\"#Question-5.-Complexité-temporelle-?\" data-toc-modified-id=\"Question-5.-Complexité-temporelle-?-322\"><span class=\"toc-item-num\">3.2.2&nbsp;&nbsp;</span>Question 5. Complexité temporelle ?</a></div><div class=\"lev1 toc-item\"><a href=\"#Conclusion\" data-toc-modified-id=\"Conclusion-4\"><span class=\"toc-item-num\">4&nbsp;&nbsp;</span>Conclusion</a></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Correction examen ALGO1 - Décembre 2019\n",
    "\n",
    "- [Page du cours](https://perso.crans.org/besson/teach/info1_algo1_2019/) : https://perso.crans.org/besson/teach/info1_algo1_2019/\n",
    "- Magistère d'Informatique (L3 SIF) & L3 Maths de Rennes - ENS Rennes - Année 2019/2020\n",
    "- Intervenants :\n",
    "  + Cours : [Lilian Besson](https://perso.crans.org/besson/) (info) et [François Schwarzentruber](http://people.irisa.fr/Francois.Schwarzentruber/math1_algo1_2019/) (maths)\n",
    "  + Travaux dirigés : [Raphaël Truffet](http://perso.eleves.ens-rennes.fr/people/Raphael.Truffet/) (info) et [Léo Henry](http://perso.eleves.ens-rennes.fr/people/leo.henry/) (maths)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Problème 1 : Programmation dynamique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img width=\"50%\" src=\"Probleme2_Q2Q3.png\"></img>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On va représenter les dominos et les chaînes de domino de façon naïve :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "exemple_dominos = [\n",
    "    (\"A\", \"H\"),\n",
    "    (\"A\", \"Z\"),\n",
    "    (\"K\", \"V\"),\n",
    "    (\"H\", \"K\"),\n",
    "    (\"Z\", \"V\"),\n",
    "    (\"V\", \"X\"),\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 2.\n",
    "\n",
    "On peut implémenter l'algorithme de \"programmation dynamique\" naïvement :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculer_tableau_C(dominos):\n",
    "    n = len(dominos)\n",
    "    x = [D[0] for D in dominos]\n",
    "    y = [D[1] for D in dominos]\n",
    "    C = [0] * n\n",
    "    C[0] = 1\n",
    "    for i in range(1, n):\n",
    "        meilleur = 1\n",
    "        for j in range(0, i-1 + 1):\n",
    "            if y[j] == x[i] and C[j] + 1 > meilleur:\n",
    "                meilleur = C[j] + 1\n",
    "        C[i] = meilleur\n",
    "    return C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et par exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 1, 2, 2, 3]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculer_tableau_C(exemple_dominos)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def longueur_sous_chaine_la_plus_longue(dominos):\n",
    "    return max(calculer_tableau_C(dominos))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et par exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "longueur_sous_chaine_la_plus_longue(exemple_dominos)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 4.\n",
    "On va juste réécrire la fonction de la question 2, en ajoutant de l'affichage :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculer_tableau_C_verbose(dominos):\n",
    "    n = len(dominos)\n",
    "    x = [D[0] for D in dominos]\n",
    "    y = [D[1] for D in dominos]\n",
    "    C = [0] * n\n",
    "    C[0] = 1\n",
    "    i = 0\n",
    "    print(f\"- C[{i+1}] = {C[i]}.\")\n",
    "    for i in range(1, n):\n",
    "        meilleur = 1\n",
    "        list_of_possible_j = []\n",
    "        list_of_values_in_max = [1]\n",
    "        for j in range(0, i-1 + 1):\n",
    "            if y[j] == x[i] and C[j] + 1 > meilleur:\n",
    "                meilleur = C[j] + 1\n",
    "                list_of_possible_j.append(j)\n",
    "                list_of_values_in_max.append(C[j] + 1)\n",
    "        C[i] = meilleur\n",
    "        if len(list_of_possible_j) > 1:\n",
    "            s1 = \", \".join(f\"C[{j+1}]+1\" for j in list_of_possible_j)\n",
    "            s2 = \" et \".join(f\"{j+1}-{i+1}\" for j in list_of_possible_j)\n",
    "            print(f\"- C[{i+1}] = max(1, {s1}) = {C[i]} (les couples {s2} sont compatibles).\")\n",
    "        elif len(list_of_possible_j) == 1:\n",
    "            j = list_of_possible_j[0]\n",
    "            print(f\"- C[{i+1}] = max(1, C[{j+1}]+1) = {C[i]} (les dés {j+1} et {i+1} sont compatibles).\")\n",
    "        else:\n",
    "            print(f\"- C[{i+1}] = {C[i+1]} (il n'y pas de dé compatible à gauche de la {i+1}ème pièce).\")\n",
    "    return C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et par exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "- C[1] = 1.\n",
      "- C[2] = 0 (il n'y pas de dé compatible à gauche de la 2ème pièce).\n",
      "- C[3] = 0 (il n'y pas de dé compatible à gauche de la 3ème pièce).\n",
      "- C[4] = max(1, C[1]+1) = 2 (les dés 1 et 4 sont compatibles).\n",
      "- C[5] = max(1, C[2]+1) = 2 (les dés 2 et 5 sont compatibles).\n",
      "- C[6] = max(1, C[3]+1, C[5]+1) = 3 (les couples 3-6 et 5-6 sont compatibles).\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1, 1, 1, 2, 2, 3]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculer_tableau_C_verbose(exemple_dominos)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 5.\n",
    "\n",
    "On va avoir besoin d'une fonction `argmax` :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "def argmax(tableau):\n",
    "    position = 0\n",
    "    valeur = tableau[position] # Invariant: max(T[0],...,T[i])\n",
    "    for i in range(1, len(tableau)):\n",
    "        if tableau[i] > valeur:\n",
    "            valeur = tableau[i]\n",
    "            # Invariant: valeur' = max(T[0],...,T[i+1]) = max(valeur, T[i+1])\n",
    "            position = i\n",
    "    return position"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "argmax([1, 1, 1, 2, 2, 3])\n",
    "argmax([1, 1, 2, 2, 3, 1])\n",
    "argmax([1, 2, 2, 3, 1, 1])\n",
    "argmax([2, 2, 3, 1, 1, 1])\n",
    "argmax([2, 3, 1, 1, 1, 2])\n",
    "argmax([3, 1, 1, 1, 2, 2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour chaque $i$, il faut mémoriser le meilleur dé $j$ à mettre à gauche de $D[i]$.\n",
    "\n",
    "Puis on prend le $i$ qui maximise $C[i]$, et on compose la sous-chaı̂ne optimale de droite à gauche : $i$, puis $J[i]$, puis $J[J[i]]$ etc, jusqu’à tomber sur un $0$.\n",
    "\n",
    "Cela donne l'algorithme suivant :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculer_sous_chaine_longueur_maximale(dominos):\n",
    "    n = len(dominos)\n",
    "    x = [D[0] for D in dominos]\n",
    "    y = [D[1] for D in dominos]\n",
    "    C = [0] * n\n",
    "    J = [0] * n\n",
    "    C[0] = 1\n",
    "    J[0] = 0\n",
    "    for i in range(1, n):\n",
    "        meilleur = 1\n",
    "        for j in range(0, i-1 + 1):\n",
    "            if y[j] == x[i] and C[j] + 1 > meilleur:\n",
    "                meilleur = C[j] + 1\n",
    "                J[i] = j\n",
    "        C[i] = meilleur\n",
    "    i_maximisant_C = argmax(C)\n",
    "    i = i_maximisant_C\n",
    "    chaine_maximale = [i]\n",
    "    while J[i] != 0:\n",
    "        chaine_maximale.append(J[i])\n",
    "        i = J[i]\n",
    "    chaine = [dominos[i] for i in chaine_maximale[::-1]]\n",
    "    print(f\"Une chaine de longueur maximale = {max(C)} a été trouvée :\")\n",
    "    print(\", \".join(f\"[{d[0]}|{d[1]}]\" for d in chaine))\n",
    "    return chaine_maximale, chaine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et par exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Une chaine de longueur maximale = 3 a été trouvée :\n",
      "[A|Z], [Z|V], [V|X]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "([5, 4, 1], [('A', 'Z'), ('Z', 'V'), ('V', 'X')])"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculer_sous_chaine_longueur_maximale(exemple_dominos)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Problème 3 : Morito"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 1. `echanger`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "def echanger(tableau, i, j):\n",
    "    tmp = tableau[i]\n",
    "    tableau[i] = tableau[j]\n",
    "    tableau[j] = tmp\n",
    "    # en Python, on peut aussi faire\n",
    "    # tableau[i], tableau[j] = tableau[j], tableau[i]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 2. `morito`\n",
    "\n",
    "On implémente l'algorithme \"mystère\" :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "def morito(tableau, verb=False):\n",
    "    n = len(tableau)\n",
    "    échangé = True\n",
    "    while échangé:\n",
    "        échangé = False\n",
    "        if verb: print(\"Début pour croissant...\")\n",
    "        for i in range(0, n-2 + 1):\n",
    "            if verb: print(f\"  Tableau = {tableau} et i = {i}\")\n",
    "            if tableau[i] > tableau[i+1]:\n",
    "                if verb: print(f\"    T[{i}] = {tableau[i]} > {tableau[i+1]} = T[{i+1}] sont échangés\")\n",
    "                echanger(tableau, i, i+1)\n",
    "                échangé = True\n",
    "        \n",
    "        if verb: print(\"Début pour décroissant...\")\n",
    "        for i in range(n-2, 0 - 1, -1):\n",
    "            if verb: print(f\"  Tableau = {tableau} et i = {i}\")\n",
    "            if tableau[i] > tableau[i+1]:\n",
    "                if verb: print(f\"    T[{i}] = {tableau[i]} > {tableau[i+1]} = T[{i+1}] sont échangés\")\n",
    "                echanger(tableau, i, i+1)\n",
    "                échangé = True\n",
    "    if verb: print(\"Pas d'échange dans les deux parcours, l'algorithme s'arrête là.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 3. Exemple\n",
    "Par exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[16, 18, 19, 12, 2019]\n",
      "[12, 16, 18, 19, 2019]\n"
     ]
    }
   ],
   "source": [
    "tableau = [16, 18, 19, 12, 2019]\n",
    "print(tableau)\n",
    "\n",
    "morito(tableau)\n",
    "print(tableau)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[16, 18, 19, 12, 2019]\n",
      "Début pour croissant...\n",
      "  Tableau = [16, 18, 19, 12, 2019] et i = 0\n",
      "  Tableau = [16, 18, 19, 12, 2019] et i = 1\n",
      "  Tableau = [16, 18, 19, 12, 2019] et i = 2\n",
      "    T[2] = 19 > 12 = T[3] sont échangés\n",
      "  Tableau = [16, 18, 12, 19, 2019] et i = 3\n",
      "Début pour décroissant...\n",
      "  Tableau = [16, 18, 12, 19, 2019] et i = 3\n",
      "  Tableau = [16, 18, 12, 19, 2019] et i = 2\n",
      "  Tableau = [16, 18, 12, 19, 2019] et i = 1\n",
      "    T[1] = 18 > 12 = T[2] sont échangés\n",
      "  Tableau = [16, 12, 18, 19, 2019] et i = 0\n",
      "    T[0] = 16 > 12 = T[1] sont échangés\n",
      "Début pour croissant...\n",
      "  Tableau = [12, 16, 18, 19, 2019] et i = 0\n",
      "  Tableau = [12, 16, 18, 19, 2019] et i = 1\n",
      "  Tableau = [12, 16, 18, 19, 2019] et i = 2\n",
      "  Tableau = [12, 16, 18, 19, 2019] et i = 3\n",
      "Début pour décroissant...\n",
      "  Tableau = [12, 16, 18, 19, 2019] et i = 3\n",
      "  Tableau = [12, 16, 18, 19, 2019] et i = 2\n",
      "  Tableau = [12, 16, 18, 19, 2019] et i = 1\n",
      "  Tableau = [12, 16, 18, 19, 2019] et i = 0\n",
      "Pas d'échange dans les deux parcours, l'algorithme s'arrête là.\n",
      "[12, 16, 18, 19, 2019]\n"
     ]
    }
   ],
   "source": [
    "tableau = [16, 18, 19, 12, 2019]\n",
    "print(tableau)\n",
    "\n",
    "morito(tableau, verb=True)\n",
    "print(tableau)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 5. Complexité temporelle ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Dans le meilleur cas, l'algorithme s'exécute en temps linéaire, ie., $\\mathcal{O}(n)$ si $n$ est la longueur du tableau $T$. Le meilleur cas correspond à un tableau trié par ordre croissant."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Pour des tableaux triés :\n",
      "Pour n = 100, l'algorithme morito prends le temps suivant\n",
      "16.7 µs ± 1.56 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n",
      "Pour n = 1000, l'algorithme morito prends le temps suivant\n",
      "187 µs ± 6.52 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n",
      "Pour n = 10000, l'algorithme morito prends le temps suivant\n",
      "2.04 ms ± 78.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n",
      "Pour n = 100000, l'algorithme morito prends le temps suivant\n",
      "21.9 ms ± 1.31 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "print(\"Pour des tableaux triés par ordre croissant :\")\n",
    "for n in [100, 1000, 10000, 100000]:\n",
    "    print(f\"Pour n = {n}, l'algorithme morito prend le temps suivant\")\n",
    "    %timeit morito(list(range(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ce petit exemple montre que la complexité temporelle empirique semble bien linéaire : multiplier $n$ par $10$ multiplie le temps de calcul par $10$ aussi !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Dans le cas moyen, l'algorithme s'exécute en temps quadratique, ie., $\\mathcal{O}(n^2)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy.random as rd\n",
    "\n",
    "def tableau_aleatoire(n):\n",
    "    return rd.randint(-1000, 1000, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Pour des tableaux aléatoires :\n",
      "Pour n = 100, l'algorithme morito prend le temps suivant\n",
      "3 ms ± 189 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "Pour n = 1000, l'algorithme morito prend le temps suivant\n",
      "287 ms ± 9.97 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "Pour n = 10000, l'algorithme morito prend le temps suivant\n",
      "30.5 s ± 1.45 s per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "print(\"Pour des tableaux aléatoires :\")\n",
    "for n in [100, 1000, 10000]:\n",
    "    print(f\"Pour n = {n}, l'algorithme morito prend le temps suivant\")\n",
    "    %timeit morito(tableau_aleatoire(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ce petit exemple montre que la complexité temporelle empirique semble bien quadratique : multiplier $n$ par $10$ multiplie le temps de calcul par $10^2=100$ !\n",
    "(le temps est plus long que pour le pire cas ci dessous, mais c'est à cause du temps pris par le calcul d'un tableau aléatoire, pas le reste)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Dans le pire cas, l'algorithme s'exécute aussi en temps quadratique, ie., $\\mathcal{O}(n^2)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Pour des tableaux triés par ordre décroissant :\n",
      "Pour n = 100, l'algorithme morito prend le temps suivant\n",
      "2.18 ms ± 324 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "Pour n = 1000, l'algorithme morito prend le temps suivant\n",
      "203 ms ± 41.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
      "Pour n = 10000, l'algorithme morito prend le temps suivant\n",
      "20.4 s ± 2.44 s per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "print(\"Pour des tableaux triés par ordre décroissant :\")\n",
    "for n in [100, 1000, 10000]:\n",
    "    print(f\"Pour n = {n}, l'algorithme morito prend le temps suivant\")\n",
    "    %timeit morito(list(range(n))[::-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ce petit exemple montre que la complexité temporelle empirique semble bien quadratique : multiplier $n$ par $10$ multiplie le temps de calcul par $10^2=100$ !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Conclusion\n",
    "\n",
    "- Regardez aussi [la correction papier]() au partiel (envoyée par mail).\n",
    "\n",
    "- Les autres problèmes pourraient aussi être implémentés, mais :\n",
    "\n",
    "  + [le notebook du cours #8 sur les flots traitent déjà le problème 4](https://perso.crans.org/besson/teach/info1_algo1_2019/notebooks/CoursMagistral_8.html)\n",
    "  + le problème 2 ne demande pas de proposer un algorithme, mais les arbres rouge-noir peuvent être implémentés sans trop de difficultés, et on pourrait tester empiriquement les différents points du problème 2. Voir par exemple [des implémentations en Python](https://duckduckgo.com/?q=code+for+red-black+tree+in+python&t=canonical&ia=web), notamment celle ci : [github.com/stanislavkozlovski/Red-Black-Tree](https://github.com/stanislavkozlovski/Red-Black-Tree)."
   ]
  }
 ],
 "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"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "297.717px",
    "width": "251.5px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": false,
   "threshold": 4,
   "toc_cell": true,
   "toc_section_display": "block",
   "toc_window_display": true
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}