{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A.e - Enonc\u00e9 12 d\u00e9cembre 2017 (2)\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 d'approximer une fonction $f$ par une fonction 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 = \\sqrt{X_i}[\\sqrt{X_i}]$ 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 = [ x**0.5 * int(x**0.5) 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 0x1c0e33655f8>]"]}, "execution_count": 5, "metadata": {}, "output_type": "execute_result"}, {"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD8CAYAAABn919SAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAGLpJREFUeJzt3Xt0VeWd//H395yTC5dwURBQwIhV\nS71rWrxga6uuQcsonc441tra0Sl2pu1I68yIv/766x/TcWVujl2LzlimWusaIrLU2nYmOEWnamkl\nyoEowilF0YRwDRAhXMz1+/sjJzRiQs7O2eeSnc9rLZfJyd45n8Xlw5NnP3s/5u6IiMjwFyt0ABER\nCYcKXUQkIlToIiIRoUIXEYkIFbqISESo0EVEIkKFLiISESp0EZGIUKGLiEREIp9vNmnSJK+srMzn\nW4qIDHvJZHKvu08e7Li8FnplZSVr167N51uKiAx7ZtaQyXGachERiQgVuohIRKjQRUQiQoUuIhIR\nKnQRkYgYtNDN7BEz22Nmb/R57Z/M7Ldm9rqZ/cTMJuQ2poiIDCaTEfqjwLzjXlsFnOfuFwC/A+4L\nOZeISCRU16a47P7nuPmh35BsaMnpew26Dt3dXzKzyuNe+0WfT9cAfxxuLBGR4WvR8vX8/PWddHX/\nfovPXQfbuPkHL7Pirsu59PSJOXnfMG4sugN4YqAvmtlCYCHAzJkzQ3g7EZHis2j5emo37KSzy+ke\n4JiubmfN1n3FWehm9i2gE1g20DHuvhRYClBVVaUdqUUkMmrqGvnXVZtpPtSe0fFmcNmsk3OWZ8iF\nbma3A/OBa9xdRS0iI0JNXSNPvNrIb3e10tY50Fi8f3+/4Pycjc5hiIVuZvOAe4FPuPuRcCOJiBSX\nmrpG7v/vTRxq7wp8btzg7CkVfPczuS1zyKDQzexx4Gpgkpk1Ad+hZ1VLGbDKzADWuPtXcphTRCSv\njo3Edx6krSvYJMTHKidy7/Wzc17gx8tklcvn+nn54RxkEREpqI9+d1XG8+H9OWvyGFbdc3V4gQLK\n6+NzRUSKzaLl63kutZtDbcGmUxIxcIfzTxvPM1+bm6N0wajQRWREWrR8PT+t30HQFR0xgxsvPJUH\nb7k4J7myoUIXkREh2dDCPSvqaWo5StzIeF48Rs9yw2IaiQ9EhS4ikVZdm2JZXQOtfaZUOjM4z4Cr\nzprEY3fOyVm2sKnQRSRyqmtTrFi7jfau7oznxkticPLYMhZcdBqLb5id44S5oUIXkUhYsGQ1G7Yf\noCwR40hH5jf8xGPGH14wrSjnxINSoYvIsFRT18g/PpviwNHO913YHKzMYwanjC3jUx+ZwmcvmZ73\nteK5pEIXkWEj2dDCl3/8KvuPdAQ6b3RJjIljSvnqJ8/i1jnRfUigCl1Eit6i5etZ+cauQM9OqSiP\nM768hL+MeIn3pUIXkaJUU9fI3/18I0cDPgBrakUZ37/t0khNpWRKhS4iRaW6NsVjaxo4EuBBWAbc\ndFFx3uyTTyp0ESm4mrpGHlm9lV0H3sv4iYYGnHnKWO648owRM6UyGBW6iORdTV0jj/z6bbbvPxJo\nSiVuMH5UCTdXzRi2a8VzSYUuInmzaPl6fvbaDroDPkAlHoMvz52lEh+ECl1EcirZ0MI/rEyRbGgh\nyGPFJ48t5RvXnaPplABU6CISumRDC//3JxvYvLs10Gh8bGmcyz80ia984swRuUolWyp0EQnFouXr\n+Z+Nu4ibBd6qrTwR40tXVGpKJUsqdBHJyoIlq6lvOhD4vFMqSll0raZUwqRCF5HAqmtTPLtxF00t\nRwhy38/o0jhfvOx0jcRzRIUuIhkb6mi88uTR/MvNF2lePMdU6CJyQr3PFj9wtCPjVSqjS2OMKy8Z\n1s8WH45U6CLyAb03/jTuO0x7gLWGY8viXDt7yoi/Bb9QVOgiAvQsNXx6XROrt+ylYf+RjM4ZlYjh\nBh+rPGlYbdUWVSp0kREu2dDCQy++xapNuzM+Rw/DKk6DFrqZPQLMB/a4+3np104CngAqgXeAm929\nJXcxRSRMyYYWvv3MBjbvas14XnxUIsZVZ0/mLt30U7QyGaE/CiwBHuvz2mLgeXevNrPF6c/vDT+e\niIRp0fL1/Pz1HXQFWGpYEjfuvPIMXdwcBgYtdHd/ycwqj3v5JuDq9Mc/Bl5AhS5SlGrqGrn/vzcF\nunszblCaiPEH507VtMowMtQ59CnuvhPA3Xea2SkDHWhmC4GFADNn6o4wkXzofSBW/bZ3A61SScSM\nK848WRc4h6mcXxR196XAUoCqqqqAD80UkSCqa1M89vI7g+5831fM4JwpFXz3M+drbnyYG2qh7zaz\naenR+TRgT5ihRCSYZEMLX/jhmkBFPnuqSjxqhlroPwNuB6rT//9paIlEJCM1dY088Nxm9h9qz/gR\ntTGDGy/UcsOoymTZ4uP0XACdZGZNwHfoKfIVZnYn0Aj8SS5Disj7BXmmigF3fVy7/YwEmaxy+dwA\nX7om5CwiMoBkQwv3rKinYd8RMr0QZcCF08fzzNfm5jKaFBHdKSpSxGrqGnlg1Wb2HmrP+JyLVOIj\nlgpdpAhd9y8vsKX5cMbHx4AbdSv+iKdCFykSyYYWfvDiWzyf2p3R7fgxg5PHaCNl+T0VukiBLViy\nmteaDgSaG9eDsaQ/KnSRAkg2tPDNJ+ozfkwtwOiSGF+8XBspy8BU6CJ51HtL/ivvZP5w0qkVZXz/\ntkt1A5AMSoUukmO9zxt/+c29GT0ga2xpnKnjy7lj7izNjUsgKnSRHEk2tFC9MsWrGY7GY8BC3QAk\nWVChi4QsyF2c0POo2i9fpSKX7KnQRUI0t/p5mt59b9DjyuLGmPIEN186Q0UuoVGhi4Skpq7xhGU+\nqiQGoE0jJGdU6CIhWfnGzgG/9hXNjUseqNBFQnL9edP41Za973tNzxyXfFKhi4Skd4nhyjd2cv15\n07TkUPJOhS4SolvnzFSRS8HECh1ARETCoUIXEYkIFbqISESo0EVEIkKFLiISESp0EZGIUKGLiESE\nCl1EJCKyKnQz+4aZbTSzN8zscTMrDyuYiIgEM+RCN7PTgL8Cqtz9PCAO3BJWMBERCSbbKZcEMMrM\nEsBoYEf2kUREZCiGXOjuvh34Z6AR2AkccPdfhBVMRESCyWbKZSJwE3AGcCowxsxu6+e4hWa21szW\nNjc3Dz2piIicUDZTLtcCb7t7s7t3AE8DVxx/kLsvdfcqd6+aPHlyFm8nIiInkk2hNwKXmdloMzPg\nGiAVTiwREQkqmzn0OuBJYB2wIf29loaUS0REAspqgwt3/w7wnZCyiIhIFnSnqIhIRKjQRUQiQoUu\nIhIRKnQRkYhQoYuIRIQKXUQkIlToIiIRoUIXEYkIFbqISESo0EVEIkKFLiISESp0EZGIUKGLiESE\nCl1EJCJU6CIiEaFCFxGJCBW6iEhEqNBFRCJChS4iEhEqdBGRiFChi4hEhApdRCQiVOgiIhGhQhcR\niYisCt3MJpjZk2b2WzNLmdnlYQUTEZFgElme/z3gWXf/YzMrBUaHkElERIZgyIVuZuOAjwNfAnD3\ndqA9nFgiw8+CJavZsP0AkyvK+P7nL+XS0ycWOpKMMNmM0GcBzcCPzOxCIAnc7e6HQ0kmUuSSDS18\ndVmS3Qfb8D6v7zrYxmf//Tc89RdXqNQlr7Ip9ARwCfB1d68zs+8Bi4Fv9z3IzBYCCwFmzpyZxduJ\nFN6CJat5rekAwPtKvD9rtu5ToUteZVPoTUCTu9elP3+SnkJ/H3dfCiwFqKqqGuzvgEjRWbBkNa9t\nP4AH/NN72ayTcxNIZABDLnR332Vm28zsHHffDFwDbAovmkhh1NQ18sBzm9l/qJ3uIQ5B7v/M+Rqd\nS95lu8rl68Cy9AqXrcCfZR9JpDCSDS18+5kNbNrZGug8A+IxGF2a4MNTK7j3+tkqcymIrArd3euB\nqpCyiORVdW2KFckmurq7KUnE2NfaPui8eF+nnzSaB/70IpW3FI1sR+giw0ayoYWHXnyL+sYW9h0e\n2nTK6NI45506TqNwKUoqdIm0ZEMLP3jxLX7z5l4OtXcN6XvEDOZ+aBKP3Tkn5HQi4VKhS+T0XtRs\nOdxOV3ewcw0YNypB3Iybq2aw+IbZOckokgsqdImE6toUK9Zuo/W9TjoCzqUkYjBl/CjOnTaOuz5x\npqZSZNhSocuwVVPXyP21mzjUFnwqJW4Qjxk3nD+NB2+5OAfpRPJPhS7DSk1dI//2yy3sbm2joyv4\nVc1JY0v55nXncOsc3bUs0aNCl6JXU9fII79+m617DhFwSvyY6RPKWb34mlBziRQbFboUpWRDC2u2\n7mPL7laeqd8R6NxEHM6aXMF3dbemjDAqdCkayYYWvvlEPY37jwS6wafX7KkqcRnZVOhSUMmGFp5a\n18T/pnaz62BboHPHlMYpK4lz86XTtbxQBBW6FEhNXSMPPreZPa2Z7Yli9Nzg0+3wocljWHXP1TnN\nJzIcqdAlb3ovbja3vseBo50ZnWPA5+bM5LOXTNdUisggVOiSU4uWr6d2w046uz3Qs1NK48ZFMybo\nmSkiAajQJXS9Jd4eYJ34uLI43cC1s6foRh+RIVKhSyiqa1M8U7+dw22dtAa4c7OiLM7n55yui5oi\nIVChy5AtWr6elW/soqOrO9B0yvhRCeaccbKemyISMhW6BPbFh+t4acveQOcYcNqEcv7yk2fptnuR\nHFGhS0aqa1PUvNLIwfcyW53SKxGD+RecqnlxkTxQocsJVdem+NFv3qGtM7OnqJx+0mjOmVrB5Ioy\n/khLDUXySoUuH9C7Xrxx3+GMV6rotnuRwlOhyzFBR+MGfLRyotaKixQJFfoIV12b4rGX3+FoR3fG\nD8TSvLhIcVKhj0A1dY088WojW3a3cqQjs9H4qESMq86erKWGIkVMhT6CBN2yrTRujC0v0dMMRYaJ\nrAvdzOLAWmC7u8/PPpKEKdnQQvXKFJt2HORwe2ZFXp6I8aUrKlXiIsNMGCP0u4EUMC6E7yUhWrBk\nNfVNBzI+fvyoBPfOm60bf0SGqawK3cymA58G/h74ZiiJJGuLlq/n56/tIJMVhzGDD0+t4O8WaMmh\nyHCX7Qj9QeBvgYoQskgIFi1fn9EenPGY8YcXTNNKFZEIGXKhm9l8YI+7J83s6hMctxBYCDBzpn6U\nz7UXftc84NdGl8RYcMl0bRYhElHZjNCvBG40sxuAcmCcmf2nu9/W9yB3XwosBaiqqhrK3r8SwNVn\nT/7ACN2Aq86axGN3zilMKBHJiyEXurvfB9wHkB6h//XxZS751zuF8lxqNzMmjtbt+CIjiNahR5Dm\nxUVGplAK3d1fAF4I43uJiMjQxAodQEREwqFCFxGJCBW6iEhEqNBFRCJChS4iEhEqdBGRiFChi4hE\nhApdRCQiVOgiIhGhQhcRiQgVuohIRKjQRUQiQoUuIhIRKnQRkYhQoYuIRIQKXUQkIlToIiIRoUIX\nEYkIFbqISESo0EVEIkKFLiISESp0EZGIUKGLiESECl1EJCKGXOhmNsPMfmlmKTPbaGZ3hxlMRESC\nSWRxbidwj7uvM7MKIGlmq9x9U0jZREQkgCEXurvvBHamP241sxRwGqBCL5BkQwtPrWtib2sbkyrK\n+Owl07n09ImFjiUieZLNCP0YM6sELgbqwvh+MrhkQwv3rKhnx7tHGT+qhP1HOujq9vcd8+TabTy+\n8HKVusgIkXWhm9lY4Clgkbsf7OfrC4GFADNnzsz27UasBUtWU990AICYQd/ubj7U3u85HV3Omq37\nVOgiI0RWhW5mJfSU+TJ3f7q/Y9x9KbAUoKqqyvs7Rj7oiw/X8as39+L9/Ip1Z/irWBI3Lpt1crjB\nRKRoDbnQzcyAh4GUuz8QXqSRp7o2xYrkNo62ddHe3U1Xd3bfb9q4Mj45e4rm0EVGmGxG6FcCXwA2\nmFl9+rX/4+612ceKtmRDCz948S1eeXsfB452ku2PLWNL47Sl/xX49PnTePCWi7MPKSLDTjarXFYD\nFmKWSKuuTfHwr9+moyv7Wad4DCrKEkwaW8Ydc2dx6xxdmxCRkFa5yAdV16ZYsXYbh9o66ejyrEbh\nMYO5H5rEY3fOCS2fiESPCj1E1bUpal5p5NB7nQx1Gjxu4A5mcKVKXEQCUKFnIYxpFANK48aFMyZw\n7/WzdRFTRIZMhR5QsqGFp9c1sXLDTvYf6RjS94gblCZi/MG5U3UBU0RCo0LPQO+qlF9taeZoR7DJ\nlBhgMWP6hFE88KcXaQQuIjmjQh9AsqGFf1iZ4rWmA7R1Bi/xseUJbv3YTBbfMDs3AUVEjqNCP051\nbYpldQ20tnUFPteAuz4+SyUuIgWhQidd4q800tbRRXuAC5wlcaO8JM7nNRIXkSIwYgu9d178hc17\nMi7xRKznOSoV5QnunTdbN/SISFEZcYVeXZviP1ZvDfS8lLJEjD+7olKjcBEpaiOq0KtrUzz00tZB\njytLGKNKE0waU6pb60Vk2BhRhf7sxl0n/HoiZvz53DM0EheRYWlEFfq8c6f2O0JPxIz5F+gphSIy\nvI2oQu8deT/86610dEFJDO6cq2WGIhIN5v1tiZMjVVVVvnbt2ry9n4hIFJhZ0t2rBjsulo8wIiKS\neyp0EZGIUKGLiESECl1EJCJU6CIiEaFCFxGJCBW6iEhEqNBFRCJChS4iEhFZFbqZzTOzzWb2ppkt\nDiuUiIgEN+RCN7M48H3geuAjwOfM7CNhBRMRkWCyeTjXx4A33X0rgJktB24CNoURrK/eLeLau7op\nL4nR3eUcbusiFjNK48bRjm4wGF+eoDwRZ+/hNnp2+HS60xtZ9O5nkYjB/AtO1ZMVRSRysin004Bt\nfT5vAuZkF+eDjt+Uoq3j91sNdXc7nd3ph4s5vHu0E+jk2Av96OyGZ+p3AKjURSRSsplDt35e+0CL\nmtlCM1trZmubm5sDv8lgm1IM1Qu/C55FRKSYZVPoTcCMPp9PB3Ycf5C7L3X3Knevmjx5cuA3mXfu\n1KEnPIGrzw6eRUSkmGUz5fIqcJaZnQFsB24Bbg0lVR+9m09oDl1E5MSGXOju3mlmXwP+B4gDj7j7\nxtCS9bH4htnaVUhEZBBZbUHn7rVAbUhZREQkC7pTVEQkIlToIiIRoUIXEYkIFbqISESo0EVEIsLc\n+79FPidvZtYMNAzx9EnA3hDjhEW5glGuYJQrmGLNBdllO93dB70bMq+Fng0zW+vuVYXOcTzlCka5\nglGuYIo1F+Qnm6ZcREQiQoUuIhIRw6nQlxY6wACUKxjlCka5ginWXJCHbMNmDl1ERE5sOI3QRUTk\nBIq+0ItxI2ozm2FmvzSzlJltNLO7C52pLzOLm9l6M/uvQmfpy8wmmNmTZvbb9K/d5YXOBGBm30j/\nPr5hZo+bWXmBcjxiZnvM7I0+r51kZqvMbEv6/xOLJNc/pX8fXzezn5jZhGLI1edrf21mbmaTiiWX\nmX093WUbzewfc/HeRV3oRbwRdSdwj7vPBi4DvlokuXrdDaQKHaIf3wOedfcPAxdSBBnN7DTgr4Aq\ndz+PnkdB31KgOI8C8457bTHwvLufBTyf/jzfHuWDuVYB57n7BcDvgPvyHYr+c2FmM4DrgMZ8B0p7\nlONymdkn6dlz+QJ3Pxf451y8cVEXOn02onb3dqB3I+qCcved7r4u/XErPcV0WmFT9TCz6cCngR8W\nOktfZjYO+DjwMIC7t7v7u4VNdUwCGGVmCWA0/ey8lQ/u/hKw/7iXbwJ+nP74x8CCvIai/1zu/gt3\n793Adw09O5YVPFfavwJ/y0AbC+fYALn+Aqh297b0MXty8d7FXuj9bURdFMXZy8wqgYuBusImOeZB\nev4wdw92YJ7NApqBH6Wng35oZmMKHcrdt9MzWmoEdgIH3P0XhU31PlPcfSf0DCSAUwqcpz93ACsL\nHQLAzG4Etrv7a4XOcpyzgavMrM7MXjSzj+biTYq90DPaiLpQzGws8BSwyN0PFkGe+cAed08WOks/\nEsAlwL+7+8XAYQozffA+6Tnpm4AzgFOBMWZ2W2FTDR9m9i16piCXFUGW0cC3gP9X6Cz9SAAT6Zmi\n/RtghZn1129ZKfZCz2gj6kIwsxJ6ynyZuz9d6DxpVwI3mtk79ExPfcrM/rOwkY5pAprcvfcnmSfp\nKfhCuxZ4292b3b0DeBq4osCZ+tptZtMA0v/PyY/qQ2FmtwPzgc97cax/PpOef5hfS/8dmA6sM7Pc\n7DQfTBPwtPd4hZ6foEO/YFvshX5sI2ozK6XnYtXPCpyJ9L+sDwMpd3+g0Hl6uft97j7d3Svp+bX6\nX3cvitGmu+8CtpnZOemXrgE2FTBSr0bgMjMbnf59vYYiuFjbx8+A29Mf3w78tIBZjjGzecC9wI3u\nfqTQeQDcfYO7n+Lulem/A03AJek/e4X2DPApADM7GyglBw8RK+pCT1906d2IOgWsyNVG1AFdCXyB\nnhFwffq/Gwodahj4OrDMzF4HLgLuL3Ae0j8xPAmsAzbQ83eiIHcbmtnjwMvAOWbWZGZ3AtXAdWa2\nhZ6VG9VFkmsJUAGsSv/5f6hIchXcALkeAWallzIuB27PxU81ulNURCQiinqELiIimVOhi4hEhApd\nRCQiVOgiIhGhQhcRiQgVuohIRKjQRUQiQoUuIhIR/x+CIdSy3re3YgAAAABJRU5ErkJggg==\n", "text/plain": ["<matplotlib.figure.Figure at 0x1c0e21a8400>"]}, "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": [], "source": ["nuage = [(x,y) for x,y in zip(X,Y)]\n", "nuage.sort()"]}, {"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", "(au carr\u00e9) 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 (Y_k - m)^2$ avec $m = (\\sum_{k=i}^j Y_k) / (j-i)$."]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [{"data": {"text/plain": ["(0.0, 15754.105018618644)"]}, "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((e[1]-m)**2 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 ``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": ["19898.600443365925"]}, "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(m-m1) + abs(m-m2)\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": ["552.6383487080093"]}, "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", "    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(m1 + m2 - m)\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": ["(553, 2184.8079894060775)"]}, "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", "    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 0x1c0e4c6f208>]"]}, "execution_count": 12, "metadata": {}, "output_type": "execute_result"}, {"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD8CAYAAABn919SAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAGNxJREFUeJzt3Xt0lfWd7/H3d++dC4FwERBQiBGr\nDvWuaUHF1lZdg5ZRejrjWGvrjJ5iZ9qOtM4Z8fT09I92XJmZ1rGz6IzlFGtdQ0SWWttOg1PsVB1a\nibIBRdilKLpDuF8icjPX7/kjOxgxIfvJfnb2zpPPay0WZOd5sj+Ly4dffs/veX7m7oiIyNAXK3QA\nEREJhwpdRCQiVOgiIhGhQhcRiQgVuohIRKjQRUQiQoUuIhIRKnQRkYhQoYuIRERiMN9swoQJXl1d\nPZhvKSIy5CWTyX3uPrG/4wa10Kurq1mzZs1gvqWIyJBnZulsjtOUi4hIRKjQRUQiQoUuIhIRKnQR\nkYhQoYuIRES/hW5mD5vZHjN7rcdr/2RmvzezV83sp2Y2Nr8xRUSkP9mM0B8B5pzw2krgfHe/EPgD\ncF/IuUREIqG2PsWs+5/l5od+RzLdnNf36ncduru/YGbVJ7z2qx4frgb+NNxYIiJD14Jl6/jFqzvp\n6Hxvi89d77Rw8w9fZPldl3PZGePy8r5h3Fh0B/B4X580s/nAfICqqqoQ3k5EpPgsWLaO+g07ae9w\nOvs4pqPTWb11f3EWupl9A2gHlvZ1jLsvBhYD1NTUaEdqEYmMuoZG/nnlZvYebs3qeDOYNX183vIM\nuNDN7HZgLnCNu6uoRWRYqGto5PGXG/n9rkO0tPc1Fu/d38+7IG+jcxhgoZvZHOBe4OPufjTcSCIi\nxaWuoZH7f7mJw60dgc+NG5wzqZLvfDq/ZQ5ZFLqZPQZcDUwwsybgW3StaikDVpoZwGp3/1Iec4qI\nDKrjI/Gd79DSEWwS4qPV47j3+hl5L/ATZbPK5bO9vLwkD1lERArqI99ZmfV8eG/OnjiSlfdcHV6g\ngAb18bkiIsVmwbJ1PJvazeGWYNMpiRi4wwWnj+Hpr8zOU7pgVOgiMiwtWLaOn63fQdAVHTGDGy86\njQdvuSQvuXKhQheRYSGZbuae5etpaj5G3Mh6XjxG13LDYhqJ90WFLiKRVlufYmlDmkM9plTaszjP\ngKvOnsCjd87MW7awqdBFJHJq61MsX7ON1o7OrOfGS2IwflQZ8y4+nYU3zMhzwvxQoYtIJMxbtIoN\n2w9SlohxtC37G37iMeNPLpxSlHPiQanQRWRIqmto5B+fSXHwWPv7Lmz2V+Yxg1NHlfHJD0/iM5dO\nHfS14vmkQheRISOZbuaLP3mZA0fbAp1XURJj3MhSvvyJs7l1ZnQfEqhCF5Git2DZOla8tivQs1Mq\ny+OMKS/hryNe4j2p0EWkKNU1NPLtX2zkWMAHYE2uLOMHt10WqamUbKnQRaSo1NaneHR1mqMBHoRl\nwE0XF+fNPoNJhS4iBVfX0MjDq7ay6+C7WT/R0ICzTh3FHVeeOWymVPqjQheRQVfX0MjDv32T7QeO\nBppSiRuMGVHCzTXThuxa8XxSoYvIoFmwbB0/f2UHnQEfoBKPwRdnT1eJ90OFLiJ5lUw38w8rUiTT\nzQR5rPjEUaV87bpzNZ0SgApdREKXTDfzf366gc27DwUajY8qjXP5hybwpY+fNSxXqeRKhS4ioViw\nbB3/uXEXcbPAW7WVJ2L8xRXVmlLJkQpdRHIyb9Eq1jcdDHzeqZWlLLhWUyphUqGLSGC19Sme2biL\npuajBLnvp6I0zhdmnaGReJ6o0EUkawMdjVePr+B7N1+sefE8U6GLyEl1P1v84LG2rFepVJTGGF1e\nMqSfLT4UqdBF5AO6b/xp3H+E1gBrDUeVxbl2xqRhfwt+oajQRQToWmr41NomVm3ZR/rA0azOGZGI\n4QYfrT5lSG3VFlUqdJFhLplu5qHn32Dlpt1Zn6OHYRWnfgvdzB4G5gJ73P38zGunAI8D1cBbwM3u\n3py/mCISpmS6mW8+vYHNuw5lPS8+IhHjqnMmcpdu+ila2YzQHwEWAY/2eG0h8Gt3rzWzhZmP7w0/\nnoiEacGydfzi1R10BFhqWBI37rzyTF3cHAL6LXR3f8HMqk94+Sbg6syvfwI8hwpdBFYs7Pr5+trC\n5uihrqGR+3+5KdDdm3GD0kSMPz5vsqZVhpCBzqFPcvedAO6+08xO7etAM5sPzAeoqtIdYRJxuzYU\nOgHw3gOx1m97O9AqlUTMuOKs8brAOUTl/aKouy8GFgPU1NQEfGimiARRW5/i0Rff6nfn+55iBudO\nquQ7n75Ac+ND3EALfbeZTcmMzqcAe8IMJSLBJNPNfP5HqwMV+YzJKvGoGWih/xy4HajN/Pyz0BKJ\nSFbqGhp54NnNHDjcmvUjamMGN16k5YZRlc2yxcfougA6wcyagG/RVeTLzexOoBH4s3yGFJH3C/JM\nFQPu+ph2+xkOslnl8tk+PnVNyFlEpA/JdDP3LF9Pev9Rsr0QZcBFU8fw9Fdm5zOaFBHdKSpSxOoa\nGnlg5Wb2HW7N+pyLVeLDlgpdpAhd973n2LL3SNbHx4AbdSv+sKdCFykSyXQzP3z+DX6d2p3V7fgx\ng/EjtZGyvEeFLlJg8xat4pWmg4HmxvVgLOmNCl2kAJLpZr7++PqsH1MLUFES4wuXayNl6ZsKXWQQ\ndd+S/9Jb2T+cdHJlGT+47TLdACT9UqGL5Fn388ZffH1fVg/IGlUaZ/KYcu6YPV1z4xKICl0kT5Lp\nZmpXpHg5y9F4DJivG4AkByp0kZC9tv0gcxf+Muvj4wZfvEpFLrlToYuEaF1jMy1Z7B5RFjdGlie4\n+bJpKnIJjQpdJCR1DY1MP0mZjyiJAWjTCMkbFbpISFa8tpMv9/G5L2luXAaBCl0kJNefPwXS739N\nzxyXwaRCFwnJrTOr2N0wkgNHWrn/UxdoyaEMOhW6SIgmVZYzqbKcGSpzKYBYoQOIiEg4VOgiIhGh\nQhcRiQgVuohIRKjQRUQiQoUuIhIRKnQRkYhQoYuIREROhW5mXzOzjWb2mpk9ZmblYQUTEZFgBlzo\nZnY68DdAjbufD8SBW8IKJiIiweQ65ZIARphZAqgAduQeSUREBmLAhe7u24HvAo3ATuCgu/8qrGAi\nIhJMLlMu44CbgDOB04CRZnZbL8fNN7M1ZrZm7969A08qIiInlcuUy7XAm+6+193bgKeAK048yN0X\nu3uNu9dMnDgxh7cTEZGTyaXQG4FZZlZhZgZcA6TCiSUiIkHlMofeADwBrAU2ZL7W4pByiYhIQDlt\ncOHu3wK+FVIWERHJge4UFRGJCBW6iEhEqNBFRCJChS4iEhEqdBGRiFChi4hEhApdRCQiVOgiIhGh\nQhcRiQgVuohIRKjQRUQiQoUuIhIRKnQRkYhQoYuIRIQKXUQkIlToIiIRoUIXEYkIFbqISESo0EVE\nIkKFLiISESp0EZGIUKGLiESECl1EJCJU6CIiEZFToZvZWDN7wsx+b2YpM7s8rGAiIhJMIsfzvw88\n4+5/amalQEUImUREZAAGPEI3s9HAx4AlAO7e6u5vhxVMZKiZt2gVq9/cz9rGZpLp5kLHkWEolxH6\ndGAv8GMzuwhIAne7+5FQkokUuWS6mS8vTbL7nRa8+8VSaO3o5JZ/+x1P/tUVXHbGuEJGlGEml0JP\nAJcCX3X3BjP7PrAQ+GbPg8xsPjAfoKqqKoe3Eym8eYtW8UrTQYD3SrwPq7fuV6HLoMql0JuAJndv\nyHz8BF2F/j7uvhhYDFBTU9PfvwGRojNv0Spe2X4QD/i3d9b08fkJJNKHARe6u+8ys21mdq67bwau\nATaFF02kMOoaGnng2c0cONxK5wCHIPd/+gKNzmXQ5brK5avA0swKl63AX+YeSaQwkulmvvn0Bjbt\nPBToPAPiMagoTVBZkqBqfAWzZmp6UQZfToXu7uuBmpCyiAyq2voUy5NNdHR2UpKIsf9Qa7/z4j2d\ncUoFD/z5xe8fif/4X0LPKZKtXEfoIkNGMt3MQ8+/wfrGZvYfGdh0SkVpnPNPG82918/QlIoUHRW6\nRFoy3cwPn3+D372+j8OtHQP6GjGD2R+awKN3zgw5nUi4VOgSOd0XNZuPtNLRGexcA0aPSBA34+aa\naSy8YUZeMorkgwpdIqG2PsXyNds49G47bQHnUhIxmDRmBOdNGc1dHz9LUykyZKnQZciqa2jk/vpN\nHG4JPpUSN4jHjBsumMKDt1ySh3Qig0+FLkNKXUMj//qbLew+1EJbR/CrmhNGlfL1687lVi0rlAhS\noUvRq2to5OHfvsnWPYcJOCV+3NSx5axaeE2ouUSKjQpdilIy3czqrfvZsvsQT6/fEejcRBzOnljJ\nd3S3pgwzKnQpGsl0M19/fD2NB44GusGn24zJKnEZ3lToUlDJdDNPrm3iv1K72fVOS6BzR5bGKSuJ\nc/NlU7W8UAQVuhRIXUMjDz67mT2HWrM63ui6wafT4UMTR7Lynqvzmk9kKFKhy6Dpvri599C7HDzW\nntU5Bnx2ZhWfuXSqplJE+qFCl7xasGwd9Rt20t7pgZ6dUho3Lp42Vs9MEQlAhS6h6y7x1gDrxEeX\nxekErp0xSTf6iAyQCl1CUVuf4un12znS0s6hAHduVpbF+dzMM3RRUyQEKnQZsAXL1rHitV20dXQG\nmk4ZMyLBzDPH67kpIiFToUtgX1jSwAtb9gU6x4DTx5bz1584W7fdi+SJCl2yUlufou6lRt55N7vV\nKd0SMZh74WmaFxcZBCp0Oana+hQ//t1btLRn9xSVM06p4NzJlUysLON/aKmhyKBSocsHdK8Xb9x/\nJOuVKrrtXqTwVOhyXNDRuAEfqR6nteIiRUKFPszV1qd49MW3ONbWmfUDsTQvLlKcVOjDUF1DI4+/\n3MiW3Yc42pbdaHxEIsZV50zUUkORIqZCH0aCbtlWGjdGlZfoaYYiQ0TOhW5mcWANsN3d5+YeScKU\nTDdTuyLFph3vcKQ1uyIvT8T4iyuqVeIiQ0wYI/S7gRQwOoSvJSGat2gV65sOZn38mBEJ7p0zQzf+\niAxRORW6mU0FPgX8PfD1UBJJzhYsW8cvXtlBNisOYwZ/NLmSb8/TkkORoS7XEfqDwN8BlSFkkRAs\nWLYuqz044zHjTy6copUqIhEy4EI3s7nAHndPmtnVJzluPjAfoKpK38rn23N/2Nvn5ypKYsy7dKo2\nixCJqFxG6FcCN5rZDUA5MNrM/t3db+t5kLsvBhYD1NTUDGTvXwng6nMmfmCEbsBVZ0/g0TtnFiaU\niAyKARe6u98H3AeQGaH/7YllLoOvewrl2dRupo2r0O34IsOI1qFHkObFRYanUArd3Z8Dngvja4mI\nyMDECh1ARETCoUIXEYkIFbqISESo0EVEIkKFLiISESp0EZGIUKGLiESECl1EJCJU6CIiEaFCFxGJ\nCBW6iEhEqNBFRCJChS4iEhEqdBGRiFChi4hEhApdRCQiVOgiIhGhQhcRiQgVuohIRKjQRUQiQoUu\nIhIRKnQRkYhQoYuIRIQKXUQkIgZc6GY2zcx+Y2YpM9toZneHGUxERIJJ5HBuO3CPu681s0ogaWYr\n3X1TSNlERCSAARe6u+8EdmZ+fcjMUsDpgAq9QJLpZp5c28S+Qy1MqCzjM5dO5bIzxhU6logMklxG\n6MeZWTVwCdAQxteT/iXTzdyzfD073j7GmBElHDjaRkenv++YJ9Zs47H5l6vURYaJnAvdzEYBTwIL\n3P2dXj4/H5gPUFVVlevbDVvzFq1ifdNBAGIGPbt77+HWXs9p63BWb92vQhcZJnIqdDMroavMl7r7\nU70d4+6LgcUANTU13tsx8kFfWNLAf7++D+/ld6wzy9/Fkrgxa/r4cIOJSNEacKGbmQFLgJS7PxBe\npOGntj7F8uQ2jrV00NrZSUdnbl9vyugyPjFjkubQRYaZXEboVwKfBzaY2frMa//b3etzjxVtyXQz\nP3z+DV56cz8Hj7WT67cto0rjtGT+F/jUBVN48JZLcg8pIkNOLqtcVgEWYpZIq61PseS3b9LWkfus\nUzwGlWUJJowq447Z07l1pq5NiEhIq1zkg2rrUyxfs43DLe20dXhOo/CYwewPTeDRO2eGlk9EokeF\nHqLa+hR1LzVy+N12BjoNHjdwBzO4UiUuIgGo0HMQxjSKAaVx46JpY7n3+hm6iCkiA6ZCDyiZbuap\ntU2s2LCTA0fbBvQ14galiRh/fN5kXcAUkdCo0LPQvSrlv7fs5VhbsMmUGGAxY+rYETzw5xdrBC4i\neaNC70My3cw/rEjxStNBWtqDl/io8gS3frSKhTfMyE9AEZETqNBPUFufYmlDmkMtHYHPNeCuj01X\niYtIQajQyZT4S420tHXQGuACZ0ncKC+J8zmNxEWkCAzbQu+eF39u856sSzwR63qOSmV5gnvnzNAN\nPSJSVIZdodfWp/h/q7YGel5KWSLGX15RrVG4iBS1YVXotfUpHnpha7/HlSWMEaUJJows1a31IjJk\nDKtCf2bjrpN+PhEz/ufsMzUSF5EhaVgV+pzzJvc6Qk/EjLkX6imFIjK0DatC7x55L/ntVto6oCQG\nd87WMkMRiYZhVejQVeoqcBGJolihA4iISDhU6CIiEaFCFxGJCBW6iEhEqNBFRCJChS4iEhEqdBGR\niFChi4hEhApdRCQicip0M5tjZpvN7HUzWxhWKBERCW7AhW5mceAHwPXAh4HPmtmHwwomIiLB5PIs\nl48Cr7v7VgAzWwbcBGwKI1hP3VvEtXZ0Ul4So7PDOdLSQSxmlMaNY22dYDCmPEF5Is6+Iy107fDp\ndGY2sujezyIRg7kXnqYnK4pI5ORS6KcD23p83ATMzC3OB524KUVL23tbDXV2Ou2dme3jHN4+1g60\nc/yFXrR3wtPrdwCo1EUkUnIpdOvltQ+0qJnNB+YDVFUF3/mnv00pBuq5P+zNy9eVYW7yBYVOIMNY\nLhdFm4BpPT6eCuw48SB3X+zuNe5eM3HixMBvMue8yQNPeBJXnxM8i0i/rq/t+iFSALmM0F8Gzjaz\nM4HtwC3AraGk6qH72eWaQxcRObkBF7q7t5vZV4D/BOLAw+6+MbRkPWhTChGR/uW0Y5G71wP1IWUR\nEZEc6E5REZGIUKGLiESECl1EJCJU6CIiEaFCFxGJCHPv/Rb5vLyZ2V4gPcDTJwD7QowTFuUKRrmC\nUa5gijUX5JbtDHfv927IQS30XJjZGnevKXSOEylXMMoVjHIFU6y5YHCyacpFRCQiVOgiIhExlAp9\ncaED9EG5glGuYJQrmGLNBYOQbcjMoYuIyMkNpRG6iIicRNEXejFuRG1m08zsN2aWMrONZnZ3oTP1\nZGZxM1tnZv9R6Cw9mdlYM3vCzH6f+b27vNCZAMzsa5k/x9fM7DEzKy9QjofNbI+ZvdbjtVPMbKWZ\nbcn8PK5Icv1T5s/xVTP7qZmNLYZcPT73t2bmZjahWHKZ2VczXbbRzP4xH+9d1IVexBtRtwP3uPsM\nYBbw5SLJ1e1uIFXoEL34PvCMu/8RcBFFkNHMTgf+Bqhx9/PpehT0LQWK8wgw54TXFgK/dvezgV9n\nPh5sj/DBXCuB8939QuAPwH2DHYrec2Fm04DrgMbBDpTxCCfkMrNP0LXn8oXufh7w3Xy8cVEXOj02\nonb3VqB7I+qCcved7r428+tDdBXT6YVN1cXMpgKfAn5U6Cw9mdlo4GPAEgB3b3X3twub6rgEMMLM\nEkAFvey8NRjc/QXgwAkv3wT8JPPrnwDzBjUUvedy91+5e/cGvqvp2rGs4Lky/hn4O/raWDjP+sj1\nV0Ctu7dkjtmTj/cu9kLvbSPqoijObmZWDVwCNBQ2yXEP0vWXubO/AwfZdGAv8OPMdNCPzGxkoUO5\n+3a6RkuNwE7goLv/qrCp3meSu++EroEEcGqB8/TmDmBFoUMAmNmNwHZ3f6XQWU5wDnCVmTWY2fNm\n9pF8vEmxF3pWG1EXipmNAp4EFrj7O0WQZy6wx92Thc7SiwRwKfBv7n4JcITCTB+8T2ZO+ibgTOA0\nYKSZ3VbYVEOHmX2DrinIpUWQpQL4BvB/C52lFwlgHF1TtP8LWG5mvfVbToq90LPaiLoQzKyErjJf\n6u5PFTpPxpXAjWb2Fl3TU580s38vbKTjmoAmd+/+TuYJugq+0K4F3nT3ve7eBjwFXFHgTD3tNrMp\nAJmf8/Kt+kCY2e3AXOBzXhzrn8+i6z/mVzL/BqYCa80sPzvNB9MEPOVdXqLrO+jQL9gWe6Ef34ja\nzErpulj18wJnIvM/6xIg5e4PFDpPN3e/z92nuns1Xb9X/+XuRTHadPddwDYzOzfz0jXApgJG6tYI\nzDKzisyf6zUUwcXaHn4O3J759e3AzwqY5TgzmwPcC9zo7kcLnQfA3Te4+6nuXp35N9AEXJr5u1do\nTwOfBDCzc4BS8vAQsaIu9MxFl+6NqFPA8nxtRB3QlcDn6RoBr8/8uKHQoYaArwJLzexV4GLg/gLn\nIfMdwxPAWmADXf8mCnK3oZk9BrwInGtmTWZ2J1ALXGdmW+hauVFbJLkWAZXAyszf/4eKJFfB9ZHr\nYWB6ZinjMuD2fHxXoztFRUQioqhH6CIikj0VuohIRKjQRUQiQoUuIhIRKnQRkYhQoYuIRIQKXUQk\nIlToIiIR8f8B93XWHGSZbEEAAAAASUVORK5CYII=\n", "text/plain": ["<matplotlib.figure.Figure at 0x1c0e4c68f98>"]}, "metadata": {}, "output_type": "display_data"}], "source": ["import matplotlib.pyplot as plt\n", "x = nuage[553][0]\n", "plt.plot(X,Y,'.')\n", "plt.plot([x,x], [0,10])"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Q7 - optimisation encore\n", "\n", "Recommencer sur les deux intervalles trouv\u00e9s"]}, {"cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [{"data": {"text/plain": ["((253, 787.5154656398129), (789, 156.7106930739271))"]}, "execution_count": 13, "metadata": {}, "output_type": "execute_result"}], "source": ["optimise(nuage, 0, 570, fct), optimise(nuage, 570, len(nuage), fct)"]}, {"cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [{"data": {"text/plain": ["[<matplotlib.lines.Line2D at 0x1c0e4c90940>]"]}, "execution_count": 14, "metadata": {}, "output_type": "execute_result"}, {"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD8CAYAAABn919SAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAGQNJREFUeJzt3Xt0VeWd//H395yTEC4RUFBQiBGv\n1Lum4gWtrbpGLaN0OsNQa7XVKXam7UjrzIC//vrrH9Nxxbk4di06Y5lqrWuIyFJr25ngFJ2qpZUo\nB6IIR4qiieF+idzN9fv7Iyc0YELOztnnkp3Pay0Wycne53wWkA9PnvPs/Zi7IyIig1+s0AFERCQc\nKnQRkYhQoYuIRIQKXUQkIlToIiIRoUIXEYkIFbqISESo0EVEIkKFLiISEYl8vti4ceO8srIyny8p\nIjLoJZPJne4+vr/j8lrolZWVrFy5Mp8vKSIy6JlZQybHacpFRCQiVOgiIhGhQhcRiQgVuohIRKjQ\nRUQiot9CN7PHzGy7mb3V47F/MrO3zexNM/uZmY3JbUwREelPJiP0x4Ebj3psGXCeu18A/B64P+Rc\nIiKRUF2b4vIHXmDWI78j2dCc09fqdx26u79iZpVHPfarHp+uAP403FgiIoPX3MWr+eWbW+jo/MMW\nn1v3tjDrR6+y5J4ruPTUsTl53TAuLLoLeKqvL5rZHGAOQEVFRQgvJyJSfOYuXk3tmi20dzidfRzT\n0ems2LirOAvdzL4DtAOL+jrG3RcCCwGqqqq0I7WIREZNXSP/umw9O/a3ZnS8GVw+5YSc5RlwoZvZ\nncAM4Dp3V1GLyJBQU9fIU6838vbWfbS09zUW790/zDw/Z6NzGGChm9mNwDzgU+5+MNxIIiLFpaau\nkQf+ex37WzsCnxs3OOukcr7/udyWOWRQ6Gb2JHAtMM7MmoDv0bWqZRiwzMwAVrj713KYU0Qkrw6P\nxLfspaUj2CTEZZVjmXfT1JwX+NEyWeXyhV4efjQHWURECuqT31+W8Xx4b84cP5Jl910bXqCA8nr7\nXBGRYjN38WpeSG1jf0uw6ZREDNzh/FNG89w3pucoXTAqdBEZkuYuXs3P6zcTdEVHzOCWC0/m4dkX\n5yRXNlToIjIkJBuauW9JPU3Nh4gbGc+Lx+hablhMI/G+qNBFJNKqa1MsqmtgX48plfYMzjPg6jPH\n8cTd03KWLWwqdBGJnOraFEtWfkBrR2fGc+MlMThh1DBmXnQK82+emuOEuaFCF5FImLlgOWs27WFY\nIsbBtswv+InHjD++YGJRzokHpUIXkUGppq6Rf3w+xZ5D7Ue8sdlfmccMThw1jM984iQ+f8mkvK8V\nzyUVuogMGsmGZr7609fZfbAt0HkjSmKMHVnK1z99JrdNi+5NAlXoIlL05i5ezdK3tga6d0p5WZzR\nZSX8VcRLvCcVuogUpZq6Rv7+l2s5FPAGWBPKh/HD2y+N1FRKplToIlJUqmtTPLGigYMBboRlwK0X\nFefFPvmkQheRgqupa+Sx5RvZuuejjO9oaMDpJ47irqtOGzJTKv1RoYtI3tXUNfLYb99j0+6DgaZU\n4gajh5cwq2ryoF0rnksqdBHJm7mLV/OLNzbTGfAGKvEYfHX6FJV4P1ToIpJTyYZmHlyaItnQTJDb\nio8fVcq3bjhb0ykBqNBFJHTJhmb+78/WsH7bvkCj8VGlca44Yxxf+9TpQ3KVSrZU6CISirmLV/M/\na7cSNwu8VVtZIsaXr6zUlEqWVOgikpWZC5ZT37Qn8Hknlpcy93pNqYRJhS4igVXXpnh+7Vaamg8S\n5LqfEaVx7rj8VI3Ec0SFLiIZG+hovPKEEfzLrIs0L55jKnQROabue4vvOdSW8SqVEaUxjisrGdT3\nFh+MVOgi8jHdF/407jpAa4C1hqOGxbl+6klD/hL8QlGhiwjQtdTw2VVNLN+wk4bdBzM6Z3gihhtc\nVnn8oNqqLapU6CJDXLKhmUdefpdl67ZlfI5uhlWc+i10M3sMmAFsd/fz0o8dDzwFVALvA7PcvTl3\nMUUkTMmGZr773BrWb92X8bz48ESMq88azz266KdoZTJCfxxYADzR47H5wIvuXm1m89Ofzws/noiE\nae7i1fzyzc10BFhqWBI37r7qNL25OQj0W+ju/oqZVR718K3AtemPfwq8hAq9eCyd3/X7TdWFzSFF\noaaukQf+e12gqzfjBqWJGH907oRQplUefO1BAOZdpprIpYHOoZ/k7lsA3H2LmZ3Y14FmNgeYA1BR\noSvC8mLrmkInkALrviFW/QcfBlqlkogZV55+QuhvcL69++1Qn096l/M3Rd19IbAQoKqqKuBNM0Uk\niOraFE+8+n6/O9/3FDM4+6Ryvv+58zU3PsgNtNC3mdnE9Oh8IrA9zFAiEkyyoZkv/XhFoCKfOkEl\nHjUDLfRfAHcC1enffx5aIhHJSE1dIw+9sJ7d+1szvkVtzOCWC7XcMKoyWbb4JF1vgI4zsybge3QV\n+RIzuxtoBP4slyFF5EhB7qliwD3XaLefoSCTVS5f6ONL14WcRUT6kGxo5r4l9TTsOkimb0QZcOGk\n0Tz3jem5jCZFRFeKihSxmrpGHlq2np37WzM+5yKV+JClQhcpQjf8y0ts2HEg4+NjwC26FH/IU6GL\nFIlkQzM/evldXkxty+hy/JjBCSO1kbL8gQpdpMBmLljOG017As2N68ZY0hsVukgBJBua+fZT9Rnf\nphZgREmMO67QRsrSNxW6SB51X5L/2vuZ35x0Qvkwfnj7pboASPqlQhfJse77jb/6zs6MbpA1qjTO\nhNFl3DV9iubGJRAVukiOJBuaqV6a4vUMR+MxYI4uAJIsqNBFQhbkKk7oulXtV69WkUv2VOgiIZpe\n/SJNH37U73HD4sbIsgSzLp2sIpfQqNBFQlJT13jMMh9eEgMIbdMIkaOp0EVCsvStLX1+7WuaG5c8\nUKGLhOSm8ybymw07j3hM9xyXfFKhi4Ske4nh0re2cNN5E7XkUPJOhS4SotumVajIpWBihQ4gIiLh\nUKGLiESECl1EJCJU6CIiEaFCFxGJCBW6iEhEqNBFRCJChS4iEhFZFbqZfcvM1prZW2b2pJmVhRVM\nRESCGXChm9kpwF8DVe5+HhAHZocVTEREgsl2yiUBDDezBDAC2Jx9JBERGYgBF7q7bwL+GWgEtgB7\n3P1XYQUTEZFgsplyGQvcCpwGnAyMNLPbezlujpmtNLOVO3bsGHhSERE5pmymXK4H3nP3He7eBjwL\nXHn0Qe6+0N2r3L1q/PjxWbyciIgcSzaF3ghcbmYjzMyA64BUOLFERCSobObQ64CngVXAmvRzLQwp\nl4iIBJTVBhfu/j3geyFlERGRLOhKURGRiFChi4hEhApdRCQiVOgiIhGhQhcRiQgVuohIRKjQRUQi\nQoUuIhIRKnQRkYhQoYuIRIQKXUQkIlToIiIRoUIXEYkIFbqISESo0EVEIkKFLiISESp0EZGIUKGL\niESECl1EJCJU6CIiEaFCFxGJCBW6iEhEqNBFRCJChS4iEhFZFbqZjTGzp83sbTNLmdkVYQUTEZFg\nElme/wPgeXf/UzMrBUaEkElERAZgwIVuZscB1wBfBnD3VqA1nFgig8/MBctZs2kP48uH8cMvXsql\np44tdCQZYrIZoU8BdgA/MbMLgSRwr7sfCCWZSJFLNjTz9UVJtu1twXs8vnVvC5//99/xzF9eqVKX\nvMqm0BPAJcA33b3OzH4AzAe+2/MgM5sDzAGoqKjI4uVECm/mguW80bQH4IgS782KjbtU6JJX2RR6\nE9Dk7nXpz5+mq9CP4O4LgYUAVVVV/X0PiBSdmQuW88amPXjAf72XTzkhN4FE+jDgQnf3rWb2gZmd\n7e7rgeuAdeFFEymMmrpGHnphPbv3t9I5wCHIA587X6NzybtsV7l8E1iUXuGyEfhK9pFECiPZ0Mx3\nn1vDui37Ap1nQDwGI0oTnDOhnHk3TVWZS0FkVejuXg9UhZRFJK+qa1MsSTbR0dlJSSLGrn2t/c6L\n93Tq8SN46M8vUnlL0ch2hC4yaCQbmnnk5Xepb2xm14GBTaeMKI1z3snHaRQuRUmFLpGWbGjmRy+/\ny+/e2cn+1o4BPUfMYPoZ43ji7mkhpxMJlwpdIqf7Tc3mA610dAY714DjhieImzGrajLzb56ak4wi\nuaBCl0iork2xZOUH7PuonbaAcymJGJw0ejjnTjyOez51uqZSZNBSocugVVPXyAO169jfEnwqJW4Q\njxk3nz+Rh2dfnIN0IvmnQpdBpaaukX/79Qa27WuhrSP4u5rjRpXy7RvO5rZpumpZokeFLkWvpq6R\nx377Hhu37yfglPhhk8aUsXz+daHmEik2KnQpSsmGZlZs3MWGbft4rn5zoHMTcThzfDnf19WaMsSo\n0KVoJBua+fZT9TTuPhjoAp9uUyeoxGVoU6FLQSUbmnlmVRP/m9rG1r0tgc4dWRpnWEmcWZdO0vJC\nEVToUiA1dY08/MJ6tu/LbE8Uo+sCn06HM8aPZNl91+Y0n8hgpEKXvOl+c3PHvo/Yc6g9o3MM+MK0\nCj5/ySRNpYj0Q4UuOTV38Wpq12yhvdMD3TulNG5cNHmM7pkiEoAKXULXXeKtAdaJHzcsTidw/dST\ndKGPyACp0CUU1bUpnqvfxIGWdvYFuHKzfFicL047VW9qioRAhS4DNnfxapa+tZW2js5A0ymjhyeY\ndtoJum+KSMhU6BLYHY/W8cqGnYHOMeCUMWX81afP1GX3IjmiQpeMVNemqHmtkb0fZbY6pVsiBjMu\nOFnz4iJ5oEKXY6quTfGT371PS3tmd1E59fgRnD2hnPHlw/gTLTUUySsVunxM93rxxl0HMl6posvu\nRQpPhS6HBR2NG/DJyrFaKy5SJFToQ1x1bYonXn2fQ22dGd8QS/PiIsVJhT4E1dQ18tTrjWzYto+D\nbZmNxocnYlx91ngtNRQpYir0ISTolm2lcWNUWYnuZigySGRd6GYWB1YCm9x9RvaRJEzJhmaql6ZY\nt3kvB1ozK/KyRIwvX1mpEhcZZMIYod8LpIDjQnguCdHMBcupb9qT8fGjhyeYd+NUXfgjMkhlVehm\nNgn4LPAPwLdDSSRZe2f7PnYeaKW+tf8yjxmcM6Gcv5+pJYcig122I/SHgb8DykPIIiGYu3g1sw/0\nv2lEPGb88QUTtVJFJEIGXOhmNgPY7u5JM7v2GMfNAeYAVFToR/lce+n3O5jdx9dGlMSYeckkbRYh\nElHZjNCvAm4xs5uBMuA4M/tPd7+950HuvhBYCFBVVTWQvX8lgGvPGg/rjnzMgKvPHMcTd08rSCYR\nyY8BF7q73w/cD5Aeof/N0WUu+ffw7It558FSmg+26XJ8kSFG69Aj6IwTu97SWPqVawqcRETyKZRC\nd/eXgJfCeC4RERmYWKEDiIhIOFToIiIRoUIXEYkIFbqISESo0EVEIkKFLiISESp0EZGIUKGLiESE\nCl1EJCJU6CIiEaFCFxGJCBW6iEhEqNBFRCJChS4iEhEqdBGRiFChi4hEhApdRCQiVOgiIhGhQhcR\niQgVuohIRKjQRUQiQoUuIhIRKnQRkYhQoYuIRMSAC93MJpvZr80sZWZrzezeMIOJiEgwiSzObQfu\nc/dVZlYOJM1smbuvCymbiIgEMOBCd/ctwJb0x/vMLAWcAqjQCyTZ0Mwzq5q4c9s+SuJGc0Mzl546\nttCxRCRPshmhH2ZmlcDFQF0Yzyf9SzY0c9+SejZ/eIjRw0vYfbCNjk4H4JbSVgDuWPgqT865QqUu\nMkRkXehmNgp4Bpjr7nt7+focYA5ARUVFti83ZM1csJz6pj0AxAzS3Q3Ajv2tvZ7T1uGs2LhLhS4y\nRGRV6GZWQleZL3L3Z3s7xt0XAgsBqqqqvLdj5OPueLSO37yzE+/lT6wzwz/Fkrhx+ZQTwg0mIkVr\nwIVuZgY8CqTc/aHwIg091bUpliQ/4FBLB62dnXR0Zvd8pfEYY0aU8OQsTbeIDCXZjNCvAr4ErDGz\n+vRj/8fda7OPFW3JhmZ+9PK7vPbeLvYcaifbH1tGlcZpSf8v8NnzJ3LJoXSJq8xFhpRsVrksByzE\nLJFWXZvi0d++R1tH9rNO8RiUD0swbtQw7po+hdumHfXexE+yfgkRGYRCWeUiH1ddm2LJyg/Y39JO\nW4dnNQqPGUw/YxxP3D0ttHwiEj0q9BBV16aoea2R/R+1M9Bp8LiBO5jBVSpxEQlAhZ6FMKZRDCiN\nGxdOHsO8m6bqTUwRGTAVekDJhmaeXdXE0jVb2H2wbUDPETcoTcT4o3Mn8PDsi0NOKCJDlQo9A92r\nUn6zYQeH2oJNpsQAixmTxgznoT+/SCNwEckZFXofkg3NPLg0xRtNe2hpD17io8oS3HZZBfNvnpqb\ngCIiR1GhH6W6NsWiugb2tXQEPteAe66ZohIXkYJQoZMu8dcaaWnroDXAG5wlcaOsJM4XNRIXkSIw\nZAu9e178pfXbMy7xRKzrPirlZQnm3Tj14xf0iIgU0JAr9OraFP+xfGOg+6UMS8T4ypWVGoWLSFEb\nUoVeXZvikVc29nvcsIQxvDTBuJGlvV9aLyJShIZUoT+/dusxv56IGX8x/TSNxEVkUBpShX7juRN6\nHaEnYsaMCybqIh8RGdSGVKF3j7wf/e1G2jqgJAZ3T9cyQxGJhiFV6NBV6ipwEYmiWKEDiIhIOFTo\nIiIRoUIXEYkIFbqISESo0EVEIkKFLiISESp0EZGIUKGLiESECl1EJCKyKnQzu9HM1pvZO2Y2P6xQ\nIiIS3IAL3cziwA+Bm4BPAF8ws0+EFUxERILJ5l4ulwHvuPtGADNbDNwKrAsjWE/dW8S1dnRSVhKj\ns8M50NJBLGaUxo1DbZ1gMLosQVkizs4DLXTt8Ol0pjey6N7PIhGDGRecrDsrikjkZFPopwAf9Pi8\nCZiWXZyPO3pTipa2P2w11NnptHemt49z+PBQO9DO4Qd60d4Jz9VvBlCpi0ikZFPo1stjH2tRM5sD\nzAGoqAi+809/m1IM1Eu/35GT5y0KE84vdAKRI5xz/DmFjjAkZFPoTcDkHp9PAjYffZC7LwQWAlRV\nVWW2G3MPfW1Kka1rzxof+nMWjZuqC51A5AjzLptX6AhDQjaF/jpwppmdBmwCZgO3hZKqh+57l2sO\nXUTk2AZc6O7ebmbfAP4HiAOPufva0JL1oE0pRET6l9WORe5eC9SGlEVERLKgK0VFRCJChS4iEhEq\ndBGRiFChi4hEhApdRCQizD3wtT4DfzGzHUDDAE8fB+wMMU5YlCsY5QpGuYIp1lyQXbZT3b3fqyHz\nWujZMLOV7l5V6BxHU65glCsY5QqmWHNBfrJpykVEJCJU6CIiETGYCn1hoQP0QbmCUa5glCuYYs0F\necg2aObQRUTk2AbTCF1ERI6h6Au9GDeiNrPJZvZrM0uZ2Vozu7fQmXoys7iZrTaz/yp0lp7MbIyZ\nPW1mb6f/7K4odCYAM/tW+u/xLTN70szKCpTjMTPbbmZv9XjseDNbZmYb0r+PLZJc/5T+e3zTzH5m\nZmOKIVePr/2NmbmZjSuWXGb2zXSXrTWzf8zFaxd1oRfxRtTtwH3uPhW4HPh6keTqdi+QKnSIXvwA\neN7dzwEupAgymtkpwF8DVe5+Hl23gp5doDiPAzce9dh84EV3PxN4Mf15vj3Ox3MtA85z9wuA3wP3\n5zsUvefCzCYDNwCN+Q6U9jhH5TKzT9O15/IF7n4u8M+5eOGiLnR6bETt7q1A90bUBeXuW9x9Vfrj\nfXQV0ymFTdXFzCYBnwV+XOgsPZnZccA1wKMA7t7q7h8WNtVhCWC4mSWAEfSy81Y+uPsrwO6jHr4V\n+Gn6458CM/Mait5zufuv3L17A98VdO1YVvBcaf8K/B19bSycY33k+kug2t1b0sdsz8VrF3uh97YR\ndVEUZzczqwQuBuoKm+Swh+n6x9zZ34F5NgXYAfwkPR30YzMbWehQ7r6JrtFSI7AF2OPuvypsqiOc\n5O5boGsgAZxY4Dy9uQtYWugQAGZ2C7DJ3d8odJajnAVcbWZ1ZvaymX0yFy9S7IWe0UbUhWJmo4Bn\ngLnuvrcI8swAtrt7stBZepEALgH+3d0vBg5QmOmDI6TnpG8FTgNOBkaa2e2FTTV4mNl36JqCXFQE\nWUYA3wH+X6Gz9CIBjKVrivZvgSVm1lu/ZaXYCz2jjagLwcxK6CrzRe7+bKHzpF0F3GJm79M1PfUZ\nM/vPwkY6rAlocvfun2SepqvgC+164D133+HubcCzwJUFztTTNjObCJD+PSc/qg+Emd0JzAC+6MWx\n/vl0uv5jfiP9PTAJWGVmEwqaqksT8Kx3eY2un6BDf8O22Av98EbUZlZK15tVvyhwJtL/sz4KpNz9\noULn6ebu97v7JHevpOvP6n/dvShGm+6+FfjAzM5OP3QdsK6Akbo1Apeb2Yj03+t1FMGbtT38Argz\n/fGdwM8LmOUwM7sRmAfc4u4HC50HwN3XuPuJ7l6Z/h5oAi5J/9srtOeAzwCY2VlAKTm4iVhRF3r6\nTZfujahTwJJcbUQd0FXAl+gaAdenf91c6FCDwDeBRWb2JnAR8ECB85D+ieFpYBWwhq7viYJcbWhm\nTwKvAmebWZOZ3Q1UAzeY2Qa6Vm5UF0muBUA5sCz97/+RIslVcH3kegyYkl7KuBi4Mxc/1ehKURGR\niCjqEbqIiGROhS4iEhEqdBGRiFChi4hEhApdRCQiVOgiIhGhQhcRiQgVuohIRPx/KnLX3B40Ck8A\nAAAASUVORK5CYII=\n", "text/plain": ["<matplotlib.figure.Figure at 0x1c0e4c665f8>"]}, "metadata": {}, "output_type": "display_data"}], "source": ["import matplotlib.pyplot as plt\n", "x = nuage[253][0]\n", "x2 = nuage[789][0]\n", "plt.plot(X,Y,'.')\n", "plt.plot([x,x], [0,10])\n", "plt.plot([x2,x2], [0,10])"]}, {"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):``. La fonction ``recursive`` tente de placer chaque point dans un intervalle distinct et elle \u00e9choue car elle d\u00e9passe le nombre d'appels r\u00e9cursifs autoris\u00e9s par le langage Python."]}, {"cell_type": "code", "execution_count": 14, "metadata": {"scrolled": false}, "outputs": [{"data": {"text/plain": ["(946, [0, 1, 1, 2, 2], [996, 996, 997, 997, 998])"]}, "execution_count": 15, "metadata": {}, "output_type": "execute_result"}], "source": ["def recursive(nuage, i, j, f):\n", "    if i+1 == j or i == j:\n", "        return [i]\n", "    k, mx = optimise(nuage, i, j, f)\n", "    if k is None:\n", "        return None\n", "    else:\n", "        r1 = recursive(nuage, i, k, f)\n", "        r2 = recursive(nuage, k, j, f)        \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", "# d\u00e9clenche une exception\n", "r = recursive(nuage, 0, len(nuage), fct)\n", "len(r), r[:5], r[-5:]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["La fonction n'est pas encore parfait et elle retourne plusieurs fois le m\u00eame point de coupure mais ce n'est pas le plus grave car la fonction retourne quasiment tous les points."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Q9 - seuil\n", "\n", "L'algorithme produit beaucoup de points de coupures. On souhaite arr\u00eater la r\u00e9cursion plus t\u00f4t en mettant un seuil sur la quantit\u00e9 obtenue $|\\Delta_{i}^k + \\Delta_{k}^j - \\Delta_{i}^j|$ qui doit \u00eatre sup\u00e9rieur \u00e0 50."]}, {"cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [{"data": {"text/plain": ["(5, [61, 253, 384, 553, 782])"]}, "execution_count": 16, "metadata": {}, "output_type": "execute_result"}], "source": ["def recursive(nuage, i, j, f, th=50):\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", "len(r), r[:5]"]}, {"cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [{"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD8CAYAAABn919SAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAGbxJREFUeJzt3Xt0VfWd9/H395yTEG4CchEUYsQr\n9a6peK+tuoqXUXw646hja6tPsTNtR6zzjNg+nc6s6ThxZurYtehTy6rWsoaILGttOw222KdqqRLl\nAIpwxAuaGORODOFirt/5Iyc0YELOztnnkp3Pay0Wycne53wWkA+//M5v75+5OyIiMvjFCh1ARETC\noUIXEYkIFbqISESo0EVEIkKFLiISESp0EZGIUKGLiESECl1EJCJU6CIiEZHI54tNmDDBKyoq8vmS\nIiKDXjKZ3OHuE/s7Lq+FXlFRwcqVK/P5kiIig56Z1WVynKZcREQiQoUuIhIRKnQRkYhQoYuIRIQK\nXUQkIvotdDN71My2mdnrPR77dzN7w8xeM7Ofm9nY3MYUEZH+ZDJCfwyYdchjy4DT3P0M4E3gvpBz\niYhEQlVNivPvf5YbH36RZF1jTl+r33Xo7v6CmVUc8thve3y6AvjzcGOJiAxecxev5levbaaj809b\nfG7Z3cKNP3qJJXdewLnHjsvJ64ZxYdHtwBN9fdHM5gBzAMrLy0N4ORGR4jN38Wpq1m6mvcPp7OOY\njk5nxcadxVnoZvYtoB1Y1Ncx7r4AWABQWVmpHalFJDKqa+v5z2Ub2L6nNaPjzeD86eNzlmfAhW5m\ntwHXApe7u4paRIaE6tp6nnilnje2NNPS3tdYvHf/Mvv0nI3OYYCFbmazgHuBT7n7vnAjiYgUl+ra\neu7/9Xr2tHYEPjducNJRo/nuDbktc8ig0M3sceAyYIKZNQDfoWtVyzBgmZkBrHD3r+Qwp4hIXh0Y\niW/eTUtHsEmI8yrGce9VM3Je4IfKZJXLzb08/EgOsoiIFNQnv7ss4/nw3pw4cSTL7rksvEAB5fX2\nuSIixWbu4tU8m9rKnpZg0ymJGLjD6ceM4emvXZyjdMGo0EVkSJq7eDW/WPMBQVd0xAyuO/NoHrrp\n7JzkyoYKXUSGhGRdI/csWUND437iRsbz4jG6lhsW00i8Lyp0EYm0qpoUi2rraO4xpdKewXkGXHLi\nBBbeMTNn2cKmQheRyKmqSbFk5fu0dnRmPDdeEoPxo4Yx+6xjmHf1jBwnzA0VuohEwuz5y1m7qYlh\niRj72jK/4CceM/7sjClFOScelApdRAal6tp6/u2ZFE372w96Y7O/Mo8ZTBo1jM984ig+d87UvK8V\nzyUVuogMGsm6Rr7801fYta8t0HkjSmKMG1nKVz99IrfMjO5NAlXoIlL05i5ezdLXtwS6d8rosjhj\nykr4m4iXeE8qdBEpStW19fzzr9axP+ANsCaPHsYPbj03UlMpmVKhi0hRqapJsXBFHfsC3AjLgOvP\nKs6LffJJhS4iBVddW8+jyzeypemjjO9oaMDxk0Zx+0XHDZkplf6o0EUk76pr63n0j++yade+QFMq\ncYMxw0u4sXLaoF0rnksqdBHJm7mLV/PLVz+gM+ANVOIx+PLF01Xi/VChi0hOJesaeWBpimRdI0Fu\nKz5xVCl3X3myplMCUKGLSOiSdY3835+vZcPW5kCj8VGlcS44YQJf+dTxQ3KVSrZU6CISirmLV/Ob\ndVuImwXeqq0sEeOLF1ZoSiVLKnQRycrs+ctZ09AU+LxJo0uZe4WmVMKkQheRwKpqUjyzbgsNjfsI\nct3PiNI4Xzj/WI3Ec0SFLiIZG+hovGL8CL5341maF88xFbqIHFb3vcWb9rdlvEplRGmMI8pKBvW9\nxQcjFbqIfEz3hT/1O/fSGmCt4ahhca6YcdSQvwS/UFToIgJ0LTV8alUDy9/aQd2ufRmdMzwRww3O\nqzhyUG3VFlUqdJEhLlnXyMPPv8Oy9VszPkc3wypO/Ra6mT0KXAtsc/fT0o8dCTwBVADvATe6e2Pu\nYopImJJ1jXz76bVs2NKc8bz48ESMS06ayJ266KdoZTJCfwyYDyzs8dg84HfuXmVm89Kf3xt+PBEJ\n09zFq/nVax/QEWCpYUncuOOi4/Tm5iDQb6G7+wtmVnHIw9cDl6U//inwHIOl0JfO6/r9qqrC5sih\nB15+AIB7zxscfyVb7r8fgMnf/GaBk2TvD0veBOCSG08qcJI/qa6t5/5frw909WbcoDQR47OnTs5q\nWuX3jy0A4NNfnDPg55DMDXQO/Sh33wzg7pvNbFJfB5rZHGAOQHl5EVwRtmVtoRPk3Bu73ih0hEBa\nUoMr7+HseH9PoSMAf7oh1pr3Pwy0SiURMy48fnxob3Buq9sYyvNIZnL+pqi7LwAWAFRWVga8aaaI\nBFFVk2LhS+/1u/N9TzGDk48azXdvOF1z44PcQAt9q5lNSY/OpwDbwgwlIsEk6xr5/I9XBCryGZNV\n4lEz0EL/JXAbUJX+/RehJRKRjFTX1vPgsxvYtac141vUxgyuO1PLDaMqk2WLj9P1BugEM2sAvkNX\nkS8xszuAeuAvchlSRA4W5J4qBtx5qXb7GQoyWeVycx9fujzkLCLSh2RdI/csWUPdzn1k+kaUAWdO\nHcPTX7s4l9GkiOhKUZEiVl1bz4PLNrBjT2vG55ylEh+yVOgiRejK7z3HW9v3Znx8DLhOl+IPeSp0\nkSKRrGvkR8+/w+9SWzO6HD9mMH6kNlKWP1GhixTY7PnLebWhKdDcuG6MJb1RoYsUQLKukW88sSbj\n29QCjCiJ8YULtJGy9E2FLpJH3Zfkv/xe5jcnnTx6GD+49VxdACT9UqGL5Fj3/cZfentHRjfIGlUa\nZ/KYMm6/eLrmxiUQFbpIjiTrGqlamuKVDEfjMWCOLgCSLKjQRUL2+qYm7p7364yPjxt8+RIVuWRP\nhS4SotX1jbS0d0Lp4Y8bFjdGliW48dxpKnIJjQpdJCTVtfVdZd6H4SUxgKw3jRDpiwpdJCRLX9/M\n0X187SuaG5c8UKGLhOSq06bw6qrdBz2me45LPqnQRUJyy8xympc2sGtvK/ffoMvxJf9U6CIhmjS6\njEmjy7hBZS4FECt0ABERCYcKXUQkIlToIiIRoUIXEYkIFbqISESo0EVEIkKFLiISESp0EZGIyKrQ\nzexuM1tnZq+b2eNmVhZWMBERCWbAhW5mxwB/C1S6+2lAHLgprGAiIhJMtlMuCWC4mSWAEcAH2UcS\nEZGBGHChu/sm4D+AemAz0OTuvw0rmIiIBJPNlMs44HrgOOBoYKSZ3drLcXPMbKWZrdy+ffvAk4qI\nyGFlM+VyBfCuu2939zbgKeDCQw9y9wXuXunulRMnTszi5URE5HCyKfR64HwzG2FmBlwOpMKJJSIi\nQWUzh14LPAmsAtamn2tBSLlERCSgrDa4cPfvAN8JKYuIiGRBV4qKiESECl1EJCJU6CIiEaFCFxGJ\nCBW6iEhEqNBFRCJChS4iEhEqdBGRiFChi4hEhApdRCQiVOgiIhGhQhcRiQgVuohIRKjQRUQiQoUu\nIhIRKnQRkYhQoYuIRIQKXUQkIlToIiIRoUIXEYkIFbqISESo0EVEIkKFLiISESp0EZGIyKrQzWys\nmT1pZm+YWcrMLggrmIiIBJPI8vzvA8+4+5+bWSkwIoRMIiIyAAMudDM7ArgU+CKAu7cCreHEEhl8\nZs9fzinv7qckHqO8rpFzjx1X6EgyxGQzQp8ObAd+YmZnAkngLnffG0oykSKXrGvkq4uSbN3dgqcf\nO9lLaW3v5HM/fJGf/fWFKnXJq2wKPQGcA3zd3WvN7PvAPODbPQ8ysznAHIDy8vIsXk6k8GbPX86r\nDU0AB0q8Lys27lShS15lU+gNQIO716Y/f5KuQj+Iuy8AFgBUVlb29z0gUnRmz1/Oq5ua8ID/es+f\nPj43gUT6MOBCd/ctZva+mZ3s7huAy4H14UUTKYzq2noefHYDu/a00jnAIcj9N5yu0bnkXbarXL4O\nLEqvcNkIfCn7SCKFkaxr5NtPr2X95uZA5xkQj8GI0gRHtCWYNn4kt8zU9KLkX1aF7u5rgMqQsojk\nVVVNiiXJBjo6OylJxNjZ3NrvvHhPxx45ggf/8qyDRuI//96q8IOKZCjbEbrIoJGsa+Th599hTX0j\nO/cObDplRGmc044+gnuvmqEpFSk6KnSJtGRdIz96/h1efHsHe1o7BvQcMYOLT5jAwjtmhpxOJFwq\ndImc7jc1G/e20tEZ7FwDjhieIG7GjZXTmHf1jJxkFMkFFbpEQlVNiiUr36f5o3baAs6lJGJw1Jjh\nnDrlCO781PGaSpFBS4Uug1Z1bT3316xnT0vwqZS4QTxmXH36FB666ewcpBPJPxW6DCrVtfX8v9+/\nxdbmFto6gr+rOWFUKd+48mQtK5RIUqFL0auurefRP77Lxm17CDglfsDUsWUsn3d5qLlEio0KXYpS\nsq6RFRt38tbWZp5e80GgcxNxOHHiaL6rqzVliFGhS9FI1jXyjSfWUL9rX6ALfLrNmKwSl6FNhS4F\nlaxrZPeOvXy4r5W7f/hioHNHlsYZVhLnxnOnanmhCCp0KZDq2noeenYD25pbeWD3R/0eb3Rd4NPp\ncMLEkSy757KcZxQZbFTokjfdb25ub/6Ipv3tGZ1jwM0zy/ncOVM1lSLSDxW65NTcxaupWbuZ9k4P\ndO+U0rhx1rSxumeKSAAqdAldd4m3BlgnHo8Zo4bFuWLGUbrQR2SAVOgSiqqaFE+v2cTelnaaA1y5\nOXpYnKPHDqf8yBG8/k+zcphQJPpU6DJgcxevZunrW2jr6Aw0nTJmeIKZx40/cN+Uus9X5y6kyBCi\nQpfAvvBILS+8tSPQOQYcM7aMv/n0ibrsXiRHVOiSkaqaFNUv17P7o8xWp3RLxODaM47WvLhIHqjQ\n5bCqalL85MX3aGnP7C4qxx45gpMnj2bi6GH8Ly01FMkrFbp8TPd68fqdezNeqaLL7kUKT4UuBwQd\njRvwyYpxWisuUiRU6ENcVU2KhS+9x/62zoxviKV5cZHipEIfgqpr63nilXre2trMvrbMRuPDEzEu\nOWmitmgTKWIq9CEk6JZtpXFjVFmJ7mYoMkhkXehmFgdWApvc/drsI0mYknWNVC1Nsf6D3extzazI\nyxIxvnhhhUpcZJAJY4R+F5ACjgjhuSREs+cvZ01DU8bHjxme4N5ZM3Thj8gglVWhm9lU4BrgX4Bv\nhJJIsvb2tj3s3NvCvgzKPGZwyuTR/PNsLTkUGeyyHaE/BPw9MDqELBKCuYtXs2NPS7/HxWPGn50x\nRStVRCJkwIVuZtcC29w9aWaXHea4OcAcgPJy/Sifa8+9uR0m9P61ESUxZp8zVZtFiERUNiP0i4Dr\nzOxqoAw4wsz+y91v7XmQuy8AFgBUVlYOZO9fCeCykybym10HP2bAJSdOYOEdMwuSSUTyY8CF7u73\nAfcBpEfof3domUv+PXTT2VyycBiN+1p1Ob7IEKN16BF0wqRRAPxk1qUFTiIi+RRKobv7c8BzYTyX\niIgMTKzQAUREJBwqdBGRiFChi4hEhApdRCQiVOgiIhGhQhcRiQgVuohIRKjQRUQiQoUuIhIRKnQR\nkYhQoYuIRIQKXUQkIlToIiIRoUIXEYkIFbqISESo0EVEIkKFLiISESp0EZGIUKGLiESECl1EJCJU\n6CIiEaFCFxGJCBW6iEhEqNBFRCJiwIVuZtPM7PdmljKzdWZ2V5jBREQkmEQW57YD97j7KjMbDSTN\nbJm7rw8pm4iIBDDgQnf3zcDm9MfNZpYCjgFU6AWSrGvkZ6saeHN3MyXxGMm6Rs49dlyhY4lInmQz\nQj/AzCqAs4HaMJ5P+pesa+SeJWv44MP9jBlewq59bXR0OgDDy1sBuHnBSzw+5wKVusgQkXWhm9ko\n4GfAXHff3cvX5wBzAMrLy7N9uSFr9vzlrGloAiBmkO5uALbvae31nLYOZ8XGnSp0kSEiq0I3sxK6\nynyRuz/V2zHuvgBYAFBZWem9HSMf94VHavnD2zvwXv7EOjP8UyyJG+dPHx9uMBEpWgMudDMz4BEg\n5e4Phhdp6KmqSbEk+T77Wzpo7eykozO75ytNxBg3opTvXaPpFpGhJJsR+kXA54G1ZrYm/dg33b0m\n+1jRlqxr5EfPv8PL7+6kaX872f7YMqo0Tkv6f4FrTp9C09iuEleZiwwt2axyWQ5YiFkiraomxSN/\nfJe2juxnneIxGD0swYRRw7j94uncMvPg9ya+9EzWLyEig1Aoq1zk46pqUixZ+T57Wtpp6/CsRuEx\ng4tPmMDCO2aGlk9EokeFHqKqmhTVL9ez56N2BjoNHjdwBzO4SCUuIgGo0LMQxjSKAaVx48xpY7n3\nqhma9xaRAVOhB5Ssa+SpVQ0sXbuZXfvaBvQccetaifLZUyfz0E1nh5xQRIYqFXoGulel/OGt7exv\nCzaZEgMsZkwdO5wH//IsjcBFJGdU6H1I1jXywNIUrzY00dIevMRHlSW45bxy5l09IzcBRUQOoUI/\nRFVNikW1dTS3dAQ+14A7L52uEheRglChky7xl+tpaeugNcAbnCVxo6wkzl9pJC4iRWDIFnr3vPhz\nG7ZlXOKJWNd9VEaXJbh31oyPXdAjIlJIQ67Q63ft5YOmj7jphy9mfM6wRIwvXVihUbiIFLUhVehV\nNSkua/qo3+OGJYzhpQkmjCzt9dJ6EZFiNKQK/Zl1W7jsMF9PxIz/ffFxGomLyKA0pAp91qmTYcXH\nH0/EjGvPmKKLfERkUBtShT7v6hnUp8rYnJ52KYnBHRdrmaGIRMOQKnSA8iNHUn7kSN770jWFjiIi\nEqpYoQOIiEg4VOgiIhGhQhcRiQgVuohIRKjQRUQiQoUuIhIRKnQRkYhQoYuIRIQKXUQkIrIqdDOb\nZWYbzOxtM5sXVigREQluwIVuZnHgB8BVwCeAm83sE2EFExGRYLK5l8t5wNvuvhHAzBYD1wPrwwjW\nU/cWca0dnZSVxOjscPa2dBCLGaVxY39bJxiMKUtQloizY28LXTt8Op3p/Z27t3l+onQn40eWckLY\nIUVECiybKZdjgPd7fN6QfixUVTUpHn5hI80ftdPS1knTvnaaWzroBNo7nX1tnTjgDh/ub2dLcwvt\nnV1fa+/sKvLOHs/nwI69rcxdvDrsqCIiBZXNCN16eexjm3Oa2RxgDkB5efCdf55ZtyXwOYezvvNY\nAJ57c3uoz1tMTjnylEJHCGTYjMGV93AmTBtV6AhFZdKx0wsdYUgx98x3uT/oRLMLgH9098+mP78P\nwN3/ta9zKisrfeXKlYFep3uEHrbZZx2tDS1EZFAws6S7V/Z3XDYj9FeAE83sOGATcBNwSxbP16vu\nzSfCmkNPxODaM1TmIhI9Ay50d283s68BvwHiwKPuvi60ZD3Mu3qGdhUSEelHVjsWuXsNUBNSFhER\nyYKuFBURiQgVuohIRKjQRUQiQoUuIhIRKnQRkYgY8IVFA3oxs+1A3QBPnwDsCDFOWJQrGOUKRrmC\nKdZckF22Y919Yn8H5bXQs2FmKzO5UirflCsY5QpGuYIp1lyQn2yachERiQgVuohIRAymQl9Q6AB9\nUK5glCsY5QqmWHNBHrINmjl0ERE5vME0QhcRkcMo+kIvxo2ozWyamf3ezFJmts7M7ip0pp7MLG5m\nq83svwudpSczG2tmT5rZG+k/uwsKnQnAzO5O/z2+bmaPm1lZgXI8ambbzOz1Ho8daWbLzOyt9O/j\niiTXv6f/Hl8zs5+b2dhiyNXja39nZm5mE4oll5l9Pd1l68zs33Lx2kVd6EW8EXU7cI+7zwDOB75a\nJLm63QWkCh2iF98HnnH3U4AzKYKMZnYM8LdApbufRtetoG8qUJzHgFmHPDYP+J27nwj8Lv15vj3G\nx3MtA05z9zOAN4H78h2K3nNhZtOAK4H6fAdKe4xDcpnZp+nac/kMdz8V+I9cvHBRFzo9NqJ291ag\neyPqgnL3ze6+Kv1xM13FFPp+qgNhZlOBa4AfFzpLT2Z2BHAp8AiAu7e6+4eFTXVAAhhuZglgBPBB\nIUK4+wvArkMevh74afrjnwKz8xqK3nO5+2/dvT396QpgajHkSvtP4O/pZUvMfOgj118DVe7ekj5m\nWy5eu9gLPS8bUWfDzCqAs4HawiY54CG6/jF39ndgnk0HtgM/SU8H/djMRhY6lLtvomu0VA9sBprc\n/beFTXWQo9x9M3QNJIBJBc7Tm9uBpYUOAWBm1wGb3P3VQmc5xEnAJWZWa2bPm9knc/EixV7oGW1E\nXShmNgr4GTDX3XcXQZ5rgW3unix0ll4kgHOAH7r72cBeCjN9cJD0nPT1wHHA0cBIM7u1sKkGDzP7\nFl1TkIuKIMsI4FvAPxQ6Sy8SwDi6pmj/D7DEzHrrt6wUe6E3ANN6fD6VAv04fCgzK6GrzBe5+1OF\nzpN2EXCdmb1H1/TUZ8zsvwob6YAGoMHdu3+SeZKugi+0K4B33X27u7cBTwEXFjhTT1vNbApA+vec\n/Kg+EGZ2G3At8FdeHOufj6frP+ZX098DU4FVZja5oKm6NABPeZeX6foJOvQ3bIu90A9sRG1mpXS9\nWfXLAmci/T/rI0DK3R8sdJ5u7n6fu0919wq6/qz+v7sXxWjT3bcA75vZyemHLgfWFzBSt3rgfDMb\nkf57vZwieLO2h18Ct6U/vg34RQGzHGBms4B7gevcfV+h8wC4+1p3n+TuFenvgQbgnPS/vUJ7GvgM\ngJmdBJSSg5uIFXWhp9906d6IOgUsydVG1AFdBHyerhHwmvSvqwsdahD4OrDIzF4DzgLuL3Ae0j8x\nPAmsAtbS9T1RkKsNzexx4CXgZDNrMLM7gCrgSjN7i66VG1VFkms+MBpYlv73/3CR5Cq4PnI9CkxP\nL2VcDNyWi59qdKWoiEhEFPUIXUREMqdCFxGJCBW6iEhEqNBFRCJChS4iEhEqdBGRiFChi4hEhApd\nRCQi/gdUAxqHlh+fygAAAABJRU5ErkJggg==\n", "text/plain": ["<matplotlib.figure.Figure at 0x1c0e3bc5c18>"]}, "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,10])"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Q10 - 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": 17, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["628 ms \u00b1 6.15 ms per loop (mean \u00b1 std. dev. of 7 runs, 1 loop each)\n"]}], "source": ["def somme_diff2(xy, i, j):\n", "    m = sum(e[1] for e in xy[i:j]) / (j-i)\n", "    return sum((e[1]-m)**2 for e in xy[i:j])\n", "\n", "def difference2(nuage, i, j, k):\n", "    m1 = somme_diff2(nuage, i, k)\n", "    m2 = somme_diff2(nuage, k, j)\n", "    m = somme_diff2(nuage, i, j)\n", "    return abs(m1+m2-m)\n", "\n", "def optimise2(nuage, i, j):\n", "    mx = -1\n", "    ib = None\n", "    for k in range(i+1,j-1):\n", "        d = difference2(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 optimise2(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": 18, "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... Nous allons optimiser ce calcul en tenant compte du fait que la fonction de co\u00fbt est $f(x,y) = (x-y)^2$. Il faut \u00e9galement se souvenir de la formule $\\mathbb{V}X = \\mathbb{E}(X^2) - (\\mathbb{E}X)^2$ ce qu'on transforme en $\\sum_{i=1}^n (X_i-M)^2 = \\sum_{i=1}^n X_i^2 - n M^2$ avec $M = \\frac{1}{n} \\sum_{i=1}^n X_i$."]}, {"cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [{"data": {"text/plain": ["((553, 13082.574312018376), (553, 13082.574312018447))"]}, "execution_count": 20, "metadata": {}, "output_type": "execute_result"}], "source": ["def optimise_rapide(nuage, i, j):\n", "    # On calcule les histogrammes.\n", "    Y = sum(y for x,y in nuage)\n", "    Y_1 = sum(y for x,y in nuage[i:i+1])\n", "    Y_2 = sum(y for x,y in nuage[i+1:j])\n", "    Y2 = sum(y**2 for x,y in nuage)\n", "    Y2_1 = sum(y**2 for x,y in nuage[i:i+1])\n", "    Y2_2 = sum(y**2 for x,y in nuage[i+1:j])\n", "    \n", "    m = Y2 - Y**2 / len(nuage)\n", "    m1 = Y2_1 - Y_1**2\n", "    m2 = Y2_2 - Y_2**2/(len(nuage)-1)\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 sommes Y?_?\n", "        y = nuage[k][1] \n", "\n", "        Y_1 += y\n", "        Y_2 -= y\n", "        Y2_1 += y**2\n", "        Y2_2 -= y**2\n", "        \n", "        m1 = Y2_1 - Y_1**2 / (k-i+1)\n", "        m2 = Y2_2 - Y_2**2 / (j-k-1)\n", "        \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)), optimise2(nuage, 0, len(nuage))"]}, {"cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["1.77 ms \u00b1 43.6 \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": ["Carr\u00e9ment plus rapide."]}, {"cell_type": "code", "execution_count": 21, "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}