ericw
/
CapesNSI2021
1
0
Fork 0
Code Issues Pull Requests Projects Releases Wiki Activity
CapesNSI2021/2021_epreuve_1.ipynb

2068 lines
110 KiB
Plaintext
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

{
"cells": [
{
"cell_type": "raw",
"metadata": {},
"source": [
"---\n",
"CAPES NSI 2021\n",
"Épreuve n°1\n",
"date: 22/03/2021\n",
"---"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Cette épreuve est constituée de deux problèmes indépendants."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Pour ce sujet, **le langage de programmation utilisé sera Python**. Vous pourrez utiliser les fonctions Python de manipulation de listes ou de matrices suivantes :\n",
"\n",
"* Création d’une liste de taille $n$ remplie avec la valeur $x$ : `li = [x] * n`. \n",
"* Obtention de la taille d’une liste `li` : `len(li)`.\n",
"* Si `li` est une liste de $n$ éléments, on peut accéder au $k^e$ élément (pour $0\\leq k < \\mathtt{len(li)}$) avec `li[k]`. On peut définir sa valeur avec `li[k] = x`.\n",
"* Un élément $x$ peut être ajouté dans une liste `li` à l’aide de `li.append(x)`. On considèrera qu’il s’agit d’une opération élémentaire.\n",
"* Les matrices sont des listes de listes, chaque sous-liste étant considérée comme une ligne de la matrice. Si `mat` est une matrice, elle possède `len(mat)` lignes et `len(mat[0])` colonnes.\n",
"* Création d’une matrice de $n$ lignes et $p$ colonnes, dont toutes les cases contiennent $x$ : `mat = [[x for j in range(p)] for i in range(n)]`.\n",
"* On accède à (resp. modifie) l’élément de `mat` dans la $i^e$ ligne et $j^e$ colonne avec `mat[i][j]` (resp. `mat[i][j] = x`).\n",
"\n",
"À moins de les redéfinir explicitement, l’utilisation de toute autre fonction sur les listes (`sort`, `index`, `max`, etc.) est interdite. On rappelle enfin qu’une fonction qui s’arrête sans avoir rencontré l’instruction `return`renvoie `None`."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Problème 1 : Points proches dans le plan"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ce problème, pouvant par exemple survenir dans le domaine de la navigation maritime, vise à détermi-ner, dans un nuage de points du plan, la paire de points les plus proches. Il est constitué de trois parties dépendantes."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Formellement, on suppose qu'on dispose de $n$ points dans le plan ($M_0$, $M_1$, ..., $M_{n-1}$) dans un ordre quelconque pour le moment. Ils seront représentés en Python par deux listes de flottants de taille $n$ : `coords_x` et `coords_y`, donnant respectivement les abscisses et les ordonnées des points. On dira ainsi que $M_i$ est le point d'indice $i$, qu'il a pour abscisse $x_i =$ `coords_x[i]` et pour ordonnée $y_i=$`coords_y[i]`. On supposera que `coords_x` et `coords_y` sont des variables globales, qu'on ne modifiera jamais au cours de l'exécution de l’algorithme."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"hors_enonce"
]
},
"source": [
"Exemple de nuage de points aléatoires"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"tags": [
"hors_enonce"
]
},
"outputs": [],
"source": [
"from random import random\n",
"n = 32\n",
"coords_x = [random() for _ in range(n)]\n",
"coords_y = [random() for _ in range(n)]"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"tags": [
"hors_enonce"
]
},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD4CAYAAAD8Zh1EAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAASqUlEQVR4nO3dXYxk513n8e8vY2YjIC+wM0CwPRmjHUuMAkuilkkDIo3GrMa+sJHCsrbIElZWRsAaIYGQjEJCZF+MAoILhHdhlI0CkYgxES8jZSKz8bplKbTNtJXgxBPZGcyLx8niIRjfRMGx+XNxqk3Rqe4603266vSp70ca1ak6j7r+fWrqV08/56nnpKqQJO1/r5p3AZKkbhjokjQQBrokDYSBLkkDYaBL0kBcNa8nPnToUB09enReTy9J+9Jjjz32D1V1eNK+uQX60aNHWV9fn9fTS9K+lORvt9o3dcglyQeTPJfks1vsT5LfTHIxyeNJ3rKbYiVJO9NmDP1DwMlt9t8EHBv9OwX8792XJUm6UlMDvaoeBv5xmya3Ar9XjUeA1yd5Q1cFSpLa6WKWy9XAM2P3L40e+xpJTiVZT7J++fLlDp5akrRhptMWq+pMVS1V1dLhwxNP0kqSdqiLQH8WuHbs/jWjxyRJM9RFoJ8FfmI02+WtwAtV9cUOfq40fGtrcPp0cyvt0tR56Ek+AqwAh5JcAn4F+DqAqvpt4BxwM3AR+DLwP/aqWE2xtgarq7CyAsvL865G06ytwYkT8OKLcPAgPPigr5t2ZWqgV9XtU/YX8D87q0g7YzjsP6urzev18svN7eqqr5l2xbVchmJSOKjfVlaaD98DB5rblZV5V6R9bm5f/VfHNsJho4duOPTf8nLzl5TDZOqIgT4UhsP+tLzsa6XOGOhDYjjMniei1SMGurRTnohWz3hSVNopT0SrZwx0aaecpaKecchF2ilPRKtnDHRpNzwRrR5xyEWSBsJAl6SBMNDVX21XInTFQglwDF191XaOt3PBpVfYQ1c/tZ3j7Vxw6RUGuvqp7Rxv54JLr3DIRf3Udo73LOaCL8J6LYvwOy6ANNenmL2lpaVaX1+fy3NLrS3CGP0i/I4DkuSxqlqatM8hF2k7izBGvwi/44Iw0KXtLMIY/SL8jgvCMXRpO4uwXssi/I4LwjF0SdpHHEOXpAVgoEvSQBjokjQQBrokDYSBLkkDYaBL0kAY6JI0EAa6JA2EgS5p57xaVK/41X/tDZdjHT5XaewdA13d842+GCat0rjT19kOQCdaDbkkOZnkySQXk9w1Yf+RJA8l+VSSx5Pc3H2p2jdcjnUxdLVK40YH4D3vaW4dvtmxqYGe5ABwL3ATcBy4PcnxTc1+Gbi/qt4M3Ab8r64L1T7icqyLYWOVxnvu2d1fYXYAOtNmyOUG4GJVPQ2Q5D7gVuDCWJsCXjvafh3whS6L1D7jcqyLY3l596/vRgdgY4jODsCOtQn0q4Fnxu5fAr53U5v3AX+W5GeBbwBunPSDkpwCTgEcOXLkSmvVftLFG12LwQ5AZ7o6KXo78KGq+vUky8CHk7ypqv5lvFFVnQHOQLMeekfPLWm/swPQiTYnRZ8Frh27f83osXF3APcDVNUa8GrgUBcFSpLaaRPo54FjSa5LcpDmpOfZTW3+DjgBkOQ7aQL9cpeFSpK2NzXQq+ol4E7gAeBzNLNZnkhyd5JbRs1+AXhXkr8EPgL8ZM3r2naStKBajaFX1Tng3KbH3ju2fQH4/m5LkyRdCddykaSBMNAlaSAMdEkaCANdkgbCQJekgTDQpaHy4hMLx/XQpSFyTfqFZA9dGiKXpF1IBro0RK5Jv5AccpGGyCVpF5KBLg2VS9IuHIdcJGkgDHRJ/eOUyx1xyEVSvzjlcsfsoUvqF6dc7piBLqlfnHK5Yw65SOoXp1zumIEuqX+ccrkjDrlI0kAY6JI0EAa6JA2EgS5JA2GgS9JAGOiSNBAGuiQNhIEuSQNhoEvSQBjoUpdc9lVz5Ff/pa647KvmzB661BWXfdWcGehSV1z2VXPWKtCTnEzyZJKLSe7aos2PJbmQ5Ikkv99tmdI+sLHs6z33ONyiuZg6hp7kAHAv8MPAJeB8krNVdWGszTHgl4Dvr6rnk3zLXhUs9ZrLvmqO2vTQbwAuVtXTVfUicB9w66Y27wLurarnAarquW7LlCRN0ybQrwaeGbt/afTYuOuB65N8MskjSU52VaAkqZ2upi1eBRwDVoBrgIeTfFdV/dN4oySngFMAR44c6eiptWNra17my2OgAWkT6M8C147dv2b02LhLwKNV9VXgr5M8RRPw58cbVdUZ4AzA0tJS7bRodcA50x4DDU6bIZfzwLEk1yU5CNwGnN3U5k9oeuckOUQzBPN0d2Wqc86Z9hhocKYGelW9BNwJPAB8Dri/qp5IcneSW0bNHgC+lOQC8BDwi1X1pb0qWh1wzrTHQIOTqvmMfCwtLdX6+vpcnlsjjh97DLTvJHmsqpYm7jPQJWn/2C7Q/eq/JA2EgS5JA2GgS9JAGOiSNBAGuiQNhIEuSQNhoEvSQBjokjQQBrokDYSBrvlaW4PTp5tbSbvS1Xro0pVz+VqpU/bQNT8uXyt1ykAfuj4PafR5+do+HzdpCw65DFnfhzSWl5ua+rZ8bd+Pm7QFA33IJg1p9C2Ylpf7V9N+OG7SBA65DFmfhzT6zOOmfcoe+pD1dUij7zxu2qe8YpEk7SNesUiSFoCBLkkDYaBL0kAY6JI0EAa6JA2EgS5JA2GgS9JAGOiSNBAGuiQNhIEuSQNhoEvSQBjokjQQBrokDUSrQE9yMsmTSS4muWubdm9PUkkmrgQmSdo7UwM9yQHgXuAm4Dhwe5LjE9q9Bvg54NGui5QkTdemh34DcLGqnq6qF4H7gFsntLsHeD/wlQ7rkyS11CbQrwaeGbt/afTYK5K8Bbi2qj623Q9KcirJepL1y5cvX3GxkqSt7fqkaJJXAb8B/MK0tlV1pqqWqmrp8OHDu31qSdKYNoH+LHDt2P1rRo9teA3wJmA1yd8AbwXOemJUkmarTaCfB44luS7JQeA24OzGzqp6oaoOVdXRqjoKPALcUlVeMFSSZmhqoFfVS8CdwAPA54D7q+qJJHcnuWWvC5T2zNoanD7d3EoDcFWbRlV1Dji36bH3btF2ZfdlSXtsbQ1OnIAXX4SDB+HBB2F5ed5VSbviN0W1mFZXmzB/+eXmdnW1259v719z0KqHLg3OykrTM9/ooa+sdPez7f1rTgx0Labl5SZoV1ebMO8ycCf1/g10zYCBrsW1vLw3QbuXvX9pGwa61LW97P1L2zDQpb2wV71/aRvOclH/OWNEasUeuvrNGSNSa/bQ1W9bzRe31y59DXvo6rdJM0bstUsT2UNXv23MGLnnnn8L7r3+lqe0T9lDV/9tnjHiPG9pIgO9T9bWnLvchvO8pYkM9L5wXPjKOM9b+hqOoffFbsaFnfEhCXvo/bHTcWF79pJG7KH3xaTZHG3Mc8aHfxlIvWIPvU92Mi48rxkf/mUg9Y6Bvt/Na8aHa35LvWOgD8E8Znw4F1zqHQNdO+NccKl3DHTtXNd/GfjFKmlXDHT1gydZpV1z2qL6wQW3pF0z0NUPGydZDxzwJKu0Qw65qB88ySrtmoGu/nDBLWlXHHKRpIEw0CVpIAx0SRoIA12SBsJAl6SBaBXoSU4meTLJxSR3Tdj/80kuJHk8yYNJ3th9qZKk7UwN9CQHgHuBm4DjwO1Jjm9q9ilgqaq+G/go8KtdFypJ2l6bHvoNwMWqerqqXgTuA24db1BVD1XVl0d3HwGu6bZMSdI0bQL9auCZsfuXRo9t5Q7g45N2JDmVZD3J+uXLl9tXKUmaqtOTokneASwBvzZpf1Wdqaqlqlo6fPhwl08tSQuvzVf/nwWuHbt/zeixfyfJjcC7gbdV1T93U54kqa02PfTzwLEk1yU5CNwGnB1vkOTNwO8At1TVc92XKUmaZmqgV9VLwJ3AA8DngPur6okkdye5ZdTs14BvBP4wyaeTnN3ix0mS9kir1Rar6hxwbtNj7x3bvrHjuiRJV8hvikrSQBjokjQQBvqQra3B6dPNraTB84pFQ7W2BidONBdcPniwubybVwOSBs0e+lCtrjZh/vLLze3q6rwrkrTHDPShWllpeuYHDjS3KyvzrkjSHnPIZaiWl5thltXVJswdbpEGz0AfsuVlg1xaIA65SNJAGOiSNBAGuiQNhIEuSQNhoEvSQBjokjQQBrokDYSBLkkDYaBL0kAY6JI0EAa6JA2EgS5JA2GgS9JAGOiSNBAGuiQNhIEuSQNhoKs/1tbg9OnmVtIV84pF6oe1NThxormg9cGDzeXzvNqSdEXsoasfVlebMH/55eZ2dXXeFUn7joGuflhZaXrmBw40tysr865I2nccclE/LC83wyyrq02YO9wiXTEDXf2xvLxYQb625geYOmWgS/OwH08C+wHUewb6UPnm67dJJ4H7/Drtxw+gBdTqpGiSk0meTHIxyV0T9v+HJH8w2v9okqOdV6r2Nt5873lPc+u87v7p4iTwLOftOwtpX5jaQ09yALgX+GHgEnA+ydmqujDW7A7g+ar6T0luA94P/Le9KFgt7Lfe3yLa7UngWfeYNz6ANp7PWUi91GbI5QbgYlU9DZDkPuBWYDzQbwXeN9r+KPBbSVJV1WGtass33/6wm5PAs/7QdhbSvtAm0K8Gnhm7fwn43q3aVNVLSV4A/iPwD+ONkpwCTgEcOXJkhyVrKt98wzePD+1Fm4W0D830pGhVnQHOACwtLdl730u++YbND21N0CbQnwWuHbt/zeixSW0uJbkKeB3wpU4qlDSZH9rapM0sl/PAsSTXJTkI3Aac3dTmLPDO0faPAv/P8XNJmq2pPfTRmPidwAPAAeCDVfVEkruB9ao6C/wf4MNJLgL/SBP6kqQZajWGXlXngHObHnvv2PZXgP/abWmSpCvhaouSNBAGuiQNhIEuSQOReU1GSXIZ+NsZPuUhNn3RqYescff6Xh9YY1f6XuNe1ffGqjo8acfcAn3WkqxX1dK869iONe5e3+sDa+xK32ucR30OuUjSQBjokjQQixToZ+ZdQAvWuHt9rw+ssSt9r3Hm9S3MGLokDd0i9dAladAMdEkaiMEGepJvTvJ/k3x+dPtNE9p8T5K1JE8keTzJTC6b1/drtLao7+eTXBgdsweTvHGW9bWpcazd25NUkplPb2tTY5IfGx3LJ5L8ft9qTHIkyUNJPjV6vW+ecX0fTPJcks9usT9JfnNU/+NJ3jLL+lrW+OOj2j6T5M+T/Oc9K6aqBvkP+FXgrtH2XcD7J7S5Hjg22v524IvA6/e4rgPAXwHfARwE/hI4vqnNzwC/Pdq+DfiDGR63NvX9EPD1o+2fnmV9bWsctXsN8DDwCLDUtxqBY8CngG8a3f+WHtZ4Bvjp0fZx4G9mXOMPAm8BPrvF/puBjwMB3go8Osv6Wtb4fWOv8U17WeNge+g01zn93dH27wI/srlBVT1VVZ8fbX8BeA6Y+A2sDr1yjdaqehHYuEbruPHaPwqcSJI9rqt1fVX1UFV9eXT3EZqLnsxSm2MIcA/NBcu/MsviRtrU+C7g3qp6HqCqnuthjQW8drT9OuALM6yPqnqYZknurdwK/F41HgFen+QNs6muMa3GqvrzjdeYPX6/DDnQv7Wqvjja/v/At27XOMkNNL2Uv9rjuiZdo/XqrdpU1UvAxjVaZ6FNfePuoOkhzdLUGkd/el9bVR+bZWFj2hzH64Hrk3wyySNJTs6sukabGt8HvCPJJZoltH92NqW1dqX/X+dtT98vM72maNeSfAL4tgm73j1+p6oqyZbzM0ef6B8G3llV/9JtlcOV5B3AEvC2edcyLsmrgN8AfnLOpUxzFc2wywpNr+3hJN9VVf80z6I2uR34UFX9epJlmgvZvMn3yZVL8kM0gf4De/Uc+zrQq+rGrfYl+fskb6iqL44Ce+Kfs0leC3wMePfoT7a91vdrtLapjyQ30nxwvq2q/nlGtW2YVuNrgDcBq6ORqm8Dzia5parWe1IjNL3JR6vqq8BfJ3mKJuDPz6bEVjXeAZwEqKq1JK+mWXRq1sNDW2n1/3Xeknw38AHgpqras/fykIdcxq9z+k7gTzc3GF0j9Y9pxuA+OqO6+n6N1qn1JXkz8DvALXMY951aY1W9UFWHqupoVR2lGbecZZhPrXHkT2h65yQ5RDME83TPavw74MSoxu8EXg1cnmGN05wFfmI02+WtwAtjQ629kOQI8EfAf6+qp/b0yWZ9RnhW/2jGnB8EPg98Avjm0eNLwAdG2+8Avgp8euzf98ygtpuBp2jG6989euxumtCB5k3zh8BF4C+A75jxsZtW3yeAvx87Zmfn8PpuW+OmtqvMeJZLy+MYmqGhC8BngNt6WONx4JM0M2A+DfyXGdf3EZrZZ1+l+YvmDuCngJ8aO4b3jur/zJxe52k1fgB4fuz9sr5XtfjVf0kaiCEPuUjSQjHQJWkgDHRJGggDXZIGwkCXpIEw0CVpIAx0SRqIfwWBVCV24nXHCAAAAABJRU5ErkJggg==\n",
"text/plain": [
"<Figure size 432x288 with 1 Axes>"
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"from matplotlib import pyplot as plt\n",
"plt.plot(coords_x, coords_y, 'r.')\n",
"plt.axis('equal')\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Approche exhaustive"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On utilise la distance euclidienne définie par $d(M_i, M_j) = \\sqrt{(x_j-x_i)^2+(y_j-y_i)^2}$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 1** Écrire une fonction `distance(i, j)` qui renvoie la distance entre les points $M_i$\n",
" et $M_j$. On utilisera la fonction `sqrt` après l’avoir importée."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [],
"source": [
"from math import sqrt\n",
"def distance(i, j):\n",
" return sqrt((coords_x[j] - coords_x[i])**2 + (coords_y[j] - coords_y[i])**2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 2** Rappeler sommairement comment sont stockés les flottants en mémoire. Quelle conséquence cela peut-il avoir sur le calcul de la distance ? On ignorera par la suite les problèmes d’approximation."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Les flottants permettent de représenter des (approximations de) nombres réels. Cette représentation s'appuie sur le fait qu'étant donné un entier $b>1$, tout nombre réel $x$ non nul peut s'écrire d'une unique façon sous la forme\n",
"$$ x = (-1)^s\\times b^e\\times m,$$\n",
"où\n",
"\n",
"* $s\\in\\{0, 1\\}$ précise le *signe* de $x$ ;\n",
"* $e\\in\\mathbb{Z}$ est un *exposant* donnant l'ordre de grandeur de $x$ dans la base $b$ ;\n",
"* $m\\in[1, b[$ est un réel appelé *mantisse*.\n",
"\n",
"Dans la pratique, par exemple dans la norme IEEE 754, la représentation des flottants se fait sur un nombre fixé de bits divisés en trois parties :\n",
"\n",
"* un bit pour le signe ;\n",
"* quelques bits pour l'exposant ;\n",
"* les bits restant pour la mantisse.\n",
"\n",
"Cette représentation a pour conséquences \n",
"\n",
"1. un nombre fini de réels peuvent être représentés (au maximum $2^n$ réels si $n$ est le nombre total de bits de la représentation) ;\n",
"2. pour la plupart des nombres réels la mantisse ne peut pas être écrite entièrement : il faut la tronquer ;\n",
"3. les opérations arithmétiques élémentaires sur les nombres flottants produisent des résultats mathématiquement faux, mais le plus souvent (heureusement) approximativement corrects."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 3** Écrire une fonction `plus_proche()` qui renvoie, à l’aide d’une recherche exhaustive, le couple d'entiers des indices $i$ et $j$ des deux points les plus proches du nuage de points."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [],
"source": [
"def plus_proche():\n",
" dmin = float('inf')\n",
" imin = jmin = -1\n",
" for i in range(n - 1):\n",
" for j in range(i + 1, n):\n",
" d = distance(i, j)\n",
" if d < dmin:\n",
" dmin, imin, jmin = d, i, j\n",
" return (imin, jmin)"
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Sur notre exemple de nuage de points, on obtient"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Indices des points les plus proches : 8 et 21\n",
"Point d'indice 8 : (0.371441, 0.322718)\n",
"Point d'indice 21 : (0.348858, 0.334010)\n",
"Distance de ces deux points : 0.025249\n"
]
}
],
"source": [
"i, j = plus_proche()\n",
"Mi, Mj = (coords_x[i], coords_y[i]), (coords_x[j], coords_y[j])\n",
"print('Indices des points les plus proches : {:d} et {:d}'.format(i, j))\n",
"print('Point d\\'indice {:d} : ({:f}, {:f})'.format(i, *Mi))\n",
"print('Point d\\'indice {:d} : ({:f}, {:f})'.format(j, *Mj))\n",
"print('Distance de ces deux points : {:f}'.format(distance(i, j)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 4** Donner, en la justifiant sommairement, la complexité de la fonction précédente en fonction de $n$."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Il y a un calcul de distance (ligne 6) et une comparaison de distances (ligne 7) au sein des deux boucles imbriquées, et il n'y en a pas ailleurs. Le nombre d'étapes de calcul est donc donné par\n",
"\n",
"$$\\sum_{i=0}^{n-2}\\sum_{j=i+1}^{n-1} 1 = \\sum_{i=0}^{n-2}(n-1-i) = \n",
" \\sum_{k=1}^{n-1} k = \\frac{n(n-1)}{2}.$$\n",
"\n",
"La complexité du calcul effectué par cette fonction est donc en $\\Theta(n^2)$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Quelques outils pour s’améliorer"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On souhaite maintenant obtenir la distance entre les deux points les plus proches avec une meilleure complexité. Pour cela nous allons décrire un algorithme utilisant une méthode de type *diviser pour régner*. Cette partie introduit des fonctions utiles pour la mise en œuvre de cet algorithme."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On se donne la fonction suivante :"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"def tri(liste):\n",
" n = len(liste)\n",
" for i in range(n):\n",
" pos = i\n",
" while pos > 0 and liste[pos] < liste[pos-1]:\n",
" liste[pos], liste[pos-1] = liste[pos-1], liste[pos]\n",
" pos -= 1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 5** Que renvoie cette fonction ? Que fait-elle ? Le démontrer soigneusement en exhibant un invariant de boucle."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"* Pas de `return` explicite dans cette fonction, elle renvoie donc `None`.\n",
"* En revanche, cette fonction peut échanger des éléments de cette liste (ligne 6). Elle peut donc modifier l'ordre des éléments de la liste.\n",
"* En fait, cette fonction trie les éléments de `liste` dans l'ordre croissant. Cela peut se démontrer avec la propriété « la tranche `liste[0:i+1]` est triée ». \n",
" * Cette propriété est vraie avant d'entrer dans la boucle `for` en considérant qu'alors $i=-1$ car alors la tranche est vide.\n",
" * Cette propriété est invariante à chaque itération. À l'étape $i$, si `liste[0:i]` est triée au début de l'étape, alors `liste[0:i+1]` est triée à la fin de cette étape.\n",
"* À la fin de la boucle, on a $i=n-1$ et la tranche `liste[0:n]`, autrement dit la liste complète est triée."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 6** Donner, en la démontrant, la complexité de la fonction `tri` en fonction de la taille de la liste donnée en paramètre."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"La complexité de cette fonction peut s'exprimer en comptant le nombre de fois que l'on compare deux éléments de la liste, ce qui n'arrive que dans la condition de la boucle `while` (ligne 5). \n",
"\n",
"Le nombre de comparaisons effectuées par la boucle `while` dépend de la liste, mais, pour $i>0$, il y a au minimum une comparaison et au maximum $i$ comparaisons. Pour $i=0$, il n'y a aucune comparaison.\n",
"\n",
"Le nombre total de comparaisons est donc au moins égal à\n",
"$$\\sum_{i=1}^{n-1} 1 = n-1,$$\n",
"et au plus égal à\n",
"$$\\sum_{i=1}^{n-1}i = \\frac{n(n-1)}{2}.$$\n",
"\n",
"Dans le pire des cas le nombre de comparaisons, et donc la complexité de cette fontion est en $O(n^2)$.\n",
"\n",
"**NB** l'algorithme de tri utilisé par cette fonction est connu sous le nom de tri par insertion."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 7** On souhaite trier une liste contenant des indices de points suivant l’ordre des abscisses croissantes. Que faudrait-il changer à la fonction `tri` ci-dessus pour qu’elle réalise cette opération ?"
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Si la liste contient les indices de points, et qu'on souhaite la trier par abscisses croissantes, il suffit de remplacer la comparaison \n",
" \n",
" liste[pos] < liste[pos-1]\n",
"par \n",
"\n",
" coords_x[liste[pos]] < coords_x[liste[pos-1]]. "
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [],
"source": [
"def tri(liste, coords):\n",
" n = len(liste)\n",
" for i in range(n):\n",
" pos = i\n",
" while pos > 0 and coords[liste[pos]] < coords[liste[pos-1]]:\n",
" liste[pos], liste[pos-1] = liste[pos-1], liste[pos]\n",
" pos -= 1"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[12, 19, 4, 2, 29, 24, 16, 11, 22, 26, 25, 6, 31, 21, 8, 13, 30, 23, 17, 27, 0, 20, 1, 15, 14, 3, 10, 18, 7, 5, 28, 9]\n",
"[3, 2, 7, 15, 6, 29, 25, 11, 19, 12, 8, 21, 1, 30, 24, 17, 26, 16, 23, 20, 9, 10, 28, 22, 5, 27, 18, 31, 13, 0, 4, 14]\n"
]
}
],
"source": [
"liste_x = list(range(n))\n",
"tri(liste_x, coords_x)\n",
"print(liste_x)\n",
"liste_y = list(range(n))\n",
"tri(liste_y, coords_y)\n",
"print(liste_y)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 8** Indiquer le nom d’un autre algorithme de tri plus efficace dans le pire des cas, ainsi que sa complexité. On ne demande pas de le programmer."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Un tri plus efficace dans le pire des cas est le tri fusion. Sa complexité dans le pire (et le meilleur) des cas est en $O(n\\log(n))$.\n",
"\n",
"**NB** le tri rapide est en $O(n\\log(n))$ en moyenne mais il est en $O(n^2)$ dans le pire des cas."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On admettra que l'on dispose de deux listes de $n$ entiers `liste_x` (resp. `liste_y`) contenant les indices des points du nuage triés par abscisses croissantes (resp. par ordonnées croissantes). On supposera désormais que deux points quelconques ont des abscisses et des ordonnées distinctes."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Dans toute la suite, un sous-ensemble de points sera décrit par un *cluster*. Un cluster est une matrice de deux lignes contenant chacune les mêmes numéros correspondant aux numéros des points dans le sous-ensemble considéré. Dans la première ligne, les points sont triés par abscisses croissantes ; dans la seconde, ils sont triés par ordonnées croissantes. La figure 1 donne la représentation de deux clusters.\n",
"\n",
"![Représentation en Python de deux clusters](clusters.png)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"tags": [
"hors_enonce"
]
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[12, 19, 4, 2, 29, 24, 16, 11, 22, 26, 25, 6, 31, 21, 8, 13, 30, 23, 17, 27, 0, 20, 1, 15, 14, 3, 10, 18, 7, 5, 28, 9], [3, 2, 7, 15, 6, 29, 25, 11, 19, 12, 8, 21, 1, 30, 24, 17, 26, 16, 23, 20, 9, 10, 28, 22, 5, 27, 18, 31, 13, 0, 4, 14]]\n"
]
}
],
"source": [
"cluster = [liste_x, liste_y]\n",
"print(cluster)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Pour être efficace, notre algorithme ne doit pas retrier les listes des indices de points à chaque étape. Nous allons donc définir une fonction qui permet d’extraire des indices d’un cluster et former ainsi un nouveau cluster plus petit."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 9** Écrire une fonction `sous_cluster(cl, x_min, x_max)` qui prend en arguments un cluster `cl` et deux flottants `x_min` et `x_max`, et renvoie le sous-cluster des points dont l’abscisse est comprise entre `x_min` et `x_max` (au sens large). Cette fonction doit avoir une complexité linéaire en la taille du cluster."
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [],
"source": [
"def sous_cluster(cl, xmin, xmax):\n",
" n = len(cl[0])\n",
" premiere_ligne = []\n",
" i = 0\n",
" while i < n and coords_x[cl[0][i]] <= xmax:\n",
" if xmin <= coords_x[cl[0][i]]:\n",
" premiere_ligne.append(cl[0][i])\n",
" i += 1\n",
" deuxieme_ligne = [j for j in cl[1] if j in premiere_ligne]\n",
" return [premiere_ligne, deuxieme_ligne]"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[22, 26, 25, 6, 31, 21, 8, 13, 30, 23, 17, 27, 0, 20, 1, 15, 14, 3, 10], [3, 15, 6, 25, 8, 21, 1, 30, 17, 26, 23, 20, 10, 22, 27, 31, 13, 0, 14]]\n"
]
}
],
"source": [
"print(sous_cluster(cluster, 0.25, 0.75))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 10** Écrire une fonction `mediane(cl)` qui prend en entrée un cluster `cl` contenant au moins 2 points et renvoie une abscisse médiane, c’est-à-dire que la moitié (au moins) des points a une abscisse inférieure ou égale à cette valeur, et la moitié (au moins) des points a une abscisse supérieure ou égale à cette valeur. Cette fonction doit avoir une complexité en $O(1)$."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [],
"source": [
"def mediane(cl):\n",
" n = len(cl[0])\n",
" return (coords_x[cl[0][(n - 1) // 2]] + coords_x[cl[0][n // 2]]) / 2"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.4233770483817454"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"mediane(cluster)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Méthode sophistiquée"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Le fonctionnement de l'algorithme utilisant une méthode de type *diviser pour régner* est illustré par la figure 2 :\n",
"\n",
"1. Si le cluster contient deux ou trois points, on calcule la distance minimale en calculant toutes les distances possibles.\n",
"2. Sinon, on sépare le cluster en deux parties $G$ et $D$ qu'on supposera de tailles égales (éventuellement à un point près) suivant la médiane des abscisses, qu’on notera $x_0$.\n",
"3. Les deux points les plus proches sont soit tous les deux dans $G$, soit tous les deux dans $D$, soit un dans $G$ et un dans $D$.\n",
"4. On calcule récursivement le couple le plus proche dans $G$ et le couple le plus proche dans $D$. On note $d_0$ la plus petite des deux distances obtenues.\n",
"5. On cherche s’il existe une paire de points $(M_1, M_2)$ telle que $M_1$ est dans $G$, $M_2$ dans $D$, et $d(M_1, M_2)< d_0$.\n",
"6. Si on en trouve une (ou plusieurs), on renvoie la plus petite de ces distances. Sinon, on renvoie $d_0$.\n",
"\n",
"![Illustration de la méthode diviser pour régner](points_proches_diviser_regner.png)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 11** Écrire une fonction `gauche(cl)` qui prend en argument un cluster `cl` contenant au moins deux points et renvoie le cluster constitué uniquement de la moitié (éventuellement arrondie à l’entier supérieur) des points les plus à gauche du cluster `cl`."
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [],
"source": [
"def gauche(cl):\n",
" x0 = mediane(cl)\n",
" return sous_cluster(cl, coords_x[cl[0][0]], x0)"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[12, 19, 4, 2, 29, 24, 16, 11, 22, 26, 25, 6, 31, 21, 8, 13], [2, 6, 29, 25, 11, 19, 12, 8, 21, 24, 26, 16, 22, 31, 13, 4]]\n"
]
}
],
"source": [
"print(gauche(cluster))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On suppose qu'on dispose d'une fonction `droite(cl)` qui renvoie le cluster contenant tous les autres points du cluster `cl` n'appartenant pas au cluster renvoyé par la fonction `gauche(cl)`."
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"tags": [
"hors_enonce"
]
},
"outputs": [],
"source": [
"def droite(cl):\n",
" x0 = mediane(cl)\n",
" return sous_cluster(cl, x0, coords_x[cl[0][-1]])"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[30, 23, 17, 27, 0, 20, 1, 15, 14, 3, 10, 18, 7, 5, 28, 9], [3, 7, 15, 1, 30, 17, 23, 20, 9, 10, 28, 5, 27, 18, 0, 14]]\n"
]
}
],
"source": [
"print(droite(cluster))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 12** Justifier que l'on peut se contenter de chercher les points $M_1$ et $M_2$ de l'étape 5 de l'algorithme dans l'ensemble des points dont l'abscisse appartient à $I_0= [x_0-d_0, x_0+d_0]$."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Si $d_0$ est la plus petite des deux distances séparant les deux points les plus proches de la partie gauche du cluster d'une part et les deux points les plus proches de la partie droite d'autre part, alors si dans la bande centrale on trouve deux points à distance strictement inférieure à $d_0$, alors l'un, $M_1$, est nécessairement dans la partie gauche, et l'autre, $M_2$, dans la partie droite (sinon cela contredirait la définition de $d_0$).\n",
"\n",
"Par ailleurs, l'abscisse $x_1$ de $M_1$ ne peut pas être strictement inférieure à $x_0-d_0$ et celle $x_2$ de $M_2$ ne peut pas être strictement supérieure à $x_0+d_0$ car dans le cas contraire on aurait $d(M_1, M_2) > d_0$.\n",
"\n",
"Cela justifie donc qu'il suffit de rechercher l'éventuelle présence d'un couple de points proches dans la bande des points d'abscisse appartenant à l'intervalle $[x_0-d_0, x_0+d_0]$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 13** Écrire une fonction `bande_centrale(cl, d0)` qui prend en argument un cluster `cl` et un réel `d0`, et renvoie le cluster des points dont l'abscisse est dans $I_0$. Cette fonction doit avoir une complexité linéaire en la taille du cluster."
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [],
"source": [
"def bande_centrale(cl, d0):\n",
" x0 = mediane(cl)\n",
" return sous_cluster(cl, x0-d0, x0+d0)"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[22, 26, 25, 6, 31, 21, 8, 13, 30, 23, 17, 27, 0, 20, 1, 15, 14], [15, 6, 25, 8, 21, 1, 30, 17, 26, 23, 20, 22, 27, 31, 13, 0, 14]]\n"
]
}
],
"source": [
"print(bande_centrale(cluster, 0.2))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 14** Montrer que deux points $M_1$ et $M_2$ (de l’étape 5 de l'algorithme) situés à une distance inférieure à $d_0$ se trouvent, dans la deuxième ligne du cluster (c'est-à-dire la ligne triée par ordonnées croissantes), séparés d'au plus 6 éléments. \n",
"\n",
"On pourra montrer par l'absurde qu'un rectangle, à préciser, de dimensions $2d_0\\times d_0$ contient au plus 8 points."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Commençons par montrer que dans un carré de côté $c$ il ne peut y avoir qu'au plus quatre points séparés d'une distance au moins égale à $c$.\n",
"\n",
"Supposons qu'on ait cinq points $M_i$, $i=1,..., 5$, tels que pour tout couple $(i, j)\\in [1, 5]^2$, avec $i\\neq j$ on ait\n",
"$$ d(M_i, M_j) \\geq c.$$\n",
"\n",
"Alors en coupant le carré selon une ligne médiane pour obtenir deux rectangles de dimension $c\\times \\frac{c}{2}$, l'un de ces deux rectangles doit contenir au moins trois des cinq points $M_i$. Et en coupant ce rectangle en deux selon une ligne médiane pour obtenir deux carrés de côtés $\\frac{c}{2}$, l'un des deux carrés doit contenir au moins deux points.\n",
"\n",
"Or dans un carré de côté $\\frac{c}{2}$ tout couple de points est à distance au moins égale à $\\frac{c\\sqrt{2}}{2} < c$. Ceci contredit que les cinq points sont à distance au moins égale à $c$. Ce qui établit le fait que dans un carré de côté $c$, on ne peut considérer qu'au maximum quatre points à distance au moins égale à $c$. (Ce qui est possible en considérant les quatre sommets du carré).\n",
"\n",
"Soit $y$ un réel quelconque. Considérons un rectangle $[x_0 - d_0; x_0+d_0]\\times[y; y+d_0]$ situé dans la bande centrée en la médiane $x_0$ du cluster et de largeur $2d_0$, $d_0$ étant la plus petite des deux distances séparant les points les plus proches situés dans le sous-cluster gauche, et les points les plus proches situés dans le sous-cluster droit.\n",
"\n",
"Les points du cluster situés dans partie gauche de ce rectangle, c'est-à dire dans le carré $[x_0-d_0; x_0]\\times [y; y+d_0]$ de côté $d_0$ sont tous à distance au moins égale à $d_0$ les uns des autres. Ils sont donc en nombre au plus égal à quatre. De même pour les points du cluster situés dans la partie droite. Par conséquent le rectangle ne contient qu'au plus huit points du rectangle. (Cette majoration doit pouvoir certainement être améliorée.)\n",
"\n",
"S'ils existent les deux points de la bande centrale à distance dtrictement inférieure à $d_0$ sont situés dans un rectangle de la forme $[x_0 - d_0; x_0+d_0]\\times[y; y+d_0]$ qui ne contient qu'au maximum huit points du cluster. Comme la deuxième ligne est triée par ordre croissant des ordonnées, il y a au maximum six points entre ces deux points."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 15** En déduire une fonction `fusion(cl, d0)` qui prend en entrée un cluster de points dont toutes les abscisses sont dans un intervalle $[x_0-d_0, x_0+d_0]$, et renvoie la distance minimale entre deux points du cluster si elle est inférieure à $d_0$, ou $d_0$ sinon. Cette fonction doit avoir une complexité linéaire en la taille du cluster `cl`. Vous justifierez cette complexité."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Compte-tenu du fait établi dans la question précédente, pour rechercher les deux points $M_1$ et $M_2$ les plus proches dans une bande centrale, il suffit de les rechercher par ordonnées croissantes, et pour une ordonnée fixée, calculer les distances avec les sept points qui suivent dans l'ordre des ordonnées."
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [],
"source": [
"def fusion(cl, d0):\n",
" n = len(cl[1])\n",
" dmin = d0\n",
" for i in range(n - 1):\n",
" for j in range(i+1, min(n, i+8)):\n",
" dist = distance(cl[1][i], cl[1][j])\n",
" if dist < dmin:\n",
" dmin = dist\n",
" return dmin"
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"La complexité de cette fonction est essentiellement proportionnelle au nombre de fois que les instructions des lignes 6 à 8 sont exécutées, autrement dit au nombre de calculs de distance. Et ce nombre de calculs de distance est égal à\n",
"\n",
"$$ \\sum_{i=0}^{n-2}\\sum_{j=i+1}^{\\min(n-1,i+7)}1 = (\\sum_{i=0}^{n-8}7) + (6 + 5 + 4 + 3 + 2 + 1) =7(n-7) + 21 = 7n - 28.$$\n",
"\n",
"Ceci établit que la complexité de la fonction est en $\\Theta(n)$, et donc qu'elle est linéaire."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 16** Écrire une fonction récursive `distance_minimale(cl)` qui prend en argument un cluster et utilise l'algorithme décrit plus haut pour renvoyer la distance minimale entre deux points du cluster."
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [],
"source": [
"def distance_minimale(cl):\n",
" n = len(cl[0])\n",
" if n == 2:\n",
" return distance(cl[0][0], cl[0][1])\n",
" else:\n",
" x0 = mediane(cl)\n",
" gauche = sous_cluster(cl, coords_x[cl[0][0]], x0)\n",
" droite = sous_cluster(cl, x0, coords_x[cl[0][-1]])\n",
" d0 = min(distance_minimale(gauche),\n",
" distance_minimale(droite))\n",
" d1 = fusion(sous_cluster(cl, x0-d0, x0+d0), d0)\n",
" return d1"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [
{
"data": {
"text/plain": [
"0.025248772056030447"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"distance_minimale(cluster)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Remarque :** dans la réalisation de cette fonction, nous n'avons pas utilisé les fonctions déterminant les parties gauche et droite, ainsi que la bande centrale du cluster, car chacune de ces trois fonctions effectue le calcul de la médiane. Notre réalisation n'effectue qu'un seul calcul de médiane."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 17** Si on note $n$ la taille du cluster `cl`, et $C(n)$ le nombre d'opérations élémentaires réalisées par la fonction `distance_minimale(cl)`, justifier que l'on a :\n",
"\n",
"$$ C(n) = 2C(n/2) +O(n).$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Lorsque $n>2$, le nombre $C(n)$ d'opérations élémentaires est égal au nombre d'opérations élémentaires pour chaque appel récursif, qui s'effectue sur des clusters ayant deux fois moins de points, soit $C(n/2)$ pour chacun d'eux, auxquelx il faut ajouter le nombre d'opérations élémentaires pour le calcul de la médiane, le calcul des sous-clusters gauche et droite et la bande centrale, et le calcul de la fusion, chacune de ces étapes s'effectuant avec une complexité linéaire, donc $\\Theta(n)$ opérations supplémentaires au total.\n",
"Ainsi on a pour $n>2$\n",
"\n",
"$$C(n) = 2C(n/2) + \\Theta(n).$$\n",
"\n",
"Pour $n=2$, le seul calcul est un calcul de distance, donc en $\\Theta(1)$.\n",
"\n",
"$$C(2) = \\Theta(1).$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 18** En déduire, en la démontrant, la complexité $C(n)$. On pourra se limiter au cas où $n$ est une puissance de 2."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Si on se limite au cas où $n$ est une puissance de deux, alors en posant $n=2^p$ et $c'(p) = C(n)$, les équations précédentes deviennent\n",
"\n",
"$$ c'(p) = 2c(p-1) + \\Theta(2^p),$$\n",
"et\n",
"$$ c'(1) = \\Theta(1).$$\n",
"\n",
"On reconnaît l'équation de récurrence d'une suite récurrente linéaire du 1er ordre, de raison 2 et de second membre $O(2^p)$. Comme ce second membre s'exprime avec une puissance de la raison, la solution de ces équations est donc de la forme\n",
"\n",
"$$c'(p) = \\Theta(p2^p).$$\n",
"\n",
"D'où l'on deduit que, lorsque $n$ est une puissance de deux,\n",
"\n",
"$$C(n) = \\Theta(n\\log(n)).$$\n",
"\n",
"On admet que cela est vrai aussi pour $n$ quelconque. La complexité est donc d'un ordre de grandeur bien inférieur à celui de l'approche exhaustive."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"hors_enonce"
]
},
"source": [
"**Vérification expérimentale des résultats établis**"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"tags": [
"hors_enonce"
]
},
"outputs": [],
"source": [
"from ap2_decorators import count\n",
"distance = count(distance)"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"tags": [
"hors_enonce"
]
},
"outputs": [],
"source": [
"N = 200\n",
"meth1 = []\n",
"meth2 = []\n",
"for n in range(2, N):\n",
" coords_x = [random() for _ in range(n)]\n",
" coords_y = [random() for _ in range(n)]\n",
" distance.counter = 0\n",
" _ = plus_proche()\n",
" meth1.append(distance.counter)\n",
" liste_x = list(range(n))\n",
" tri(liste_x, coords_x)\n",
" liste_y = list(range(n))\n",
" tri(liste_y, coords_y)\n",
" cluster = [liste_x, liste_y]\n",
" distance.counter = 0\n",
" _= distance_minimale(cluster)\n",
" meth2.append(distance.counter)"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"tags": [
"hors_enonce"
]
},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAYMAAAD4CAYAAAAO9oqkAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAAra0lEQVR4nO3de3RV5Z3/8ff3HG7eGC6iUoEBW3AqooCpii0VKypip6gz09rpGlCpqEB/47K/1er0Z3W0s+rUVh1bhxqLVrqsl44j0gq1yDLajkENF1HxArYoYbg1WvEGIcn398fe+7Bzck5ykpzk3D6vtbJyznP22efJTvJ89/N9nv1sc3dERKSyJQpdARERKTwFAxERUTAQEREFAxERQcFARESAPoWuQFcdfvjhPnr06EJXQ0SkpKxZs+bP7j4svbxkg8Ho0aOpq6srdDVEREqKmb2VqVxpIhERUTAQEZEcgoGZjTSzp8xso5m9Ymb/HJYPMbOVZrYp/D44LDczu8PMNpvZBjObHNvXnHD7TWY2J1Z+kpm9FL7nDjOznvhhRUQks1zGDJqAb7r7WjM7DFhjZiuBi4FV7n6zmV0DXAN8GzgXGBt+nQIsAk4xsyHA9UAV4OF+lrn7u+E2lwHPAcuBGcCKzv4w+/fvp76+nr1793b2rZKjAQMGMGLECPr27VvoqohIHnUYDNx9O7A9fPy+mb0KHA3MAqaFm90H1BAEg1nAEg8WPVptZoPMbHi47Up3fwcgDCgzzKwGGOjuq8PyJcD5dCEY1NfXc9hhhzF69GjUucg/d6ehoYH6+nrGjBlT6OqISB51aszAzEYDkwjO4I8MAwXADuDI8PHRwNbY2+rDsvbK6zOUZ/r8eWZWZ2Z1u3fvbvP63r17GTp0qAJBDzEzhg4dqp6XSBnKORiY2aHAI8BV7r4n/lrYC+jx5U/dvdrdq9y9atiwNtNko3r2dDUqmo6vSAHV1sL3vx98z7OcgoGZ9SUIBPe7+3+HxTvD9A/h911h+TZgZOztI8Ky9spHZCivCHfddRfvvvtuoashIsWuthbOPBOuuy74nueAkMtsIgMWA6+6+62xl5YB0YygOcBjsfLZ4ayiU4H3wnTSE8DZZjY4nHl0NvBE+NoeMzs1/KzZsX2VtRtvvJHBgwczePBgANavX8/y5ctTr99www388Ic/7PL+O/v+1157jSlTptC/f/9ufa6I9IAlS2DvXmhuhsZGqKnJ6+5zmU30WeCfgJfMbH1Y9i/AzcDDZjYXeAv4cvjacmAmsBn4CLgEwN3fMbObgBfC7W6MBpOB+cDPgYMIBo47PXhcir773e+2er5+/Xrq6uqYOXNmQeozZMgQ7rjjDpYuXVqQzxeRLGpr4Z57ILoZWZ8+MG1aXj+iw56Bu//B3c3dT3D3ieHXcndvcPcz3X2su0+PGnYPLHD3T7r7BHevi+3rHnf/VPh1b6y8zt2PD9+z0Hvz9mt5zMFt2bKFv/mbv+Hiiy9m3LhxfO1rX+PJJ5/ks5/9LGPHjuX5558H4MMPP+TSSy/l5JNPZtKkSTz22GM0Njby3e9+l4ceeoiJEyfy0EMPAbBx40amTZvGMcccwx133JH6rFtvvZXjjz+e448/nttvvz1V/m//9m+MGzeOz33uc7z++uup8jfffJMZM2Zw0kknMXXqVF577bU29T/iiCP4zGc+o2mjIsWkthZuuAGamoLnZnDJJTBlSn4/x91L8uukk07ydBs3bmxT1q5nn3U/6CD3ZDL4/uyznXt/mj/96U+eTCZ9w4YN3tzc7JMnT/ZLLrnEW1pafOnSpT5r1ix3d7/22mv9F7/4hbu7v/vuuz527Fj/4IMP/N577/UFCxak9nf99df7lClTfO/evb57924fMmSINzY2el1dnR9//PH+wQcf+Pvvv+/HHXecr127NlX+4Ycf+nvvveef/OQn/ZZbbnF39y984Qv+xhtvuLv76tWr/Ywzzsj6c1x//fWp92XS6eMsIl0TtVGJhDsE37vZVgF1nqFNLdmF6vKipibIvcVzcN2MtmPGjGHChAkAjB8/njPPPBMzY8KECWzZsgWA3/3udyxbtiyVl9+7dy9vv/12xv2dd9559O/fn/79+3PEEUewc+dO/vCHP3DBBRdwyCGHAHDhhRfy+9//npaWFi644AIOPvhgAL70pS8B8MEHH/Dss8/yD//wD6n97tu3r1s/p4j0gmicwB0SCZg+Pegl5LtXQAmvWpoX06ZBv35BIOjXLy85uP79+6ceJxKJ1PNEIkFT2M1zdx555BGOPfbYVu997rnn2t1fMplM7aMzWlpaGDRoEOvXr+/0e0WkQNLHCfr27bFAAJW+UN2UKbBqFdx0U/C9hw5yunPOOYcf//jHePhLXrduHQCHHXYY77//fofvnzp1KkuXLuWjjz7iww8/5NFHH2Xq1Kl8/vOfZ+nSpXz88ce8//77/PrXvwZg4MCBjBkzhl/96ldAEIxefPHFHvrpRKTbemucIKayewYQHNxeCgKR6667jquuuooTTjiBlpYWxowZw29+8xvOOOMMbr75ZiZOnMi1116b9f2TJ0/m4osv5uSTTwbg61//OpMmTQLgK1/5CieeeGJqMDhy//33c+WVV/K9732P/fv3c9FFF3HiiSe22u+OHTuoqqpiz549JBIJbr/9djZu3MjAgQN74CiISEbR9QT79kFLS5Ae6t8fZs/u0Y+16Oy01FRVVXn6zW1effVVPv3pTxeoRpVDx1mkB115Jdx1V4+NE5jZGnevSi+v7DSRiEgx6eVxgjgFAxGRYlCAcYI4jRmIiBRagcYJ4tQzEBEptOh6gigQTJ/eqzMcQcFARKSwCjhOEKdgUGBawlqkghV4nCBOwaCAim0J6/vvv58TTjiBCRMmcNppp+nCNJGeFI0TPPnkgfTQgAG9Ok4QpwHkAiq2JazHjBnD008/zeDBg1mxYgXz5s3LuESGiORBL647lIuK7xnUbq3l+7//PrVbtYT1aaedluqlnHrqqdTX17fZRkTyoEjGCVrJtJRpKXzlYwnrZ99+1g/63kGe/NekH/S9g/zZt7WEdeSWW27xuXPnZnxNS1iLdMOzz7qfffaBZanN3K+4otc+nq4uYW1m9wBfBHa5+/Fh2UNAtOTmIOAv7j7RzEYDrwLRKelqd78ifM9JHLib2XLgn93dzWwI8BAwGtgCfNnde2VEtWZLDY3NjTR7M43NjdRsqWHKSC1h/dRTT7F48WL+8Ic/dOtYiEiaIrieIJtcxgx+DvwEWBIVuPtXosdm9iPgvdj2b7r7xAz7WQRcBjxHEAxmENze8hpglbvfbGbXhM+/3amfooumjZ5Gv2Q/Gpsb6Zfsx7TR07q9z1JfwnrDhg18/etfZ8WKFQwdOrTTnyUiWUQzh+KBoMDjBHG53PbyGeCdTK+FN7D/MvBAe/sws+HAQHdfHXZTlgDnhy/PAu4LH98XK+9xU0ZOYdXsVdx0xk2smr2q272CXBXrEtZvv/02F154Ib/4xS8YN25cvn5cEamuhtNPh5UrW/cIiiQQQPcHkKcCO919U6xsjJmtM7OnzWxqWHY0EB+NrA/LAI509+3h4x3Akdk+zMzmmVmdmdXt3r27m1UPTBk5hWunXttrgQCCJaz379/PCSecwPjx47nuuusAOOOMM9i4cWOrAeRM4ktYn3LKKaklrCdPnpxawvrcc89ts4T14sWLOfHEExk/fjyPPfZYm/3eeOONNDQ0MH/+fCZOnEhVVZuFDUWks2prYcEC2L8/GDA2K8gVxh3JaQnrcCzgN9GYQax8EbDZ3X8UPu8PHOruDeEYwVJgPDAOuNndp4fbTQW+7e5fNLO/uPug2D7fdffBHdVJS1gXjo6zSI6i1NDKla1nDj39dMECQbYlrLt8nYGZ9QEuBE6Kytx9H7AvfLzGzN4kCATbgBGxt48IywB2mtlwd98eppN2dbVOIiJFIz5YHPUIkkn4yU+KqkcQ6U6aaDrwmrun0j9mNszMkuHjY4CxwB/DNNAeMzs1HGeYDUR5imXAnPDxnFi5iEjpSl987qyz4JlnYN68Qtcsow6DgZk9ANQCx5pZvZnNDV+6iLYDx58HNpjZeuC/gCvcPRp8ng/8DNgMvEkwkwjgZuAsM9tEEGBu7vqPA7mkvaTrdHxFclCMF5V1oMM0kbt/NUv5xRnKHgEeybJ9HXB8hvIG4MyO6pGLAQMG0NDQwNChQwk6IJJP7k5DQwMDBgwodFVEilcRLT7XGWW1NtGIESOor68nXzONpK0BAwYwYsSIjjcUqURFfFFZR8oqGPTt25cxY8YUuhoiUqmKbPG5zqj4hepERPKiBMcJ4hQMRES6q0THCeLKKk0kItLrqqth4cIgEETpoRIZJ4hTz0BEpKtKZKmJXCgYiIh0RZQaam4+UNanT0mNE8QpTSQi0lklttRELtQzEBHprBJbaiIXCgYiIp1R4lNIs1EwEBHJVRlMIc1GYwYiIrko4aUmcqGegYhIR7Ldv7gEp5Bmo56BiEh7sl1UVgbjBHHqGYiIZFNGF5V1RMFARCSTMruorCO53OnsHjPbZWYvx8puMLNtZrY+/JoZe+1aM9tsZq+b2Tmx8hlh2WYzuyZWPsbMngvLHzKzfvn8AUVEOi0aLH7yyQM9gj59Svqiso7k0jP4OTAjQ/lt7j4x/FoOYGbHEdwOc3z4nv80s2R4X+Q7gXOB44CvhtsC/Hu4r08B7wJz0z9IRKRXleFFZR3pMBi4+zPAOx1tF5oFPOju+9z9TwT3Oz45/Nrs7n9090bgQWCWBfem/ALB/ZIB7gPO79yPICKSR2V6UVlHujNmsNDMNoRppMFh2dHA1tg29WFZtvKhwF/cvSmtPCMzm2dmdWZWp1tbikjelfFFZR3pajBYBHwSmAhsB36Urwq1x92r3b3K3auGDRvWGx8pIpWiuhpOPx1WrjyQHhowoGwuKutIl4KBu+9092Z3bwHuJkgDAWwDRsY2HRGWZStvAAaZWZ+0chGR3lNBU0iz6VIwMLPhsacXANFMo2XARWbW38zGAGOB54EXgLHhzKF+BIPMy9zdgaeAvw/fPwd4rCt1EhHpkgqbQppNh1cgm9kDwDTgcDOrB64HppnZRMCBLcDlAO7+ipk9DGwEmoAF7t4c7mch8ASQBO5x91fCj/g28KCZfQ9YByzO1w8nItKuMrwvQVeZRyPmJaaqqsrr6uoKXQ0RKWVXXgl33XVgmYnp08u+R2Bma9y9Kr1caxOJSOWprQ2uJVi8uOKmkGajYCAilSVKDe3deyAQVNAU0my0NpGIVJbo6uJ4IKigKaTZKBiISOXIdHXx5ZdX1BTSbJQmEpHKkOnq4rlzYdGiglarWCgYiEj5K/NbVuaD0kQiUt4q4JaV+aCegYiUrwq5ZWU+qGcgIuVJ6w11ioKBiJQfrTfUaUoTiUh5SU8NVfB6Q52hnoGIlI9MqaEKuGVlPigYiEh5UGqoW5QmEpHSp6Wou009AxEpfdF6Q9F1BEoNdZp6BiJSurQUdd502DMws3vMbJeZvRwru8XMXjOzDWb2qJkNCstHm9nHZrY+/Ppp7D0nmdlLZrbZzO4wMwvLh5jZSjPbFH4f3AM/p4iUmyg1dNddwYAxaCnqbsglTfRzYEZa2UrgeHc/AXgDuDb22pvuPjH8uiJWvgi4jOC+yGNj+7wGWOXuY4FV4XMRkfZpKeq86jAYuPszwDtpZb9z93DpP1YDI9rbh5kNBwa6+2oP7rO5BDg/fHkWcF/4+L5YuYhIW7W1we0q01NDWoq6W/IxZnAp8FDs+RgzWwfsAf6fu/8eOBqoj21TH5YBHOnu28PHO4Ajs32Qmc0D5gGMGjUqD1UXkZKS7S5lWoq627o1m8jMvgM0AfeHRduBUe4+Cbga+KWZDcx1f2Gvwdt5vdrdq9y9atiwYd2ouYiUJKWGekyXg4GZXQx8Efha2Ijj7vvcvSF8vAZ4ExgHbKN1KmlEWAawM0wjRemkXV2tk4iUMd2lrEd1KRiY2QzgW8CX3P2jWPkwM0uGj48hGCj+Y5gG2mNmp4aziGYDj4VvWwbMCR/PiZWLiATau0uZAkFedDhmYGYPANOAw82sHrieYPZQf2BlOEN0dThz6PPAjWa2H2gBrnD3aPB5PsHMpIOAFeEXwM3Aw2Y2F3gL+HJefjIRKX3RdQT33htMH9VdynqMuWdN0Re1qqoqr6urK3Q1RKSnZBosju5SpovKuszM1rh7VXq5lqMQkeKUabBYdynrMQoGIlJcdB1BQWhtIhEpHrqOoGDUMxCR4qHrCApGwUBECk+poYJTmkhECkupoaKgnoGIFJZSQ0VBwUBECkOpoaKiNJGI9D6lhoqOegYi0vuUGio6CgYi0nuUGipaShOJSO9QaqioqWcgIr1DqaGipmAgIj1LqaGSoDSRiPQcpYZKhnoGItIzoruT7dun1FAJyCkYmNk9ZrbLzF6OlQ0xs5Vmtin8PjgsNzO7w8w2m9kGM5sce8+ccPtNZjYnVn6Smb0UvueO8NaYIlKqqqvh9NNh5coDdyfr10+poSKWa8/g58CMtLJrgFXuPhZYFT4HOJfg3sdjgXnAIgiCB8EtM08BTgaujwJIuM1lsfelf5aIlIJofGD+/OA2le5Bb2D6dKip0T2Li1hOYwbu/oyZjU4rnkVwb2SA+4Aa4Nth+RIP7qe52swGmdnwcNuV0T2RzWwlMMPMaoCB7r46LF8CnM+BeySLSCnIND4A0KeP7k5WArozZnCku28PH+8AjgwfHw1sjW1XH5a1V16foVxESkn61FEIAsFPfqJAUALyMpvI3d3MvOMtu8fM5hGknhg1alRPf5yI5KK2NggE6VNH584NBooVCEpCd4LBTjMb7u7bwzTQrrB8GzAytt2IsGwbB9JKUXlNWD4iw/ZtuHs1UA1QVVXV48FHRDqgqaNloztpomVANCNoDvBYrHx2OKvoVOC9MJ30BHC2mQ0OB47PBp4IX9tjZqeGs4hmx/YlIsVMVxWXjZx6Bmb2AMFZ/eFmVk8wK+hm4GEzmwu8BXw53Hw5MBPYDHwEXALg7u+Y2U3AC+F2N0aDycB8ghlLBxEMHGvwWKSYKTVUdsy9NLMtVVVVXldXV+hqiFSe6mpYuBCamlr3CC6/XKmhEmBma9y9Kr1cy1GISO5qa2HBgiAQRJQaKgtajkJEchMtL9HcfKAsmdRVxWVCPQMR6Vh6asgsCAR33gnz5hW6dpIH6hmISPui1FB8eYmzzoJnnlEgKCMKBiKSXabUkJaXKEtKE4lIW9HU0Xvvbd0jSCa1vESZUjAQkdYyTR1NJIKVR9UjKFsKBiISiHoDd9/dOi1kBv37KxCUOQUDEcm+/HQyCZddpquKK4CCgYhkX35aU0crhoKBSCXTGkMSUjAQqVTZ1hjS8tMVScFApBJpjSFJo4vORCqN1hiSDNQzEKkkWmNIslDPQKQS1NbClVfC/PlaY0gyUs9ApNxlGigGrTEkrXS5Z2Bmx5rZ+tjXHjO7ysxuMLNtsfKZsfdca2abzex1MzsnVj4jLNtsZtd094cSkVD6iqORPn20xpC00uWegbu/DkwEMLMksA14lOCex7e5+w/j25vZccBFwHjgE8CTZjYufPlO4CygHnjBzJa5+8au1k1EyD5QrCuKJYN8pYnOBN5097fMLNs2s4AH3X0f8Ccz2wycHL622d3/CGBmD4bbKhiIdEV7K45qoFiyyNcA8kXAA7HnC81sg5ndY2aDw7Kjga2xberDsmzlbZjZPDOrM7O63bt356nqImWkuhpOPx3uugv27YOWlmDFUQ0USwe6HQzMrB/wJeBXYdEi4JMEKaTtwI+6+xkRd6929yp3rxo2bFi+ditS+jLNFgKtOCo5y0ea6FxgrbvvBIi+A5jZ3cBvwqfbgJGx940Iy2inXEQ6km22kMYHpBPyEQy+SixFZGbD3X17+PQC4OXw8TLgl2Z2K8EA8ljgecCAsWY2hiAIXAT8Yx7qJVL+Mi0rAVpxVDqtW8HAzA4hmAV0eaz4B2Y2EXBgS/Sau79iZg8TDAw3AQvcvTncz0LgCSAJ3OPur3SnXiIVQbOFJI/M493KElJVVeV1dXWFroZIYWhZCekiM1vj7lXp5VqOQqSUaFkJ6SFajkKkVGhZCelBCgYixS7bjepBy0pI3igYiBQzTRuVXqJgIFKsNG1UepGCgUgx0rRR6WUKBiLFRIvMSYEoGIgUi0zjA4kETJ+u2ULS4xQMRAot22whLTInvUjBQKSQNFtIioSCgUghdHTtgMYHpJcpGIj0NvUGpAgpGIj0FvUGpIgpGIj0BvUGpMgpGIj0JPUGpEQoGIj0FPUGpIR0+34GZrbFzF4ys/VmVheWDTGzlWa2Kfw+OCw3M7vDzDab2QYzmxzbz5xw+01mNqe79RIpmGw3p4egN/Cf/wmLFikQSFHJV8/gDHf/c+z5NcAqd7/ZzK4Jn38bOJfg3sdjgVOARcApZjYEuB6oIrhd5hozW+bu7+apfiI9L76URGOjegNSUnoqTTQLmBY+vg+oIQgGs4AlHtxrc7WZDTKz4eG2K939HQAzWwnMAB7oofqJ5Fe2lBBobEBKQj6CgQO/MzMH7nL3auBId98evr4DODJ8fDSwNfbe+rAsW3krZjYPmAcwatSoPFRdpJvaW0qib1+49FL1BqQk5CMYfM7dt5nZEcBKM3st/qK7exgoui0MNNUAVVVVedmnSJdpgFjKSLeDgbtvC7/vMrNHgZOBnWY23N23h2mgXeHm24CRsbePCMu2cSCtFJXXdLduIj1C00WlDHVrNpGZHWJmh0WPgbOBl4FlQDQjaA7wWPh4GTA7nFV0KvBemE56AjjbzAaHM4/ODstEikt1NZx+Otx1V9sbz1xxBTzzjAKBlKTu9gyOBB41s2hfv3T335rZC8DDZjYXeAv4crj9cmAmsBn4CLgEwN3fMbObgBfC7W6MBpNFioJ6A1LmzNNnPpSIqqoqr6urK3Q1pBJobEDKiJmtcfeq9HJdgSySjXoDUkEUDEQyUW9AKoyCgUicegNSoRQMREBLSUjFUzCQylVbCzU18Je/wG23aSkJqWgKBlKZ2ltLSEtJSAVSMJDK0t6YACglJBVLwUAqR0e9gWRSKSGpWAoGUv46miF09dUwaBBMm6begFQsBQMpTx0NDisdJNKKgoGUn/bSQaAZQiIZKBhI+dDgsEiXKRhI6WvvgjHQ4LBIDhQMpDTlesGYBodFcqJgIKVHF4yJ5J2CgZQOjQmI9JguBwMzGwksIbjbmQPV7v4fZnYDcBmwO9z0X9x9efiea4G5QDPwf9z9ibB8BvAfQBL4mbvf3NV6SZnJJR2kMQGRbutOz6AJ+Ka7rw3vg7zGzFaGr93m7j+Mb2xmxwEXAeOBTwBPmtm48OU7gbOAeuAFM1vm7hu7UTcpB7lMEdWYgEhedDkYhDey3x4+ft/MXgWObucts4AH3X0f8Ccz2wycHL622d3/CGBmD4bbKhhUoigVtGMH/PrXSgeJ9JK8jBmY2WhgEvAc8FlgoZnNBuoIeg/vEgSK1bG31XMgeGxNKz8ly+fMA+YBjBo1Kh9Vl2IRBYHFi2H//szbKB0k0mO6HQzM7FDgEeAqd99jZouAmwjGEW4CfgRc2t3PAXD3aqAaoKqqKkPeQEpKvBewYkXmawRA6SCRXtCtYGBmfQkCwf3u/t8A7r4z9vrdwG/Cp9uAkbG3jwjLaKdcylEuvQAIpojOnat0kEgv6M5sIgMWA6+6+62x8uHheALABcDL4eNlwC/N7FaCAeSxwPOAAWPNbAxBELgI+Meu1kuKVK6zgvr2hZkz4aijFAREelF3egafBf4JeMnM1odl/wJ81cwmEqSJtgCXA7j7K2b2MMHAcBOwwN2bAcxsIfAEwdTSe9z9lW7US4pNR7OCQL0AkQIzz/bPWeSqqqq8rq6u0NWQbHKdFfS3f6tegAhQu7WWmi01TBs9jSkj2/4v1G6tZcmLSwCYfeLsjNvkwszWuHtVermuQJb8iQeAxx/XrCCRmPYa+9qttZy55EwamxtJJpJcOvHSVg1+7dZapt03jcbmRgDuXX8vT815qssBIRMFA+m6aBxg6FBYt67jAWHNCpIKFW/s+yX7sWr2qlYNec2WGhqbG2n2Zpqbm/npmp/ys3U/486ZdzLhiAncUHMD+5sP/G81NjdSs6VGwUCKQPo4gJnGA6RXxc+0gXZTLF3ZZ1f3E+1j6MFDafiogWmjp7Vq7KOGPF7naaOn0S/Zj71Ne3GC/6Omliau/M2VmBkt3pIqB+iX7Jf6ufNFwUBy1944QHog6NsXzjtP4wHSabk0yOlpFcNoammiX7Ift8+4PdUId6ZBT9/nzE/N5KhDj2L2ibOB1sEmWx2jfexr2kcLLSQsQf9kf26fcTv9kv1S+35+2/P869P/yv7m/SQSCa6ecjVzTpzDjg928Os3fk1zMLeGFlqIYoBhfOYTn2Hy8MndGjPIRsFA2pfrOEAiEaSBNC1UuqF6TTULly+k2Zvpn+yfSqekN77xM+2W5hYAHOfjpo+Z//h8gHYDQ6bGfMmLS1Jn5s3NzSx9fSkAd6+9O7X/Pok+zPzUTFZsXtGqId+zdw8AOz7c0ersvsVb2Nu0l3Xb17Fq9iqWvLiEe9ffy2OvP3Zgm5YWfvA/P0gFjm+e9k1uq72NppamVr2BPok+3D7j9rwHgdT+e2SvUtpyDQCgcYAKlcvMl/QUTjxtku09C5YvoKmlCYB9zftY8uKSVAPa1NKUOmOHoHH0Zie45InU2XT0fV/TviCwtDSnGu1B/Qcx9OChXPXbq1L5+9tn3M667etYvG5xq8Y3Eu0Pglx9FCTgQEPeHsdZvG5x6nl6I5/al7fQ2NzIoP6DePrip1M/dxR0fjLzJz0WCEBTSyXSmQAAGgcoE5ka9Y7KXtr1Urtn7/HGNkrh7G/eTwstGEYykWx1Nj1p+CQaPmrg7ffepnpNdZAaAZKWpE+iD43NjRkbz6QlgaCxNdrm1ROWoMVbWr0nYYlW2yZIkEwk2zTQCRKpenSFYXz68E/z6p9fTe3XMPom+6ZSWmaGux+oS9gziA8u52MMo03dskwtVTCoRFHDDzBpUm4zgUDjAGUmfYZLdIYcPxuNZrPEc+nNLc2ps+Uoj/2Jwz6RSp1g4O6tGsFMjXmcYSQsQcISqTP500aexu/f+n277432HTXqLd7SppFtT8ISbeo6oM+A1LHY8cGO1M9lZqkA095nxMcJrvrtVa3SRklLctnkyxj1V6M61WvKJ11nUOnaO/PvaCaQAkBZiufd9zbt5crHr2zVMLa0tDD/8fmcNPwk9jXvo8VbaE67eNBxnv/f50krbLNNRwHB8VSAmXfSPCYNn8Q3Vnwj9Z6+ib6cN/Y8Ht/0OPtb9qfKEpZoM3D89ntvc/fau1OfGzXcGevhtPqMuZPmthmczTZrKXo89OChrNu+DjjQy4ka9QlHTGiV5uqX7Ndm/z3d+OdKwaAcpc//7yj1o5lAvaozXf9crzqNp2iihin9oqX0z4ymM0YzXzJlCZq9uW1jD6lGNj0Nk0mCBNOPmc7E4RMzDozGOc6ovxpFw0cNNLcc6H3MnTSXRV9c1OZ4QNsppbVba7nvxfta9XgaPmpIHZuoYU7V31t/RropI6dkbbw7+v1F75194uy8p3vyTWmicpHLQnDZaCZQj8jUcKWfJabnh6PtJw2flBrUjJ8Jnzf2PI469KjU69G2V/32qlSjHonOdKPX069ujeqzdvtaXvjfF1INdIJEm7nt8TPqqHH/u+P+jm+s+Ebqqth4Dr9Pok+r6Z6ZxhWi+g8cMJDbam9rNQYBtHuRVi7Hvr2rfdPHNrryGaVKYwblJH7m39DQ+QAQP/OfNCnYR5nNBGpvHnh7Fyp19qw9vq/2GvKooUxvYGcdO4ujDj2KHR/saJUCiV7vKOcNbfPecVEuPj23nbRkqjw+yBsfJ0ifxZOtcc92pp7p+OZyLHty8DSXzy13CgalLD7gO3Bg64a/vXx/XBGlfjpz5Wi2KYrxs+L0fG36bJbo4qH4GWi8AY3mjgOs2Lyi1RTG9IuOos9OH1iE1lMQc23Ii0H6oGZngqeUHgWDUpBplk+uUz3jooXgrr4a9gTT9wodACLxGSzxgb0+iT5cOvHSVo17psa7oxki6VMH8yHTWX13GEHwyGWmSzxQpfccMu033tNYsXlFm2mZ6UEqmj1TKSkS0Wyi4pGe4sl1kDebqGcQDwDdvAAsveucaa2VjpbYzXTGPm30tFZXecbbwsbmRn665qdZ65TLQGVntuuM+Bl/rtIb8vQrVn/83I8z5vjjYwLpxzrT8Y0a/Sh9863PfqvN9vExim+c8o1UgI0CcE8sbSClRz2DnpDpDB+6nuKJ73oELDkRMGPShLNoOBiGHjKMdR9sgk98gkkTz82aQukotZKe/kgkEnxl/Fd4+JWHUzNAsl00lJ4jTxflrqFrjWuu0s980y8eSp/Pnp7iyTSFMZv0AdMorZStIc8WYDPN/umMzlwN3N66OlIZij5NZGYzgP8guNvZz9z95va277VgkD5NE6gdP5Cav6xn2qCJ8MYb1PT7X4YePZZ129fCRx8z6fm3WXdE0ABN2g7rhpPxccPBMPSj7K+nHu9KsO7kUew4FB4/aCv7yW9uulD7SFoSd09dzNPc0tzmqs9MFyNlCkTxx/Ez4ejioej1qJEGMg7+Rg1ydFadHhzjn51taqNIMSvqYGBmSeAN4CygHngB+Kq7b8z2nq4Gg9oV1dSseSQ4m96+FrCwEcnwuM8I1r28Elo81TjvOARWjIOmBFgLuEGLBd87/XN7O+8zDqRRurDvYha/yjO9cc52AU/0eldnpnSHzqSlnBR7MJgC3ODu54TPrwVw9+9ne09XgkHtimrO/J/L2ZcMGvBuSW+snQONdmcfd6sa+T+rTx8wjVJD6SmjuHiOPH0efHwgWHlqkcIq9gHko4Gtsef1wCnpG5nZPGAewKhRozr9ITVrHqExCS0Jutd4O9ASPo8HhXj7mB4ooscceNyVhjzTIGN7Uy07O2YAtJlKGc9/L/jMgg4vwc/k/GPP19m1SBErlp7B3wMz3P3r4fN/Ak5x94XZ3tOtnkEiDAhd1NeSnGfjWOGb2O9NJDCuPuQs9uzeChiTqr7IuoOz57Sjx11pyHVGLSLdUew9g23AyNjzEWFZXk05dx6rIPcxg+GTMs7SiQ8y6mxXRMpBsfQM+hAMIJ9JEAReAP7R3V/J9p6inloqIlKkirpn4O5NZrYQeIJgauk97QUCERHJr6IIBgDuvhxYXuh6iIhUom4Mo4qISLlQMBAREQUDERFRMBAREYpkamlXmNlu4K1OvOVw4M89VJ3uKta6FWu9oHjrVqz1AtWtK4q1XtD1uv21uw9LLyzZYNBZZlaXaW5tMSjWuhVrvaB461as9QLVrSuKtV6Q/7opTSQiIgoGIiJSWcGgutAVaEex1q1Y6wXFW7dirReobl1RrPWCPNetYsYMREQku0rqGYiISBYKBiIiUv7BwMxmmNnrZrbZzK4pcF1GmtlTZrbRzF4xs38Oy28ws21mtj78mlmg+m0xs5fCOtSFZUPMbKWZbQq/D+7lOh0bOy7rzWyPmV1VqGNmZveY2S4zezlWlvEYWeCO8G9vg5lNLkDdbjGz18LPf9TMBoXlo83s49jx+2kv1yvr78/Mrg2P2etmdk5P1auduj0Uq9cWM1sflvfmMcvWVvTc35q7l+0XwXLYbwLHAP2AF4HjClif4cDk8PFhBPdwOA64Afi/RXC8tgCHp5X9ALgmfHwN8O8F/n3uAP66UMcM+DwwGXi5o2MEzARWENzw9FTguQLU7WygT/j432N1Gx3frgD1yvj7C/8fXgT6A2PC/99kb9Yt7fUfAd8twDHL1lb02N9aufcMTgY2u/sf3b0ReBCYVajKuPt2d18bPn4feJXg/s/FbBZwX/j4PuD8wlWFM4E33b0zV57nlbs/A7yTVpztGM0ClnhgNTDIzIb3Zt3c/Xfu3hQ+XU1wF8FeleWYZTMLeNDd97n7n4DNBP/HvV43MzPgy8ADPfX52bTTVvTY31q5B4Ojga2x5/UUSeNrZqOBScBzYdHCsHt3T2+nYmIc+J2ZrTGzeWHZke6+PXy8AziyMFUD4CJa/2MWwzGD7Meo2P7+LiU4e4yMMbN1Zva0mU0tQH0y/f6K6ZhNBXa6+6ZYWa8fs7S2osf+1so9GBQlMzsUeAS4yt33AIuATwITge0EXdNC+Jy7TwbOBRaY2efjL3rQHy3IXGQz6wd8CfhVWFQsx6yVQh6j9pjZd4Am4P6waDswyt0nAVcDvzSzgb1YpaL8/aX5Kq1PPnr9mGVoK1Ly/bdW7sFgGzAy9nxEWFYwZtaX4Jd7v7v/N4C773T3ZndvAe6mB7vF7XH3beH3XcCjYT12Rt3N8PuuQtSNIECtdfedYR2L4piFsh2jovj7M7OLgS8CXwsbEMI0TEP4eA1Bbn5cb9Wpnd9fsRyzPsCFwENRWW8fs0xtBT34t1buweAFYKyZjQnPLC8ClhWqMmEOcjHwqrvfGiuP5/YuAF5Of28v1O0QMzssekww8PgywfGaE242B3ist+sWanWWVgzHLCbbMVoGzA5nepwKvBfr4vcKM5sBfAv4krt/FCsfZmbJ8PExwFjgj71Yr2y/v2XARWbW38zGhPV6vrfqFTMdeM3d66OC3jxm2doKevJvrTdGxgv5RTDK/gZBFP9OgevyOYJu3QZgffg1E/gF8FJYvgwYXoC6HUMwi+NF4JXoWAFDgVXAJuBJYEgB6nYI0AD8VaysIMeMICBtB/YT5GXnZjtGBDM77gz/9l4CqgpQt80EueTo7+2n4bZ/F/6e1wNrgb/t5Xpl/f0B3wmP2evAub19zMLynwNXpG3bm8csW1vRY39rWo5CRETKPk0kIiI5UDAQEREFAxERUTAQEREUDEREBAUDERFBwUBERID/D00rnzZ778lpAAAAAElFTkSuQmCC\n",
"text/plain": [
"<Figure size 432x288 with 1 Axes>"
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"liste_n = list(range(2, N))\n",
"plt.plot(liste_n, meth1, 'r.', label='méthode 1')\n",
"plt.plot(liste_n, meth2, 'g.', label='méthode 2')\n",
"plt.legend()\n",
"plt.show()"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [],
"source": [
"from math import log"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAX0AAAD4CAYAAAAAczaOAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAA8YklEQVR4nO3deXxU1dnA8d8zk419CftmIgaQfZegYDAuuIFitVorKipWxUqXt5W2KIoWtyrVuoAVBGuFthRFRUUQBCWABIIgsgQISZDNsEO2mTnvHzOTTpKZySSZzEyS5+uHTybn3rn35CY+98w55z5HjDEopZSqHyzhroBSSqnQ0aCvlFL1iAZ9pZSqRzToK6VUPaJBXyml6pGocFegIq1atTIJCQnhroZSStUa6enpPxpjWnvbFvFBPyEhgY0bN4a7GkopVWuIyH5f27R7Ryml6hEN+kopVY9o0FdKqXok4vv0vSkuLiY3N5eCgoJwV6VeiouLo1OnTkRHR4e7KkqpSqqVQT83N5cmTZqQkJCAiIS7OvWKMYa8vDxyc3NJTEwMd3WUUpVUK7t3CgoKiI+P14AfBiJCfHy8fspSqpaqlUEf0IAfRnrtlaq6tJw0ZqyZQVpOWljOX2HQF5E5InJERLZ5lC0UkQzXvywRyXCVJ4hIvse2NzzeM0hEtopIpoi8LPUscsyaNYvjx4+HuxpKqTBKy0kjdX4qU1dOJXV+qtfAX9M3hUBa+m8Doz0LjDE/Ncb0N8b0BxYB//XYvMe9zRjzC4/y14H7gCTXv1LHrMuefPJJWrRoQYsWLQDIyMhg6dKlJdunTZvGCy+8UOXjV/b97777Ln379qVPnz4MHz6cLVu2VPncSqnArcpaRZG9CLuxU2QvYlXWqlLb3TeFP33xJ0a+PZLZ6bODXocKg74xZjVwzNs2V2v9FuA9f8cQkfZAU2PMOuNctWU+cEOla1tLPfbYY9xyyy0l35cN+qGWmJjIl19+ydatW5k6dSoTJ04MW12Uqk9SElKIscZgFSsx1hhSElJKbV+VtYpCWyEOHNgcNiYtnRT0Fn91+/RHAIeNMbs9yhJFZLOIfCkiI1xlHYFcj31yXWVeichEEdkoIhuPHj1azSo6BfMjU1ZWFj169OCuu+6iW7du3H777SxfvpyLL76YpKQkNmzYAMDZs2eZMGECQ4cOZcCAAXzwwQcUFRXx2GOPsXDhQvr378/ChQsB2L59OykpKZx//vm8/PLLJed68cUX6d27N71792bmzJkl5U8//TTdunXjkksuYefOnSXle/bsYfTo0QwaNIgRI0awY8eOcvUfPnx4yaeOYcOGkZubW24fpVTwJXdOZsX4FUwfNZ0V41eQ3Dm51PaUhBQslv+FZbuxl/s0UG3GmAr/AQnANi/lrwO/8fg+Foh3vR4E5ABNgcHAco/9RgAfBXLuQYMGmbK2b99ersyftdlrTYOnGhjrE1bT4KkGZm322kq9v6x9+/YZq9Vqvv32W2O3283AgQPN3XffbRwOh3n//ffN2LFjjTHGTJkyxbzzzjvGGGOOHz9ukpKSzJkzZ8zcuXPNQw89VHK8xx9/3CQnJ5uCggJz9OhR07JlS1NUVGQ2btxoevfubc6cOWNOnz5tevbsaTZt2lRSfvbsWXPy5EnTtWtX8/zzzxtjjLnsssvMrl27jDHGrFu3zowaNcrvz/L888+be+65p9LXoLK/A6VUYGZtnGWin4w2licsVY5XwEbjI6ZWeZ6+iEQB41zB3X0DKQQKXa/TRWQP0A04AHTyeHsnV1lIeOtHK3uHrazExET69OkDQK9evUhNTUVE6NOnD1lZWQAsW7aMJUuWlPS3FxQUkJ2d7fV41157LbGxscTGxtKmTRsOHz7MV199xY033kijRo0AGDduHGvWrMHhcHDjjTfSsGFDAMaMGQPAmTNnWLt2LTfffHPJcQsLC33+DCtXruStt97iq6++qta1UEoFz8RBE+nTpg+rslaRkpBS7VhVVnUezroc2GGMKekbEJHWwDFjjF1Ezsc5YLvXGHNMRE6JyDBgPTAeeKU6Fa8Mdz9akb3Iaz9aVcTGxpa8tlgsJd9bLBZsNhvg/BS1aNEiunfvXuq969ev93s8q9VacozKcDgcNG/enIyMjAr3/fbbb7n33nv55JNPiI+Pr/S5lFJVl5aT5jeoJ3dODnqwdwtkyuZ7QBrQXURyReQe16ZbKT+AOxL41jWF8z/AL4wx7kHgB4G/A5nAHuCT6lc/MBX1o9WUq666ildeecXdpcXmzZsBaNKkCadPn67w/SNGjOD999/n3LlznD17lsWLFzNixAhGjhzJ+++/T35+PqdPn+bDDz8EoGnTpiQmJvLvf/8bcN50vM3Myc7OZty4cbzzzjt069YtWD+uUioAgUzbrEkVtvSNMbf5KL/LS9kinFM4ve2/EehdyfoFTU3eOX2ZOnUqkydPpm/fvjgcDhITE/noo48YNWoUzzzzDP3792fKlCk+3z9w4EDuuusuhg4dCsC9997LgAEDAPjpT39Kv379aNOmDUOGDCl5z7vvvssDDzzAU089RXFxMbfeeiv9+vUrddwnn3ySvLw8HnzwQQCioqJ0zQKlQqQmupsrQ9yt0Eg1ePBgUzYgff/991x44YVhqpEC/R0oVVXulr67u7kmeh9EJN0YM9jbtlqZcE0ppWord3dzTQ3UVkSDvlJKBVFFg7QQnu5mNw36SikVJKHouqmuWptlUymlIk1FuXUigQZ9pZQKkopy60QC7d5RSqkgCfcgbSC0pV9FEyZMoE2bNvTu7fvRgw8++IC+ffvSv39/Bg8eXCrdwbx580hKSiIpKYl58+ZV6txvv/02kyZNqnLdDx48yHXXXVfhfpdffrmuAaBUJSV3TmbKiCkRGfBBg36V3XXXXXz66ad+90lNTWXLli1kZGQwZ84c7r33XgCOHTvGE088wfr169mwYQNPPPFESIPriy++yH333VfhfnfccQevvfZaCGqkVP0UjlW0NOhX0ciRI2nZsqXffRo3blyytODZs2dLXn/22WdcccUVtGzZkhYtWnDFFVd4vYEkJCTw+OOPM3DgQPr06eM1TXJWVhaXXXYZffv2JTU1tSSh2549exg2bBh9+vThT3/6E40bNy55z6JFixg92rmGzdtvv824ceMYPXo0SUlJ/O53vyvZb8yYMbz3nt+lEpRSVRSudAy1vk//iQ+/Y/sPp4J6zJ4dmvL49b2CcqzFixczZcoUjhw5wscffwzAgQMH6Ny5c8k+nTp14sAB70lHW7VqxaZNm3jttdd44YUX+Pvf/15q+8MPP8ydd97JnXfeyZw5c/jlL3/J+++/zyOPPMIjjzzCbbfdxhtvlKxayb59+2jRokWpBG8ZGRls3ryZ2NhYunfvzsMPP0znzp1p0aIFhYWF5OXlaVI2pYIsXOkYtKVfw2688UZ27NjB+++/z9SpUyv9/nHjxgEwaNCgkpTNntLS0vjZz34GOLtj3OMGaWlpJSmW3dvB2Z/funXrUsdITU2lWbNmxMXF0bNnT/bv31+yrU2bNvzwww+VrrdSyr9wzfSp9S39YLXIa9rIkSPZu3cvP/74Ix07dmTVqlUl23Jzc0lJSfH6PneLvKrplstq0KABBQUFXs/h7TwFBQU0aNCg2udVSpUWrpk+2tKvQZmZmSVplTdt2kRhYSHx8fFcddVVLFu2jOPHj3P8+HGWLVvGVVddVaVzDB8+nAULFgDODJsjRjhXqBw2bBiLFjkTnrq3A3Tr1s3rJwZvjDEcOnSIhISEKtVNKeVfOGb6aNCvottuu43k5GR27txJp06deOuttwB44403SvrQFy1aRO/evenfvz8PPfQQCxcuRERo2bIlU6dOZciQIQwZMoTHHnuswkFhX1555RXmzp1L3759eeedd/jrX/8KwMyZM3nxxRfp27cvmZmZNGvWDIBGjRrRtWtXMjMzKzx2eno6w4YNIyqq1n8gVEq5aGrlOurcuXM0aNAAEWHBggW89957fPDBB4BzcDk9PZ2nnnrK7zEeeeQRxowZQ2pqarlt+jtQKrgCSdQWKE2tXA+lp6czadIkjDE0b96cOXPmlGy78cYbycvLq/AYvXv39hrwlVLBFcpEbRr066gRI0Z4XSrRzf2gmD+BPMCllKq+UE7frLV9+pHeLVWX6bVXKrhCOX0zkIXR54jIERHZ5lE2TUQOiEiG6981HtumiEimiOwUkas8yke7yjJF5NHqVDouLo68vDwNPmFgjCEvL4+4uLhwV0WpOsM9fXP6qOk1noO/woFcERkJnAHmG2N6u8qmAWeMMS+U2bcn8B4wFOgALAe6uTbvAq4AcoFvgNuMMdsrqqC3gdzi4mJyc3PLzTdXoREXF0enTp2Ijo4Od1WUUl5UayDXGLNaRBICPNdYYIExphDYJyKZOG8AAJnGmL2uCi1w7Vth0PcmOjqaxMTEqrxVKaXqteoM5E4SkfHARuA3xpjjQEdgncc+ua4ygJwy5Rf5OrCITAQmAnTp0qUaVVRK1Wae0xiBoE1pDOb0yGAcK5j1qUhVg/7rwHTAuL7+BZgQrEoZY2YDs8HZvROs4yqlag/PaYxWixVBsDls1Z7SGMzpkRUdK5BgHup1das0e8cYc9gYYzfGOIA3+V8XzgGgs8eunVxlvsqVUsorz2mMxfbioK09G8x1bP0dK9DUyaFeV7dKQV9E2nt8eyPgntmzBLhVRGJFJBFIAjbgHLhNEpFEEYkBbnXtq5RSXnlOY4y2RgdtSmOwpkem5aSRfTKbKEuU12MFGsxDnW2zwu4dEXkPSAFaiUgu8DiQIiL9cXbvZAH3AxhjvhORf+EcoLUBDxlj7K7jTAI+A6zAHGPMd8H+YZRSdUfZLJQQnD79YGS3LNv1dN/A+xjfb3ypY7mDubvbxlcwD3W2zVqZe0cppcJpxpoZTF05FbuxYxUr00dNZ8qIKeX2C+UArSfNvaOUUkFUmVZ8pC2QrkFfKVWvVaU1Hq4FUIJBg75Sqt6qznTJyrbiw9XVU5YGfaVUWERCEAxVdstQz8X3R4O+UirkIiUIBto3X12hTJ1cEQ36SqmQi5QgGKq++VDdXAKhQV8pFXLBCIK1KedNJA386jx9pVRYVCfgBqN7KFK6mLzJPX6Ob3NPck2f9hXv7IXO01dKRZzqzGEPRveQrzQJNZHVM1AFxXZmfbmX11Zl0jDGyqjubWgQYw3qOTToK6VqnWB0D5U9RnzD+BrJ6hkIYwyfbz/Mkx9tJ/d4Ptf2ac8frr0w6AEfNOgrpWqhYPSRlz2GZ8vfYXcAYDDlPkkE2i0V6FoAe46e4YkPt7N611G6tW3MP++9iOEXtKr0zxMoDfpKqVopkO6higJ02WO4W/5lW/ruwB3oOEAgawGcKbTxyhe7mfPVPuKirDx2XU/uSD6PaGuVkh8HTIO+UipiBHtFq8oM1AaS1dPXWELZevv71LBy3yoO/9iFPy/9niOnC7l5UCd+N7oHrZvEVuvnDZQGfaVURAj2bJqKBmoDafmX3cfbWIK3envu59nSb0g3vtw8kNkHM+jbqRmz7hjEgC4tqvwzVoUGfaVURAj2A1v+BmqrelPxNpYwY82McvWeMmJKqf3OFDh4aXkm32e34qhYeGZcH24Z3BmLRar881WVBn2lVESozowcb91C/gZqq3NTKftpwFe9kzsnM7TjMBZ8k80Ln+3kZH4r7kxO4FeXd6NZw+hKnzdYNOgrpSJCVWfk+OsW8jVQ6+2mEuhsm0Drnb7/OI8v2ca2A6cYmtiSJ8b04sL2TQO8GjVHg75SKmJU5YGtQFvw/m4qgcy2CbTeR04X8OwnO1m0KZd2TeN4+bYBXN+3PSKh78rxRoO+UqpWq0y3kK+bir/ZNvO3zGf+lvkA5dbB9VRsdzBvbRYzl++m0GbngZSuTBp1AY1iIyvMVph7R0TmANcBR4wxvV1lzwPXA0XAHuBuY8wJEUkAvgd2ut6+zhjzC9d7BgFvAw2ApcAjJoDEP5p7RynlyVv/fXWnevpq6VstVowxFDuKAYi1xrLyzpXlzrF611Ge+PA79hw9S0r31jx+fS8SWzWq/g9bRf5y7wQS9EcCZ4D5HkH/SuALY4xNRJ4FMMb83hX0P3LvV+Y4G4BfAutxBv2XjTGfVFR5DfpKKbeaTJLmrU8/+2Q2s9JnYfhfnLzy/CuZljKN5M7J7M87y/SPvmf594dJiG/I1Ot6clmPNmHvyqlWwjVjzGpXMPcsW+bx7TrgJxVUoD3Q1BizzvX9fOAGoMKgr5Sqe6raMq/JPPze5uin5aQxJ2MORfaikvLl+5bz1f5vuLfbv/lkSxHRVuHRq3tw98UJxEYFP1dOsAWjs2kCsNDj+0QR2QycAv5kjFkDdARyPfbJdZV5JSITgYkAXbp0CUIVlVKRoqLWur8bQqgXI0nunMyqO1cxf8t8Nh3cxMYfNtKgeCQtbHfzwaYCxg3syO9H96Bt07garUcwVSvoi8gfARvwrqvoINDFGJPn6sN/X0R6Vfa4xpjZwGxwdu9Up45Kqcjir7Ve0Q2hohk4NZEK2f0J4N30Nfzfvg3EOHpQbMnk6XGJjB/SP2jnCZUqB30RuQvnAG+qe0DWGFMIFLpep4vIHqAbcADo5PH2Tq4ypVQdEkjg9ddaD6T7xtsMnJrs6//xTCEvfLaThRtP0SruQgYkZTPxkiFc3GV4UI4falUK+iIyGvgdcKkx5pxHeWvgmDHGLiLnA0nAXmPMMRE5JSLDcA7kjgdeqX71lVKRItDA66+1XjZnTfbJbNJy0ioM4DXR1++egvnXFbvJL7Jz7yWJPJyaRNM430/Thmr5xeqoMOiLyHtACtBKRHKBx4EpQCzwuWuU2j01cyTwpIgUAw7gF8aYY65DPcj/pmx+gg7iKlWnVCbw+pov774hzN8yn7kZc3lz05vM2zKPmaNnkncuz2cwDaSvvzIBefWuozz50XYyj5zh0m6tmXpdTy5o09jveyJ5+UVPgczeuc1L8Vs+9l0ELPKxbSNQbiqnUqr28gykwcydsyprFTaHDbuxU2grZNLSSTiMw2cwrSiFQ6ABeX/eWZ76+Hs+336Y8+Ib8tadgwOeglmTM4uCKbIeFVNKRRR/rWNvgTRYuXM8byAi4nxS1jgqTLPgnmY5Y82MgPLgu50ttPHqykz+vmYfUVbh96N7MOGSyk3BDPXMoqrSoK+U8qqi1rG3QDplxJSg5M7xTE0c3zCeyZ9ODiiY+qqzr4BsjOGDjB+Y8cn3HD5VyLgBHfn91VWbghmMJRxDQYO+UsqrilrHwWrZ+ktN7D5fnzZ9AgqmvursLSBvzT3JtA+/I33/cfp2asZrtw9i0HnVW9CkKgnjQk2DvlLKq4qCerBatoEcJ9Bg6q/O7mP8eKaQRxd9y8KNOcQ3iuG5m/ryk0GdwrKgSThUmHsn3DT3jlLhU5kZL5EyXdFXPYrtDuan7Wfm8l3kF9m5a3gCv7zc/xTM2qpaCdfCTYO+UpHPW186BL4QSU1bs/soT3zonII5sltrHgtgCmZtVq2Ea0qp+qE6LfWyfenzt8xn3pZ5NT5nvaI6Z+edY/rH20umYP59/GBSLwx/Fsxw0qCvlKr2g0Vl+9KBGp+z7q/OZwpt/O2LTOZ85ZyC+bvR3bnnksRakQWzpmnQV6oeqKhFXN0Hi8oOxgIlLf3KpFOoDG91vqjjMP6Tnstzn+3kxzOFtTILZk3ToK9UHRdIKz4Y0y/LzrDxlk4hmN08ZevcLuZixrz6FdsOnGJgl+b8/c7B9O/cPCjnqks06CtVxwWauTLYDxaVTadQE4uerBi/gg+3f83enH48sfg07ZvF8ddb+zOmX4d63W/vjwZ9peq4QFvxNfFgkfvchbZCRIT4hvFBO/bZQhtrv2/JojW9ELEx+fIk7h/ZlQYx1oiZPhqJdMqmUvVAOIPg7PTZTFo6CbuxE2uNrXYXj8NhWLz5AM99toPDpwoZ278Dvx/dgw7NGwC1J9tlTdIpm0rVc74WHqmpG4HnsfPO5eEwjgoTpgUiff9xnvxoO1tyTtDPR+qE2pLtMlw06CtVD9Vka7jssWeOnlntQeIfTuTz7Kc7+CDjB9o0ieUvN/fjxgEdvaZOqC3ZLsNFg75S9VBFreGKUipXZvpn3rm8Kg8S5xfZmbV6D298uQeHgUmjLuCBlK40ivUdumpLtstw0aCvVD2TlpNG9slsoixR4KBca9jfp4CqTv+s7CCxMYYlW37g2U928MPJAq7t055Hr+5B55YNA3q/5/l0ULc0DfpK1SOeQdtqsXJ9t+tp17hdqX38fQrw3FZgK2D+lvlBn/65JecET360nfT9x+nVoSkv/bQ/F51ftVk/OqhbngZ9peoRz6Bt7IaPd3+MwzhKPTjlr088JSEFq8WK3W7HYJibMZfx/cZ7DfyVDa6HTxXw7Kc7+O+mA7RqHMtzN/XlpkGdsFYj5bEO6pZnCWQnEZkjIkdEZJtHWUsR+VxEdru+tnCVi4i8LCKZIvKtiAz0eM+drv13i8idwf9xlFL+uAO6VaxYLBbsxl4qIML/WurTR00v1zJO7pzMhP4TEJyB2OawlbyvqgqK7fzti92MemEVH205yC8u7crK317KLUM6VyvgQ+mfVwd1nQKapy8iI4EzwHxjTG9X2XPAMWPMMyLyKNDCGPN7EbkGeBi4BrgI+Ksx5iIRaQlsBAYDBkgHBhljjvs7t87TVyq43H3cZZchDLTrI1hdJsYYlm49xJ+Xfs+BE/lc1astf7jmQs6Lb1SVH8tvfetbn35Q8umLSALwkUfQ3wmkGGMOikh7YJUxpruIzHK9fs9zP/c/Y8z9rvJS+/miQV+pmlPVRVKgernytx04yZMfbmdD1jF6tGvCY9f3ZHjXVlX5EZQXNfVwVltjzEHX60NAW9frjkCOx365rjJf5d4qPBGYCNClS5dqVFEp5U+gfe/eWvdTRkyp9Pk+3vE1Ly/fy67clrRoFMPTN/bm1iFdqt2NowIXUJ9+RYzz40LQ8jkYY2YbYwYbYwa3bt06WIdVSlWRtwHRysgvsvN///2CB94+xI7cJpyNXsJztzXk9ovO04AfYtUJ+odd3Tq4vh5xlR8AOnvs18lV5qtcKRXh/A2IpuWkMWPNDNJy0sq9z+Ew/HdTLqNeWMW/N+RTYN3ED7EPcCz6Lb45uDqEP4Fyq073zhLgTuAZ19cPPMonicgCnAO5J139/p8Bf3bP8gGuBCr/+VApFXK+5t77G9TdsO8YT328nW9zT9K3UzPuT43moeUvYTQ9QlgFFPRF5D2cA7GtRCQXeBxnsP+XiNwD7Aduce2+FOfMnUzgHHA3gDHmmIhMB75x7fekMeZYkH4OpVQN8RzALduP763bp0PDvjzzyQ4+2XaI9s3ieOmn/Rjbz5knp0cH7zeO+ja7Jpw0tbJS9YivAOuv3N/0TM/tsZbm3HXBQpZtLSTaauGBS7ty74jzaRDje11afWK2ZmhqZaWUzwDrL/BW9ERrcudkPrt9OW+s2caWPZ1YuqWAmwd14jdXdg9oXVp9Yjb0gjJ7RykV+XzNwPE3M8ffAK4xhi92HGbaoiK+/q4jfTq05KOHL+G5n/QLeCFyfWI29LSlr1Q94Sunjr9cO74GcHccOsVTH33PV5k/ktiqEW+OH8zlF7ap9Lq0mgY59LRPX6l6JJA+ffD9tO2R0wW89PkuFn6TQ5O4aCZfnsTtF51HTJR2GkSSoKRhCBcN+kqFjq/+/YJiO299tY/XVmZSaHNw5/AEHr7sApo3jAl3lZUXOpCrlApI2f79lftWcSSvC899upMDJ/K5smdbplxzIYmtgpsUTYWOBn2lVAnP/v2G9OaL9AHMPpxBrw5NeeHmfiR3rdpiJipyaNBXSpVI7pzMghuW8dfl+9lzsDmnrFE8/5Ne3DSwk9dFyFXto0FfKQXAyfxiXluZydyvT2OxtOSR1K7cf+n5NIzRMFGX6G9TqXquyObgnXX7eeWL3ZzML+amgZ34zZXdaN+sQbirpmqABn2l6in3ylXPfbaD/XnnGJHUiilXX0jPDk3DXTVVgzToK1UPpe8/xtMff8+m7BN0b9uEeROGcmk3XbuiPtCgr1Q9kvXjWZ791JkBs02TWJ67qS83DeqkC5nUIxr0laoBkZYu+NjZIl5esZt/rNtPTJSFX1/RjXtHJOogbT2kv3GlgiwU6YLTctKYv2U+AOP7jfd5/IJiO2+vzeLVlZmcLbRx69AuTL48iTZNAkuIpuoeDfpKBVlNpwtOy0kjZV4KRfYiAOZmzGXlnStLncPhMCzZ8gPPf+Z8kja1RxsevboHSW2bBK0eqnbSoK9UkPnLWhkMq7JWUWwvLvm+7I1l7Z4f+fPS79l24BS9OjTl+Z/0ZfgFrYJaB1V7adBXKshqMl1wWk4a2SezibJEUexwBn73jSXzyGlmLN3Bih1H6Ni8QallCpVy06CvVA1I7pxcI/347rECq8XKDd1voF3jdoxJ+jkfbmzMwm/W0DDayu9H9+DuixOIi/a9TKGqv6oc9EWkO7DQo+h84DGgOXAfcNRV/gdjzFLXe6YA9wB24JfGmM+qen6l6hvPsQIcMKDtRTR33MRv391Doe0kdww7j1+mJtGykaY7Vr5VOegbY3YC/QFExAocABYDdwMvGWNe8NxfRHoCtwK9gA7AchHpZoyxV7UOStUF7umd8Q3jyTuX57NLqGSswGajqeMKFn/Vl+NndzG6Vzt+f3UPTXesAhKs7p1UYI8xZr+f5dLGAguMMYXAPhHJBIYCaUGqg1K1jrvLptBWiAMHFrEQa431Os1zWKdhPD/yE/7+5Y8cPxPHeZ2b8eYdFzI4oWWp40XS8wEq8gQr6N8KvOfx/SQRGQ9sBH5jjDkOdATWeeyT6yorR0QmAhMBunTpEqQqKhV53F02DhwAOIzD6zTPTdnHeeaTHWzYd4bEVvE8PbY7V/duV2pN2lA8H6Bqv2ovbCkiMcAY4N+uoteBrji7fg4Cf6nsMY0xs40xg40xg1u31nwgqu6KbxiPRSwIzuBtEUupaZ57jp7hgX+kM+61tew9epbpN/Rm2a9Gck2f9uUWIff2fIBSZQWjpX81sMkYcxjA/RVARN4EPnJ9ewDo7PG+Tq4ypeqltJw0Jn86GbvDjtVi5dfJv6Z5bHNSElLo2mwAf1y8lQXf5BAXZeFXlzvTJjSK9f2/bE0/H6DqhmAE/dvw6NoRkfbGmIOub28EtrleLwH+KSIv4hzITQI2BOH8StVKnl07YoTmsc2ZNOS3vLl6L3etXkGx3XB57zieHjOC1k1ifR7Hsx+/7PMB2sevyqpW0BeRRsAVwP0exc+JSH/AAFnubcaY70TkX8B2wAY8pDN3VF0USKD1fMgKB8RYGlJwahgpz68i72wRBVFrOR47j39kHWPwrpk+Z/V468efMmKKz20a+FW1gr4x5iwQX6bsDj/7Pw08XZ1zKhXJAgm0pR6ykiiu7fw4Bw8OZt6acySfH0+79ut4ZfOzzvn4Nnjw4wcBvB7PX56fms4BpGonfSJXqSBwt+6zT2ZXGGjdwTja1osWtgls2XkBPdo14tmbehDbIJN3vt2JRSzOoA8lX70dz18/vvbxK2806CtVDe4Ux3Mz5mJz2LBarP/rsvERaG1FbWlV+Dhx9oHY5SgPpDbit6kj2HBgHanzLy/JnikIBlPy2tvx/OX5qckcQKr20qCvVBW5u2kKbAUlwRkH3DfwPro061Iu0OYcO8eU979mza7WRNOQkzFzefq6K3lwaApQujvGgoUoSxQO48BqsTKh/wSfefP95fmpiRxAqnbToK9UFbmDdNnWeNngfPxsEa+uzGR+2n7sxsbpqMWcjPoXYingZOGgkv3KdsfMHO17ANcfnbGj/NGgr1QVuR+sMhiiLFHlWuPnimzM/TqLN77cw9lCGz8Z1ImRPU9zy+IFiJd+9mB0x+iMHVURDfpKVcBby9nzwSqLxcIrV79CnzZ9WJW1CpvdkHWwAy9/kcnR04Wk9mjD70b3oHs756pVK5r4Duz+umMCacHrjB1VEQ36ql4KtAvEV8u57INVmw9uZvInv8JadBHNi9tgNccZktCC128fWJIQzfOc7rn0lalvIC14nbGjKqJBX9U7lekC8dVyLhVcLTEcOdaG5mefJcYkUiR7uW7IPl4bd01JfpzqdrtU1IL391SuUp6qnXBNqXBKy0ljxpoZpOUEnqG7MonJ3MHdKtaSlrM7wM4cPZMH+/2FEU0Wk759KBYakBfzAicaPcr4oYNKJUSrbjI0b/XwvAap81OZunIqqfNTAUo+SVT22qi6T1v6qtaqauu5Ml0gZQdXAVLnp2KKO9C8+E5i7QNp08TKUzf04Lx2Lfgq50pSEv5crh7V7XbxN8jr64aiA7rKGw36qtYKdNCybP99ZWfJeA6uPvrpX2h8bhIN7Zfi4AwX9TjI2z+7mwYxVuA8RiQM93nu6na7+Brk9XZD0QFd5YsGfVVr+Ws9ey5BOPnTyeVavJV9aOnIqQJe/mI3/1rfnTiTyKmof1MY9zGTU5e4An55/pKhBZOvm5gO6CpvNOirWstXsPMMtiKCwzh8rkhVkZPninlj9R7mfr2PYruDM1Gfcdz6HlhP8urVr/o9lmdru9BWyLRV05iWMq1GWtxlb2KagkH5okFf1WreWuyl0hkYC1aL1WfuGl/yi+zMXbuPN1bt4XShjbH9OhDX/Ate2PA6dmPHaqzkncvzewz3JxH3+rfL9y1nTfaakPWvawoG5Y0GfVXnVCedQbHdwYJvcnhlxW6OuB6s+u1V3bmwfVPScgp4OT3wLhN3a3vaqmks37e8yp82lAomMcaEuw5+DR482GzcuDHc1VC1TGXzz9gdhg8yDjBz+W6yj51jSEILfj+6R8mDVVU9rvs9OpNGhZKIpBtjBnvdpkFf1WcOh+HT7w7x4ue7yDxyhp7tm/J/V3UnpXvrcguPV4cmQVOhpEFf1QuVCazGGL7YcYS/LNvF9oOnSGrTmF9f0Y2rerVj/YF1GqBVreYv6GufvqoTAu1CMcawdk8eLyzbyebsE5wX35CXftqPMf06YrWIdsWoOq/aQV9EsoDTgB2wGWMGi0hLYCGQgHNx9FuMMcfF+Xn5r8A1wDngLmPMpurWQdV9FbXiA3kYaWPWMV5YtpN1e4/RvlkcM8b14SeDOhFttVTqOErVZsFq6Y8yxvzo8f2jwApjzDMi8qjr+98DVwNJrn8XAa+7virlUyCtb38Pam3NPclfPt/Jqp1HadU4lmnX9+TWoV2Iiy7/UJVmqVR1XU1174wFUlyv5wGrcAb9scB84xxIWCcizUWkvTHmYA3VQ9VCZVv1ZVvf87fML7XdMwGa59TMnYdO89Lnu/j0u0M0bxjNo1f3oHvnw6w7sIDNh7x/YtCHmlRdF4ygb4BlImKAWcaY2UBbj0B+CGjret0RyPF4b66rrFTQF5GJwESALl26BKGKqrbw1qr3fMgJ4K3Nb+EwjpI5+GXTLLRr0JdHFmxmyZYfaBQTxeTLk5hwSSLfHd1YsvC4v/n7+lCTqsuCEfQvMcYcEJE2wOcissNzozHGuG4IAXPdOGaDc/ZOEOqoIpy7tZ59Mrtcn/qUEVOYOXomk5ZOwuawYTd2AIrsRSzavqhkf3txM55YksnuA8eJtgr3j+zKwAvySD+0iO+OppRLizBp6aSSm0dFA7Y65VLVFdUO+saYA66vR0RkMTAUOOzuthGR9sAR1+4HgM4eb+/kKlN1kGegBHwGTc/WvdViJcoSBQ6wWqxkn8wmLSeNvHN5OIyj3CLkN/W8ia+zthFXNIZGttFkHojijmHn8eCoruw5sZnU+VeUtOwfvujhkjVtLWLBbuw4jKPCvDg6o0fVJdUK+iLSCLAYY067Xl8JPAksAe4EnnF9/cD1liXAJBFZgHMA96T259dNZQO5INgcNq9B07MFjgPuG3gfAHMz5vLmpjeZt2UeM0fPLBlgtVqsTOg/gesv+Dnf7G5O+4LZ2B2GUT3jmD7mYjo0bwDAWxmlW/Yvpb1Usqbtr5N/zSvrXymXF8ezy8ddN2+fPjToq9qqui39tsBi15OLUcA/jTGfisg3wL9E5B5gP3CLa/+lOKdrZuKcsnl3Nc+vIpRnIHfYHQAYjNegWXbGzPh+450LjLu6cgpsBWw+uLlkgLV/m5Fs3N2CX/1jPzbHScYN6MTDlyXRJb4haTlpzNvq/ETheVwRcdbFtaZt89jm5fLieHb5eN6oPD996IweVdtVK+gbY/YC/byU5wGpXsoN8FB1zqlqB8+AW7alXzZo+poxY7VYsdvtGAxzM+YyNunnOE6N5VfL9lNkO8GNAzrx8GUXkNCqEeC9G8Z93LJ59d3nmZYyjTXZa0rfGIyj1I3K/emjS7Mu2qevaj1Nw6BqjLc+/fiG8QFnvHzgoweYlT4LMU1obruZFmYsDoeFG/p35OHUJBJdwd5txpoZTF051Zn6WKxMHzW91KIlvgZjvS24UlGXlFKRTNMwqLDwNvWxMgOiN3T7Of/ZYKNB0WiEGC7qFseT1yfTtXVjr/tX9GCVr6mY7rKyc/3dZdq6V3WJBn0VMr4W8C77aWBQu5Fs3hPPvLWnaVx0A107HOcXKW35Sd9L/B6/qg9W+Zudo8Fe1TUa9FXIeD5kJSKcKDxRaoaPxTShQeF1NLYlYeUE1/ZtzyOpSSS1bRLwOaryYJXm21H1iaXiXZQKjuTOycwcPROrxYrDOPjL2r9QYCvAOOJoWHALrc++TlPbzRRY0/nJyJ387WcDKxXwq8p9M7KKVWfnqDpPW/oqpNwPWTmMA4tpTFPbWJraxmChEQXWtZyIfg9L9CHG9VkRsjppvh1Vn2jQVyGVkpBCrLQipuhqmtiuwUJDzlnWckW/YiYNv5FVWY0DCrzBToug+XZUfaFBX9U4d4Du13okmzJb0LHwLYpshvyorzkZtRBL9CEmDV8RcODVtAhKVZ0GfVWj0nLSuOLtm4ktvJ7GtiNY5QQ39O/Ig6Mu4GhhPKuymla6ta4Dr0pVnQZ9VWNyjp3jyQ93E3/2b4BwzrqSe0Z05pnR1wJwAVXrUtGFTpSqOg36Kuj2553l1ZWZ/HfTAQzxFEQv44T131ijTzC2V/UHaHXgVamq06CvgmbP0TO8+kUmH2z5AatF+Pmw87j/0vPJOtWSVVntghqgdeBVqarRoK/KqezMmJ2HTvO3lZl89O0PxEZZuHt4AhNHnk+bpnEAtG+mAVqpSKFBX5VSmZkxm7KP89rKPSz//jCNYqzcP7Ir945IpFXj2BDXWikVKA36qpSKZsaszV7LuxvT2bavI/uPxtIoVngkNYleCUdJP7SY3cdTaNVYW/VKRSoN+qoUXzNjHA7DK6tX89yyDKIdF2Ajj9NR7/CDdTmH5EH++K9XdN68UrWABn1VStmZMYM7XMR/0nN548s9ZB45g0gj8qJf4Yx1BYgNDLyw9gUAHMah8+aVinC6iIryqqDYzsJvcpi9ei8HTuTTo10TrujrYOra6yi05+PAUbKvIERZonAYR0lLHzQXvVLhoouoqHK8zdBJy0njs92ryT81hOVb7eSdLWLweS2YfkMvRnVvg4gwPOlzVmWt4kThCedC48ZOrDW23OIjmiZBqchU5aAvIp2B+TgXRzfAbGPMX0VkGnAfcNS16x+MMUtd75kC3APYgV8aYz6rRt1VFXmboXPinIPx786lQdGVWMinX5doXv95MkMTW5Z6r+f8+Bu63+B1CcQZa2ZomgSlIlR1Wvo24DfGmE0i0gRIF5HPXdteMsa84LmziPQEbgV6AR2A5SLSzRhjr0YdVBV4ztCxF7dk+oe72ZnbgoaOsZyzfs2Z6EUM6zOBoYlX+j2OO5CXvYFomgSlIleVg74x5iBw0PX6tIh8D3T085axwAJjTCGwT0QygaFAWlXroKomJSGFhvQirug6GtiHsSvXwsjusfwn+37yzf5KBWpvUzynjJiiaRKUilBB6dMXkQRgALAeuBiYJCLjgY04Pw0cx3lDWOfxtlx83CREZCIwEaBLly7BqKLCOe1yxY4jzF5taHnuz8RE2bhmUEP+MPpi2jSJY2LOPyodqMu26uMbxjNjzQxSElKYMmJKDf9ESqnKqvbsHRFpDHwJPG2M+a+ItAV+xNnPPx1ob4yZICJ/A9YZY/7het9bwCfGmP/4O77O3qmetJw0lu/5EkvhRXycUcAPxx20amLhwUt78NMhnfn2yDcBB3pf6Rnc5fEN45n86WQdwFUqzGps9o6IRAOLgHeNMf8FMMYc9tj+JvCR69sDQGePt3dylaka8vnur7ntnddpUDQaK+cotuzlVMx/OehYxzcn7sK2bUDAQdpfegb34K4O4CoV+aoze0eAt4DvjTEvepS3d/X3A9wIbHO9XgL8U0RexDmQmwRsqOr5lW85x87x1lf7+Mf6PBrbbyPfks6pqP9SaPkWIwYcMCt9VskC5d4eqirbqg9k4RIdwFUq8lWnpX8xcAewVUQyXGV/AG4Tkf44u3eygPsBjDHfici/gO04Z/48pDN3/KtstsuMnBO89dU+lm49iADJSQ14P+dh8snEarESgzMgG9d/DocDq8WKIKWCtLdWfSABXfPcKxX5qjN75ytAvGxa6uc9TwNPV/Wc9Ym/7hTPm8GQDhfx6XeHmPPVPjZln6BxbBT3XJLI3RcnkHUqg8ZbRgGjGNB+AJsPbubQmUN8kvkJNoeNGGsMM0fPZPPBzaXOXZ0ZOZrnXqnIpk/kRihf3Snum0GxLZom9gzayM0UFDbgvPiGPH59T34yqBPbjm7kyTW/Zm7GXGwOm7M1nyElgf7lq18u9fSsu19/3pZ55Vr1VouV7JPZpOWkaUBXqg6whLsCyrv4hvFYxIJFLKUC7+JtaTTMv5v2+XNoWjSeE8W7ONHgWf58Syx3X5zItqMbSZ2fyqz0WRTaC7EbO8X24lI3kLxzeUwZMcVvX/2K8Su4b+B9CMLs9NmMfHsks9Nnh/uyKKWqSVv6ESgtJ43Jn07G7rAjIhiHYd6GDSxOa0+cfRCNOJ+z1lWcilpCsWUfVrHyj63vsDr7S7JPZpf024MzGVq0NRrhfy19z/54X3317htCsb0YBw4cDgeTlk6iT5s+2tpXqhbToB+B3K1vY6JpaBtFE9v1xJjzsHOcE1H/4EzUp2A57fwUYKyICG9uehODIcoSRZQlChxgtViZ0H8C4/uNLzlu2f54f4OvKQkpWCwWHA5nRk27ses0TKVqOQ36Eah78xG0LL6PuOIULDSmSPbwY/SLnLWuduawB6xYuWfAPQC8uelN7K6JUMX2YoZ0GMLA9gMZ3298uQDvja+++uTOybx6zatMWjqpJJumTsNUqnbToB8B0nLS+GLfKpoxnGXbCvk2u5jGci2J7U9y+7AmFFvjePiTNYjDjgEsYiHGGsP4fuNZlbUKz6eqDYaNBzey9cjWkhZ+dUwcNJE+bfroNEyl6ggN+mH22a6vuf0frxJXfDlR5gx2yeNM9GcUx6zk3XGLXEF2JH3b9vGaxhggNiqWQlshCBhjgr6Clc7aUaru0KAfBsYYMnJO8E7afhZn5NHY3E6BZQvHo+eQb1mPERtWYy0VtP11wbj75MvmvtGuGKVUWRr0a5jng1R92gxhScYPvLchm60HTtIgGs5EfcZJy4cUW3KwihULYLBUKmh73hC0K0Yp5Y8G/RqUlpNG6rxUTPF5vGg/THPzI8V2C93bNmH6Db3Zm7+A6WtmlQzCgvNTgMViYebomVUK2toVo5TyR4N+DUjLSeOt9PdYn+mg+dnniDGJOCjgRNQXPHhZX2LjvuWCjtFcwEieXeucIy8izuRnOBAj5J3LC/ePoZSqgzToB5Exhjnr1/CHjz4izjYKIQYju8mL/htnrV+CFDBjfRQO48C62jmH3r2guPbHK6VCQYN+NaTlpDF/y3zOFTSgjeU61uws5NBJB7EM5ox1GaejllFs2YtFLAhgESt2Y8dhHNjtdmalzyIuKq4kmZr2xyulapoG/SpasWctN82fTlzxpcQ5+gD5FFq3ciZ6BWetazBSCECsNbYkwdmJwhO8lPYSxpiS9MaeUyu1P14pVdM06PtRNp+9ze5g7Z48Zn2VwdrdZ2luJlEsBzgeNZ+z1pXYLUcBsGBhSIehpZ6KdWfHtDvsJYnUHMahXTlKqZDSoO9DST57m41G9CW1w/+xLTuaouJYHJzhnHUNp6OWUyQ7y60qEG2NLjf7xp1Px4GjJIVCl2ZdtCtHKRVSGvTLSMtJY17GfNZnHaFB/h20tF1MFPFs3FNIvnUD52LWcM7yDUgxFiwM7TAUgI0HN+IwDgTh7v53V7iUYNm8OEopFQoa9HEG+rcz3mHvYcPmLDtx9mSiTBsaU0S+ZSPHrWvIt36DkYKS9whCbFQsM0fPBCi1ypW3nDe6lKBSKhKIZ7KuSDR48GCzcePGoB/XOZf+n2QejGF7rpVY+0CsNMFQTL5lM+esqzlnXY+R/HLvjbZEc8+Ae0q11iu7nq1SStUUEUk3xgz2ti3kLX0RGQ38FbACfzfGPFNT53IH4viG8Ww+uBmHQ2gbN5R1e/LYmlNEjONyhChiOUm+dT351g3kWzaXBPpoSzQWiS1ZcvCaC66hXeN2XrtmdOaNUqo2CGnQFxEr8CpwBZALfCMiS4wx24N9rtnps/nlx3/AYjuPaEdX4hy9iHX0xEJDoDUi+zgVtZh8y3oKLbtAnAuFRFuiuTbphpLgDt4XH1FKqdoo1C39oUCmMWYvgIgsAMYCQQ36a7LW8uR/omln5pWUFUsOZ61fUGDdSoFlKw45VbLNGejH+G3FK6VUXRDqoN8RyPH4Phe4qOxOIjIRmAjQpUuXSp/kq5wvybfupZg8iiyZFFv24pCzJdstYiHGEuO3u0YppeqiiJy9Y4yZDcwG50BuZd+fkpDC9AbTKbQVYrFY+G3yrzlV4GzZD2g/oNwiJEopVV+EOugfADp7fN/JVRZUOj1SKaW8C3XQ/wZIEpFEnMH+VuBnNXEinU2jlFLlhTToG2NsIjIJ+AznlM05xpjvQlkHpZSqz0Lep2+MWQosDfV5lVJKgSXcFVBKKRU6GvSVUqoe0aCvlFL1iAZ9pZSqRyI+y6aIHAX2V+ItrYAfa6g61RGp9QKtW1VEar0gcusWqfWCule384wxrb1tiPigX1kistFXStFwitR6gdatKiK1XhC5dYvUekH9qpt27yilVD2iQV8ppeqRuhj0Z4e7Aj5Ear1A61YVkVoviNy6RWq9oB7Vrc716SullPKtLrb0lVJK+aBBXyml6pE6E/RFZLSI7BSRTBF5NMx16SwiK0Vku4h8JyKPuMqnicgBEclw/bsmDHXLEpGtrvNvdJW1FJHPRWS362uLMNSru8d1yRCRUyIyOVzXTETmiMgREdnmUeb1OonTy66/vW9FZGCI6/W8iOxwnXuxiDR3lSeISL7HtXujpurlp24+f38iMsV1zXaKyFVhqNtCj3pliUiGqzxk181PrKi5vzVjTK3/hzNN8x7gfCAG2AL0DGN92gMDXa+bALuAnsA04LdhvlZZQKsyZc8Bj7pePwo8GwG/z0PAeeG6ZsBIYCCwraLrBFwDfAIIMAxYH+J6XQlEuV4/61GvBM/9wnTNvP7+XP8/bAFigUTX/7/WUNatzPa/AI+F+rr5iRU19rdWV1r6JQuuG2OKAPeC62FhjDlojNnken0a+B7n+sCRaizgXkV+HnBD+KoCQCqwxxhTmSexg8oYsxo4VqbY13UaC8w3TuuA5iLSPlT1MsYsM8bYXN+uw7kiXcj5uGa+jAUWGGMKjTH7gEyc/x+HvG4iIsAtwHs1dX5f/MSKGvtbqytB39uC6xERZEUkARgArHcVTXJ9LJsTjm4UwADLRCTdtQA9QFtjzEHX60NA2zDUy9OtlP4fMNzXzM3XdYqkv78JOFuCbokisllEvhSREWGqk7ffXyRdsxHAYWPMbo+ykF+3MrGixv7W6krQj0gi0hhYBEw2xpwCXge6Av2Bgzg/UobaJcaYgcDVwEMiMtJzo3F+hgzbPF4RiQHGAP92FUXCNSsn3NfJGxH5I2AD3nUVHQS6GGMGAL8G/ikiTUNcrYj8/ZVxG6UbGSG/bl5iRYlg/63VlaAfkgXXK0NEonH+Et81xvwXwBhz2BhjN8Y4gDepwY+zvhhjDri+HgEWu+pw2P0R0fX1SKjr5eFqYJMx5jBExjXz4Os6hf3vT0TuAq4DbncFCVxdJ3mu1+k4+827hbJefn5/Yb9mACISBYwDFrrLQn3dvMUKavBvra4E/ZIF110txVuBJeGqjKuP8C3ge2PMix7lnn1vNwLbyr63huvVSESauF/jHADchvNa3ena7U7gg1DWq4xSra5wX7MyfF2nJcB418yKYcBJj4/mNU5ERgO/A8YYY855lLcWEavr9flAErA3VPVyndfX728JcKuIxIpIoqtuG0JZN5fLgR3GmFx3QSivm69YQU3+rYVihDoU/3COau/CeVf+Y5jrcgnOj2PfAhmuf9cA7wBbXeVLgPYhrtf5OGdMbAG+c18nIB5YAewGlgMtw3TdGgF5QDOPsrBcM5w3noNAMc5+03t8XSecMyledf3tbQUGh7hemTj7ed1/a2+49r3J9XvOADYB14fhmvn8/QF/dF2zncDVoa6bq/xt4Bdl9g3ZdfMTK2rsb03TMCilVD1SV7p3lFJKBUCDvlJK1SMa9JVSqh7RoK+UUvWIBn2llKpHNOgrpVQ9okFfKaXqkf8HjRCNLNZJL50AAAAASUVORK5CYII=\n",
"text/plain": [
"<Figure size 432x288 with 1 Axes>"
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"c = 1.3\n",
"plt.plot(liste_n, meth2, 'g.', label='méthode 2')\n",
"plt.plot(liste_n, [c*n*log(n) for n in liste_n], label='{:3.2f} nlog(n)'.format(c))\n",
"plt.legend()\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Problème 2 : Composantes connexes et biconnexes"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Site Internet et bases de données"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On s'intéresse dans cette partie à un site Internet d'échange de supports de cours entre enseignant·e·s de NSI. Chaque personne désirant proposer ou récupérer du contenu doit commencer par se créer un compte sur ce site et peut ensuite accéder à du contenu ou en proposer."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 19** Expliquer sommairement la différence entre Internet et le web."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Internet est un réseau (de réseaux) d'ordinateurs permettant de mettre en place plusieurs protocoles de communication.\n",
"\n",
"Le web est un réseau hypertexte qui fonctionne grâce à Internet. Les nœuds de ce réseau sont des pages consultables grâce à un navigateur (comme Firefox, Safari, Opera, ...)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 20** Expliquer deux conséquences du règlement général sur la protection des données (RGPD) sur le site Internet."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ce site repose sur une base de données contenant en particulier trois tables.\n",
"\n",
"- La table `comptes` possède un enregistrement par utilisateur ou utilisatrice, et ses attributs sont :\n",
" - `id`, un identifiant numérique, unique pour chaque compte ;\n",
" - `nom`, le nom de la personne possédant le compte ;\n",
" - et d'autres informations, concernant le mot de passe, l'adresse mail, des préférences sur le site, etc., que nous ne détaillons pas ici.\n",
"- La table `ressources` possède un enregistrement par document téléversé sur le site. Ses attributs sont :\n",
" - `id`, un identifiant numérique, unique pour chaque ressource ;\n",
" - `owner`, l'identifiant de la personne ayant créé la ressource ;\n",
" - `titre`, une chaine de caractères décrivant la ressource ;\n",
" - `type`, chaine de caractères pouvant être `cours`, `ds`, `tp` ou `td`.\n",
"- La table `chargement` mémorise chaque fois qu'un utilisateur télécharge une ressource sur le site. Ses attributs sont :\n",
" - `date`, date du téléchargement, par exemple `'2021-02-28'` pour le 28 février 2021 (on peut utiliser des opérations de comparaison classiques avec ce format) ;\n",
" - `id_u`, identifiant de l'utilisateur qui télécharge la ressource ;\n",
" - `id_r`, identifiant de la ressource téléchargée."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Voici un extrait de chacune de ces tables :\n",
"\n",
"![extrait des trois tables](extrait_tables.png)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 21** Écrire une requête SQL permettant de connaitre le nombre total de ressources de type `cours` présentes sur le site."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"~~~sql\n",
"SELECT COUNT(*) FROM ressources WHERE type = 'cours'\n",
"~~~"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 22** Que fait la requête suivante ?\n",
"\n",
"~~~sql\n",
"SELECT ressources.titre, comptes.nom\n",
"FROM chargement\n",
" JOIN ressources ON ressources.id = chargement.id_r\n",
" JOIN comptes ON comptes.id = chargement.id_u\n",
"ORDER BY chargement.date DESC\n",
"LIMIT 1\n",
"~~~"
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"On obtient une table d'un seul enregistrement contenant le titre de la ressource la plus récemment téléchargée, ainsi que le nom de celui qui a effectué ce téléchargement."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 23** Écrire une requête SQL qui permet de déterminer la liste des triplets $(x, y, n)$, signifiant que la personne possédant l'identifiant $x$ a téléchargé $n$ fois des documents téléversés par la personne possédant l'identifiant $y$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On définit le graphe non-orienté $G(V, E)$ où $V$ est l'ensemble des identifiants de comptes sur le site et $E\\subset V\\times V$ l'ensemble des paires d'identifiants telles que le premier compte a déjà téléchargé des documents téléversés par l'autre et réciproquement. Ainsi, si $(x, y)\\in E$, alors on doit avoir $(y, x)\\in E$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 24** Écrire une requête SQL qui renvoie la table des couples $(x, y)$ de $E$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Composantes connexes"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"L'objectif de cette partie est de déterminer les composantes connexes du graphe $G$ défini à la partie précédente. Dans toute la suite, on notera $|X|$ le cardinal d'un ensemble $X$. On supposera que l'ensemble $V$ est constitué de sommets numérotés par des entiers consécutifs commençant à 0, c’est-à-dire que $V=\\{0,1, . . . ,|V|-1\\}$. On dira que deux sommets $x$, $y$ de $V$ sont voisins lorsque $(x, y)\\in E$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"La requête de la question 24 permet de récupérer le résultat sous forme d'une liste de tuples à deux valeurs. On souhaite avoir plutôt une représentation par listes d'adjacences, à savoir une liste de $|V|$ sous-listes, la $i^e$ sous-liste contenant les voisins du sommet $i$. On illustre ces différentes représentations avec le graphe $G_{ex}$ de la figure 3.\n",
"\n",
"![un graphe exemple](graphe_Gex.png)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ce graphe serait obtenu à la question 24 sous la forme :"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [],
"source": [
"g_ex_a = [\n",
" (0, 1), (0, 2), (0, 3), (1, 0), (1, 4), (1, 8),\n",
" (2, 0), (2, 3), (3, 0), (3, 2), (3, 6),\n",
" (4, 1), (5, 6), (6, 3), (6, 5),\n",
" (7, 9), (8, 1), (9, 7)\n",
"]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Sa représentation par listes d’adjacences serait :"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [],
"source": [
"g_ex_b = [[1, 2, 3], [0, 4, 8], [0, 3],\n",
" [0, 2, 6], [1], [6], [3, 5], [9], [1], [7]\n",
" ]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 25** Écrire une fonction `adjacences(n, li)` qui prend en argument un entier `n` correspondant à $|V|$ et `li`, une liste de couples correspondant à un ensemble $E$ (comme par exemple `g_ex_a`) dans un ordre quelconque, et renvoyant la représentation du graphe $G(V, E)$ sous forme de listes d’adjacences (comme par exemple `g_ex_b`)."
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [],
"source": [
"def adjacences(n, li):\n",
" l_adj = [[] for _ in range(n)]\n",
" for (x, y) in li:\n",
" l_adj[x].append(y)\n",
" return l_adj"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"adjacences(10, g_ex_a) == g_ex_b"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On se donne le programme suivant"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [],
"source": [
"class Arbre():\n",
" def __init__(self, sommet):\n",
" self.sommet = sommet\n",
" self.children = []\n",
" \n",
" def add_child(self, child):\n",
" self.children.append(child)\n",
" \n",
"def parcours(listes_adjacences):\n",
" n = len(listes_adjacences)\n",
" deja_vu = [False] * n\n",
" \n",
" def explorer(i):\n",
" arbre = Arbre(i)\n",
" voisins = listes_adjacences[i]\n",
" for s in voisins:\n",
" if not deja_vu[s]:\n",
" deja_vu[s] = True\n",
" arbre.add_child(explorer(s))\n",
" return arbre\n",
" \n",
" res = []\n",
" for i in range(n):\n",
" if not deja_vu[i]:\n",
" deja_vu[i] = True\n",
" res.append(explorer(i))\n",
" return res "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 26** Quel est le type de la valeur renvoyée par la fonction `parcours` ? Appliquer à la main cette fonction sur la liste d’adjacence `g_ex_b` du graphe $G_{ex}$ de la figure 3, et représenter la valeur de retour de cette fonction. Quel est le nom de ce parcours ?"
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Le type de la valeur renvoyée par la fonction `parcours` est celui de la variable locale `res`. Cette variable est initialisée à une liste vide (ligne 22), et les seules éventuelles modifications se font via la méthode `append` (ligne 26). Le type renvoyé est donc une liste.\n",
"\n",
"On peut ajouter que la liste renvoyée ne contient que des objets de la classe `Arbre`."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 27** Montrer que la complexité de la fonction `parcours` est en $O(|V|+|E|)$. Dans toute la suite, on dira qu'un algorithme ayant cette complexité est *linéaire*."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 28** Rappeler la définition de la connexité d’un graphe."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Un graphe non orienté est connexe si pour tout couple $(x, y)$ de sommets, il existe un chemin menant de $x$ à $y$.\n",
"\n",
"En particulier, un graphe est connexe si et seulement si en partant d'un sommet $x$ quelconque, on peut atteindre n'importe quel autre, autrement dit si l'arbre obtenu par la `explorer(x)` contient tous les sommets du graphe."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 29** Écrire une fonction `connexe(listes_adjacences)` qui renvoie `True` si le graphe décrit par les listes d'adjacences `listes_adjacences` est connexe et `False` sinon."
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [],
"source": [
"def connexe(liste_adjacences):\n",
" return len(parcours(liste_adjacences)) == 1"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"connexe(g_ex_b)"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# sous graphe de G_ex et renommage du sommet 8 en 7\n",
"autre_graphe = [list(g_ex_b[i]) for i in range(9) if i != 7]\n",
"autre_graphe[1][2] = 7\n",
"connexe(autre_graphe)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 30** Écrire une fonction `composantes_connexes(p_graphe)` prenant en argument `p_graphe` le graphe obtenu avec la fonction `parcours` et renvoie les composantes connexes sous forme de liste de listes de sommets."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"**Remarque** la description de l'argument de la fonction demandée dans l'énoncé ne correspond pas à la réponse fournie à la question 26. On répond donc à cette question en considérant que l'argument de la fonction est un graphe décrit pas une liste d'adjacences."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"On commence par une fonction qui renvoie la liste des sommets contenu dans un arbre."
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [],
"source": [
"def liste_noeuds(arbre):\n",
" res = [arbre.sommet]\n",
" for child in arbre.children:\n",
" res.extend(liste_noeuds(child))\n",
" return res"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [],
"source": [
"def composantes_connexes(liste_adjacences):\n",
" return list(map(liste_noeuds, parcours(liste_adjacences)))"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {
"tags": [
"reponse"
]
},
"outputs": [
{
"data": {
"text/plain": [
"[[0, 1, 4, 8, 2, 3, 6, 5], [7, 9]]"
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"composantes_connexes(g_ex_b)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 31** Quelle est la limitation liée au fait que la fonction `explorer`, codée en Python, est récursive ?"
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Par défaut, Python limite à environ 1000 le nombre des appels récursifs à une fonction. Donc si le graphe contient un grand nombre de sommets de sorte qu'on y trouve un chemin contenant plus de 1000 sommets non visités, la fonction `explorer` ne pourra pas accomplir son travail. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Dans toute la suite, lorsqu'une fonction est demandée, on pourra utiliser ou non une fonction récursive, au choix des candidat.e.s."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Graphes biconnexes"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On suppose dans cette partie que $G$ est un graphe connexe. Si $\\forall i\\in [0;k]\\, x_i\\in V$, on appelle *chaine* une suite finie $(x_0, x_1, ... , x_k)$ telle que pour tout $i$, on ait $(x_i, x_{i+1})\\in E$. Cette chaine est un *cycle* lorsque $x_0=x_k$, et c'est de plus un *cycle élémentaire* si tous les sommets $x_0$, ... , $x_{k−1}$ sont distincts deux à deux. On dit que $G(V, E)$ est *biconnexe* lorsque :\n",
"\n",
"- $|V|= 1$ ;\n",
"- $|V|= 2$, $V=\\{a, b\\}$ et $(a, b)\\in E$;\n",
"- ou $|V|\\geq 3$ et pour toute paire $(x, y)\\in V^2$, il existe un cycle élémentaire contenant $x$ et $y$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 32** Montrer qu'un graphe biconnexe est également connexe."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Lorsque $|V|=1\\mbox{ ou }2$, il n'y a pas de distinctions entre la connexité et la biconnexité.\n",
"\n",
"Soit $G=(V, E)$ un graphe à au moins trois sommets, et $x$ et $y$ deux sommets distincts de ce graphe. La biconnexité entraîne l'existence d'un cycle élémentaire $(x_0, x_1, ..., x_k=x_0)$ contenant $x$ et $y$. Il existe deux indices $i$ et $j$ tels que $x_i=x$ et $x_j=y$. On peut toujours supposer que $i<j$. Alors $(x_i=x, x_{i+1}, ..., x_j=y)$ est une chaîne reliant les deux sommets $x$ et $y$. \n",
"\n",
"On est assuré de l'existence d'une chaîne reliant deux sommets quelconques : le graphe est connexe."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 33** Donner un exemple de graphe connexe mais pas biconnexe."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Prenons le graphe à trois sommets et deux arêtes défini par\n",
"\n",
"* $V=\\{a, b, c\\}$ \n",
"* $E=\\{(a, b), (b, c)\\}$.\n",
"\n",
"Ce graphe est évidemment connexe mais pas biconnexe car il n'y a pas de cycle élémentaire contenant les sommets $a$ et $c$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On dit qu'un sommet $x$ de $G$ est un *point d'articulation* lorsque le graphe $G$ privé du sommet $x$ (et des arêtes issues de $x$) n'est plus connexe. Notre objectif dans cette partie est de montrer la propriété suivante si $G(V, E)$ possède au moins 3 sommets :\n",
"\n",
"$G(V, E)$ est biconnexe si et seulement si $G$ ne possède pas de point d’articulation."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"hors_enonce"
]
},
"source": [
"**Remarque** dans un graphe non connexe ayant au moins trois sommets, tous les sommets sont des points d'articulation. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 34** Sur le graphe $G'_{ex}$ de la figure 4, donner les points d’articulations.\n",
"\n",
"![Graphe de la figure 4](graphe_Gprime_ex.png)"
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Les points d'articulation de $G'_{ex}$ sont les sommets 4, 6, 8 et 11."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Dans toute la suite, on considère un graphe $G$ ayant au moins 3 sommets."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 35** Soit $G(V, E)$ possédant un point d'articulation. Montrer que $G$ n'est pas biconnexe."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Soit $a$ un point d'ariculation de $G$, et considérons le graphe $G'$ obtenu en supprimant $a$ de $V$, ainsi que les arêtes dont une extrémité est $a$. Par définition d'un point d'articulation, le graphe $G'$ n'est pas connexe.\n",
"Considérons $x$ et $y$ deux sommets de $G'$ situés dans deux composantes connexes différentes. Alors deux cas de figures se présentent :\n",
"\n",
"1. Les sommets $x$ et $y$ sont dans deux composantes connexes différentes de $G$, et alors $G$ n'est pas connexe et a fortiori pas biconnexe compte-tenu du résultat établi à la question 32.\n",
"2. Les sommets $x$ et $y$ sont dans une même composante connexe de $G$, et alors toute chaîne menant de $x$ à $y$ doit contenir le point d'articulation $a$. Un éventuel cycle contenant $x$ et $y$ aurait alors la forme $(x_0, ..., x_i=x, ..., x_j=y, ..., x_k=x_0)$. De ce cycle on peut extraire deux chaînes reliant $x$ et $y$ : $(x_i, ..., x_j)$ et $(x_j, ..., x_0, ..., x_i)$. Chacune de ces deux chaînes doit contenir $a$ et le cycle ne peut donc pas être élémentaire. Ainsi, $G$ n'est pas biconnexe."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 36** Inversement, supposons $G(V, E)$ un graphe sans point d'articulation, et tel que $|V|\\geq 3$. Considérons deux sommets $x$ et $y$.\n",
"\n",
"1. Justifier qu'il existe une chaine $(x_0=x, x_1, ... , x_k=y)$ dans le graphe.\n",
"2. Montrer qu'il existe un cycle élémentaire contenant $x_0$ et $x_1$.\n",
"3. Pour $i\\geq 1$, on suppose qu'il existe un cycle élémentaire $C$ contenant $x_0$ et $x_i$. Montrer qu'il existe alors un cycle élémentaire contenant $x_0$ et $x_{i+1}$. On pourra distinguer deux cas selon que $C$ contient ou non $x_{i+1}$.\n",
"4. En déduire que $G$ est biconnexe."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"1. Dans un graphe non connexe ayant au moins trois sommets, tous les sommets sont des points d'articulation. Par conséquent si un graphe n'a pas de points d'articulation, il doit être connexe. Cela entraîne l'existence d'une chaîne $(x_0=x, x_1, ... , x_k=y)$ reliant n'importe quel couple $(x, y)$ de points de ce graphe.\n",
"2. $(x_0, x_1, x_0)$ est un cycle élémentaire.\n",
"3. Soit $i\\leq 1$. Supposons qu'il existe un cycle élémentaire $C$ contenant $x_0$ et $x_i$.\n",
" \n",
" * Supposons que $x_{i+1}\\in C$. Alors $C$ est un cycle élémentaire contenant $x_0$ et $x_i+1$.\n",
" * Supposons maintenant que $x_{i+1}\\not\\in C$. Comme $G$ n'a aucun point d'articulation, il existe une chaîne menant de $x_{i+1}$ à $x_0$ sans passer par $x_i$. On peut toujours considérer que cette chaîne est élémentaire (i.e. ne contient que des sommets distincts). On construit alors un cycle élémentaire en extrayant de $C$ une chaîne menant de $x_0$ à $x_i$, puis en poursuivant avec l'arête $(x_i, x_{i+1})$ (qui existe bien dans la chaîne établie au point 1.). Il suffit de terminer le cycle avec la chaîne élémentaire menant de $x_{i+1}$ à $x_0$.\n",
"4. Grâce aux faits établis aux points 2 et 3, on a par induction qu'il existe un cycle élémentaire contenant $x_0$ et $x_i$ pour n'importe quelle valeur de $i$ comprise entre 1 et $k$. En particulier il existe un cycle élémentaire contenant les deux sommets quelconques $x$ et $y$ de $G$. $G$ est donc biconnexe. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 37** Expliquer comment on peut déterminer si un sommet particulier est un point d'articulation à l'aide d'un parcours en profondeur."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Pour déterminer si un sommet $x$ d'un graphe $G$ est un point d'articulation, il suffit de faire un parcours en profondeur à partir sans s'autoriser le repassage par $x$. (Cela revient à initialiser le tableau `deja_vus` à la ligne 11 du code précédent, en mettant la valeur `True` à l'indice correspondant à $x$.)\n",
"\n",
"Alors $x$ est un point d'articulation si et seulement si la liste obtenue a une longueur strictement plus grande que 1."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 38** En déduire un algorithme qui prend en entrée un graphe connexe décrit par ses listes d'adjacences, et détermine si ce graphe est biconnexe en utilisant la propriété précédente. On ne demande pas de programmer cet algorithme en Python. Quelle serait sa complexité en fonction des caractéristiques $|E|$ et $|V|$ du graphe ?"
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Voci la description d'un algorithme permettant de déterminer si un graphe est biconnexe. À chaque étape du TQ on met à jour une variable booléenne `biconnexe` en lui donnant la valeur obtenue par la détermination d\n",
" \n",
" biconnexe = True\n",
" i = 0\n",
" TQ biconnexe et i < |V| faire\n",
" biconnexe = i est un point d'articulation\n",
" i = i+1\n",
" renvoyer biconnexe\n",
" \n",
"Chaque étape du TQ a un coût linéaire, donc en $O(|V| + |E|)$. Le nombre d'étapes du TQ est au maximum égal à $|V|$. Le coût global de cet algorithme pour déterminer le caractère biconnexe d'un graphe est donc $O\\left(|V|(|V|+|E|)\\right)$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Algorithme efficace pour déterminer les points d’articulation"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Dans cette partie, on détaille comment déterminer tous les points d'articulation d'un graphe $G(V, E)$ avec une complexité linéaire."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On modifie le programme `parcours` pour lui faire remplir et renvoyer une liste `prefixe` correspondant aux ordres d'appel de la fonction `explorer`. De plus, on suppose désormais que `listes_adjacences` décrit un graphe connexe, et on ne renverra qu'un seul arbre, issu de l'exploration à partir du sommet 0, et la liste `prefixe`. On utilise `nonlocal` pour que la variable `count` soit définie pour toute la fonction `parcours` et pas uniquement au sein de la fonction `explorer`."
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {},
"outputs": [],
"source": [
"def parcours(listes_adjacences):\n",
" n = len(listes_adjacences)\n",
" deja_vu = [False] * n\n",
" prefixe = [-1] * n\n",
" count = 1\n",
" \n",
" def explorer(i):\n",
" nonlocal count\n",
" prefixe[i] = count\n",
" count += 1\n",
" arbre = Arbre(i)\n",
" voisins = listes_adjacences[i]\n",
" for s in voisins:\n",
" if not deja_vu[s]:\n",
" deja_vu[s] = True\n",
" arbre.add_child(explorer(s))\n",
" return arbre\n",
" deja_vu[0] = True\n",
" return explorer(0), prefixe"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 39** Donner les valeurs de la liste `prefixe` renvoyée par le programme ci-dessus si on l'applique sur le graphe $G'_{ex}$ de la figure 4. On supposera que les voisins sont rangés par ordre croissant de leur numéro dans les listes d'adjacences."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"La figure ci-dessous montre l'arbre des appels récursifs à la fonction `explorer` sur l'exemple du graphe $G'_{ex}$. Les nombres dans les cases encadrées sont les numéros des sommets transmis à la fonction `explorer` dans les différents appels. (Les pointillés infiquent les appels récursifs non envisagés pour cause de sommet déjà vu.) En rouge à côté des sommets, figurent les valeurs de la variable `count` lors de l'appel à la fonction `explorer`, valeur qui sera inscrite dans la liste `prefixe`.\n",
"\n",
"![arbre des appels à explorer](arbre_appels_recursifs_parcours.png)\n",
"\n",
"Ainsi la liste `prefixe` obtenue finalement est\n",
"\n",
" [1, 2, 3, 10, 11, 5, 4, 8, 9, 12, 6, 7, 13]\n",
" \n",
"**Remarque** à noter que la liste porte bien son nom puisqu'elle donne pour chaque sommet son rang dans un parcours préfixe de l'arbre."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 40** Soit $G$ un graphe connexe dans lequel on réalise le parcours avec la fonction ci-dessus, et soit $(i, j)$ une arête de $G$ telle que `prefixe[i] < prefixe[j]`. Montrer que $j$ est un descendant de $i$ dans l'arbre."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Considérons une arête $(i, j)$ de $G$ telle que $\\mathtt{prefixe}[i] < \\mathtt{prefixe}[j]$.\n",
"\n",
"On déduit de cette inégalité que dans le parcours, le sommet $i$ a été rencontré avant le sommet $j$. Au début de l'évaluation de $\\mathtt{explorer}(i)$, $j$ n'a donc pas été déjà vu. Mais il le sera durant cette évaluation parce que $j$ est un voisin de $i$. Et donc $j$ apparaît parmi les successeurs de $i$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Pour chaque sommet $i$, on note $\\mathcal{V}(i)$ le voisinage de $i$, c'est-à-dire l'ensemble constitué de $i$ et de ses voisins. Par extension, pour tout $A\\subset V$, on notera $\\mathcal{V}(A) = \\cup_{i\\in A}\\mathcal{V}(i)$. En supposant réalisé un parcours dans l'arbre, on notera de plus $\\mathcal{D}(i)$ l'ensemble des descendants de $i$ dans l'arbre. Enfin, on définit $\\mathtt{ord}[i]$ par :\n",
"\n",
"$$ \\mathtt{ord}[i] = \\min_{j\\in \\mathcal{V}(\\mathcal{D}(i))} \\mathtt{prefixe}[j].$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 41** Sur le graphe $G'_{ex}$ de la figure 4, donner pour chaque sommet les valeurs de $\\mathtt{ord}[i]$, en se basant sur les valeurs obtenues à la question 39."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"En considérant qu'un sommet d'un arbre fait partie de ses descendants :\n",
"\n",
" ord = [1, 1, 1, 9, 9, 4, 1, 7, 8, 11, 5, 4, 9]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On admettra qu'un sommet $i$ du graphe qui n'est pas la racine est un point d'articulation si et seulement si un de ses fils $j$ vérifie $\\mathtt{ord}[j] = \\mathtt{prefixe}[i]$. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Qu'appelle-t-on racine d'un graphe ? Fils d'un sommet ?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On supposera de plus qu'on dispose d'une fonction `calcule_ord(listes_adjacences)` qui renvoie la liste des $\\mathtt{ord}[i]$ du graphe décrit par `listes_adjacences`, avec une complexité linéaire."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 42** Écrire une fonction `points_articulation(listes_adjacences)` qui renvoie la liste des points d'articulation d'un graphe. On fera attention à traiter la racine de l'arbre comme un cas particulier."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"~~~python\n",
"def points_articulation(liste_adjacences):\n",
" arbre, prefixe = parcours(liste_adjacences)\n",
" ord = calcule_ord(liste_adjacences)\n",
" \n",
"~~~"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On définit une composante biconnexe d'un graphe $G$ comme un sous-ensemble de sommets maximal (au sens de l'inclusion) qui est biconnexe."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 43** Sur le graphe $G'_{ex}$ de la figure 4, donner la liste des composantes biconnexes."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"reponse"
]
},
"source": [
"Les composantes biconnexes de $G'_{ex}$ sont les sous-graphes induits par les sous-ensembles suivants de sommets :\n",
"\n",
"* $\\{0, 1, 2, 5, 6, 10\\}$,\n",
"* $\\{6, 11\\}$,\n",
"* $\\{7, 8, 11\\}$,\n",
"* $\\{8, 12\\}$,\n",
"* $\\{3, 4, 8\\}$,\n",
"* $\\{4, 9\\}$.\n",
"\n",
"**Remarque** contrairement aux composantes connexes, deux composantes biconnexes distinctes peuvent contenir un même sommet. Ces sommets figurant dans deux composantes biconnexes distinctes sont les points d'articulation.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Question 44** Décrire un algorithme qui renvoie les composantes biconnexes d'un graphe avec une complexité linéaire. On ne demande pas de programmer cet algorithme."
]
},
{
"cell_type": "code",
"execution_count": null,
"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.7.3"
},
"toc-autonumbering": true,
"toc-showcode": false,
"widgets": {
"application/vnd.jupyter.widget-state+json": {
"state": {},
"version_major": 2,
"version_minor": 0
}
}
},
"nbformat": 4,
"nbformat_minor": 4
}
Reference in New Issue View Git Blame Copy Permalink