_doc/notebooks/td1a/td1a_correction_session7.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:133dc16341ba8fd1372e997574f38fd1de0ae45a6670f5b4f4fb4aab2dfd50ca"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "TD 7 : Programmation dynamique et plus court chemin (correction)"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Plan\n",
      "\n",
      "* [Exercice 1](#exo1)\n",
      "* [Exercice 2](#exo2)\n",
      "* [Exercice 3](#exo3)\n",
      "* [Exercice 4](#exo4)\n",
      "* [Exercice facultatif](#exof)\n",
      "* [Exercice 5](#exo5)\n",
      "* [Exercice 6](#exo6)\n",
      "* [Exercice 7](#exo7)\n",
      "* [Exercice 8](#exo8)\n",
      "* [Prolongements : degr\u00e9 de s\u00e9paration sur Facebook](#prol)"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import pyensae\n",
      "pyensae.download_data(\"matrix_distance_7398.zip\", website  = \"xd\")"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 1,
       "text": [
        "['matrix_distance_7398.txt']"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import pandas\n",
      "df = pandas.read_csv(\"matrix_distance_7398.txt\", sep=\"\\t\", header=False, names=[\"v1\",\"v2\",\"distance\"])\n",
      "matrice = df.values\n",
      "matrice[:5]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "array([['Courbevoie', 'Sevran', 26564],\n",
        "       ['Colombes', 'Alfortville', 36843],\n",
        "       ['Bagneux', 'Marcq-En-Baroeul', 233455],\n",
        "       ['Suresnes', 'Gennevilliers', 10443],\n",
        "       ['Lens', 'Maubeuge', 93768]], dtype=object)"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<h3 id=\"exo1\"> Exercice 1</h3>"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "vil = { }\n",
      "for row in matrice :\n",
      "    vil [row[0]] = 0\n",
      "    vil [row[1]] = 1\n",
      "vil = list(vil.keys())\n",
      "print (len(vil))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "196\n"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<h3 id=\"exo2\">Exercice 2</h3>\n",
      "\n",
      "La distance n'existe pas encore. L'exception du court programme suivant le montre. Rejoindre Bordeaux depuis Charleville n\u00e9cessite plusieurs \u00e9tapes."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "dist = { }\n",
      "for row in matrice :\n",
      "    a = row[0]\n",
      "    b = row[1]\n",
      "    dist[a,b] = dist[b,a] = row[2]\n",
      "print (len(dist))\n",
      "print ( dist[\"Charleville-Mezieres\",\"Bordeaux\"] )  # elle n'existe pas encore"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "7888\n"
       ]
      },
      {
       "ename": "KeyError",
       "evalue": "('Charleville-Mezieres', 'Bordeaux')",
       "output_type": "pyerr",
       "traceback": [
        "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mKeyError\u001b[0m                                  Traceback (most recent call last)",
        "\u001b[1;32m<ipython-input-5-bf31d4830b2f>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m      5\u001b[0m     \u001b[0mdist\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0ma\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mb\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mdist\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mb\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0ma\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mrow\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      6\u001b[0m \u001b[0mprint\u001b[0m \u001b[1;33m(\u001b[0m\u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mdist\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 7\u001b[1;33m \u001b[0mprint\u001b[0m \u001b[1;33m(\u001b[0m \u001b[0mdist\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;34m\"Charleville-Mezieres\"\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;34m\"Bordeaux\"\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m)\u001b[0m  \u001b[1;31m# elle n'existe pas encore\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
        "\u001b[1;31mKeyError\u001b[0m: ('Charleville-Mezieres', 'Bordeaux')"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<h3 id=\"exo3\">Exercice 3</h3>\n",
      "\n",
      "On peut remplir facilement toutes les cases correspondant aux villes reli\u00e9es \u00e0 Charleville-M\u00e9zi\u00e8res, c'est-\u00e0-dire toutes les villes accessibles en une \u00e9tape."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "d = { }\n",
      "d['Charleville-Mezieres'] = 0\n",
      "for v in vil : d[v] = 1e10\n",
      "for v,w in dist :\n",
      "    if v == 'Charleville-Mezieres': \n",
      "        d[w] = dist[v,w]\n",
      "print(len(d))        "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "196\n"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<h3 id=\"exo4\">Exercice 4</h3>\n",
      "\n",
      "Si on d\u00e9couvre que $d[w] > d[v] + dist[w,v]$, cela veut dire qu'il faut mettre \u00e0 jour le tableau $d$ car il ne contient pas la distance optimale. On r\u00e9p\u00e8te cela pour toutes les paires $(v,w)$."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for v,w in dist :\n",
      "    d2 = d[v] + dist[v,w]\n",
      "    if d2 < d[w] :\n",
      "        d[w] = d2\n",
      "print ( d[\"Bordeaux\"] )        "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "804288\n"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "On trouve 813197 m\u00e8tres pour la distance (Charleville-Mezieres, Bordeaux). Ce n'est pas forc\u00e9ment la meilleure. Pour \u00eatre s\u00fbr, il faut r\u00e9p\u00e9ter la m\u00eame it\u00e9ration autant de fois qu'il y a de villes (car le plus long chemin contient autant d'\u00e9tapes qu'il y a de villes). "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for i in range(0,len(d)) :        \n",
      "    for v,w in dist :\n",
      "        d2 = d[v] + dist[v,w]\n",
      "        if d2 < d[w] :\n",
      "            d[w] = d2\n",
      "print ( d[\"Bordeaux\"] )             "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "795670\n"
       ]
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<h3 id=\"exof\">Exercice facultatif</h3>\n",
      "\n",
      "Pour montrer que l'algorithme sugg\u00e9r\u00e9 permettra d'obtenir la solution optimale, il faut montrer qu'il n'est pas n\u00e9cessaire d'envisager aucun autre ordre que celui des skieurs et des paires tri\u00e9s par taille croissante. Cela ne veut pas dire qu'un autre ordre ne sera pas optimal, cela veut dire que pour obtenir l'appariement de co\u00fbt optimal, il existe une solution pour laquelle skieurs et skis sont rang\u00e9s dans l'ordre.\n",
      "\n",
      "On consid\u00e8re donc un appariement $\\sigma$ qui associ\u00e9 le skieur $t_i$ \u00e0 la paire $s_{\\sigma(i)}$. Il suffit que montrer que :\n",
      "\n",
      "$$\\forall i,j,  \\; t_i \\leqslant t_j \\Longleftrightarrow s_{\\sigma(i)} \\leqslant s_{\\sigma(j)}$$\n",
      "\n",
      "Pour montrer cela, on fait un raisonnement par l'absurde : pour $i$ et $j$ quelconques, on suppose qu'il existe un appariement optimal tel que  $t_i \\geqslant  t_j$ et $s_{\\sigma(i)} < s_{\\sigma(j)}$. Le co\u00fbt $C(\\sigma)$ de cet appariement est :\n",
      "\n",
      "$$ C(\\sigma) = \\sum_{k=1}^{N} \\left| t_k - s_{\\sigma(k)} \\right| = \\alpha + \\left| t_i - s_{\\sigma(i)} \\right| + \\left| t_j - s_{\\sigma(j)} \\right| $$\n",
      "\n",
      "Le co\u00fbt de l'appariement en permutant les skieurs $i$ et $j$ (donc en les rangeant dans l'ordre croissant) est :\n",
      "\n",
      "$$ C(\\sigma') = \\sum_{k=1}^{N} \\left| t_k - s_{\\sigma(k)} \\right| = \\alpha + \\left| t_j - s_{\\sigma(i)} \\right| + \\left| t_i - s_{\\sigma(j)} \\right| $$\n",
      "\n",
      "On calcule :\n",
      "\n",
      "$$ C(\\sigma) - C(\\sigma') = \\left| t_i - s_{\\sigma(i)} \\right| + \\left| t_j - s_{\\sigma(j)} \\right|  - \\left| t_j - s_{\\sigma(i)} \\right| - \\left| t_i - s_{\\sigma(j)} \\right| $$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Premier cas : $t_j \\geqslant s_{\\sigma(i)} $ et $t_i > t_j \\geqslant s_{\\sigma(i)}$\n",
      "\n",
      "$$ \\begin{array}{rcl} C(\\sigma) - C(\\sigma') &=& \\left| t_i - s_{\\sigma(i)} \\right| + \\left| t_j - s_{\\sigma(j)} \\right|  - \\left(  t_j - s_{\\sigma(j)} + s_{\\sigma(j)} - s_{\\sigma(i)} \\right) - \\left| t_i - s_{\\sigma(j)} \\right| \\\\ &=&  t_i - s_{\\sigma(i)}  + \\left| t_j - s_{\\sigma(j)} \\right|  - \\left(  t_j - s_{\\sigma(j)} \\right) - \\left( s_{\\sigma(j)} - s_{\\sigma(i)} \\right) - \\left| t_i - s_{\\sigma(j)} \\right| \\\\ &=&  t_i - s_{\\sigma(i)}- \\left| t_i - s_{\\sigma(i)} \\right|  + \\left| t_j - s_{\\sigma(j)} \\right|  - \\left(  t_j - s_{\\sigma(j)} \\right) \\\\ &=&  \\left| t_j - s_{\\sigma(j)} \\right|  - \\left(  t_j - s_{\\sigma(j)} \\right|) \\\\  &\\geqslant& 0 \\end{array} $$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Second cas : $t_j \\leqslant s_{\\sigma(i)} $ et $t_j \\leqslant s_{\\sigma(i)} \\leqslant s_{\\sigma(j)}$\n",
      "\n",
      "$$\\begin{array}{rcl} C(\\sigma) - C(\\sigma') &=& \\left| t_i - s_{\\sigma(i)} \\right| + s_{\\sigma(j)} -t_j  - \\left(  s_{\\sigma(i)} - t_j\\right) - \\left| t_i - s_{\\sigma(j)} \\right| \\\\ &=& \\left| t_i - s_{\\sigma(i)} \\right| + s_{\\sigma(j)} -  s_{\\sigma(i)} - \\left| t_i - s_{\\sigma(j)} \\right| \\\\ &\\geqslant& \\left| t_i - s_{\\sigma(j)}\\right| - \\left|  s_{\\sigma(j)} -  s_{\\sigma(i)} \\right| + s_{\\sigma(j)} -  s_{\\sigma(i)} - \\left| t_i - s_{\\sigma(j)} \\right| \\\\ &\\geqslant& 0 \\end{array}$$\n",
      "\n",
      "Dans les deux cas, on montre donc qu'il existe un appariement meilleur ou \u00e9quivalent en permutant les deux skieurs $i$ et $j$, c'est-\u00e0-dire en les triant par ordre croissant de taille. Nous avons donc montr\u00e9 que, si les paires de ski sont tri\u00e9es par ordre croissant de taille, il existe nec\u00e9ssairement un appariement optimal pour lequel les skieurs sont aussi tri\u00e9s par ordre croissant. Lors de la recherche de cet appariement optimal, on peut se restreindre \u00e0 ces cas de figure."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<h3 id=\"exo5\">Exercice 5</h3>\n",
      "\n",
      "$$\n",
      "p(n,m) = \\min \\left\\{  p(n-1,m-1) + \\left| t_n - s_m \\right|, p(n,m-1) \\right\\}\n",
      "$$\n",
      "\n",
      "Lorsqu'on consid\u00e8re le meilleur appariement des paires $1..m$ et des skieurs $1..n$, il n'y a que deux choix possibles pour la paire $m$ :\n",
      "\n",
      "- soit elle n'est associ\u00e9e \u00e0 aucun skieur et dans ce cas : $p(n,m) = p(n,m-1)$,\n",
      "- soit elle est associ\u00e9e au skieur $n$ (et \u00e0 aucun autre) : $p(n,m) = p(n-1,m-1) + \\left| t_n - s_m \\right|$."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<h3 id=\"exo6\">Exercice 6</h3>"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import random\n",
      "skieurs = [ random.gauss(1.75, 0.1) for i in range(0,10) ]\n",
      "paires  = [ random.gauss(1.75, 0.1) for i in range(0,15) ]\n",
      "skieurs.sort()\n",
      "paires.sort()\n",
      "\n",
      "p = { }\n",
      "p [-1,-1] = 0\n",
      "for n,taille in enumerate(skieurs) : p[n,-1] = p[n-1,-1] + taille\n",
      "for m,paire  in enumerate(paires ) : p[-1,m] = 0\n",
      "for n,taille in enumerate(skieurs) :\n",
      "    for m,paire in enumerate(paires) :\n",
      "        p1 = p.get ( (n  ,m-1), 1e10 ) \n",
      "        p2 = p.get ( (n-1,m-1), 1e10 ) + abs(taille - paire)\n",
      "        p[n,m] = min(p1,p2)\n",
      "        \n",
      "print (p[len(skieurs)-1,len(paires)-1])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0.19573001943098167\n"
       ]
      }
     ],
     "prompt_number": 18
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<h3 id=\"exo7\">Exercice 7</h3>\n",
      "\n",
      "Il faut imaginer que $p$ peut \u00eatre repr\u00e9sent\u00e9 sous forme de matrice et qu'\u00e0 chaque fois, on prend le meilleur chemin parmi 2 :\n",
      "\n",
      "- Chemin horizontal : on ne choisit pas la paire $m$.\n",
      "- Chemin diagonal : on choisit la paire $m$ pour le skieur $n$"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from IPython.core.display import Image \n",
      "Image(filename='graph_notebook_ski.png') "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAkAAAAD8CAIAAAAQb4xGAAAAAXNSR0IArs4c6QAAAARnQU1BAACx\njwv8YQUAAAAJcEhZcwAADsMAAA7DAcdvqGQAACvrSURBVHhe7d13XBP3/wfwA8ISRVScVBEHrVon\nDlREcY86wAXWjXW37lq1pWq12iqtRa0KtWrFLbhQ+TpQVAqiPxQF1C9DsALCV0ZDUkiTk99dciiB\nJCQx65LX848+uDubkMv7fa+7zw2IcgAAABZCgAEAACshwAAAgJUQYAAAwEoIMADNI7nJly8+LBQx\nkwCgDQgwAI0ieelXAye1NiMazrrBZeYBgDYgwAA0gHx9Y7P/hE8G9enU0qmlc22CggAD0DIEGIAG\nkMWJJ4ODD4XfTisWFV30roMAA9A+BBiAhiHAAHQDAQagYQgwAN1AgAFoGAIMQDcQYGBQBM9Pr/Ie\n4uXuPmr5kRQePYfkpoR9N9dv8oSxQzx6DfANOJXMJcXzeakR2xZM8h43epiXh5fPqsOJxeL5+ocA\nA12q3jMsbBo1IcDAgJSl7Bg9YksCT5ge1JUgnBfeyH64y7f3yDVhT7j0LVX8R1vdLIi6Y0JflKQd\nmdtv0JLQBwVC+n9L3eNlQ9Qevv85PaV3CDDQHVk9w8KmURMCDAxHcdS83nOuFFE/5R/rb0EQNq5u\nveeHv3zXYGXJmz6ioqGD//RBU/Y+luxs0kRZe9zo+VufCJg5+oQAA52R2TMsbBo1IcDAYHBvzO05\n+2ox9RM/blkLqreIjgH33jUchR+/qiU9v9msiLzKQx8CSY+2+up+KTNHnxBgoCuye4aFTaMmBBgY\nCmF68JRFlwvon1J/6ky1lsPEC/TUO2TOH/05BMHpu7fKsEfheToyzPseyjGEEX0EGOhIzT3DlqZR\nEwIMDA6Ze8TLkiCsBh97Jd1aRZG+DlSTdv45VboVS27Na0rN/3Dj4zJmjlz8hG+721tQ/1h5ZpwG\nA3aoMsyCAANdk9szmmgaA4YAA4NTHOlXj2qtbkHp0i3HvyceC2m5Kp7PzJHgxy2nB09aLIuTni8L\nWfLs6pHfgvepIHj/8RuZqjQ5Agx0TV7PaKRpDBgCDAwNP36FM9Vardc9kB6bF6YHdaPm15tyhR7y\nf4cXs9iJmu+8okqL6g0CDHRMXs+wp2nUhAADAyNMDaQH8x1nXK+y+c8/NdyGICwHHpEeJCmJ/qwJ\n9e8rzkXznpyLSNXvWWkEGOiW3J5hT9OoCQEGhoXMDaUH862HnMhj5jCKr01rQPVc50DpsXxu1OxG\n1GzXgIfiBiw4P7XfV3req0SAgU7J7RkWNY2aEGBgWJhzzl1/qXoCTHIxcNUxj9KENa3oVlz/iD5L\nJco64DP0x2Q9n5UuivCm/56K48woBBjogLyeYVPTqAkBBgaFOefcak2C9IiGKGMXPZbv4BspPZZf\n9ni9K0HU8Y4oKi8XZp/27zfngtTNLjpHlr68urIt9asSZl3W38lj8T2iwBLyeoY9TaM+BBgYlPwT\n9GCIy9JYqXsxy8u512c4EkRdn7P5VTpNlB0208W25eSAjV/4eHlvjS3SUydyb853tbe1seLQ2UWY\nmVuYm9E/mFta29Zy6PRlXJXPA6Ap8nrG8Jvm/SHAwKCQ/MyYK3Evqp9QFuTei4xKKaKf7lYVycuM\nuxQeEZMmfvYbgGmR2zMm0DQIMAAAYCUEGAAAsBICDAAAWAkBBgAArIQAAwAAVkKAAQAAKyHAAACA\nlRBgAADASggwAABgJQQYAACwEgIMAABYCQEGAACshAADAABWQoABAAArIcAAAICVEGAAAMBKCDAA\nAGAlBBgAALASAgwAAFgJAQYAAKyEAAMAAFZCgAEAACshwAAAgJUQYAAAwEoIMAAAYCUEGAAAsBIC\nDAAAWAkBBgAArIQAAwAAVkKAAQAAKyHAAACAlRBgAADASggwAABgJQQYAACwEgIMAABYCQEGAACs\nhAADAABWQoABAAArIcAAAICVEGAAAMBKCDAAAGAlBBgAALASAgwAAFgJAQYAAKyEAAMAAFZCgAEA\nACshwAAAgJUQYAAAwEoIMAAAYCUEGAAAsBICDAAAWAkBBgAArIQAAwAAVkKAAQAAKyHAAACAlRBg\nAADASggwAABgJQQYAACwEgIMAABYCQEGAACshAADAABWQoABAAArIcAAAICVEGAAAMBKCDAAAGAl\nBBgAALASAgwAAFgJAQYAAKyEAAMAAFZCgAEAACshwAAAgJUQYAAAwEoIMAAAYCUEGAAAsBICDAAA\nWAkBBgAArIQAAwAAVkKAAQAAKyHAAACAlRBgAADASggwAABgJQQYAACwEgIMFBBknQtYGvykjJkE\no8NPDFqy6UqukJmE94em0RQlihMBBvKUpR3w+7j32tuFJDMDjBBZELXKvZv/ySxkmCagaTSp5uI0\nygAjucmXLz4sFDGToAay8NaXXVqMO/hcwMxgIdQBo4YVIUgLGeXsvv4ul5kGNRlB0xhcz9RQnMYW\nYCQv/WrgpNZmRMNZN9CPahO9Ovtps4ZjD7N2txx1wFBuRQgzD4xs6DLvGo4b3gPbm8ZQe0ZhcRpH\ngJGvb2z2n/DJoD6dWjq1dK5NUBBg74F7+wuXWm7bn7BtRxJ1wFB9RZQmbuho99GaeB4zDapiZ9NI\nKsXAe0ZBcRpJgBUnngwOPhR+O61YVHTRu47Jbrg0oixpi5uVo9+F16zbHUcdMNRYEeSrE5/YW7vv\neMriMWM9YmvTSCrF0HtGfnEa3zkwBNh7Krk1rxnRdN6tEmaapVAHDKVXRFHk1AaEy6p4PjMNyjOO\npjHgnpFXnAgwkFZ4ya8+0WzBbZbnF+qggvIrovDiRAeisX9UMTMNyjKSpjHknpFTnAgwkFJ0iaoT\ne5+IQmaatVAHDOVXBJl3fIg19Q+j0DmqMZamMeSekVOcSgZYWcapVd5D+vfsNWr5kRTxqTSSmxL2\n3Vy/yRPGDu3fd6BvQNjTEsMY/cWGS4rwZUTAxKFevXoMnrfvQTH1FZHFj08ETB89YsSwISN9Vx1O\nkv7a+HHLWhBEj30vZF9Ha3J1IHh+mvrAXu7uMj7wEI9eA3wDTiVzxR+Y5KVGbFswyXvc6GFeHl4+\nqw4n0mvbAKiwIgTJmz4iCNeARJO+CVfFlqmhad62jKn0jLZaRnZxKhVgpY9/HD7s+wSeIP2XrgTh\nvOhG9sNdvr1Hrgl7wqW/Mv6jrW4WhKNvWK4h3D2AAKtEmPHb+EHr7hQLsw96WhKOU8/e/2OO58CF\nB+lKIbn3NnW3tu66Ovrd9anC9CDqG24yJ1rmWIjJ1UFZyo7RI7Yk8CSrxXmhzA9cd0zoi5K0I3P7\nDVoS+qCAvoS6LHWPlw1Re/j+54ZwQbUqK6Looo89Yd7795eGsUHVB1VbRnHTVGoZ0+gZLbaMzOJU\nJsBKohd5zLlSRP2Uf6y/BUFYt3XrPT/85bt3KhNno5l7iJz9dp1CgL3Di1vVZ3JYHvWFF0WI14qt\n89idj8V7RWJ5xwdbEUT7DY8qdmpKbvo3JohOP6XJKiOTq4PiqHm9K39gG1eZH5jo4D990JS9ldar\nKGuPGz1/qyFcU63KiihNWNOaIFosizPZCzlUbhmFTVO5ZUyiZ7TZMjKLU4kA496c7z77Kn3ujC8+\nVCaIjgH33r0zhXrlVvTs7c+qf4U6hwB7ix+/2n18WD71k+Dpjx9TK8V+7PGcyn0iaT2i/ZYUpmpe\nHelnQXC8TryWTEoxuTrg3pjbU/EH5sevaknPbzYrgt7kvSUZ7SBafXW/lJmjR6qsCPJFcHdqKzs8\nvICZYWpUbxlFTSPVMqbQM1ptGZnFWXOACdODpyy6TP8/wtSfOlPv4TDxgnR5k7lHvCwJotYn5wzh\nJCYCrAKZe3LG7JO5VJmQOYcHUN+Q3Ziz0t9c4blPalHrqsH065J1JcwI6kIQdbwj6F2oKkyuDpT4\nwDl/9OcQBKfv3ioDH4Xn6fc273sop3KP6olKKyL/WD9zguj5uyH84nqgessoahrpCjKBntFyy8gq\nTiUv4qAx69pq8LFX0u9RGDG+LvXLdt/9vMajYH7Ct93tqSNLFZhxGgzYocJQDAKsuqJLkxzocYrg\nLKlvSJDyfTt6FTstjpHsJUlmOPhdofeh5NFAHeigDDRYB3I/cFGkL7Vaic4/p0o3Y8mteU2p+R9u\nfFzjxRCG1hAF4cOsCaJLUEaNrWzklG0ZpZpGXEG67xn9bTu10zKyilOFACuO9KtHvUe3oHTp9+ZG\nzW5EzW+/ObnGdi0nS55dPfJb8D4VBO8/fiOz5ld+CwFWDT9uaXNqlbhukK4O8tWxgVSVUe3zK9M+\nwmfbOxJE3YmXZRyBvaWBOtBBGWiwDuR9YP498WhIy6p3V/LjltOjJ0qdSTK0hig4PYgqCTd5V6Ga\nDKVbRqmmYSpI1z2jv22ndlpGVnEqH2D8+BXO1Hu0XvdAepCy6Oo0R2q+UvmlCwiwqpjR/CZzqzwn\nQLKTSRAdvq8Yz5eMMtuMPKtgPMPk6kDeBxamB3Wj5tebUmXXmxez2Ima77zCQB5podKKyAvtQ+24\nexylzwKZMOVbRpmmYSrIdHpGSy0jqziVDjBhaiA9qOk44+3Yr0ThJV86aztuFX+jZPHDc9eylD9m\n1QIEWBX0sDO142I3+oz0Webi6zMbUivK0nNvxtvdJMmVV91D5F9GbXJ1IO8Dl+efGm5Drb6BR6RH\nSUqiP2tC/fuKs9G8J+ciUqXbWMdUWRGSDXeDaddMu3dUaZmam4apINPpGS21jMziVDbAyNxQelDT\nesiJPGaORMF58Rhul+3ixyyKXh4a47U12Sg2XEZD/JgAguixV2o0n8w7M56e3WZ5TKX1VPpgbWuC\ncFkt91Ig46oDYSlfeoijOnkfuLz42rQG1Ot3DpQezWcGhVwDHopXYcH5qf2+0u+hmCoNUXJ7fjOC\naFfp+MIkqdIyNTZNRQUZzbazpq7RVsvILE5lA4w5+db1F+lBTeai0m6/iO+BEDzdMXx0sJ7v3qT2\nh+i/CeA4Ew/EEePFLqFH8y367K+8h8iNWU41nUXnr2Ol11LB2TF2hPXQ07Kuo6cZTx1wY7/uTu0O\nWnVeGVUg93hT7gcuZy4HrjrqwVwV7bpefJ+QKOuAz9Af9Tw+pEJDkDkH+5hXH+ExNaq1TE1NU1FB\nRrHtVKZrtNQysotTyQBjTr61WpMgvZfB+/PzDypuQhdkHJzsuTxa0fl/rSNLX15d2Zb6TQmzLuvv\n5Jn2fqSY4MkPHajVYd7Aqfemh0zhCJ6H+jkRnPaLzudUbRhR5t4eCk6mGk8dlCUGuNLL6Ut6Q7KY\nmdXJ+8CijF30aL6Db6T0tr7s8XrqZSXXVAuzT/v3m3NB6nYXXVOtIUqi5zQmLAeE0teRmy4VW6aG\npnlbQUbQM0p1jbZaRnZxKhlg+Sfog0KXpbFSN6VRBBkHfJrZtZu1cePicV5+ux5VXa4j3JvzXe1t\nbaw44pVrZm5hbkb/YG5pbVvLodOXcXr6tfSPzD7kSa0U2xGh0UET+gz1DwjctsbPrZmz5+I/qj3S\nTawsaRPVvVWP8isYUR3wHwUOb2pp3az9R50W32bmVSfvA3Ovz3AkiLo+Z/OrrERRdthMF9uWkwM2\nfuHj5b01tkg/WaBWQ4g3T+Y9d1XZczYxKreM4qZ5W0EG2jPiSlG6VJToGi21jJziVDLASH5mzJW4\nF9KRyhBx02Iiwi/dzeLpp1dBgcKL9Di7Wc+9maJykvc87lLYmcjY1CIFWyhhWlAPC/MeO2VuxYyv\nDgTJ27yX3WImqpP7gQW59yKjUopkXW1O8jLjLoVHxKSJn/7GHoKUrR0Ja6+DL9n1a2ua6i2jsGkU\ntQxrt52KukY7LSOvOJU9BwasJBmmIFzX13xL7Vui7MNDbC26BT4ziQHYwgszRu9OZyZMmngX12F8\ntR1kE6NOy5ha0+i+a+QWJwLMmAlStrSnmlHVKzJ599a1s2y+mPV/01IJhRdnD/3OtP96iARZEDmj\nsW3P7Skmvi7UbBmTahqdd42C4kSAGTHy5e8eFgRh6XW0ygNdakIWXp/XwmHA7jQj358sSwkc5R1S\n+Z4eU1WWtNWtdtuVf5rC5lcRtVvGdJpG912jqDgRYEaJ5GXcCQ/ZNNWVPh9r57Fqz9Gz0c8kf0VO\nOaL8yAWuTUYdyDTejTvJjdsw0jsoWfbZCZNS9uRnz0adVt/W0xUnBuG9W8YkmkYPXaO4OBFgRqk0\nec9nPt4TfD+dPnPmtCmTJ/qM857za5JqRcdP+nmws8d38SoOpbAG7+Hve2+8Mu0LFmhk0Z11PVqN\nCUkz7cFDTbSM8TeNrrumxuJEgIFcZHH8ttG9Zp/OxlbeaAkyDvn1mrhbX/c9GB80jeYoUZwIMFBI\nWJCaWoheNFrC10/TZV7ZDOpD02iGEsWJAAMAAFZCgAEAACshwAAAgJUQYAAAwEoIMAAAYCUEGAAA\nsBICDMDgHDhwoLQUjwgBqAECDMCwFBYWWlpaOjo6fvPNN7m5ucxcAKgGAQZgcEQiUVhYmIeHh5WV\n1bRp0xISEpgFAFAJAgzAcN2/f3/q1KnUAZmnp2d4eDhJmvDjdgGqQYABGLqcnJx169Y5Ojq6uLj8\n9NNPf//9N7OAFQrOjnebd8uY/1CL8X9Cg4UAA2CH0tLSkJCQjz/+uE6dOkuWLElPZ8cfkiZf7mpL\n9DlZwEwaIeP/hIYLAQbAMleuXBk5ciSHwxk3btzNmzeZuYZK7uad5Kb9GZtWwv5BUQSY/iDAAFjp\n2bNnCxcutLOz69q168GDBwUCffwl4MKrS323POAzUzLJ27zzYj7/gLDwPJLHTLMXAkx/EGAALFZY\nWPjDDz80b968SZMmGzZsyM/PZxbohChzd/em3hFFzKRMcjbv/PiVzgThGpDI/r+jiQDTHwQYAOsJ\nhcLjx4+7u7tbW1vPmjUrMTGRWaBl6geY4Nm2jgTRZE60EVz6gADTHwQYgPGIi4vz9fW1tLQcOHDg\n+fPn37x5wyzQDtUDTMTNTHqQkHA/6seeFgSn9/Yb9xMeJGXp9ESYsOj5/asnfw/542zci1JNvDEC\nTH8QYADG5q+//lq9enX9+vXbtm27c+dOHk/B32R/LyoHGJl/84fF/v7+0wY2JAiioddU6uc5nwfG\nFOoowfgpv/v3dZ+0Nuhw2KmDgYuH9p1z6oWQWaY2BJj+IMAAjBOfz9+zZ89HH33k4OCwYsWKzMxM\nZoHmqDuEyL+7vAVBtP3moW6f91iWtKV7owHBzyWRVRK7xs3OfuSZQvHUe0CA6Q8CDMCYvXnz5tKl\nS0OHDuVwOBMmTLhz5w6zQBPUDDDhs+2dCKKR/03dngATPd/VlbBw2xxfJKIn+Y9/XeC/OSpPPPE+\nEGD6gwADMAnJycmfffaZra1tjx49QkND//33X2aBcsj8i3N7uraR1rpFPYLgNHZhJiu07TBsc0LF\ntfXVN+9k7hEvS6LWqLDXzIxKpIYSSZHMkUVR5v6hDcyJGplZtZx9rZj5n2gFEZMcxEtsnd3HL/3p\nzOMi6ddX+OZyfhkKAkx/EGAAJuT169ebN29u1qyZk5MT9QM1ySyoEcnPTrp3V1rs+a/a1RuwI4qZ\nfCvh2eu3d6VV37wXR/rVI8x67cuSOvYhC2O2zp4xdVi3/isuPX8c+pW//9x5/t69u4zc9GeVnCkn\nizPu3Y6uWcyjHOkxSlFB7E7/Aa71zMQxRlh0Wh0jCTjqzbfMnjFtuPSbu3casfFOfk5U4Odz5y+c\n9+ngzr38jz6vfrsdAkx/EGAAJoc6/KIOwrp3704dkFGHZdTBGbNARWoNIfLvrWpJEK4bHkvuAONn\n3U8uEJULnu7yW3Gj6FWoJ4ew7+QTeLeYTq3iy5McbLyOa+BmZ7IkIz4ujSuJQkH+44vbxzsRRJO5\n4kcYCp7u9FsRVZQb2q/Km9fjNPccteRUJv2rCp5s7WDpvCK+2m3bCDD9QYABmK47d+5MmDCBw+EM\nHTr00qVLql52r06AibL29aSS4zPJw28Fz3aOnXAgU1jOvftryEMeL2aRE1Fr6IEsyXUWohchvTh1\nangDZQgz9vazJIgPK1KTUvpgXVtbtx2p9DvJfXMzotWKP7niyfKS6DmNzdttTq52CIYA0x8EGICp\ny8zMXLFiRd26ddu1a7dnzx4+X+GzoSpRJ8Co4GhNEG6/Zoqoo6KE7ePGbnv0dpyPvr3ZotHsKCYy\nyJzQwbbWAw5lyzv7pLTShDWuDt0WHEuvyC9R7vnP2rb2v/z63UtXefPygvPj6li47cpgLrPn313h\nbNZ8SWz1WxIQYPqDAAMAWklJSVBQUJs2berXr7969eq//vqLWSCfWkOIgrTfvD+o7zZ9+YIJQ302\n3nz97kwYmfPHAOtaI04zj8MSZQZ7WNkODs0R8ZLORLzNHrWI8qI2TBg+buYX6zZ+v3HNXO/+fUYs\nCX1aOairvHl5yZ0FzczafF1xpX/J7QVORMuV8Xxh9o3TdwsqRyoCTH8QYADwDkmS58+fHzhwoKWl\npa+v7927d5kFsqh5GX05yc9Juns3ObfKgzCKIsbXtXDbyRzzkLmHPS3tRp7ME2T9MWv20Zfvfbl7\nuYiX8+R+zO3YB6l51R/BIf3m5YLkTR+ZNZxVcTzGj1vWwsI1ILGU++c3Pt/clToMQ4DpDwIMAGRI\nTEycNWuWtbW1u7v7iRMnRCIZAUK+DOndfHJk5UvVq1F+816W9F07mw4b356m4ids6Nuyh/+Xi2as\nOpWp7WftV33zwrOj6jh4n6v4tUXZp6d++OGEL1f6+wfGVb36HgGmNwgwAJArLy9vw4YNjRs3btGi\nxQ8//FBUVOVoq6wgp5g5ZpFDhc07yXtV9dUEhdn5GnlgYY2qvnn1dyb5eTI/LAJMfxBgAFADgUBw\n8ODBLl262NnZLVy48NmzZ8wCJRj/5h0Bpj8IMABQ1s2bN8eOHcvhcEaOHHnlyhVmrmLZez60GBD2\n3k8cNGDG/wkNFgIMAFSTnp6+ZMmSOnXqfPzxxyEhIaWlCp/JKypMvpum0z+YomvG/wkNFgIMANTx\n999///zzzy4uLo6OjuvWrcvJyWEWAOgKAgwA1EeSZHh4uKenp5WV1dSpU//v//6PWQCgfQgwANAA\nKrqmTZtGxZiHh0dYWBgVbMwCAK1BgAGAxuTm5n7zzTcNGzZ0cXEJDAz8+++/mQUAWoAAAwANKy0t\n/e233zp27FinTp0vvvgiLS2NWQCgUQgwANCWa9eujRo1isPhjBkzJioqipkLoCEIMADQrv/+97+L\nFi2ys7Pr0qXLgQMHysre67m8AG8hwABAF4qKin788ccWLVo0btz422+/zcvTwJ+pBBOHAAMA3RGJ\nRCdPnuzdu7e1tfXMmTMfPnzILABQHQIMAPTg7t27fn5+lpaWAwYMOHfuHC67BzUgwABAb16+fLlm\nzZr69eu3adPml19+KSkpYRYAKAEBBgB69s8//+zdu7ddu3Z169ZdtmzZ8+fPmQUACiHAAMAgvHnz\n5vLly8OGDeNwOD4+Prdv32YWAMiBAAMAw5KSkjJv3jxbW9vu3bsfPnz433//ZRYASEOAAYAhKigo\n+P77752cnJo2bfrdd9/973//YxYAVECAAYDhEgqFR48e7dmzJ3VANmfOnKSkJGYBAAIMAFghJiZm\n4sSJHA5n8ODBFy9efPPmDbMATBgCDABYIysra+XKlQ4ODh9++OHu3bv5fD6zAEwSAgwAWIbH4+3a\ntcvV1bVevXpffvnlixcvmAVgYhBgAMBKb968uXDhwqBBgzgczqRJk2JjY5kFYDIQYADAbo8fP/b3\n97exsenVq9exY8eEQiGzAIwdAgwAjEF+fv7GjRubNGnywQcfbNmypaCggFkAxgsBBgDGQyAQHDp0\nqGvXrrVq1Zo/f/7Tp0+ZBWCMEGAAYISio6O9vb05HM6IESP+85//MHPBuCDAAMBoZWRkLF261N7e\nvkOHDvv27fvnn3+YBWAUEGAAYOS4XO6OHTtatWrl6Oi4du3a7OxsZgGwHAIMAEwCSZJnzpzp37+/\npaXllClT7t27xywA1kKAAYBpSUhImD59upWVVd++fU+dOiUSiZgFwDYIMAAwRa9evQoICGjUqJGz\ns/P27duLi4uZBcAeCDAAMF1lZWX79+/v1KlT7dq1Fy9enJqayiyQxnsQtCrwTiHJTIKBQIABAJRf\nv3599OjRHA6H+i/1MzO3QmnyT561630SklrGzACDgAADAGBQR2DUcRh1NEYdk1FHZtTxGbOgXPjy\n5JSmli6fncvFGTPDgQADAJBSVFS0bds2Z2fnRo0aBQQEvHr1Sjy79Om+MQ1ruX19C0OJhgIBBgAg\ng0gkOnXqVN++fa2srKZPn/7gwYPycn7SzhH1bTp9fi4bDww2BAgwAABF4uPjp0yZYmlp2b9//zNn\njj361cfJ0mlCcDKPWQ56gwADAKhZdnb22rVrGzRo0KqVy8Z5A7vZ2XsEXHuFAzG9QoABAMgh5L3O\nyUxNfnjvzzt/3ktMSX+RmVP467597du3r2Nn07a2WV33xZezBcw/Bp1DgAEAyMSNmt2MIAhzS5va\ndR3sa1lSP0tY1nN2bufWuGljM2rC3H7Eyr0FuDZRHxBgAADKEpWVFOQ8T/rz8vG9P6xdNG1Al+ZM\nrJlbffrTMeYfga4gwAAA1EeWvYr+Y22bD1p/cfgqMwt0BQEGAACshAADAABWQoABAAArIcAAAICV\nEGAAAMBKCDAAAGAlBBgAALASAgx0Q5B1LmBp8BP8PUAN4CcGLdl0JReP4TN2bGwa3RYnAgx0oCzt\ngN/Hvdfext9R0gyyIGqVezf/k1nIMOPF1qbRaXEiwEDbyMJbX3ZpMe7gczzzVBUkN/nyxYeF8h6x\nJ0gLGeXsvv4ul5kGo8LuptFdcSLAQLtEr85+2qzh2MM4WFAeyUu/GjiptRnRcNYN+dsAYeaBkQ1d\n5l3DYa3RYX/T6Ko4EWCgVdzbX7jUctv+BEdfNSJf39jsP+GTQX06tXRq6VybfkCswgArLy9N3NDR\n7qM18fjDisbFKJpGN8WJAAMtKkva4mbl6HfhNQ4SakYWJ54MDj4UfjutWFR00btOzQFWTr468Ym9\ntfuOp9g/MB7G0jQ6KU4EGGhPya15zYim826VMNOgLCUDjPqHkVMbEC6r4vnMNLCdETWNDooTAQZa\nU3jJrz7RbMFt5JfKlA6w8sKLEx2Ixv5Rxcw0sJtRNY32ixMBBtpSdImqXnufiEJmGpSnfICReceH\nWFP/MKqmfwhsYFxNo/3i1H2AlWWcWuU9pH/PXqOWH0kRn+AjuSlh3831mzxh7ND+fQf6BoQ9LcEp\nEwMkfBkRMHGoV68eg+fte1BMfUVk8eMTAdNHjxgxbMhI31WHk6S/Nn7cshYE0WPfC9kXgmuxDgTP\nT1Mv7eXuLuOlh3j0GuAbcCqZK35pkpcasW3BJO9xo4d5eXj5rDqcSH8uA6B8gJULkjd9RBCuAYm4\nR9zgVG4ZZXpGcdNIWkYbPaO1htF6ceo6wEof/zh82PcJPEH6L10JwnnRjeyHu3x7j1wT9oRLf2X8\nR1vdLAhH37Bcebe/gJ4IM34bP2jdnWJh9kFPS8Jx6tn7f8zxHLjwIF3BJPfepu7W1l1XR7+7alaY\nHkR9w03mRMscC9FiHZSl7Bg9YksCT/ILOC+U+dJ1x4S+KEk7MrffoCWhDwroi5XLUvd42RC1h+9/\nbgiXLqsQYNS/9bEnzHv//lKdTRfIIMq78u38r488KHi/rZB0yyjRMwqbpqJltNAzZdprGG0Xp44D\nrCR6kcecK0XUT/nH+lsQhHVbt97zw1++WwNl4sQ2cw+Rs98OesKLW9VnclgeVYZFEeJtq63z2J2P\nxXtrYnnHB1sRRPsNjyp2tUpu+jcmiE4/pckqby3WQXHUvN6VX9rGVeZLEx38pw+asrfSJxBl7XGj\n5281hKuXVQmw0oQ1rQmixbI4XMihISQ38bf5Ho3NOU79Zm8Jfyz3ZnLFqrVMjT2jqGnetYzGe6Y4\nSnsNo+3i1G2AcW/Od599lT6jxxcfKhNEx4B779YIhfq8rejZ259V/wpBf/jxq93Hh+VTPwme/vgx\n9Q3Zjz2eU7lPJK1HtN+SwlTzqyP9LAiO14nXkkkpWqwD7o25PRW/ND9+VUt6frNZEfTG5S3JaAfR\n6qv7pcwcPVIlwMgXwd2p7dnw8AJmBmhEWc6d31aMcrUhOM0H+G85EZvFU+koolrL1NwzCprmXcto\nvGeoltFew2i7OHUaYML04CmLLtOfRJj6U2fqsztMvCD9ucjcI17UwXatT87hzL8hIXNPzph9Mpcq\nXzLn8ADqG7Ibc1b6mys890kt6httMP26ZIsrzAjqQhB1vCPE+4zStFgHSrx0zh/9OQTB6bu3ytBH\n4Xk6M8z7HspRaTulHaoEGLXn3M+cIHr+rvgXFwgE/wOV5WXeP/vLykl9WlhT5dy699i53+w8Fhmb\n8leeZPHff//NrN8qqrVMzT2joGkq1bWme4Z+aS02jHLFqTbdX8RBY9a11eBjr6Q/VmHE+LrUSuy+\n+7l6R+2gbUWXJjnQ4xTBWVLfkCDl+3bUF0c4LY6R7L1JZjj4XRHvNMqhxTqQ+9JFkb7UByA6/5wq\n3Y4lt+Y1peZ/uPFxjeeb+Qnfdre3oD+u0sw4DQbsUGFsUqUAKwgfRm1duwRlKFxZEydOlPwuoEFm\n5hbx/5OTYQymZWruGWWahszVUs9oq2GUK0616SfAiiP96lGfvVtQuvQ64UbNbkTNb785WVsXrcD7\n4cctbU59Q64bpKuWfHVsIFX9VPv8yrSP8Nn2jgRRd+JlGUdgb2mxDuS9NP+eeDykZdW7K/lxy+nx\nE6UG68mSZ1eP/Ba8TwXB+4/fyFThw6gWYKcHUSvfTd71nozS0tI8UF/2f++c3PHVHJ/+nZrbUV8N\nYePQ6IOWbTqN+OHtAKBsFS1Tc88o0zTFkVrqGW01jHLFqTa9BBg/foUz9dlbr3sgPXhadHWa4/t8\nB6BtzGh+k7lVnhMg2ckkiA7fV3SzZOzbZuRZBeMZWqwDeS8tTA/qRs2vN6XKTi4vZrETNd95hYE8\n0kKlAMsL7UPt4Xscpc+3gIaR/Myo4HXTvFztCcK+jceEz78/cOlual6p9GGKfG9bpuaeUaJpqLrW\nTs9orWG0XJz6CDBhaiA92Oo4o2Lol1F4yZfeB+i4VfyFksUPz13LUn7QBbSPHg6ndqfsRp+RPstc\nfH1mQ+qbs/Tcm/F2901y5VX3EPnXz2qxDuS9dHn+qeE21C868Ij0OElJ9GdNqH9fcT6a9+RcRKp0\nI+uYKgEm2UQ2mHZNiawD5ZVlx/y+2vtje8LcyWPmpqMxz9W5xepdyyjRMzU2DV3XWukZrTWMtotT\nDwFG5obSg63WQ07kMXMkCs6Lx3C7bBc//FH08tAYr63JKm64QKvEjwkgiB57pQbzybwz4+nZbZbH\nVKrS0gdrWxOEy2q5lyipWwfCUr70IEd18l66vPjatAbUa3cOlB7PZ4ZfXAMein/ZgvNT+32l30Mx\nVQKs5Pb8ZgTR7t2OPLwn+jL6eb0bEpwPPGdvCUtU8zJ6sXcto0TP1NQ04rpWo2dqbBntNYy2i1MP\nAcacFOz6i/RgK3NNabdfxPdACJ7uGD462CDuKYUKvNgl9Gi+RZ/9lfcQuTHLqaaz6Px1rPS2tuDs\nGDvCeuhpWdfR09SpA27s192pHUKrziujChTsDst56XLmguCq4x7M9ceu68U35IiyDvgM/VHPo9jU\nrjj991QcZ9b8EB4y52Af8+pjPKA+yY3MoQnveSMzpVLLKNMzNTQNU9cq9YxSLaO1htF6ceo+wJiT\ngq3WJEjvZfD+/PyDipvQBRkHJ3suj1Z0/h90TvDkhw7UN2fewKn3podMQQueh/o5EZz2i87nSJc+\nVdeZe3soOMmrTh2UJQa4Uv8PhdM3JIuZWZ28lxZl7KLH8x18I6XbqezxeuplJVcvC7NP+/ebc0Hq\nhhddI0tfXl3Zlv6YZl3W38mrYd+1JHpOY8JyQCh9xTYYlsoto0zPKG4apq5V6hnlWkZrDaP14tR9\ngOWfoA9WXZbGSt0sRxFkHPBpZtdu1saNi8d5+e16VHU56BeZfciTQxC2I0Kjgyb0GeofELhtjZ9b\nM2fPxX9UfaKbRFnSJqp7q44+VFCrDviPAoc3tbRu1v6jTotvM/Oqk/fS3OszHAmirs/Z/Cq/rig7\nbKaLbcvJARu/8PHy3hpbpJ8s4N6c72pva2NFrWWKmbmFuRn9g7mltW0th05fxsnsCPEWyrznrir7\nzmAApFpGqZ5R2DSSulaxZ5RqGW01jPaLU/cBRvIzY67EvZCOeoaImxYTEX7pror3vIMuFF6kx9nN\neu7NFJWTvOdxl8LORMamFikoTWFaUA8L8x47ZZbv+9SBIHmb97JbzER1cl9akHsvMiqlSNbAEMnL\njLsUHhGTJn7+G3sIUrZ2JKy9Dr5k169tGqRaRrmeUdQ0krpWr2cUt4yWGkYHxamHc2DASpJhCsJ1\nfc03+r4lyj48xNaiW+AzDZ/BLbwwY/TudGbCpIl3cR3GV9tFBgOgTstoq2n00TK6KE4EGChFkLKl\nPdWMyt2Y9A7v3rp2ls0Xa/bP8xVenD30O/z1EGovuCByRmPbnttTsC4MkJoto5Wm0UPL6KY4EWCg\nDPLl7x4WBGHpdbTKg2ZqQhZen9fCYcDuNI3tT5alBI7yDql084zJKkva6la77co/Nbp3ABqidsto\nvmn00TI6Kk4EGChG8jLuhIdsmupKX1Bg57Fqz9Gz0c8kf91OOaL8yAWuTUYdyNRE/5DcuA0jvYOS\nZZ4GMC1lT372bNRp9W09XXECcsluGVV6RpNNo5eW0VlxIsBAsdLkPZ/5eE/w/XT6zJnTpkye6DPO\ne86vSap1Az/p58HOHt/FqziUIgPv4e97b7zCBQtk0Z11PVqNCUnD4KHhkd0yKvaMxppG9y2jy+JE\ngIEukMXx20b3mn06G9mjAYKMQ369Ju7GnSbGjZ1No9viRICBrggLUlPf56k8UEH4+mm6zGubwdiw\nr2l0W5wIMAAAYCUEGAAAsBICDAAAWAkBBgAArIQAAwAAVkKAAQAAC5WX/z+JKWda6CIslwAAAABJ\nRU5ErkJggg==\n",
       "prompt_number": 10,
       "text": [
        "<IPython.core.display.Image at 0x748f790>"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "`` \\xymatrix{  & m-1  & m \\\\      n-1   &  p(n-1,m-1) \\ar[dr]^{ + \\abs{t_n - s_m}} &  p(n-1,m) \\\\      n     &  p(n,m-1)   \\ar[r] & p(n,m) \\\\ \t\t\t\t} ``"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "p = { }\n",
      "p [-1,-1] = 0\n",
      "best = { }\n",
      "for n,taille in enumerate(skieurs) : p[n,-1] = p[n-1,-1] + taille\n",
      "for m,paire  in enumerate(paires ) : p[-1,m] = 0\n",
      "for n,taille in enumerate(skieurs) :\n",
      "    for m,paire in enumerate(paires) :\n",
      "        p1 = p.get ( (n  ,m-1), 1e10 ) \n",
      "        p2 = p.get ( (n-1,m-1), 1e10 ) + abs(taille - paire)\n",
      "        p[n,m] = min(p1,p2)\n",
      "        \n",
      "        if p[n,m] == p1 : best [n,m] = n,m-1\n",
      "        else : best [n,m] = n-1,m-1\n",
      "        \n",
      "print (p[len(skieurs)-1,len(paires)-1])\n",
      "\n",
      "chemin = [ ]\n",
      "pos = len(skieurs)-1,len(paires)-1\n",
      "while pos in best :\n",
      "    print (pos)\n",
      "    chemin.append(pos)\n",
      "    pos = best[pos]\n",
      "chemin.reverse()\n",
      "print (chemin)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0.19573001943098167\n",
        "(9, 14)\n",
        "(9, 13)\n",
        "(9, 12)\n",
        "(9, 11)\n",
        "(8, 10)\n",
        "(7, 9)\n",
        "(6, 8)\n",
        "(5, 7)\n",
        "(4, 6)\n",
        "(4, 5)\n",
        "(3, 4)\n",
        "(2, 3)\n",
        "(1, 2)\n",
        "(0, 1)\n",
        "[(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (4, 6), (5, 7), (6, 8), (7, 9), (8, 10), (9, 11), (9, 12), (9, 13), (9, 14)]\n"
       ]
      }
     ],
     "prompt_number": 19
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<h3 id=\"exo8\">Exercice 8</h3>\n",
      "\n",
      "Les deux algorithmes ont un co\u00fbt quadratique."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<h3 id=\"prol\">Prolongements : degr\u00e9 de s\u00e9paration sur Facebook</h3>"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import pyensae # utiliser pyensae >= 0.8\n",
      "files = pyensae.download_data(\"facebook.tar.gz\",website=\"http://snap.stanford.edu/data/\")\n",
      "import pandas\n",
      "df = pandas.read_csv(\"facebook/1912.edges\", sep=\" \", names=[\"v1\",\"v2\"])\n",
      "print(df.shape)\n",
      "df.head()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "(60050, 2)\n"
       ]
      },
      {
       "html": [
        "<div style=\"max-height:1000px;max-width:1500px;overflow:auto;\">\n",
        "<table border=\"1\" class=\"dataframe\">\n",
        "  <thead>\n",
        "    <tr style=\"text-align: right;\">\n",
        "      <th></th>\n",
        "      <th>v1</th>\n",
        "      <th>v2</th>\n",
        "    </tr>\n",
        "  </thead>\n",
        "  <tbody>\n",
        "    <tr>\n",
        "      <th>0</th>\n",
        "      <td> 2290</td>\n",
        "      <td> 2363</td>\n",
        "    </tr>\n",
        "    <tr>\n",
        "      <th>1</th>\n",
        "      <td> 2346</td>\n",
        "      <td> 2025</td>\n",
        "    </tr>\n",
        "    <tr>\n",
        "      <th>2</th>\n",
        "      <td> 2140</td>\n",
        "      <td> 2428</td>\n",
        "    </tr>\n",
        "    <tr>\n",
        "      <th>3</th>\n",
        "      <td> 2201</td>\n",
        "      <td> 2506</td>\n",
        "    </tr>\n",
        "    <tr>\n",
        "      <th>4</th>\n",
        "      <td> 2425</td>\n",
        "      <td> 2557</td>\n",
        "    </tr>\n",
        "  </tbody>\n",
        "</table>\n",
        "</div>"
       ],
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 11,
       "text": [
        "     v1    v2\n",
        "0  2290  2363\n",
        "1  2346  2025\n",
        "2  2140  2428\n",
        "3  2201  2506\n",
        "4  2425  2557"
       ]
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}