maj rapport
authorjerome <jerome@fac>
Thu, 5 Dec 2013 17:01:25 +0000 (18:01 +0100)
committerjerome <jerome@fac>
Thu, 5 Dec 2013 17:01:25 +0000 (18:01 +0100)
rapport.tex

index 651b7de..678daf7 100755 (executable)
@@ -66,7 +66,7 @@
 \definecolor{key}{rgb}{0.6,0,0.6}
 \definecolor{bck}{rgb}{0.92,0.92,0.92}
 \definecolor{comment}{rgb}{0.5,0.5,0.5}
-\definecolor{string}{rgb}{0,0.5,0}
+\definecolor{string}{rgb}{0.5,0,0}
 \definecolor{number}{rgb}{0,0.5,0.5}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
@@ -87,7 +87,8 @@ morekeywords={},
 commentstyle=\color{comment},
 keywordstyle=\color{string},
 breaklines=true,
-morekeywords={procédure, début, fin, entiers, variables, pour,faire, tant que, si, alors, sinon, de, à, <--}
+literate={<--}{{$\leftarrow$}}2,
+morekeywords={procedure, debut, fin, entiers, variables, pour,faire, tant, que, si, alors, sinon, de, a, ou, et}
 }
 
 \renewcommand{\FrenchLabelItem}{\space\textbullet}
@@ -102,19 +103,178 @@ morekeywords={procédure, début, fin, entiers, variables, pour,faire, tant que,
 
 
   \maketitle{}
+  \vfill{}
+  \tableofcontents{}
   \thispagestyle{empty}
   \newpage
-  \LARGE{\tableofcontents{}}
-  \normalsize{}
-  \newpage
   \section{Introduction}
+  
+Ce projet a pour but d'implémenter trois algorithmes permettant de trouver les minimums situé entre deux éléments de valeurs consécutives dans une permutation.
+
+Ces trois algorithmes permettent de comparer les efficacités entre un algorithme naïf "chercherMinPremier" et deux algorithmes "chercherMinCURang" et "chercherMinCUCompress" utilisant une structure classe-union, respectivement sans et avec compression de chemins.
+
+Au-delà des difficultés d'implémentation, les études comparatives de ces trois algorithmes permettent de mettre en évidence la supériorité d'efficacité des structures classe-union classique et surtout avec compression des chemins sur un algorithme intuitif, cette supériorité se étant de plus en plus flagrante avec l'augmentation de la taille des données.
+  \section{Commandes}
+
+Dans le dossier "intervallesCommuns" (où se trouve le Makefile) :
+
+Compilation : make
+
+Exécution : make launch
+
+  \newpage
+  \section{Algorithmes utilisés}
+procédure chercherMinPremier(Permutation p)
+       \begin{lstlisting}
+variables :
+       entiers : i, j, t, idMin, idMax, idVMin, idVMax
+
+debut
+               
+       pour t de 1 a p.n-1 faire
+               idVMin <-- -1
+               idVMax <-- -1
+               j <-- 0
+               tant que idVMin = 1 ou idVMax = -1 faire
+                       si p.elts[j] = t+1 alors
+                               idVMax <-- j
+                       fin si
+                       si p.elts[j] = t alors
+                               idVMin <-- j
+                       fin si
+                       j <-- j + 1
+               fin tant que
+               si idMin < idMax alors
+                       idMin <-- idVMin
+                       idMax <-- idVMax
+               sinon
+                       idMin <-- idVMax
+                       idMax <-- idVMin
+               fin si
+               p.mins[t-1] <-- p.elts[idMin]
+               pour i de idMin+1 a idMax faire
+                       si p.elts[i] < p.mins[t-1] alors
+                               p.mins[t-1] <-- p.elts[i]
+                       fin si
+               fin pour
+       fin pour
+       
+fin
+               \end{lstlisting}
+               
+  \newpage
+procédure chercherMinCURang(Permutation p, tableau de paires r)               
+               \begin{lstlisting}
+variables :
+       ClasseUnion : c
+       entiers : h, ph
+               
+debut
+               
+       c <-- nouvelle ClasseUnion(p.n+2)
+       pour h de 0 a p.n faire
+               ph <-- p.elts[h]
+               pour chaque classe dans c (si c non vide) telle que identifiant id de la classe > ph faire
+                       union(ph, id)
+               fin pour
+               ajouter h a la classe qui a pour identifiant ph
+               pour chaque paire dans R faire
+                       si h = paire.r2 alors
+                               mins[min(p.elts[paire.r1],p.elts[paire.r2])] <-- ajouter identifiant de la classe qui contient paire.r1
+                       fin si
+               fin pour
+       fin pour
+
+fin            
+               \end{lstlisting}
+
+La procedure chercherMinCUCompress est strictement la même que chercherMinCURang, en remplaçant la
+
+ligne 7 par "c $\leftarrow$ nouvelle ClasseUnionCompress(p.n+2)"
+
+  \newpage
+  \section{Explication du fonctionnement des algorithmes}
+
+-chercherMinPremier(Permutation p) :
+
+L'algorithme commence par une boucle "pour" qui va de la valeur 1 à la valeur n-1 via une variable t, et dans laquelle on s'intéresse aux valeurs t et t+1. Cette boucle englobe tout l'algorithme, ce qui assure qu'on va regarder toutes les paires possibles.
+
+A chaque tour de cette boucle pour, on (ré)initialise les variables idVMin et idVMax à -1, ce qui assure qu'on va rentrer dans la boucle "tant que idVMin = -1 ou idVMax = -1 faire" qui vient juste après. La variable j est, elle, initialisée à 0 de la même manière à chaque tour du pour, et incrémentée à chaque tour du tant que qui suit :
+
+Dans cette première boucle tant que, on regarde les valeurs stockées dans le tableau elts contenant les éléments de la permutation aux indices j et j+1. Les deux "si" permettent de stocker les indices des cases du tableau elts auxquelles se trouve les valeurs recherchées (t et t+1). Dès que ces deux valeurs ont été trouvées (et stockées dans idVMin et idVMax), on sort du tant que.
+
+Une fois ces deux valeurs trouvées, idMin prend idVMin et idMax prend idVMax, ou on les intervertit si besoin (cas où t+1 est placé avant t dans la permutation). Puis on stocke elts[idVMin] dans le tableau des minimums, à l'indice t-1 (puisque t est au mimimum 1 et mins commence à 0), c'est-à-dire qu'on initialise le minimum recherché à la valeur de t.
+
+Ensuite, on rentre dans un deuxième "pour" avec i de idMin+1 à idMax. A chaque tour, si elts[i] est strictement plus petit que mins[t-1], on remplace mins[t-1] par elts[i], ce qui permet bien de garder au final le plus petit élément situé entre t et t+1. On sort de la boucle pour.
+La boucle principale se termine ici, , on a stocké dans mins tous les minimums situés entre les valeurs t et t+1 dans la permutation.
+
+
+-chercherMinCURang(Permutation p, tableau de paires R) :
+
+On commence par instancier une ClasseUnion c de taille n+2.
+
+On rentre alors dans une boucle "pour" englobant tout l'algorithme, qui via une variable h fait toutes les valeurs de 0 à n-1.
+
+A chaque tour de cette boucle, un entier ph prend pour valeur l'entier en position h du tableau elts des éléments de la permutation.
+
+On rentre alors dans un "pour" interne au premier, qui regarde dans chaque classe de c et, si c n'est pas vide, fait l'union de la classe contenant ph et de la classe courante, seulement si l'identifiant de cette dernière est supérieur ou égal à celui de la classse contenant ph. Fin du "pour".
+
+On ajoute alors la valeur h à la classe d'identifiant ph (si cette classe n'existe pas, elle est créée).
+
+Vient une autre boucle "pour" (toujours dans la première boucle) qui regarde chaque paire de R, et si h est égal au r2 de la paire courante, ajoute en à de mins à l'indice le plus petit des deux éléments de la paire courante. Fin du pour.
+
+Fin de la boucle pour principale.
+
+  \newpage
+  \section{Complexités de tous les algorithmes/programmes écrits}
+  
+-chercherMinPremier :
+-Meilleur des cas : O("boucle principale":(n-2) * ("tantque 1":((3+3+5)*2+2+1) + "si":3 + "pour":(idMax - idMin - 1) * "si":4) = O((n-2) * (25 + (idMax-idMin-1) * 4)) = O(n)
+       
+-Pire des cas : O("boucle principale":(n-2) * ("tantque 1":3+(8+1)*(n-2)+18) + "si":3 + "pour":(idMax - idMin - 1) * "si":6) = O((n-2) * (24 + 9*(n-2) + (idMax-idMin-1) * 6)) = O(n²)
+       
+-Moyenne : O(n*log(n))
+
+
+-chercherMinCURang :
+
+-Meilleur des cas : O("boucle principale":(n+1) * ("pour":(log(n) * "union":cst) + "pour":log(n) + 1 + "pour":log(n))) = O((n+1)*3*log(n))
+       
+-Pire des cas : 
+       
+-Moyenne : 
+
+  \newpage
+  \section{Etude comparative}
+
+N.B. : Les algorithmes avec structure classe-union ont été optimisés depuis la séance de TP, ce qui les rend bien plus efficaces que sur les graphiques suivants (environ un tiers gagné pour chercherMinCURang et deux pour chercherMinCUCompress)
+
+  \begin{figure}[h]
+    \centering
+    \includegraphics[width=15cm]{./perm-croissant.png}
+    \caption{\label{fig:perm-croi} Permutations ordonnées par ordre croissant}
+  \end{figure}
+
+  \begin{figure}[h]
+    \centering
+    \includegraphics[width=15cm]{./perm-decroissant.png}
+    \caption{\label{fig:perm decroi} Permutations ordonnées par ordre décroissant}
+  \end{figure}
+
+ \vfill{}
 
+On voit ici que l'algorithme chercherMinPremier est bien plus efficace que les algorithmes implementant
 
+les structures classe-union lorsque les permutations sont triées
+  
+  \begin{figure}[h]
+    \centering
+    \includegraphics[width=15cm]{./perm-random.png}
+    \caption{\label{fig:file} Permutations aléatoires (donc non ordonnées)}
+  \end{figure}
 
-%  \begin{figure}[h]
-%    \centering
-%    \includegraphics[width=15cm]{./file.png}
-%    \caption{\label{fig:file} Desc File}
-%  \end{figure}
+Avec des permutations aléatoires, l'algorithme chercherMin est le moins efficace.
 
 \end{document}