De la lecture
authorjerome <jerome@fac>
Thu, 5 Dec 2013 17:56:44 +0000 (18:56 +0100)
committerjerome <jerome@fac>
Thu, 5 Dec 2013 17:56:44 +0000 (18:56 +0100)
rapport.tex

index 678daf7..7a2f338 100755 (executable)
@@ -103,17 +103,34 @@ morekeywords={procedure, debut, fin, entiers, variables, pour,faire, tant, que,
 
 
   \maketitle{}
-  \vfill{}
+  \paragraph{}
+
+~\\
+\vskip3mm
+\hskip7mm
+~\\
+\vskip3mm
+\hskip7mm
+~\\
+\vskip3mm
+\hskip7mm
+
   \tableofcontents{}
   \thispagestyle{empty}
   \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.
+
+\paragraph{}
+~\\
+\vskip3mm
+\hskip7mm
+
   \section{Commandes}
 
 Dans le dossier "intervallesCommuns" (où se trouve le Makefile) :
@@ -196,7 +213,7 @@ ligne 7 par "c $\leftarrow$ nouvelle ClasseUnionCompress(p.n+2)"
   \section{Explication du fonctionnement des algorithmes}
 
 -chercherMinPremier(Permutation p) :
-
+\paragraph{}
 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 :
@@ -209,42 +226,68 @@ Ensuite, on rentre dans un deuxième "pour" avec i de idMin+1 à idMax. A chaque
  
 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.
 
+\paragraph{}
+~\\
+\vskip2mm
+\hskip4mm
 
 -chercherMinCURang(Permutation p, tableau de paires R) :
-
+\paragraph{}
 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.
+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, c'est à dire qu'il va faire un élément de la permutation à chaque tour (dans l'ordre dans lequel ils sont rangés)
+
+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 si l'identifiant de cette dernière est supérieur ou égal à celui de la classe contenant ph. Fin du "pour". (On réunit donc dans une même classe tous les éléments compris entre les éléments entre lesquels on veut trouver le minimum)
 
-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 ensuite la valeur h à la classe d'identifiant ph (si cette classe n'existe pas, elle est créée).
 
-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 l'identifiant de la classe contenant r1 à mins (à la position correspondant à l'indice le plus petit des deux éléments de la paire courante). Fin du pour. On a ici trouvé le minimum de l'intervalle considéré dans la permutation (l'identifiant de la classe)
 
-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. Les conditions sont remplies.
 
-Fin de la boucle pour principale.
+\paragraph{}
+~\\
+\vskip2mm
+\hskip4mm
+
+-chercherMinCUCompress :
+
+L'algorithme fait strictement la même chose que chercherMinCUCompress mais avec la classe-union avec compression des chemins. Se référer donc à l'explication de chercherMinCURang
 
   \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)
+\paragraph{}
+-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²)
+-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^2)$
        
--Moyenne : O(n*log(n))
+-Moyenne : $O(n*log(n))$
 
+\paragraph{}
+~\\
+\vskip3mm
+\hskip7mm
 
 -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))
+\paragraph{}
+-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)) = O(n*log(n))$
        
--Pire des cas : 
+-Pire des cas : $O("boucle principale":(n+1) * ("pour":(n * "union":cst) + "pour":n + 1 + "pour":n) = O(n)$
        
--Moyenne : 
+-Moyenne : O(n*log(n))
+
+\paragraph{}
+~\\
+\vskip3mm
+\hskip7mm
+
+-chercherMinCUCompress :
+\paragraph{}
+Même ordre de grandeur de complexité que pour chercherMinCURang, mais cependant plus efficace grâce à la compression des chemins
 
   \newpage
   \section{Etude comparative}
@@ -265,7 +308,7 @@ N.B. : Les algorithmes avec structure classe-union ont été optimisés depuis l
 
  \vfill{}
 
-On voit ici que l'algorithme chercherMinPremier est bien plus efficace que les algorithmes implementant
+On voit ici que l'algorithme chercherMinPremier est bien plus efficace que les algorithmes implémentant
 
 les structures classe-union lorsque les permutations sont triées