SHARE
TWEET

Untitled

a guest Aug 12th, 2017 44 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. \documentclass{article}
  2. \usepackage[utf8]{inputenc}
  3. \begin{document}
  4. \par
  5. Ejercicio 6 del Capitulo 1
  6. \par Sea $\{S_i\}_{i= 1..n}$ la lista de barcos, y $\{P_i\}_{i= 1..n}$ la lista de puertos. Sea $A$ un array n*m, donde $A(i,j)$ dice el lugar donde se encuentra el barco $i$ el dia $j$.
  7. Construiremos $\sigma : \{1 \cdots n\}\rightarrow \{1 \cdots m\}$ que dice el dia en que se trunca cada barco, y probaremos la correctitud del algoritmo, es decir, las condicion: $\forall i,j \in\{1 \cdots n\}$  $(\forall d > \sigma(i))$ $ \sigma(j) \geq d \Rightarrow A(j,d)\neq A(i,\sigma(i)).$
  8. \\[12pt]
  9. \par
  10. \par d = m
  11. \par listS = $\{1 \cdots n\}$
  12. \par listP = $\{1 \cdots m\}$
  13. \par Mientras  notEmpty(list) hacer\{
  14. \par    Encontrar $P_{i_1} \cdots P{i_l}$ en listP de los puertos que terminan su trabajo en el dia d, para los barcos en listS\footnote{Es decir, son los puertos que no reciben mas barcos de $listS$ luego del dia $d$}. . Asignar $\sigma(S_{j_1})$ = d $c\dots \sigma(s_{j_l})$ = d, donde $A(j_k,d) = i_k$.
  15. \par Eliminar $P_{i_1} \cdots P_{i_l}$ de listP.
  16. \par Eliminar $S_{j_1} \cdots S_{j_l}$ de listS.
  17. \par d = d+1
  18. \par \}
  19. \\[12pt]
  20. \par Correctitud:
  21. \par Veamos ahora que se cumple la condicion de correctitud anteriormente propuesta:   Supongamos por absurdo $\exists i,j \in\{1 \cdots n\}$  $(\exists d_0 > \sigma(i)) A(j,d_0)=A(i,\sigma(i))$ y $\sigma(j) \geq d_0$. $\sigma(j) = d_0$ es imposible pues seria $A(j,d_0) = A(i,d_0)$, lo cual es absurdo por hipotesis. Entonces, se debe tener $\sigma(j) > d_0$. Pero en el paso del algoritmo en que $d = d_0$ $j$ aun no ha truncado y por lo tanto $j\in listS$. El algoritmo calcula que la labor de $A(i\sigma(i))$ no ha terminado, pues $j$ pasara por alli el dia $d_0$. Pero esto se contradice con el algoritmo.
  22. Ahora falta ver que
  23. \end{document}
RAW Paste Data
Pastebin PRO Summer Special!
Get 40% OFF on Pastebin PRO accounts!
Top