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?

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

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).

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

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).

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

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).

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

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).

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

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).

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

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).

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. 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)

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. 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

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. 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 ?

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. 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 ?

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. 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 ?

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. 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 ?

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. 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 ?

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. 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 ?

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. 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?

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. 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

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

Ideas?

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. 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?

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. 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?

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. 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?

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. 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

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.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?

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.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?

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.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} .. 1

I Dudas?

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.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?

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. 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.

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.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.

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.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. 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.

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.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, complejidad

espacial, 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.

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.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, complejidad

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

implementació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.

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.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, complejidad

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

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.