API tools faq
paste
Advertisement
juaniisuar

Untitled

juaniisuar
Jun 20th, 2018
375
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 21.68 KB | None | 0 0
raw download clone embed print report
  1. \documentclass[12pt]{article}
  2. \usepackage[utf8]{inputenc}
  3. \usepackage[spanish]{babel}
  4. \usepackage[pdftex]{graphicx}
  5. \usepackage{float}
  6. \usepackage{booktabs}
  7. \usepackage[table,xcdraw]{xcolor}
  8. \usepackage{ltxtable}
  9. \usepackage{listings}
  10. \lstset{language=Haskell}
  11. \usepackage{color}
  12. \begin{document}
  13. \begin{titlepage}
  14.  
  15. \begin{minipage}{2.6cm}
  16. \includegraphics[width=\textwidth]{fceia.pdf}
  17. \end{minipage}
  18. \hfill
  19. %
  20. \begin{minipage}{6cm}
  21. \begin{center}
  22. \normalsize{Universidad Nacional de Rosario\\
  23. Facultad de Ciencias Exactas,\\
  24. Ingeniería y Agrimensura\\}
  25. \end{center}
  26. \end{minipage}
  27. \hspace{0.5cm}
  28. \hfill
  29. \begin{minipage}{2.6cm}
  30. \includegraphics[width=\textwidth]{unr.pdf}
  31. \end{minipage}
  32.  
  33. \vspace{0.5cm}
  34.  
  35. \begin{center}
  36. \normalsize{\sc Estructuras de Datos II}\\
  37. \vspace{0.5cm}
  38. \large{Trabajo Práctico II}\\
  39.  
  40. \Large{\bf Secuencias}\\
  41. \vspace{5cm}
  42.  
  43. \normalsize
  44. Román Castellarin\\
  45. Juan Ignacio Suarez\\
  46.  
  47. \vspace*{0.5cm}
  48. \small{ \today }
  49.  
  50.  
  51. \end{center}
  52. \end{titlepage}
  53. \newpage
  54.  
  55. \section{Implementacion basada en Arrays Persistentes}
  56.  
  57. \begin{tabular}{@{}lcc@{}}
  58. \toprule
  59. & W & S \\ \midrule
  60. filterS p x & $O(|x| + \sum\limits_{i=0}^{|x|-1} W[p\ x_i])$ & $(\log |x| + \max\limits_{i=0}^{|x|-1} S[p\ x_i])$ \\
  61. reduceS f e s & $ O(|s| + \sum\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} W[x\oplus y])$ & $ O(\log |s|\cdot \max\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} S[x\oplus y])$ \\
  62. scanS & $O(|s| + \sum\limits_{(x\oplus y)\in\mathcal{O}_s(\oplus,e,s)} W[x\oplus y])$ & $O(\log |s|\cdot \max\limits_{(x\oplus y)\in\mathcal{O}_s(\oplus,e,s)} S[x\oplus y])$ \\
  63. showtS & $O(1)$ & $O(1)$ \\ \bottomrule
  64. \end{tabular}
  65.  
  66. \subsection{filterA es $O(|x| + \sum\limits_{i=0}^{|x|-1} W[p\ x_i])$ en trabajo.\\ y $O(\log |x| + \max\limits_{i=0}^{|x|-1} S[p\ x_i])$ en profundidad.}
  67. \begin{table}[h]
  68. \begin{lstlisting}
  69. filterA p x = A.flatten (mapA g x)
  70. where g y = if p y then singletonA y else emptyA
  71. \end{lstlisting}
  72. \caption{Definicion de filterA}
  73. \end{table}
  74. \begin{table}[h]
  75. \begin{lstlisting}
  76. emptyA = A.fromList []
  77. singletonA x = A.fromList [x]
  78. mapA f x = A.tabulate g (A.length x)
  79. where g n = f (x ! n)
  80. \end{lstlisting}
  81. \caption{Definicion de emptyA, singletonA y mapA}
  82. \end{table}
  83. \begin{itemize}
  84. \item \textbf{Lema:} \texttt{singletonA} y \texttt{emptyA} son $O(1)$ en trabajo y profundidad.
  85.  
  86. \textit{Dem:} Ambas hacen una cantidad constante de operaciones independientemente de la entrada.
  87.  
  88. \item \textbf{Lema:} \texttt{mapA f s} es $O( \sum\limits_{i=0}^{|s|-1} W[f\ s_i] )$ en trabajo y $O( \max\limits_{i=0}^{|s|-1} S[f\ s_i] )$ en profundidad.
  89.  
  90. \textit{Dem:} Se desprende como corolario de las cotas de \texttt{tabulate g n} con $g\ i = f\ s_i$ y $n=|s|$.
  91.  
  92. \end{itemize}
  93.  
  94. Concentremonos en la definicion de \texttt{filterA} presentada arriba:
  95. \begin{itemize}
  96. \item Del primer lema, resulta que $W[g\ y]\in O(W[p\ y])$ y $S[g\ y]\in O(S[p\ y])$.
  97. \item Del segundo lema, resulta que \texttt{map\ g\ x} es $O(\sum\limits_{i=0}^{|x|-1} W[p\ x_i])$ en trabajo y $O(\max\limits_{i=0}^{|x|-1} S[p\ x_i])$ en profundidad.
  98. \item Es necesario calcular primero \texttt{map\ g\ x} para luego aplicar el \texttt{flatten}, por lo que las profundidades y trabajos se suman ya que no se realizan en paralelo.
  99. \item Tenemos entonces por la especificacion dada de \texttt{flatten} que \texttt{filter\ p\ x} es $O(|x| + \sum\limits_{i=0}^{|x|-1} W[p\ x_i])$ en trabajo ya que $|g\ y| \in O(1)$, mientras que en profundidad es $O(\log |x| + \max\limits_{i=0}^{|x|-1} S[p\ x_i])$.
  100. \end{itemize}
  101.  
  102.  
  103. \subsection{reduceA es $O(|s| + \sum\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} W[x\oplus y])$ en trabajo,\\
  104. y $ O(\log |s|\cdot \max\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} S[x\oplus y])$ en profundidad.}
  105.  
  106. Utilizaremos $\mathcal{O}_r(\oplus,e,s)$ para denotar el conjunto de aplicaciones de $\oplus$ al invocar \texttt{reduceA $\oplus$ e s}. Notemos que para reducir una secuencia de largo $n$ por aplicacion repetida de $\oplus$ (en cualquier orden) hacen falta $n-1$ aplicaciones, por lo que cardinalidad de este conjunto es $O(|s|)$.
  107.  
  108. Para el analisis general de costo, supondremos primero que $W[x \oplus y]$ es $O(1)$, y luego deduciremos el caso general.
  109.  
  110. \begin{table}[h!]
  111. \begin{lstlisting}
  112. reduceA f e s = case A.length s of
  113. 0 -> e
  114. _ -> f e (reduceByContraction f s)
  115. where reduceByContraction f s = case A.length s of
  116. 1 -> s ! 0
  117. _ -> reduceByContraction f (contractA f s)
  118. \end{lstlisting}
  119. \caption{Definicion de reduceA}
  120. \end{table}
  121.  
  122. \begin{table}[h!]
  123. \begin{lstlisting}
  124. contractA f s | n == 1 = s
  125. | even n = A.tabulate g (n//2)
  126. | otherwise = A.tabulate g' (n//2 + 1)
  127. where n = A.length s
  128. g i = f (s ! (2*i)) (s ! (2*i + 1))
  129. g' i = if i == (n//2) then s ! (2*i) else g i
  130. \end{lstlisting}
  131. \caption{Definicion de contractA}
  132. \end{table}
  133.  
  134. \begin{itemize}
  135. \item \textbf{Lema:} Para $W_\oplus,S_\oplus \in O(1)$, \texttt{contractA $\oplus$ s} es $O(|s|)$ en trabajo y $O(1)$ en profundidad:
  136.  
  137. \textit{Dem:} Corolario de las cotas de \texttt{tabulate g n} con $g\ i = s_{2i}\oplus s_{2i+1}$ y $n\in O(|s|)$.
  138. \end{itemize}
  139. \begin{itemize}
  140. \item Veamos que como \texttt{contract} reduce la longitud de la secuencia en un factor de $1/2$, \texttt{reduceByContraction} solo recursa $O(\log |s|)$ veces, y por lo tanto (usando el lema anterior) resulta $O(\log |s|)$ en profundidad.\\
  141. En simbolos: $S(n) = S(n/2) + O(1) \Rightarrow S \in O(\log n)$
  142.  
  143. \item Para el trabajo, (usando el lema anterior) veamos que obtenemos una serie geometrica, por lo que resulta $O(|s|)$.\\
  144. En simbolos: $W(n) = W(n/2) + O(n) \Rightarrow S \in O(n)$
  145. \end{itemize}
  146. Para una especificacion de costos general, notemos que solo debemos agregarle al trabajo obtenido, el trabajo de cada operacion ($x\oplus y$) hecho, y la profundidad no puede empeorar mas que en un factor $\max\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} S[x\oplus y]$.
  147.  
  148. Por lo que finalmente obtenemos:
  149. $$O(|s| + \sum\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} W[x\oplus y])$$ en trabajo, y
  150.  
  151. $$ O(\log |s|\cdot \max\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} S[x\oplus y])$$ en profundidad.
  152.  
  153. \subsubsection{scanA es $O(|s| + \sum\limits_{(x\oplus y)\in\mathcal{O}_s(\oplus,e,s)} W[x\oplus y])$ en trabajo,\\
  154. y $ O(\log |s|\cdot \max\limits_{(x\oplus y)\in\mathcal{O}_s(\oplus,e,s)} S[x\oplus y])$ en profundidad.}
  155.  
  156.  
  157.  
  158. \begin{table}[h]
  159. \begin{lstlisting}
  160. scanA f e s = (scan_seq, scan_last)
  161. where (scan_seq, scan_last) = (scanA' f e s) ||| (reduceA f e s)
  162. scanA' f e s = case A.length s of
  163. 0 -> emptyA
  164. 1 -> singletonA e
  165. n -> tabulateA g n
  166. where s' = scanA' f e (contractA f s)
  167. g i | even i = s' ! (i//2)
  168. | otherwise = f (s' ! (i//2)) (s ! (i-1))
  169. \end{lstlisting}
  170. \caption{Definicion de scanA}
  171. \end{table}
  172.  
  173. Analogamente a como hicimos para el analisis de reduceA, supondremos primero que $\oplus$ es $O(1)$ en trabajo y profundidad, y consideraremos el conjunto $\mathcal{O}_s(\oplus,e,s)$ de aplicaciones de $\oplus$ al invocar \texttt{scanS $\oplus$ e s}.
  174.  
  175. \begin{itemize}
  176. \item \textbf{Lema:} Para $W_\oplus,S_\oplus \in O(1)$, \texttt{scanA' $\oplus$ e s} es $O(|s|)$ en trabajo y $O(\log |s|)$ en profundidad.
  177.  
  178. \textit{Dem:} De manera similar al analisis de reduceA, vemos que la recurrencia para el trabajo es $W(n) = W(n/2) + O(n)$, donde el $O(n)$ viene del trabajo de \texttt{tabulateA} y \texttt{contractA}, y el $W(n/2)$ del trabajo de la llamada recursiva (contractA reduce en un factor de 1/2 la secuencia). De donde el trabajo resulta $O(|s|)$. De la misma forma, la recurrencia para la profundidad es $S(n) = S(n/2) + O(1)$ donde el $O(1)$ viene de la profundidad de \texttt{contractA} y \texttt{tabulateA}, ambas $O(1)$. Resulta asi una profundidad de $O(\log |s|)$
  179. \end{itemize}
  180.  
  181. Realicemos ahora un analisis general de costos.
  182.  
  183. \begin{itemize}
  184. \item Veamos que \texttt{scanA} consiste esencialmente de dos llamadas en paralelo, una a \texttt{scanA'} y otra a \texttt{reduceA}.
  185.  
  186. \item Es muy importante notar que por esta razon, $\mathcal{O}_r(\oplus,e,s) \subseteq \mathcal{O}_s(\oplus,e,s)$
  187.  
  188. \item Por lo ya demostrado arriba, el trabajo de \texttt{scanA} queda $O(W[scanA'] + W[reduceA]) =$ $$O(|s| + \sum\limits_{(x\oplus y)\in\mathcal{O}_s(\oplus,e,s)} W[x\oplus y])$$
  189.  
  190. \item Para la profundidad, obtenemos $O(\max (S[scanA'], S[reduceA])) = $ $$O(\log |s|\cdot \max\limits_{(x\oplus y)\in\mathcal{O}_s(\oplus,e,s)} S[x\oplus y])$$
  191. \end{itemize}
  192. \subsubsection{showtA es $O(1)$ en trabajo y profundidad.}
  193.  
  194. \begin{table}[h]
  195. \begin{lstlisting}
  196. showtA x | n == 0 = EMPTY
  197. | n == 1 = ELT (x ! 0)
  198. | otherwise = NODE (takeA x m) (dropA x m)
  199. where n = A.length x
  200. m = n//2
  201. \end{lstlisting}
  202. \caption{Definicion de showtA}
  203. \end{table}
  204.  
  205. \begin{itemize}
  206. \item \textbf{Lema:} \texttt{takeA, dropA} son $O(1)$ en trabajo y profundidad.
  207.  
  208. \textit{Dem:} Corolario de las cotas de \texttt{subArray}.
  209.  
  210. \end{itemize}
  211.  
  212. \texttt{showtA} realiza una cantidad constante de operaciones ya que no recursa e invoca funciones que realizan trabajo y profundidad constante.
  213.  
  214. \section{Implementacion basada en Listas}
  215.  
  216. \begin{tabular}{@{}lcc@{}}
  217. \toprule
  218. & W & S \\
  219. \midrule
  220. filterS & $O(|s| + \sum\limits_{i=0}^{|s|-1} W[f\ s_i])$ & $O(|s| + \max\limits_{i} S[f\ s_i] )$ \\
  221. showtS & $O(|s|)$ & $O(|s|)$ \\
  222. reduceS & $O(|s| + \sum\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} W[x\oplus y])$ & $O(|s| + \max\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} S[x\oplus y])$ \\
  223. scanS & $O(|s| + \sum\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} W[x\oplus y])$ & $O(|s| + \max\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} S[x\oplus y])$ \\
  224. \bottomrule
  225. \end{tabular}
  226.  
  227.  
  228. \subsection{filterL es $O(|s| + \sum\limits_{i=0}^{|s|-1} W[f\ s_i])$ en trabajo, y $O(|s| + \max\limits_{i} S[f\ s_i] )$ prof.}
  229.  
  230. \begin{table}[h]
  231. \begin{lstlisting}
  232. filterL f [] = []
  233. filterL f (x:xs) =
  234. let (x',xs') =
  235. (if f x then [x] else []) ||| (filterL f xs)
  236. in x'++xs'
  237. \end{lstlisting}
  238. \caption{Definicion de filterL}
  239. \end{table}
  240. \begin{itemize}
  241.  
  242. \item \textbf{Trabajo de filterL:}
  243.  
  244. Teniendo como segundo argumento el largo de la secuencia $s$:
  245.  
  246. $$ W_{filterL}(f, 0) = c_0 $$
  247. $$ W_{filterL}(f, n) = 1 + ( 1 + W(if\ f\ s_0\ then\ [x]\ else\ []) + W_{filterL}(f, n-1) ) + W(x'++xs') = $$
  248.  
  249. Como el costo de 'if' es constante (además de construir el resultado), vemos rápidamente que el costo de esta primer expresión es $W(f\ s_0) + k$.
  250. Además, siendo $x'$ la asignación de este resultado, vemos que $x'++xs'$ también será de costo constante pues $x'$ será $[]$ o $[x]$ y la función $++$ depende del tamaño del primer argumento. Siguiendo:
  251.  
  252. $$ = c_1 + W(f\ s_0) + W_{filterL}(f, n-1) = ... = \sum\limits_{i=0}^{n-1} c_i + \sum\limits_{i=0}^{n-1} W[f\ s_i] $$
  253.  
  254. Donde se desprende $\sum\limits_{i=0}^{n-1} c_i$ de orden lineal más la sumatoria de costos de $f$ en los valores de la secuencia. Es decir:
  255.  
  256. $$ W_{filterL} \in O(n + \sum\limits_{i=0}^{n-1} W[f\ s_i] ) = O(|s| + \sum\limits_{i=0}^{|s|-1} W[f\ s_i]) $$
  257.  
  258. \item \textbf{Profundidad de filterL:}
  259.  
  260. Similar a como analizamos el trabajo, tenemos:
  261.  
  262. $$ S_{filterL}(f, 0) = c_0 $$
  263. $$ S_{filterL}(f, n) = 1 + ( 1 + max\{ S(if\ f\ s_0\ then\ [x]\ else\ []), S_{filterL}(f, n-1)\} ) + S(x'++xs') = $$
  264.  
  265. Así como sucedía con el costo también sucede con la profundidad, en el caso del 'if' también tenemos $S(f\ s_0) + k$ y la profundidad de $++$ seguirá siendo constante. Siguiendo:
  266.  
  267. $$ = c_1 + max\{ S(f\ s_0), S_{filterL}(f, n-1) \} = $$
  268. $$ = c_1 + max\{ S(f\ s_0), c_2 + max\{S(f\ s_1), S_{filterL}(f, n-2) \} \} \ (1) $$
  269.  
  270. Sea $S_f$ tal que $S_f = \max\limits_{0<=i<n} S(f\ s_i)$.
  271. Volviendo a $(1)$, reemplazando con $S_f$ nos queda:
  272.  
  273. $$ (1) \leq $$
  274. $$ c_1 + max\{ S_f, c_2 + max\{S_f, S_{filterL}(f, n-2) \} \} \leq $$
  275. $$ c_1 + max\{ S_f, c_2 + max\{S_f, ... max\{ S_f, c_0 \} ... \} \} = $$
  276.  
  277. Considerando el peor caso $c_0 < S_f$, esto resulta en:
  278.  
  279. $$ = \sum\limits_{i=0}^{n-1} c_i + S_f $$
  280.  
  281. Nuevamente se desprende de la primer sumatoria un orden lineal, sumado a $S_f$, el cual por definición era el máximo $S(f\ s_i)$ para algún $i$. Por lo tanto:
  282.  
  283. $$ S_{filterL} \in O(n + \max\limits_{i} S[f\ s_i] ) = O(|s| + \max\limits_{i} S[f\ s_i] ) $$
  284.  
  285. \end{itemize}
  286.  
  287.  
  288. \subsection{showtL es $O(|s|)$ en trabajo, y $O(|s|)$ prof.}
  289.  
  290. \begin{table}[h]
  291. \begin{lstlisting}
  292. showtL [] = EMPTY
  293. showtL [x] = ELT x
  294. showtL s = let mid = div (lengthL s) 2
  295. (l,r) = (takeL s mid) ||| (dropL s mid)
  296. in NODE l r
  297. \end{lstlisting}
  298. \caption{Definicion de showtL}
  299. \end{table}
  300.  
  301. \begin{itemize}
  302.  
  303. \item \textbf{Lema:} \texttt{takeL y dropL} son $O(|s|)$ en trabajo y $O(|s|)$ en profundidad.
  304.  
  305. \textit{Dem:} Se desprende de la definción $takeL\ s\ n = take\ n\ s$, $dropL\ s\ n = drop\ n\ s$, y la documentación oficial de las mismas.
  306.  
  307. \item \textbf{Trabajo y profundidad de showtL:}
  308.  
  309. Notar que EMPTY y ELT son constructores de TreeView, por lo que tienen trabajo y profundidad constante. Resulta instantáneo el análisis del trabajo:
  310.  
  311. $$ W_{showtL}(0) = c_0 $$
  312. $$ W_{showtL}(1) = c_1 $$
  313. $$ W_{showtL}(n) = 1 + W_{takeL}(n/2) + W_{dropL}(n/2) $$
  314. $$ W_{showtL}(n) = c_2 + W_{takeL}(n/2) + W_{dropL}(n/2) $$
  315.  
  316. Donde teníamos $W_{takeL} \in O(|s|)$ y $W_{dropL} \in O(|s|)$, por lo tanto:\\
  317.  
  318. $$ W_{showtL} \in O(|s|) $$
  319.  
  320. \item \textbf{Profundidad de showtL:}
  321.  
  322. De forma análoga al análisis anterior:
  323.  
  324. $$ S_{showtL}(0) = c_0 $$
  325. $$ S_{showtL}(1) = c_1 $$
  326. $$ S_{showtL}(n) = 1 + max\{ S_{takeL}(n/2), W_{dropL}(n/2) \} $$
  327. $$ S_{showtL}(n) = c_2 + max\{ S_{takeL}(n/2), W_{dropL}(n/2) \} $$
  328.  
  329. Donde tenemos $S_{takeL} \in O(|s|)$ y $S_{dropL} \in O(|s|) \Rightarrow max\{ S_{takeL}(n/2), W_{dropL}(n/2) \} \in O(|s|)$ Luego:
  330.  
  331. $$ S_{showtL} \in O(|s|) $$
  332.  
  333. \end{itemize}
  334.  
  335.  
  336. \subsection{reduceL es $O(|s| + \sum\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} W[x\oplus y])$ en trabajo, y $O(\log |s|\cdot \max\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} S[x\oplus y])$ prof.}
  337.  
  338. \begin{table}[h]
  339. \begin{lstlisting}
  340. reduceL f e [] = e
  341. reduceL f e [x] = f e x
  342. reduceL f e s = reduceL f e (contractL f s)
  343.  
  344. contractL f [] = []
  345. contractL f [x] = [x]
  346. contractL f (x:y:xs) = let (x',xs') = f x y ||| contractL f xs
  347. in x':xs'
  348. \end{lstlisting}
  349. \caption{Definicion de reduceL y contractL}
  350. \end{table}
  351.  
  352. \begin{itemize}
  353.  
  354. \item \textbf{Lema:} \texttt{contractL} es $O(|s| + \sum\limits_{i=0}^{|s|/2} W[s_{2i} \oplus s_{2i+1}])$ en trabajo y $O(|s| + \max\limits_{0 \leq i \leq |s|/2} S[s_{2i} \oplus s_{2i+1}])$ en prof.
  355.  
  356. \textit{Dem:}
  357. De la definición de contractL:
  358.  
  359. $$ W_{contractL}(\oplus, 0) = c_0 $$
  360. $$ W_{contractL}(\oplus, 1) = c_1 $$
  361. $$ W_{contractL}(\oplus, n) = 1 + W(s_0 \oplus s_1) + W_{contractL}(\oplus, n-2) \leq \sum\limits_{i=0}^{n/2} W[s_{2i} \oplus s_{2i+1}] + \sum\limits_{i=0}^{n/2} c_i $$
  362.  
  363. Notar que la longitud de la lista es $n/2 = |s|/2$ pues por cada elemento nuevo quitamos 2 elementos en $n-2$ de la secuencia original en la siguiente recursión. De esto obtenemos un término lineal sumado a el trabajo de aplicar la función en cada par de la secuencia, por lo tanto:
  364.  
  365. $$ W_{contractL} \in O(n + \sum\limits_{i=0}^{n/2} W[s_{2i} \oplus s_{2i+1}]) = O(|s| + \sum\limits_{i=0}^{|s|/2} W[s_{2i} \oplus s_{2i+1}]) $$
  366.  
  367. Similarmente con la profundidad:
  368.  
  369. $$ S_{contractL}(\oplus, 0) = c_0 $$
  370. $$ S_{contractL}(\oplus, 1) = c_1 $$
  371. $$ S_{contractL}(\oplus, n) = 1 + max\{ S(s_0 \oplus s_1), S_{contractL}(\oplus, n-2) \} $$
  372.  
  373. Donde en cada recurrencia nos quedamos con el máximo $S(s_i \oplus s_j)$ de esa instancia. Podemos acotar este resultado simplemente considerando el máximo $S(s_i \oplus s_j)$ de cualquier aplicación del conjunto $\mathcal{O}_r(\oplus,e,s)$ como cota. Resulta entonces:
  374.  
  375. $$ S_{contractL} \in O(|s| + \max\limits_{0 \leq i \leq |s|/2} S[s_{2i} \oplus s_{2i+1}]) $$
  376.  
  377. \item \textbf{Trabajo de reduceL:}
  378.  
  379. Comenzando con la definición de reduceL:
  380.  
  381. $$ W_{reduceL}(\oplus, e, 0) = c_0 $$
  382. $$ W_{reduceL}(\oplus, e, 1) = W(\oplus\ e\ s_0) $$
  383. $$ W_{reduceL}(\oplus, e, n) = 1 + W_{contractL}(\oplus, n) + W_{reduceL}(\oplus, e, n/2) = $$
  384. $$ 1 + W_{contractL}(\oplus\ n) = 1 + ( 1 + W_{contractL}(\oplus, n/2) + W_{reduceL}(\oplus, e, n/4) ) = $$
  385. $$ ... = c + W_{reduceL}(\oplus, n/2) + ... + W(\oplus\ e\ s_0)\ o\ c_0\ (dependiendo\ de\ la\ paridad) $$
  386.  
  387. Como vimos en la implementación con arreglos tenemos $n-1$ aplicaciones en total, y como de la ecuación planteada surge la serie geométrica $n/2 + n/4 + ... + 1 = n-1$ de aplicaciones en elementos distintos (utilizamos los nuevos generados anteriormente) tenemos la suma del trabajo en todas las aplicaciones, además del costo lineal de $contractL$ (y la constante). Es decir:
  388.  
  389. $$ W_{reduceL} \in O(|s| + \sum\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} W[x\oplus y]) $$
  390.  
  391. \item \textbf{Profundidad de reduceL:}
  392.  
  393. Similarmente al caso anterior:
  394.  
  395. $$ S_{reduceL}(\oplus, e, 0) = c_0 $$
  396. $$ S_{reduceL}(\oplus, e, 1) = W(\oplus\ e\ s_0) $$
  397. $$ S_{reduceL}(\oplus, e, n) = 1 + max\{ S_{contractL}(\oplus, n), S_{reduceL}(\oplus, e, n/2) \} $$
  398.  
  399. Al expandir la expresión obtenemos un $max$ con $\log n = \log |s|$ parámetros, de donde nos quedamos con el máximo $S(s_i \oplus s_j)$ para cada caso. De nuevo, podemos acotarlo eligiendo siempre la máxima aplicación del conjunto $\mathcal{O}_r(\oplus,e,s)$ y nos queda:
  400.  
  401. $$ S_{reduceL} \in O(\log |s|\cdot \max\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} S[x\oplus y]) $$
  402.  
  403. \end{itemize}
  404.  
  405.  
  406. \subsection{scanL es $O(|s| + \sum\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} W[x\oplus y])$ en trabajo, y $O(\log |s|\cdot \max\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} S[x\oplus y])$ prof.}
  407.  
  408. \begin{table}[h]
  409. \begin{lstlisting}
  410. expandL f _ [] = []
  411. expandL f (x:xs) [y] = [x]
  412. expandL f (x:xs) (y:y':ys) = x:(f x y):expandL f xs ys
  413.  
  414. scanL f e [] = ([], e)
  415. scanL f e [x] = ([e], f e x)
  416. scanL f e s = let (l, res) = scanL f e (contractL f s)
  417. in (expandL f l s, res)
  418. \end{lstlisting}
  419.  
  420. \caption{Definicion de expandL y scanL}
  421. \end{table}
  422.  
  423. \begin{itemize}
  424.  
  425. \item \textbf{Lema:} \texttt{expandL} es $(|s| + \sum\limits_{i=0}^{|s|/2} W[cs_{i} \oplus s_{2i}])$ en trabajo y $O(|s| + \max\limits_{0 \leq i \leq |s|/2} S[cs_{i} \oplus s_{2i}])$ en prof.
  426.  
  427. \textit{Dem:} De la definición de expandL, donde cs es la secuencia parcial y s es la secuencia original, cn y n sus respectivas longitudes :
  428.  
  429. $$ W_{expandL}(\oplus, 0, n) = c_0 $$
  430. $$ W_{expandL}(\oplus, n, 1) = c_1 $$
  431. $$ W_{expandL}(\oplus, cn, n) = 1 + W(cs_0 \oplus s_0) + W_{expandL}(\oplus, cn-1, n-2) = ... $$
  432. $$ ... = c + W(cs_0 \oplus s_0) + W(cs_1 \oplus n_2) + .. + W(cs_{n/2} \oplus s_n) \leq $$
  433.  
  434. Entonces:
  435.  
  436. $$ W_{expandL} \in O(n + \sum\limits_{i=0}^{n/2} W[cs_{i} \oplus s_{2i}]) = O(|s| + \sum\limits_{i=0}^{|s|/2} W[cs_{i} \oplus s_{2i}]) $$
  437.  
  438. Análogamente para la profundidad:
  439.  
  440. $$ S_{expandL}(\oplus, 0, n) = c_0 $$
  441. $$ S_{expandL}(\oplus, n, 1) = c_1 $$
  442. $$ S_{expandL}(\oplus, cn, n) = 1 + max\{ S(cs_0 \oplus s_0), S_{expandL}(\oplus, cn-1, n-2)\} = ... $$
  443.  
  444. De donde resulta:
  445.  
  446. $$ S_{expandL} \in O(|s| + \max\limits_{0 \leq i \leq |s|/2} S[cs_{i} \oplus s_{2i}]) $$
  447.  
  448. \item \textbf{Trabajo de scanL:}
  449. De la definición de scanL:
  450.  
  451. $$ W_{scanL}(\oplus, e, 0) = c_0 $$
  452. $$ W_{scanL}(\oplus, e, 1) = c_1 + W[e \oplus x] $$
  453. $$ W_{scanL}(\oplus, e, n) = c_2 + W_{contractL}(n) + W_{scanL}(\oplus, e, n/2) + W_{expandL}(n/2, n) $$
  454.  
  455. Notar que contractL y expandL de hecho tienen la misma estructura y sólo difieren en aplicaciones distintas, y ambos pueden ser acotados superiormente de una forma similar como en reduce: eligiendo la sumatoria de aplicaciones en $\mathcal{O}_r(\oplus,e,s)$, pues cada aplicación de $\oplus$ en cada ejecucion tanto de contractL como expandL es miembro de este conjunto, es decir
  456.  
  457. $$ W_{contractL}, W_{expandL} \in O(|s| + \sum\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} W[x\oplus y]) $$
  458.  
  459. Esto nos resulta muy útil porque ahora alteramos el orden de los términos en la ecuación anterior y vemos:
  460.  
  461. $$ W_{scanL}(\oplus, e, n) = c_2 + W_{scanL}(\oplus, e, n/2) + ( W_{contractL}(n) + W_{expandL}(n/2, n) ) $$
  462.  
  463. Donde observamos la misma estructura que en reduce, con contractL y expandL igualmente acotados. Con el mismo razonamiento anterior de la serie geométrica nos queda:
  464.  
  465. $$ W_{scanL} \in O(|s| + \sum\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} W[x\oplus y]) $$
  466.  
  467.  
  468. \item \textbf{Profundidad de scanL:}
  469. De la definición de scanL:
  470.  
  471. $$ S_{scanL}(\oplus, e, 0) = c_0 $$
  472. $$ S_{scanL}(\oplus, e, 1) = c_1 + S[e \oplus x] $$
  473. $$ S_{scanL}(\oplus, e, n) = 1 + ( 1 + max\{ S_{scanL}(\oplus, e, n/2), S_{contractL}(\oplus, n/2) \} ) + S_{expandL}(n/2, n) $$
  474.  
  475. Con el mismo argumento anterior podemos ver que también acotamos a contractL y expandL:
  476.  
  477. $$ S_{contractL}, S_{expandL} \in O(|s| + \max\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} S[x\oplus y]) $$
  478.  
  479. Y también tenemos $\log s$ recursiones. Por lo tanto:
  480.  
  481. $$ S_{scanL} \in O(\log |s|\cdot \max\limits_{(x\oplus y)\in\mathcal{O}_r(\oplus,e,s)} S[x\oplus y]) $$
  482.  
  483. \end{itemize}
  484.  
  485.  
  486. \end{document}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!