Stagiaire_diviser_pour_regner.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "STpZ2AsPwRCO"
   },
   "source": [
    "# Le paradigme de programmation \"Diviser pour régner\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Table des matières\n",
    "**[Chapitre 0 - Introduction](#M0)**  \n",
    "\n",
    "\n",
    "**[Chapitre 1 - Calcul du maximum d'une liste](#M1)**  \n",
    "- [1. Enoncé](#M11)\n",
    "- [2. Implémentation en Python](#M12) \n",
    " \n",
    "**[Chapitre 2 - Recherche d'un élément dans une liste](#M2)**.   \n",
    "- [1. Enoncé](#M21)  \n",
    "- [(Exercice 1) Implémentation en Python](#M22)  \n",
    "\n",
    "**[Chapitre 3 - Recherche d'un élément dans une liste triée](#M3)**  \n",
    "- [1. Enoncé](#M31) \n",
    "- [(Exercice 2) Implémentation en Python](#M32)  \n",
    "\n",
    "**[Chapitre 4 - Distance minimale dans un nuage de points](#M4)** \n",
    "- [1. Enoncé](#M41) \n",
    "- [Exercice 3](#M42) \n",
    "- [Exercice 4](#M43) \n",
    "- [Exercice 5](#M44)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ## <font color=#3876C2> Chapitre 0 - Introduction</font> <a name=\"M0\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "tM74HcxfwfgC"
   },
   "source": [
    "La méthode dite \"diviser pour régner\" se décompose ainsi en trois phases :\n",
    "\n",
    "1.   Diviser : on divise les données initiales en plusieurs sous-parties.\n",
    "2.   Régner : on résout récursivement chacun des sous-problèmes associés (ou on les résout directement si leur taille est assez petite).\n",
    "3.   Combiner : on combine les différents résultats obtenus pour obtenir une solution au problème initial.\n",
    "\n",
    "Cela va prendre tout son sens sur les exemples à venir, qui vont nous permettre de nous familiariser avec ce principe général.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "2aLqG4C2xME2"
   },
   "source": [
    " ## <font color=#3876C2> Chapitre 1 - Calcul du maximum d'une liste</font> <a name=\"M1\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> 1. Enoncé</font> <a name=\"M11\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "SKvg68xHxPpB"
   },
   "source": [
    "Le problème est de calculer le maximum d'une liste de nombres.\n",
    "\n",
    "En adoptant le paradigme \"diviser pour régner\", l'idée pour résoudre cette question est de calculer récursivement le maximum de la première moitié de la liste et celui de la seconde, puis de les comparer. Le plus grand des deux sera le maximum de toute la liste. La condition d'arrêt à la récursivité sera l'obtention d'une liste à un seul élément, son maximum étant bien sûr la valeur de cet élément.\n",
    "\n",
    "Voici donc les trois étapes de la résolution de ce problème via la méthode \"diviser pour régner\" :\n",
    "\n",
    "1.   Diviser la liste en deux sous-listes en la “coupant” par la moitié.\n",
    "\n",
    "2.   Calculer récursivement le maximum de chacune de ces sous-listes. Arrêter la récursion lorsque les listes n'ont plus qu'un seul élément.\n",
    "\n",
    "3.   Retourner le plus grand des deux maximums précédents."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Vmj76raTxenZ"
   },
   "source": [
    "### <font color=#FEB229> 2. Implémentation en Python</font> <a name=\"M12\"></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "collapsed": true,
    "id": "y2nb53_oxnaU"
   },
   "outputs": [],
   "source": [
    "def maximum(l,d,f):\n",
    "  '''Chercher le maximum d'une liste l, \"d\" comme \"début\", \"m\" comme \"milieu\", et \"f\" comme \"fin\". '''\n",
    "  if d == f:\n",
    "      return l[d]\n",
    "  m = (d+f) // 2\n",
    "  x = maximum(l,d,m)\n",
    "  y = maximum(l,m+1,f)\n",
    "  return x if x > y else y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "collapsed": true,
    "id": "1WT7m9bHxwlh",
    "outputId": "a3ec4af6-b1cb-4381-8841-28021c252d5b"
   },
   "outputs": [],
   "source": [
    "maximum([4, 7, 5, 9, 11, 2],0, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "InBYUXtCzJ4i"
   },
   "source": [
    " ## <font color=#3876C2> Chapitre 2 - Recherche d'un élément dans une liste</font> <a name=\"M2\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> 1. Enoncé</font> <a name=\"M21\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "DB2cFor7zWNf"
   },
   "source": [
    "Le problème est de rechercher la présence d’un élement dans une liste.\n",
    "\n",
    "En adoptant le paradigme \"diviser pour régner\", l'idée pour résoudre cette question est de rechercher récursivement l'élément dans la première moitié de la liste et dans la seconde, puis de combiner les résultats via l'opérateur logique or. En effet, l'élément recherché sera dans la liste s'il est dans la première moitié ou dans la seconde. La condition d'arrêt à la récursivité sera l'obtention d'une liste à un seul élément, car il est alors immédiat de conclure si l'élément recherché appartient à une telle liste ou non.\n",
    "\n",
    "Voici donc les trois étapes de la résolution de ce problème via la méthode \"diviser pour régner\" :\n",
    "\n",
    "1.   Diviser la liste en deux sous-listes en la “coupant” par la moitié.\n",
    "\n",
    "2.   Rechercher la présence de l’élément dans chacune de ces sous-listes. Arrêter la récursion lorsque les listes n'ont plus qu'un seul élément.\n",
    "\n",
    "3.   Combiner avec l'opérateur logique or les résultats obtenus."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "3AtW_D_oznPy"
   },
   "source": [
    "### <font color=#FEB229> (Exercice 1) Implémentation en Python</font> <a name=\"M22\"></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "collapsed": true,
    "id": "M-WJRzU7zm34"
   },
   "outputs": [],
   "source": [
    "def recherche(l,x,d,f):\n",
    "    '''Chercher un élément x dans une liste l, \"d\" comme \"début\", \"m\" comme \"milieu\", et \"f\" comme \"fin\". '''\n",
    "    '''Ecrire votre fonction ici'''\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "collapsed": true,
    "id": "Kvbc6XWuz8bu",
    "outputId": "639312b2-24d2-4b31-adb1-17c785a2fd5e"
   },
   "outputs": [],
   "source": [
    "recherche([4, 7, 5, 9, 11, 2], 1, 0, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "1TOG3sdZ0wLW"
   },
   "source": [
    "## <font color=#3876C2> Chapitre 3 - Recherche d'un élément dans une liste triée</font> <a name=\"M3\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> 1. Enoncé</font> <a name=\"M31\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "tmrZqWNb06Uh"
   },
   "source": [
    "Le problème est de rechercher la présence d’un élement dans une liste préalablement triée.\n",
    "\n",
    "L'idée pour résoudre cette question est d'utiliser une méthode dichotomique. La liste étant triée, après comparaison avec l’élément du \"mileu\" il est en effet facile de voir dans quelle moitié peut éventuellement se trouver l’élément cherché. On aura plus alors qu'à recommencer récursivement la recherche."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "wAEzYqws1Aue"
   },
   "source": [
    "Là encore la condition d'arrêt à la récursivité sera l'obtention d'une liste à un seul élément.\n",
    "\n",
    "Voici donc les trois étapes de la résolution de ce problème via la méthode \"diviser pour régner\"\n",
    "\n",
    "1.   Diviser la liste en deux sous-listes de même taille (à un élément près) en la \"coupant\" par la moitié.\n",
    "\n",
    "2.   Rechercher récursivement la présence de l’élément recherché dans la “bonne” des deux sous-listes après l'avoir comparé à l'élément situé au milieu de la liste.\n",
    "\n",
    "3.   Pas de résultats à combiner puisque l’on ne “travaille” que sur l'une des deux sous-listes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "36RghbYb1QVI"
   },
   "source": [
    "### <font color=#FEB229> (Exercice 2) Implémentation en Python</font> <a name=\"M32\"></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "collapsed": true,
    "id": "yeUv5kAW2XNY"
   },
   "outputs": [],
   "source": [
    "def dicho(l,x,d,f):\n",
    "    '''Chercher un élément x dans une liste triée l, \"d\" comme \"début\", \"m\" comme \"milieu\", et \"f\" comme \"fin\". '''\n",
    "    '''Ecrire votre fonction ici'''\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "collapsed": true,
    "id": "EHAR5Ttj2hyc",
    "outputId": "32d35863-a4b6-442c-c1a4-f5028e33e322"
   },
   "outputs": [],
   "source": [
    "recherche([4, 7, 12, 19, 21, 22], 19, 0, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "JrYjTkjW2zV7"
   },
   "source": [
    "## <font color=#3876C2> Chapitre 4 - Distance minimale dans un nuage de points</font> <a name=\"M4\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> 1. Enoncé</font> <a name=\"M41\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "z88fQFvUREPv"
   },
   "source": [
    "On s’intéresse au problème suivant : étant donné un ensemble P = {$p_1$, . . . , $p_n$} de n ≥ 2 points distincts du plan, trouver deux points réalisant la distance minimale parmi ce nuage de points. On suppose que n ≥ 2 et que tous les points sont distincts."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![stratégie](distmin.PNG)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Illustration de la stratégie diviser pour régner pour trouver la distance minimale dans un nuage\n",
    "de points.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> Exercice 3</font> <a name=\"M42\"></a>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ecrire la fonction *distance* qui calcule la distance euclidienne entre deux points du\n",
    "plan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from math import sqrt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "collapsed": true,
    "id": "uIbzfibNQgal"
   },
   "outputs": [],
   "source": [
    "def distance(point1, point2):\n",
    "    '''Ecrire votre fonction ici'''\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "collapsed": true,
    "id": "nCcNGrptRU_E",
    "outputId": "b45f9a9d-92cd-4446-d15e-25d9faf60256"
   },
   "outputs": [],
   "source": [
    "distance((1,3),(1,5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "collapsed": true,
    "id": "HwuYdWKgRdGp",
    "outputId": "59e42dd1-0c6c-479a-cca4-aec933870f84"
   },
   "outputs": [],
   "source": [
    "distance((1,3),(4,7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> Exercice 4</font> <a name=\"M43\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Écrire en Python une fonction *distance_plus_proche* prenant en entrée une liste de n points et renvoyant la distance minimale entre deux points quelconques, en implémentant cette stratégie naïve."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "collapsed": true,
    "id": "-7bLDLNhR9q6",
    "outputId": "b391a358-0c44-4099-9035-c86f4bc040da"
   },
   "outputs": [],
   "source": [
    "def distance_plus_proche(points):\n",
    "    '''Ecrire votre fonction ici'''\n",
    "    \n",
    "    return d_min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "collapsed": true,
    "id": "pTk2q6GuSq5C",
    "outputId": "e7316c8b-b8bd-4bd3-f119-26a1a760bc57"
   },
   "outputs": [],
   "source": [
    "distance_plus_proche([(1,3),(1,5),(4,7),(10,3),(11,5),(14,17)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "collapsed": true,
    "id": "LodqkJVwSyyy",
    "outputId": "22443308-f2b0-4a7f-e871-d940db2ff45a"
   },
   "outputs": [],
   "source": [
    "distance_plus_proche([(1,3),(8,5),(4,7),(10,3),(11,5),(14,17)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "distance_plus_proche([(94, 5), (96, -79), (20, 73), (8, -50), (78, 2), (100, 63), (-14, -69), (99, -8), (-11, -7), (-78, -46)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> Exercice 5</font> <a name=\"M44\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On va adopter une stratégie de type diviser pour régner. On sépare les points de P en deux parties *$P_G$* et *$P_D$* séparées par une droite verticale d’abscisse $x_0$ (voir figure ci-dessus). Notons $d_G$, respectivement $d_D$, la distance minimale entre deux points de *$P_G$*, respectivement *$P_D$*, et $\\delta$ = min($d_G$, $d_D$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La distance minimale est soit  $\\delta$, soit une distance entre un point de *$P_G$* et un point de *$P_D$*. Dans ce dernier cas, elle est atteinte pour des points situés dans la bande délimitée par les droites verticales d’abscisses $x_0$ − $\\delta$ et $x_0$ + $\\delta$, que nous appelons T, représentée par des pointillés sur la figure ci-dessus. On note que dans le pire des cas il y a n points dans T."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Explication pas à pas en anglais"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from IPython.display import HTML\n",
    "HTML('<iframe width=\"560\" height=\"315\" src=\"https://www.youtube.com/embed/6UBDkbVhJck\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen></iframe>')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'algorithme implémenté en pseudo-code :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://rosettacode.org/wiki/Closest-pair_problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def distance_plus_proche_ameliore(P):\n",
    "    if len(P) < 2 :\n",
    "          return float(\"inf\")\n",
    "    else :\n",
    "        d_min = distance(P[0], P[1])\n",
    "        minPoints = [( P[0], P[1]) ]\n",
    "        for i in range(len(P)) :\n",
    "            for j in range(i+1, len(P)) :\n",
    "                if distance(P[i], P[j]) < d_min :\n",
    "                    d_min = distance(P[i],P[j])\n",
    "                    minPoints = [P[i],P[j]]\n",
    "    return d_min, minPoints\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "P1 = [(0,0),(7,6),(2,20),(12,5),(16,16),(5,8),(19,7),(14,22),(8,19),(7,29),(10,11),(1,13)]\n",
    "P2 = [(94, 5), (96, -79), (20, 73), (8, -50), (78, 2), (100, 63), (-14, -69), (99, -8), (-11, -7), (-78, -46)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "distance_plus_proche_ameliore(P2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%timeit distance_plus_proche_ameliore(P2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Px = [p for (p, n) in P2]\n",
    "Px = sorted(Px)\n",
    "Px"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "Py = [n for (p, n) in P2]\n",
    "Py = sorted(Py)\n",
    "Py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Écrire en Python une fonction *closestPair* prenant en entrée une Px et Py et renvoyant la distance minimale entre deux points quelconques de P2 par exemple, en implémentant cette dernière stratégie."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def closestPair(Px, Py):\n",
    "    '''Recherche des points les plus proches dans P2. Retourne la distance et le couple de points'''\n",
    "    '''Ecrire votre fonction ici'''\n",
    "    \n",
    "    return closest, closestP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "closestPair(Px, Py)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%timeit closestPair(Px, Py)"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "presentation_diviser_pour_regner.ipynb",
   "provenance": [],
   "version": "0.3.2"
  },
  "hide_input": false,
  "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}