Premiere/Theme05_Algorithmique/05_Dichotomie.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dichotomie\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*ou comment rechercher efficacement dans une liste triée ?*\n",
    "\n",
    "\n",
    "# Activité d'introduction\n",
    "## Jeu du *\"devine un nombre entre 1 et 100\"*\n",
    "Si je choisis un nombre entre 1 et 100, quelle est la stratégie optimale pour deviner ce nombre le plus vite possible ?  \n",
    "(à chaque étape, une indication (trop grand, trop petit) permet d'affiner la proposition suivante)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Réponse attendue :** la meilleure stratégie est de *couper en deux* à chaque fois l'intervalle d'étude. On démarre de 50, puis 75 ou 25, etc.\n",
    "\n",
    "\n",
    "Il convient toute fois de remettre en question cette méthode qui paraît *naturellement* optimale : si je propose 90 comme nombre de départ, j'ai certes moins de chance que le nombre soit entre 90 et 100, mais s'il l'est, j'ai gagné un gros avantage car mon nouvel intervalle est très réduit.\n",
    "\n",
    "On peut alors rappeler la notion d'**espérance probabiliste**.\n",
    "\n",
    "Exemple : \"On lance un dé, s'il tombe sur le 6 vous recevez 2 euros, sinon vous me donnez 1 euro. Voulez-vous jouer ?\" \n",
    "\n",
    "**Retour sur le jeu du choix du nombre**\n",
    "\n",
    "Le graphique ci-dessous représente le nombre de coups moyens (sur 10 000 parties simulées)\n",
    "\n",
    "![image](data/fig1.png)\n",
    "\n",
    "**Interprétations et remarques** \n",
    "- si le choix se porte *toujours* sur le nombre situé à la moitié de l'intervalle (0.5), le nombre de coups moyen avant la victoire (sur 10 000 parties) est environ 6.\n",
    "- si le choix se porte *toujours* sur le nombre situé à 90 % de l'intervalle (0.9), le nombre de coups moyen avant la victoire (sur 10 000 parties) est environ 11.\n",
    "- l'asymétrie de la courbe (qui devrait être symétrique) est due aux arrondis par défaut dans le cas de nombres non entiers.\n",
    "\n",
    "## Conclusion générale de l'activité d'introduction\n",
    "La stratégie optimale est de diviser en deux à chaque étape l'intervalle d'étude. On appelle cela une méthode par **dichotomie**, du grec ancien διχοτομία, dikhotomia (« division en deux parties »).\n",
    "\n",
    "La méthode de dichotomie fait partie des méthodes dites *«diviser pour mieux régner»*. \n",
    "\n",
    "Extrait de [Wikipedia](https://fr.wikipedia.org/wiki/Diviser_pour_r%C3%A9gner_(informatique)) :\n",
    "\n",
    "![](data/diviser_pour_regner.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithmes de recherche d'une valeur dans une liste triée\n",
    "\n",
    "**Préambule** : la méthode que nous allons utiliser implique que les valeurs ont été triées  auparavant.\n",
    "\n",
    "Si les valeurs ne sont pas triées (ou pas triables), cela peut vite être problématique.\n",
    "\n",
    "**Exemple :** pouvez-vous deviner la couleur à laquelle je pense ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "coul = [\"bleu\", \"jaune\", \"rouge\", \"vert\", \"violet\", \"marron\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*hormis le test de toutes les valeurs, aucune méthode efficace n'est possible.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans toute la suite, nous rechercherons un élément dans une liste d'entiers **triée** dans l'ordre croissant.  \n",
    "Considérons donc la liste L suivante : \n",
    "![image](fig0.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "L = [2, 3, 6, 7, 11, 14, 18, 19, 24]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'objectif est de définir un algorithme de recherche efficace d'une valeur arbitraire présente dans cette liste."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Méthode 1 : recherche par balayage\n",
    "C'est la méthode la plus intuitive : on essaie toutes les valeurs (par exemple, dans l'ordre croissant) jusqu'à trouver la bonne."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 1  \n",
    "Écrire un code permettant d'afficher l'indice de la valeur `14` dans la liste `L = [2, 3, 6, 7, 11, 14, 18, 19, 24]`.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "L = [2, 3, 6, 7, 11, 14, 18, 19, 24]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Correction :*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for k in range(len(L)):\n",
    "    if L[k] ==  14 :\n",
    "        return k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 2  \n",
    "Écrire une fonction `trouve(L, p)` qui renvoie l'indice d'une valeur `p` dans une liste `L `. Si la valeur `p` n'est pas trouvée, on renverra `\"non trouvé\"`.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def trouve(L, p) :\n",
    "    for k in range(len(L)) :\n",
    "        if L[k] :\n",
    "            return k\n",
    "    return \"non trouvé\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "L = [\"lundi\", \"mardi\", \"mercredi\", \"jeudi\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "trouve(L,\"mardi\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'non trouvé'"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "trouve(L,\"samedi\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Complexité de la méthode\n",
    "\n",
    "Le nombre (maximal) d'opérations nécessaires est proportionnel à la taille de la liste à étudier. Si on appelle $n$ la longueur de la liste, on dit que cet algorithme est **d'ordre $n$**, ou **linéaire**, ou en $O(n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Questions :** \n",
    "- La méthode utilisée nécessitait-elle que la liste soit triée ?\n",
    "- Est-on sûr que cet algorithme s'arrête ? \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Méthode 2 : recherche dichotomique\n",
    "Comment appliquer la méthode vue dans l'activité d'introduction ? \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Exemple d'algorithme:\n",
    "- on se place *au milieu* de la liste.\n",
    "- on regarde si on est inférieur ou supérieur à la valeur cherchée.\n",
    "- on ne garde que la bonne moitié de la liste qui nous intéresse, et on recommence jusqu'à trouver la bonne valeur.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Illustration\n",
    "\n",
    "Recherchons la valeur 14 dans notre liste `L`.\n",
    "\n",
    "![image](data/fig3.png)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- étape 1 : toute la liste est à traiter. On se place sur l'élément central. Son indice est la partie entière de la moitié de la longueur de la liste. Ici il y a 9 éléments, donc on se place sur le 4ème, qui est 11.\n",
    "- étape 2 : on compare 11 à la valeur cherchée (14). Il faut donc garder tout ce qui est supérieur à 11.\n",
    "- étape 3 : on se place au milieu de la liste des valeurs qu'il reste à traiter. Ici il y a 4 valeurs, donc il n'y a pas de valeur centrale. On va donc se positionner sur la 2ème valeur, qui est 18.\n",
    "- étape 4 : on compare la valeur 18 à la valeur cherchée : 14. Elle est supérieure, donc on garde ce qui est à gauche. Il n'y a plus qu'une valeur.\n",
    "- étape 5 : on se place sur la valeur 14 et on compare avec 14. La valeur est trouvée."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Programmation de la méthode de dichotomie"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous allons travailler avec deux variables `indice_debut` et `indice_fin` qui vont délimiter la liste à étudier. Ces indices sont représentés en bleu sur la figure ci-dessous. La valeur de l'`indice_central` (représenté en rouge) sera égale à `(indice_debut + indice_fin) // 2`\n",
    "![image](data/fig4.png)\n",
    "Le programme s'arrête lorsque la valeur cherchée a été trouvée, ou lorsque `indice_fin` devint inférieur à `indice_debut`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def trouve_dicho(L, n) :\n",
    "    indice_debut = ...\n",
    "    indice_fin = ...\n",
    "    while indice_debut <= indice_fin :\n",
    "        indice_centre = (... + ...) // 2     # on prend l'indice central\n",
    "        valeur_centrale = L[...]             # on prend la valeur centrale \n",
    "        if valeur_centrale == ... :          # si la valeur centrale est la valeur cherchée...\n",
    "            return indice_centre\n",
    "        if valeur_centrale < ... :             # si la valeur centrale est trop petite...\n",
    "            indice_debut = indice_centre + 1\n",
    "        else :\n",
    "            indice_fin = indice_centre - 1\n",
    "    return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "0\n",
      "8\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "L = [2, 3, 6, 7, 11, 14, 18, 19, 24]\n",
    "print(trouve_dicho(L,14))\n",
    "print(trouve_dicho(L,2))\n",
    "print(trouve_dicho(L,24))\n",
    "print(trouve_dicho(L,1976))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une visualisation de l'évolution des variables `indice_debut` et `indice_fin` est disponible sur le site pythontutor via [ce lien](http://pythontutor.com/visualize.html#code=L%20%3D%20%5B2,%203,%206,%207,%2011,%2014,%2018,%2019,%2024%5D%0A%0Adef%20trouve_dicho%28L,%20n%29%20%3A%0A%20%20%20%20indice_debut%20%3D%200%0A%20%20%20%20indice_fin%20%3D%20len%28L%29%20-%201%0A%20%20%20%20while%20indice_debut%20%3C%3D%20indice_fin%20%3A%0A%20%20%20%20%20%20%20%20indice_centre%20%3D%20%28indice_debut%20%2B%20indice_fin%29%20//%202%0A%20%20%20%20%20%20%20%20valeur_centrale%20%3D%20L%5Bindice_centre%5D%0A%20%20%20%20%20%20%20%20if%20valeur_centrale%20%3D%3D%20n%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20indice_centre%0A%20%20%20%20%20%20%20%20if%20valeur_centrale%20%3C%20n%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20indice_debut%20%3D%20indice_centre%20%2B%201%0A%20%20%20%20%20%20%20%20else%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20indice_fin%20%3D%20indice_centre%20-%201%0A%20%20%20%20return%20None%0A%0Aprint%28trouve_dicho%28L,14%29%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false).\n",
    "\n",
    "![image](data/fig5.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Terminaison de l'algorithme\n",
    "Est-on sûr que l'algorithme va se terminer ?  \n",
    "La boucle `while` qui est utilisée doit nous inciter à la prudence (voir [cours](https://github.com/glassus/nsi/blob/master/Premiere/Theme01_Bases_de_Python/02_Boucle_while/boucles_while.ipynb) sur la boucle While).  \n",
    "Il y a en effet le risque de rentrer dans une boucle infinie.  \n",
    "Pourquoi n'est-ce pas le cas ?\n",
    "\n",
    "**Aide :** observer la position des deux flèches bleues lors de l'exécution de l'algorithme \n",
    "![image](data/fig4.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La condition de la boucle `while` est `indice_debut <= indice_fin `, qui pourrait aussi s'écrire `indice_fin >= indice_debut `.  \n",
    "Au démarrage de la boucle, on a :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "    indice_debut = 0\n",
    "    indice_fin = len(L) - 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ceci qui nous assure donc de bien rentrer dans la boucle. \n",
    "\n",
    "Ensuite, à chaque étape, les deux variables `indice_debut` et `indice_fin` vont se **rapprocher** jusqu'à ce que le programme rencontre un `return` ou bien jusqu'à ce que `indice_fin` devienne inférieur à `indice_debut`.  \n",
    "\n",
    "Ceci nous assure donc que le programme va bien se terminer.\n",
    "\n",
    "**Variant de boucle**  \n",
    "On dit que la valeur `indice_fin - indice_debut ` représente le **variant de boucle** de cet algorithme. \n",
    "Ce variant est un nombre entier, d'abord strictement positif, puis qui va décroître jusqu'à la valeur 0."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Complexité de l'algorithme"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Combien d'étapes (au maximum) sont-elles nécessaires pour arriver à la fin de l'algorithme ?  \n",
    "Imaginons que la liste initiale possède 8 valeurs. \n",
    "Après une étape, il ne reste que 4 valeurs à traiter. \n",
    "Puis 2 valeurs.  \n",
    "Puis une seule valeur.  \n",
    "Il y a donc 3 étapes avant de trouver la valeur cherchée."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercice :**  \n",
    "1. Remplissez le tableau ci-dessous :\n",
    "\n",
    "| taille de la liste | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 |\n",
    "| :----------------- |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n",
    "| nombre d'étapes    | _ | _ |  _  |   3 |  _ | _   | _   | _   | _   |  _  |\n",
    "\n",
    "2. Pouvez-vous deviner le nombre d'étapes nécessaires pour une liste de 4096 termes ?\n",
    "3. Pour une liste de $2^n$ termes, quel est le nombre d'étapes ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Conclusion :** C'est le nombre de puissances de 2 que contient le nombre $N$ de termes de la liste qui est déterminant dans la complexité de l'algorithme. Ce nombre s'appelle le *logarithme de base 2* et se note $\\log_2(N)$. On dit que l'algorithme de dichotomie a une **vitesse logarithmique**. On rencontrera parfois la notation $O(\\log_2(n))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Expériences et comparaison des vitesses d'exécution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Avec une liste contenant 100 000 valeurs "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# cette ligne de code permet de transformer le contenu du fichier input_centmille.txt\n",
    "# en une liste L de 100 000 valeurs.\n",
    "\n",
    "L = open(\"data/input_centmille.txt\",'r').read().split('\\n')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mesurons le temps nécessaire pour trouver l'indice de la dernière valeur de la liste (qui est 299474) avec la méthode de balayage (méthode 1) :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.43 ms ± 86.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit trouve(L, 299474)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mesurons le temps nécessaire pour trouver l'indice de la dernière valeur de la liste (qui est 299474) avec la méthode par dichotomie (méthode 2) :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.21 µs ± 19.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit trouve_dicho(L, 299474)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Comparaison des deux méthodes :** l'algorithme dichotomique est bien plus rapide que l'algorithme de balayage (la différence d'ordre de grandeur est de $10^3$, qui correspond bien à l'ordre de grandeur de $\\frac{n}{\\log(n)}$ lorsque $n$ vaut $10^5$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Avec une liste contenant 1 000 000 valeurs (soit 10 fois plus que la liste précédente)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ce code permet de transformer le contenu du fichier million.txt en une liste L de 1 000 000 valeurs.\n",
    "f = open(\"data/input_million.txt\",'r')\n",
    "l = f.readlines()\n",
    "L = []\n",
    "for k in l :\n",
    "    L.append(int(k[:-1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mesurons le temps nécessaire pour trouver l'indice de la dernière valeur de la liste (qui est 2999306) avec la méthode de balayage (méthode 1) :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "46.9 ms ± 615 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit trouve(L, 2999306)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mesurons le temps nécessaire pour trouver l'indice de la dernière valeur de la liste (qui est 2999306) avec la méthode par dichotomie (méthode 2) :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.04 µs ± 39.4 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit trouve_dicho(L, 2999306)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Comparaison des deux méthodes :** l'algorithme dichotomique est toujours bien plus rapide que l'algorithme de balayage (la différence d'ordre de grandeur est de $10^4$, qui correspond bien à l'ordre de grandeur de $\\frac{n}{\\log(n)}$ lorsque $n$ vaut $10^6$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Influence de la taille de la liste sur la vitesse de chaque méthode :\n",
    "- méthode 1: la recherche dans une liste 10 fois plus grand prend environ 10 fois plus de temps : la vitesse de l'algorithme est bien proportionnelle à la taille $n$ de la liste. $ \\frac{10^6}{10^5} = 10$\n",
    "- méthode 2: la recherche dans une liste 10 fois plus grand prend environ 1,2 fois plus de temps : la vitesse de l'algorithme est bien proportionnelle au **logarithme** de la taille $n$ de la liste.  $\\frac{\\log(1000000)}{\\log(100000)} \\approx 1,2$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Remarque :** Il ne faut toutefois pas oublier que la méthode dichotomique, bien plus rapide, nécessite que la liste ait été auparavant triée. Ce qui rajoute du temps de calcul ! (cf [tri par insertion](https://github.com/glassus/nsi/blob/master/Premiere/Theme05_Algorithmique/03_Tri_par_insertion.ipynb) ou [tri par sélection](https://github.com/glassus/nsi/blob/master/Premiere/Theme05_Algorithmique/04_Tri_par_selection.ipynb) )"
   ]
  },
  {
   "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.6.9"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}