Taller1 Algoritmos

P RESENTADO POR : S ERGIO D ANIEL T ORRES

C ÓDIGO : 261591

D ANIEL F ELIPE S ABOGAL

C ÓDIGO : 258272

U NIVERSIDAD N ACIONAL DE C OLOMBIA

P RESENTADO A : I NG . J UAN M ENDIVELSO

Taller de Algoritmos
EJERCICIO 1
Muestre que las siguientes afirmaciones son falsas o verdaderas justificando su respuesta:
1.

2

3

3 n −5 n=O(n )
2

3

3

3 n −5 n≤cn =O( n )
5
3 − ≤cn
n
Para n grande laafirmación es verdadera
2.

5

(n≥ 3c )

3

5 n =Ω(n )

Según las definiciones de notación asintótica:
5

3

3

5 n ≥cn =Ω(n )
2
5 n ≥c
c
n≥
5

√

Lo cual es válido para n grande y c>0; por tanto la afirmación es verdadera.
3.

2

3

n lg n=o (n )

Aplicando la definición:
2

3

3

n log n log n< cn

Como esto es cierto para todos los valores de c>0 significa que la afirmación es verdadera
4.3

n !=ω(n )

Para probar la afirmación se aplica la definición:
3

3

n !>cn =ω(n )
3
n !> cn

Esta inecuación no se cumple para todos los valores; así que, según la definición, la afirmación sería falsa.
5.

4

5

n − 1=Θ(n )

Se debe probar que se cumple la siguiente desigualdad:
5

4

5

0≤c 1 n ≤n −1≤c2 n
4
0≤n (c 1 n−1)≤−1≤n ( c2 n−1 )
4

Llegados a este punto solo basta con observar ladesigualdad de la izquierda para comprobar que la afirmación
el falsa.

EJERCICIO 2
Use el método maestro para dar cotas ajustadas para las siguientes recurrencias:
1.

T ( n)=4T( n/2)+ n

Para este caso a=4 y b=2, entonces se tiene:
n

log 2 4

=n
2−ϵ

f (n)=n=O( n

2

)

ϵ>0

Entonces se puede aplicar el caso 1, en el cual se tiene la siguiente solución:
2

T ( n)=Θ(n )

2.

2

T ( n)=4T( n/2)+ nAl igual que en el punto anterior en este caso a=4 y b=2, entonces:
n

log 2 4

=n

2

2

2

f (n)=n =Θ( n )

Se puede aplicar el caso 2, entonces la solución sería:
T ( n)=Θ(n

3.

log b a

2

log n)=Θ(n logn )

3

T ( n)=4T( n/2)+n

Para este caso a=4 y b=2, entonces se tiene:
n

log 2 4

=n

2

f (n)=n 3=Ω(n 2+ϵ)

ϵ>0

Para poder aplicar el caso 3 también se tiene que cumplir la siguientecondición:
3

a f ( n/ b )=4f (n /2 )=4 (n / 2) ≤cn
3
3
4 n ≤8c n
1
≤c
2

3

c< 1

Entonces se puede aplicar el caso 3, en el cual se obtiene la cota dada por

3

T ( n)=Θ(f (n ))=Θ(n )

4.

T ( n)=2T(n /4 )+√ n

Para este caso a=2 y b=4, entonces se tiene:
n

log 4 2

=n

1/ 2

f (n)=n3=Ω(n 2+ϵ)

ϵ>0

Es decir, se puede aplicar el caso 2 cuya solución sería:
T ( n)=Θ(n

log b a

log n)=Θ( √ n logn )EJERCICIO 3
Realice los siguientes ejercicios:
1.

Use el árbol de recursión para determinar una buena cota asintótica superior para la recurrencia
T ( n)=3T([n/2 ])+n . Use el método de la substitución para verificar su respuesta.

El planteamiento del árbol de recursión sería como el que se indica a continuación:

El costo en el ultimo nivel será

n

log(3)

, la sumatoria de los costos terminasimplificándose como:
(1+log 3−log 2)

3cn

T ( n)=O (n

Usando el método de sustitución, suponemos

– 2cn=O (n

log(3)

)

log (3)

)=0 (n 1.58)

T ( n)≤cn

log 3

con

c>0 :

T ( n)=3T([ n/2 ])+n
log

T ( n)≤3[ c1 (n / 2) 3 – c2 (n / 2)]+n
log3
=c1 n – ((3 /2 )c 2 n)+ n
=c1 nlog 3 – c 2 n con c 2≥2

En el caso base:
1≤c1−2

2.

1=T (1)≤c1 (1

que se cumple si

log 3

) – c2

c1 ≥3

El profesorCaesar desea desarrollar un algoritmo de multiplicación de matrices que sea asintóticamente
más rápido que el algoritmo de Strassen. Su algoritmo usará el método divide y vencerás, dividiendo cada
matriz en subproblemas de tamaño n/4 x n/4, y los pasos dividir y combinar requerirán juntos un tiempo
Θ(n) . Él necesita determinar cuantos subproblemas tiene que crear su algoritmo con el fin devencer el

algoritmo de Strassen. Si su algoritmo crea a subproblemas, entonces la recurrencia para el tiempo de
ejecución T ( n) sería

2

T ( n)=aT (n /4 )+Θ(n ) ¿Cuál es el valor entero más grande de a para el que el

algoritmo del profesor Caesar podría ser asintóticamente más rápido que el algoritmo de Strassen?

Si tenemos en cuenta que la recurrencia del algoritmo de Strassen es:
2

T (...

Leer documento completo

Regístrate para leer el documento completo.