Pouet (doc)

1 files changed, 57 insertions, 0 deletions

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".