06-recherche.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3801ecc6",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<div style='width:20em'><img src='img/logo-igm.png'></div>\n",
    "<div style='font-size:larger'><strong>Algorithmique et programmation 2</strong><br>\n",
    "L1 Mathématiques - L1 Informatique<br>\n",
    "Semestre 2\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e974c2a",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "# Algorithmes de recherche dans une liste"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99e24772",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Problème 1 : recherche dans une liste quelconque\n",
    "\n",
    "### Énoncé du problème\n",
    "\n",
    "Étant donnée une liste `lst` et un élément `x`, `lst` contient-elle `x` ?\n",
    "\n",
    "- Problème extrêmement important\n",
    "- Sous une forme ou une autre, résolu des millions de fois par jour\n",
    "- En Python : `x in lst`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8cc18c0f",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Algorithme : recherche exhaustive (itérative)\n",
    "\n",
    "- Pour chaque élément `elem` de `lst`\n",
    "    - Si `elem` vaut `x`, répondre `True`\n",
    "- À la fin du parcours, répondre `False`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fac18618",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Implémentation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e232e0ca",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def rech_exh_iter(lst, x):\n",
    "    for elem in lst:\n",
    "        if elem == x:\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e1f43c06",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "lst = list(range(10))\n",
    "rech_exh_iter(lst, 9), rech_exh_iter(lst, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ecced2d",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Preuve de correction\n",
    "    \n",
    "Invariant : si $k$ est le nombre de tours de boucles déjà réalisé, `lst[:k]` ne contient pas `x`.\n",
    "\n",
    "- Vrai quand aucune itération n'a été réalisée ($k = 0$).\n",
    "- Supposons la propriété vraie après $k$ itérations.\n",
    "    - Si `len(lst)` est $k$, la boucle s'arrête et le résultat est `False`. Par hypothèse de récurrence, `lst[:k] == lst` ne contient pas `x`.\n",
    "    - Sinon, il existe un élément `lst[k]`. Si `lst[k] == x` le résultat est `True` et il n'y a pas d'autre itération. Sinon on a bien que `lst[:k+1]` ne contient pas `x`.\n",
    "\n",
    "On en déduit que l'algorithme calcule le bon résultat."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c776ed12",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Complexité\n",
    "\n",
    "- En temps : $O(n)$ dans le pire cas, où $n$ est `len(lst)`.\n",
    "    - Preuve : maximum $n$ itérations, chaque itération en $O(1)$.\n",
    "- En espace : $O(1)$ espace supplémentaire\n",
    "    - On ne compte pas la liste `lst` elle-même\n",
    "    - On admet que la gestion de la boucle n'occupe qu'un espace constant"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de617d80",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Algorithme : recherche exhaustive (récursive)\n",
    "\n",
    "- Si `lst` est vide, répondre `False`\n",
    "- Sinon, si `lst[0]` vaut `x`, répondre `True`\n",
    "- Sinon, rechercher `x` dans la liste privée de son premier élement"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00f015e0",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Implémentation (version naïve)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ce3d572d",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def rech_exh_rec(lst, x):\n",
    "    if len(lst) == 0:\n",
    "        return False\n",
    "    elif lst[0] == x:\n",
    "        return True\n",
    "    else:\n",
    "        return rech_exh_rec(lst[1:], x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "51c51f86",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "lst = list(range(10))\n",
    "rech_exh_rec(lst, 9), rech_exh_rec(lst, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "381e9231",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Preuve de correction\n",
    "    \n",
    "Par récurrence sur la taille de la liste :\n",
    "- Résultat correct sur une liste vide\n",
    "- Supposons la propriété vraie après sur toute liste de taille au plus $k$, supposont `lst` de taille $k+1$\n",
    "    - Si `lst[0] == x` le résultat est correct\n",
    "    - Sinon, par HR l'appel récursif renvoie le bon résultat sur `lst[1:]`, et comme `lst[0] != x` c'est aussi le bon résultat sur `lst` toute entière"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "024a0f67",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Complexité\n",
    "\n",
    "- En temps : $O(n^2)$ dans le pire cas, où $n$ est `len(lst)`.\n",
    "    - Preuve : complexité majorée par la suite $T(0) = c$, $T(n) = c.(n-1) + T(n-1)$\n",
    "    - Suite déjà rencontrée en cours : $T(n) \\in O(n^2)$\n",
    "    - Coupable : calcul de `lst[1:]` !\n",
    "- En espace : $O(n^2)$ dans le pire cas\n",
    "    - Gestion de la pile : $O(1)$ par appel\n",
    "    - Recopie de la liste à chaque appel !\n",
    "    - Même calcul que ci-dessus"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc0fbf6b",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Rappel :\n",
    "\n",
    "$$\n",
    "\\sum_{i=0}^{n-1} i = \\big( 0 + 1 + \\cdots + (n-2) + (n-1) \\big) = \\frac{n(n-1)}{2} \\in O(n^2)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "36694ec8",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Implémentation récursive (version améliorée)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2472a791",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def rech_exh_rec_bis(lst, x, i=0):\n",
    "    if len(lst) == i:\n",
    "        return False\n",
    "    elif lst[i] == x:\n",
    "        return True\n",
    "    else:\n",
    "        return rech_exh_rec_bis(lst, x, i+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2ac087c6",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "lst = list(range(10))\n",
    "rech_exh_rec_bis(lst, 9), rech_exh_rec_bis(lst, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3c4ace41",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Preuve de correction\n",
    "    \n",
    "Par récurrence sur `len(lst) - i` : résultat correct sur `lst[i:]` \n",
    "- Propriété vraie si `len(lst) - i` nul : la fonction renvoie `False` et `lst[i:]` est bien vide\n",
    "- Supposons la propriété vraie pour `len(lst) - i` au plus $k$, soit `len(lst) - i` $=k+1$\n",
    "    - Si `lst[i] == x` le résultat est correct\n",
    "    - Sinon, par HR l'appel récursif renvoie le bon résultat sur `lst[i+1:]`, et comme `lst[i] != x` c'est aussi le cas sur `lst[i:]`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "26a65600",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Complexité\n",
    "\n",
    "- En temps : $O(n)$ dans le pire cas, où $n$ est `len(lst)`.\n",
    "    - Preuve : complexité majorée par la suite $T(0) = c$, $T(n) = c + T(n-1)$\n",
    "- En espace : $O(n)$ dans le pire cas\n",
    "    - Gestion de la pile : $O(1)$ par appel\n",
    "    - Même calcul que ci-dessus"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "caab7220",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Chronométrage\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ed0bb2b9",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "def trace_courbes(abscisses, series,\n",
    "                  title='', xlabel='', ylabel=''):\n",
    "    \"\"\"Pour chaque couple (nom, ordonnées) de la liste series, trace la courbe\n",
    "    des ordonnees avec la legende nom dans matplotlib. L'abscisse des points\n",
    "    est donnée par la liste abscisses.\n",
    "    Le paramètres optionnels title, xlabel et ylabel donnent le titre du\n",
    "    graphique et les étiquettes des axes x et y.\"\"\"\n",
    "    for nom, donnees in series:\n",
    "        plt.plot(abscisses, donnees, label=nom)\n",
    "    plt.title(title)\n",
    "    plt.xlabel(xlabel)\n",
    "    plt.ylabel(ylabel)\n",
    "    plt.legend()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "213a810a",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "from timeit import repeat\n",
    "\n",
    "def chrono(fonction, args, nombre=100000, reps=5):\n",
    "    \"\"\"Renvoie le temps d'exécution en secondes de 'nombre' répétitions de\n",
    "    l'appel fonction(*args).\"\"\"\n",
    "\n",
    "    # le plus simple est de passer à la fonction timeit une fonction sans\n",
    "    # argument, donc on doit définir une fonction auxiliaire\n",
    "    def f():\n",
    "        # passe un par un chaque argument de la liste args à\n",
    "        # la fonction\n",
    "        return fonction(*args)\n",
    "\n",
    "    def avg(lst):\n",
    "        return sum(lst) / len(lst)\n",
    "\n",
    "    return avg(repeat(f, number=nombre, repeat=reps))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67a55562",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def chrono_et_trace_rech(xs, \n",
    "                         fs=(rech_exh_iter, rech_exh_rec, rech_exh_rec_bis),\n",
    "                         nombre=100000, reps=5):\n",
    "    ys = []\n",
    "    for f in fs:\n",
    "        times = []\n",
    "        for x in xs:\n",
    "            lst = list(range(x))\n",
    "            times.append([chrono(f, [lst, x], nombre, reps)])\n",
    "        ys.append((f.__name__, times))\n",
    "    trace_courbes(xs, ys)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "48bd8776",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "xs = list(range(0, 1001, 100))\n",
    "chrono_et_trace_rech(xs, (rech_exh_iter, rech_exh_rec, rech_exh_rec_bis), nombre=100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "53a7b88e",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "xs = list(range(0, 1001, 100))\n",
    "chrono_et_trace_rech(xs, (rech_exh_iter, rech_exh_rec_bis), nombre=1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "021c7cde",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Peut-on faire mieux ?\n",
    "\n",
    "On peut démontrer qu'il faut faire au moins `len(lst)` accès à la liste pour répondre correctement  \n",
    "*(borne inférieure de complexité sur le **problème**)*\n",
    "\n",
    "- Soit `f` une fonction de recherche effectuant moins de `len(lst)` accès sur au moins une liste `lst`\n",
    "- Soit `x` un élément n'appartenant pas à `lst`, `f(lst, x)` renvoie forcément `False`\n",
    "- Soit `i` l'indice d'un élément non vu\n",
    "    - Si l'on avait remplacé `lst[i]` par `x` la fonction aurait aussi renvoyé `False` (résultat incorrect)\n",
    "  \n",
    "**Conclusion :** si on ne sait rien sur la liste, on ne peut\n",
    "pas faire mieux que `len(lst)` comparaisons !"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "79c794fa",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Problème 2 : recherche dans une liste triée\n",
    "\n",
    "### Énoncé du problème\n",
    "\n",
    "Étant donnée une liste `lst` d'éléments **comparables** deux à deux, **triée** dans l'ordre croissant, et un élément `x`, `lst` contient-elle `x` ?\n",
    "\n",
    "Qu'est-ce qui change par rapport au problème précédent ?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4af2c2f9",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Préambule : jeu de la devinette\n",
    "\n",
    "**Objectif :** deviner un nombre entier compris entre 1 et $N$, en posant le moins de questions possible. \n",
    "\n",
    "Trois personnes jouent :\n",
    "- Devinante (**D**)\n",
    "- Répondante (**R**)\n",
    "- Arbitre (**A**)\n",
    "\n",
    "On commence par prendre $N = 15$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78411423",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Déroulement :\n",
    "\n",
    "1.  **R** choisit un entier $n$ entre 1 et $15$ et le\n",
    "    communique secrètement à **A**.\n",
    "\n",
    "2.  **D** propose à **R** un entier $a$ entre 1 et 15.\n",
    "\n",
    "3.  **R** répond \"égal\" si $n = a$, \"plus petit\" si $n < a$, \"plus grand\" si\n",
    "    $n > a$. **A** vérifie que la réponse est honnête.\n",
    "\n",
    "4.  Si **D** a proposé $a = n$, la partie est terminée, **A** annonce le score. Sinon,\n",
    "    on recommence au point 2.\n",
    "\n",
    "But de **D** : deviner $n$ en faisant le moins possible de\n",
    "propositions (en comptant la proposition finale, pour laquelle $a = n$). Le\n",
    "nombre de propositions est appelé *score* de la partie. **D** souhaite donc\n",
    "gagner avec le plus *petit* score possible."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad4c961b",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Travail demandé\n",
    "\n",
    "1. Faites des groupes de 3 et jouez quelques parties\n",
    "2. Décrivez une stratégie pour **D** pour gagner\n",
    "   *toutes* les parties avec un score le plus petit possible. \n",
    "3. Quel est le meilleur score que **D** est **sûre** d'atteindre (*score maximal pour $N = 15$*) ?\n",
    "4. Quel est le meilleur score pour $N = 31$ ? Et pour $N = 50$ ? Et pour $N$\n",
    "   quelconque ?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "50e6d6ea",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Bilan\n",
    "\n",
    "- En jouant \"bien\", quand $N = 15$, **D** peut garantir un score maximal de 4. \n",
    "- Stratégie : si les nombres possibles sont les $g \\leq a \\leq d$, on propose $(g + d) / 2$ (arrondi comme on veut).\n",
    "- Pourquoi ça marche : 15 possibilités au début, $\\leq 7$ après 1 question, $\\leq 3$ après 2 questions, $\\leq 1$ après 3 questions, trouvé à la quatrième.\n",
    "- Quand $N = 31$, 5 questions suffisent. Quand $N = 50$, 6 questions. Et pour $N$ quelconque... voir la suite."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bfdbeabd",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Retour aux listes\n",
    "\n",
    "**Idée d'algorithme (ou *stratégie*) :** procéder par *dichotomie*\n",
    "\n",
    "- Si on voit un élément trop petit, inutile de chercher avant\n",
    "- Si on voit un élément trop grand, inutile de chercher après\n",
    "- Pour éliminer le plus de cas possible on regarde toujours au\n",
    "    milieu de l'intervalle"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0401042b",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Exemple :** on recherche l'élément `112`\n",
    "\n",
    "![Recherche dichotomique](img/dicho-0.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9da7c66a",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "`m = (g + d) // 2 = 9`\n",
    "\n",
    "![Recherche dichotomique](img/dicho-1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3bd7c0b9",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "`lst[9] < 112` : on continue la recherche à droite de `m`\n",
    "\n",
    "![Recherche dichotomique](img/dicho-2.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "374053c6",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "`g = m + 1 = 10`\n",
    "\n",
    "![Recherche dichotomique](img/dicho-3.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46f0d649",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "`m = (g + d) // 2 = 14`\n",
    "\n",
    "![Recherche dichotomique](img/dicho-4.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "50dc19d2",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "`lst[14] > 112` : on continue la recherche à gauche de `m`\n",
    "\n",
    "![Recherche dichotomique](img/dicho-5.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5bcc76e2",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "`d = m - 1 = 13`\n",
    "\n",
    "![Recherche dichotomique](img/dicho-6.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e88a4e5",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "`m = (g + d) // 2 = 11`\n",
    "\n",
    "![Recherche dichotomique](img/dicho-7.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8521490d",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "`lst[11] < 112` : on continue la recherche à droite de `m`\n",
    "\n",
    "![Recherche dichotomique](img/dicho-8.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7187f381",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "`g = m + 1 = 12`\n",
    "\n",
    "![Recherche dichotomique](img/dicho-9.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "addb6f8f",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "`m = (g + d) // 2 = 12`\n",
    "\n",
    "![Recherche dichotomique](img/dicho-10.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "790747e1",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "`lst[12] < 112` : on continue la recherche à droite de `m`\n",
    "\n",
    "![Recherche dichotomique](img/dicho-11.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c11015df",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "`g = m + 1 = 13`\n",
    "\n",
    "![Recherche dichotomique](img/dicho-12.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d84653a9",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "`m = (g + d) // 2 = 13`, et `lst[13] == 112`\n",
    "\n",
    "![Recherche dichotomique](img/dicho-13.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "743a97db",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Algorithme : recherche par dichotomie (itérative)\n",
    "\n",
    "Soient `lst` une liste croissante de `n` éléments, `x` un élément\n",
    "\n",
    "- Posons `g = 0`, `d = n - 1`\n",
    "- Tant que l'intervalle $[g, d]$ contient au moins un élément :\n",
    "    - Calculer `m = (g + d) // 2`\n",
    "    - Si `lst[m] == x`, répondre `True`\n",
    "    - Si `lst[m] < x`, fixer `g` à `m+1`\n",
    "    - Si `lst[m] > x`, fixer `d` à `m-1`\n",
    "- Si l'on sort de la boucle, répondre `False`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7774676",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Implémentation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1a368db4",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def dicho_iter(lst, x):\n",
    "    g, d = 0, len(lst) - 1\n",
    "    while g <= d:\n",
    "        m = (g + d) // 2\n",
    "        if lst[m] == x:\n",
    "            return True\n",
    "        elif lst[m] < x:\n",
    "            g = m + 1\n",
    "        else:\n",
    "            d = m - 1\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e45a4b3f",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "lst = list(range(10))\n",
    "dicho_iter(lst, 3), dicho_iter(lst, 3.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38286880",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Preuve de correction\n",
    "    \n",
    "Par récurrence sur le nombre de tours de boucle : en début d'itération, ni `lst[:g]` ni `lst[d+1:]` ne contiennent `x`\n",
    "- Propriété vraie après 0 itérations : `lst[:g]` et `lst[d+1:]` sont vides\n",
    "- Supposons la propriété vraie après `k` itérations. Si `lst[m] == x` la fonction renvoie un résultat correct et termine. Sinon :\n",
    "    - Si `lst[m] < x`, au début de l'itération suivante `g` vaut `m+1`. Or comme `lst` est croissante, tous les éléments d'indice au plus `g-1` sont inférieurs à `x` (et donc différents)\n",
    "    - Si `lst[m] > x`, au début de l'itération suivante `d` vaut `m-1`. Or comme `lst` est croissante, tous les éléments d'indice au moins `d+1` sont supérieurs à `x` (et donc différents)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "30d4f206",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Preuve de terminaison\n",
    "\n",
    "- La quantité `d - g` diminue strictement à chaque tour de boucle\n",
    "- La boucle s'arrête si `d - g` devient négatif ou nul\n",
    "- Donc le nombre de tours ne peut pas être infini"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d8dfbe4",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Complexité\n",
    "\n",
    "- Chaque tour de boucle prend un temps $O(1)$\n",
    "- Au début du premier tour de boucle, on cherche parmi `len(lst)` éléments (`d - g` vaut `len(lst) - 1`)\n",
    "- À chaque tour, on élimine une possibilité plus la moitié de ce qui reste (`d - g` décrémenté et divisé par deux)\n",
    "- Si `d - g <= 1` la boucle s'arrête à la fin du tour"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "36ee7920",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Parmi combien de nombres peut-on trouver à coup sûr en $k$ tours de boucle ?\n",
    "\n",
    "\\begin{array}{l|c|c|c|c|c|c|c}\n",
    "  \\hline\n",
    "  k & 1 & 2 & 3 & 4 & 5 & 6 & \\ldots \\\\\\hline\n",
    "  n & 1 & 3 & 7 & 15 & 31 & 63 & \\ldots\\\\\n",
    "  \\hline\n",
    "\\end{array}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "08d6071c",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "*Conjecture :* en $k$ tours on peut distinguer parmi $2^k - 1$ nombres\n",
    "\n",
    "- Preuve : par récurrence\n",
    "    - En 0 tours on peut distinguer parmi $ 2^0 - 1 = 0$ nombres\n",
    "    - Si on sait chercher parmi $2^k - 1$ en $k$ questions, on peut chercher parmi $2 (2^k - 1) + 1 = 2^{k+1} - 1$ nombres en $k+1$ questions\n",
    "- Suite déjà rencontrée dans le cours sur les tours de Hanoï"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e0163b6",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "*Conclusion :* Pour $n$ quelconque, on devra donc chercher au plus en $k$ tours où $k$ est\n",
    "  l'unique entier tel que :\n",
    "  \n",
    "\\begin{align*}\n",
    " & & 2^{k-1} - 1 & < n \\leq 2^k - 1 \\\\\n",
    "\\text{soit } & & 2^{k-1} & \\leq n < 2^k \\\\\n",
    "\\text{soit } & & k-1 & \\leq \\log_2 n < k \\\\\n",
    "\\text{soit } & & k = & \\lfloor \\log_2 n \\rfloor + 1\n",
    "\\end{align*}\n",
    "\n",
    "\n",
    "On obtient donc une complexité en\n",
    "$O(\\log_2(n))$ au pire"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "89498205",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "![Nombre de comparaisons](img/graphe-comparaisons.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "094e9e81",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Parenthèse : nombre de chiffres d'un nombre\n",
    "\n",
    "Soit $n$ un entier positif écrit en base 10.\n",
    "\n",
    "Combien de chiffres a-t-il ?\n",
    "\n",
    "- Un nombre à $k$ chiffres est compris entre $10^{k-1}$ et ${10^k}-1$\n",
    "- Le nombre de chiffres de $n$ est donc le plus petit $k$ tel que $10^{k-1} \\leq n \\leq {10^k}-1$\n",
    "- Comment calculer ce nombre ?\n",
    "  - On essaie tous les $k$ un par un, ou bien...\n",
    "  - On utilise la fonction $\\log_{10}$ (logarithme en base 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a17ce5f",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Proposition :** Tout nombre entier positif $n$ a exactement $\\lfloor \\log_{10}(n) \\rfloor + 1$ chiffres en base 10\n",
    "\n",
    "**Proposition (bis) :** Tout nombre entier positif $n$ peut être divisé au plus $\\lfloor \\log_{10}(n) \\rfloor + 1$ fois par $10$ avant d'obtenir $0$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d93b5e8b",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Liste des chiffres\n",
    "\n",
    "**Exercice / rappel :** Écrire une fonction (itérative ou récursive)\n",
    "`chiffres(n)` recevant un entier positif `n` et renvoyant la liste de ses\n",
    "chiffres (décimaux).\n",
    "\n",
    "Quelle est la complexité de cette fonction ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "29ac5a92",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def chiffres(n):\n",
    "    res = []\n",
    "    while n != 0:\n",
    "        n, r = n // 10, n % 10\n",
    "        res.append(r)\n",
    "    res.reverse()  # complexité O(len(res))\n",
    "    return res\n",
    "\n",
    "chiffres(1976)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "59968a5f",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def chiffres(n):\n",
    "    if n == 0:\n",
    "        return []\n",
    "    else:\n",
    "        n, r = n // 10, n % 10\n",
    "        res = chiffres(n)\n",
    "        res.append(r)\n",
    "        return res\n",
    "\n",
    "chiffres(1976)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d06d034e",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Complexité ??**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05052467",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Généralisation\n",
    "\n",
    "Soit $n$ un entier positif écrit **en base $b$**. Combien de chiffres a-t-il ?\n",
    "\n",
    "- Un nombre à $k$ chiffres est compris entre $b^{k-1}$ et ${b^k}-1$\n",
    "- Le nombre de chiffres de $n$ est donc le plus petit $k$ tel que $b^{k-1} \\leq n \\leq {b^k}-1$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "40527134",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "**Proposition :** Tout nombre entier positif $n$ a exactement $\\lfloor\n",
    "\\log_{b}(n) \\rfloor + 1$ chiffres en base $b$\n",
    "\n",
    "**Proposition (bis) :** Tout nombre entier positif $n$ peut être divisé au plus\n",
    "$\\lfloor \\log_{b}(n) \\rfloor + 1$ fois par $b$ avant d'obtenir $0$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1cd9d1a6",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Liste des chiffres en base $b$\n",
    "\n",
    "**Exercice / rappel :** Écrire une fonction (itérative ou récursive)\n",
    "`chiffres(n, base)` recevant un entier positif `n` et renvoyant la liste de ses\n",
    "chiffres en base `b`.\n",
    "\n",
    "Quelle est la complexité de cette fonction ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d2fbcae9",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def chiffres(n, base=10):\n",
    "    res = []\n",
    "    while n != 0:\n",
    "        n, r = n // base, n % base\n",
    "        res.append(r)\n",
    "    res.reverse()\n",
    "    return res\n",
    "\n",
    "chiffres(1976, 2), bin(1976)\n",
    "# peut-on prédire le nombre de chiffres ?\n",
    "# indice : 2**11 == 2048"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a7960e35",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def chiffres(n, base=10):\n",
    "    if n == 0:\n",
    "        return []\n",
    "    else:\n",
    "        n, r = n // base, n % base\n",
    "        res = chiffres(n, base)\n",
    "        res.append(r)\n",
    "        return res\n",
    "\n",
    "chiffres(1976, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "173decc9",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Complexité ??**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d6d7f3a",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Algorithme : recherche par dichotomie (récursive)\n",
    "\n",
    "Soient `lst` une liste croissante de `n` éléments, `x` un élément\n",
    "\n",
    "- Si la liste est vide, la réponse est `False`\n",
    "- Sinon :\n",
    "    - Calculer `m = len(lst) // 2`\n",
    "    - Si `lst[m] == x`, répondre `True`\n",
    "    - Si `lst[m] < x`, chercher dans `lst[m+1:]`\n",
    "    - Si `lst[m] > x`, chercher dans `lst[:m]`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "81caa63a",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Implémentation récursive (naïve)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f763d424",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def dicho_rec(lst, x):\n",
    "    if len(lst) == 0:\n",
    "        return False\n",
    "    m = len(lst) // 2\n",
    "    if lst[m] == x:\n",
    "        return True\n",
    "    elif lst[m] < x:\n",
    "        return dicho_rec(lst[m+1:], x)\n",
    "    else:\n",
    "        return dicho_rec(lst[:m], x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "328ad814",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "lst = list(range(10))\n",
    "dicho_rec(lst, 3), dicho_rec(lst, 3.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d005b99e",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "from callstats import CallRecorder\n",
    "\n",
    "@CallRecorder\n",
    "def dicho_rec_2(lst, x):\n",
    "    if len(lst) == 0:\n",
    "        return False\n",
    "    m = len(lst) // 2\n",
    "    if lst[m] == x:\n",
    "        return True\n",
    "    elif lst[m] < x:\n",
    "        return dicho_rec_2(lst[m+1:], x)\n",
    "    else:\n",
    "        return dicho_rec_2(lst[:m], x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "53d48955",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "from IPython.display import Image\n",
    "lst = list(range(100))\n",
    "g = dicho_rec_2(lst, 3.5).graph()\n",
    "Image(g.pipe(format='png'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75e8c0be",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Variante : avec des indices\n",
    "\n",
    "Soient `lst` une liste croissante de `n` éléments, `x` un élément, `g` et `d` deux indices\n",
    "\n",
    "- Si `g > d`, la réponse est `False`\n",
    "- Sinon :\n",
    "    - Calculer `m = (g + d) // 2`\n",
    "    - Si `lst[m] == x`, répondre `True`\n",
    "    - Si `lst[m] < x`, chercher entre `m+1` et `d`\n",
    "    - Si `lst[m] > x`, chercher entre `g` et `m-1`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6242a630",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Implémentation récursive (efficace)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dc749d31",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def dicho_rec_3(lst, x, g=0, d=None):\n",
    "    if d is None:\n",
    "        d = len(lst) - 1\n",
    "    if g > d:\n",
    "        return False\n",
    "    m = (g + d) // 2\n",
    "    if lst[m] == x:\n",
    "        return True\n",
    "    if lst[m] > x:\n",
    "        return dicho_rec_3(lst, x, g, m-1)\n",
    "    else:\n",
    "        return dicho_rec_3(lst, x, m+1, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5ecde734",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "lst = list(range(10))\n",
    "dicho_rec_3(lst, 3), dicho_rec_3(lst, 3.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a4afd8a",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Correction, terminaison, complexité de la version récursive\n",
    "\n",
    "TODO ! 😅"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57e229f0",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Chronométrage"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bd604f0c",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "xs = list(range(100, 10000, 50))\n",
    "#chrono_et_trace_rech(xs, (rech_exh_iter, dicho_iter, dicho_rec, dicho_rec_bis))\n",
    "chrono_et_trace_rech(xs, (dicho_iter, dicho_rec), nombre=10, reps=10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8158fbdb",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "xs = list(range(100, 1000000, 500))\n",
    "#chrono_et_trace_rech(xs, (rech_exh_iter, dicho_iter, dicho_rec, dicho_rec_bis))\n",
    "chrono_et_trace_rech(xs, (dicho_iter, dicho_rec_3), nombre=100, reps=10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b7fa3b0d",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Peut-on faire mieux ?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06923b78",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Retour sur le jeu de la devinette\n",
    "\n",
    "1.  **R** fait **semblant** de choisir un entier $n$ entre 1 et $15$.\n",
    "\n",
    "2.  **D** propose à **R** un entier $a$ entre 1 et 15.\n",
    "\n",
    "3.  **R** répond ce qu'elle veut. **A** vérifie que la réponse est cohérente avec les réponses précédentes.\n",
    "\n",
    "4.  Si **R** a répondu « égal », la partie est terminée, **A** annonce le score. Sinon,\n",
    "    on recommence au point 2.\n",
    "\n",
    "But de **D** : deviner $n$ en faisant le moins possible de\n",
    "propositions.  \n",
    "But de **R** : forcer **D** à poser le plus de questions possible."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "30928215",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Travail demandé\n",
    "\n",
    "1. Faites des groupes de 3 et jouez quelques parties\n",
    "2. Décrivez une stratégie pour **R** pour forcer **D** à poser le plus de questions possible.\n",
    "3. Quel est le meilleur score que **D** peut atteindre (*score minimal pour $N = 15$*) ?\n",
    "4. Quel est le meilleur score pour $N = 31$ ? Et pour $N = 50$ ? Et pour $N$\n",
    "   quelconque ?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "565e32c2",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Bilan\n",
    "\n",
    "- En jouant \"bien\", quand $N = 15$, **R** peut forcer un score minimal de 4. \n",
    "- Stratégie : toujours répondre de manière à conserver le plus grand nombre de possibilités.\n",
    "- Pourquoi ça marche : 15 possibilités au début, $\\geq 7$ après 1 question, $\\geq 3$ après 2 questions, $\\geq 1$ après 3 questions, trouvé à la quatrième.\n",
    "- Quand $N = 31$, 5 questions au minimum. Quand $N = 50$, 6 questions. Et pour $N$ quelconque... ?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5bd20a31",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Bilan final\n",
    "\n",
    "- La recherche d'élément dans une liste est un problème fondamental. \n",
    "- Quand la liste n'est pas triée, il n'existe pas de meilleur algorithme que la recherche exhaustive, en $O(n)$\n",
    "- Quand la liste est triée, il existe un algorithme très efficace : la recherche par dichotomie, en $O(\\log n)$\n",
    "    - On peut démontrer qu'il est impossible de faire mieux ! (argument du jeu de la devinette, phase 2)\n",
    "    - Plus d'informations en M1 info !"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "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.11.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}