{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Tas binomiaux\n", "\n", "Marc Lorenzi\n", "\n", "6 juillet 2019" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "import random\n", "import math" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "plt.rcParams['figure.figsize'] = (20, 8)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Un tas est un ensemble d'objets auxquels sont assignées des __priorités__. On doit pouvoir effectuer sur un tas les opérations suivantes :\n", "\n", "- Tester si un tas est vide.\n", "- Déterminer un objet de priorité minimale.\n", "- Insérer un objet de priorité donnée.\n", "- Supprimer un objet de priorité minimale.\n", "\n", "Une dernière opération s'avérera ici cruciale. Nous voudrions aussi pouvoir\n", "\n", "- Fusionner deux tas.\n", "\n", "Il va de soi que l'on désire pouvoir effectuer ces opérations le plus rapidement possible ! Il existe différentes implémentations de la structure de tas. Les tas que nous étudierons ici s'appellent les __tas binomiaux__. Mis à part le test \"le tas est-il vide ?\", qui s'effectuera en $O(1)$, toutes les autres opérations seront réalisées en temps $O(\\lg n)$ où $n$ est le nombre d'objets dans le tas. On pourra également dire mieux pour l'opération d'insertion. Patience ...\n", "\n", "Avant de parler de tas binomiaux, intéressons-nous aux __arbres binomiaux__." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1. Arbres binomiaux" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.1 Les arbres, leur représentation en Python" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Nous allons considérer tout au long de ce notebook des arbres. Sans entrer dans une théorie sans fin, un arbre est soit \"vide\", soit non vide. S'il n'est pas vide, il est composé d'une __racine__, qui possède une valeur, et de zéro, un ou plusieurs __fils__ qui sont eux mêmes des arbres.\n", "\n", "Nous représenterons en Python\n", "\n", "- L'arbre vide par `None`.\n", "- Un arbre non vide de racine de valeur $x$ et de fils $t_0,\\ldots,t_{k-1}$ par le couple $(x,[t_0,\\ldots,t_{k-1}])$ formé de la valeur de la racine et de la liste des fils (qui peut être vide).\n", "\n", "Enfin nous confondrons dans le langage courant la racine avec sa valeur, les fils de l'arbre avec leurs racines, etc. Si peu de rigeur peut faire peur, mais normalement cela ne devrait pas poser de problème." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def est_vide(t): return t == None\n", "def racine(t): return t[0]\n", "def fils(t): return t[1]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.2 Qu'est-ce qu'un arbre binomial ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour tout entier naturel $n$ nous allons définir par récurrence sur $n$ ce qu'est un arbre binomial d'ordre $n$.\n", "\n", "- Un arbre binomial d'ordre 0 est constitué d'une simple racine et n'a pas de fils.\n", "- Soit $n\\in\\mathbb N$. Soit $t=(x,[t_0,\\ldots,t_{k-1}])$ un arbre non vide. On dit que $t$ est un arbre binomial d'ordre $n+1$ lorsque\n", "\n", " - $t_{k-1}$ est un arbre binomial d'ordre $n$.\n", " - $(x, [t_0,\\ldots,t_{k-2}])$ est un arbre binomial d'ordre $n$.\n", " - La racine de $t_{k-1}$ a une valeur supérieure ou égale à $x$.\n", " \n", "Un arbre binomial d'ordre $n+1$ est donc fabriqué en \"recollant\" deux arbres binomiaux d'ordre $n$. Voici la fonction qui colle les arbres :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def coller_arbres(t1, t2):\n", " if racine(t1) <= racine(t2):\n", " fils(t1).append(t2)\n", " return t1\n", " else:\n", " fils(t2).append(t1)\n", " return t2" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "t1 = coller_arbres((4,[]),(7,[]))\n", "t2 = coller_arbres((5,[]),(3,[]))\n", "t3 = coller_arbres((1,[]),(2,[]))\n", "t4 = coller_arbres((6,[]),(8,[]))\n", "t = coller_arbres(t1, t2)\n", "u = coller_arbres(t3, t4)\n", "v = coller_arbres(t, u)\n", "print(v)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Remarque__ : La fonction ci-dessus modifie __physiquement__ l'arbre $t_1$ (ou $t_2$, cela dépend). Pour ce que nous allons faire dans ce notebook cela ne pose pas de problème. En revanche, dans certaines applications cela peut être dramatique : dans l'opération de recollement, l'un des deux arbres est perdu irrémédiablement, et en plus on ne sait pas lequel." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Proposition__ : La complexité de la fonction `coller_arbres` est $O(1)$.\n", "\n", "__Démonstration__ : Évident, à condition d'admettre que la fonction Python `append` s'exécute en $O(1)$. En réalité ce n'est pas tout à fait exact, mais ceci est une autre histoire ..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Histoire de pouvoir manipuler de \"gros\" arbres binomiaux, voici une fonction qui renvoie un arbre binomial d'ordre $n$. La valeur des noeuds n'a pas d'importance, j'ai mis 0 parce qu'il fallait mettre quelque chose." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def test_binomial(n):\n", " if n == 0: return (0, [])\n", " else:\n", " t1 = test_binomial(n - 1)\n", " t2 = test_binomial(n - 1)\n", " return coller_arbres(t1, t2)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(test_binomial(6))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Beurk. Écrivons illico une fonction qui écrit un arbre $t$ de façon un peu plus jolie.\n", "\n", "- Si $t$ est vide, la fonction affiche $\\_$.\n", "- Sinon, elle affiche\n", " - La racine de $t$,\n", " - puis, entre parenthèses et séparés par des virgules, les fils de la racine." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def arbre_vers_chaine(t):\n", " if t == None: s = '_'\n", " else:\n", " s = str(racine(t))\n", " fs = fils(t)\n", " if fs != []:\n", " s += '('\n", " n = len(fs)\n", " for k in range(n):\n", " s += arbre_vers_chaine(fs[k])\n", " if k < n - 1: s += ','\n", " s += ')'\n", " return s" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def print_arbre(t): print(arbre_vers_chaine(t))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print_arbre(test_binomial(6))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ah oui, c'est beaucoup mieux. Comme nous pouvons le voir sur l'exemple ci-dessus :-) nous avons le résultat suivant :" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Proposition__ : Soit $t$ un arbre binomial d'ordre $n$. (La racine de) $t$ a exactement $n$ fils.\n", "\n", "__Démonstration__ : Faisons une récurrence sur $n$.\n", "\n", "- Pour $n=0$, c'est évident. La racine d'un arbre binomial d'ordre 0 n'a pas de fils.\n", "- Soit $n\\in\\mathbb N$. Supposons la propriété vraie pour $n$. Soit $t$ un arbre binomial d'ordre $n+1$. $t$ a été obtenu en recollant deux arbres binomiaux d'ordre $n$, $t_1$ et $t_2$. Pour fixer les idées, supposons que la racine de $t_2$ est inférieure à celle de $t_1$. Les fils de la racine de $t$ sont donc :\n", "\n", " - Les fils de $t_2$ : il y en a $n$ par l'hypothèse de récurrence.\n", " - $t_1$.\n", "\n", "La racine de $t$ a donc $n+1$ fils. On en déduit une fonction `ordre` qui renvoie en temps $O(1)$ l'ordre d'un tas binomial. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def ordre(t): return len(fils(t))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "ordre(test_binomial(10))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour s'entraîner aux récurrences et se familiariser avec les arbres binomiaux, voici deux exercices faciles.\n", "\n", "__Exercice__ Montrez que la racine d'un arbre binomial est le plus petit noeud de l'arbre.\n", "\n", "__Exercice__ : Soit $t$ un arbre binomial d'ordre $n$. Montrez que les $n$ fils de $t$ sont, de gauche à droite, un arbre binomial d'ordre 0, un arbre binomial d'ordre 1, ..., un arbre binomial d'ordre $n-1$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Si vous regardez le résultat affiché par `print_arbre(test_binomial(6))`, vous pouvez avoir un micro-doute : ceci est-il bien un arbre binomial ? Écrivons une fonction qui prend un arbre en paramètre et renvoie `True` si c'est un arbre binomial et `False` sinon." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def est_arbre_binomial(t):\n", " if t[1] == []: return True\n", " else:\n", " t1 = (racine(t), fils(t)[:-1])\n", " t2 = fils(t)[-1]\n", " return est_arbre_binomial(t1) and est_arbre_binomial(t2) \\\n", " and racine(t1) <= racine(t2) and ordre(t1) == ordre(t2)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "est_arbre_binomial(test_binomial(6))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.3 Hauteur d'un arbre binomial" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Définition__ : La hauteur $h(t)$ d'un arbre $t$ est définie inductivement comme suit :\n", "\n", "- L'arbre vide a pour hauteur 0.\n", "- Si $t$ n'a pas de fils, $h(t)=1$.\n", "- Si $t$ est un arbre possédant $k$ fils $t_0,\\ldots,t_{k-1}$,\n", "\n", "$$h(t)=1+\\max(h(t_0),\\ldots,h(t_{k-1}))$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Proposition__ : La hauteur d'un arbre binomial d'ordre $n$ est $n+1$.\n", "\n", "__Démonstration__ : Une récurrence sur $n$, encore !\n", "\n", "- Un arbre binomial d'ordre 0 est de hauteur 1.\n", "- Soient $t_1,t_2$ deux arbres binomiaux d'ordre $n$. Soit $t$ l'arbre obtenu en recollant $t_1$ et $t_2$. Les fils de $t$ sont, par exemple, $t_1$ et les fils de $t_2$. Par l'hypothèse de récurrence, $h(t_1)=n+1$ et les fils de $t_2$ sont de hauteur inférieure ou égale à $n$, puisque $h(t_2)=n+1$. Donc, le max des hauteurs des fils de $t$ est $n+1$ (la hauteur de $t_1$) et ainsi, $h(t)=n+2$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def hauteur(t):\n", " if t == None: return 0\n", " else:\n", " fs = fils(t)\n", " h = 0\n", " for f in fs:\n", " h = max(h, hauteur(f))\n", " return h + 1" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(hauteur(test_binomial(16)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.4 Représentation graphique" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Il est très intéressant de visulaiser les arbres binomiausx, car ils ont des formes très remarquables. Je n'entre pas dans le détails des deux fonctions ci-dessous. La fonction `dessin_aux` est appelée par `dessin_arbre_binomial` pour dessiner l'allure d'un arbre binomial d'ordre $n$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def dessin_aux(t, xmin, xmax, ymin, ymax, dy):\n", " r = racine(t)\n", " fs = fils(t)\n", " n = len(fs)\n", " xm = (xmin + xmax) / 2\n", " for k in range(n):\n", " x1 = xmin + k * (xmax - xmin) / n\n", " x2 = xmin + (k + 1) * (xmax - xmin) / n\n", " xmm = (x1 + x2) / 2\n", " plt.plot([xmin, x1], [ymax, ymax - dy], 'k')\n", " dessin_aux(fs[k], x1, x2, ymin, ymax - dy, dy)\n", " plt.plot([xmin], [ymax], 'or', markersize=6)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def dessin_arbre_binomial(n):\n", " t = test_binomial(n)\n", " h = hauteur(t)\n", " dy = 10 / h\n", " plt.xlim(0, 10)\n", " plt.ylim(0, 10)\n", " plt.axis('off')\n", " dessin_aux(t, 1, 9, 1, 9, dy)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Voici par exemple un arbre binomial d'ordre 5." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "dessin_arbre_binomial(5)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Si vous avez fait les exercices proposés, vous savez que avez en prime, sous la racine, des arbres binomiaux d'ordres 0, 1, 2, 3 et 4. Et sous les racines de ces arbres, d'autres arbres binomiaux. Etc.\n", "\n", "Combien de noeuds (c'est à dire de points rouges) ? Il y en a 32. \n", "\n", "Combien de noeuds à chaque niveau ? 1, 5, 10, 10, 5, 1. Bigre, sont-ce des coefficients binomiaux ? La reste de cette section est là pour prouver que les tas binomiaux portent bien leur nom." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.6 Nombre de noeuds d'un arbre binomial" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Proposition__ : Un arbre binomial d'ordre $n$ possède $2^n$ noeuds.\n", "\n", "__Démonstration__ : On fait une récurrence sur $n$.\n", "\n", "- Un arbre binomial d'ordre 0 a $1=2^0$ noeud.\n", "- Supposons la propriété vraie pour l'entier $n$. Soit $t$ un arbre binomial d'ordre $n+1$. L'arbre $t$ est obtenu en recollant deux arbres binomiaux d'ordre $n$. Par l'hypothèse de récurrence, chacun de ces deux arbres possède $2^n$ noeuds. Le nombre de noeuds de $t$ est donc\n", "\n", "$$2^n+2^n=2^{n+1}$$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def nombre_noeuds(t):\n", " if t == None: return 0\n", " else:\n", " n = 1\n", " for f in fils(t):\n", " n = n + nombre_noeuds(f)\n", " return n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "nombre_noeuds(test_binomial(16))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.6 Nombre de noeuds de profondeur donnée" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Nous y voici. Nous allons enfin comprendre pourquoi un arbre binomial est appelé \"binomial\".\n", "\n", "La profondeur d'un noeud dans l'arbre $t$ est la distance de la racine de $t$ à ce noeud. Pour faire concret, voyez le dessin de l'arbre. Comptez le nombre de traits entre la racine de l'arbre et le noeud qui vous intéresse : c'est cela, la profondeur. Ainsi, la racine est de profondeur 0, les (racines des) fils de la racine sont de profondeur 1, etc. Un arbre binomial d'ordre $n$ est de hauteur $n+1$. Il possède donc des noeuds aux profondeurs $0, 1,\\ldots,n$. Combien un arbre binomial a-t-il de noeuds à une profondeur donnée ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Proposition__ : Soit $t$ un arbre binomial d'ordre $n$. Soit $0\\le k\\le n$. À la profondeur $k$, l'arbre $t$ possède exactement $\\binom n k$ noeuds.\n", "\n", "On comprend enfin pourquoi un tel arbre est dit binomial.\n", "\n", "__Démonstration__ : Une récurrence s'impose.\n", "\n", "- Pour $n=0$ c'est évident.\n", "- Soit $n\\in\\mathbb N$. Supposons la propriété vraie pour $n$. Soit $t$ un arbre binomial d'ordre $n+1$, obtenu en recollant deux arbres binomiaux $t_1$ et $t_2$ d'ordre $n$. Par exemple, les fils de $t$ sont les fils de $t_2$, suivis de $t_1$ (et la racine de $t$ est celle de $t_2$). Soit $1\\le k\\le n$. Les noeuds de $t$ à la profondeur $k$ sont :\n", "\n", " - Les noeuds de $t_1$ à la profondeur $k-1$. Il y en a $\\binom n {k-1}$ par l'hypothèse de récurrence.\n", " - Les noeuds de $t_2$ à la profondeur $k$. Il y en a $\\binom n {k}$ par l'hypothèse de récurrence.\n", " \n", "Le nombre de noeuds de $t$ à la profondeur $k$ est donc\n", "\n", "$$\\binom n {k-1} + \\binom n k=\\binom {n+1}k$$\n", "\n", "__Exercice__ : Il reste à voir ce qui se passe pour $k=0$ et $k=n+1$.\n", "\n", "__Corollaire__ : $\\sum_{k=0}^n \\binom n k = 2 ^n$.\n", "\n", "__Démonstration__ : Additionnez les nombres de noeuds à chaque profondeur, vous obtiendrez le nombre total de noeuds de l'arbre." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. Tas binomiaux" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Rappelons-nous que les éléments d'un tas sont des __objets__ munis d'une __priorité__. Pour simplifier la présentation qui va suivre, nous allons laisser de côté les objets. Les éléments d'un tas seront donc simplement des priorités, que nous supposerons être des __entiers__. Le lecteur qui veut à tout prix que son tas contienne aussi des objets remplacera tous les éléments du tas par des couples formés d'un objet et d'un entier." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2.1 C'est quoi ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Définition__ : Soit $n\\ge 0$. Soit $h=[t_0,\\ldots,t_{n}]$ une liste d'arbres. On dit que $h$ est un tas binomial lorsque, pour tout entier $0\\le k\\le n$, $t_k$ est soit l'arbre vide, soit un tas binomial d'ordre $k$. Nous ferons de plus l'hypothèse que $t_{n}$ n'est pas vide.\n", "\n", "On convient également que la liste vide $[]$ est un tas binomial. Nous l'appellerons le tas vide.\n", "\n", "L'entier $n+1$ est appelé la longueur du tas. Le tas vide est de longueur 0." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Notation__ : Pour un tas $h$ ou un arbre $t$ nous noterons $|h|$ (ou $|t|$) le nombre de noeuds du tas (ou de l'arbre)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Proposition__ : Soit $n\\in\\mathbb N$. Soit $h$ un tas binomial de longueur $n+1$. On a\n", "\n", "$$2^{n}\\le |h|< 2^{n+1}$$\n", "\n", "et donc\n", "\n", "$$n=\\lfloor \\lg |h|\\rfloor$$\n", "\n", "où $\\lg$ désigne le logarithme en base 2 et les crochets désignent la partie entière.\n", "\n", "__Démonstration__ : Pour $k=0,\\ldots,n$, posons $a_k=0$ si $t_k$ est vide, et $a_k=1$ sinon. Rappelons nous que $a_n=1$ puisque $t_n$ n'est pas vide. On a \n", "\n", "$$|h|=\\sum_{k=0}^{n}|t_k|=\\sum_{k=0}^{n}a_k2^k$$\n", "\n", "Majorons :\n", "\n", "$$|h|\\le\\sum_{k=0}^{n}2^k=2^{n+1}-1<2^{n+1}$$\n", "\n", "Minorons :\n", "\n", "$$|h|\\ge a_n2^n=2^n$$\n", "\n", "En passant au logarithme, on obtient\n", "\n", "$$n\\le \\lg |h| n$ il n'y en a pas.\n", "- Si $2^j\\le n$, c'est à dire $j\\le\\lfloor\\lg n\\rfloor$, il y en a $\\left\\lfloor\\frac{n}{2^{j+1}}+\\frac 1 2\\right\\rfloor$.\n", "\n", "Ainsi,\n", "\n", "$$\\mathcal C = \\sum_{j=0}^{\\lfloor\\lg n\\rfloor}j\\left\\lfloor\\frac{n}{2^{j+1}}+\\frac 1 2\\right\\rfloor$$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def complexite_theorique(n):\n", " s = 0\n", " p = math.floor(math.log(n, 2))\n", " for j in range(p + 1):\n", " s = s + j * math.floor(n / 2 ** (j + 1) + 1/ 2)\n", " return s" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "complexite_theorique(100)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Majorons l'horrible somme $\\mathcal C$ ci-dessus. On a\n", "\n", "$$\\mathcal C \\le \\sum_{j=0}^{\\lfloor\\lg n\\rfloor}j\\left(\\frac{n}{2^{j+1}}+\\frac 1 2\\right)$$\n", "\n", "D'une part,\n", "\n", "$$\\sum_{j=0}^{\\lfloor\\lg n\\rfloor}\\frac j 2\\le \\frac 1 2\\lfloor\\lg n\\rfloor^2=o(n)$$\n", "\n", "D'autre part,\n", "\n", "$$\\sum_{j=0}^{\\lfloor\\lg n\\rfloor}\\frac{nj}{2^{j+1}}\\le Sn$$\n", "\n", "où \n", "\n", "$$S=\\sum_{j=0}^{\\infty}\\frac{j}{2^{j+1}}$$\n", "\n", "est la somme d'une série convergente. Ainsi, on a \n", "\n", "$$\\mathcal C\\le Sn+o(n)$$\n", "\n", "et donc, bien évidemment,\n", "\n", "$$\\mathcal C = O(n)$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.6 Tests" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Les calculs que nous venons de faire, personne n'y croit n'est-ce pas ? Avec toutes ces parties entières de fractions de logarithmes de puissances de 2, on a bien dû se tromper quelque part ??? Alors faisons quelques tests.\n", "\n", "Définissons tout d'abord un compteur global." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "compteur = 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Modifions légèrement la fonction `inserer` pour qu'elle incrémente le compteur à chaque appel à `coller_arbres`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def inserer_test(x, h):\n", " global compteur\n", " r = (x, [])\n", " k = 0\n", " n = len(h)\n", " while k < n and r != None:\n", " if h[k] == None:\n", " h[k] = r\n", " r = None\n", " else:\n", " r = coller_arbres(r, h[k])\n", " compteur += 1\n", " h[k] = None\n", " k = k + 1\n", " if r != None: h.append(r)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Écrivons enfin une fonction qui renvoie la liste des valeurs du compteur lors de $n$ insertions dans un tas initialement vide. Ou, si l'on préfère les valeurs du compteur divisées par le numéro de l'insertion, c'est à dire les complexités \"moyennes\" pour $k$ insertions." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def test_complexite(n, moy=False):\n", " global compteur\n", " compteur = 0\n", " h = []\n", " cs = []\n", " for k in range(1, n + 1):\n", " inserer_test(0, h)\n", " if moy: cs.append(compteur / k)\n", " else: cs.append(compteur)\n", " return cs" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "cs1 = test_complexite(200)\n", "print(cs1)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "cs2 = [complexite_theorique(k) for k in range(1, 201)]\n", "print(cs2)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "cs1 == cs2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Youpi, théorie rigoureusement identique à la réalité. Les mauvaises langues s'en souviendront la prochaine fois :-).\n", "\n", "Dessinons ..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "cs = test_complexite(100, moy=False)\n", "plt.plot(cs, 'k')\n", "plt.grid()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Dessinons aussi la courbe de la \"complexité moyenne\"." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "cs = test_complexite(100, moy=True)\n", "plt.plot(cs, 'k')\n", "plt.grid()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Exercice__ : Réévaluez les deux cellules ci-dessus pour 10000 insertions. Une idée de la valeur de $S$, la somme de la série vue plus haut ? Grosse flemme ? Lisez la suite :-)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Proposition__ : \n", "\n", "$$\\sum_{j=0}^\\infty\\frac{j}{2^{j+1}}=1$$\n", "\n", "__Démonstration__ : Considérons la série entière \n", "$$f(x)=\\frac 1 2\\sum_{j=0}^\\infty \\left( \\frac x 2\\right)^j$$\n", "\n", "Cette série a pour rayon de convergence 2. La fonction $f$ est donc dérivable sur $]-2,2[$ et on a pour tout $x\\in]-2,2[$\n", "\n", "$$f'(x)=\\frac 1 2\\sum_{j=1}^\\infty \\frac j {2^j}x^{j-1}$$\n", "\n", "et donc\n", "\n", "$$\\sum_{j=0}^\\infty\\frac{j}{2^{j+1}}=f'(1)$$\n", "\n", "Par ailleurs, \n", "\n", "$$f(x)=\\frac 1 2\\frac{1}{1-\\frac x 2}=\\frac{1}{2-x}$$\n", "\n", "donc\n", "\n", "$$f'(x)=\\frac 1 {(2-x)^2}$$\n", "\n", "d'où $f'(1)=1$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 4. Fusion de deux tas binomiaux" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4.1 L'addition des entiers naturels" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Avant de fusionner des tas, faisons quelques petits rappels sur ... l'addition des entiers naturels.\n", "\n", "Tout entier naturel $a$ s'écrit de façon unique\n", "\n", "$$a=\\sum_{k=0}^\\infty a_k2^k$$\n", "\n", "où les $a_k\\in\\{0,1\\}$ sont tous nuls sauf un nombre fini.\n", "\n", "Soient $a=\\sum_{k=0}^\\infty a_k2^k$ et $b=\\sum_{k=0}^\\infty b_k2^k$ deux entiers. Soit $c=a+b=\\sum_{k=0}^\\infty c_k2^k$. Que valent les $c_k$ en fonction des $a_k$ et des $b_k$ ? C'est facile, mais attention aux retenues.\n", "\n", "Posons $r_0=0$ et, pour tout $k\\ge 0$, \n", "\n", "$$r_{k+1}=(a_k+b_k+r_k)\\div 2$$\n", "\n", "où le symbole $\\div$ désigne le quotient de la division euclidienne. On a alors\n", "\n", "$$\\forall k\\in\\mathbb N, c_k=(a_k+b_k+r_k)\\bmod 2$$\n", "\n", "Pour préparer le terrain pour la fusion des tas, il y a 8 cas, résumés dans le tableau ci-dessous." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\\begin{array}{|c|c|c|c|c|c|c|}\n", "\\hline \n", "&a_k&b_k&r_k&\\Rightarrow& c_k& r_{k+1}\\\\\n", "\\hline\n", "1&0&0&0&& 0&0\\\\\n", "\\hline\n", "2&0&1&0&&1&0\\\\\n", "\\hline\n", "3&1&0&0&&1&0\\\\\n", "\\hline\n", "4&1&1&0&&0&1\\\\\n", "\\hline\n", "5&0&0&1&&1&0\\\\\n", "\\hline\n", "6&1&0& 1&&0&1\\\\\n", "\\hline\n", "7&0&1& 1&& 0& 1\\\\\n", "\\hline\n", "8&1&1&1&&1&1\\\\\n", "\\hline\n", "\\end{array}$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Représentons les entiers naturels en Python par la liste de leurs chiffres binaires, le chiffre des unités étant le premier élément de la liste. Bien évidemment nos listes sont finies et notre belle description théorique est un peu mise à mal. Alors commençons par définir une fonction `chiffre`. Elle prend en paramètres une liste $a$ d'entiers et un entier $k$.\n", "\n", "- Si $k$ est strictement inférieur à la longueur de $a$, la fonction renvoie $a[k]$.\n", "- Sinon, la fonction renvoie 0.\n", "\n", "Avec cette petite astuce tout se passe donc comme si $a$ était une liste infinie." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def chiffre(a, k):\n", " if k < len(a): return a[k]\n", " else: return 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Voici maintenant la fonction `somme_entiers`. Elle reprend ce qui a été dit plus haut. Remarquez que la longueur de $a+b$ est le maximum des longueurs de $a$ et de $b$, plus, peut-être, 1, s' il y a une retenue sur la somme des derniers chiffres. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def somme_entiers(a, b):\n", " n = max(len(a), len(b))\n", " c = n * [0]\n", " r = 0 \n", " for k in range(n):\n", " ak = chiffre(a, k)\n", " bk = chiffre(b, k)\n", " w = (ak, bk, r)\n", " if w == (0, 0, 0): c[k], r = 0, 0\n", " elif w == (0, 1, 0): c[k], r = 1, 0\n", " elif w == (1, 0, 0): c[k], r = 1, 0\n", " elif w == (1, 1, 0): c[k], r = 0, 1\n", " elif w == (0, 0, 1): c[k], r = 1, 0\n", " elif w == (1, 0, 1): c[k], r = 0, 1\n", " elif w == (0, 1, 1): c[k], r = 0, 1\n", " else: c[k], r = 1, 1\n", " if r != 0: c.append(r)\n", " return c" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "somme_entiers([0, 1, 1], [1, 1, 1])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4.2 Fusion" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pourquoi cette digression sur la somme de deux entiers naturels, me direz vous ? Eh bien parce que un tas binomial \"ressemble\" beaucoup à un entier naturel. La fonction `fusionner` aura une forte ressemblance avec `somme_entiers`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction ci-dessous est à comparer à la fonction `chiffre` ..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def element_tas(a, k):\n", " if k < len(a): return a[k]\n", " else: return None" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Et voici la fonction de fusion. Soient $a=(a_k)_{k\\ge 0}$ et $b=(b_k)_{k\\ge 0}$ deux tas binomiaux où, pour tout entier $k$, $a_k$ et $b_k$ sont des arbres binomiaux d'ordre $k$, ou l'arbre vide. On suppose également, cela va de soi, que les $a_k$ et les $b_k$ sont tous vides sauf un nombre fini. Comment fusionner $a$ et $b$ ? Notons $c=(c_k)_{k\\ge 0}$ le tas binomial que nous allons fabriquer.\n", "\n", "Si $t$ et $t'$ sont deux arbres binomiaux de même ordre $n$, notons $t\\oplus t'$ l'arbre binomial d'ordre $n+1$ obtenu en recollant $t$ et $t'$. Notons également $\\emptyset$ l'arbre vide.\n", "\n", "On fabrique par récurrence sur $k$ les $c_k$ ainsi qu'une suite de retenues $(r_k)_{k\\ge 0}$ où $r_k$ est un arbre binomial d'ordre $k$, ou l'arbre vide.\n", "\n", "Posons $r_0=\\emptyset$. Soit maintenant $k\\in\\mathbb N$. On dispose de $a_k$, $b_k$ et $r_k$ qui sont des arbres binomiaux d'ordre $k$, ou l'arbre vide.\n", "\n", "- Si ces trois arbres sont vides, on pose $c_k=\\emptyset$ et $r_{k+1}=\\emptyset$.\n", "- Si deux de ces arbres sont vides, on pose $c_k=$ celui des trois qui est non vide et $r_{k+1}=\\emptyset$.\n", "- Si un seul de ces arbres est vide, on pose $c_k=\\emptyset$ et $r_{k+1}=$ le recollement des deux arbres non vides, qui est bien un arbre binomial d'ordre $k+1$.\n", "- Si aucun de ces arbres n'est vide, on pose $c_k=$ l'un des trois arbres et $r_{k+1}=$ le recollement des deux autres arbres.\n", "\n", "Résumons le tout dans un tableau. Il y a en tout 8 cas. Lorsqu'une lettre apparaît dans une case, l'arbre correspondant est supposé non vide. \n", "\n", "Remarquons que dans le cas numéro 8 il y a une certaine dose d'arbitraire dans les choix de recollements." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\\begin{array}{|c|c|c|c|c|c|c|}\n", "\\hline \n", "&a_k&b_k&r_k&\\Rightarrow& c_k& r_{k+1}\\\\\n", "\\hline\n", "1&\\emptyset&\\emptyset&\\emptyset&& \\emptyset&\\emptyset\\\\\n", "\\hline\n", "2&\\emptyset&b_k&\\emptyset&&b_k&\\emptyset\\\\\n", "\\hline\n", "3&a_k&\\emptyset&\\emptyset&&a_k&\\emptyset\\\\\n", "\\hline\n", "4&a_k&b_k&\\emptyset&&\\emptyset&a_k\\oplus b_k\\\\\n", "\\hline\n", "5&\\emptyset&\\emptyset&r_k&&r_k&\\emptyset\\\\\n", "\\hline\n", "6&a_k&\\emptyset& r_k&&\\emptyset&r_k\\oplus a_k\\\\\n", "\\hline\n", "7&\\emptyset&b_k& r_k&& \\emptyset& r_k\\oplus b_k\\\\\n", "\\hline\n", "8&a_k&b_k&r_k&&r_k&a_k\\oplus b_k\\\\\n", "\\hline\n", "\\end{array}$$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def fusionner(a, b):\n", " n = max(len(a), len(b))\n", " c = n * [None]\n", " r = None\n", " for k in range(n):\n", " ak = element_tas(a, k)\n", " bk = element_tas(b, k)\n", " w = (ak == None, bk == None, r == None)\n", " if w == (True, True, True): c[k], r = None, None\n", " elif w == (True, False, True): c[k], r = bk, None\n", " elif w == (False, True, True): c[k], r = ak, None\n", " elif w == (False, False, True): c[k], r = None, coller_arbres(ak, bk)\n", " elif w == (True, True, False): c[k], r = r, None\n", " elif w == (False, True, False): c[k], r = None, coller_arbres(r, ak)\n", " elif w == (True, False, False): c[k], r = None, coller_arbres(r, bk)\n", " else: c[k], r = r, coller_arbres(ak, bk)\n", " if r != None: c.append(r)\n", " return c" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "a = random_tas(list(range(100)))\n", "b = random_tas(list(range(100, 200)))\n", "c = fusionner(a, b)\n", "print_tas(c)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "a = random_tas(list(range(10000)))\n", "b = random_tas(list(range(100000, 200000)))\n", "c = fusionner(a, b)\n", "print(est_tas_binomial(c))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Proposition__ : La complexité de `fusionner` est $O(\\max(\\lg |a|, \\lg |b|)$.\n", "\n", "__Démonstration__ : La fonction effectue une simple boucle `for`. Chaque itération s'exécute en $O(1)$, et le nombre d'itérations est égal à la plus grande des longueurs des deux tas. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4.3 Insertion d'un élément (bis)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Remarquons que nous disposons, grâce à la fonction d efusion, d'une nouvelle façon d'insérer un élément dans un tas $h$ : il suffit de fusionner le tas $h$ et le tas qui contient $x$ comme seul élément !" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def inserer_par_fusion(x, h):\n", " a = [(x, [])]\n", " return fusionner(a, h)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Remarque__ : De la façon dont nous avons écrit `fusionner`, cette fonction est moins efficace que la fonction `inserer` que nous avions écrite dans la section 3." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4.4 Suppression de l'élément minimal" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Proposition__ : Soit $t$ un arbre binomial. La liste des fils de $t$ est un tas binomial.\n", "\n", "__Démonstration__ : Laissée au lecteur. Elle se fait par récurrence sur l'ordre de l'arbre binomial." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction `supprimer_min` est alors évidente. Pour supprimer l'élément minimal du tas (non vide) $h$ :\n", "\n", "- On recherche l'indice $j$ dans le tas de l'arbre dont la racine est le plus petit élément du tas $h$. Soit $h'$ le tas formé par la liste des fils de $h[j]$.\n", "- On met $h[j]$ à `None`.\n", "- On fusionne $h$ et $h'$.\n", "\n", "Petit détail pour terminer : il se pourrait que le dernier arbre du tas obtenu soit vide. Dans ce cas on le supprime." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def indice_min(h):\n", " n = len(h)\n", " if n == 0: raise Exception('Tas vide')\n", " j = 0\n", " while j < n and h[j] == None: j = j + 1\n", " for k in range(j, n):\n", " if h[k] != None and racine(h[k]) < racine(h[j]): j = k\n", " return j" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def supprimer_min(h):\n", " j = indice_min(h)\n", " h1 = fils(h[j])\n", " h[j] = None\n", " h2 = fusionner(h1, h)\n", " if h2 != [] and h2[-1] == None: h2.pop()\n", " return h2" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "h = random_tas(list(range(16)))\n", "print_tas(h)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "h = supprimer_min(h)\n", "print_tas(h)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Proposition__ : La complexité de `supprimer_min` est $O(\\lg |h|)$.\n", "\n", "__Démonstration__ : Soit $n=\\lg |h|$. La recherche de $j$ s'effectue en temps $O(n)$. La fusion de $h_1$ et $h$ également." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4.5 Pour résumer" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour résumer ... voici un tableau résumant les complexités des fonctions que nous avons étudiées." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\\begin{array}{|c|c|c|c|}\n", "\\hline \n", "Fonction&Paramètre(s)&Complexité& Complexité\\ amortie\\\\\n", "\\hline\n", "est\\_vide&h&O(1)\\\\\n", "\\hline\n", "minimum&h&O(\\lg |h|)\\\\\n", "\\hline\n", "inserer&h&O(\\lg |h|)&O(1)\\\\\n", "\\hline\n", "supprimer\\_min&h&O(\\lg |h|)\\\\\n", "\\hline\n", "fusionner&h_1,h_2&O(\\max(\\lg |h_1|, \\lg |h_2|))\\\\\n", "\\hline\n", "\\end{array}$$" ] }, { "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.6.4" } }, "nbformat": 4, "nbformat_minor": 2 }