{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"toc": "true"
},
"source": [
"# Table of Contents\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# TP 3 - Programmation pour la préparation à l'agrégation maths option info"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- En OCaml."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val print : ('a, out_channel, unit) format -> 'a = \n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"The OCaml toplevel, version 4.04.2\n"
]
},
{
"data": {
"text/plain": [
"- : int = 0\n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let print = Printf.printf;;\n",
"Sys.command \"ocaml -version\";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# Arbres binaires de recherche"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 1 : ABR"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Variante non polymorphe et sans utilisation d'enregistrement pour nommer les champs :"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type abr0 = Leaf0 | Node0 of (int * string * abr0 * abr0)\n"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type abr0 =\n",
" | Leaf0\n",
" | Node0 of (int * string * abr0 * abr0)\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Mais on préfère la variant polymorphe, qui permettra une syntaxe plus concise :"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type 'a abr = Leaf | Node of 'a anode\n",
"and 'b anode = { key : int; value : 'b; left : 'b abr; right : 'b abr; }\n"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type 'a abr =\n",
" | Leaf\n",
" | Node of 'a anode\n",
"\n",
"and 'b anode = {\n",
" key : int;\n",
" value : 'b;\n",
" left : 'b abr; (* pour toute clé [k] dans [left], [k] < [key] *)\n",
" right : 'b abr (* pour toute clé [k] dans [right], [key] < [k] *)\n",
"}\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Compter les clés est facile :"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val nb_keys : 'a abr -> int = \n"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec nb_keys (a : 'a abr) : int =\n",
" match a with\n",
" | Leaf -> 0\n",
" | Node n -> 1 + nb_keys n.left + nb_keys n.right\n",
" (* | Node (key, value, left, right) -> 1 + nb_keys left + nb_keys right) *)\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Deux exemples :"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val a1 : string abr = Node {key = 1; value = \"un\"; left = Leaf; right = Leaf}\n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let a1 = Node { key=1; value=\"un\"; left=Leaf; right=Leaf } ;;\n",
"(* let a1 = Node (1,\"un\",Leaf,Leaf) *)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"val a2 : string abr =\n",
" Node\n",
" {key = 2; value = \"deux\";\n",
" left = Node {key = 1; value = \"un\"; left = Leaf; right = Leaf};\n",
" right = Leaf}\n"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let a2 = Node { key=2; value=\"deux\"; left=a1; right=Leaf } ;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 2 : `trouve`"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Avec un type de retour `'a option`, qui renvoie `None` si rien n'a été trouvé, ou `Some a` si la valeur `a` est trouvée."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val trouve : 'a abr -> int -> 'a option = \n"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec trouve (a : 'a abr) (k : int) : 'a option =\n",
" match a with\n",
" | Leaf -> None\n",
" | Node n when k = n.key -> Some n.value\n",
" (* sinon on cherche à gauche ou à droite *)\n",
" | Node n when k < n.key -> trouve n.left k\n",
" | Node n -> trouve n.right k\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : string option = Some \"un\"\n"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : string option = None\n"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"trouve a2 1;;\n",
"trouve a2 3;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Avec une exception :"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val trouve2 : 'a abr -> int -> 'a = \n"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec trouve2 (a : 'a abr) (k : int) : 'a =\n",
" match a with\n",
" | Leaf -> failwith \"Key not found\"\n",
" | Node n when k = n.key -> n.value\n",
" (* sinon on cherche à gauche ou à droite *)\n",
" | Node n when k < n.key -> trouve2 n.left k\n",
" | Node n -> trouve2 n.right k\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"- : string = \"un\"\n"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
},
{
"ename": "error",
"evalue": "error",
"output_type": "error",
"traceback": [
"\u001b[31mException: Failure \"Key not found\".\nRaised at file \"pervasives.ml\", line 32, characters 22-33\nCalled from file \"toplevel/toploop.ml\", line 180, characters 17-56\n\u001b[0m"
]
}
],
"source": [
"trouve2 a2 1;;\n",
"trouve2 a2 3;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 3 : `insertion`"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val insertion : 'a abr -> int -> 'a -> 'a abr = \n"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec insertion (a : 'a abr) (k : int) (v : 'a) : 'a abr =\n",
" match a with\n",
" | Leaf ->\n",
" Node { key=k; value=v; left=Leaf; right=Leaf }\n",
" | Node n when k=n.key ->\n",
" Node { n with value = v; key = k }\n",
" | Node n when k < n.key ->\n",
" Node { n with left = insertion n.left k v }\n",
" | Node n ->\n",
" Node { n with right = insertion n.right k v }\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Quelques tests :"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : string option = Some \"un\"\n"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : string option = Some \"deux\"\n"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : string option = None\n"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"trouve (insertion (insertion Leaf 2 \"deux\") 1 \"un\") 1;;\n",
"trouve (insertion (insertion Leaf 2 \"deux\") 1 \"un\") 2;;\n",
"trouve (insertion (insertion Leaf 2 \"deux\") 1 \"un\") 3;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 4 : `suppression`"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`minimum a` renvoie le couple `(key, value)` de l'arbre `a` avec `key` minimal dans `a`.\n",
"Lance une exception si `a` est vide."
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val minimum : 'a abr -> int * 'a = \n"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec minimum (a: 'a abr) : int * 'a =\n",
" match a with\n",
" | Leaf -> failwith \"empty tree\"\n",
" | Node n when n.left = Leaf -> (n.key, n.value)\n",
" | Node n -> minimum n.left\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int * string = (1, \"un\")\n"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"minimum (insertion (insertion Leaf 2 \"deux\") 1 \"un\");;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"La suppression se fait dans le cas où la clé `k` est trouvée :"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val suppression : 'a abr -> int -> 'a abr = \n"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec suppression (a: 'a abr) (k:int) : 'a abr =\n",
" match a with\n",
" | Leaf -> Leaf (* rien a supprimer *)\n",
" | Node n when k = n.key -> (* trouvé ! *)\n",
" if n.right = Leaf\n",
" then n.left\n",
" else\n",
" let (k_min, v) = minimum n.right in\n",
" Node { key = k_min; value = v; left = n.left; right = suppression n.right k_min }\n",
" | Node n when k < n.key -> (* à chercher à gauche *)\n",
" Node { n with left = suppression n.left k }\n",
" | Node n -> (* à chercher à droite *)\n",
" Node { n with right = suppression n.right k }\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : string option = None\n"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : string option = Some \"deux\"\n"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"trouve (suppression (insertion (insertion Leaf 2 \"deux\") 1 \"un\") 1) 1 ;;\n",
"\n",
"trouve (suppression (insertion (insertion Leaf 2 \"deux\") 1 \"un\") 1) 2 ;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 5 : `fusion`"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`decoupe a k` sépare l'arbre `a` en deux arbres `(a1, a2)` tels que l'union des clés-valeurs de `a1` et `a2` est égale à l'ensemble des clés-valeurs de `a` (privé de l'association liée à `k` si elle était présente dans `a`).\n",
"\n",
"- Les clés de `a1` sont `<` à `k`.\n",
"- Les clés de `a2` sont `>` à `k`."
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val decoupe : 'a abr -> int -> 'a abr * 'a abr = \n"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* [decoupe a k] sépare l'arbre [a] en deux arbres [(a1, a2)]\n",
" tels que l'union des clés-valeurs de [a1] et [a2] est égale à\n",
" l'ensemble des clés-valeurs de [a] (privé de l'association\n",
" liée à [k] si elle était présente dans [a]).\n",
" Les clés de [a1] sont < à [k].\n",
" Les clés de [a2] sont > à [k].\n",
"*)\n",
"\n",
"let rec decoupe (a : 'a abr) (k : int) : ('a abr) * ('a abr) =\n",
" match a with\n",
" | Leaf -> (Leaf, Leaf)\n",
" | Node n when k = n.key -> (n.left, n.right)\n",
" | Node n when k < n.key ->\n",
" let (left1, left2) = decoupe n.left k in\n",
" (left1, Node { n with left = left2 })\n",
" | Node n ->\n",
" let (right1, right2) = decoupe n.right k in\n",
" (Node { n with right = right1 }, right2)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val fusion : 'a abr -> 'a abr -> 'a abr = \n"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* si une clé est présente dans les deux arbres, nous gardons celle de [a1] *)\n",
"let rec fusion (a1 : 'a abr) (a2 : 'a abr) : 'a abr =\n",
" match a1 with\n",
" | Leaf -> a2\n",
" | Node n ->\n",
" let (left2, right2) = decoupe a2 n.key in\n",
" Node { n with left = fusion n.left left2; right = fusion n.right right2 }\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val a1 : string abr =\n",
" Node\n",
" {key = 2; value = \"deux\";\n",
" left = Node {key = 1; value = \"un\"; left = Leaf; right = Leaf};\n",
" right = Leaf}\n"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val a2 : string abr =\n",
" Node\n",
" {key = 2; value = \"two\"; left = Leaf;\n",
" right = Node {key = 3; value = \"trois\"; left = Leaf; right = Leaf}}\n"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : string option = Some \"un\"\n"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : string option = Some \"deux\"\n"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : string option = Some \"trois\"\n"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : string option = None\n"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let a1 = insertion (insertion Leaf 2 \"deux\") 1 \"un\" ;;\n",
"\n",
"let a2 = insertion (insertion Leaf 2 \"two\") 3 \"trois\" ;;\n",
"\n",
"trouve (fusion a1 a2) 1;;\n",
"trouve (fusion a1 a2) 2;;\n",
"trouve (fusion a1 a2) 3;;\n",
"trouve (fusion a1 a2) 4;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 6 : avantages et les inconvénients des ABR"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"> Discussions durant la séance..."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# Tas binaire min (ou max)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Solution concise, à adapter\n",
"> Référence: Chris Okasaki, *\"Purely Functional Data Structures\"*."
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type 'a heap = E | T of int * 'a * 'a heap * 'a heap\n"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type 'a heap = E | T of int * 'a * ('a heap) * ('a heap)"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val rank : 'a heap -> int = \n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rank : 'a heap -> int = function\n",
" | E -> 0\n",
" | T (r, _, _, _) -> r\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"La première primitive est la création d'un tas avec la clé `x`, et deux sous-tas `a` et `b`.\n",
"Le rang est minimisé."
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val make : 'a -> 'a heap -> 'a heap -> 'a heap = \n"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let make (x : 'a) (a : 'a heap) (b : 'a heap) =\n",
" let ra = rank a\n",
" and rb = rank b in\n",
" if ra >= rb then\n",
" T (rb + 1, x, a, b)\n",
" else\n",
" T (ra + 1, x, b, a)\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On peut vérifier si un tas est vide, ou créer le tas vide."
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val empty : 'a heap = E\n"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let empty : 'a heap = E\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val is_empty : 'a heap -> bool = \n"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let is_empty : 'a heap -> bool = function\n",
" | E -> true\n",
" | T _ -> false\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"La fusion est assez naturelle : on procède par récurrence, en joignant deux tas et en continuant la fusion pour les tas plus petits.\n",
"On gare la plus petite clé à la racine, pour conserver la propriété *tournoi*."
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val merge : 'a heap -> 'a heap -> 'a heap = \n"
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec merge (h1 : 'a heap) (h2 : 'a heap) : 'a heap =\n",
" match h1, h2 with\n",
" | E, h | h, E ->\n",
" h\n",
" | T (_, x, a1, b1), T (_, y, a2, b2) ->\n",
" if x <= y then\n",
" make x a1 (merge b1 h2)\n",
" else\n",
" make y a2 (merge h1 b2)\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"L'insertion correspond à la fusion d'un tas avec une seule clé et du tas courant :"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val insert : 'a -> 'a heap -> 'a heap = \n"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let insert (x : 'a) (h : 'a heap) : 'a heap =\n",
" merge (T (1, x, E, E)) h\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"La lecture de la plus petite clé est triviale :"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"exception Empty\n"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val mini : 'a heap -> 'a = \n"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"exception Empty;;\n",
"\n",
"let mini : 'a heap -> 'a = function\n",
" | E -> raise Empty\n",
" | T (_, x, _, _) -> x\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Et l'extraction n'est pas compliquée : il suffit de fusionner les deux sous-tas, ce qui va produire un tas tournoi avec les clés restantes."
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val extract_min : 'a heap -> 'a * 'a heap = \n"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let extract_min : 'a heap -> ('a * 'a heap) = function\n",
" | E -> raise Empty\n",
" | T (_, x, a, b) -> x, merge a b\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Et maintenant pour le tri par tas :\n",
"\n",
"1. On crée un tas vide,\n",
"2. Dans lequel on insère les valeurs du tableau à trier, une par une,\n",
"3. Puis on déconstruit le tas en extrayant le minimum, un par un, et en les stockant dans un tableau,\n",
"4. Le tableau obtenu est trié dans l'ordre croissant."
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val tripartas : int array -> int array = \n"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let tripartas (a : 'a array) : 'a array =\n",
" let n = Array.length a in\n",
" let tas = ref empty in\n",
" for i = 0 to n - 1 do\n",
" tas := insert a.(i) !tas\n",
" done;\n",
" let a2 = Array.make n (-1) in\n",
" for i = 0 to n - 1 do\n",
" let m, t = extract_min !tas in\n",
" a2.(i) <- m;\n",
" tas := t;\n",
" done;\n",
" a2\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Complexité :\n",
"\n",
"1. L'étape 1. est en $\\mathcal{O}(1)$,\n",
"2. L'étape 2. est en $\\mathcal{O}(\\log n)$ pour chacune des $n$ valeurs,\n",
"3. L'étape 3. est aussi en $\\mathcal{O}(\\log n)$ pour chacune des $n$ valeurs,\n",
"\n",
"$\\implies$ L'algorithme de tri par tas est en $\\mathcal{O}(n \\log n)$ en temps et en $\\mathcal{O}(n)$ en mémoire externe."
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int array = [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10|]\n"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tripartas [| 10; 3; 4; 1; 2; 7; 8; 5; 9; 6 |] ;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 7 : arbre tournoi"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On va utiliser un tableau de taille $n$ pour représenter en place les $n$ éléments du tas min.\n",
"\n",
"La référence pour cette implémentation vient du Cormen, des éléments sont aussi dans Beauquier & Bernstel, et sur Internet [sur la page Wikipédia](https://fr.wikipedia.org/wiki/Tas_binaire) des tas binaires.\n",
"\n",
"- Le tableau, `a` contiendra `-1` pour un élément non utilisé.\n",
"- On doit retenir le nombre `n` d'éléments dans l'arbre, qui peut être modifié."
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type arbre = int array\n"
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"type arbre_tournoi = { mutable n : int; a : arbre; }\n"
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type arbre = int array;;\n",
"\n",
"type arbre_tournoi = {\n",
" mutable n : int;\n",
" a : arbre\n",
"};;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Par exemple, l'arbre suivant s'écrit comme suit :\n",
""
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val arbre_test : arbre_tournoi = {n = 7; a = [|1; 2; 3; 4; 5; 6; 7|]}\n"
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val arbre_test2 : arbre_tournoi = {n = 6; a = [|2; 1; 3; 4; 5; 6; -1; -1|]}\n"
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let arbre_test = {\n",
" n = 7;\n",
" a = [|1; 2; 3; 4; 5; 6; 7|]\n",
"}\n",
"\n",
"let arbre_test2 = {\n",
" n = 6;\n",
" a = [|2; 1; 3; 4; 5; 6; -1; -1|]\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val capacite : arbre_tournoi -> int = \n"
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val nb_element : arbre_tournoi -> int = \n"
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let capacite (an : arbre_tournoi) : int =\n",
" Array.length an.a\n",
";;\n",
"\n",
"let nb_element (an : arbre_tournoi) : int =\n",
" let n = an.n\n",
" and m = Array.length an.a in\n",
" assert (n <= m);\n",
" n\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int = 7\n"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 7\n"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 8\n"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 6\n"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"capacite arbre_test;;\n",
"nb_element arbre_test;;\n",
"\n",
"capacite arbre_test2;;\n",
"nb_element arbre_test2;;"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val a_racine : arbre_tournoi -> bool = \n"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let a_racine (an : arbre_tournoi) : bool =\n",
" an.n > 0\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val est_racine : int -> bool = \n"
]
},
"execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let est_racine = (=) 0 ;;"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val racine : arbre_tournoi -> int * int = \n"
]
},
"execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let racine (an : arbre_tournoi) : int * int =\n",
" if 0 >= an.n then failwith \"Pas de racine\";\n",
" (0, an.a.(0))\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int * int = (0, 1)\n"
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"racine arbre_test;;"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val a_noeud : arbre_tournoi -> int -> bool = \n"
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let a_noeud (an : arbre_tournoi) (i : int) : bool =\n",
" an.n > i\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val noeud : arbre_tournoi -> int -> int * int = \n"
]
},
"execution_count": 40,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let noeud (an : arbre_tournoi) (i : int) : int * int =\n",
" if i >= an.n then failwith (Printf.sprintf \"Pas de noeud i = %i and an.n = %i\" i an.n);\n",
" (i, an.a.(i))\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val valeur : arbre_tournoi -> int -> int = \n"
]
},
"execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let valeur (an : arbre_tournoi) (i : int) : int =\n",
" snd (noeud an i)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int * int = (0, 1)\n"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"noeud arbre_test 0;;"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val a_gauche : arbre_tournoi -> int -> bool = \n"
]
},
"execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let a_gauche (an : arbre_tournoi) (i : int) : bool =\n",
" an.n > 2*i + 1\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val gauche : arbre_tournoi -> int -> int * int = \n"
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let gauche (an : arbre_tournoi) (i : int) : int * int =\n",
" if 2*i + 1 >= an.n then failwith (Printf.sprintf \"Pas de fils gauche i = %i, 2*i+1 = %i and an.n = %i\" i (2*i+1) an.n);\n",
" (2*i + 1, an.a.(2*i + 1))\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int * int = (1, 2)\n"
]
},
"execution_count": 45,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"gauche arbre_test 0;;"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val a_droite : arbre_tournoi -> int -> bool = \n"
]
},
"execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let a_droite (an : arbre_tournoi) (i : int) : bool =\n",
" an.n > 2*i + 2\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val droite : arbre_tournoi -> int -> int * int = \n"
]
},
"execution_count": 47,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let droite (an : arbre_tournoi) (i : int) : int * int =\n",
" if 2*i + 2 >= an.n then failwith (Printf.sprintf \"Pas de fils droit i = %i, 2i+2=%i and an.n = %i\" i (2*i+2) an.n);\n",
" (2*i + 2, an.a.(2*i + 2))\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Une et deux descentes à droite, par exemple :"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int * int = (2, 3)\n"
]
},
"execution_count": 48,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"droite arbre_test 0;;"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int * int = (6, 7)\n"
]
},
"execution_count": 49,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let i, _ = droite arbre_test 0 in\n",
"droite arbre_test i;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On parcourt les sous-arbres pour trouver le minimum :"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val min_sous_arbre : arbre_tournoi -> int -> int = \n"
]
},
"execution_count": 50,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec min_sous_arbre (an : arbre_tournoi) (i : int) : int =\n",
" match (a_gauche an i, a_droite an i) with\n",
" | (false, false) -> max_int\n",
" | (true, false) ->\n",
" let g, vg = gauche an i in\n",
" min vg (min_sous_arbre an g)\n",
" | (false, true) ->\n",
" let d, vd = droite an i in\n",
" min vd (min_sous_arbre an d)\n",
" | (true, true) ->\n",
" let g, vg = gauche an i in\n",
" let d, vd = droite an i in\n",
" min (min vg vd) (min (min_sous_arbre an g) (min_sous_arbre an d))\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : arbre_tournoi = {n = 7; a = [|1; 2; 3; 4; 5; 6; 7|]}\n"
]
},
"execution_count": 51,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 2\n"
]
},
"execution_count": 51,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"arbre_test;;\n",
"min_sous_arbre arbre_test 0;;"
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val est_tournoi : arbre_tournoi -> bool = \n"
]
},
"execution_count": 52,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let est_tournoi (an : arbre_tournoi) : bool =\n",
" let rec depuis (i : int) : bool =\n",
" (* cet arbre *)\n",
" let _, vr = noeud an i in\n",
" let min_v = min_sous_arbre an i in\n",
" let res = ref (vr < min_v) in\n",
" (* sous-arbres *)\n",
" if !res && a_gauche an i then\n",
" res := !res && depuis (fst (gauche an i));\n",
" if !res && a_droite an i then\n",
" res := !res && depuis (fst (droite an i));\n",
" !res\n",
" in\n",
" depuis 0\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 53,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"est_tournoi arbre_test;;"
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : arbre_tournoi = {n = 6; a = [|2; 1; 3; 4; 5; 6; -1; -1|]}\n"
]
},
"execution_count": 54,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = false\n"
]
},
"execution_count": 54,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"arbre_test2;;\n",
"est_tournoi arbre_test2;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 8 : `parent`, `fils_gauche` et `fils_droit`"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val parent : arbre_tournoi -> int -> int * int = \n"
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val fils_gauche : arbre_tournoi -> int -> int * int = \n"
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val fils_droite : arbre_tournoi -> int -> int * int = \n"
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let parent (an : arbre_tournoi) (i : int) =\n",
" noeud an ((i - 1) / 2)\n",
";;\n",
"\n",
"let fils_gauche = gauche;;\n",
"let fils_droite = droite;;"
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : arbre_tournoi = {n = 7; a = [|1; 2; 3; 4; 5; 6; 7|]}\n"
]
},
"execution_count": 56,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int * int = (1, 2)\n"
]
},
"execution_count": 56,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int * int = (0, 1)\n"
]
},
"execution_count": 56,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int * int = (2, 3)\n"
]
},
"execution_count": 56,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int * int = (0, 1)\n"
]
},
"execution_count": 56,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"arbre_test;;\n",
"\n",
"noeud arbre_test 1;;\n",
"parent arbre_test 1;;\n",
"noeud arbre_test 2;;\n",
"parent arbre_test 2;;"
]
},
{
"cell_type": "code",
"execution_count": 57,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int * int = (4, 5)\n"
]
},
"execution_count": 57,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int * int = (1, 2)\n"
]
},
"execution_count": 57,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int * int = (3, 4)\n"
]
},
"execution_count": 57,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int * int = (4, 5)\n"
]
},
"execution_count": 57,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int * int = (5, 6)\n"
]
},
"execution_count": 57,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int * int = (2, 3)\n"
]
},
"execution_count": 57,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int * int = (5, 6)\n"
]
},
"execution_count": 57,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int * int = (6, 7)\n"
]
},
"execution_count": 57,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"noeud arbre_test 4;;\n",
"parent arbre_test 4;;\n",
"gauche arbre_test 1;;\n",
"droite arbre_test 1;; (* 4 *)\n",
"\n",
"noeud arbre_test 5;;\n",
"parent arbre_test 5;;\n",
"gauche arbre_test 2;; (* 5 *)\n",
"droite arbre_test 2;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 9 : `echange`"
]
},
{
"cell_type": "code",
"execution_count": 58,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val echange : 'a array -> int -> int -> unit = \n"
]
},
"execution_count": 58,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let echange (a : 'a array) (i : int) (j : int) : unit =\n",
" let vi, vj = a.(i), a.(j) in\n",
" a.(i) <- vj;\n",
" a.(j) <- vi;\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 10 : `insertion`"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Si besoin, en insérant un élément dans un tableau déjà plein, on doit doubler sa capacité. Ce n'est pas compliqué : d'abord on double le tableau, puis on fait l'insertion normale."
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val double_capacite : arbre_tournoi -> arbre_tournoi = \n"
]
},
"execution_count": 59,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let double_capacite (an : arbre_tournoi) : arbre_tournoi =\n",
" let c = capacite an in\n",
" let a2 = Array.make (2 * c) (-1) in\n",
" for i = 0 to an.n - 1 do\n",
" a2.(i) <- an.a.(i)\n",
" done;\n",
" { n = an.n; a = a2 }\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"L'opération élémentaire s'appelle une \"percolation haute\" : pour rétablir si nécessaire la propriété d'ordre du tas binaire : tant que `x` n'est pas la racine de l'arbre et que `x` est strictement inférieur (tas min) à son père on échange les positions entre `x` et son père."
]
},
{
"cell_type": "code",
"execution_count": 60,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val percolation_haute : arbre_tournoi -> int -> unit = \n"
]
},
"execution_count": 60,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let percolation_haute (an : arbre_tournoi) (i : int) : unit =\n",
" let i = ref i in\n",
" let p = ref (fst (parent an !i)) in\n",
" (* Printf.printf \"\\nStart:\\ni = %i, p = %i%!\" !i !p; flush_all(); *)\n",
" while ((valeur an !p) > (valeur an !i)) do\n",
" echange an.a !i !p;\n",
" i := !p;\n",
" p := fst (parent an !i);\n",
" (* Printf.printf \"\\ni = %i, p = %i%!\" !i !p; flush_all(); *)\n",
" done;\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Maintenant, l'insertion a proprement dite :"
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val insertion : arbre_tournoi -> int -> arbre_tournoi = \n"
]
},
"execution_count": 61,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec insertion (an : arbre_tournoi) (x : int) : arbre_tournoi =\n",
" let n, c = an.n, capacite an in\n",
" if n == c then begin\n",
" let an2 = double_capacite an in\n",
" insertion an2 x\n",
" end else begin\n",
" let an2 = { n = n + 1; a = Array.copy an.a } in\n",
" an2.a.(n) <- x;\n",
" percolation_haute an2 n;\n",
" an2\n",
" end\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val arbre_test : arbre_tournoi = {n = 7; a = [|1; 2; 3; 4; 5; 6; 7; -1|]}\n"
]
},
"execution_count": 62,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val a2 : arbre_tournoi = {n = 8; a = [|-40; 1; 3; 2; 5; 6; 7; 4|]}\n"
]
},
"execution_count": 62,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : arbre_tournoi = {n = 7; a = [|1; 2; 3; 4; 5; 6; 7; -1|]}\n"
]
},
"execution_count": 62,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : arbre_tournoi =\n",
"{n = 9; a = [|-40; -20; 3; 1; 5; 6; 7; 4; 2; -1; -1; -1; -1; -1; -1; -1|]}\n"
]
},
"execution_count": 62,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let arbre_test = {\n",
" n = 7;\n",
" a = [|1; 2; 3; 4; 5; 6; 7; -1|]\n",
"};;\n",
"\n",
"let a2 = insertion arbre_test (-40);;\n",
"arbre_test;;\n",
"\n",
"(* on le voit doubler ! *)\n",
"insertion a2 (-20);;"
]
},
{
"cell_type": "code",
"execution_count": 63,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val arbre_test : arbre_tournoi =\n",
" {n = 7; a = [|1; 2; 3; 4; 5; 6; 7; -1; -1; -1; -1|]}\n"
]
},
"execution_count": 63,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : arbre_tournoi = {n = 10; a = [|-40; -20; 3; 1; -10; 6; 7; 4; 2; 5; -1|]}\n"
]
},
"execution_count": 63,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let arbre_test = {\n",
" n = 7;\n",
" a = [|1; 2; 3; 4; 5; 6; 7; -1; -1; -1; -1|]\n",
"};;\n",
"\n",
"insertion (insertion (insertion arbre_test (-40)) (-20)) (-10);;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 11 : `creation`"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"La sémantique de cette fonction est de créer un tas min à partir d'un tableau de valeur."
]
},
{
"cell_type": "code",
"execution_count": 64,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val creation : int array -> arbre_tournoi = \n"
]
},
"execution_count": 64,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let creation (a : 'a array) : arbre_tournoi =\n",
" let n = Array.length a in\n",
" let avide = Array.make n (-1) in\n",
" let an = ref {n = 0; a = avide} in\n",
" for i = 0 to n - 1 do\n",
" an := insertion !an a.(i)\n",
" done;\n",
" !an\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 65,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val arbre_test3 : arbre_tournoi = {n = 5; a = [|1; 5; 3; 20; 7|]}\n"
]
},
"execution_count": 65,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let arbre_test3 = creation [|20; 1; 3; 5; 7|];;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Notez que cet arbre est bien tournoi, mais n'est pas trié."
]
},
{
"cell_type": "code",
"execution_count": 66,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 66,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val sorted : 'a array -> 'a array = \n"
]
},
"execution_count": 66,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = false\n"
]
},
"execution_count": 66,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"est_tournoi arbre_test3;;\n",
"\n",
"let sorted (a : 'a array) : 'a array =\n",
" let a2 = Array.copy a in\n",
" Array.sort Pervasives.compare a2;\n",
" a2\n",
";;\n",
"\n",
"(sorted arbre_test3.a) == (arbre_test3.a);;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 12 : `diminue_clef`"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On peut augmenter ou diminuer la priorité (la clé) d'un nœud mais il faut ensuite satisfaire la contrainte d'ordre. Si l'on augmente la clé on fera donc une percolation-haute à partir de notre nœud et si l'on diminue la clé on fera un percolation-basse."
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"> Faites le vous-même."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 13 : `extraire_min`"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On fait une percolation basse pour déplacer la racine jusqu'à une feuille, puis on inverse la feuille avec la dernière valeur du tableau (la feuille la plus à droite), et on met une valeur arbitraire (`-1`) dedans et on diminue la taille du tas (`{ n with n = n - 1 }`)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"D'abord, on a besoin de récupérer un des deux fils si l'un des deux a une clé plus petite."
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val indice_min_fils : arbre_tournoi -> int -> int = \n"
]
},
"execution_count": 67,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let indice_min_fils (an : arbre_tournoi) (i : int) : int =\n",
" let g = ref i and d = ref i in\n",
" if a_gauche an i then\n",
" g := fst (fils_gauche an i);\n",
" if a_droite an i then\n",
" d := fst (fils_droite an i);\n",
" if (valeur an !g) < (valeur an !d)\n",
" then !g\n",
" else !d\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"La percolation basse n'est pas trop compliquée :"
]
},
{
"cell_type": "code",
"execution_count": 68,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val percolation_basse : arbre_tournoi -> int -> unit = \n"
]
},
"execution_count": 68,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let percolation_basse (an : arbre_tournoi) (i : int) : unit =\n",
" let i = ref i in\n",
" let f = ref (indice_min_fils an !i) in\n",
" while ((valeur an !f) < (valeur an !i)) do\n",
" echange an.a !i !f;\n",
" i := !f;\n",
" f := indice_min_fils an !i;\n",
" done;\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Enfin l'extraction du minimum est facile."
]
},
{
"cell_type": "code",
"execution_count": 69,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val extraire_min : arbre_tournoi -> int * arbre_tournoi = \n"
]
},
"execution_count": 69,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let extraire_min (an : arbre_tournoi) : (int * arbre_tournoi) =\n",
" let an = { an with a = Array.copy an.a } in\n",
" if a_gauche an 0 then begin\n",
" let m = an.a.(0) in\n",
" an.n <- an.n - 1;\n",
" echange an.a 0 an.n;\n",
" an.a.(an.n) <- (-1);\n",
" percolation_basse an 0;\n",
" m, an\n",
" end\n",
" else\n",
" (snd (racine an)), { n = 0; a = [||] };\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Et pour un exemple :"
]
},
{
"cell_type": "code",
"execution_count": 70,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val a : arbre_tournoi = {n = 5; a = [|1; 5; 3; 20; 7|]}\n"
]
},
"execution_count": 70,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val m : int = 1\n",
"val a : arbre_tournoi = {n = 4; a = [|3; 5; 7; 20; -1|]}\n"
]
},
"execution_count": 70,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val m : int = 3\n",
"val a : arbre_tournoi = {n = 3; a = [|5; 20; 7; -1; -1|]}\n"
]
},
"execution_count": 70,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val m : int = 5\n",
"val a : arbre_tournoi = {n = 2; a = [|7; 20; -1; -1; -1|]}\n"
]
},
"execution_count": 70,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val m : int = 7\n",
"val a : arbre_tournoi = {n = 1; a = [|20; -1; -1; -1; -1|]}\n"
]
},
"execution_count": 70,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val m : int = 20\n",
"val a : arbre_tournoi = {n = 0; a = [||]}\n"
]
},
"execution_count": 70,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let a = creation [|20; 1; 3; 5; 7|];;\n",
"let m, a = extraire_min a;;\n",
"let m, a = extraire_min a;;\n",
"let m, a = extraire_min a;;\n",
"let m, a = extraire_min a;;\n",
"let m, a = extraire_min a;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"## Exercice 14 : tri par tas"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"La meilleure façon de vérifier notre implémentation est d'implémenter le tri par tas :\n",
"\n",
"- on construit un tas depuis la liste de valeur,\n",
"- on extrait le minimum successivement."
]
},
{
"cell_type": "code",
"execution_count": 71,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val tripartas : int array -> int array = \n"
]
},
"execution_count": 71,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let tripartas (a : 'a array) : 'a array =\n",
" let n = Array.length a in\n",
" let avide = Array.make n (-1) in\n",
" let an = ref (creation a) in\n",
" for i = 0 to n - 1 do\n",
" let m, an2 = extraire_min !an in\n",
" avide.(i) <- m;\n",
" an := an2;\n",
" done;\n",
" avide\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 72,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val array1 : int array = [|10; 3; 4; 1; 2; 7; 8; 5; 9; 6|]\n"
]
},
"execution_count": 72,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val array2 : int array = [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10|]\n"
]
},
"execution_count": 72,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 72,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let array1 = [| 10; 3; 4; 1; 2; 7; 8; 5; 9; 6 |] ;;\n",
"let array2 = tripartas array1;;\n",
"assert ((sorted array2) = array2);;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# Union-Find"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 15 : Union-Find avec tableaux"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Version simple avec des tableaux simples."
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type representant = Aucun | Element of int\n"
]
},
"execution_count": 73,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"type unionfind = representant array\n"
]
},
"execution_count": 73,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type representant = Aucun | Element of int;; (* [int option] pourrait suffire *)\n",
"\n",
"type unionfind = representant array;;"
]
},
{
"cell_type": "code",
"execution_count": 74,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val create_uf : int -> unionfind = \n"
]
},
"execution_count": 74,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let create_uf (n : int) : unionfind =\n",
" Array.make n Aucun\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 75,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val makeset : unionfind -> int -> unit = \n"
]
},
"execution_count": 75,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let makeset (uf : unionfind) (i : int) : unit =\n",
" if uf.(i) = Aucun then\n",
" uf.(i) <- Element i\n",
" else\n",
" failwith \"Element deja present\"\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 76,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val union : unionfind -> int -> int -> unit = \n"
]
},
"execution_count": 76,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let union (uf : unionfind) (i : int) (j : int) : unit =\n",
" let n = Array.length uf in\n",
" if (uf.(i) = Aucun || uf.(j) = Aucun) then\n",
" failwith \"Element absent\";\n",
" for k = 0 to (n - 1) do\n",
" if uf.(k) = Element j then\n",
" uf.(j) <- Element i\n",
" done\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 77,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val find : unionfind -> int -> int = \n"
]
},
"execution_count": 77,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* très facile *)\n",
"let find (uf : unionfind) (i : int) : int =\n",
" match uf.(i) with\n",
" | Aucun -> failwith \"Element absent\"\n",
" | Element i -> i\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Tests :"
]
},
{
"cell_type": "code",
"execution_count": 78,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val uf_test : unionfind = [|Aucun; Aucun; Aucun; Aucun; Aucun; Aucun|]\n"
]
},
"execution_count": 78,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 78,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unionfind =\n",
"[|Element 0; Element 1; Element 2; Element 3; Element 4; Element 5|]\n"
]
},
"execution_count": 78,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 5\n"
]
},
"execution_count": 78,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 78,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unionfind =\n",
"[|Element 0; Element 1; Element 1; Element 3; Element 4; Element 5|]\n"
]
},
"execution_count": 78,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 78,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unionfind =\n",
"[|Element 0; Element 1; Element 1; Element 3; Element 4; Element 2|]\n"
]
},
"execution_count": 78,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 0\n"
]
},
"execution_count": 78,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unionfind =\n",
"[|Element 0; Element 1; Element 1; Element 3; Element 4; Element 2|]\n"
]
},
"execution_count": 78,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 1\n"
]
},
"execution_count": 78,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unionfind =\n",
"[|Element 0; Element 1; Element 1; Element 3; Element 4; Element 2|]\n"
]
},
"execution_count": 78,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = false\n"
]
},
"execution_count": 78,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = false\n"
]
},
"execution_count": 78,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let uf_test = create_uf 6;;\n",
"for i = 0 to 5 do\n",
" makeset uf_test i\n",
"done;;\n",
"\n",
"uf_test;;\n",
"\n",
"find uf_test 5;;\n",
"union uf_test 1 2;;\n",
"\n",
"uf_test;;\n",
"union uf_test 2 5;;\n",
"\n",
"uf_test;;\n",
"find uf_test 0;;\n",
"\n",
"uf_test;;\n",
"find uf_test 1;;\n",
"\n",
"uf_test;;\n",
"find uf_test 1 = find uf_test 5;;\n",
"find uf_test 1 = find uf_test 4;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 16 : Union-Find avec forêts"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Version avancée avec des forêts."
]
},
{
"cell_type": "code",
"execution_count": 79,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type position = Aucun | Racine | Fils of int\n"
]
},
"execution_count": 79,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"type unionfind = position array\n"
]
},
"execution_count": 79,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type position = Aucun | Racine | Fils of int;;\n",
"\n",
"type unionfind = position array;;"
]
},
{
"cell_type": "code",
"execution_count": 80,
"metadata": {},
"outputs": [
{
"name": "stderr",
"output_type": "stream",
"text": [
"File \"[80]\", line 2, characters 17-22:\n",
"Warning 41: Aucun belongs to several types: position representant\n",
"The first one was selected. Please disambiguate if this is wrong.\n"
]
},
{
"data": {
"text/plain": [
"val create_uf : int -> unionfind = \n"
]
},
"execution_count": 80,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let create_uf (n : int) : unionfind =\n",
" Array.make n Aucun\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 81,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val makeset : unionfind -> int -> unit = \n"
]
},
"execution_count": 81,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let makeset (uf : unionfind) (i : int) : unit =\n",
" if uf.(i) = Aucun then\n",
" uf.(i) <- Racine (* i devient son propre représentant *)\n",
" else\n",
" failwith \"Element deja present\"\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 82,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val find : unionfind -> int -> int = \n"
]
},
"execution_count": 82,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec find (uf : unionfind) (i : int) : int =\n",
" match uf.(i) with\n",
" | Aucun -> failwith \"Element absent\"\n",
" | Fils j ->\n",
" let racine = find uf j in\n",
" uf.(i) <- Fils racine; (* modifie la forêt ! *)\n",
" racine\n",
" | Racine -> i (* la racine est le représentant *)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 83,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val union : unionfind -> int -> int -> unit = \n"
]
},
"execution_count": 83,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let union (uf : unionfind) (i : int) (j : int) : unit =\n",
" if (uf.(i) = Aucun || uf.(j) = Aucun) then\n",
" failwith \"Element absent\"\n",
" else\n",
" (* choix arbitraire de préférer la racine de i,\n",
" on devrait préférer celle de l'arbre le plus petit pour \"écraser\" la forêt.\n",
" Cf. Papadimitriou ou Cormen (ou Wikipédia).\n",
" *)\n",
" let racinei = find uf i in\n",
" uf.(racinei) <- Fils j\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Tests :"
]
},
{
"cell_type": "code",
"execution_count": 84,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val uf_test : unionfind = [|Aucun; Aucun; Aucun; Aucun; Aucun; Aucun|]\n"
]
},
"execution_count": 84,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 84,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unionfind = [|Racine; Racine; Racine; Racine; Racine; Racine|]\n"
]
},
"execution_count": 84,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 5\n"
]
},
"execution_count": 84,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 84,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unionfind = [|Racine; Fils 2; Racine; Racine; Racine; Racine|]\n"
]
},
"execution_count": 84,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 84,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unionfind = [|Racine; Fils 2; Fils 5; Racine; Racine; Racine|]\n"
]
},
"execution_count": 84,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 0\n"
]
},
"execution_count": 84,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unionfind = [|Racine; Fils 2; Fils 5; Racine; Racine; Racine|]\n"
]
},
"execution_count": 84,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 5\n"
]
},
"execution_count": 84,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : unionfind = [|Racine; Fils 5; Fils 5; Racine; Racine; Racine|]\n"
]
},
"execution_count": 84,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 84,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = false\n"
]
},
"execution_count": 84,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let uf_test = create_uf 6;;\n",
"for i = 0 to 5 do\n",
" makeset uf_test i\n",
"done;;\n",
"\n",
"uf_test;;\n",
"\n",
"find uf_test 5;;\n",
"union uf_test 1 2;;\n",
"\n",
"uf_test;;\n",
"union uf_test 2 5;;\n",
"\n",
"uf_test;;\n",
"find uf_test 0;;\n",
"\n",
"uf_test;;\n",
"find uf_test 1;;\n",
"\n",
"uf_test;;\n",
"find uf_test 1 = find uf_test 5;;\n",
"find uf_test 1 = find uf_test 4;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercice 17 : Bonus & discussions"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"En classe.\n",
"\n",
"Je recommande aussi la lecture de [ce document (en anglais)](http://jeffe.cs.illinois.edu/teaching/algorithms/notes/17-unionfind.pdf), si tout ça vous intéresse et si vous envisagez d'en faire un développement. Ce document contient notamment une analyse bien propre de la complexité amortie de l'opération Find pour l'algorithme optimisé, qui donne une complexité en $\\mathcal{O}(\\alpha(n))$ (pour $n$ valeurs dans la structure Union-Find, et si $\\alpha$ est la fonction inverse d'Ackermann, cf. Theorem 4 page 9)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Bonus : algorithme de Kruskal"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Representations de graphe pondérés"
]
},
{
"cell_type": "code",
"execution_count": 85,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type poids = int\n"
]
},
"execution_count": 85,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"type arete = Absent | Present of poids\n"
]
},
"execution_count": 85,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"type graphe_matrix = arete array array\n"
]
},
"execution_count": 85,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"type graphe_list = (int * poids) list array\n"
]
},
"execution_count": 85,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type poids = int;;\n",
"\n",
"type arete = Absent | Present of poids;;\n",
"type graphe_matrix = arete array array;;\n",
"\n",
"type graphe_list = ((int * poids) list) array;;"
]
},
{
"cell_type": "code",
"execution_count": 86,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val taille_graphe : 'a array -> int = \n"
]
},
"execution_count": 86,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let taille_graphe = Array.length;; (* nb sommets *)"
]
},
{
"cell_type": "code",
"execution_count": 87,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val liste_aretes : graphe_list -> (int * int * poids) list = \n"
]
},
"execution_count": 87,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let liste_aretes (gl : graphe_list) =\n",
" let resultat = ref [] in\n",
" let n = taille_graphe gl in\n",
" let rec traitement_liste (i : int) = function (* c'est un List.iter... *)\n",
" | [] -> ()\n",
" | (j, p) :: q -> begin\n",
" resultat := (i, j, p) :: !resultat;\n",
" traitement_liste i q\n",
" end\n",
" in\n",
" for i = 0 to (n - 1) do (* c'est un Array.iter *)\n",
" traitement_liste i gl.(i)\n",
" done;\n",
" !resultat\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 88,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val graphe_test : graphe_list =\n",
" [|[(1, 11); (2, 2); (3, 1)]; [(2, 7)]; []; [(4, 5)]; [(1, 1)]|]\n"
]
},
"execution_count": 88,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : (int * int * poids) list =\n",
"[(4, 1, 1); (3, 4, 5); (1, 2, 7); (0, 3, 1); (0, 2, 2); (0, 1, 11)]\n"
]
},
"execution_count": 88,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let graphe_test : graphe_list =\n",
" [| [(1, 11); (2, 2); (3, 1)];\n",
" [(2, 7)];\n",
" [];\n",
" [(4, 5)];\n",
" [(1, 1)]\n",
" |]\n",
";;\n",
"\n",
"liste_aretes graphe_test;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Algorithme de Kruskal"
]
},
{
"cell_type": "code",
"execution_count": 89,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"val kruskal : graphe_list -> (int * int * poids) list = \n"
]
},
"execution_count": 89,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let kruskal (gl : graphe_list) =\n",
" let aretes = liste_aretes gl in\n",
" let aretes = List.sort (\n",
" fun (_, _, x) -> fun (_, _, y) -> x - y\n",
" ) aretes in\n",
" let n = taille_graphe gl in\n",
" let uf = create_uf n in\n",
" let result = ref [] in (* difficle de faire sans référence ici... *)\n",
" let traitement_arete (i, j, p) =\n",
" if not (find uf i = find uf j) then begin\n",
" result := (i, j, p) :: !result;\n",
" union uf i j\n",
" end\n",
" in\n",
" for i = 0 to (n - 1) do\n",
" makeset uf i\n",
" done;\n",
" List.iter traitement_arete aretes;\n",
" !result\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Cet algorithme donne bien un arbre couvrant, il faudrait vérifier sa minimalité."
]
},
{
"cell_type": "code",
"execution_count": 90,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : (int * int * poids) list = [(3, 4, 5); (0, 2, 2); (0, 3, 1); (4, 1, 1)]\n"
]
},
"execution_count": 90,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"kruskal graphe_test;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"# Conclusion\n",
"\n",
"Fin. À la séance prochaine."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "OCaml 4.04.2",
"language": "OCaml",
"name": "ocaml-jupyter"
},
"language_info": {
"codemirror_mode": "text/x-ocaml",
"file_extension": ".ml",
"mimetype": "text/x-ocaml",
"name": "OCaml",
"nbconverter_exporter": null,
"pygments_lexer": "OCaml",
"version": "4.04.2"
},
"toc": {
"colors": {
"hover_highlight": "#DAA520",
"running_highlight": "#FF0000",
"selected_highlight": "#FFD700"
},
"moveMenuLeft": true,
"nav_menu": {
"height": "511px",
"width": "251px"
},
"navigate_menu": true,
"number_sections": true,
"sideBar": true,
"threshold": 4,
"toc_cell": true,
"toc_section_display": "block",
"toc_window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 2
}