SYNTHESE -  DIVISER POUR REGNER.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# FICHE DE SYNTHESE : DIVISER POUR REGNER\n",
    "\n",
    "Le paradigme \"diviser pour régner\" fait partie des entrées prépondérentes au bac.\n",
    "\n",
    "## I)  Le principe\n",
    "\n",
    "Les 15 joueuses d’une équipe de volleyball ont la liste des joueuses de l’équipe avec leur numéro de téléphone. La capitaine reçoit l’information que le prochain match a été déplacé. Il faut prévenir toutes les autres joueuses.\n",
    "\n",
    "### Solution 1 : \n",
    "la capitaine se charge d’appeler toutes les autres joueuses. Si elle passe 5 minutes au téléphone avec chacune d’entre-elles. Question : En combien de temps (noté t1) l’ensemble de l’équipe est informé? En déduire la complexité de cette solution en fonction de n (taille de l’équipe)"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution 2 : \n",
    "Une solution plus efficace et plus confortable pour la capitaine est qu’elle divise la liste de joueuses en deux moitiés. Elle appelle alors la première joueuse de chacune des deux listes obtenues. Elle leur donne l’information de report de match et leur demande à leur tour de faire la même chose : diviser en deux la demi-liste à laquelle elles appartiennent, appeler la première joueuse de chacune des parties et ainsi de suite … jusqu’à ce qu’il n’y ait plus personne à prévenir.\n",
    "\n",
    "Représentons l’arbre des appels pour la liste de 15 joueuses numérotées de 1 à 15.\n",
    "<img src=\"https://allophysique.com/docs/nsi/algorithmes/images/page5_appels.png\" width=500>\n",
    "Question : Si on suppose qu’un appel téléphonique dure 5 min. En combien de temps (noté t2) l’ensemble de l’équipe est informé ? En déduire la complexité de cette solution en fonction de n (taille de l’équipe)\n",
    "\n"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## II) Exemples classiques simples : \n",
    "\n",
    "### 1) la recherche par dichotomie\n",
    "on dispose d'un tableau de taille n trié, on cherche si une valeur v est présente dans le tableau"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 10, 18, 29, 36, 64, 72, 72, 85, 105, 120, 122, 137, 148, 160, 160, 182, 192, 199, 205, 219, 221, 245, 248, 250, 251, 253, 277, 286, 295, 303, 307, 310, 326, 333, 338, 348, 349, 372, 372, 373, 377, 432, 434, 454, 467, 469, 494, 501, 523, 538, 556, 592, 606, 614, 624, 633, 637, 657, 664, 675, 680, 690, 716, 720, 721, 723, 734, 736, 739, 739, 747, 747, 777, 778, 801, 802, 818, 825, 827, 832, 836, 840, 850, 865, 869, 878, 891, 919, 940, 941, 957, 961, 965, 970, 971, 977, 978, 988, 998]\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "n=100\n",
    "t = [random.randint(0,1000) for i in range(n)]\n",
    "t.sort()\n",
    "print(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Méthode naïve : on parcourt le tableau jusqu'à trouver l'élément \n",
    "\n",
    "Quelle est la complexité de cet algorithme ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recherche(v,t):\n",
    "    \"\"\" entree : v valeur, t tableau\n",
    "        sortie : booleen qui dit si v appartient à t\"\"\"\n",
    "    # à coder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Méthode par dichotomie : \n",
    "on va passer par une fonction intermédiaire récursive \n",
    "`dicho(v,t,imin,imax)` qui cherche v entre l'indice imin et imax\n",
    "\n",
    "Quelle est la complexité de cet algorithme ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dicho(v,t,imin,imax):\n",
    "    \"\"\" entree : v valeur, t tableau, imin indice min , imax indicemax où cherché\n",
    "    sortie : booleen qui dit si v appartient à t entre les indices ci-dessus\"\"\"   \n",
    "    # à coder    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2) L'exponentiation rapide \n",
    "\n",
    "on cherche à calculer x^n = x*x*x*x ....*x (n fois)\n",
    "\n",
    "### méthode naïve (mais récursive!)\n",
    "\n",
    "Quelle est la complexité de cet algorithme ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def exp(x,n):\n",
    "    \"\"\"entrée : x réel, n entier positif\n",
    "       sortie : la valeur de x^n\n",
    "    \"\"\"\n",
    "    # à coder en récursif !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### méthode \"diviser pour régner\"\n",
    "\n",
    "on utilise le fait que x^6 = x^3 * x^3\n",
    "on fera attention à la parité de n .\n",
    "\n",
    "Quelle est la complexité de cet algorithme ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def exp2(x,n):\n",
    "    \"\"\"entrée : x réel, n entier positif\n",
    "       sortie : la valeur de x^n\n",
    "    \"\"\"\n",
    "    # à coder en récursif !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3) Exemple moins classique :\n",
    "On cherche le maximum dans un tableau de n valeurs non trié."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "n=100\n",
    "t = [random.randint(0,1000) for i in range(n)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### approche naïve : on cherche linéairement le maximum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxi(t):\n",
    "     \"\"\"entrée :t tableau non vide\n",
    "       sortie : la valeur max\n",
    "    \"\"\" \n",
    "    # à coder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### approche \"diviser pour régner\".\n",
    "\n",
    "On découpe le tableau en 2 et on compare les 2 max obtenus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxi2(t,imin,imax):\n",
    "    \"\"\"entrée :t tableau non vide, imin et imax deux indices\n",
    "       sortie : la valeur max entre imin et imax\n",
    "    \"\"\" "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4) Le grand classique du \"diviser pour régner\" : le tri-fusion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "n=100\n",
    "t = [random.randint(0,1000) for i in range(n)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "rappel : \n",
    "\n",
    " 1) on dispose d'une fonction `fusion` qui réunit deux listes triées\n",
    " \n",
    " 2) on découpe le tableau en deux et on trie les parties séparément (on peut ensuite fusionner les résultats\n",
    "\n",
    "                                                                                                                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fusion(t1,t2):\n",
    "    \"\"\"entrée : t1 et t2 deux tableaux triés \n",
    "       sortie : un tableau contenant les valeurs triées de t1 et t2\"\"\"\n",
    "    # à coder\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tri_fusion(t):\n",
    "    \"\"\"entree: t tableau non vide\n",
    "      sortie : tableau trié \n",
    "    \"\"\"\n",
    "     # à coder"
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}