Taller 1 Algoritmos
Taller 1
Miller Alexander Correa GPunto 1
-
- Show that for any real constants a and b, where b>0
Solution :
Siendo y Entonces para todo .Se tiene que y por lo tanto
Ahora sea y
Entonces
Si
Si
Si
Por lo tanto
By Theorem 3.1 - Prove that ∩ is the empty set. Podemos definir formalmente y 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 ∩ como:
y =
Esta desigualdad no se cumple para ninguna función por lo tanto la intersección de 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)) .
- Show that for any real constants a and b, where b>0
Solution:
| Index | Equation | |
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 | ||
| 7 | ||
| 8 | ||
| 9 | ||
| 10 | ||
| 11 | ||
| 12 | ||
| 13 | ||
| 14 | ||
| 15 | ||
| 16 | KaTeX parse error: Expected '}', got '\srqt' at position 4: 2^{\̲s̲r̲q̲t̲(2lg(n))} | |
| 17 | ||
| 18 | ||
| 19 | ||
| 20 | ||
| 21 | ||
| 22 | ||
| 23 | ||
| 24 |
- 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
Teniendo en cuenta que es asintóticamente positiva. Para par tenemos:
Para impar tenemos
KaTeX parse error: Expected 'EOF', got '}' at position 95: …rac{f(2n+1)}{1}}̲
Draw the recursion tree for , 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
Se puede validar también a través del método de sustitución.
Es igual para
- Usar el método maestro para dar cotas ajustadas para las siguientes recurrencias:
En estos problemas se puede ver que respectivamente. Se compara con . Las recurrencias es cada una de un caso diferente del teorema maestro
Por lo tanto:
-
- ,la función tiene una cota con
Por lo tanto
- ,la función tiene una cota con
-
- ,la función tiene una cota
Por lo tanto
- ,la función tiene una cota
-
- ,la función tiene una cota con
por lo tanto
- ,la función tiene una cota con
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).
Dibuje el árbol de recursión y calcule:
i. La altura del mismo
ii. El número de nodos por cada nivel
iii. La suma de los nodos de cada nivel
iv. . La suma total
- Determine el comportamiento asintótico de justificándolo de manera detallada
- Por el método maestro podemos estudiar el comportamiento asintótico de la función de recurrencia :
Donde es de la forma con
por lo tanto
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
