Práctica 2 - Ejercicio 2.8 - Algoritmos y Estructura de Datos III

2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

Práctica 2 - Ejercicio 2.8Algoritmos y Estructura de Datos III

Facultad de Ciencias Exactas y Naturales,Universidad de Buenos Aires

27 de Marzo de 2013

Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires

Práctica 2 - Ejercicio 2.8

2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

2.8 - Euclides

2.8. a.Escribir el algoritmo de Euclides para calcular el máximocomún divisor entre 2 números b y c en forma recursiva y norecursiva. Mostrar que su complejidad es O(min{b,c}). ¿Puedeconstruir un ejemplo (un peor caso) donde esta complejidadefectivamente se alcance? ¿Puede hacerlo para b y c tangrandes como se desee?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

Euclides - RepasoRegla de euclides

Si b,c enteros positivos y b ≥ c luegomcd(b, c) = mcd(c,b mod c).

PruebaBasta mostrar que mcd(b, c) = mcd(c,b − c).

I Si g|b y g|c ⇒ g|b − c: mcd(b, c) ≤ mcd(c,b − c).I b = g · k1, c = g · k2,b − c = g · k1 − g · k2 = g · (k1 − k2)

I ≤ : Busco el mayor g posible. Sirve para (b, c)⇒ sirvepara (c,b − c), pero talvez haya g′ > g que divida(c,b − c).

I Si g|b − c y g|c ⇒ g|b : mcd(b, c) ≥ mcd(b − c, c).



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN









2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN




I Si g|b y g|c ⇒ g|b − c: mcd(b, c) ≤ mcd(c,b − c).

I b = g · k1, c = g · k2,b − c = g · k1 − g · k2 = g · (k1 − k2)





2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN









2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN









2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN









2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

2.8. a. Algoritmo recursivo

Algorithm 1: Euclides-RecursivoData: b, cResult: mcd(b, c)if c = 0 then

return belse

return Euclides-Recursivo(c,b mod c)



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

2.8. a. Algoritmo no recursivo

Algorithm 2: Euclides-IterativoData: b, cResult: mcd(b, c)while c 6= 0 do

t := cc := b mod tb := t

return b



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

2.8. a. ComplejidadI Mostrar que la complejidad temporal está acotada por:

O(min{b, c}).

I Qué número es menor luego de la primer iteración?I (b, c)⇒ (c,b mod c)I Comparar c vs b mod c:

c c

b

b < c b > c

cc c b mod cb mod c

b

I si b = c ?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN


O(min{b, c}).I Qué número es menor luego de la primer iteración?

I (b, c)⇒ (c,b mod c)I Comparar c vs b mod c:

c c

b

b < c b > c

cc c b mod cb mod c

b

I si b = c ?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN


O(min{b, c}).I Qué número es menor luego de la primer iteración?I (b, c)⇒ (c,b mod c)

I Comparar c vs b mod c:

c c

b

b < c b > c

cc c b mod cb mod c

b

I si b = c ?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN


O(min{b, c}).I Qué número es menor luego de la primer iteración?I (b, c)⇒ (c,b mod c)I Comparar c vs b mod c:

c c

b

b < c b > c

cc c b mod cb mod c

b

I si b = c ?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN



c c

b

b < c b > c

cc c b mod cb mod c

b

I si b = c ?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN



c c

b

b < c b > c

cc c b mod cb mod c

b

I si b = c ?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

2.8. a. Complejidad

I Luego de la primer iteración: c := b mod c ≤ min{b, c}

I En cada iteración c disminuye en al menos una unidadI El algoritmo termina cuando c = 0I Luego de k + 1 iteraciones, el algoritmo termina, donde

k = min{b, c}I Ejemplo de un peor caso? Familia de peores casos?

Ideas?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

2.8. a. Complejidad

I Luego de la primer iteración: c := b mod c ≤ min{b, c}I En cada iteración c disminuye en al menos una unidad

I El algoritmo termina cuando c = 0I Luego de k + 1 iteraciones, el algoritmo termina, donde


Ideas?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

2.8. a. Complejidad

I Luego de la primer iteración: c := b mod c ≤ min{b, c}I En cada iteración c disminuye en al menos una unidadI El algoritmo termina cuando c = 0

I Luego de k + 1 iteraciones, el algoritmo termina, dondek = min{b, c}

I Ejemplo de un peor caso? Familia de peores casos?Ideas?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

2.8. a. Complejidad

I Luego de la primer iteración: c := b mod c ≤ min{b, c}I En cada iteración c disminuye en al menos una unidadI El algoritmo termina cuando c = 0I Luego de k + 1 iteraciones, el algoritmo termina, donde

k = min{b, c}

I Ejemplo de un peor caso? Familia de peores casos?Ideas?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

2.8. a. Complejidad

I Luego de la primer iteración: c := b mod c ≤ min{b, c}I En cada iteración c disminuye en al menos una unidadI El algoritmo termina cuando c = 0I Luego de k + 1 iteraciones, el algoritmo termina, donde


Ideas?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

2.8. b.Analizar el siguiente algoritmo para determinar el máximocomún divisor entre dos números b y c, y mostrar que sucomplejidad también es O(min {b,c}).

1. Poner g = min { b,c }2. mientras g > 13. si b/g y c/g son enteros, informar mcd = g y parar.4. poner g = g - 15. informar mcd = 1 y parar



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

2.8.b - Euclides

I Es correcto?

I Busca ordenadamente el primer g que cumpla lapropiedad de ser mcd.

I La iteracion recorre: g = min {b,c} .. 1I Dudas?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

2.8.b - Euclides

I Es correcto?I Busca ordenadamente el primer g que cumpla la

propiedad de ser mcd.

I La iteracion recorre: g = min {b,c} .. 1I Dudas?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

2.8.b - Euclides


propiedad de ser mcd.I La iteracion recorre: g = min {b,c} .. 1

I Dudas?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

2.8.b - Euclides


propiedad de ser mcd.I La iteracion recorre: g = min {b,c} .. 1I Dudas?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

2.8. c.Las complejidades calculadas para los algoritmos de las partesa. y b. son iguales. ¿Cuál de los dos algoritmos elegiría?Justificar y comentar.



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

2.8.c - Elección de algoritmoI Cual prefieren? Por qué?

I Factores a tomar en cuenta para decidir qué algoritmoutilizar:

1. Teoría: Correctitud, Complejidad temporal, complejidadespacial, etc.

2. Practica: Resultados experimentales, dificultad de laimplementación, propenso a errores, etc.

I Cuando usamos O() para la complejidad temporal damosuna garantía de peor caso, pero es una cota superior. Esacota no es necesariamente ajustada.

I En la vida real, lo ideal es mezclar resultados teoricos ypracticos para sacar conclusiones.

I En este caso, es importante notar la diferencia entre lascotas superiores encontradas para medir la complejidadtemporal, una es ajustada y la otra no.



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

2.8.c - Elección de algoritmoI Cual prefieren? Por qué?I Factores a tomar en cuenta para decidir qué algoritmo

utilizar:

1. Teoría: Correctitud, Complejidad temporal, complejidadespacial, etc.







2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN


utilizar:1. Teoría: Correctitud, Complejidad temporal, complejidad

espacial, etc.







2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN



espacial, etc.2. Practica: Resultados experimentales, dificultad de la

implementación, propenso a errores, etc.






2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN




implementación, propenso a errores, etc.I Cuando usamos O() para la complejidad temporal damos

una garantía de peor caso, pero es una cota superior. Esacota no es necesariamente ajustada.





2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN










2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN










2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

2.8. d.Probar que se puede mejorar la complejidad calculada en a.demostrando que el algoritmo de Euclides es en realidadO(log2(min{b, c})).



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

2.8.d - Mejorando la complejidad temporal

I Qué tan rápido decrecen (b, c)?

I En una iteración: (b, c)⇒ (c,b mod c)I Hacer ejemplos y pensar hasta que se nos ocurra algo...



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN


I Qué tan rápido decrecen (b, c)?I En una iteración: (b, c)⇒ (c,b mod c)

I Hacer ejemplos y pensar hasta que se nos ocurra algo...



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN


I Qué tan rápido decrecen (b, c)?I En una iteración: (b, c)⇒ (c,b mod c)I Hacer ejemplos y pensar hasta que se nos ocurra algo...



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN


I Qué tan rápido decrecen (b, c)?I En una iteración: (b, c)⇒ (c,b mod c)I Hacer ejemplos y pensar hasta que se nos ocurra algo...



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN


LemaSi b ≥ c ⇒ b mod c < b

2 .



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN



2 ,

Caso 1: c ≤ b/2

c

b

c ≤ b/2

cc c b mod c

b mod c < c ≤ b/2

b/2

b/2



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN



2

Caso 2: c > b/2

c

b

c > b/2 b mod c = b - c < b/2

b/2

bb/2c b mod c



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN


I Cada dos iteraciones, b y c disminuyen a la mitad (o más).

I Luego de la primer iteración: b1 ≥ c1 y b1 ≤ min{b0, c0}I Concluyo que una cota superior de la complejidad

temporal es O(log2(min{b, c})I Se puede mejorar?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN


I Cada dos iteraciones, b y c disminuyen a la mitad (o más).I Luego de la primer iteración: b1 ≥ c1 y b1 ≤ min{b0, c0}

I Concluyo que una cota superior de la complejidadtemporal es O(log2(min{b, c})

I Se puede mejorar?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN


I Cada dos iteraciones, b y c disminuyen a la mitad (o más).I Luego de la primer iteración: b1 ≥ c1 y b1 ≤ min{b0, c0}I Concluyo que una cota superior de la complejidad

temporal es O(log2(min{b, c})

I Se puede mejorar?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN


I Cada dos iteraciones, b y c disminuyen a la mitad (o más).I Luego de la primer iteración: b1 ≥ c1 y b1 ≤ min{b0, c0}I Concluyo que una cota superior de la complejidad

temporal es O(log2(min{b, c})I Se puede mejorar?



2.8. a. 2.8. b. 2.8. c. 2.8. d. FIN

Fin

DUDAS



Documents

Práctica 2 - Ejercicio 2.8 - Algoritmos y Estructura de Datos III