Pouet (doc)

13 files changed, 437 insertions, 1 deletions

diff --git a/doc/Makefile.am b/doc/Makefile.am
index ee5aba4..d27abf6 100644
--- a/doc/Makefile.am
+++ b/doc/Makefile.am
@@ -1 +1,10 @@
-EXTRA_DIST = README.fr README.en
+ps:
+	make -f Makefile.doc ps
+
+clean:
+	make -f Makefile.doc clean
+
+distclean:
+	make -f Makefile.doc clean
+
+EXTRA_DIST = algo.tex algorithmes.tex bib.tex conclusion.tex description.tex intro.tex manuel.tex outils.tex structures.tex temps.tex
diff --git a/doc/README.en b/doc/README.en
deleted file mode 100644
index e69de29..0000000
--- a/doc/README.en
+++ /dev/null
diff --git a/doc/README.fr b/doc/README.fr
deleted file mode 100644
index e69de29..0000000
--- a/doc/README.fr
+++ /dev/null
diff --git a/doc/algo.tex b/doc/algo.tex
new file mode 100644
index 0000000..c1c164e
--- /dev/null
+++ b/doc/algo.tex
@@ -0,0 +1,89 @@
+%initialisations----------------------------------------------------------------
+\documentclass[french,11pt,a4paper,twoside,openright]{report}
+\usepackage[T1]{fontenc}
+\usepackage[latin1]{inputenc}
+\usepackage[francais]{babel}
+\usepackage{a4}
+\usepackage{ulem}
+\usepackage{multirow}
+\usepackage[dvips]{graphics}
+\usepackage{vmargin}
+\usepackage{fancyhdr}
+\usepackage{oldstyle}
+\usepackage{listings}
+\usepackage{verbatim}
+%fin des initialisations--------------------------------------------------------
+
+\pagestyle{fancyplain}
+\addtolength{\headwidth}{\marginparsep}
+\addtolength{\headwidth}{\marginparwidth}
+% titre de chapitre
+\renewcommand{\chaptermark}[1]{\markboth{#1} {}}
+% titre de section
+\renewcommand{\sectionmark}[1]{\markright{\thesection\ #1}}
+
+\lhead[\fancyplain{}{\bfseries\textos{\thepage}}]{\fancyplain{}{\bfseries\rightmark}}
+\rhead[\fancyplain{}{\bfseries\leftmark}]{\fancyplain{}{\bfseries\textos{\thepage}}}
+\cfoot{\fancyplain{\textos{\thepage}}{}}
+
+\newcommand{\clearemptydoublepage}{\newpage{\pagestyle{empty}\cleardoublepage}}
+
+\def\addcontentsline#1#2#3{%                                                    
+  \addtocontents{#1}{\protect\contentsline{#2}{#3}{\textos{\thepage}}}}
+% \setmargrb{leftmargin}{topmargin}{rightmargin}{bottommargin}
+\setmargrb{1.5cm}{2cm}{1.5cm}{4cm}
+
+\begin{document}
+\renewcommand{\chaptername}{Section}
+\newcommand{\bracebits}{$\underbrace{\hspace{2cm}}$}
+
+%page de garde
+\title{Projet d'Algorithmique\\
+	Rapport \vspace{1.0cm}}
+\author{Barrère Jordi, Noble Nicolas\vspace{2.0cm}}
+\date{\textit{dernière révision: \today}}
+\maketitle
+\strut\thispagestyle{empty}
+\vfill
+\pagebreak
+\setcounter{page}{1}
+
+
+
+\tableofcontents
+
+\clearemptydoublepage
+
+\input{intro}
+\clearemptydoublepage
+\part{Analyse}
+\input{description}
+\clearemptydoublepage
+\input{structures}
+\clearemptydoublepage
+\input{algorithmes}
+\clearemptydoublepage
+\input{temps}
+\clearemptydoublepage
+\part{Synthèse}
+\input{manuel}
+\clearemptydoublepage
+\input{outils}
+\clearemptydoublepage
+
+\chapter{Code source}
+\lstset{language=C++,basicstyle=\scriptsize,stringspaces=false}
+\input{source}
+
+\clearemptydoublepage
+\input{conclusion}
+\clearemptydoublepage
+\input{bib}
+\clearpage
+\strut\thispagestyle{plain}
+\begin{tiny}
+\begin{center}
+Cette documentation a été réalisée sous Linux Slackware 7.1 à l'aide de \LaTeX\ et cvs.
+\end{center}
+\end{tiny}
+\end{document}
diff --git a/doc/algorithmes.tex b/doc/algorithmes.tex
new file mode 100644
index 0000000..d4c43c5
--- /dev/null
+++ b/doc/algorithmes.tex
@@ -0,0 +1,57 @@
+\chapter{Algorithmes}
+\section{Tas Binomial}
+\paragraph{}
+L'implémentation de certaines parties des algorithmes sur les tas binomiaux ont nécessité quelques changements, notemment
+en ce qui concerne la gestion des cellules. En effet, il se pose un grave problème lors de l'implémentation de "DIMINUER-CLÉ",
+car nous effectuons des changements dans les cellules. Et si l'appelant a gardé des pointeurs sur les cellules elles-mêmes, alors
+leur contenu ne correspondra plus à la valeur d'insertion. Il faudrait pouvoir modifier aussi les pointeurs sur les cellules
+qui ont été renvoyés à l'appelant, ce qui est impossible, vu que ces variables ne font pas partie de l'espace de données de notre
+structure.
+\paragraph{}
+Pour résoudre ce problème, nous avons une table de pointeurs "tampon" qui vont stoquer les vrais pointeurs sur
+les cellules du tas binomial. Comme ces pointeurs sont conservés dans la structure
+de données, nous pouvons les modifier à loisir, lors d'une opération diminuer clef. Ainsi les pointeurs renvoyés à l'appelant
+ne sont pas les pointeurs sur le tas directement, mais des pointeurs sur cette structure tampon, qui joue le role d'intermédiaire.
+\paragraph{}
+Cette structure est une liste doublement chaînée non triée (afin de pouvoir libérer la mémoire correctement
+à la fin du programme), et vu que les deux seules opérations que nous effectuons dessus sont "INSERER" et "SUPPRIMER", nous ne
+faisons que des opérations en $O(1)$ ce qui n'aura aucune influence sur le déroulement des algorithmes eux-mêmes.
+\paragraph{}
+L'implémentation de l'algorithme "FUSIONNER-TAS-BINOMIAUX" a été réalisé différemment de l'idée du cormen. En effet, le livre
+suggérait de créer un troisième tas, et d'y placer les éléments de T1 et de T2 pour effacer T1 et T2 ensuite. Nous nous contentons
+d'effectuer une fusion "sur place". C'est à dire nous vidons le tas T2 et nous insérons ses éléments à la bonne place dans le tas
+T1. Ceci a pour but d'éviter la copie des cellules, pour la même raison que ci-dessus. Autant limiter les opérations et nous
+contenter d'utiliser les blocs mémoires déjà alloués.
+\paragraph{}
+L'implémentation de l'algorithme "UNION" ne diffère que très légèrement de l'algorithme proposé, et nous obtenons un algorithme
+légèrement plus simple. En effet, dans l'algorithme proposé, nous avons un cas particulier dans le cas où nos pointeurs se
+trouvent en début de liste. Nous résolvons le problème directement car notre structure de données est récursive et le tas est
+aussi une cellule de tas binomial. Ainsi, physiquement, nous ne commençons pas à la première, mais à la deuxième cellule du tas.
+Le problème du cas particulier est donc réglé.
+\section{Tas de Fibonacci}
+\paragraph{}
+Le tas de Fibonacci, quique d'allure complexe, n'a pas posé de problèmes d'implémentations particuliers. La seule particularité
+fut d'implémenter certaines des phrases "en français dans le texte" telles que "parcourir la liste des pointeurs de base". Nous avons
+aussi inversé en général l'ordre des choses lors de l'implémentation, ceci afin d'eviter de complexifier le code C++. En effet,
+deux opérations consécutives peuvent influencer l'une sur l'autre, et mener à des situations de programmation délicates. Les
+inverser peut présenter un aventage d'un point de vue conception, et n'influencer en rien le déroulement de l'algorithme. Le code
+source des tas de Fibonacci est commenté de manière à pouvoir suivre les changements effectués lors de l'implémentation.
+\paragraph{}
+La seule restriction que nous avons posé fut sur l'algorithme "CONSOLIDER" pour lequel le tableau A possède une taille fixe.
+En effet, nous ne pouvons évaluer à l'avance le nombre de case dont nous aurons besoin, sachant que certaines branches du
+tas peuvent être dégénérées.
+\section{Liste chaînée triée}
+\paragraph{}
+Cette implémentation n'a posé aucun problèmes particuliers, la structure étant extrèmement simple. La seule particularité qu'il
+peut être amusant de souligner, est que l'algorithme "UNION" est en fait la partie "FUSION" de l'algorithme de tri fusion.
+\section{Tas Binaire}
+\paragraph{}
+Comme pour le tas binomial, les cellules pouvant être échangées, nous ne pouvons renvoyer directement de pointeur sur le
+tableau lui-même. De ce fait, nous avons utilisé exactement la même structure "tampon" que pour le tas binomial.
+\paragraph{}
+Le tableau dans lequel nous stoquons les valeurs n'est en aucun cas limité en revanche. Nous avons inclus un mécanisme qui
+va redimentionner le tableau automatiquement en fonction des indices demandés, ce qui nous permet d'effectuer des tests
+comme si la structure avait une dimension infinie.
+\paragraph{}
+Le reste de l'implémentation n'a posé aucun problème. Il est à noter en revanche qu'il a fallu inverser les conditions par rapport
+à ce qui est décrit dans le livre. En effet, le tas binaire du livre nous donne une structure permettant d'effectuer "EXTRAIRE-MAX".
diff --git a/doc/bib.tex b/doc/bib.tex
new file mode 100644
index 0000000..1203fbb
--- /dev/null
+++ b/doc/bib.tex
@@ -0,0 +1,7 @@
+\begin{thebibliography}{WWW99}
+% pour citer le Tanenbaum : \cite{Tanenbaum}
+% pour citer le Tanenbaum page 238 : \cite[page 238]{Tanenbaum} 
+
+\bibitem[COR]{Cormen} T. Cormen, C. Leiserson, R. Rivest \textit{Introduction à l'algorithmique}, Dunod.
+
+\end{thebibliography}
diff --git a/doc/conclusion.tex b/doc/conclusion.tex
new file mode 100644
index 0000000..e5d9edf
--- /dev/null
+++ b/doc/conclusion.tex
@@ -0,0 +1,9 @@
+\chapter*{Conclusion}
+\addcontentsline{toc}{chapter}{Conclusion}
+\markboth{CONCLUSION}{CONCLUSION}
+
+Ce projet a été mené à terme, et l'ensemble des conditions du sujet ont été respectées.
+L'effort de recherche mené sur la manière d'implémenter les algorithmes en C++ a
+sans aucun doute été profitable pour notre connaissance personnelle. De plus, les algorithmes
+implémentés sont "durables": ils peuvent nous resservir dans n'importe quel autre projet nécessitant
+des structures de files de priorités, ce qui porte un intérêt quant au développement de ce projet.
diff --git a/doc/description.tex b/doc/description.tex
new file mode 100644
index 0000000..e86c698
--- /dev/null
+++ b/doc/description.tex
@@ -0,0 +1,19 @@
+\chapter{Description}
+\paragraph{}
+Nous allons décrire dans cette première partie tous ce que nous avons effectué comme travail de réflexion afin de
+programme ce projet. Il y a beaucoup de détails relatifs à l'implémentation dont nous ne parlerons pas, comme les structures
+sur les listes chaînées, ou l'initialisation du terminal pour gérer le menu du programme de test. En revanche, nous appuyerons
+sur les détails d'implémentation purement algorithmiques qui nous ont posé problème.
+\paragraph{}
+En ce qui concerne le langage de programmation, nous avons choisi le C++, car c'est le langage qui nous semblait le plus
+adapté pour créer les structures de données nécessaire à la programmation de ce projet.
+\paragraph{}
+Nous avons implémenté les algorithmes de files de priorités suivants:
+\begin{itemize}
+\item Tas Binaire
+\item Tas Binomial
+\item Tas de Fibonacci
+\item Liste chaînée triée
+\end{itemize}
+\paragraph{}
+L'algorithme utilisant les files de priorité implémenté est l'algorithme de compression de dictionnaire Huffman.
diff --git a/doc/intro.tex b/doc/intro.tex
new file mode 100644
index 0000000..46d0e3c
--- /dev/null
+++ b/doc/intro.tex
@@ -0,0 +1,11 @@
+\chapter*{Introduction}
+\addcontentsline{toc}{chapter}{Introduction}
+\markboth{INTRODUCTION}{INTRODUCTION}
+
+\paragraph{}
+Ce projet a pour but d'une part l'implémentation d'algorithmes de files de priorités et l'implémentation d'un algorithme
+utilisant ces files de priorités d'autre part.
+
+\paragraph{}
+Ce présent document va tenter de décrire en totalité la progression de la
+mise en forme de ce projet. Nous vous souhaitons bonne lecture. 
diff --git a/doc/manuel.tex b/doc/manuel.tex
new file mode 100644
index 0000000..fcdc3af
--- /dev/null
+++ b/doc/manuel.tex
@@ -0,0 +1,124 @@
+\chapter{Manuel d'utilisation}
+\paragraph{}
+Ce projet génère deux binaire. Le premier appelé testTas n'est qu'une petite application nous permettant d'utiliser l'API
+C++ générée par notre classe de file de priorités. Voici un exemple d'exécution:
+\begin{verbatim}
+Priority list type: 0 - Binary Heap
+Choice: Please select an action
+a - Add a key into the priority list
+c - Change priority list type
+d - Delete a Key from the priority list
+e - Extract Min onto the priority list
+l - Lower Key onto a key of the priority list
+p - Print the current priority list on the screen
+r - Remove the whole priority list
+t - Test the priority list algorithms
+q - Quit
+\end{verbatim}
+
+A partir de cet instant, le programme nous propose un menu nous permettant d'effectuer plusieurs actions sur le tas. La
+fonction 'a' permet d'ajouter une clef dans le tas en cours. Comme il est impossible d'effectuer une recherche sur un tas
+pour y retrouver le pointeur d'un élément, le programme nous propose de sauvegarder le pointeur résultat dans un tableau:
+
+\begin{verbatim}
+Choice: Please select a slot to save the cell
+0 - Empty slot
+1 - Empty slot
+2 - Empty slot
+3 - Empty slot
+4 - Empty slot
+5 - Empty slot
+6 - Empty slot
+7 - Empty slot
+8 - Empty slot
+9 - Empty slot
+n - Don't store
+c - Cancel
+\end{verbatim}
+
+Ce tableau apparaitra régulièrement dans toutes les fonctions du menu afin de choisir une cellule sur laquelle agir. Toutes
+les fonctions du menu parlent d'elles mêmes. La fonction 't' va lancer une batterie de tests sur les algorithmes de la
+file de priorité sélectionnée.
+
+\paragraph{}
+Le deuxième binaire généré est 'Huffman'. Il sert à utiliser l'algorithme d'huffman implémenté. Voici sa ligne d'aide:
+\begin{verbatim}
+$ ./Huffman -h
+Huffman [{-f|-i} file] {type}
+Huffman -h
+This will encode the input file with the Huffman code
+using the priority list defined by type.
+Type is a number taken from this list:
+  0 : Binary Heap (default)
+  1 : Binomial Heap
+  2 : Fibonacci Heap
+  3 : Sorted chained list
+-f file means that you specify a dictionnary file which is
+        structured as described into the README file.
+-i file means that you specify a file to encode. It will
+        built a quiet dumb dictionnary.
+By default, a dictionnary will be built from stdin.
+-h prints this help and exit.
+\end{verbatim}
+
+La structure d'un dictionnaire est la suivante:
+\begin{verbatim}
+Mot1 : Fréquence1
+Mot2 : Fréquence2
+...
+\end{verbatim}
+
+Chaque mot est une chaîne de caractères servant à identifier la fréquence associée. Voici un exemple complet de dictionnaire
+et d'utilisation du programme avec ce dictionnaire:
+
+\begin{verbatim}
+Pixel@the-babel-tower:~/Projets_LI/Semestre1/Projet-Algo/src$ cat dict.sample
+MOT1 : 2000
+MOT2 : 1234
+MOT3 : 15987
+MOT4 : 1203
+MOT5 : 192837
+MOT6 : 12987
+Pixel@the-babel-tower:~/Projets_LI/Semestre1/Projet-Algo/src$ ./Huffman -f dict.sample   
+MOT3 (15987) = 00
+MOT1 (2000) = 0100
+MOT4 (1203) = 01010
+MOT2 (1234) = 01011
+MOT6 (12987) = 011
+MOT5 (192837) = 1
+Bitstream length           : 283957 bits (= 35495 bytes)
+Real size input            : 7239936 bits (= 904992 bytes)
+Size squeezed by           : 96.0779 percents
+Dictionnary size           : 336 bits (= 42 bytes)
+Total bitstream length     : 284293 bits (= 35537 bytes)
+Real gain (4 bytes header) : 96.0728 percents
+\end{verbatim}
+
+Il est indiqué que le programme est capable de générer un dictionnaire à partir d'un fichier. Il s'agit simplement de compter
+les caractères provenant de l'entrée et d'en générer un dictionnaire. Exemple:
+
+\begin{verbatim}
+$ cat dict.sample | Huffman 
+\32 (12) = 00
+6 (1) = 01000
+4 (2) = 01001
+3 (4) = 0101
+0 (4) = 0110
+5 (2) = 01110
+7 (3) = 01111
+1 (6) = 1000
+M (6) = 1001
+: (6) = 1010
+\10 (6) = 1011
+O (6) = 1100
+8 (3) = 11010
+9 (3) = 11011
+2 (6) = 1110
+T (6) = 1111
+Bitstream length           : 294 bits (= 37 bytes)
+Real size input            : 608 bits (= 76 bytes)
+Size squeezed by           : 51.6447 percents
+Dictionnary size           : 512 bits (= 64 bytes)
+Total bitstream length     : 806 bits (= 101 bytes)
+Real gain (4 bytes header) : -38.1579 percents
+\end{verbatim}
diff --git a/doc/outils.tex b/doc/outils.tex
new file mode 100644
index 0000000..69bbc53
--- /dev/null
+++ b/doc/outils.tex
@@ -0,0 +1,21 @@
+\chapter{Outils utilisés}
+\paragraph{}
+Pour développer ce projet, nous avons choisi d'utiliser une série d'outils GNU pour nous simplifier la tâche.
+Nous utilisons entre-autres, GNU autoconf \& automake pour gérer notre arborescence de développement. Ainsi le
+présent projet est découpé en ces répertoires:
+\begin{itemize}
+\item src contenant les sources des programmes exécutables. C'est notemment dans ce répertoire que seront stoqués
+les binaires des exécutables produit par la compilation du projet.
+\item lib contenant tous les sources purement algorithmiques, dont ne dépend pas l'implémentation finale.
+\item include contenant tous les fichiers .h
+\item doc contenant le source \LaTeX\ de cette présente documentation
+\item po contenant les fichiers d'internationalisation (traduction française)
+\item intl contenant le code source nécessaire au support de l'internationalisation.
+\end{itemize}
+En dehors de autoconf \& automake, nous avons utilisé un serveur CVS (Concurrent Version System) qui nous a permis
+de travailler à plusieurs sur ce projet, sans avoir à nous soucier de rapatrier et de fusionner les codes sources
+de tout le monde.
+\paragraph{}
+Enfin, pour pouvoir compiler ce projet, il suffit de taper la commande './configure' au shell et de suivre les instructions.
+Les binaires seront placés dans le répertoire src. Pour générer cette documentation, il suffit d'aller dans le répertoire doc
+et de taper 'make ps'.
diff --git a/doc/structures.tex b/doc/structures.tex
new file mode 100644
index 0000000..c6c7013
--- /dev/null
+++ b/doc/structures.tex
@@ -0,0 +1,64 @@
+\chapter{Structures de données}
+\section{Files de priorités}
+Pour l'implémentation des files de priorités, nous avons remarqué que, comme pour des arbres ou des listes
+chaînées, la structure est (dans le cas des tas Binomiaux et des tas de Fibonacci) récursive. Nous avons donc
+choisi comme structure de données de base C++ une classe récursive. Qu'importe si les informations de récursivités
+ne sont pas utilisés dans les autres dérivés de file de priorité. La classe implémentée est la suivante:
+
+\begin{lstlisting}{}
+class PriorityList {
+      protected:
+        class GeneralException;
+        int type;
+        Key_t Key;
+        Datas_t Datas;
+          PriorityList(Key_t IKey, Datas_t const &IDatas);
+
+      public:
+          PriorityList(void);
+          virtual ~ PriorityList(void);
+
+        virtual Key_t ReadKey(Cell C);
+        virtual Datas_t ReadDatas(Cell C);
+        virtual int n(void);
+        virtual int rn(void) = 0;
+
+        virtual void Dump(ostream & os) = 0;
+        virtual bool IsEmpty(void) = 0;
+
+        virtual Cell Min(void) = 0;
+        virtual Cell Insert(Key_t IKey, Datas_t const &IDatas) = 0;
+        virtual Key_t Extract_Min(Datas_t & Datas) = 0;
+        virtual PriorityList *Union(PriorityList * P) = 0;
+        virtual bool Lower_Key(Cell x, Key_t NKey) = 0;
+        virtual Key_t Delete(Datas_t & Datas, Cell x) = 0;
+        PriorityList *GenericUnion(PriorityList * P);
+        int GetType(void);
+};
+\end{lstlisting}
+
+Les types Key\_t, Datas\_t et Cell sont définis dans un include, et n'influencent en rien le comportement des algorithmes.
+Il suffit que Key\_t soit un type "comparable" (nous avons mis int), et que Datas\_t et Cell soient capables de véhiculer
+des informations. Pour ces deux derniers types, nous avons mis void *. A partir de cette classe de base, nous allons
+dériver toutes les classes suivantes pour permettre l'implémentation des files de priorités.
+
+\section{Huffman}
+Pour l'implémentation de l'algorithme de Huffman, nous avons eu besoin d'écrire une petite structure d'arbre toute simple:
+
+\begin{lstlisting}{}
+class HTree {
+      private:
+        HTree * left, *right;
+        int freq;
+        char *objet;
+      public:
+          HTree(int n_freq, char *n_objet);
+          HTree(HTree * n_left, HTree * n_right);
+         ~HTree();
+          ostream & Trace(ostream & os, int d = 0);
+        int ReadFreq(void);
+        char *ReadObj(void);
+};
+\end{lstlisting}
+
+Notez au passage que la sturcture de données possède une fonction "trace" qui nous sert à générer visuellement le résultat de la compression.
diff --git a/doc/temps.tex b/doc/temps.tex
new file mode 100644
index 0000000..8763553
--- /dev/null
+++ b/doc/temps.tex
@@ -0,0 +1,26 @@
+\chapter{Analyse de temps}
+\paragraph{}
+L'analyse de temps n'est pas très difficile. En effet les différents temps sont déjà calculés pour ce qui est des
+tas Binomiaux, des tas de Fibonacci et des tas binaires. Nous présenterons aussi les temps pour les files de priorités.
+Voici donc les différents temps nécessaires pour les opérations de bases pour tous les algorithmes:
+\paragraph{}
+\begin{center}
+\begin{tabular}{lcccc}
+Procédure & Tas binaire & Tas binomial & Tas de Fibonacci & Liste chaînée triée\\
+\hline\\
+\textsc{Créer-Tas} & $\Theta(1)$ & $\Theta(1)$ & $\Theta(1)$ & $\Theta(1)$\\
+\textsc{Insérer} & $\Theta(\lg n)$ & $O(\lg n)$ & $\Theta(1)$ & $O(n)$\\
+\textsc{Minimum} & $\Theta(1)$ & $O(\lg n)$ & $\Theta(1)$ & $\Theta(1)$\\
+\textsc{Extraire-Min} & $\Theta(\lg n)$ & $\Theta(\lg n)$ & $O(\lg n)$ & $\Theta(1)$\\
+\textsc{Union} & $\Theta(n)$ & $O(\lg n)$ & $\Theta(1)$ & $O(n)$\\
+\textsc{Diminuer-Clé} & $\Theta(\lg n)$ & $\Theta(\lg n)$ & $\Theta(1)$ & $O(n)$\\
+\textsc{Supprimer} & $\Theta(\lg n)$ & $\Theta(\lg n)$ & $O(\lg n)$ & $\Theta(1)$\\
+\end{tabular}
+\end{center}
+\paragraph{}
+Les temps de la liste chaînée triée sont simples à analyser et à expliquer. La liste étant triée et doublement chaînée,
+les opérations MINIMUM, EXTRAIRE-MIN, et SUPPRIMER sont directes, donc en $\Theta(1)$. Ensuite, l'insertion doit trouver
+le bon emplacement, donc parcourir au pire toute la liste chaînée afin d'effectuer l'insertion. C'est pourquoi l'opération
+UNION est en $O(n)$. De même, l'opération DIMINUER-CLE va effectuer l'opération inverser, et déplacer l'élément vers la
+gauche jusqu'à trouver sa nouvelle place, donc au pire va parcourir toute la liste. Ce qui nous fait des opérations en $O(n)$.
+Enfin, l'opération UNION est l'implémentation de l'algorithme FUSIONNER du tri fusion. Nous avons donc un temps en $O(n)$ aussi.