Taller 1 Algoritmos

Taller 1 Algoritmos

   junio 06, 2018       Macorreag

---

Taller 1

Miller Alexander Correa G

Punto 1

1. • Show that for any real constants a and b, where b>0
     $(n + a)^b = \Theta (n^b)$
     Solution :
     Siendo $c = 2^b$ y $n_0 \geq 2a$ Entonces para todo $n \geq n_0$ .Se tiene que $(n +a)^b \leq (2n)^b = cn^b$ y por lo tanto $(n+a)^b = \mathcal{O}(n^b)$
     Ahora sea $n_{0} \geq \frac{-a}{ 1- (1/2)^{1/b} }$ y $c= 1/2$
     Entonces $n \geq n_0 \geq \frac{-a}{1-(1/2)^{1/b}}$
     Si $n - \frac{n}{2^{1/b}} \geq -a$
     Si $n + a \geq ( \frac{1}{2} )^{a/b} n$
     Si $(n + a)^b \geq cn^b$
     Por lo tanto $(n + a)^b = \Omega(n^b)$
     By Theorem 3.1 $(n + a)^b = \mathcal{O}(n^b)$
   • Prove that $o(g(n))$ ∩ $ω(g(n))$ is the empty set. Podemos definir formalmente $o(g(n))$ y $ω(g(n))$ de la siguiente manera:
     Solution
     Por definición o(g(n)) = {f(n) : ∀c, n tal que 0≤f(n) ≤ cg(n), ∀n } 0 > n0 2.
     Por definición ω(g(n)) = {f(n) : ∀c, n tal que 0≤cg(n) ≤ f(n), ∀n }
     Podemos entonces definir $o(g(n))$ ∩ $\omega (g(n))$ como:
     $o(g(n))$ y $\omega (g(n))$ = ${f(n): ∀_c,n_0 \geq cg(n) \geq f(n) \geq cg(n) ∀_n > n_0}$
     Esta desigualdad no se cumple para ninguna función $f (n)$ por lo tanto la intersección de $o(g(n)) y ω(g(n))$ debe ser el conjunto vacío.
   • Rank the following functions by order of growth; that is,and an arrangement g1, g2, …. , g30 of the functions satisfying g1 = Ω(g2), g2 = Ω(g3), … , g29 = Ω(g30) .Partition your list into equivalence classes such that functions f(n) and g(n) are in the same class if and only if f(n) = Θ(g(n)) .
     

Solution:

Index	Equation
1	$2^{2^{n+1}}$
2	$2^{2^{n}}$
3	$(n+1)!$
4	$n!$
5	$n2^n$
6	$e^{n}$
7	$2^n$
8	$(\frac{3}{2})^n$
9	$(lg(n))!$
10	$n^{lg(lg(n))}$	$lg(n)^{lg(n)}$
11	$n^3$
12	$n^2$	$4^{lg(n)}$
13	$(lg(n))$	$lg(n!)$
14	$2^{lg{n}}$	$n$
15	$\sqrt(2)^{lg(n)}$
16	KaTeX parse error: Expected '}', got '\srqt' at position 4: 2^{\̲s̲r̲q̲t̲(2lg(n))}
17	$lg^{2}(n)$
18	$ln(n)$
19	$\sqrt(lg(n))$
20	$ln(ln(n))$
21	$2^{lg(n)}$
22	$lg(n)$	$lg(lg(n))$
23	$lg(lg(n))$
24	$1$	$n^{1/lg(n)}$

• ​Give an example of a single nonnegative function f(n) such that for all functions gi (n) in part (a), f(n) is neither O(gi (n)) nor Ω(gi (n)) .
  Solution
  Si definimos la función
  $f(n)\left\{\begin{matrix} g_1(n)! & n & mod 2=0 \\ \frac{1}{n}& n & mod 2 = 1 \end{matrix}\right.$
  Teniendo en cuenta que $f(n)$ es asintóticamente positiva. Para $n$ par tenemos:
  $\lim_{n \to \infty} \frac{f(2n)}{g_i({2n)}}\geq \lim_{n \to \infty} \frac{f(2n)}{g_i({2n)}}$
  $\lim_{n \to \infty} (g_1(2n)-1)!$
  $= \infty$
  Para $n$ impar tenemos
  KaTeX parse error: Expected 'EOF', got '}' at position 95: …rac{f(2n+1)}{1}}̲
  $\lim_{n \to \infty} \frac{1}{2n +1}$
  $= 0$

​Draw the recursion tree for $T(n) = 4T([n/2]) + cn$, where c is a constant, and provide a tight asymptotic bound on its solution. Verify your bound by the substitution method.

Solution

Se incrementa el número de subproblemas por cada recursión en 4. Se disminuye el tamaño del subproblema en 2 más 2 adicionales. De esa manera, en cada nivel del árbol hay 4i nodos cada uno de coste c(n/2+2) a una profundidad i, que sigue la secuencia i = 0,1,2,…,lgn.
Costo total tree
$t(n)=\displaystyle \sum_{i=0}^{lgn} 4^i c\left( \frac{n}{2^i} + 2 \right)$
$=\displaystyle \sum_{i=0}^{lg(n)} 4^i c \frac{n}{4^i}+ \sum_{i=0}^{lg(n)} 4^i c2$
$=cn\sum_{i=0}^{lg(n)} \frac{4^i}{2^i} + 2c\sum_{i=0}^{lg(n)}4^i$
$=cn\sum_{i=0}^{lg(n)} 2^i + 2c\sum_{i=0}^{lg(n)}4^i$
$=cn\frac{2^{lgn+1-1}}{2-1} +2c\frac{4^{lg(n)+1}-1}{4-1}$
$=cn(2^{lg(n)+1}-1)+2c\frac{2c}{3}(4^{lgn+1}-1)$
$=cn(2n-1)+\frac{2c}{3}(4n^2-1)$
$=2cn^2-2n+\frac{8cn^2}{3}-\frac{2c}{3}$
$= \mathcal{O}(n^2)$
Se puede validar también a través del método de sustitución.
$T(n)=4T(n/2+2)+n$
$\leq 4d(n/2+2)^2-b(n/2+2)+n$
$=4d(n^2/4+2n+4-bn/2-2b)+n$
$=dn^2+8dn+16d-2dbn-8db+n$
$dn^2-dbn+8dn+16n-dbn-8db+n$
$d(n^2-bn)-(db-8d-1)n-(b-2)8d$
$\leq d(n^2-bn)$
Es igual para $db-1-8d\geq0$

• Usar el método maestro para dar cotas ajustadas para las siguientes recurrencias:
  • $T(n) = 8T(\frac{n}{2})+n$
  • $T(n)=8T(\frac{n}{2})+n^3$
  • $T(n)=8T(\frac{n}{2})+n^5$
    En estos problemas se puede ver que $a=8,b=2 y f(n)=n,n^2,n^3$ respectivamente. Se compara $f(n)$ con $n$ . Las recurrencias es cada una de un caso diferente del $log ab = n log 82$ teorema maestro

Por lo tanto:

• $T(n) = 8T(\frac{n}{2}) + n$
  • $n^{log_28}=n^3 = \theta(n^3)$,la función $f(n)$ tiene una cota $\theta(n^{log_b(a)-e})$ con $e=2$
    Por lo tanto $T(n)= O(n^3)$
• $T(n) = 8T(\frac{n}{2}) + n^3$
  • $n^{log_28}=n^3=\theta(n^3)$,la función $f(n)$ tiene una cota $\theta(n^{log_ba})$
    Por lo tanto $T(n)= O(n^3log(n))$
• $T(n) = 8T(\frac{n}{2}) + n^5$
  • $n^{log_28}=n^3=\theta(n^3)$,la función $f(n)$ tiene una cota $\theta(n^{log_b(a)+e})$ con $e=2$
    por lo tanto $T(n) = \theta(n^5)$

Punto 2

def misterio(n):
 if n <= 1:
  return 1 
 else:
  r = misterio(n / 2)
  i = 1
  while n > i*i:
   i = i + 1 
  r = r + misterio(n / 2) 
  return r

Plantee una ecuación de recurrencia para T (n), el tiempo que toma la función misterio(n).
$T(n)=2T(n/2)+Θ(n^{1/2} )$
Dibuje el árbol de recursión y calcule:
i. La altura del mismo $log_2(n)$
ii. El número de nodos por cada nivel $2^{log_2(n)}$
iii. La suma de los nodos de cada nivel $2^ik(\frac{n}{2^i}^{\frac{1}{2}})$
iv. . La suma total $Θ(n)$

• Determine el comportamiento asintótico de $T (n)$ justificándolo de manera detallada
• Por el método maestro podemos estudiar el comportamiento asintótico de la función de recurrencia $T(n)$:
  Donde es de la forma $O(n)$ con $\epsilon O(n) = 0.5$
  por lo tanto $T(n)= \theta (n)$

Punto 3

22.3-1 ​(pág 610) Realizar un cuadro 3x3 con filas y columnas WHITE, GRAY, BLACK. En cada celda (𝑖,𝑗), indique si en algún momento durante la búsqueda en la profundidad de un grafo dirigido, puede haber una arista o un vértice de color i a un vértice de color j. Por cada arista posible indique que tipo puede ser. Haga otro cuadro pero utilizando un grado no dirigido

**Solution **
Grafo dirigido

	White	Gray	Black
white	Alkinds	Back,Cross	Tree, Forward y Croos
Gray	Back,Cross	Tree, Forward y Croos	Tree, Forward y Croos
Black	Back,Cross	Back,Cross	Alkinds

Grafo NO Dirigido

	White	Gray	Black
white	Alkinds	-	-
Gray	Alkinds	Tree, Forward y Back	-
Black	Alkinds	Alkinds	Alkinds

Punto 4

22.3-2​ (Pág 611) Muestre como DFS funciona en el grafo de la figura 22.6. Asuma que el ciclo for de la línea 5-7 del DFS considera los vértices en orden alfabético, y asuma que cada lista de adyacencia está ordenada alfabéticamente. Muestre el descubrimiento y los tiempos de cada vértice y muestre la clasificación de cada arista.
- Forward edges: (q,w).
- Back edges: (z,x), (w,s), (y,q).
- Tree edges: (q,s),(s,v),(v,w),(q,t),(t,x),(x,z),(t,y),(r,u).
- Cross edges: (u,y),(r,y)

Punto 5

22.4-2​ Dé un algoritmo de tiempo lineal que tome como input un grado dirigido acíclico 𝐺 = (𝑉, 𝐸) y dos vértices s y t, y retorna el número de caminos simples de s a t en G. Añada un campo a la representación de vértices para mantener un número entero. Inicialmente, establece la cuenta del vértice t en 1 y la de otros vértices en 0. Comienza ejecutando DFS con s como vértice de inicio. Cuando se descubre t, debe marcarse inmediatamente como terminado (NEGRO), sin ningún otro tratamiento a partir de él. Posteriormente, cada vez que DFS finaliza un vértice v, establece el conteo de v como la suma de los conteos de todos los vértices adyacentes a v. Cuando DFS finalice el vértice s, deténgase y devuelva el conteo calculado para s.

def SIMPLE-PATHS(u,v):
 if u == v:
     return 1
elif  u.paths == None:
 return u.paths
else
 for w in adj[u]:
  paths.append(SIMPLE-PATHS(w,v))
 return u.paths

Read More

   marzo 14, 2018       Macorreag

---

https://raygun.com/blog/10-costly-software-errors-history/ Pruebas de correctitud

Read More

Desarrollo de la Ingeniería en Colombia

Desarrollo de la Ingeniería en Colombia

   marzo 13, 2018       Macorreag

---

Linea de Tiempo desarrrollo contesto político y social

Aqui dejare una síntesis de los apuntes tomados en Desarrollo de la ingeniería en Colombia. Linea de tiempo usando TimeLine.Js Se nos olvido como somos . No sabemos qué queremos ser. Tenemos los mejores jugadores pero no sabemos que queremos hacer El futuro es consecuencia de lo que fuimos. “Los ricos se creen ingleses, la clase media se cree gringa y los pobres se creen mexicanos. En el país no hay colombianos”. Jaime Garzón En el los pueblos y fuera de la ciudad esta lo que realmente somos ,(Hay que conocernos ) Como se identifica Definirnos como mestizos es una alternativa válida para definir lo que realmente somos pero no es la única.Dado que más que lazos genéticos que compartimos con los europeos, nativos y africanos hemos heredado modos de costumbre y de vida, esto debido en gran parte a la globalización. La adopción de definirse como mestizo conllevaría el desarrollo de una identidad propia que incentivaría el desarrollo en distintos campos basado en los recursos y necesidades propias del país. Este desarrollo no implicaría necesariamente el aislamiento frente a las demás culturas y sus nuevas tecnologías, sino por el contrario afirmaríamos que somos ciudadanos del mundo .Como tal estamos dispuestos a intercambiar conocimientos y a su vez resolver nuestras necesidades de la mejor manera, consolidando así lo que realmente somos.

Read More

Proyecto Agorithm Sort

Proyecto Agorithm Sort

   marzo 05, 2018       Macorreag

---

Read More