{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"toc": "true"
},
"source": [
"# Table of Contents\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# TP 7 - Programmation pour la préparation à l'agrégation maths option info\n",
"TP 5 : Algorithmes gloutons et files de priorité."
]
},
{
"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": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : string -> unit = \n"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"print_endline"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"## Algorithme de Dijkstra - avec des files non mutables\n",
"\n",
"Déjà vu, on le retraite ici."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Files de priorité min"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type 'a priopqueue = (int * 'a) list\n"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* file de priorité version non-mutable *)\n",
"type 'a priopqueue = (int * 'a) list;;"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val vide : 'a priopqueue = []\n"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* file vide *)\n",
"let vide : 'a priopqueue = [ ];;"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val inserer : 'a -> int -> 'a priopqueue -> 'a priopqueue = \n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* [inserer x clef q] insere l'element [x] dans la file [q]\n",
" avec le clef [x], et renvoie la nouvelle file ainsi créée.\n",
" Termine avec une exception si la file contient déjà [x] *)\n",
"let inserer (x:'a) (clef:int) (q:'a priopqueue) : 'a priopqueue =\n",
" if List.exists (fun (_, v) -> x = v) q\n",
" then failwith \"l'element est déjà dans la file\"\n",
" else (clef,x) :: q\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val est_vide : 'a priopqueue -> bool = \n"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* [est_vide q] teste si la file [q] est vide *)\n",
"let est_vide (q:'a priopqueue) : bool = (q = [ ]);;"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val trouve_min_aux : 'a -> int -> 'a priopqueue -> int * 'a = \n"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* [trouve_min_aux min_val min_clef q] renvoie un couple de clef minimale\n",
" dans (min_val,min_clef)::q *)\n",
"let rec trouve_min_aux (min_val:'a) (min_clef:int) (q:'a priopqueue) : int * 'a =\n",
" match q with\n",
" | [ ] -> (min_clef, min_val)\n",
" | (clef, _) :: q when clef > min_clef -> trouve_min_aux min_val min_clef q\n",
" | (clef, v) :: q -> trouve_min_aux v clef q\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val trouve_min : 'a priopqueue -> 'a = \n"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* [trouve_min q] renvoie un élément de clef minimale la file [q].\n",
" Lance une exception si la liste est vide *)\n",
"let trouve_min (q:'a priopqueue) : 'a =\n",
" match q with\n",
" | [ ] -> failwith \"trouve_min: la file est vide\"\n",
" | (clef, v) :: q -> snd (trouve_min_aux v clef q)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : char = '1'\n"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : char = '2'\n"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let _ = trouve_min (inserer '1' 1 (inserer '2' 2 (inserer '3' 3 vide)));;\n",
"let _ = trouve_min (inserer '1' 4 (inserer '2' 2 (inserer '3' 3 vide)));;"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val supprime : 'a -> 'a priopqueue -> 'a priopqueue = \n"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* [supprime v q] renvoie une file contenant les éléments de [q], sauf [x].\n",
" [x] doit apparaitre une et une seule fois dans la file. *)\n",
"let rec supprime (x:'a) (q:'a priopqueue) : 'a priopqueue =\n",
" match q with\n",
" | [ ] -> [ ]\n",
" | (_, v) :: q when v=x -> q\n",
" | (clef, v) :: q -> (clef, v) :: (supprime x q)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val extraire_min : 'a priopqueue -> 'a * 'a priopqueue = \n"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* [extraire_min q] renvoie un élément de q, de clef minimal,\n",
" ainsi que la nouvelle file obtenue en supprimant cet\n",
" élément; termine avec une exception si la file est vide *)\n",
"let extraire_min (q:'a priopqueue) : 'a * 'a priopqueue =\n",
" if q = [ ] then\n",
" failwith \"extraire_min: file vide\"\n",
" else\n",
" let min = trouve_min q in\n",
" (min, supprime min q)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : char * char priopqueue = ('1', [(2, '2'); (3, '3')])\n"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : char * char priopqueue = ('2', [(4, '1'); (3, '3')])\n"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let _ = extraire_min (inserer '1' 1 (inserer '2' 2 (inserer '3' 3 vide)));;\n",
"let _ = extraire_min (inserer '1' 4 (inserer '2' 2 (inserer '3' 3 vide)));;"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val diminuer_clef : 'a -> int -> 'a priopqueue -> 'a priopqueue = \n"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* [diminuer_clef q clef x] modifie la clef de l'élément [x]\n",
" dans la file q en lui associant la nouvelle clef [clef], qui\n",
" doit être inferieur à la clef actuelle de [x].\n",
" Termine avec une exception si la file ne contient pas [x] *)\n",
"let rec diminuer_clef (x:'a) (clef:int) (q:'a priopqueue) : 'a priopqueue =\n",
" match q with\n",
" | [ ] -> failwith \"diminuer_clef : l'élément n'est pas présent\"\n",
" | (_, v) :: q when v=x -> (clef, x) :: q\n",
" | (c, v) :: q -> (c, v) :: diminuer_clef x clef q\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val f : char priopqueue = [(1, '1'); (2, '2'); (3, '3')]\n"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : char priopqueue = [(1, '1'); (2, '2'); (0, '3')]\n"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : char priopqueue = [(1, '1'); (0, '2'); (3, '3')]\n"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let f = inserer '1' 1 (inserer '2' 2 (inserer '3' 3 vide));;\n",
"let _ = diminuer_clef '3' 0 f;;\n",
"let _ = diminuer_clef '2' 0 f;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Graphe par tableau de listes d'adjacence"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type sommet = int\n"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"type graph = {\n",
" taille : int;\n",
" adj : (int * sommet) list array;\n",
" entree : sommet;\n",
"}\n"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type sommet = int;;\n",
"type graph = {\n",
" taille: int; (* les sommets sont des entiers entre 0 et taille-1 *)\n",
" adj: (int * sommet) list array;\n",
" entree: sommet\n",
"};;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ce qui suit est purement optionnel, ce n'était pas demandé, ne vous embêtez pas à chercher à tout comprendre, c'est simplement pour visualiser les graphes et les afficher ensuite."
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val print : out_channel -> ('a, out_channel, unit) format -> 'a = \n"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val dot : string -> graph -> (int * int) list -> unit = \n"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val dot2svg : string -> int = \n"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let print = Printf.fprintf;;\n",
"\n",
"let dot outname (g:graph) (bold:(int*int) list) : unit =\n",
" let f = open_out (outname ^ \".dot\") in\n",
" print f \"digraph G {\\n\";\n",
" for i=0 to g.taille-1 do\n",
" print f \" som%d [label=\\\"%d\\\"];\\n\" i i\n",
" done;\n",
" for i=0 to g.taille-1 do\n",
" List.iter (fun (c,j) ->\n",
" let option = if List.mem (i,j) bold then \",style=bold\" else \"\" in\n",
" print f \" som%d -> som%d [label=\\\"%d\\\"%s];\\n\" i j c option\n",
" ) g.adj.(i);\n",
" done;\n",
" print f \"}\\n\";\n",
" close_out f\n",
";;\n",
"\n",
"let dot2svg outname =\n",
" Sys.command (Printf.sprintf \"dot -Tsvg %s.dot > %s.svg\" outname outname);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exemple de visualisation de graphe"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val s : int = 0\n",
"val a : int = 1\n",
"val b : int = 2\n",
"val c : int = 3\n",
"val d : int = 4\n"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val g1 : graph =\n",
" {taille = 5;\n",
" adj = [|[(2, 1); (4, 2); (2, 3)]; [(1, 4)]; [(4, 4)]; [(1, 2)]; []|];\n",
" entree = 0}\n"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let s = 0\n",
"and a = 1\n",
"and b = 2\n",
"and c = 3\n",
"and d = 4;;\n",
"let g1 = {\n",
" taille = 5;\n",
" entree = s;\n",
" adj = [|\n",
" [(2,a); (4,b); (2,c)]; (* adj(s) *)\n",
" [(1,d)]; (* adj(A) *)\n",
" [(4,d)]; (* adj(B) *)\n",
" [(1,b)]; (* adj(C) *)\n",
" [ ]; (* adj(D) *)\n",
" |]\n",
"};;"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 0\n"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let _ = dot \"TP7__g1\" g1 [ ];;\n",
"dot2svg \"TP7__g1\";;"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"digraph G {\n",
" som0 [label=\"0\"];\n",
" som1 [label=\"1\"];\n",
" som2 [label=\"2\"];\n",
" som3 [label=\"3\"];\n",
" som4 [label=\"4\"];\n",
" som0 -> som1 [label=\"2\"];\n",
" som0 -> som2 [label=\"4\"];\n",
" som0 -> som3 [label=\"2\"];\n",
" som1 -> som4 [label=\"1\"];\n",
" som2 -> som4 [label=\"4\"];\n",
" som3 -> som2 [label=\"1\"];\n",
"}\n"
]
},
{
"data": {
"text/plain": [
"- : int = 0\n"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Sys.command \"cat TP7__g1.dot\";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Le second argument permet d'afficher un certain chemin :"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let _ = dot \"TP7__g2\" g1 [(0,3);(3,2);(2,4)];;"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"digraph G {\n",
" som0 [label=\"0\"];\n",
" som1 [label=\"1\"];\n",
" som2 [label=\"2\"];\n",
" som3 [label=\"3\"];\n",
" som4 [label=\"4\"];\n",
" som0 -> som1 [label=\"2\"];\n",
" som0 -> som2 [label=\"4\"];\n",
" som0 -> som3 [label=\"2\",style=bold];\n",
" som1 -> som4 [label=\"1\"];\n",
" som2 -> som4 [label=\"4\",style=bold];\n",
" som3 -> som2 [label=\"1\",style=bold];\n",
"}\n"
]
},
{
"data": {
"text/plain": [
"- : int = 0\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 0\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Sys.command \"cat TP7__g2.dot\";;\n",
"dot2svg \"TP7__g2\";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Dijkstra"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Une fois qu'on dispose de tout ça, écrire l'algorithme de Dijkstra est relativement rapide.\n",
"\n",
"- Voir [ce site](https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html) pour de belles visualisations de l'algorithme de Dijkstra.\n",
"- Et [cette page](https://jilljenn.github.io/tryalgo/tryalgo/tryalgo.html#module-tryalgo.dijkstra) pour une implémentation propre en Python ([lien direct vers le code](https://jilljenn.github.io/tryalgo/_modules/tryalgo/dijkstra.html#dijkstra))."
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"val dijkstra : graph -> int array = \n"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let dijkstra g =\n",
" let q = ref vide in\n",
" let dist = Array.init g.taille (fun i ->\n",
" if i=g.entree then 0 else max_int\n",
" ) in\n",
" for i=0 to g.taille - 1 do (* initialisation de la file *)\n",
" q := inserer i dist.(i) !q\n",
" done;\n",
" while not (est_vide !q) do\n",
" let (x, q') = extraire_min !q in\n",
" q := q'; (* ne pas oublier de mettre à jour la file *)\n",
" (* on regarde les adjacents de x *)\n",
" List.iter (fun (c,y) ->\n",
" if dist.(y) > dist.(x) + c\n",
" then begin\n",
" dist.(y) <- dist.(x) + c;\n",
" q := diminuer_clef y dist.(y) !q\n",
" end\n",
" ) g.adj.(x)\n",
" done;\n",
" dist\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int array = [|0; 2; 3; 2; 3|]\n"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let _ = dijkstra g1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Contre-exemples\n",
"\n",
"Trouver des cas simples faisant échouer l’algorithme si une des hypothèses n'est pas satisfaite : par exemple un graphe non connexe, ou un graphe avec une arête de poids négatif."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Un graphe non connexe"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val s : int = 0\n",
"val a : int = 1\n",
"val b : int = 2\n",
"val c : int = 3\n",
"val d : int = 4\n",
"val e : int = 5\n",
"val f : int = 6\n"
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val g2 : graph =\n",
" {taille = 7;\n",
" adj =\n",
" [|[(2, 1); (4, 2); (2, 3)]; [(1, 4)]; [(4, 4)]; [(1, 2)]; []; [(5, 6)];\n",
" []|];\n",
" entree = 0}\n"
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let s = 0\n",
"and a = 1\n",
"and b = 2\n",
"and c = 3\n",
"and d = 4\n",
"and e = 5\n",
"and f = 6;;\n",
"let g2 = {\n",
" taille = 7;\n",
" entree = s;\n",
" adj = [|\n",
" [(2,a); (4,b); (2,c)]; (* adj(s) *)\n",
" [(1,d)]; (* adj(A) *)\n",
" [(4,d)]; (* adj(B) *)\n",
" [(1,b)]; (* adj(C) *)\n",
" [ ]; (* adj(D) *)\n",
" [(5,f)]; (* adj(E) *)\n",
" [ ]; (* adj(F) *)\n",
" |]\n",
"};;"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int array = [|0; 2; 3; 2; 3; 4611686018427387903; -4611686018427387900|]\n"
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let _ = dijkstra g2;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Oups, ça n'a pas l'air correct !"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Un graphe avec un poids négatif"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val s : int = 0\n",
"val a : int = 1\n",
"val b : int = 2\n",
"val c : int = 3\n",
"val d : int = 4\n"
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val g3 : graph =\n",
" {taille = 5;\n",
" adj =\n",
" [|[(2, 1); (-4, 2); (2, 3)]; [(1, 4)]; [(-4, 4)]; [(1, 2)]; [(2, 2)]|];\n",
" entree = 0}\n"
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let s = 0\n",
"and a = 1\n",
"and b = 2\n",
"and c = 3\n",
"and d = 4;;\n",
"let g3 = {\n",
" taille = 5;\n",
" entree = s;\n",
" adj = [|\n",
" [(2,a); (-4,b); (2,c)]; (* adj(s) *)\n",
" [(1,d)]; (* adj(A) *)\n",
" [(-4,d)]; (* adj(B) *)\n",
" [(1,b)]; (* adj(C) *)\n",
" [(2,b)]; (* adj(D) *)\n",
" |]\n",
"};;"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {},
"outputs": [
{
"ename": "error",
"evalue": "runtime_error",
"output_type": "error",
"traceback": [
"\u001b[31mException:\nFailure \"diminuer_clef : l'\\195\\169l\\195\\169ment n'est pas pr\\195\\169sent\".\nRaised at file \"pervasives.ml\", line 32, characters 22-33\nCalled from file \"[13]\", line 9, characters 31-53\nCalled from file \"[13]\", line 9, characters 31-53\nCalled from file \"[22]\", line 17, characters 21-48\nCalled from file \"list.ml\", line 77, characters 12-15\nCalled from file \"[22]\", line 13, characters 8-220\nCalled from file \"toplevel/toploop.ml\", line 180, characters 17-56\n\u001b[0m"
]
}
],
"source": [
"let _ = dijkstra g3;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Oups, ça n'a pas l'air correct non plus !"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"## Algorithme de Dijkstra - avec des files mutables\n",
"\n",
"Déjà vu, on le retraite ici."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Files de priorité min mutables"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type 'a priopqueue = (int * 'a) list ref\n"
]
},
"execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* file de priorité version non-mutable *)\n",
"type 'a priopqueue = (int * 'a) list ref;;"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val vide : unit -> 'a priopqueue = \n"
]
},
"execution_count": 47,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* file vide *)\n",
"let vide () : 'a priopqueue = ref [ ];;"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val inserer : 'a -> int -> 'a priopqueue -> unit = \n"
]
},
"execution_count": 48,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* [inserer x clef q] insere l'element [x] dans la file [q]\n",
" avec le clef [x].\n",
" Termine avec une exception si la file contient déjà [x] *)\n",
"let inserer (x:'a) (clef:int) (q:'a priopqueue) : unit =\n",
" if List.exists (fun (_, v) -> x=v) !q\n",
" then failwith \"l'element est déjà dans la file\"\n",
" else q := (clef,x) :: !q\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val est_vide : 'a priopqueue -> bool = \n"
]
},
"execution_count": 49,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* [est_vide q] teste si la file [q] est vide *)\n",
"let est_vide (q:'a priopqueue) : bool = (!q = [ ]);;"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val trouve_min_aux : 'a -> int -> (int * 'a) list -> int * 'a = \n"
]
},
"execution_count": 50,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* [trouve_min_aux min_val min_clef q] renvoie un couple de clef minimale\n",
" dans (min_val,min_clef)::q *)\n",
"let rec trouve_min_aux (min_val:'a) (min_clef:int) (q:(int*'a) list) : int * 'a =\n",
" match q with\n",
" | [ ] -> (min_clef, min_val)\n",
" | (clef, _) :: q when clef > min_clef -> trouve_min_aux min_val min_clef q\n",
" | (clef, v) :: q -> trouve_min_aux v clef q\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val trouve_min : (int * 'a) list -> 'a = \n"
]
},
"execution_count": 51,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* [trouve_min q] renvoie un élément de clef minimale la file [q].\n",
" Lance une exception si la liste est vide *)\n",
"let trouve_min (q:(int*'a) list) : 'a =\n",
" match q with\n",
" | [ ] -> failwith \"trouve_min: la file est vide\"\n",
" | (clef, v) :: q -> snd (trouve_min_aux v clef q)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val supprime : 'a -> (int * 'a) list -> (int * 'a) list = \n"
]
},
"execution_count": 52,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* [supprime v q] renvoie une file contenant les éléments de [q], sauf [x].\n",
" [x] doit apparaitre une et une seule fois dans la file. *)\n",
"let rec supprime (x:'a) (q:(int*'a) list) : (int*'a) list =\n",
" match q with\n",
" | [ ] -> [ ]\n",
" | (_, v) :: q when v=x -> q\n",
" | (clef, v) :: q -> (clef,v) :: (supprime x q)\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val extraire_min : 'a priopqueue -> 'a = \n"
]
},
"execution_count": 53,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* [extraire_min q] renvoie un élément de q, de clef minimal,\n",
" et met à jour la file; termine avec une exception si la file est vide *)\n",
"let extraire_min (q:'a priopqueue) : 'a =\n",
" if !q = [ ] then failwith \"extraire_min: file vide\"\n",
" else\n",
" let min = trouve_min !q in\n",
" q := supprime min !q;\n",
" min\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val diminuer_clef : 'a -> int -> 'a priopqueue -> unit = \n"
]
},
"execution_count": 54,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* [diminuer_clef q clef x] modifie la clef de l'élément [x]\n",
" dans la file q en lui associant la nouvelle clef [clef], qui\n",
" doit être inferieur à la clef actuelle de [x].\n",
" Termine avec une exception si la file ne contient pas [x] *)\n",
"let diminuer_clef (x:'a) (clef:int) (q:'a priopqueue) : unit =\n",
" let rec diminuer_aux (l:(int*'a) list) : (int*'a) list =\n",
" match l with\n",
" | [ ] -> failwith \"diminuer_clef : l'élément n'est pas présent\"\n",
" | (_, v) :: q when v=x -> (clef, x) :: q\n",
" | (c, v) :: q -> (c, v) :: diminuer_aux q in\n",
" q := diminuer_aux !q\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Dijkstra, 2ème version"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"C'est aussi assez direct :"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val dijkstra : graph -> int array * int array = \n"
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let dijkstra g =\n",
" let q = vide () in\n",
" let dist = Array.init g.taille (fun i ->\n",
" if i=g.entree then 0 else max_int\n",
" ) in\n",
" let pere = Array.init g.taille (fun i -> i) in\n",
" for i=0 to g.taille - 1 do (* initialisation de la file *)\n",
" inserer i dist.(i) q;\n",
" done;\n",
" while not (est_vide q) do\n",
" let x = extraire_min q in\n",
" (* on regarde les adjacents de x *)\n",
" List.iter (fun (c,y) ->\n",
" if dist.(y) > dist.(x) + c\n",
" then begin\n",
" pere.(y) <- x;\n",
" dist.(y) <- dist.(x) + c;\n",
" diminuer_clef y dist.(y) q\n",
" end) g.adj.(x)\n",
" done;\n",
" dist, pere\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exemples"
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int array * int array = ([|0; 2; 3; 2; 3|], [|0; 0; 3; 0; 1|])\n"
]
},
"execution_count": 56,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let _ = dijkstra g1;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Et les contre-exemples maintenant :"
]
},
{
"cell_type": "code",
"execution_count": 57,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int array * int array =\n",
"([|0; 2; 3; 2; 3; 4611686018427387903; -4611686018427387900|],\n",
" [|0; 0; 3; 0; 1; 5; 5|])\n"
]
},
"execution_count": 57,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let _ = dijkstra g2;;"
]
},
{
"cell_type": "code",
"execution_count": 58,
"metadata": {},
"outputs": [
{
"ename": "error",
"evalue": "runtime_error",
"output_type": "error",
"traceback": [
"\u001b[31mException:\nFailure \"diminuer_clef : l'\\195\\169l\\195\\169ment n'est pas pr\\195\\169sent\".\nRaised at file \"pervasives.ml\", line 32, characters 22-33\nCalled from file \"[54]\", line 10, characters 35-49\nCalled from file \"[54]\", line 10, characters 35-49\nCalled from file \"[54]\", line 11, characters 9-24\nCalled from file \"list.ml\", line 77, characters 12-15\nCalled from file \"[55]\", line 13, characters 8-232\nCalled from file \"toplevel/toploop.ml\", line 180, characters 17-56\n\u001b[0m"
]
}
],
"source": [
"let _ = dijkstra g3;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"## Arbres couvrants de poids minimal\n",
"\n",
"On ne traite que l'algorithme de Prim. L'algorithme de Kruskal n'est pas plus compliqué, il utilise une autre structure de données (Union-Find, déjà traité aussi)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Algorithme de Prim"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val prim : graph -> int array * int array = \n"
]
},
"execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let prim g =\n",
" let q = vide () in\n",
" let poids = Array.init g.taille (fun i ->\n",
" if i=g.entree then 0 else max_int\n",
" ) in\n",
" let pere = Array.init g.taille (fun i -> i) in\n",
" for i=0 to g.taille-1 do (* initialisation de la file *)\n",
" inserer i poids.(i) q;\n",
" done;\n",
" while not (est_vide q) do\n",
" let x = extraire_min q in\n",
" (* on regarde les adjacents de x *)\n",
" List.iter (fun (c,y) ->\n",
" if poids.(y) > c\n",
" then begin\n",
" pere.(y) <- x;\n",
" poids.(y) <- c;\n",
" diminuer_clef y poids.(y) q\n",
" end)\n",
" g.adj.(x)\n",
" done;\n",
" Array.iteri (fun i p ->\n",
" if i != p then Printf.printf \" (%d, %d)\\n\" i p\n",
" ) pere;\n",
" poids, pere;\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exemple"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int array * int array = ([|0; 2; 1; 2; 1|], [|0; 0; 3; 0; 1|])\n"
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let _ = prim g1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"## Tas binaire min"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"module type Ordered = sig type t val le : t -> t -> bool end\n"
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"exception Empty\n"
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"module Make :\n",
" functor (X : Ordered) ->\n",
" sig\n",
" type t\n",
" val empty : t\n",
" val is_empty : t -> bool\n",
" val insert : X.t -> t -> t\n",
" val min : t -> X.t\n",
" val extract_min : t -> X.t * t\n",
" val merge : t -> t -> t\n",
" val length : t -> int\n",
" end\n"
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(** {2 Leftist heaps, by Jean-Christophe Filliâtre} *)\n",
"\n",
"(**************************************************************************)\n",
"(* *)\n",
"(* Copyright (C) Jean-Christophe Filliâtre *)\n",
"(* *)\n",
"(* This software is free software; you can redistribute it and/or *)\n",
"(* modify it under the terms of the GNU Library General Public *)\n",
"(* License version 2.1, with the special exception on linking *)\n",
"(* described in file LICENSE. *)\n",
"(* *)\n",
"(* This software is distributed in the hope that it will be useful, *)\n",
"(* but WITHOUT ANY WARRANTY; without even the implied warranty of *)\n",
"(* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. *)\n",
"(* *)\n",
"(**************************************************************************)\n",
"\n",
"(* Leftist heaps.\n",
"\n",
" See for instance Chris Okasaki's \"Purely Functional Data Structures\" *)\n",
"\n",
"module type Ordered = sig\n",
" type t\n",
" val le: t -> t -> bool\n",
"end\n",
"\n",
"exception Empty\n",
"\n",
"module Make(X : Ordered) :\n",
"sig\n",
" type t\n",
" val empty : t\n",
" val is_empty : t -> bool\n",
" val insert : X.t -> t -> t\n",
" val min : t -> X.t\n",
" val extract_min : t -> X.t * t\n",
" val merge : t -> t -> t\n",
" val length : t -> int\n",
"end\n",
"=\n",
"struct\n",
"\n",
" type t = E | T of int * X.t * t * t\n",
"\n",
" let rank = function E -> 0 | T (r,_,_,_) -> r\n",
"\n",
" let rec length = function E -> 0 | T (_,_,t1,t2) -> 1 + (length t1) + (length t2)\n",
"\n",
" let make x a b =\n",
" let ra = rank a and rb = rank b in\n",
" if ra >= rb then T (rb + 1, x, a, b) else T (ra + 1, x, b, a)\n",
"\n",
" let empty = E\n",
"\n",
" let is_empty = function E -> true | T _ -> false\n",
"\n",
" let rec merge h1 h2 = match h1,h2 with\n",
" | E, h | h, E ->\n",
" h\n",
" | T (_,x,a1,b1), T (_,y,a2,b2) ->\n",
" if X.le x y then make x a1 (merge b1 h2) else make y a2 (merge h1 b2)\n",
"\n",
" let insert x h = merge (T (1, x, E, E)) h\n",
"\n",
" let min = function E -> raise Empty | T (_,x,_,_) -> x\n",
"\n",
" let extract_min = function\n",
" | E -> raise Empty\n",
" | T (_,x,a,b) -> x, merge a b\n",
"\n",
"end"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"## Codage de Huffman\n",
"\n",
"C'est un grand classique pour les leçons \"Programmation dynamique\" et \"Algorithmique du texte\".\n",
"Le présenter en développement sans l'avoir implémenter est difficilement pardonnable."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"TODO : utiliser une file de priorité mutable plutôt qu'un tas min ? Je n'ai pas encore eu le temps de terminer cette correction."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Fréquences de lettres dans un texte"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val frequencies : string -> (char, int) Hashtbl.t = \n"
]
},
"execution_count": 40,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(** Calcule l'alphabet du texte [text] ainsi que son tableau de fréquence.\n",
" Linéaire en temps et espace dans la taille du texte. *)\n",
"let frequencies text =\n",
" let n = String.length text in\n",
" let f = Hashtbl.create 128 in\n",
" for i = 0 to n-1 do\n",
" if Hashtbl.mem f text.[i] then\n",
" Hashtbl.replace f text.[i] (1 + Hashtbl.find f text.[i])\n",
" else Hashtbl.add f text.[i] 1;\n",
" done;\n",
" f\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val alphabet : string -> char list = \n"
]
},
"execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(** Renvoie juste l'alphabet qui compose le texte [text]. *)\n",
"let alphabet text =\n",
" let f = frequencies text in\n",
" let alp = ref [ ] in\n",
" Hashtbl.iter (fun carct _ -> alp := carct :: !alp) f;\n",
" !alp\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val text1 : string =\n",
" \"https://www.un.org/fr/universal-declaration-human-rights/index.html : Article premier\\n\\nTous les etres humains naissent libres et egaux en dignite et en droits. Ils sont doues de raison et de conscience et doivent agir les uns envers les autres dans un esprit de fraternite.\\nArticle 2\\n\\n1. Chacun peut se prevaloir de tous les droits et de toutes les libertes proclames dans la presente Declaration, sans distinction aucune, notamment de race, de couleur, de sexe, de langue, de religion, d'opinion politique ou de toute autre opinion, d'origine nationale ou sociale, de fortune, de naissance ou de toute autre situation.\\n2. De plus, il ne sera fait aucune distinction fondee sur le statut politique, juridique ou international du pays ou du territoire dont une personne est ressortissante, que ce pays ou territoire soit independant, sous tutelle, non autonome ou soumis a une limitation quelconque de souverainete.\"\n"
]
},
"execution_count": 51,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : char list =\n",
"['l'; '2'; 'h'; '1'; 'g'; 'f'; 'j'; 'o'; 'y'; 'e'; '-'; 'v'; 'm'; 'D'; 'd';\n",
" 'i'; 'b'; ' '; 'C'; 'u'; 'n'; 't'; 'q'; ':'; 'T'; 'p'; 'A'; '/'; 'I'; ',';\n",
" 'x'; 'a'; 'r'; 'c'; 'w'; 's'; '\\n'; '.'; '\\'']\n"
]
},
"execution_count": 51,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(** Un exemple. https://www.un.org/fr/universal-declaration-human-rights/index.html *)\n",
"let text1 = \"https://www.un.org/fr/universal-declaration-human-rights/index.html : Article premier\\n\\nTous les etres humains naissent libres et egaux en dignite et en droits. Ils sont doues de raison et de conscience et doivent agir les uns envers les autres dans un esprit de fraternite.\\nArticle 2\\n\\n1. Chacun peut se prevaloir de tous les droits et de toutes les libertes proclames dans la presente Declaration, sans distinction aucune, notamment de race, de couleur, de sexe, de langue, de religion, d'opinion politique ou de toute autre opinion, d'origine nationale ou sociale, de fortune, de naissance ou de toute autre situation.\\n2. De plus, il ne sera fait aucune distinction fondee sur le statut politique, juridique ou international du pays ou du territoire dont une personne est ressortissante, que ce pays ou territoire soit independant, sous tutelle, non autonome ou soumis a une limitation quelconque de souverainete.\";;\n",
"let _ = alphabet text1;;"
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val print : ('a, Format.formatter, unit) format -> 'a = \n"
]
},
"execution_count": 52,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val print_frequencies : (char, int) Hashtbl.t -> unit = \n"
]
},
"execution_count": 52,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(** Pour affiche facilement. *)\n",
"let print = Format.printf;;\n",
"\n",
"(** Pour visualiser un tableau des fréquences ainsi calculée. *)\n",
"let print_frequencies f =\n",
" flush_all();\n",
" print \"\\n\\nTable des fréquences f :\\n\";\n",
" flush_all();\n",
" Hashtbl.iter (fun carct freq -> print \"%C: %i, \" carct freq) f;\n",
" flush_all();\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"'\\'': 2, '.': 9, '\\n': 6, 's': 60, 'w': 3, 'c': 19, 'r': 47, 'a': 46, 'x': 3, ',': 15, 'I': 1, '/': 5, 'A': 2, 'p': 16, 'T': 1, ':': 2, 'q': 6, 't': 70, 'n': 67, 'u': 53, 'C': 1, ' ': 134, 'b': 2, 'i': 64, 'd': 35, 'D': 2, 'm': 10, 'v': 5, '-': 3, 'e': 112, 'y': 2, 'o': 56, 'j': 1, 'f': 5, 'g': 8, '1': 1, 'h': 6, '2': 2, 'l': 32, \n",
"\n",
"Table des fréquences f :\n"
]
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 73,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"print_frequencies (frequencies text1);;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Structure de tas binaire min"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type codage = F of char * int | N of (int * codage * codage)\n"
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val freq : codage -> int = \n"
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"module CodageFreq : sig type t = codage val le : codage -> codage -> bool end\n"
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"module MinHeap :\n",
" sig\n",
" type t = Make(CodageFreq).t\n",
" val empty : t\n",
" val is_empty : t -> bool\n",
" val insert : CodageFreq.t -> t -> t\n",
" val min : t -> CodageFreq.t\n",
" val extract_min : t -> CodageFreq.t * t\n",
" val merge : t -> t -> t\n",
" val length : t -> int\n",
" end\n"
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val check_freq : codage -> unit = \n"
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* #use \"Heap.ml\";; *)\n",
"(* open Heap;; *)\n",
"\n",
"type codage =\n",
" | F of char * int | N of (int * codage * codage);;\n",
"\n",
"let freq = function F (_, i) -> i | N (i,_ , _) -> i;;\n",
"\n",
"module CodageFreq = struct\n",
" type t = codage\n",
" let le c1 c2 = (freq c1) <= (freq c2)\n",
"end;;\n",
"\n",
"module MinHeap = Make(CodageFreq);;\n",
"\n",
"let rec check_freq = function\n",
" | F(_,i) -> assert( (i >= 0) )\n",
" | N(i, c1, c2) -> assert( (i >= 0) && (i = (freq c1) + (freq c2)) ); check_freq c1; check_freq c2;\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exemple d'un codage préfixe (Figure 16.4 p378 du Cormen)"
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val sigma_fromlist : ('a * 'b) list -> ('a, 'b) Hashtbl.t = \n"
]
},
"execution_count": 56,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val sigma1 : (char, int) Hashtbl.t = \n"
]
},
"execution_count": 56,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val codage1 : codage =\n",
" N\n",
" (100, F ('a', 45),\n",
" N\n",
" (55, N (25, F ('c', 12), F ('b', 13)),\n",
" N (30, N (14, F ('f', 5), F ('e', 9)), F ('d', 16))))\n"
]
},
"execution_count": 56,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let sigma_fromlist l =\n",
" let h = Hashtbl.create (List.length l) in\n",
" List.iter (fun (c, f) -> Hashtbl.add h c f) l;\n",
" h\n",
";;\n",
"\n",
"let sigma1 = sigma_fromlist [('f', 5); ('e', 9); ('c', 12); ('b', 13); ('d', 16); ('a', 45) ];;\n",
"\n",
"let codage1 = N(100,\n",
" F('a', 45),\n",
" N(55,\n",
" N(25,\n",
" F('c',12),\n",
" F('b',13)\n",
" ),\n",
" N(30,\n",
" N(14,\n",
" F('f',5),\n",
" F('e',9)\n",
" ),\n",
" F('d',16)\n",
" )\n",
")\n",
");;"
]
},
{
"cell_type": "code",
"execution_count": 57,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 57,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let _ = check_freq codage1;;"
]
},
{
"cell_type": "code",
"execution_count": 58,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val coutx : int -> codage -> int = \n"
]
},
"execution_count": 58,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val cout : codage -> int = \n"
]
},
"execution_count": 58,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 324\n"
]
},
"execution_count": 58,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(** Calcul du nombre de bits nécessaires pour stocker le fichier. *)\n",
"let rec coutx prof = function\n",
" | F(c, f) -> begin\n",
" print \"\\nFeuille %C de profondeur %i et de fréquence %i.\" c prof f;\n",
" (f * prof);\n",
" end\n",
" | N(_, c1, c2) -> (coutx (prof+1) c1) + (coutx (prof+1) c2)\n",
";;\n",
"\n",
"(** Il faudrait rajouter la taille du codage lui-même. *)\n",
"let cout = coutx 1;;\n",
"\n",
"let _ = cout codage1;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Algorithme glouton de codage préfixe optimal de Huffman"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On commence avec une fonction auxiliaire :"
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val huffmanx : (char, int) Hashtbl.t -> CodageFreq.t = \n"
]
},
"execution_count": 59,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let huffmanx sigma =\n",
" let n = Hashtbl.length sigma in\n",
" let q = ref (MinHeap.empty) in\n",
" Hashtbl.iter (fun c f -> q := (MinHeap.insert (F(c,f)) !q) ) sigma;\n",
" for i = 1 to n-1 do\n",
" flush_all();\n",
" print \"\\n\\nHuffmanx : %i-ième étape. La file q est de taille %i.\" i (MinHeap.length !q);\n",
" let x, q2 = MinHeap.extract_min (!q) in\n",
" flush_all();\n",
" print \"\\nOn retire à q le noeud x de fréquence minimale (= %i).\" (freq x);\n",
" let y, q3 = MinHeap.extract_min q2 in\n",
" flush_all();\n",
" print \"\\nOn retire à q second noeud y de fréquence minimale (= %i).\" (freq y);\n",
" q := q3;\n",
" let z = N( (freq x) + (freq y), x, y) in\n",
" flush_all();\n",
" print \"\\nOn les fusionne en z un nouveau noeud de fréquence %i, de fils gauche = x et droit = y.\" ( freq z );\n",
" q := MinHeap.insert z !q;\n",
" flush_all();\n",
" print \"\\nOn ajoute ce noeud z a la file de priorité min q.\";\n",
" done;\n",
" MinHeap.min !q\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"On les fusionne en z un nouveau noeud de fréquence 54, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 1-ième étape. La file q est de taille 6.\n",
"On retire à q le noeud x de fréquence minimale (= 5).\n",
"On retire à q second noeud y de fréquence minimale (= 9).\n",
"On les fusionne en z un nouveau noeud de fréquence 14, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 2-ième étape. La file q est de taille 5.\n",
"On retire à q le noeud x de fréquence minimale (= 12).\n",
"On retire à q second noeud y de fréquence minimale (= 13).\n",
"On les fusionne en z un nouveau noeud de fréquence 25, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 3-ième étape. La file q est de taille 4.\n",
"On retire à q le noeud x de fréquence minimale (= 14).\n",
"On retire à q second noeud y de fréquence minimale (= 16).\n",
"On les fusionne en z un nouveau noeud de fréquence 30, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 4-ième étape. La file q est de taille 3.\n",
"On retire à q le noeud x de fréquence minimale (= 25).\n",
"On retire à q second noeud y de fréquence minimale (= 30).\n",
"On les fusionne en z un nouveau noeud de fréquence 55, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 5-ième étape. La file q est de taille 2.\n",
"On retire à q le noeud x de fréquence minimale (= 45).\n",
"On retire à q second noeud y de fréquence minimale (= 55).\n"
]
},
{
"data": {
"text/plain": [
"- : unit = ()\n"
]
},
"execution_count": 62,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(* Vérification sur l'exemple. *)\n",
"assert(codage1 = (huffmanx sigma1));;"
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val huffman : string -> CodageFreq.t = \n"
]
},
"execution_count": 61,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val sigma2 : (char, int) Hashtbl.t = \n"
]
},
"execution_count": 61,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"On les fusionne en z un nouveau noeud de fréquence 100, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 1-ième étape. La file q est de taille 8.\n",
"On retire à q le noeud x de fréquence minimale (= 1).\n",
"On retire à q second noeud y de fréquence minimale (= 1).\n",
"On les fusionne en z un nouveau noeud de fréquence 2, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 2-ième étape. La file q est de taille 7.\n",
"On retire à q le noeud x de fréquence minimale (= 2).\n",
"On retire à q second noeud y de fréquence minimale (= 2).\n",
"On les fusionne en z un nouveau noeud de fréquence 4, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 3-ième étape. La file q est de taille 6.\n",
"On retire à q le noeud x de fréquence minimale (= 3).\n",
"On retire à q second noeud y de fréquence minimale (= 4).\n",
"On les fusionne en z un nouveau noeud de fréquence 7, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 4-ième étape. La file q est de taille 5.\n",
"On retire à q le noeud x de fréquence minimale (= 5).\n",
"On retire à q second noeud y de fréquence minimale (= 7).\n",
"On les fusionne en z un nouveau noeud de fréquence 12, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 5-ième étape. La file q est de taille 4.\n",
"On retire à q le noeud x de fréquence minimale (= 8).\n",
"On retire à q second noeud y de fréquence minimale (= 12).\n",
"On les fusionne en z un nouveau noeud de fréquence 20, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 6-ième étape. La file q est de taille 3.\n",
"On retire à q le noeud x de fréquence minimale (= 13).\n",
"On retire à q second noeud y de fréquence minimale (= 20).\n",
"On les fusionne en z un nouveau noeud de fréquence 33, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 7-ième étape. La file q est de taille 2.\n",
"On retire à q le noeud x de fréquence minimale (= 21).\n",
"On retire à q second noeud y de fréquence minimale (= 33).\n"
]
},
{
"data": {
"text/plain": [
"- : CodageFreq.t =\n",
"N\n",
" (54, F ('h', 21),\n",
" N\n",
" (33, F ('g', 13),\n",
" N\n",
" (20, F ('f', 8),\n",
" N\n",
" (12, F ('e', 5),\n",
" N (7, F ('d', 3), N (4, N (2, F ('b', 1), F ('a', 1)), F ('c', 2)))))))\n"
]
},
"execution_count": 61,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(** Pour un texte entier, on calcule directement le codage. *)\n",
"let huffman text =\n",
" let freq = frequencies text in\n",
" huffmanx freq\n",
";;\n",
"\n",
"let sigma2 = sigma_fromlist [ ('a',1); ('b',1); ('c',2); ('d',3); ('e',5); ('f',8); ('g',13); ('h',21) ];;\n",
"let _ = huffmanx sigma2;;"
]
},
{
"cell_type": "code",
"execution_count": 74,
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"'\\'': 2, '.': 9, '\\n': 6, 's': 60, 'w': 3, 'c': 19, 'r': 47, 'a': 46, 'x': 3, ',': 15, 'I': 1, '/': 5, 'A': 2, 'p': 16, 'T': 1, ':': 2, 'q': 6, 't': 70, 'n': 67, 'u': 53, 'C': 1, ' ': 134, 'b': 2, 'i': 64, 'd': 35, 'D': 2, 'm': 10, 'v': 5, '-': 3, 'e': 112, 'y': 2, 'o': 56, 'j': 1, 'f': 5, 'g': 8, '1': 1, 'h': 6, '2': 2, 'l': 32, \n",
"\n",
"Huffmanx : 1-ième étape. La file q est de taille 39.\n",
"On retire à q le noeud x de fréquence minimale (= 1).\n",
"On retire à q second noeud y de fréquence minimale (= 1).\n",
"On les fusionne en z un nouveau noeud de fréquence 2, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 2-ième étape. La file q est de taille 38.\n",
"On retire à q le noeud x de fréquence minimale (= 1).\n",
"On retire à q second noeud y de fréquence minimale (= 1).\n",
"On les fusionne en z un nouveau noeud de fréquence 2, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 3-ième étape. La file q est de taille 37.\n",
"On retire à q le noeud x de fréquence minimale (= 1).\n",
"On retire à q second noeud y de fréquence minimale (= 2).\n",
"On les fusionne en z un nouveau noeud de fréquence 3, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 4-ième étape. La file q est de taille 36.\n",
"On retire à q le noeud x de fréquence minimale (= 2).\n",
"On retire à q second noeud y de fréquence minimale (= 2).\n",
"On les fusionne en z un nouveau noeud de fréquence 4, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 5-ième étape. La file q est de taille 35.\n",
"On retire à q le noeud x de fréquence minimale (= 2).\n",
"On retire à q second noeud y de fréquence minimale (= 2).\n",
"On les fusionne en z un nouveau noeud de fréquence 4, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 6-ième étape. La file q est de taille 34.\n",
"On retire à q le noeud x de fréquence minimale (= 2).\n",
"On retire à q second noeud y de fréquence minimale (= 2).\n",
"On les fusionne en z un nouveau noeud de fréquence 4, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 7-ième étape. La file q est de taille 33.\n",
"On retire à q le noeud x de fréquence minimale (= 2).\n",
"On retire à q second noeud y de fréquence minimale (= 2).\n",
"On les fusionne en z un nouveau noeud de fréquence 4, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 8-ième étape. La file q est de taille 32.\n",
"On retire à q le noeud x de fréquence minimale (= 3).\n",
"On retire à q second noeud y de fréquence minimale (= 3).\n",
"On les fusionne en z un nouveau noeud de fréquence 6, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 9-ième étape. La file q est de taille 31.\n",
"On retire à q le noeud x de fréquence minimale (= 3).\n",
"On retire à q second noeud y de fréquence minimale (= 3).\n",
"On les fusionne en z un nouveau noeud de fréquence 6, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 10-ième étape. La file q est de taille 30.\n",
"On retire à q le noeud x de fréquence minimale (= 4).\n",
"On retire à q second noeud y de fréquence minimale (= 4).\n",
"On les fusionne en z un nouveau noeud de fréquence 8, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 11-ième étape. La file q est de taille 29.\n",
"On retire à q le noeud x de fréquence minimale (= 4).\n",
"On retire à q second noeud y de fréquence minimale (= 4).\n",
"On les fusionne en z un nouveau noeud de fréquence 8, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 12-ième étape. La file q est de taille 28.\n",
"On retire à q le noeud x de fréquence minimale (= 5).\n",
"On retire à q second noeud y de fréquence minimale (= 5).\n",
"On les fusionne en z un nouveau noeud de fréquence 10, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 13-ième étape. La file q est de taille 27.\n",
"On retire à q le noeud x de fréquence minimale (= 5).\n",
"On retire à q second noeud y de fréquence minimale (= 6).\n",
"On les fusionne en z un nouveau noeud de fréquence 11, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 14-ième étape. La file q est de taille 26.\n",
"On retire à q le noeud x de fréquence minimale (= 6).\n",
"On retire à q second noeud y de fréquence minimale (= 6).\n",
"On les fusionne en z un nouveau noeud de fréquence 12, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 15-ième étape. La file q est de taille 25.\n",
"On retire à q le noeud x de fréquence minimale (= 6).\n",
"On retire à q second noeud y de fréquence minimale (= 6).\n",
"On les fusionne en z un nouveau noeud de fréquence 12, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 16-ième étape. La file q est de taille 24.\n",
"On retire à q le noeud x de fréquence minimale (= 8).\n",
"On retire à q second noeud y de fréquence minimale (= 8).\n",
"On les fusionne en z un nouveau noeud de fréquence 16, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 17-ième étape. La file q est de taille 23.\n",
"On retire à q le noeud x de fréquence minimale (= 8).\n",
"On retire à q second noeud y de fréquence minimale (= 9).\n",
"On les fusionne en z un nouveau noeud de fréquence 17, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 18-ième étape. La file q est de taille 22.\n",
"On retire à q le noeud x de fréquence minimale (= 10).\n",
"On retire à q second noeud y de fréquence minimale (= 10).\n",
"On les fusionne en z un nouveau noeud de fréquence 20, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 19-ième étape. La file q est de taille 21.\n",
"On retire à q le noeud x de fréquence minimale (= 11).\n",
"On retire à q second noeud y de fréquence minimale (= 12).\n",
"On les fusionne en z un nouveau noeud de fréquence 23, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 20-ième étape. La file q est de taille 20.\n",
"On retire à q le noeud x de fréquence minimale (= 12).\n",
"On retire à q second noeud y de fréquence minimale (= 15).\n",
"On les fusionne en z un nouveau noeud de fréquence 27, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 21-ième étape. La file q est de taille 19.\n",
"On retire à q le noeud x de fréquence minimale (= 16).\n",
"On retire à q second noeud y de fréquence minimale (= 16).\n",
"On les fusionne en z un nouveau noeud de fréquence 32, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 22-ième étape. La file q est de taille 18.\n",
"On retire à q le noeud x de fréquence minimale (= 17).\n",
"On retire à q second noeud y de fréquence minimale (= 19).\n",
"On les fusionne en z un nouveau noeud de fréquence 36, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 23-ième étape. La file q est de taille 17.\n",
"On retire à q le noeud x de fréquence minimale (= 20).\n",
"On retire à q second noeud y de fréquence minimale (= 23).\n",
"On les fusionne en z un nouveau noeud de fréquence 43, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 24-ième étape. La file q est de taille 16.\n",
"On retire à q le noeud x de fréquence minimale (= 27).\n",
"On retire à q second noeud y de fréquence minimale (= 32).\n",
"On les fusionne en z un nouveau noeud de fréquence 59, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 25-ième étape. La file q est de taille 15.\n",
"On retire à q le noeud x de fréquence minimale (= 32).\n",
"On retire à q second noeud y de fréquence minimale (= 35).\n",
"On les fusionne en z un nouveau noeud de fréquence 67, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 26-ième étape. La file q est de taille 14.\n",
"On retire à q le noeud x de fréquence minimale (= 36).\n",
"On retire à q second noeud y de fréquence minimale (= 43).\n",
"On les fusionne en z un nouveau noeud de fréquence 79, de fils gauche = x et droit = y.\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 27-ième étape. La file q est de taille 13.\n",
"On retire à q le noeud x de fréquence minimale (= 46).\n",
"On retire à q second noeud y de fréquence minimale (= 47).\n",
"On les fusionne en z un nouveau noeud de fréquence 93, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 28-ième étape. La file q est de taille 12.\n",
"On retire à q le noeud x de fréquence minimale (= 53).\n",
"On retire à q second noeud y de fréquence minimale (= 56).\n",
"On les fusionne en z un nouveau noeud de fréquence 109, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 29-ième étape. La file q est de taille 11.\n",
"On retire à q le noeud x de fréquence minimale (= 59).\n",
"On retire à q second noeud y de fréquence minimale (= 60).\n",
"On les fusionne en z un nouveau noeud de fréquence 119, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 30-ième étape. La file q est de taille 10.\n",
"On retire à q le noeud x de fréquence minimale (= 64).\n",
"On retire à q second noeud y de fréquence minimale (= 67).\n",
"On les fusionne en z un nouveau noeud de fréquence 131, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 31-ième étape. La file q est de taille 9.\n",
"On retire à q le noeud x de fréquence minimale (= 67).\n",
"On retire à q second noeud y de fréquence minimale (= 70).\n",
"On les fusionne en z un nouveau noeud de fréquence 137, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 32-ième étape. La file q est de taille 8.\n",
"On retire à q le noeud x de fréquence minimale (= 79).\n",
"On retire à q second noeud y de fréquence minimale (= 93).\n",
"On les fusionne en z un nouveau noeud de fréquence 172, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 33-ième étape. La file q est de taille 7.\n",
"On retire à q le noeud x de fréquence minimale (= 109).\n",
"On retire à q second noeud y de fréquence minimale (= 112).\n",
"On les fusionne en z un nouveau noeud de fréquence 221, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 34-ième étape. La file q est de taille 6.\n",
"On retire à q le noeud x de fréquence minimale (= 119).\n",
"On retire à q second noeud y de fréquence minimale (= 131).\n",
"On les fusionne en z un nouveau noeud de fréquence 250, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 35-ième étape. La file q est de taille 5.\n",
"On retire à q le noeud x de fréquence minimale (= 134).\n",
"On retire à q second noeud y de fréquence minimale (= 137).\n",
"On les fusionne en z un nouveau noeud de fréquence 271, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 36-ième étape. La file q est de taille 4.\n",
"On retire à q le noeud x de fréquence minimale (= 172).\n",
"On retire à q second noeud y de fréquence minimale (= 221).\n",
"On les fusionne en z un nouveau noeud de fréquence 393, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 37-ième étape. La file q est de taille 3.\n",
"On retire à q le noeud x de fréquence minimale (= 250).\n",
"On retire à q second noeud y de fréquence minimale (= 271).\n",
"On les fusionne en z un nouveau noeud de fréquence 521, de fils gauche = x et droit = y.\n",
"On ajoute ce noeud z a la file de priorité min q.\n",
"\n",
"Huffmanx : 38-ième étape. La file q est de taille 2.\n",
"On retire à q le noeud x de fréquence minimale (= 393).\n",
"On retire à q second noeud y de fréquence minimale (= 521).\n"
]
},
{
"data": {
"text/plain": [
"- : CodageFreq.t =\n",
"N\n",
" (914,\n",
" N\n",
" (393,\n",
" N\n",
" (172,\n",
" N\n",
" (79, N (36, N (17, F ('g', 8), F ('.', 9)), F ('c', 19)),\n",
" N\n",
" (43, N (20, N (10, F ('/', 5), F ('v', 5)), F ('m', 10)),\n",
" N\n",
" (23, N (11, F ('f', 5), F ('\\n', 6)),\n",
" N\n",
" (12, N (6, F ('-', 3), N (3, F ('I', 1), F ('\\'', 2))),\n",
" F ('q', 6))))),\n",
" N (93, F ('a', 46), F ('r', 47))),\n",
" N (221, N (109, F ('u', 53), F ('o', 56)), F ('e', 112))),\n",
" N\n",
" (521,\n",
" N\n",
" (250,\n",
" N\n",
" (119,\n",
" N\n",
" (59,\n",
" N\n",
" (27, N (12, N (6, F ('x', 3), F ('w', 3)), F ('h', 6)),\n",
" F (',', 15)),\n",
" N\n",
" (32, F ('p', 16),\n",
" N\n",
" (16,\n",
" N\n",
" (8, N (4, F ('2', 2), F ('b', 2)),\n",
" N (4, N (2, F ('C', 1), F ('T', 1)), F ('A', 2))),\n",
" N\n",
" (8, N (4, F ('y', 2), F ('D', 2)),\n",
" N (4, F (':', 2), N (2, F ('1', 1), F ('j', 1))))))),\n",
" F ('s', 60)),\n",
" N (131, F ('i', 64), N (67, F ('l', 32), F ('d', 35)))),\n",
" N (271, F (' ', 134), N (137, F ('n', 67), F ('t', 70)))))\n"
]
},
"execution_count": 74,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let _ = huffman text1;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"## Coloration de graphes\n",
"\n",
"Voyons une approche gloutonne.\n",
"\n",
"On va trier les sommets par degrés décroissants, et attribuer à chaque sommet une couleur, soit la plus petite possible parmi celles non utilisées par ces voisins, soit une nouvelle.\n",
"\n",
"On représente un graphe par tableau de listes d'adjacence. Notre exemple sera le graphe suivant, sans considérer les étiquettes des arêtes et en le considérant non orienté :"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Représentation des graphes"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type sommet = int\n"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"type graphe = sommet list array\n"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type sommet = int ;;\n",
"type graphe = (sommet list) array;;"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val nb_sommet : graphe -> int = \n"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let nb_sommet (g : graphe) = Array.length g;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Et des coloriages"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type couleur = int\n"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"type coloriage = couleur array\n"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type couleur = int;;\n",
"type coloriage = couleur array;; (* c.(i) est la couleur du sommet i... *)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val verifie_coloriage : graphe -> coloriage -> bool = \n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let verifie_coloriage (g : graphe) (c : coloriage) =\n",
" let res = ref true in\n",
" let n = nb_sommet g in\n",
" for i = 0 to n-1 do\n",
" if c.(i) < 0 || c.(i) >= n then res := false;\n",
" List.iter (fun j ->\n",
" if c.(i) == c.(j) then res := false;\n",
" ) g.(i)\n",
" done;\n",
" !res\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exemple"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val g1 : graphe = [|[1; 2; 3]; [0; 4]; [0; 3; 4]; [0; 2]; [1; 2]|]\n"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let g1 : graphe = [|\n",
" [1; 2; 3]; (* voisins de 0 *)\n",
" [0; 4]; (* voisins de 1 *)\n",
" [0; 3; 4]; (* voisins de 2 *)\n",
" [0; 2]; (* voisins de 3 *)\n",
" [1; 2] (* voisins de 4 *)\n",
"|];;"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val coloriage1 : int array = [|0; 1; 1; 1; 0|]\n"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = false\n"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val coloriage2 : int array = [|0; 1; 2; 1; 0|]\n"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let coloriage1 = [|0; 1; 1; 1; 0|];;\n",
"let _ = verifie_coloriage g1 coloriage1;; (* 3 -> 2 mais ont la même couleur *)\n",
"\n",
"let coloriage2 = [|0; 1; 2; 1; 0|];;\n",
"let _ = verifie_coloriage g1 coloriage2;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On a bien sûr une approche naïve :"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val coloriage_naif : graphe -> coloriage = \n"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let coloriage_naif (g : graphe) : coloriage =\n",
" let n = nb_sommet g in\n",
" Array.init n (fun i -> i);\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val coloriage3 : coloriage = [|0; 1; 2; 3; 4|]\n"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let coloriage3 = coloriage_naif g1;;\n",
"let _ = verifie_coloriage g1 coloriage3;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"C'est une borne supérieure triviale sur le nombre minimal de couleur requis pour colorier un graphe."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Algorithme glouton pour le coloriage\n",
"\n",
"Pour plus de détails, voir par exemple [cette page là](http://jean-paul.davalan.pagesperso-orange.fr/graphs/col/index.html)."
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val degres : graphe -> int array = \n"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let degres (g : graphe) : int array =\n",
" Array.map List.length g\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int array = [|3; 2; 3; 2; 2|]\n"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let _ = degres g1;;"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"type permutation = int array\n"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val trie_par_degres : graphe -> permutation = \n"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type permutation = int array;;\n",
"\n",
"let trie_par_degres (g : graphe) : permutation =\n",
" let n = nb_sommet g in\n",
" let indices = Array.init n (fun i -> i) in\n",
" let d = degres g in\n",
" let cmp_deg i j = Pervasives.compare d.(j) d.(i) in\n",
" Array.stable_sort cmp_deg indices;\n",
" indices\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : permutation = [|0; 2; 1; 3; 4|]\n"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let _ = trie_par_degres g1;;"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val plus_petite_couleur_libre : int -> couleur list -> couleur = \n"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let plus_petite_couleur_libre (n : int) (cs : couleur list) : couleur =\n",
" let rep = ref 0 in\n",
" while List.mem !rep cs do\n",
" incr rep\n",
" done;\n",
" assert (!rep < n);\n",
" !rep\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"val coloriage_glouton : graphe -> coloriage = \n"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let coloriage_glouton (g : graphe) : coloriage =\n",
" let n = nb_sommet g in\n",
" let c = Array.make n (-1) in\n",
" let perm = trie_par_degres g in\n",
" for i = 0 to n-1 do\n",
" (* on regarde le sommet perm.(i) *)\n",
" let couleurs_voisins = List.map (fun j -> c.(j)) g.(perm.(i)) in\n",
" c.(perm.(i)) <- plus_petite_couleur_libre n couleurs_voisins;\n",
" done;\n",
" c\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val coloriage_glouton_pas_trie : graphe -> coloriage = \n"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let coloriage_glouton_pas_trie (g : graphe) : coloriage =\n",
" let n = nb_sommet g in\n",
" let c = Array.make n (-1) in\n",
" for i = 0 to n-1 do\n",
" (* on regarde le sommet i *)\n",
" let couleurs_voisins = List.map (fun j -> c.(j)) g.(i) in\n",
" c.(i) <- plus_petite_couleur_libre n couleurs_voisins;\n",
" done;\n",
" c\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exemples"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val coloriage4 : coloriage = [|0; 1; 1; 2; 0|]\n"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let coloriage4 = coloriage_glouton g1;;\n",
"let _ = verifie_coloriage g1 coloriage4;;"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val coloriage5 : coloriage = [|0; 1; 1; 2; 0|]\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let coloriage5 = coloriage_glouton_pas_trie g1;;\n",
"let _ = verifie_coloriage g1 coloriage5;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On remarque que la procédure gloutonne a ici trouvé un coloriage minimal et optimal mais différent de celui proposé plus haut.\n",
"\n",
"- Comment peut-on vérifier que c'est un coloriage minimal ? Il faudrait essayer chaque changement de couleur (ce n'est pas simple)\n",
"- Et comment vérifier l'optimalité ? Il faudrait tester *tous* les coloriages à `c-1` couleurs (si celui là en a `c`) et montrer qu'aucun ne convient (ce n'est pas simple non plus, il y a beaucoup de coloriages possibles).\n",
"\n",
"Note : une première indication est qu'ici on a utilisé `c=3` couleurs avec un graphe de degré maximum $\\delta_{\\max} = 3$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Pour un contre exemple :"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val g2 : graphe =\n",
" [|[1; 2; 3; 4; 5]; [0; 2; 3; 4; 5]; [0; 1; 3; 4]; [0; 1; 2; 5]; [0; 1; 2];\n",
" [0; 1; 3]|]\n"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let g2 : graphe = [|\n",
" [1; 2; 3; 4; 5]; (* voisins de 0 *)\n",
" [0; 2; 3; 4; 5]; (* voisins de 1 *)\n",
" [0; 1; 3; 4]; (* voisins de 2 *)\n",
" [0; 1; 2; 5]; (* voisins de 3 *)\n",
" [0; 1; 2]; (* voisins de 4 *)\n",
" [0; 1; 3] (* voisins de 5 *)\n",
"|];;"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val coloriage6 : coloriage = [|0; 1; 2; 3; 3; 2|]\n"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let coloriage6 = coloriage_glouton g2;;\n",
"let _ = verifie_coloriage g2 coloriage6;;"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val coloriage6 : coloriage = [|0; 1; 2; 3; 3; 2|]\n"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let coloriage6 = coloriage_glouton_pas_trie g2;;\n",
"let _ = verifie_coloriage g2 coloriage6;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Et en changeant l'ordre des sommets :"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val g3 : graphe =\n",
" [|[5; 4; 2]; [5; 4; 3]; [5; 4; 3; 0]; [5; 4; 2; 1]; [5; 3; 2; 1; 0];\n",
" [4; 3; 2; 1; 0]|]\n"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let g3 : graphe = [|\n",
" [5; 4; 2]; (* voisins de 0 *)\n",
" [5; 4; 3]; (* voisins de 1 *)\n",
" [5; 4; 3; 0]; (* voisins de 2 *)\n",
" [5; 4; 2; 1]; (* voisins de 3 *)\n",
" [5; 3; 2; 1; 0]; (* voisins de 4 *)\n",
" [4; 3; 2; 1; 0] (* voisins de 5 *)\n",
"|];;"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val coloriage6 : coloriage = [|3; 2; 2; 3; 0; 1|]\n"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let coloriage6 = coloriage_glouton g3;;\n",
"let _ = verifie_coloriage g3 coloriage6;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Là on vérifie que l'ordre des sommets est important, par exemple si on ne trie pas les sommets par degrés décroissants, l'algorithme glouton trouche un coloriage sous-optimal (avec 5 couleurs ici) :"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val coloriage6 : coloriage = [|0; 0; 1; 2; 3; 4|]\n"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : bool = true\n"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let coloriage6 = coloriage_glouton_pas_trie g3;;\n",
"let _ = verifie_coloriage g3 coloriage6;;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Je n'ai pas trouvé de contre exemple qui donne un coloriage sous-optimal pour la première version (avec tri par degrés décroissants) de l'algorithme.\n",
"Si vous en avez un, [envoyez le moi !](https://perso.crans.org/besson/contact/)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"## Conclusion\n",
"\n",
"Fin. À la séance prochaine. Le dernier TP (TP8) traitera de programmation logique (en mai).\n",
"\n",
"> En attendant, essayez de finir ce sujet TP#7 et aussi la partie 2 (avec Python) du TP#6 sur le $\\lambda$-calcul."
]
}
],
"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_position": {
"height": "491px",
"left": "0px",
"right": "1141px",
"top": "134px",
"width": "238px"
},
"toc_section_display": "block",
"toc_window_display": false
},
"varInspector": {
"cols": {
"lenName": 16,
"lenType": 16,
"lenVar": 40
},
"kernels_config": {
"python": {
"delete_cmd_postfix": "",
"delete_cmd_prefix": "del ",
"library": "var_list.py",
"varRefreshCmd": "print(var_dic_list())"
},
"r": {
"delete_cmd_postfix": ") ",
"delete_cmd_prefix": "rm(",
"library": "var_list.r",
"varRefreshCmd": "cat(var_dic_list()) "
}
},
"types_to_exclude": [
"module",
"function",
"builtin_function_or_method",
"instance",
"_Feature"
],
"window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 2
}