{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A.algo - Programmation dynamique et plus court chemin (correction)\n", "\n", "Correction."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["
run previous cell, wait for 2 seconds
\n", ""], "text/plain": [""]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["On r\u00e9cup\u00e8re le fichier ``matrix_distance_7398.txt`` depuis [matrix_distance_7398.zip](http://www.xavierdupre.fr/enseignement/complements/matrix_distance_7398.zip) qui contient des distances entre diff\u00e9rentes villes (pas toutes)."]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [{"data": {"text/plain": ["['matrix_distance_7398.txt']"]}, "execution_count": 3, "metadata": {}, "output_type": "execute_result"}], "source": ["import pyensae.datasource\n", "pyensae.datasource.download_data(\"matrix_distance_7398.zip\", website = \"xd\")"]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [{"data": {"text/plain": ["array([['Boulogne-Billancourt', 'Beauvais', 85597],\n", " ['Courbevoie', 'Sevran', 26564],\n", " ['Colombes', 'Alfortville', 36843],\n", " ['Bagneux', 'Marcq-En-Baroeul', 233455],\n", " ['Suresnes', 'Gennevilliers', 10443]], dtype=object)"]}, "execution_count": 4, "metadata": {}, "output_type": "execute_result"}], "source": ["import pandas\n", "df = pandas.read_csv(\"matrix_distance_7398.txt\", sep=\"\\t\", header=None, names=[\"v1\",\"v2\",\"distance\"])\n", "matrice = df.values\n", "matrice[:5]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 1"]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["196\n"]}], "source": ["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))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 2\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", "execution_count": 5, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["7888\n"]}], "source": ["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))"]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [{"ename": "KeyError", "evalue": "('Charleville-Mezieres', 'Bordeaux')", "output_type": "error", "traceback": ["\u001b[1;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[1;31mKeyError\u001b[0m Traceback (most recent call last)", "\u001b[1;32m\u001b[0m in \u001b[0;36m\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\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')"]}], "source": ["print ( dist[\"Charleville-Mezieres\",\"Bordeaux\"] ) # elle n'existe pas encore"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 3\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", "execution_count": 7, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["196\n"]}], "source": ["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)) "]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 4\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", "execution_count": 8, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["798824\n"]}], "source": ["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\"] ) "]}, {"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", "execution_count": 9, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["795670\n"]}], "source": ["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\"] ) "]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice facultatif\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)}$ et :\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)}$ et :\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": ["## Exercice 5\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", "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": ["## Exercice 6"]}, {"cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["0.40180280093469833\n"]}], "source": ["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])"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 7\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", "execution_count": 11, "metadata": {}, "outputs": [{"data": {"image/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", "text/plain": [""]}, "execution_count": 12, "metadata": {}, "output_type": "execute_result"}], "source": ["from pyquickhelper.helpgen import NbImage\n", "NbImage('graph_notebook_ski.png') "]}, {"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) \\\\ } ``"]}, {"cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["0.40180280093469833\n", "(9, 14)\n", "(8, 13)\n", "(7, 12)\n", "(6, 11)\n", "(5, 10)\n", "(4, 9)\n", "(3, 8)\n", "(2, 7)\n", "(1, 6)\n", "(0, 5)\n", "(0, 4)\n", "[(0, 4), (0, 5), (1, 6), (2, 7), (3, 8), (4, 9), (5, 10), (6, 11), (7, 12), (8, 13), (9, 14)]\n"]}], "source": ["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)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 8\n", "\n", "Les deux algorithmes ont un co\u00fbt quadratique."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Prolongements : degr\u00e9 de s\u00e9paration sur Facebook"]}, {"cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["(60050, 2)\n"]}, {"data": {"text/html": ["
\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
v1v2
022902363
123462025
221402428
322012506
424252557
\n", "
"], "text/plain": [" v1 v2\n", "0 2290 2363\n", "1 2346 2025\n", "2 2140 2428\n", "3 2201 2506\n", "4 2425 2557"]}, "execution_count": 14, "metadata": {}, "output_type": "execute_result"}], "source": ["import pyensae.datasource # utiliser pyensae >= 0.8\n", "files = pyensae.datasource.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()"]}, {"cell_type": "code", "execution_count": 14, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "code", "execution_count": 15, "metadata": {"collapsed": true}, "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.4"}}, "nbformat": 4, "nbformat_minor": 2}