{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A.e - Enonc\u00e9 12 d\u00e9cembre 2017 (1)\n", "\n", "Correction du premier \u00e9nonc\u00e9 de l'examen du 12 d\u00e9cembre 2017. Celui-ci m\u00e8ne \u00e0 l'impl\u00e9mentation d'un algorithme qui permet de retrouver une fonction $f$ en escalier \u00e0 partir d'un ensemble de points $(X_i, f(X_i))$."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["<div id=\"my_id_menu_nb\">run previous cell, wait for 2 seconds</div>\n", "<script>\n", "function repeat_indent_string(n){\n", "    var a = \"\" ;\n", "    for ( ; n > 0 ; --n)\n", "        a += \"    \";\n", "    return a;\n", "}\n", "var update_menu_string = function(begin, lfirst, llast, sformat, send, keep_item, begin_format, end_format) {\n", "    var anchors = document.getElementsByClassName(\"section\");\n", "    if (anchors.length == 0) {\n", "        anchors = document.getElementsByClassName(\"text_cell_render rendered_html\");\n", "    }\n", "    var i,t;\n", "    var text_menu = begin;\n", "    var text_memo = \"<pre>\\nlength:\" + anchors.length + \"\\n\";\n", "    var ind = \"\";\n", "    var memo_level = 1;\n", "    var href;\n", "    var tags = [];\n", "    var main_item = 0;\n", "    var format_open = 0;\n", "    for (i = 0; i <= llast; i++)\n", "        tags.push(\"h\" + i);\n", "\n", "    for (i = 0; i < anchors.length; i++) {\n", "        text_memo += \"**\" + anchors[i].id + \"--\\n\";\n", "\n", "        var child = null;\n", "        for(t = 0; t < tags.length; t++) {\n", "            var r = anchors[i].getElementsByTagName(tags[t]);\n", "            if (r.length > 0) {\n", "child = r[0];\n", "break;\n", "            }\n", "        }\n", "        if (child == null) {\n", "            text_memo += \"null\\n\";\n", "            continue;\n", "        }\n", "        if (anchors[i].hasAttribute(\"id\")) {\n", "            // when converted in RST\n", "            href = anchors[i].id;\n", "            text_memo += \"#1-\" + href;\n", "            // passer \u00e0 child suivant (le chercher)\n", "        }\n", "        else if (child.hasAttribute(\"id\")) {\n", "            // in a notebook\n", "            href = child.id;\n", "            text_memo += \"#2-\" + href;\n", "        }\n", "        else {\n", "            text_memo += \"#3-\" + \"*\" + \"\\n\";\n", "            continue;\n", "        }\n", "        var title = child.textContent;\n", "        var level = parseInt(child.tagName.substring(1,2));\n", "\n", "        text_memo += \"--\" + level + \"?\" + lfirst + \"--\" + title + \"\\n\";\n", "\n", "        if ((level < lfirst) || (level > llast)) {\n", "            continue ;\n", "        }\n", "        if (title.endsWith('\u00b6')) {\n", "            title = title.substring(0,title.length-1).replace(\"<\", \"&lt;\")\n", "         .replace(\">\", \"&gt;\").replace(\"&\", \"&amp;\");\n", "        }\n", "        if (title.length == 0) {\n", "            continue;\n", "        }\n", "\n", "        while (level < memo_level) {\n", "            text_menu += end_format + \"</ul>\\n\";\n", "            format_open -= 1;\n", "            memo_level -= 1;\n", "        }\n", "        if (level == lfirst) {\n", "            main_item += 1;\n", "        }\n", "        if (keep_item != -1 && main_item != keep_item + 1) {\n", "            // alert(main_item + \" - \" + level + \" - \" + keep_item);\n", "            continue;\n", "        }\n", "        while (level > memo_level) {\n", "            text_menu += \"<ul>\\n\";\n", "            memo_level += 1;\n", "        }\n", "        text_menu += repeat_indent_string(level-2);\n", "        text_menu += begin_format + sformat.replace(\"__HREF__\", href).replace(\"__TITLE__\", title);\n", "        format_open += 1;\n", "    }\n", "    while (1 < memo_level) {\n", "        text_menu += end_format + \"</ul>\\n\";\n", "        memo_level -= 1;\n", "        format_open -= 1;\n", "    }\n", "    text_menu += send;\n", "    //text_menu += \"\\n\" + text_memo;\n", "\n", "    while (format_open > 0) {\n", "        text_menu += end_format;\n", "        format_open -= 1;\n", "    }\n", "    return text_menu;\n", "};\n", "var update_menu = function() {\n", "    var sbegin = \"\";\n", "    var sformat = '<a href=\"#__HREF__\">__TITLE__</a>';\n", "    var send = \"\";\n", "    var begin_format = '<li>';\n", "    var end_format = '</li>';\n", "    var keep_item = -1;\n", "    var text_menu = update_menu_string(sbegin, 2, 4, sformat, send, keep_item,\n", "       begin_format, end_format);\n", "    var menu = document.getElementById(\"my_id_menu_nb\");\n", "    menu.innerHTML=text_menu;\n", "};\n", "window.setTimeout(update_menu,2000);\n", "            </script>"], "text/plain": ["<IPython.core.display.HTML object>"]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Q1 - \u00e9chantillon al\u00e9atoire\n", "\n", "G\u00e9n\u00e9rer un ensemble al\u00e9atoire de 1000 nombres $(X_i,Y_i)$ qui v\u00e9rifie :\n", "\n", "* $X_i$ suit une loi uniforme sur $[0,16]$\n", "* $Y_i = \\mathbb{1}_{[\\sqrt{X_i}] \\mod 2}$ o\u00f9 $[A]$ est la partie enti\u00e8re de $A$.\n", "\n", "On pourra se servir de la fonction ``random`` du module ``random``."]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": ["import random\n", "X = [random.random() * 16 for i in range(0,1000)]\n", "Y = [ int(x**0.5) % 2 for x in X]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Q1 - dessiner le nuage de points - donn\u00e9e\n", "\n", "Le code suivant vous est donn\u00e9 afin de v\u00e9rifier vos r\u00e9ponses."]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": ["%matplotlib inline"]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [{"data": {"text/plain": ["[<matplotlib.lines.Line2D at 0x1f893f9e518>]"]}, "execution_count": 5, "metadata": {}, "output_type": "execute_result"}, {"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAFI1JREFUeJzt3X+Q3Hd93/Hne797e9JJsi2hAxFJ\nsexWphYureFqXJhQEvCM7GTkdpoydkuGJAwumZikKU0rSsfNuNOMA52QZnABDyEOKdh1HZJoGIFh\nCCkzSez4BMFYVh00AtuH7frwb0uW7nb33T9273w6nXx78p727sPzMXNz+/3uZ7/f1+1+77Xf/e7t\nfSMzkSSVpTboAJKk/rPcJalAlrskFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWqD2rFmzdv\nzh07dgxq9ZK0Kh04cOCHmTm62LiBlfuOHTsYHx8f1OolaVWKiId6GedhGUkqkOUuSQWy3CWpQJa7\nJBXIcpekAi1a7hHxmYh4IiLuP831ERG/GxGHI+K+iHhj/2NKkpailz+FvBX4OPDZ01x/JbCz+/Vm\n4BPd7yve5+95mN/+6oM8c2yaqhZsXDvEsekWEdBqJVOtZNPIEMebLY5OtWi3k1bCcBVELTg+3Qag\nFvCGreeSQKNeY+NIg2eOTfG9Hx7l2RenabaTdveEV+saFWuHK55+YYpWd16jClqZBFCv1XjV+gbP\nHpvmhanW7PKrWrCuUWfz+gY/dt5a/vr7T82uf2bMmnqNqVay9by1XHnJFn7/L77HiVZSBbzvJy5k\n71UXn8V7VwA37T/EZ+/+Psen29QiaNRrnL9phPVr6tz/g2e78yFhdhuBzuO5cWSI5443mW69dEV0\nv6oqqEdwotWevV1Vg23njTBUBc128uTRKZrNNq1M1gxVHJ1q0mq/tJzsfm90xwO0EqqAbRtHeM05\nw/ztEy/w/PHpzo2yc5t1jYpWQrudDDdqRAbPvjjN3HO6Vd1ttp2w5Zxhjk23efbYS9v8mnoNAlrt\nZLiqUa+Co93tfcNwnaPTLZrN9kn3yZqhGpkw3W4TBEO1oJlJq5Wdn6X7Q61fU9Fsw4lmCwg2DFes\nqVe8MNXktees4fHnj9Nqw9qhGk8dPTn3zH0/XK9RRSdTVYPhoYrjUy0IGBnqLP/cNXXqVXCi2SYD\nXjje5Ph0e/a+nbF2qMZ0q02z3Vl2AJvWNfi1K17Hv3zzj/e+MS1R9HKavYjYAXwxMy9Z4LpPAX+e\nmbd1px8E3p6Zj73cMsfGxnKQf+f++Xse5j/+8XcGtv5BeP/bLPiz6ab9h/jkN44MOoZWsN/8Z39/\nyQUfEQcyc2yxcf045r4VeGTO9ER33kKhrouI8YgYn5yc7MOqz9yX7n/Z554iffng44OO8CPF+1uL\nWc4e6ke5xwLzFnw5kJm3ZOZYZo6Nji766dlldeUlrx3o+gdh9+u3DDrCjxTvby1mOXuoH/9+YALY\nPmd6G/BoH5a7rGZeCnnMXctl5v72mLvH3FfrMfefBq4HrqLzRurvZuZliy1z0MfcJWk16vWY+6J7\n7hFxG/B2YHNETAD/GRgCyMxPAvvpFPth4BjwC2ceW5LUD4uWe2Zeu8j1Cfxy3xJJkl4xP6EqSQWy\n3CWpQJa7JBXIcpekAlnuklQgy12SCmS5S1KBLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtd\nkgpkuUtSgSx3SSqQ5S5JBbLcJalAlrskFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWp\nQJa7JBXIcpekAlnuklQgy12SCtRTuUfE7oh4MCIOR8TeBa7/8Yj4ekR8KyLui4ir+h9VktSrRcs9\nIirgZuBKYBdwbUTsmjfsPwF3ZOalwDXA/+h3UElS73rZc78MOJyZRzJzCrgduHremATO6V4+F3i0\nfxElSUtV72HMVuCROdMTwJvnjfkN4CsR8QFgHfDOvqSTJJ2RXvbcY4F5OW/6WuDWzNwGXAX8YUSc\nsuyIuC4ixiNifHJyculpJUk96aXcJ4Dtc6a3cephl/cCdwBk5l8Ba4DN8xeUmbdk5lhmjo2Ojp5Z\nYknSonop93uBnRFxQUQ06Lxhum/emIeBdwBExMV0yt1dc0kakEXLPTObwPXAXcAhOn8VczAiboyI\nPd1hHwTeFxHfBm4Dfj4z5x+6kSSdJb28oUpm7gf2z5t3w5zLDwBv7W80SdKZ8hOqklQgy12SCmS5\nS1KBLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ5S5JBbLcJalAlrsk\nFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnuklQgy12SCmS5S1KB\nLHdJKpDlLkkFstwlqUCWuyQVqKdyj4jdEfFgRByOiL2nGfOuiHggIg5GxOf7G1OStBT1xQZERAXc\nDFwBTAD3RsS+zHxgzpidwIeAt2bm0xHx6uUKLElaXC977pcBhzPzSGZOAbcDV88b8z7g5sx8GiAz\nn+hvTEnSUvRS7luBR+ZMT3TnzXURcFFE/EVE3B0RuxdaUERcFxHjETE+OTl5ZoklSYvqpdxjgXk5\nb7oO7ATeDlwLfDoizjvlRpm3ZOZYZo6Njo4uNaskqUe9lPsEsH3O9Dbg0QXG/GlmTmfm94AH6ZS9\nJGkAein3e4GdEXFBRDSAa4B988b8CfCTABGxmc5hmiP9DCpJ6t2i5Z6ZTeB64C7gEHBHZh6MiBsj\nYk932F3AkxHxAPB14Ncz88nlCi1JenmROf/w+dkxNjaW4+PjA1m3JK1WEXEgM8cWG+cnVCWpQJa7\nJBXIcpekAlnuklQgy12SCmS5S1KBLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtS\ngSx3SSqQ5S5JBbLcJalAlrskFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXI\ncpekAlnuklQgy12SCmS5S1KBeir3iNgdEQ9GxOGI2Psy4342IjIixvoXUZK0VIuWe0RUwM3AlcAu\n4NqI2LXAuA3ArwD39DukJGlpetlzvww4nJlHMnMKuB24eoFx/wX4CHC8j/kkSWegl3LfCjwyZ3qi\nO29WRFwKbM/ML/YxmyTpDPVS7rHAvJy9MqIGfAz44KILirguIsYjYnxycrL3lJKkJeml3CeA7XOm\ntwGPzpneAFwC/HlEfB+4HNi30JuqmXlLZo5l5tjo6OiZp5Ykvaxeyv1eYGdEXBARDeAaYN/MlZn5\nbGZuzswdmbkDuBvYk5njy5JYkrSoRcs9M5vA9cBdwCHgjsw8GBE3RsSe5Q4oSVq6ei+DMnM/sH/e\nvBtOM/btrzyWJOmV8BOqklQgy12SCmS5S1KBLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtd\nkgpkuUtSgSx3SSqQ5S5JBbLcJalAlrskFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWp\nQJa7JBXIcpekAlnuklQgy12SCmS5S1KBLHdJKpDlLkkFstwlqUCWuyQVqKdyj4jdEfFgRByOiL0L\nXP9vI+KBiLgvIr4WEef3P6okqVeLlntEVMDNwJXALuDaiNg1b9i3gLHMfANwJ/CRfgeVJPWulz33\ny4DDmXkkM6eA24Gr5w7IzK9n5rHu5N3Atv7GlCQtRS/lvhV4ZM70RHfe6bwX+NJCV0TEdRExHhHj\nk5OTvaeUJC1JL+UeC8zLBQdGvBsYAz660PWZeUtmjmXm2OjoaO8pJUlLUu9hzASwfc70NuDR+YMi\n4p3Ah4F/kpkn+hNPknQmetlzvxfYGREXREQDuAbYN3dARFwKfArYk5lP9D+mJGkpFi33zGwC1wN3\nAYeAOzLzYETcGBF7usM+CqwH/ndE/E1E7DvN4iRJZ0Evh2XIzP3A/nnzbphz+Z19ziVJegX8hKok\nFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnuklQgy12SCmS5S1KB\nLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ5S5JBbLcJalAlrskFchy\nl6QCWe6SVCDLXZIKZLlLUoEsd0kqUE/lHhG7I+LBiDgcEXsXuH44Iv5X9/p7ImJHv4NKknq3aLlH\nRAXcDFwJ7AKujYhd84a9F3g6M/8u8DHgt/odVJLUu3oPYy4DDmfmEYCIuB24Gnhgzpirgd/oXr4T\n+HhERGZmH7MCcNP+Q3z27oc4NtUCoAqoVzVqAa12MlyvcaKVVEAzk0xYU6+RwIvTLdrzEm3ZMMzN\n734Tbzp/Y7+jrggHHnqa3/rSIQ5PHoVMjk61yEyqWrDtvLX84JkXOdFqE0ArX7o/p5ttWt37qlEF\n564d4oXjTY4328zchVXAto0jXLRlA9+ZeIbHnztx0rprAQkM1YJ6VSMzOdFsAzBcr9FOmNlEEphu\nvfTgVDXYNNKg1U6eO96kUQ9OTLch4NXrh5nO5Llj07QyqSJotnP2sa0FDFU1qoBj021q0VlBu7vs\n4SpoA+1M1tQrhus1nj/RpNlKsvtz1SJo5UvLbFRB0tnGagFrG3W2bBjmyJNHabVfWm8tgsykVguG\n6zUaVY13jW1n71UX9+0xlXrRS7lvBR6ZMz0BvPl0YzKzGRHPAq8CftiPkDNu2n+IT37jyEnzWgmt\nZnt2eqrVOuV2L0ydOm/G48+f4J9/4i/5o196S3EFf+Chp3nXp/5ytnxO0kq+O3n0lNnNhGb75BtM\ntZLJF6YWWgQPPXWMh546tuD6Z4pxqpWnPC4vTi8Uas6y25y0zuZUd2EJj817Emlx8jN2O5l9Epmb\nY8aJOU8iR6daHJ23fbQSWvP2S6bm3Kad8PzxJs8fb56y3nb3dq1WMt1qAa3ZbdaC19nUyzH3WGDe\n/D3yXsYQEddFxHhEjE9OTvaS7yRfPvj4km/Tq7uPPLlsyx6Uu488uXCx66xbzm1XWkgv5T4BbJ8z\nvQ149HRjIqIOnAs8NX9BmXlLZo5l5tjo6OiSw+5+/ZYl36ZXl1/4qmVb9qBcfuGrqPx7qBVhObdd\naSG9/OrfC+yMiAsiogFcA+ybN2Yf8J7u5Z8F/mw5jrfvvepi3v+2CxlpVLPzqugcv107VKNRBRuG\nKxr1GmvrNYaqoF4L1jcq1jWqzrHXebZsGC7ykAzAm87fyB3/+i1ctmMjm9Y12DQy1D0OHKwdqrFz\ndB0jQzWqGtRrENH5vmaoc7x6RqMKRtc3WFuvnfQSrQo4f9MIV+x6DVvOGT5l/bXoLLNRBSONirVD\nte5xaVg7VJvN0qiCoerkB6eqwej6TuZ6LRhpdDJVNXjtOcNs3tCgUQVVrbP8uY9trbtNjAzVZqfn\nbujD3fVVNVjXqNg0MsRQFbM/WxWd9wlq8+6Doe566jXYsKbOztF1Jz15dq6Lzu2rYP1wZ9nvf9uF\nHpLRWRe9dHBEXAX8DlABn8nM/xoRNwLjmbkvItYAfwhcSmeP/ZqZN2BPZ2xsLMfHx1/xDyBJP0oi\n4kBmji02rpc3VMnM/cD+efNumHP5OPAvlhpSkrQ8PCIrSQWy3CWpQJa7JBXIcpekAlnuklSgnv4U\ncllWHDEJPHSGN99Mn/+1QZ+Ya+lWajZzLY25luaV5Do/Mxf9FOjAyv2ViIjxXv7O82wz19Kt1Gzm\nWhpzLc3ZyOVhGUkqkOUuSQVareV+y6ADnIa5lm6lZjPX0phraZY916o85i5Jenmrdc9dkvQyVl25\nL3ay7kGIiO0R8fWIOBQRByPiVwedaa6IqCLiWxHxxUFnmRER50XEnRHxf7v32z8edCaAiPi17mN4\nf0Tc1v2Pp4PK8pmIeCIi7p8zb1NEfDUivtv9ftb/V/Vpcn20+1jeFxF/HBHnrYRcc677dxGREbF5\npeSKiA90u+xgRHyk3+tdVeXe48m6B6EJfDAzLwYuB355heSa8avAoUGHmOe/A1/OzL8H/ANWQL6I\n2Ar8CjCWmZfQ+RfX1www0q3A7nnz9gJfy8ydwNe602fbrZya66vAJZn5BuBvgQ+d7VAsnIuI2A5c\nATx8tgN13cq8XBHxk3TOPf2GzHw98N/6vdJVVe7MOVl3Zk4BMyfrHqjMfCwzv9m9/Dydoto62FQd\nEbEN+Gng04POMiMizgHeBvweQGZOZeYzg001qw6s7Z5RbIRTzzp21mTmNzj1jGZXA3/QvfwHwD89\nq6FYOFdmfiUzZ04qezedM7YNPFfXx4B/zwKn/jwbTpPrl4CbMvNEd8wT/V7vaiv3hU7WvSJKdEZE\n7KBz0pJ7Bptk1u/Q2bBX0tlULwQmgd/vHi76dESsG3SozPwBnT2oh4HHgGcz8yuDTXWK12TmY9DZ\nqQBePeA8C/lF4EuDDgEQEXuAH2TmtwedZZ6LgJ+IiHsi4v9ExD/q9wpWW7n3dCLuQYmI9cAfAf8m\nM59bAXl+BngiMw8MOss8deCNwCcy81LgKIM5vHCS7vHrq4ELgB8D1kXEuwebanWJiA/TOUz5uRWQ\nZQT4MHDDYmMHoA5spHMY99eBOyJioX47Y6ut3Hs5WfdARMQQnWL/XGZ+YdB5ut4K7ImI79M5hPVT\nEfE/BxsJ6DyOE5k58+rmTjplP2jvBL6XmZOZOQ18AXjLgDPN9/8i4rUA3e99fzl/piLiPcDPAP9q\nOc6hfAb+Dp0n6m93fwe2Ad+MiJVwtvIJ4AvZ8dd0Xln39c3e1VbuvZys+6zrPuP+HnAoM3970Hlm\nZOaHMnNbZu6gc1/9WWYOfE80Mx8HHomI13VnvQN4YICRZjwMXB4RI93H9B2sgDd655l7Mvr3AH86\nwCyzImI38B+APZl5bNB5ADLzO5n56szc0f0dmADe2N3+Bu1PgJ8CiIiLgAZ9/gdnq6rcu2/YXA/c\nReeX7o7MPDjYVEBnD/nn6OwZ/03366pBh1rhPgB8LiLuA/4h8JsDzkP3lcSdwDeB79D5/RjYJxwj\n4jbgr4DXRcRERLwXuAm4IiK+S+cvQG5aIbk+DmwAvtrd/j+5QnIN3GlyfQa4sPvnkbcD7+n3qx0/\noSpJBVpVe+6SpN5Y7pJUIMtdkgpkuUtSgSx3SSqQ5S5JBbLcJalAlrskFej/A3Fj4I4AMwiFAAAA\nAElFTkSuQmCC\n", "text/plain": ["<matplotlib.figure.Figure at 0x1f892ef8160>"]}, "metadata": {}, "output_type": "display_data"}], "source": ["import matplotlib.pyplot as plt\n", "plt.plot(X, Y, '.')"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Q2 - tri\n", "\n", "Trier les points selon les $X$."]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"data": {"text/plain": ["[(0.014962888038782651, 0),\n", " (0.020462778257442693, 0),\n", " (0.022310859639508962, 0),\n", " (0.03078728731371605, 0),\n", " (0.03153252863972433, 0)]"]}, "execution_count": 6, "metadata": {}, "output_type": "execute_result"}], "source": ["nuage = [(x,y) for x,y in zip(X,Y)]\n", "nuage.sort()\n", "nuage[:5]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Q3 - moyenne\n", "\n", "On suppose que les $Y$ sont tri\u00e9s selon les $X$ croissants.\n", "Calculer la moyenne des diff\u00e9rences entre $Y$ et la moyenne $m$ des $Y$\n", "(en valeur absolue) sur un intervalle $[i,j]$, $j$ exclu.\n", "Ecrire une fonction ``def somme_diff(nuage, i, j)`` qui ex\u00e9cute ce calcul\n", "qui correspond \u00e0 $\\sum_{k=i}^{j-1} |Y_k - m|$ avec $m = (\\sum_{k=i}^{j-1} Y_k) / (j-i)$."]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [{"data": {"text/plain": ["(0.0, 476.2380000000092)"]}, "execution_count": 7, "metadata": {}, "output_type": "execute_result"}], "source": ["def somme_diff(xy, i, j):\n", "    m = sum(e[1] for e in xy[i:j]) / (j-i)\n", "    return sum(abs(e[1]-m) for e in xy[i:j])\n", "\n", "somme_diff(nuage, 0, 5), somme_diff(nuage, 0, len(nuage))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Q4 - distance\n", "\n", "Soit $i,j$ deux entiers, on coupe l'intervalle en deux : $i,k$ et $k,j$. On calcule la ``somme_diff`` sur ces deux intervalles, on fait la somme des diff\u00e9rences (en valeurs absolues) de ces moyennes par rapport \u00e0 la valeur sur le plus grand intervalle. On \u00e9crit la fonction ``def difference(nuage, i, j, k):``."]}, {"cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [{"data": {"text/plain": ["18.56022222223197"]}, "execution_count": 8, "metadata": {}, "output_type": "execute_result"}], "source": ["def difference(nuage, i, j, k):\n", "    m1 = somme_diff(nuage, i, k)\n", "    m2 = somme_diff(nuage, k, j)\n", "    m = somme_diff(nuage, i, j)\n", "    return abs(m1+m2-m)\n", "\n", "difference(nuage, 0, len(nuage), 100)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Q5 - fonction comme param\u00e8tre\n", "\n", "Le langage Python permet de passer une fonction \u00e0 une autre fonction en tant qu'argument. Un exemple :"]}, {"cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [{"data": {"text/plain": ["1"]}, "execution_count": 9, "metadata": {}, "output_type": "execute_result"}], "source": ["def fct(x, y):\n", "    return abs(x-y)\n", "\n", "def distance_list(list_x, list_y, f):\n", "    return sum(f(x,y) for x,y in zip(list_x, list_y))\n", "\n", "distance_list([0, 1], [0, 2], fct)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Ecrire la fonction pr\u00e9c\u00e9dente en utilisant la fonction ``fct``."]}, {"cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [{"data": {"text/plain": ["494.7982222222412"]}, "execution_count": 10, "metadata": {}, "output_type": "execute_result"}], "source": ["def somme_diff(xy, i, j, f):\n", "    m = sum(e[1] for e in xy[i:j]) / (j-i)\n", "    # On a modifi\u00e9 les fonctions pr\u00e9c\u00e9dentes pour calculer\n", "    # une fonction d'erreur \"custom\" ou d\u00e9finie par l'utilisateur.\n", "    return sum(f(e[1], m) for e in xy[i:j])\n", "\n", "def difference(nuage, i, j, k, f):\n", "    m1 = somme_diff(nuage, i, k, f)\n", "    m2 = somme_diff(nuage, k, j, f)\n", "    m = somme_diff(nuage, i, j, f)\n", "    return abs(m - m1) + abs(m - m2)\n", "\n", "difference(nuage, 0, len(nuage), 100, fct)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Q6 - optimiser\n", "\n", "On veut d\u00e9terminer le $i$ optimal, celui qui maximise la diff\u00e9rence dans l'intervalle $[i,j]$. On souhaite garder la fonction ``fct`` comme argument. Pour cela, impl\u00e9menter la fonction ``def optimise(nuage, i, j, f):``."]}, {"cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [{"data": {"text/plain": ["(565, 711.6476814159435)"]}, "execution_count": 11, "metadata": {}, "output_type": "execute_result"}], "source": ["def optimise(nuage, i, j, f):\n", "    mx = -1\n", "    ib = None\n", "    for k in range(i+1,j-1):\n", "        d = difference(nuage, i,j,k, f)\n", "        if ib is None or d > mx:\n", "            mx = d\n", "            ib = k\n", "    if ib is None:\n", "        # Au cas o\u00f9 l'intervalle est vide, on retourne une coupure\n", "        # \u00e9gale \u00e0 i.\n", "        ib = i\n", "        mx = 0\n", "    return ib, mx\n", "\n", "optimise(nuage, 0, len(nuage), fct)"]}, {"cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [{"data": {"text/plain": ["[<matplotlib.lines.Line2D at 0x1f893ea57b8>]"]}, "execution_count": 12, "metadata": {}, "output_type": "execute_result"}, {"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAFLZJREFUeJzt3X+Q3Hd93/Hne797e9JJsi2hAxFJ\nsexGphYureFqXJhQEvCMbDJyO00ZO6WhKYNLJiZpQtOK0nEz7jTjQCakGVzAQ8AhBTuuQxINkTEM\nIWUmiR2fIdiWVAeNwPZhuz7825Klu91994/dO59OJ9+evKc9ffJ8zNzcfr/fz36/r9vde+33vrt7\n38hMJEllqQ06gCSp/yx3SSqQ5S5JBbLcJalAlrskFchyl6QCWe6SVCDLXZIKZLlLUoHqg9rwxo0b\nc9u2bYPavCSdke69994fZuboYuMGVu7btm1jfHx8UJuXpDNSRDzUyzgPy0hSgSx3SSqQ5S5JBbLc\nJalAlrskFWjRco+Iz0bEExHxwEmWR0T8TkQcjIj7IuKN/Y8pSVqKXt4KeTPwCeDzJ1l+ObC9+/Vm\n4JPd7yveF+9+mN/62oM8c2SaqhasXz3EkekWEdBqJVOtZMPIEEebLQ5PtWi3k1bCcBVELTg63Qag\nFvCGzWeTQKNeY/1Ig2eOTPG9Hx7m2RenabaTdveEV2saFauHK55+YYpWd16jClqZBFCv1XjV2gbP\nHpnmhanW7PqrWrCmUWfj2gY/cs5q/vr7T81uf2bMqnqNqVay+ZzVXH7RJj73F9/jWCupAt7/4+ez\n+4oLT+OtK4Ab9h7g83d9n6PTbWoRNOo1zt0wwtpVdR74wbPd+ZAw+xiBzv25fmSI5442mW69tCC6\nX1UV1CM41mrPXq+qwZZzRhiqgmY7efLwFM1mm1Ymq4YqDk81abVfWk92vze64wFaCVXAlvUjvOas\nYf72iRd4/uh050rZuc6aRkUrod1Ohhs1IoNnX5xm7jndqu5jtp2w6axhjky3efbIS4/5VfUaBLTa\nyXBVo14Fh7uP93XDdQ5Pt2g228fdJquGamTCdLtNEAzVgmYmrVZ2fpbuD7V2VUWzDceaLSBYN1yx\nql7xwlST1561isefP0qrDauHajx1+PjcM7f9cL1GFZ1MVQ2GhyqOTrUgYGSos/6zV9WpV8GxZpsM\neOFok6PT7dnbdsbqoRrTrTbNdmfdAWxY0+CXL3sdP/PmH+39wbRE0ctp9iJiG/DlzLxogWWfBv48\nM2/pTj8IvD0zH3u5dY6NjeUg3+f+xbsf5j//0f0D2/4gfOBtFvyyumN35/vlNwCdYv/UNw8NMJBW\nul//5/9gyQUfEfdm5thi4/pxzH0z8Mic6YnuvIVCXRMR4xExPjk52YdNn7o7HnjZ554ifWXf44OO\nULbH7+98dXl7azHL2UP9KPdYYN6Cfw5k5k2ZOZaZY6Oji356dlldftFrB7r9Qdj5+k2DjvB3ire3\nFrOcPdSPfz8wAWydM70FeLQP611WM38Kecxdy2Xm9vaYu8fcz9Rj7u8CrgWuoPNC6u9k5iWLrXPQ\nx9ylvvvcuzrff+5PB5tDRev1mPuie+4RcQvwdmBjREwA/xUYAsjMTwF76RT7QeAI8HOnHluS1A+L\nlntmXr3I8gR+oW+JJEmvmJ9QlaQCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpek\nAlnuklQgy12SCmS5S1KBLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ\n5S5JBbLcJalAlrskFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQXqqdwjYmdEPBgRByNi9wLL\nfzQivhER346I+yLiiv5HlST1atFyj4gKuBG4HNgBXB0RO+YN+y/AbZl5MXAV8D/7HVSS1Lte9twv\nAQ5m5qHMnAJuBa6cNyaBs7qXzwYe7V9ESdJS1XsYsxl4ZM70BPDmeWN+DfhqRHwQWAO8sy/pJEmn\npJc991hgXs6bvhq4OTO3AFcAvx8RJ6w7Iq6JiPGIGJ+cnFx6WklST3op9wlg65zpLZx42OV9wG0A\nmflXwCpg4/wVZeZNmTmWmWOjo6OnlliStKheyv0eYHtEnBcRDTovmO6ZN+Zh4B0AEXEhnXJ311yS\nBmTRcs/MJnAtcCdwgM67YvZFxPURsas77EPA+yPiO8AtwL/JzPmHbiRJp0kvL6iSmXuBvfPmXTfn\n8n7grf2NJkk6VX5CVZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnuklQgy12SCmS5S1KB\nLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ5S5JBbLcJalAlrskFchy\nl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAvVU7hGxMyIejIiDEbH7JGPe\nHRH7I2JfRHyxvzElSUtRX2xARFTAjcBlwARwT0Tsycz9c8ZsBz4MvDUzn46IVy9XYEnS4nrZc78E\nOJiZhzJzCrgVuHLemPcDN2bm0wCZ+UR/Y0qSlqKXct8MPDJneqI7b64LgAsi4i8i4q6I2LnQiiLi\nmogYj4jxycnJU0ssSVpUL+UeC8zLedN1YDvwduBq4DMRcc4JV8q8KTPHMnNsdHR0qVklST3qpdwn\ngK1zprcAjy4w5k8yczozvwc8SKfsJUkD0Eu53wNsj4jzIqIBXAXsmTfmj4GfAIiIjXQO0xzqZ1BJ\nUu8WLffMbALXAncCB4DbMnNfRFwfEbu6w+4EnoyI/cA3gF/NzCeXK7Qk6eUt+lZIgMzcC+ydN++6\nOZcT+JXulyRpwPyEqiQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ5S5JBbLcJalAlrskFchyl6QC\nWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnuklQgy12SCmS5S1KBLHdJKpDl\nLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSpQT+UeETsj4sGIOBgRu19m3E9HREbE\nWP8iSpKWatFyj4gKuBG4HNgBXB0ROxYYtw74ReDufoeUJC1NL3vulwAHM/NQZk4BtwJXLjDuvwEf\nBY72MZ8k6RT0Uu6bgUfmTE90582KiIuBrZn55T5mkySdol7KPRaYl7MLI2rAx4EPLbqiiGsiYjwi\nxicnJ3tPKUlakl7KfQLYOmd6C/DonOl1wEXAn0fE94FLgT0LvaiamTdl5lhmjo2Ojp56aknSy+ql\n3O8BtkfEeRHRAK4C9swszMxnM3NjZm7LzG3AXcCuzBxflsSSpEUtWu6Z2QSuBe4EDgC3Zea+iLg+\nInYtd0BJ0tLVexmUmXuBvfPmXXeSsW9/5bEkSa+En1CVpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ5S5J\nBbLcJalAlrskFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnuklQg\ny12SCmS5S1KBLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ5S5JBbLc\nJalAPZV7ROyMiAcj4mBE7F5g+a9ExP6IuC8ivh4R5/Y/qiSpV4uWe0RUwI3A5cAO4OqI2DFv2LeB\nscx8A3A78NF+B5Uk9a6XPfdLgIOZeSgzp4BbgSvnDsjMb2Tmke7kXcCW/saUJC1FL+W+GXhkzvRE\nd97JvA+4Y6EFEXFNRIxHxPjk5GTvKSVJS9JLuccC83LBgRHvAcaAjy20PDNvysyxzBwbHR3tPaUk\naUnqPYyZALbOmd4CPDp/UES8E/gI8E8z81h/4kmSTkUve+73ANsj4ryIaABXAXvmDoiIi4FPA7sy\n84n+x5QkLcWi5Z6ZTeBa4E7gAHBbZu6LiOsjYld32MeAtcD/joi/iYg9J1mdJOk06OWwDJm5F9g7\nb951cy6/s8+5JEmvgJ9QlaQCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnu\nklQgy12SCmS5S1KBLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ5S5J\nBbLcJalAlrskFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQXqqdwjYmdEPBgRByNi9wLLhyPi\nD7rL746Ibf0OKknq3aLlHhEVcCNwObADuDoidswb9j7g6cz8MeDjwG/0O6gkqXf1HsZcAhzMzEMA\nEXErcCWwf86YK4Ff616+HfhERERmZh+zAnDD3gN8/q6HODLVAqAKqFc1agGtdjJcr3GslVRAM5NM\nWFWvkcCL0y3a8xJtWjfMje95E286d32/o64I9z70NL9xxwEOTh6GTA5PtchMqlqw5ZzV/OCZFznW\nahNAK1+6PaebbVrd26pRBWevHuKFo02ONtvM3IRVwJb1I1ywaR33TzzD488dO27btYAEhmpBvaqR\nmRxrtgEYrtdoJ8w8RBKYbr1051Q12DDSoNVOnjvapFEPjk23IeDVa4eZzuS5I9O0MqkiaLZz9r6t\nBQxVNaqAI9NtatHZQLu77uEqaAPtTFbVK4brNZ4/1qTZSrL7c9UiaOVL62xUQdJ5jNUCVjfqbFo3\nzKEnD9PqrvjWxpME8DMf/lNqtWC4XqNR1Xj32FZ2X3Fhv+5SqSe9lPtm4JE50xPAm082JjObEfEs\n8Crgh/0IOeOGvQf41DcPHTevldBqtmenp1qtE673wtSJ82Y8/vwx/sUn/5I//Pm3FFfw9z70NO/+\n9F/Ols9xWsl3Jw+fMLuZ0Gwff4WpVjL5wtRCq+Chp47w0FNHFtz+TDFOtfKE++XF6YVCzVl3m+O2\n2ZzqrizhsXlPIi2Of8ZuJ7NPInNzzDg250nk8FSLw/MeH62E1rz9kqk512knPH+0yfNHmyfkzpnr\nt5LpVgtozT5mLXidTr0cc48F5s3fI+9lDBFxTUSMR8T45ORkL/mO85V9jy/5Or2669CTy7buQbnr\n0JMLF7uWxf72uexvn7vgsuV87EoL6aXcJ4Ctc6a3AI+ebExE1IGzgafmrygzb8rMscwcGx0dXXLY\nna/ftOTr9OrS81+1bOselEvPfxWV74c6ba5v/izXN392wWXL+diVFtLLr/49wPaIOC8iGsBVwJ55\nY/YA7+1e/mngz5bjePvuKy7kA287n5FGNTuvis7x29VDNRpVsG64olGvsbpeY6gK6rVgbaNiTaPq\nHHudZ9O64SIPyQC86dz13Pbv3sIl29azYU2DDSND3ePAweqhGttH1zAyVKOqQb0GEZ3vq4Y6x6tn\nNKpgdG2D1fXacX+iVQHnbhjhsh2vYdNZwydsvxaddTaqYKRRsXqo89pILWD1UG02S6MKhqrj75yq\nBqNrO5nrtWCk0clU1eC1Zw2zcV2DRhVUtc765963te5jYmSoNjs994E+3N1eVYM1jYoNI0MMVTH7\ns1XReZ2gNu82GOpup16DdavqbB9dc9yTZ2dZdK5fBWuHO+v+wNvO95CMTrvopYMj4grgt4EK+Gxm\n/veIuB4Yz8w9EbEK+H3gYjp77FfNvAB7MmNjYzk+Pv6KfwBJ+rskIu7NzLHFxvXygiqZuRfYO2/e\ndXMuHwX+5VJDSpKWh0dkJalAlrskFchyl6QCWe6SVCDLXZIK1NNbIZdlwxGTwEOnePWN9PlfG/SJ\nuZZupWYz19KYa2leSa5zM3PRT4EOrNxfiYgY7+V9nqebuZZupWYz19KYa2lORy4Py0hSgSx3SSrQ\nmVruNw06wEmYa+lWajZzLY25lmbZc52Rx9wlSS/vTN1zlyS9jDOu3Bc7WfcgRMTWiPhGRByIiH0R\n8UuDzjRXRFQR8e2I+PKgs8yIiHMi4vaI+L/d2+2fDDoTQET8cvc+fCAibun+x9NBZflsRDwREQ/M\nmbchIr4WEd/tfj/t/6v6JLk+1r0v74uIP4qIc1ZCrjnL/kNEZERsXCm5IuKD3S7bFxEf7fd2z6hy\n7/Fk3YPQBD6UmRcClwK/sEJyzfgl4MCgQ8zzP4CvZObfB/4hKyBfRGwGfhEYy8yL6PyL66sGGOlm\nYOe8ebuBr2fmduDr3enT7WZOzPU14KLMfAPwt8CHT3coFs5FRGwFLgMePt2Bum5mXq6I+Ak6555+\nQ2a+HvjNfm/0jCp35pysOzOngJmTdQ9UZj6Wmd/qXn6eTlFtHmyqjojYArwL+Mygs8yIiLOAtwG/\nC5CZU5n5zGBTzaoDq7tnFBvhxLOOnTaZ+U1OPKPZlcDvdS//HvDPTmsoFs6VmV/NzJmTyt5F54xt\nA8/V9XHgP7LAqT9Ph5Pk+nnghsw81h3zRL+3e6aV+0In614RJTojIrbROWnJ3YNNMuu36TywV9LZ\nVM8HJoHPdQ8XfSYi1gw6VGb+gM4e1MPAY8CzmfnVwaY6wWsy8zHo7FQArx5wnoX8W+COQYcAiIhd\nwA8y8zuDzjLPBcCPR8TdEfF/IuIf93sDZ1q593Qi7kGJiLXAHwL/PjOfWwF5fgp4IjPvHXSWeerA\nG4FPZubFwGEGc3jhON3j11cC5wE/AqyJiPcMNtWZJSI+Qucw5RdWQJYR4CPAdYuNHYA6sJ7OYdxf\nBW6LiIX67ZSdaeXey8m6ByIihugU+xcy80uDztP1VmBXRHyfziGsn4yI/zXYSEDnfpzIzJm/bm6n\nU/aD9k7ge5k5mZnTwJeAtww403z/LyJeC9D93vc/509VRLwX+CngXy3HOZRPwd+j80T9ne7vwBbg\nWxGxEs5WPgF8KTv+ms5f1n19sfdMK/deTtZ92nWfcX8XOJCZvzXoPDMy88OZuSUzt9G5rf4sMwe+\nJ5qZjwOPRMTrurPeAewfYKQZDwOXRsRI9z59Byvghd555p6M/r3Anwwwy6yI2An8J2BXZh4ZdB6A\nzLw/M1+dmdu6vwMTwBu7j79B+2PgJwEi4gKgQZ//wdkZVe7dF2yuBe6k80t3W2buG2wqoLOH/K/p\n7Bn/TffrikGHWuE+CHwhIu4D/hHw6wPOQ/cviduBbwH30/n9GNgnHCPiFuCvgNdFxEREvA+4Abgs\nIr5L5x0gN6yQXJ8A1gFf6z7+P7VCcg3cSXJ9Fji/+/bIW4H39vuvHT+hKkkFOqP23CVJvbHcJalA\nlrskFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kq0P8H47XvjvpdAVUAAAAASUVORK5CYII=\n", "text/plain": ["<matplotlib.figure.Figure at 0x1f893ea52b0>"]}, "metadata": {}, "output_type": "display_data"}], "source": ["import matplotlib.pyplot as plt\n", "x = nuage[552][0]\n", "plt.plot(X,Y,'.')\n", "plt.plot([x,x], [0,1])"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Le premier point de coupure trouv\u00e9 (le trait orange) correspond \u00e0 un des bords d'un des escaliers."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Q7 - optimisation encore\n", "\n", "Recommencer sur les deux intervalles trouv\u00e9s. La question \u00e9tait juste histoire que le r\u00e9sultat \u00e0 la question pr\u00e9c\u00e9dente est reproductible sur d'autres intervalles."]}, {"cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [{"data": {"text/plain": ["((1, 0.0), (565, 618.0710615624871))"]}, "execution_count": 13, "metadata": {}, "output_type": "execute_result"}], "source": ["optimise(nuage, 0, 68, fct), optimise(nuage, 68, len(nuage), fct)"]}, {"cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [{"data": {"text/plain": ["[<matplotlib.lines.Line2D at 0x1f8943ece80>]"]}, "execution_count": 14, "metadata": {}, "output_type": "execute_result"}, {"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAFOlJREFUeJzt3X+Q3Hd93/Hne3dvTzpJtiV0IJCE\nZCcytXBoDVfbhQklAc/IaiI305SxU1raMrhkYpImNEUMHTfjThkDnZBmcAAPIQ4pseM4NNEQGcMQ\nUmaS2PgMwViSFTQC24et+PAP2Zasu9vdd//YvfPpdPLtSSvt6ZPnY+bm9vv9fvb7fd3u9173ve/e\n3jcyE0lSWSr9DiBJ6j3LXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnuklSgWr82vHbt\n2ty8eXO/Ni9J56QHHnjgR5k5vNC4vpX75s2bGR0d7dfmJemcFBGPdDPO0zKSVCDLXZIKZLlLUoEs\nd0kqkOUuSQVasNwj4nMR8WREPHSS5RERvx0RByLiwYh4Y+9jSpIWo5s/hbwN+CTw+ZMsvxrY0vm4\nAvhU5/OS94f3PcpvfnU/zx6doloJVi8f4OhUkwhoNpPJZrJmaIBjjSZHJpu0WkkzYbAaRCU4NtUC\noBLwhvXnk0C9VmH1UJ1nj07y/R8d4fCLUzRaSatzwasV9SrLB6s888Ikzc68ejVoZhJArVLhFSvr\nHD46xQuTzZn1VyvBinqNtSvrvOaC5XzzB0/PbH96zLJahclmsv6C5Vx96Tp+76++z0QzqQa89ycv\nYuf2S87ioyuAm3fv4/P3/oBjUy0qEdRrFTatGWLlshoP/fBwZz4kzOwj0H4+Vw8N8NyxBlPNlxZE\n56NaDWoRTDRbM/erVmDDBUMMVINGK3nqyCSNRotmJssGqhyZbNBsvbSe7Hyud8YDNBOqARtWD/Gq\n8wb5uydf4PljU+07Zfs+K+pVmgmtVjJYrxAZHH5xitnXdKt29tlWwrrzBjk61eLw0Zf2+WW1CgQ0\nW8lgtUKtGhzp7O+rBmscmWrSaLSOe0yWDVTIhKlWiyAYqASNTJrNbH8tnS9q5bIqjRZMNJpAsGqw\nyrJalRcmG7z6vGUcev4YzRYsH6jw9JHjc08/9oO1CtVoZ6pWYHCgyrHJJgQMDbTXf/6yGrVqMNFo\nkQEvHGtwbKo189hOWz5QYarZotFqrzuANSvq/OpVr+MXrnht9zvTIkU3l9mLiM3AlzLz0nmWfQb4\ny8y8vTO9H3hbZj7xcuscGRnJvv2d+907efjQ82zbv70/2++T973Vgj+TPvrNjwLwwcs/CLSL/dPf\nONjPSFriPvJzP7Hogo+IBzJzZKFxvTjnvh54bNb0WGfefKGuj4jRiBgdHx/vwaZP0aHvkoce7N/2\n++TLew71O0LRHn76YR5++uGZaR9vLeTuh172GPi09KLcY5558/46kJm3ZuZIZo4MDy/47tkzas2K\nel+33w/bXr+u3xH+QfHx1kKuvvTVZ2zdvfj3A2PAxlnTG4DHe7DeM+pVq5bxkZ/7Cc+564yZfrw9\n5+45936cc+9Fue8CboiIO2i/kHp4ofPtS8UvXPHaM/rg9ptl3n87t1/i86C+WLDcI+J24G3A2ogY\nA/47MACQmZ8GdgPbgQPAUeA/nKmwkqTuLFjumXndAssT+KWeJZIknTbfoSpJBbLcJalAlrskFchy\nl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnuklQgy12SCmS5S1KBLHdJ\nKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ5S5JBbLcJalAlrskFchyl6QC\nWe6SVCDLXZIK1FW5R8S2iNgfEQciYuc8y18bEV+PiG9HxIMRsb33USVJ3Vqw3COiCtwCXA1sBa6L\niK1zhv034M7MvAy4FvidXgeVJHWvmyP3y4EDmXkwMyeBO4Br5oxJ4LzO7fOBx3sXUZK0WLUuxqwH\nHps1PQZcMWfMbwBfiYj3AyuAd/QknSTplHRz5B7zzMs509cBt2XmBmA78AcRccK6I+L6iBiNiNHx\n8fHFp5UkdaWbch8DNs6a3sCJp13eA9wJkJl/AywD1s5dUWbempkjmTkyPDx8aoklSQvqptzvB7ZE\nxIURUaf9gumuOWMeBd4OEBGX0C53D80lqU8WLPfMbAA3APcA+2j/VcyeiLgpInZ0hn0AeG9EfAe4\nHfj3mTn31I0k6Szp5gVVMnM3sHvOvBtn3d4LvKW30SRJp8p3qEpSgSx3SSqQ5S5JBbLcJalAlrsk\nFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnuklQgy12SCmS5S1KB\nLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ5S5JBbLcJalAlrskFchy\nl6QCWe6SVKCuyj0itkXE/og4EBE7TzLmnRGxNyL2RMQf9jamJGkxagsNiIgqcAtwFTAG3B8RuzJz\n76wxW4APAW/JzGci4pVnKrAkaWHdHLlfDhzIzIOZOQncAVwzZ8x7gVsy8xmAzHyytzElSYvRTbmv\nBx6bNT3WmTfbxcDFEfFXEXFvRGybb0URcX1EjEbE6Pj4+KklliQtqJtyj3nm5ZzpGrAFeBtwHfDZ\niLjghDtl3pqZI5k5Mjw8vNiskqQudVPuY8DGWdMbgMfnGfNnmTmVmd8H9tMue0lSH3RT7vcDWyLi\nwoioA9cCu+aM+VPgpwAiYi3t0zQHexlUktS9Bcs9MxvADcA9wD7gzszcExE3RcSOzrB7gKciYi/w\ndeDXM/OpMxVakvTyFvxTSIDM3A3snjPvxlm3E/i1zockqc98h6okFchyl6QCWe6SVCDLXZIKZLlL\nUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnuklQgy12SCmS5S1KBLHdJKpDlLkkFstwlqUCWuyQV\nyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ5S5JBbLcJalAlrskFchyl6QCWe6SVCDLXZIKZLlLUoEs\nd0kqUFflHhHbImJ/RByIiJ0vM+7nIyIjYqR3ESVJi7VguUdEFbgFuBrYClwXEVvnGbcK+GXgvl6H\nlCQtTjdH7pcDBzLzYGZOAncA18wz7n8AHwOO9TCfJOkUdFPu64HHZk2PdebNiIjLgI2Z+aUeZpMk\nnaJuyj3mmZczCyMqwCeADyy4oojrI2I0IkbHx8e7TylJWpRuyn0M2DhregPw+KzpVcClwF9GxA+A\nK4Fd872ompm3ZuZIZo4MDw+fempJ0svqptzvB7ZExIURUQeuBXZNL8zMw5m5NjM3Z+Zm4F5gR2aO\nnpHEkqQFLVjumdkAbgDuAfYBd2bmnoi4KSJ2nOmAkqTFq3UzKDN3A7vnzLvxJGPfdvqxJEmnw3eo\nSlKBLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ5S5JBbLcJalAlrsk\nFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnuklQgy12SCmS5S1KB\nLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUoK7KPSK2RcT+iDgQETvnWf5rEbE3Ih6MiK9FxKbe\nR5UkdWvBco+IKnALcDWwFbguIrbOGfZtYCQz3wDcBXys10ElSd3r5sj9cuBAZh7MzEngDuCa2QMy\n8+uZebQzeS+wobcxJUmL0U25rwcemzU91pl3Mu8B7p5vQURcHxGjETE6Pj7efUpJ0qJ0U+4xz7yc\nd2DEu4AR4OPzLc/MWzNzJDNHhoeHu08pSVqUWhdjxoCNs6Y3AI/PHRQR7wA+DPzzzJzoTTxJ0qno\n5sj9fmBLRFwYEXXgWmDX7AERcRnwGWBHZj7Z+5iSpMVYsNwzswHcANwD7APuzMw9EXFTROzoDPs4\nsBL444j424jYdZLVSZLOgm5Oy5CZu4Hdc+bdOOv2O3qcS5J0GnyHqiQVyHKXpAJZ7pJUIMtdkgpk\nuUtSgSx3SSqQ5S5JBbLcJalAlrskFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7\nJBXIcpekAlnuklQgy12SCmS5S1KBLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtS\ngSx3SSpQV+UeEdsiYn9EHIiInfMsH4yIP+osvy8iNvc6qCSpewuWe0RUgVuAq4GtwHURsXXOsPcA\nz2TmjwOfAD7a66CSpO7VuhhzOXAgMw8CRMQdwDXA3lljrgF+o3P7LuCTERGZmT3MCsDNu/fx+Xsf\n4ehkE4BqQK1aoRLQbCWDtQoTzaQKNDLJhGW1Cgm8ONWklXBH/SkArt3556xbNcgt73oTb9q0utdR\nl4QHHnmGj969jwPjRyCTI5NNMpNqJdhwwXJ++OyLTDRbBNDMlx7PqUaLZufZq1eD85cP8MKxBsca\nLaaf1GrAhtVDXLxuFd8de5ZDz00ct+1KQAIDlaBWrZCZTDRaAAzWKrQSpneRBKaaL+0u1QqsGarT\nbCXPHWtQrwUTUy0IeOXKQaYyee7oFM1MqhE0WkkrX9ruQLVCNeDoVItKtDfQ6qx7sBq0gFYmy2pV\nBmsVnp9o0Ggm2fm6KhE086V11qtB0t7HKgHL6zXWrRrk4FNHaHZWPLTpKSD4sQ/9OZVKMFirUK9W\neOfIRnZuv6RXT6nUlW7KfT3w2KzpMeCKk43JzEZEHAZeAfyoFyGn3bx7H5/+xsHj5jUTmo3WzPRk\ns3nC/V6YPHHetEPPT/CvPvXX/Mkvvrm4gn/gkWd452f+eqZ8jtNMvjd+5ITZjYRG6/g7TDaT8Rcm\n51sFjzx9lEeePjrv9qeLcbKZJzwvL07NF2rWulsct83GZGdlCU/M+SHS5PhjiFYy80Nkdo5pE7N+\niByZbHJkzv7RTGjOOS6ZnHWfVsLzxxo8f6xx3Jj2XbJ9/2Yy1WwCzZl91oLX2dTNOfeYZ97cI/Ju\nxhAR10fEaESMjo+Pd5PvOF/ec2jR95nP3tYm9rY2HTfv3oNP9WTdS8m9B5+av9h1RrQmXkNr4jXz\nLuvVvit1q5sj9zFg46zpDcDjJxkzFhE14Hzg6bkrysxbgVsBRkZGFn3KZtvr151w5H4qbmr8uxPm\nXXnRK057vUvNlRe9gmoFC/4smfj7nz3psm2vX3cWk0jdHbnfD2yJiAsjog5cC+yaM2YX8O7O7Z8H\n/uJMnG/fuf0S3vfWixiqV2fmVaN9/nb5QIV6NVg1WKVeq7C8VmGgGtQqwcp6lRX1avvc6xzrVg0W\neUoG4E2bVnPnf3ozl29ezZoVddYMDXTOAwfLBypsGV7B0ECFagVqFYhof1420D5fPa1eDYZX1lle\nqxz3K1o1YNOaIa7a+irWnTd4wvYr0V5nvRoM1assH2i/NlIJWD5QmclSrwYD1eOfnGoFhle2M9cq\nwVC9nalagVefN8jaVXXq1aBaaa9/9nNb6ewTQwOVmenZO/pgZ3vVCqyoV1kzNMBANWa+tmq0Xyeo\nzHkMBjrbqVVg1bIaW4ZXUJ214vayaN+/GqwcbK/7fW+9yFMyOuuimw6OiO3AbwFV4HOZ+T8j4iZg\nNDN3RcQy4A+Ay2gfsV87/QLsyYyMjOTo6OhpfwGS9A9JRDyQmSMLjevmtAyZuRvYPWfejbNuHwP+\n9WJDSpLODN+hKkkFstwlqUCWuyQVyHKXpAJZ7pJUoK7+FPKMbDhiHHjkFO++lh7/a4MeMdfiLdVs\n5loccy3O6eTalJnDCw3qW7mfjogY7ebvPM82cy3eUs1mrsUx1+KcjVyelpGkAlnuklSgc7Xcb+13\ngJMw1+It1WzmWhxzLc4Zz3VOnnOXJL28c/XIXZL0Ms65cl/oYt39EBEbI+LrEbEvIvZExK/0O9Ns\nEVGNiG9HxJf6nWVaRFwQEXdFxMOdx+2f9TsTQET8auc5fCgibu/8x9N+ZflcRDwZEQ/NmrcmIr4a\nEd/rfD7r/6v6JLk+3nkuH4yI/xsRFyyFXLOW/ZeIyIhYu1RyRcT7O122JyI+1uvtnlPl3uXFuvuh\nAXwgMy8BrgR+aYnkmvYrwL5+h5jjfwNfzsx/BPxjlkC+iFgP/DIwkpmX0v4X19f2MdJtwLY583YC\nX8vMLcDXOtNn222cmOurwKWZ+Qbg74APne1QzJ+LiNgIXAU8erYDddzGnFwR8VO0rz39hsx8PfC/\ner3Rc6rcmXWx7sycBKYv1t1XmflEZn6rc/t52kW1vr+p2iJiA/AvgM/2O8u0iDgPeCvwuwCZOZmZ\nz/Y31YwasLxzRbEhTrzq2FmTmd/gxCuaXQP8fuf27wP/8qyGYv5cmfmVzJy+qOy9tK/Y1vdcHZ8A\n/ivzXPrzbDhJrl8Ebs7Mic6YJ3u93XOt3Oe7WPeSKNFpEbGZ9kVL7utvkhm/RXvHXkoX27sIGAd+\nr3O66LMRsaLfoTLzh7SPoB4FngAOZ+ZX+pvqBK/KzCegfVABvLLPeebzH4G7+x0CICJ2AD/MzO/0\nO8scFwM/GRH3RcT/i4h/2usNnGvl3tWFuPslIlYCfwL858x8bgnk+Rngycx8oN9Z5qgBbwQ+lZmX\nAUfoz+mF43TOX18DXAi8BlgREe/qb6pzS0R8mPZpyi8sgSxDwIeBGxca2wc1YDXt07i/DtwZEfP1\n2yk718q9m4t190VEDNAu9i9k5hf7nafjLcCOiPgB7VNYPx0R/6e/kYD28ziWmdO/3dxFu+z77R3A\n9zNzPDOngC8Cb+5zprn+PiJeDdD53PNf509VRLwb+Bng35yJayifgh+j/YP6O53vgQ3AtyJiKVyt\nfAz4YrZ9k/Zv1j19sfdcK/duLtZ91nV+4v4usC8zf7PfeaZl5ocyc0Nmbqb9WP1FZvb9SDQzDwGP\nRcTrOrPeDuztY6RpjwJXRsRQ5zl9O0vghd45Zl+M/t3An/Uxy4yI2AZ8ENiRmUf7nQcgM7+bma/M\nzM2d74Ex4I2d/a/f/hT4aYCIuBio0+N/cHZOlXvnBZsbgHtof9PdmZl7+psKaB8h/1vaR8Z/2/nY\n3u9QS9z7gS9ExIPAPwE+0uc8dH6TuAv4FvBd2t8ffXuHY0TcDvwN8LqIGIuI9wA3A1dFxPdo/wXI\nzUsk1yeBVcBXO/v/p5dIrr47Sa7PARd1/jzyDuDdvf5tx3eoSlKBzqkjd0lSdyx3SSqQ5S5JBbLc\nJalAlrskFchyl6QCWe6SVCDLXZIK9P8B9lDz6kne5/4AAAAASUVORK5CYII=\n", "text/plain": ["<matplotlib.figure.Figure at 0x1f894398550>"]}, "metadata": {}, "output_type": "display_data"}], "source": ["import matplotlib.pyplot as plt\n", "x = nuage[58][0]\n", "x2 = nuage[552][0]\n", "plt.plot(X,Y,'.')\n", "plt.plot([x,x], [0,1])\n", "plt.plot([x2,x2], [0,1])"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Q8 - fonction r\u00e9cursive\n", "\n", "Pouvez-vous imaginer une fonction r\u00e9cursive qui produit toutes les s\u00e9parations. Ecrire la fonction ``def recursive(nuage, i, j, f, th=0.1):``."]}, {"cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [{"data": {"text/plain": ["[68, 242, 565]"]}, "execution_count": 15, "metadata": {}, "output_type": "execute_result"}], "source": ["def recursive(nuage, i, j, f, th=0.1):\n", "    k, mx = optimise(nuage, i, j, f)\n", "    if mx <= th:\n", "        return None\n", "    r1 = recursive(nuage, i, k, f, th=th)\n", "    r2 = recursive(nuage, k, j, f, th=th)\n", "    if r1 is None and r2 is None:\n", "        return [k]\n", "    elif r1 is None:\n", "        return [k] + r2\n", "    elif r2 is None:\n", "        return r1 + [k]\n", "    else:\n", "        return r1 + [k] + r2\n", "    \n", "r = recursive(nuage, 0, len(nuage), fct)\n", "r"]}, {"cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [{"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAFTtJREFUeJzt3X+Q3PV93/Hne3dvTzpJgGQdyJYE\ngla4yJQW5wrUnrhObGaEkkjJTNqBNI3rekydCU6auG7lcYemZJpSu2OnHVPbjOMQpzaUEDdRPDKY\ncZwfkwbCYccYSSXWyAaOH+bMDwESp7vdffeP3TtOp5NuT6y0pw/Px8zN7fe7n/1+X7e797rvffb2\nvpGZSJLKUul3AElS71nuklQgy12SCmS5S1KBLHdJKpDlLkkFstwlqUCWuyQVyHKXpALV+rXjtWvX\n5qZNm/q1e0k6Iz344IM/zMzhhcb1rdw3bdrE6Ohov3YvSWekiHi0m3FOy0hSgSx3SSqQ5S5JBbLc\nJalAlrskFWjBco+Iz0fEMxHx8HGuj4j4HxGxPyIeioi39j6mJGkxuvlTyNuATwFfOM711wCbOx9X\nAp/ufF7yvnT/Y3zi3kd44fAU1UqwevkAh6eaRECzmUw2kzVDA0w0mhyabNJqJc2EwWoQlWBiqgVA\nJeCy9WeTQL1WYfVQnRcOT/K9Hx7i4CtTNFpJq3PCqxX1KssHqzz/8iTNzrp6NWhmEkCtUuENK+sc\nPDzFy5PNme1XK8GKeo21K+u86Zzl/PX3n5vZ//SYZbUKk81k/TnLuebSdfzOX36PI82kGvD+H72I\nndsuOY33rgBu3r2PL9z3fSamWlQiqNcqXLBmiJXLajz8xMHOekiYeY5A+/FcPTTAixMNppqvXhGd\nj2o1qEVwpNmauV21AhvOGWKgGjRaybOHJmk0WjQzWTZQ5dBkg2br1e1k53O9Mx6gmVAN2LB6iPPO\nGuRvn3mZlyam2jfK9m1W1Ks0E1qtZLBeITI4+MoUs8/pVu08Z1sJ684a5PBUi4OHX33OL6tVIKDZ\nSgarFWrV4FDn+b5qsMahqSaNRuuo+2TZQIVMmGq1CIKBStDIpNnM9tfS+aJWLqvSaMGRRhMIVg1W\nWVar8vJkgzeetYynX5qg2YLlAxWeO3R07un7frBWoRrtTNUKDA5UmZhsQsDQQHv7Zy+rUasGRxot\nMuDliQYTU62Z+3ba8oEKU80WjVZ72wGsWVHnV69+Mz935fndP5kWKbo5zV5EbAK+kpmXznPdZ4E/\nzczbO8uPAO/MzKdOtM2RkZHs59+5f+n+x5j44w8DcFPjF/qW41QbPO+PATjyg5/iA++w4E+nm3fv\nIz/1SQA+e9mOPqfRUvSbP/P3F13wEfFgZo4sNK4Xc+7rgcdnLY911s0X6vqIGI2I0fHx8R7s+uR9\n9eGn2FJ5lC2Vrt4PcMaqDD5JZfBJAO7e83Sf07y+3L3naS46+AQXHXyi31G0RH314RMeA78mvSj3\nmGfdvL8OZOatmTmSmSPDwwu+e/aUuubSN/Z1//2w9S3r+h3hdcX7Wws5lT3Ui38/MAZsnLW8AXiy\nB9s9pX7uyvP5wf0rGHvuMLVKFDvnDu25SKdkTr+d2y7hL25ZztMvTlAJnHN3zv20zrn3otx3ATdE\nxB20X0g9uNB8+1Jx3qplnLdqGfvfu63fUU6Jndsu4b13/3778laLvR/OXzPE+WuGOPBffqLfUfQ6\ns2C5R8TtwDuBtRExBvxHYAAgMz8D7Aa2AfuBw8B7T1VYSVJ3Fiz3zLxugesT+KWeJZIkvWa+Q1WS\nCmS5S1KBLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ5S5JBbLcJalA\nlrskFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnuklQgy12SCmS5\nS1KBLHdJKpDlLkkFstwlqUCWuyQVqKtyj4itEfFIROyPiJ3zXH9+RHwjIr4VEQ9FxLbeR5UkdWvB\nco+IKnALcA2wBbguIrbMGfYfgDsz83LgWuB/9jqoJKl73Ry5XwHsz8wDmTkJ3AHsmDMmgbM6l88G\nnuxdREnSYtW6GLMeeHzW8hhw5Zwxvw58LSI+CKwA3t2TdJKkk9LNkXvMsy7nLF8H3JaZG4BtwO9F\nxDHbjojrI2I0IkbHx8cXn1aS1JVuyn0M2DhreQPHTru8D7gTIDP/ClgGrJ27ocy8NTNHMnNkeHj4\n5BJLkhbUTbk/AGyOiAsjok77BdNdc8Y8BrwLICIuoV3uHppLUp8sWO6Z2QBuAO4B9tH+q5g9EXFT\nRGzvDPsQ8P6I+DZwO/AvM3Pu1I0k6TTp5gVVMnM3sHvOuhtnXd4LvL230SRJJ8t3qEpSgSx3SSqQ\n5S5JBbLcJalAlrskFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnu\nklQgy12SCmS5S1KBLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ5S5J\nBbLcJalAlrskFchyl6QCWe6SVKCuyj0itkbEIxGxPyJ2HmfMP4uIvRGxJyK+1NuYkqTFqC00ICKq\nwC3A1cAY8EBE7MrMvbPGbAY+Arw9M5+PiHNPVWBJ0sK6OXK/AtifmQcycxK4A9gxZ8z7gVsy83mA\nzHymtzElSYvRTbmvBx6ftTzWWTfbxcDFEfGXEXFfRGydb0MRcX1EjEbE6Pj4+MklliQtqJtyj3nW\n5ZzlGrAZeCdwHfC5iDjnmBtl3pqZI5k5Mjw8vNiskqQudVPuY8DGWcsbgCfnGfNHmTmVmd8DHqFd\n9pKkPuim3B8ANkfEhRFRB64Fds0Z84fAjwFExFra0zQHehlUktS9Bcs9MxvADcA9wD7gzszcExE3\nRcT2zrB7gGcjYi/wDeDDmfnsqQotSTqxBf8UEiAzdwO756y7cdblBH6t8yFJ6jPfoSpJBbLcJalA\nlrskFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnuklQgy12SCmS5\nS1KBLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ5S5JBbLcJalAlrsk\nFchyl6QCWe6SVCDLXZIK1FW5R8TWiHgkIvZHxM4TjPvZiMiIGOldREnSYi1Y7hFRBW4BrgG2ANdF\nxJZ5xq0Cfhm4v9chJUmL082R+xXA/sw8kJmTwB3AjnnG/QbwMWCih/kkSSehm3JfDzw+a3mss25G\nRFwObMzMr/QwmyTpJHVT7jHPupy5MqICfBL40IIbirg+IkYjYnR8fLz7lJKkRemm3MeAjbOWNwBP\nzlpeBVwK/GlEfB+4Ctg134uqmXlrZo5k5sjw8PDJp5YknVA35f4AsDkiLoyIOnAtsGv6ysw8mJlr\nM3NTZm4C7gO2Z+boKUksSVrQguWemQ3gBuAeYB9wZ2buiYibImL7qQ4oSVq8WjeDMnM3sHvOuhuP\nM/adrz2WJOm18B2qklQgy12SCmS5S1KBLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpk\nuUtSgSx3SSqQ5S5JBbLcJalAlrskFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7\nJBXIcpekAlnuklQgy12SCmS5S1KBLHdJKpDlLkkFstwlqUCWuyQVqKtyj4itEfFIROyPiJ3zXP9r\nEbE3Ih6KiK9HxAW9jypJ6taC5R4RVeAW4BpgC3BdRGyZM+xbwEhmXgbcBXys10ElSd3r5sj9CmB/\nZh7IzEngDmDH7AGZ+Y3MPNxZvA/Y0NuYkqTF6Kbc1wOPz1oe66w7nvcBX53vioi4PiJGI2J0fHy8\n+5SSpEXpptxjnnU578CInwdGgI/Pd31m3pqZI5k5Mjw83H1KSdKi1LoYMwZsnLW8AXhy7qCIeDfw\nUeCfZOaR3sSTJJ2Mbo7cHwA2R8SFEVEHrgV2zR4QEZcDnwW2Z+YzvY8pSVqMBcs9MxvADcA9wD7g\nzszcExE3RcT2zrCPAyuB34+Iv4mIXcfZnCTpNOhmWobM3A3snrPuxlmX393jXJKk18B3qEpSgSx3\nSSqQ5S5JBbLcJalAlrskFchyl6QCWe6SVCDLXZIKZLlLUoEsd0kqkOUuSQWy3CWpQJa7JBXIcpek\nAlnuklQgy12SCmS5S1KBLHdJKpDlLkkFstwlqUCWuyQVyHKXpAJZ7pJUIMtdkgpkuUtSgSx3SSqQ\n5S5JBbLcJalAlrskFchyl6QCdVXuEbE1Ih6JiP0RsXOe6wcj4n93rr8/Ijb1OqgkqXsLlntEVIFb\ngGuALcB1EbFlzrD3Ac9n5t8FPgn8114HlSR1r9bFmCuA/Zl5ACAi7gB2AHtnjdkB/Hrn8l3ApyIi\nMjN7mBWAm3fv4wv3PcrhySYA1YBatUIloNlKBmsVjjSTKtDIJBOW1Sok8MpUk9asRHfUn6VerZCP\nPs+PXLC611GXhJcmGjz+3GHe+hv3QiaHJptkJtVKsOGc5TzxwiscabYIoJmv3p9TjRbNzn1VrwZn\nLx/g5YkGE40W03dhNWDD6iEuXreK74y9wNMvHjlq35WABAYqQa1aITM50mgBMFir0EqYfookMNV8\n9cGpVmDNUJ1mK3lxokG9FhyZakHAuSsHmcrkxcNTNDOpRtBo5cxjWwkYqFaoBhyealGJ9g5anW0P\nVoMW0MpkWa3KYK3CS0caNJpJdr6uSgTNfHWb9WqQtJ9jlYDl9RrrVg1y4NlDNFuv7rcSQWZSqQSD\ntQr/6dHnOXfVIBf07BGVutNNua8HHp+1PAZcebwxmdmIiIPAG4Af9iLktJt37+Mzf37gqHXNhGaj\nNbM82Wwec7uXJ49d9+r4Ftd++v/yB7/4tuIK/sFHn2fvUwfJhFcOTR59ZTP57vihY27TSGi0Wket\nm2wm4y9PHjO2mfDoc4d59LnD8+5/uhgnm3nM4/LKVGueW8zadouj9tmY7Gws4ak5P0SaHH0M0Upm\nfojMzjHtyKwfIocmmxya8/xoJjTnHJdMzrpNK9s/NF+aaByz31bnds1mMtVs0mi2ePKFV7h59z52\nbrvkRF+y1FPdzLnHPOvmHpF3M4aIuD4iRiNidHx8vJt8R7l7z9OLvs2J7G1dwN5W+5jqvgPP9nTb\nS8F9B56lOfEmWkfe1O8or1sHzl7PgbPX9/y5Ky2kmyP3MWDjrOUNwJPHGTMWETXgbOC5uRvKzFuB\nWwFGRkYWPWWz9S3rjjlyfy1uavzCzOWrLnpDz7a7VFx10Rv4xL0/NTNtoNPvs5ftAOADb1nX5yR6\nvenmyP0BYHNEXBgRdeBaYNecMbuA93Qu/yzwJ6divn3ntkv4wDsuYqhenVlXjfb87fKBCvVqsGqw\nSr1WYXmtwkA1qFWClfUqK+rV9tzrHOtWDRY5JQPwIxes5s5//Tau2LSaNSvqrBkaYLDWvp+WD1TY\nPLyCoYEK1QrUKhDR/rxsoD1fPa1eDYZX1lleqxz1K1o14II1Q1y95TzWnTV4zP4r0d5mvRoM1ass\nH6h05qVh+UBlJku9GgxUj35wqhUYXtnOXKsEQ/V2pmoF3njWIGtX1alXg2qlvf3Zj22l85wYGqjM\nLM9+og929letwIp6lTVDAwxUY+Zrq0b7dYLKnPtgoLOfWgVWLauxeXgF1Vkbbl8X7dtXg5WD7W1/\n4B0XOSWj0y666eCI2Ab8FlAFPp+Z/zkibgJGM3NXRCwDfg+4nPYR+7XTL8Aez8jISI6Ojr7mL0CS\nXk8i4sHMHFloXDfTMmTmbmD3nHU3zro8AfzTxYaUJJ0avkNVkgpkuUtSgSx3SSqQ5S5JBbLcJalA\nXf0p5CnZccQ48OhJ3nwtPf7XBj1irsVbqtnMtTjmWpzXkuuCzBxeaFDfyv21iIjRbv7O83Qz1+It\n1WzmWhxzLc7pyOW0jCQVyHKXpAKdqeV+a78DHIe5Fm+pZjPX4phrcU55rjNyzl2SdGJn6pG7JOkE\nzrhyX+hk3f0QERsj4hsRsS8i9kTEr/Q702wRUY2Ib0XEV/qdZVpEnBMRd0XE/+vcb/+435kAIuJX\nO4/hwxFxe+c/nvYry+cj4pmIeHjWujURcW9EfLfz+bT/r+rj5Pp457F8KCL+T0ScsxRyzbru30ZE\nRsTapZIrIj7Y6bI9EfGxXu/3jCr3Lk/W3Q8N4EOZeQlwFfBLSyTXtF8B9vU7xBz/Hbg7M/8e8A9Y\nAvkiYj3wy8BIZl5K+19cX9vHSLcBW+es2wl8PTM3A1/vLJ9ut3FsrnuBSzPzMuBvgY+c7lDMn4uI\n2AhcDTx2ugN13MacXBHxY7TPPX1ZZr4F+G+93ukZVe7MOll3Zk4C0yfr7qvMfCozv9m5/BLtolrf\n31RtEbEB+Angc/3OMi0izgLeAfw2QGZOZuYL/U01owYs75xRbIhjzzp22mTmn3PsGc12AL/bufy7\nwE+f1lDMnyszv5aZ0yeVvY/2Gdv6nqvjk8C/Y55Tf54Ox8n1i8DNmXmkM+aZXu/3TCv3+U7WvSRK\ndFpEbKJ90pL7+5tkxm/RfmIvpZPtXQSMA7/TmS76XESs6HeozHyC9hHUY8BTwMHM/Fp/Ux3jvMx8\nCtoHFcC5fc4zn38FfLXfIQAiYjvwRGZ+u99Z5rgY+NGIuD8i/iwi/lGvd3CmlXtXJ+Lul4hYCfwB\n8G8y88UlkOcngWcy88F+Z5mjBrwV+HRmXg4coj/TC0fpzF/vAC4E3gSsiIif72+qM0tEfJT2NOUX\nl0CWIeCjwI0Lje2DGrCa9jTuh4E7I2K+fjtpZ1q5d3Oy7r6IiAHaxf7FzPxyv/N0vB3YHhHfpz2F\n9eMR8b/6GwloP45jmTn9281dtMu+394NfC8zxzNzCvgy8LY+Z5rrBxHxRoDO557/On+yIuI9wE8C\n//xUnEP5JPwd2j+ov935HtgAfDMilsLZyseAL2fbX9P+zbqnL/aeaeXezcm6T7vOT9zfBvZl5if6\nnWdaZn4kMzdk5iba99WfZGbfj0Qz82ng8Yh4c2fVu4C9fYw07THgqogY6jym72IJvNA7x+yT0b8H\n+KM+ZpkREVuBfw9sz8zD/c4DkJnfycxzM3NT53tgDHhr5/nXb38I/DhARFwM1OnxPzg7o8q984LN\nDcA9tL/p7szMPf1NBbSPkP8F7SPjv+l8bOt3qCXug8AXI+Ih4B8Cv9nnPHR+k7gL+CbwHdrfH317\nh2NE3A78FfDmiBiLiPcBNwNXR8R3af8FyM1LJNengFXAvZ3n/2eWSK6+O06uzwMXdf488g7gPb3+\nbcd3qEpSgc6oI3dJUncsd0kqkOUuSQWy3CWpQJa7JBXIcpekAlnuklQgy12SCvT/ASq5AD2686hT\nAAAAAElFTkSuQmCC\n", "text/plain": ["<matplotlib.figure.Figure at 0x1f8943313c8>"]}, "metadata": {}, "output_type": "display_data"}], "source": ["import matplotlib.pyplot as plt\n", "plt.plot(X, Y, '.')\n", "for i in r:\n", "    x = nuage[i][0]\n", "    plt.plot([x,x], [0,1])"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Q9 - co\u00fbt\n", "\n", "Quel est le co\u00fbt de la fonction ``optimize`` en fonction de la taille de l'intervalle ? Peut-on mieux faire  (ce qu'on n'impl\u00e9mentera pas)."]}, {"cell_type": "markdown", "metadata": {}, "source": ["Tel qu'il est impl\u00e9ment\u00e9, le co\u00fbt est en $O(n^2)$, le co\u00fbt peut \u00eatre lin\u00e9aire en triant les \u00e9l\u00e9ments dans l'ordre croissant, ce qui a \u00e9t\u00e9 fait, ou $n\\ln n$ si on inclut le co\u00fbt du tri bien qu'on ne le fasse qu'une fois. Voyons plus en d\u00e9tail comment se d\u00e9barrasser du co\u00fbt en $O(n^2)$. Tout d'abord la version actuelle."]}, {"cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["503 ms \u00b1 21.1 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\n"]}], "source": ["def somme_diff_abs(xy, i, j):\n", "    m = sum(e[1] for e in xy[i:j]) / (j-i)\n", "    return sum(abs(e[1]-m) for e in xy[i:j])\n", "\n", "def difference_abs(nuage, i, j, k):\n", "    m1 = somme_diff_abs(nuage, i, k)\n", "    m2 = somme_diff_abs(nuage, k, j)\n", "    m = somme_diff_abs(nuage, i, j)\n", "    return abs(m1+m2-m)\n", "\n", "def optimise_abs(nuage, i, j):\n", "    mx = -1\n", "    ib = None\n", "    for k in range(i+1,j-1):\n", "        d = difference_abs(nuage, i,j,k)\n", "        if ib is None or d > mx:\n", "            mx = d\n", "            ib = k\n", "    if ib is None:\n", "        ib = i\n", "        mx = 0\n", "    return ib, mx\n", "\n", "%timeit optimise_abs(nuage, 0, len(nuage))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["L'instruction suivante permet de voir o\u00f9 le programme passe la majeure partie de son temps."]}, {"cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [], "source": ["# %prun optimise_abs(nuage, 0, len(nuage))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["La fonction [sum](https://docs.python.org/3/library/functions.html#sum) cache une boucle, avec la boucle ``for`` dans la fonction ``optimise``, cela explique le co\u00fbt en $O(n^2)$. Le fait qu'\u00e0 chaque it\u00e9ration, on passe une observation d'un c\u00f4t\u00e9 \u00e0 l'autre de la coupure puis on recalcule les moyennes... Il y a deux fa\u00e7ons d'optimiser ce calcul selon qu'on tient compte du fait que les valeurs de $Y$ sont binaires ou non.\n", "\n", "Dans le premier cas, il suffit de compter les valeurs 0 ou 1 de part et d'autres de la coupure (histogrammes) pour calculer la moyenne. Lorsque $k$ varie, il suffit de mettre \u00e0 jour les histogrammes en d\u00e9duisant et en ajoutant le $Y_k$ aux bons endroits."]}, {"cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [{"data": {"text/plain": ["((565, 235.4096814159292), (565, 235.40968141593424))"]}, "execution_count": 19, "metadata": {}, "output_type": "execute_result"}], "source": ["def histogramme_y(xy, i, j):\n", "    d = [0, 0]\n", "    for x, y in xy[i:j]:\n", "        d[y] += 1\n", "    return d\n", "\n", "def somme_diff_histogramme(d):\n", "    m = d[1] * 1.0 / (d[0] + d[1])\n", "    return (1-m) * d[1] + m * d[0]\n", "\n", "def optimise_rapide(nuage, i, j):\n", "    # On calcule les histogrammes.\n", "    d1 = histogramme_y(nuage, i, i+1)\n", "    d2 = histogramme_y(nuage, i+1, j)\n", "    d = d1.copy()\n", "    d[0] += d2[0]\n", "    d[1] += d2[1]\n", "    \n", "    m = somme_diff_histogramme(d)\n", "    m1 = somme_diff_histogramme(d1)\n", "    m2 = somme_diff_histogramme(d2)\n", "    mx = -1\n", "    ib = None\n", "    for k in range(i+1,j-1):\n", "        d = abs(m1+m2-m)\n", "        if ib is None or d > mx:\n", "            mx = d\n", "            ib = k\n", "        # On met \u00e0 jour les histogrammes. On ajoute d'un c\u00f4t\u00e9, on retranche de l'autre.\n", "        y = nuage[k][1] \n", "        d1[y] += 1\n", "        d2[y] -= 1\n", "        m1 = somme_diff_histogramme(d1)\n", "        m2 = somme_diff_histogramme(d2)\n", "    if ib is None:\n", "        ib = i\n", "        mx = 0\n", "    return ib, mx\n", "\n", "# On v\u00e9rifie qu'on obtient les m\u00eames r\u00e9sultats.\n", "optimise_rapide(nuage, 0, len(nuage)), optimise_abs(nuage, 0, len(nuage))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["C'est carr\u00e9ment plus rapide et cela marche pour toute fonction ``fct``."]}, {"cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["1.63 ms \u00b1 150 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 1000 loops each)\n"]}], "source": ["%timeit optimise_rapide(nuage, 0, len(nuage))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Si on ne suppose pas que les $Y_i$ sont binaires et qu'ils sont quelconques, les histogrammes contiendront plus de deux \u00e9l\u00e9ments. Dans ce cas, il faut conserver deux tableaux tri\u00e9s des $Y_i$, de part et d'autres de la coupure. Lorsqu'on bouge la coupure $k$, cela revient \u00e0 d\u00e9placer $Y_k$ d'un tableau \u00e0 l'autre ce qui se fera par recherche dichotomique donc en $O(\\ln n)$. La mise \u00e0 jour de la moyenne des valeurs absolues est imm\u00e9diate si la fonction ``fct=abs(x-y)`` et pas forc\u00e9ment imm\u00e9diate dans le cas g\u00e9n\u00e9ral. Lorsque c'est une valeur absolue, il faut utiliser quelques r\u00e9sultats sur la [r\u00e9gression quantile](http://www.xavierdupre.fr/app/ensae_teaching_cs/helpsphinx/notebooks/td_note_2017_2.html?highlight=mediane)."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Q10 - autre nuage de points\n", "\n", "Comment l'algorithme se comporte-t-il lorsque tous les points sont distincts ?"]}, {"cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [], "source": ["import random\n", "X2 = list(range(10))\n", "Y2 = X2"]}, {"cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [{"data": {"text/plain": ["[<matplotlib.lines.Line2D at 0x1f8944d3ba8>]"]}, "execution_count": 22, "metadata": {}, "output_type": "execute_result"}, {"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAW4AAAD8CAYAAABXe05zAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAC4NJREFUeJzt3cGL33edx/HXu0mLtiqGdi62pWlh\ncVcEqR12owVZrIddLHrZQ3dXYYXSy65WcRHXi/+AiB6KEOp6adBD7GGR4rqw9bCHlp1pC7WNQomm\nTa04lqxKWUhD33uY6aZJJzPfJPPL7/fJ7/E4JZNvZt58yTz55jPzm3d1dwAYxzXzHgCAiyPcAIMR\nboDBCDfAYIQbYDDCDTAY4QYYjHADDEa4AQazfxbv9KabbuqDBw/O4l0DXJXW19d/190rU66dSbgP\nHjyYtbW1WbxrgKtSVZ2Yeq2jEoDBCDfAYIQbYDDCDTAY4QYYjHADDEa4AfbA+olTeejxF7J+4tTM\nP9ZMvo8bYJmsnziVv3/4iZw+80au239Njtx/KHfddmBmH88TN8BleuL4qzl95o280cnrZ97IE8df\nnenHE26Ay3Tojhtz3f5rsq+Sa/dfk0N33DjTj+eoBOAy3XXbgRy5/1CeOP5qDt1x40yPSRLhBtgT\nd912YObBfpOjEoDBCDfAYIQbYDDCDTAY4QYYjHADDEa4AQYj3ACDEW6AwQg3wGCEG2Awwg0wGOEG\nGIxwAwxGuAEGMyncVfWlqnquqn5WVd+vqnfMejAAtrdruKvq5iRfSLLa3R9Msi/JfbMeDGCKK7ld\nfVFM3YCzP8k7q+r1JNcn+fXsRgKY5kpvV18Uuz5xd/fLSb6R5MUkryT5fXf/5PzrquqBqlqrqrWN\njY29nxTgPFd6u/qimHJUciDJp5PcnuR9SW6oqs+cf113H+7u1e5eXVlZ2ftJAc5zpberL4opRyWf\nSPLL7t5Ikqp6NMlHkzwyy8EAdnOlt6sviinhfjHJoaq6Psn/JrknydpMpwKY6EpuV18UU864n0xy\nNMlTSZ7d+juHZzwXABcw6btKuvvrSb4+41kAmMArJwEGI9wAgxFugMEIN8BghBtgMMINMBjhBhiM\ncAMMRrgBBiPcAIMRboDBCDfAYIQbYDDCDTAY4QYu2TJuWF8EU7e8A5xjWTesLwJP3MAlWdYN64tA\nuIFLsqwb1heBoxLgkizrhvVFINzAJVvGDeuLwFEJwGCEG2Awwg0wGOEGGIxwAwxGuAEGI9wAgxFu\ngMEIN8BghBtgMMINMBjhBhiMcAMMRrgBBjMp3FX13qo6WlU/r6pjVfWRWQ8GwPam/jzubyf5cXf/\nTVVdl+T6Gc4EwA52DXdVvSfJx5L8Q5J09+kkp2c7FrCT9ROnbJ5ZYlOeuO9IspHke1X1oSTrSR7s\n7tdmOhmwLdvVmXLGvT/Jh5N8p7vvTPJakq+ef1FVPVBVa1W1trGxscdjAm+yXZ0p4T6Z5GR3P7n1\n+6PZDPk5uvtwd6929+rKyspezgi8he3q7HpU0t2/qaqXqur93f2LJPckeX72owHbsV2dqd9V8vkk\nR7a+o+R4ks/NbiRgN7arL7dJ4e7uZ5KszngWACbwykmAwQg3wGCEG2Awwg0wGOEGGIxwAwxGuAEG\nI9wAgxFugMEIN8BghBtgMMINMBjhBhiMcAMMRrgBBiPccBHWT5zKQ4+/kPUTp+Y9Ckts6gYcWHq2\nq7MoPHHDRLarsyiEGyayXZ1F4agEJrJdnUUh3HARbFdnETgqARiMcAMMRrgBBiPcAIMRboDBCDfA\nYIQbYDDCDTAY4QYYjHADDEa4AQYj3ACDEW6AwQg3wGAmh7uq9lXV01X1o1kOBMDOLuaJ+8Ekx2Y1\nCADTTAp3Vd2S5JNJHp7tOLA929XhrKkbcL6V5CtJ3j3DWWBbtqvDuXZ94q6qe5P8trvXd7nugapa\nq6q1jY2NPRsQbFeHc005Krk7yaeq6ldJfpDk41X1yPkXdffh7l7t7tWVlZU9HpNlZrs6nKu6e/rF\nVX+Z5J+7+96drltdXe21tbXLHA3OWj9xynZ1rmpVtd7dq1OuteWdIdiuDmddVLi7+6dJfjqTSQCY\nxCsnAQYj3ACDEW6AwQg3wGCEG2Awwg0wGOEGGIxwAwxGuAEGI9wAgxFugMEIN8BghBtgMMINMBjh\nBhiMcLMj29Vh8diAwwXZrg6LyRM3F2S7Oiwm4eaCbFeHxeSohAu667YDOXL/IdvVYcEINzuyXR0W\nj6MSgMEIN8BghBtgMMINMBjhBhiMcAMMRrgBBiPcAIMRboDBCDfAYIQbYDDCDTAY4QYYjHADDGbX\ncFfVrVX1eFUdq6rnqurBKzEYANub8vO4zyT5cnc/VVXvTrJeVf/R3c/PeDYAtrHrE3d3v9LdT239\n+o9JjiW5edaDLTvb1YELuagNOFV1MMmdSZ6cxTBssl0d2MnkL05W1buS/DDJF7v7D9v8+QNVtVZV\naxsbG3s549KxXR3YyaRwV9W12Yz2ke5+dLtruvtwd6929+rKyspezrh0bFcHdrLrUUlVVZLvJjnW\n3d+c/UjYrg7sZMoZ991JPpvk2ap6ZuttX+vux2Y3FrarAxeya7i7+7+S1BWYBYAJvHISYDDCDTAY\n4QYYjHADDEa4AQYj3ACDEW6AwQg3wGCEG2Awwg0wGOEGGIxwAwxGuAEGI9wAgxFugMEI9zZsWAcW\n2UVteV8GNqwDi84T93lsWAcWnXCfx4Z1YNE5KjmPDevAohPubdiwDiwyRyUAgxFugMEIN8BghBtg\nMMINMBjhBhiMcAMMRrgBBiPcAIMRboDBCDfAYIQbYDDCDTAY4QYYzKRwV9VfVdUvquqFqvrqrIcC\n4MJ2DXdV7UvyUJK/TvKBJH9bVR+Y9WAAbG/KE/efJ3mhu4939+kkP0jy6VkMY7s6wO6mbMC5OclL\nb/n9ySR/sdeD2K4OMM2UJ+7a5m39touqHqiqtapa29jYuOhBbFcHmGZKuE8mufUtv78lya/Pv6i7\nD3f3anevrqysXPQgtqsDTDPlqOS/k/xJVd2e5OUk9yX5u70exHZ1gGl2DXd3n6mqf0ry70n2JfnX\n7n5uFsPYrg6wuylP3Onux5I8NuNZAJjAKycBBiPcAIMRboDBCDfAYIQbYDDV/bYXQV7+O63aSHLi\nEv/6TUl+t4fjjMy9OJf7cS7346yr4V7c1t2TXr04k3Bfjqpa6+7Vec+xCNyLc7kf53I/zlq2e+Go\nBGAwwg0wmEUM9+F5D7BA3ItzuR/ncj/OWqp7sXBn3ADsbBGfuAHYwcKE20Lis6rq1qp6vKqOVdVz\nVfXgvGeat6raV1VPV9WP5j3LvFXVe6vqaFX9fOvfyEfmPdM8VdWXtj5PflZV36+qd8x7pllbiHBb\nSPw2Z5J8ubv/LMmhJP+45PcjSR5McmzeQyyIbyf5cXf/aZIPZYnvS1XdnOQLSVa7+4PZ/NHT9813\nqtlbiHDnCi4kHkF3v9LdT239+o/Z/MS8eb5TzU9V3ZLkk0kenvcs81ZV70nysSTfTZLuPt3d/zPf\nqeZuf5J3VtX+JNdnmw1dV5tFCfd2C4mXNlRvVVUHk9yZ5Mn5TjJX30rylSRvzHuQBXBHko0k39s6\nOnq4qm6Y91Dz0t0vJ/lGkheTvJLk9939k/lONXuLEu5JC4mXTVW9K8kPk3yxu/8w73nmoaruTfLb\n7l6f9ywLYn+SDyf5TnffmeS1JEv7NaGqOpDN/53fnuR9SW6oqs/Md6rZW5RwT1pIvEyq6tpsRvtI\ndz8673nm6O4kn6qqX2XzCO3jVfXIfEeaq5NJTnb3m/8DO5rNkC+rTyT5ZXdvdPfrSR5N8tE5zzRz\nixLu/19IXFXXZfOLC/8255nmpqoqm2eYx7r7m/OeZ566+1+6+5buPpjNfxf/2d1X/RPVhXT3b5K8\nVFXv33rTPUmen+NI8/ZikkNVdf3W5809WYIv1k7aOTlrV3Ih8SDuTvLZJM9W1TNbb/va1u5P+HyS\nI1sPOceTfG7O88xNdz9ZVUeTPJXN78Z6OkvwKkqvnAQYzKIclQAwkXADDEa4AQYj3ACDEW6AwQg3\nwGCEG2Awwg0wmP8DL5F7pmi3lNEAAAAASUVORK5CYII=\n", "text/plain": ["<matplotlib.figure.Figure at 0x1f894331dd8>"]}, "metadata": {}, "output_type": "display_data"}], "source": ["import matplotlib.pyplot as plt\n", "plt.plot(X2,Y2,'.')"]}, {"cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [], "source": ["nuage2 = [(x,y) for x,y in zip(X2,Y2)]\n", "nuage2.sort()"]}, {"cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [{"data": {"text/plain": ["(5, [2, 3, 5, 7, 8])"]}, "execution_count": 24, "metadata": {}, "output_type": "execute_result"}], "source": ["r = recursive(nuage2, 0, len(nuage2), fct)\n", "len(r), r"]}, {"cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [{"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD8CAYAAABn919SAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAADmFJREFUeJzt3X9s3Hd9x/HXy744Ia0jjGNGSBu7\nllB/iGkqtrYrldDUgMYA0Qntj7IUMTQr/zAoiAm1+4f9VVYJIfijQooMFAmrCIVKQ4gxJhY0JnFh\nvqYSDS4QGdw4TRbXXHFG3Tonv/eHr6udX/bd93v+nj/3fEhRbOeS71tfJU9dPvb57YgQAGDn6yl6\nAABAPgg6ACSCoANAIgg6ACSCoANAIgg6ACSCoANAIgg6ACSCoANAIkrbebH9+/fHyMjIdl4SAHa8\narX6YkQMbfa4bQ36yMiIpqent/OSALDj2Z7byuM4cgGARBB0AEgEQQeARBB0AEgEQQeARGwadNtf\ns33R9rPrPvYm2/9u+9eNnwfaOyYAYDNbeYb+hKT3XvGxhyX9KCLeJulHjfcBAAXaNOgR8Z+SfnfF\nh++X9I3G29+Q9Fc5z4Ub+deH134U6LGfPabHfvZYoTN0kguPPqoLjz5a9Bgd4yff/pV+8u1fFT2G\nTjxxTCeeOFb0GNum1RcW/VFEnJekiDhv+83Xe6Dto5KOStKhQ4davBw2uPDzoifQc797rugROsqr\nM9yP9V48+79FjyBJujg3W/QI26rtnxSNiGMRMR4R40NDm75yFQDQolaD/j+2D0hS4+eL+Y0EAGhF\nq0H/rqSPNt7+qKR/yWccAECrtvJli09K+qmk223P2/47Sf8s6T22fy3pPY33AQAF2vSTohHx4ev8\n0uGcZwEAZMArRQEgEQQdABJB0AEgEQQdABJB0AEgEQQdABJB0AEgEQQdABJB0AEgEQQdABJB0AEg\nEQQdABJB0AGgjapzNT1+4oyqc7W2X6vVFXQAgE1U52o6MlnRSn1VfaUeTU2UNTY80Lbr8QwdANqk\nMruolfqqVkO6XF9VZXaxrdcj6ADQJuXRQfWVetRraVepR+XRwbZejyMXAGiTseEBTU2UVZldVHl0\nsK3HLRJBB4C2GhseaHvIX8ORCwAkgqADQCIIOgAkgqADQCIIOgAkgqADQCIIOgAkgqADQCIIOgAk\ngqADQCIIOgAkgqADQCIyBd32p22ftv2s7Sdt78lrMABAc1oOuu2Dkj4paTwi3i6pV9IDeQ0GAGhO\n1iOXkqQ32C5J2ivphewjAUA+Lr1S17na8rbs8+wELQc9Is5J+oKk5yWdl/T7iPhhXoMBQBbVuZpm\nzi9pvrasI5OVroh6liOXAUn3S7pN0lsl3WT7wWs87qjtadvTCwsLrU8KAE2ozC4qQgptzz7PTpDl\nyOXdkn4TEQsRcVnSU5LeeeWDIuJYRIxHxPjQ0FCGywHA1pVHB2VL1vbs8+wEWVbQPS+pbHuvpGVJ\nhyVN5zIVAGQ0NjygUwf2aWn5sqYmytu2Bq5ILQc9Ik7aPi7paUl1SackHctrMADIqn9PSf17Sl0R\ncynjkuiI+Jykz+U0CwAgA14pCgCJIOgAkAiCDgCJIOgAkAiCDgCJIOgAkAiCDgCJIOgAkAiCDgCJ\nIOgAkAiCDgCJIOgAkAiCDgCJIOgAcnfp1bpeeKl7dnl2CoIOIFev7fI8W3u5a3Z5dgqCDiBXa7s8\nQxHds8uzUxB0ALla2+Vp2d2zy7NTZNpYBABXGhse0OkD+3Rp+bKmJu7qmvVvnYCgA8hd/+6S+nd3\nzy7PTsGRCwAkgqADQCIIOgAkgqADQCIIOgAkgqADQCIIOgAkgqADQCIIOgAkgqADQCIIOgAkgqAD\nQCIyBd32G20ft/2c7Rnb9+Q1GACgOVm/2+KXJf0gIv7adp+kvTnMBKBF1bmaKrOLKo8O8p0Ou1DL\nQbe9T9K7JP2tJEXEiqSVfMYC0KzqXE1HJitaqa+qr9SjqYkyUe8yWY5cRiUtSPq67VO2J23fdOWD\nbB+1PW17emFhIcPlANxIZXZRK/VVrbL6rWtlCXpJ0jskfSUi7pb0B0kPX/mgiDgWEeMRMT40NJTh\ncgBupDw6qL5Sj3pZ/da1spyhz0uaj4iTjfeP6xpBB7A9xoYHNDVR5gy9i7Uc9Ii4YPus7dsj4peS\nDkv6RX6jAWjW2PAAIe9iWb/K5ROSphpf4TIr6WPZRwIAtCJT0CPiGUnjOc0CAMiAV4oCQCIIOgAk\ngqADQCIIOgAkgqADQCIIOgAkgqADQCIIOgAkgqADQCIIOgAkgqADQCIIOgAkgqADObj0al3nXlpW\nda5W9CjoYgQdyKg6V9PM+SWdrb2sI5MVoo7CEHQgo8rsolYjJHZ5omAEHcioPDqoHltmlycKlnVj\nEdD1xoYHtPvAPi0tX9bURJkVcCgMQQdy0L+7pP7dJQ0TcxSIIxcASARBB4BEEHQASARBB4BEEHQA\nSARBB4BEEHQASARBB4BEEHQASARBB4BEEHQASARBB4BEZA667V7bp2x/L4+BAACtyeMZ+kOSZnL4\ncwAAGWQKuu1bJL1f0mQ+4wDNqc7V9PiJM6x9A5T9+6F/SdJnJfXnMAvQlOpcTUcmK1qpr6qv1MNy\nCXS9lp+h2/6ApIsRUd3kcUdtT9ueXlhYaPVywFUqs4taqa9qlV2egKRsRy73Svqg7d9K+pak+2x/\n88oHRcSxiBiPiPGhoaEMlwM2Ko8Oqq/Uo152eQKSMhy5RMQjkh6RJNt/LukfIuLBnOYCNjU2PKCp\nibIqs4sqjw5y3IKux05R7GhjwwOEHGjIJegR8WNJP87jzwIAtIZXigJAIgg6ACSCoANAIgg6ACSC\noANAIgg6ACSCoANAIgg6ACSCoANAIgg6ACSCoANAIgg6ACSCoANAIgg6WnLplbrOvbTMLk+ggxB0\nNK06V9PMhSXN117WkckKUQc6BEFH0yqzi4oIBbs8gY5C0NG08uigbMvs8gQ6Civo0LSx4QHd+ZZ9\nWnrlsj7/vjIr4IAOQdDRkv49JfXvKRFzoINw5AIAiSDoAJAIgg4AiSDoAJAIgg4AiSDoAJAIgg4A\niSDoAJAIgg4AiSDoAJAIgg4AiSDoAJCIloNu+1bbJ2zP2D5t+6E8BwMANCfLM/S6pM9ExJ2SypI+\nbvuufMbCjVx69TLr3wBcpeWgR8T5iHi68fYlSTOSDuY1GK6tOlfTzPklnWX9G4Ar5HKGbntE0t2S\nTl7j147anrY9vbCwkMflulpldlGrsfY2698ArJc56LZvlvQdSZ+KiKUrfz0ijkXEeESMDw0NZb1c\n1yuPDqrHa2+z/g3Aepk2FtnepbWYT0XEU/mMhBsZGx7QpQP7tLRc19SHWP8G4HUtB922JX1V0kxE\nfDG/kbCZ/t271L97lw4ScwDrZDlyuVfSRyTdZ/uZxo/35TQXAKBJLT9Dj4j/kuQcZwEAZMArRQEg\nEQQdABJB0AEgEQQdABJB0AEgEQQdABJB0AEgEQQdABJB0AEgEQQdABJB0AEgEQQdABJB0JtQnavp\n8RNnWPsGoCNlWnDRTapzNR2ZrGilvqq+Uo+mJlguAaCz8Ax9iyqzi1qpr2o12OUJoDMR9C0qjw6q\nr9SjXrPLE0Bn4shli8aGBzQ1UVZldlHl0UGOWwB0HILehLHhAUIOoGNx5AIAiSDoAJAIgg4AiSDo\nAJAIgg4AiSDoAJAIgg4AiSDoAJAIgg4AiSDoAJAIgg4AiSDoAJCITEG3/V7bv7R9xvbDeQ0FAGhe\ny0G33SvpcUl/KekuSR+2fVdegwEAmpPlGfqfSjoTEbMRsSLpW5Luz2esjdjlCQCby/L90A9KOrvu\n/XlJf5ZtnKuxyxMAtiZL0H2Nj8VVD7KPSjoqSYcOHWr6Itfa5dn1QX/LHxc9ge540x1Fj9BRdt/J\n/Vhv/603Fz2CJOnNw6NFj7CtHHFVg7f2G+17JP1TRPxF4/1HJCkiPn+93zM+Ph7T09NNXee1Z+iX\n66vaxTN0AF3IdjUixjd7XJZn6P8t6W22b5N0TtIDkv4mw593TezyBICtaTnoEVG3/feS/k1Sr6Sv\nRcTp3CZbh12eALC5TEuiI+L7kr6f0ywAgAx4pSgAJIKgA0AiCDoAJIKgA0AiCDoAJKLlFxa1dDF7\nQdJci799v6QXcxxnp+N+vI57sRH3Y6MU7sdwRAxt9qBtDXoWtqe38kqpbsH9eB33YiPux0bddD84\ncgGARBB0AEjETgr6saIH6DDcj9dxLzbifmzUNfdjx5yhAwBubCc9QwcA3MCOCDrLqNfYvtX2Cdsz\ntk/bfqjomTqB7V7bp2x/r+hZimb7jbaP236u8ffknqJnKortTzf+nTxr+0nbe4qeqd06Pugso96g\nLukzEXGnpLKkj3fxvVjvIUkzRQ/RIb4s6QcRcYekP1GX3hfbByV9UtJ4RLxda9/i+4Fip2q/jg+6\ntnEZdaeLiPMR8XTj7Uta+8d6sNipimX7FknvlzRZ9CxFs71P0rskfVWSImIlIl4qdqpClSS9wXZJ\n0l5JLxQ8T9vthKBfaxl1V0dMkmyPSLpb0sliJynclyR9VtJq0YN0gFFJC5K+3jiCmrR9U9FDFSEi\nzkn6gqTnJZ2X9PuI+GGxU7XfTgj6lpZRdxPbN0v6jqRPRcRS0fMUxfYHJF2MiGrRs3SIkqR3SPpK\nRNwt6Q+SuvJzTrYHtPY/+dskvVXSTbYfLHaq9tsJQZ+XdOu6929RF/zX6Xps79JazKci4qmi5ynY\nvZI+aPu3WjuKu8/2N4sdqVDzkuYj4rX/tR3XWuC70bsl/SYiFiLisqSnJL2z4JnabicE/f+XUdvu\n09onNr5b8EyFsG2tnY/ORMQXi56naBHxSETcEhEjWvt78R8RkfyzsOuJiAuSztq+vfGhw5J+UeBI\nRXpeUtn23sa/m8Pqgk8QZ9opuh22cxn1DnCvpI9I+rntZxof+8fGbldAkj4haarx5GdW0scKnqcQ\nEXHS9nFJT2vtq8NOqQteMcorRQEgETvhyAUAsAUEHQASQdABIBEEHQASQdABIBEEHQASQdABIBEE\nHQAS8X+IytouEH9+fwAAAABJRU5ErkJggg==\n", "text/plain": ["<matplotlib.figure.Figure at 0x1f894500710>"]}, "metadata": {}, "output_type": "display_data"}], "source": ["import matplotlib.pyplot as plt\n", "plt.plot(X2,Y2,'.')\n", "for i in r:\n", "    x = nuage2[i][0]\n", "    plt.plot([x,x], [0,10])"]}, {"cell_type": "markdown", "metadata": {}, "source": ["La fonction va placer un point dans chaque intervalle, il y aura quasiment autant de points de coupures que de points. Presque autant car l'impl\u00e9mentation a quelques effets de bords comme la boucle ``for k in range(i+1,j-1):`` qui ne consid\u00e8re pas les extr\u00e9mit\u00e9s d'un intervalle comme de potentiels points de coupures."]}, {"cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [], "source": []}], "metadata": {"kernelspec": {"display_name": "Python 3", "language": "python", "name": "python3"}, "language_info": {"codemirror_mode": {"name": "ipython", "version": 3}, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.4"}}, "nbformat": 4, "nbformat_minor": 2}