Mpinning Gyalg13(Recurr)

1

❚ Def. La relación: Q={(f,g) | f:NR, g: NR tal que f está en O(g)} es reflexiva y transitiva, pero no es un orden parcial ni una relación de equivalencia.

❚ Dibuje el digrafo de la relación Q sobre la notación O según la definición anterior para las funciones {f1,f2,f3,f4,f5,f6,f7,f8}, donde:

❙ f1(n) = 1, f2(n) = n, f3(n) = log2(n), f4(n) = nlog2(n), f5(n) = n2, f6(n) = n3, f7(n) = n2log2(n), f8(n) = 2n

2

f1

f2

f3

f4

f5

f6

f7

f8

3

Sistemas de Recurrencia

• ¿Recuerdan a Fibonacci?

• an = an-1 + an-2

• La característica de la recurrencia es la capacidad de especificar un término an como una función de los términos a0, a1, ..., an-1

4

❚ Una recurrencia por sí sola no es suficiente para definir los términos de una secuencia, también resulta necesario especificar los valores de algunos términos iniciales de la secuencia.

❚ Estos se llaman condiciones de borde o condiciones iniciales de la secuencia.

❚ En el caso de Fibonacci, las condiciones de borde son❙ a0 = 0

❙ a1 = 1

5

❚ Definición. Un sistema de recurrencia es un conjunto de condiciones de borde y ecuaciones de recurrencia que especifican una secuencia única o una función (a veces una función parcial) desde Nk R, con k =1,2,...

❚ La solución a un sistema de recurrencia es una función f: Nk R, tal que f satisface tanto las condiciones de borde como las ecuaciones de recurrencia.

6

Ejemplo

❚ Sea f(h,k) el número máximo de hojas en un árbol de altura k, donde cada nodo del árbol tiene outdegree k o menos. La función puede ser expresada a través del siguiente sistema de recurrencia:❙ f(0,k) = 1

❙ f(h,k) = k · f(h-1,k), para h > 0

7

Otro ejemplo

❚ ¿Qué hace el siguiente procedimiento?procedure SUM(n);

begin

total 0;

for i 1 to n step 1 do

total total + A[i];

return total

end

8

❚ Supongamos que se define la complejidad de SUM como el número de sumas hechas por SUM.

❚ Esta complejidad es caracterizada por el siguiente sistema recurrente:❙ f(1) = 1,

❙ f(n) = f(n-1) + 1, para n > 0

❚ De lo anterior, se deduce que❙ f(n) = n para n 1

❚ Por lo tanto, SUM es un algoritmo O(n) y tiene complejidad lineal

9

Ejemplo: Torres de Hanoi

❚ Puzzle inventado por el matemático francés Edouard Lucas, 1883.

A B C

10

❚ El juego original de Lucas tiene 8 discos, posteriormente le agregó una leyenda romántica sobre una torre mucho mayor, la Torre de Brahma, que supuestamente contiene 64 discos de oro puro sobre una de tres varillas de diamante.

❚ Al comienzo de los tiempos, Dios colocó estos discos dorados sobre la primera varilla y ordenó que un grupo de monjes los transfiriera a la tercera de acuerdo a las reglas

11

❚ Los monjes supuestamente debían trabajar noche y día en esa tarea. Cuando finalizaran, la torre se derrumbaría y el mundo llegaría a su fin.

❚ ¿Qué es lo mejor que podemos hacer?, o dicho en otras palabras, ¿cuántos movimientos son necesarios y suficientes para llevar a cabo esa tarea?

12

❚ La mejor manera de enfrentar una pregunta como esta es generalizar un poco. La torre de Lucas tiene 8 discos y la torre de Brahma tiene 64 discos. Consideremos lo que ocurre si tenemos n discos.

❚ La ventaja de la generalización es que se puede reducir el problema. De hecho, normalmente es ventajoso observar primeramente los casos simples.

13

❚ El próximo paso en la solución del problema es introducir la notación apropiada: Name and Conquer

❚ Digamos que Tn es el número mínimo de movimientos para transferir n discos desde una varilla a otra según las reglas de Lucas.

❚ El caso más simple es T0 =0 (los pasos aparentemente triviales pueden ser fundamentales)

❚ Entonces, obviamente, T1 = 1 y T2 = 3.

14

¿Cómo podemos manejar una torre grande?

Ensayemos con tres discos:

A B C

15

La idea ganadora

❚ Transferir los dos discos del tope a la varilla B

❚ Mover el tercer disco a la varilla C

❚ Poner los otros dos sobre él

16

Pista general para n discos

❚ Primero se transfieren los n-1 discos menores a una varilla diferente (lo que requiere Tn-1 movimientos)

❚ Luego se mueve el mayor (lo que requiere un movimiento)

❚ Finalmente se transfieren los n-1 discos a la varilla en que quedó el disco mayor (lo que requiere, de nuevo, Tn-1 movimientos)

17

❚ Así, podemos transferir n discos (para n > 0) en, a lo más, 2·Tn-1 + 1 movimientos

❚ O sea, Tn 2·Tn-1 + 1 , para n > 0

❚ Esta fórmula usa en vez de = porque nuestra construcción prueba que 2·Tn-1 + 1 movimientos son suficientes, no hemos mostrado que son necesarios.

18

Entonces,

❚ Las inecuaciones Tn 2·Tn-1 + 1, n > 0, junto con la solución trivial para n = 0 llevan a:

❚ T0 = 0

❚ Tn = 2·Tn-1 + 1

❚ La recurrencia nos permite calcular Tn para cualquier n.

19

❚ A nadie le gusta calcular a partir de una recurrencia. Cuando n es grande, esto toma mucho tiempo. La recurrencia sólo da información local, indirecta.

❚ Una solución a la recurrencia nos alegraría. Tener una forma cerrada para Tn nos permitiría un cálculo rápido, incluso para un n grande.

❚ ¿Cómo se resuelve una recurrencia?

20

❚ Una forma es suponer una solución y luego probar que esa suposición es correcta

❚ Para suponer (con base), lo mejor es revisar unos “casos menores”❙ T3 = 2·3 + 1 = 7

❙ T4 = 2·7 + 1 = 15

❙ T5 = 2·15 + 1 = 31

❙ T6 = 2·31 + 1 = 63

❚ ¿A qué se parece?

21

❚ Se parece a algo así como Tn = 2n - 1 para n 0. Al menos funciona para n 6.

❚ Las recurrencias son ideales para el tratamiento con inducción matemática.

22

❚ Primero se prueba la afirmación cuando n tiene su valor menos, n0; a esto le llamamos base inductiva. Luego probamos la afirmación para n > n0 suponiendo que ya se ha probado para todos los valores entre n0 y n-1, inclusive; esto es lo que se llama inducción.

❚ En nuestro caso Tn = 2n -1 se deduce fácilmente de T0 =0 y Tn = 2·Tn-1 + 1, para n>0.

❚ La base es trivial, ya que T0 = 20 -1 = 0.

23

❚ La inducción se da para n > 0 si suponemos que Tn = 2n - 1 es verdad cuando n se reemplaza por n-1.

❚ Tn = 2·Tn-1+1 = 2 ·(2n-1-1) + 1 = 2n - 1

❚ De aquí, Tn = 2n - 1 se cumple para n también.

❚ Así, nuestra búsqueda de Tn ha terminado exitosamente.

24

❚ Por supuesto, la tarea de los monjes no ha terminado, ellos están afanosamente moviendo discos y seguirán así por un buen tiempo más, porque para n = 64 hay 264 - 1 movimientos... (alrededor de 18 quintillones).

❚ Aún a la velocidad imposible de 1 movimiento por microsegundo, se requerirían algo así como 5000 siglos para transferir la torre de Brahma.

25

Etapas para encontrar la forma cerrada:

❚ Observar los casos más simples. Esto nos da una visión parcial del problema y es útil en las etapas 2 y 3.

❚ Encontrar y probar una expresión matemática para la cantidad que nos interesa.

❚ Encontrar y probar la forma cerrada de la expresión matemática.

26

Más ejercicios.

❚ Supongamos que un cierto algoritmo A ordena una secuencia de n números en forma ascendente, intercambiando, de alguna manera, pares de números; y supongamos además que puede demostrarse que el número exacto de pasos que el algoritmo A ejecuta es t(n) = 3 + 6 + 9 +...+3n

❚ ¿Cuál es el orden del algoritmo A?

27

❚ Es posible decir que el algoritmo A ejecuta en O(n2) pasos, según el siguiente razonamiento:

❚ t(n) puede escribirse como un término general ya que

❚ Tenemos que demostrar que existen f(n), C y n0 tales que t(n) C·f(n) para todo n n0

t(n) = 3i = 3n(n+1)/2i=1

n

28

❚ Si elegimos C = 3, n0 = 1 y f(n) = n2

❚ Tenemos que demostrar que se cumple 3·n·(n+1)/2 3·n2

❚ En efecto, multiplicando por 2/3 se tiene que n2 + n 2·n2, o sea n n2, lo que es válido para todo n > 1

29

Un cálculo

❚ Supongamos que vamos a ordenar 106 números. Usaremos un algoritmo O(n2) para un supercomputador y un algoritmo O(n log n) para un PC. Digamos que los t(n) respectivos son 2n2 y 50 n log n.

❚ El supercomputador ejecuta 100.000.000 instrucciones por segundo. El PC ejecuta 1.000.000 de instrucciones por segundo

30

❚ El supercomputador demorará:

2·(106)2 instrucciones

108 instrucciones/segundo= 20.000 segundos

5,56 horas

❚ El PC demorará:

50·106 log2 106 instrucciones

106 instrucciones/segundo= 996,677 segundos

16,61 minutos

31

Líneas en el plano(Jacob Steiner, Suiza, 1826)

❚ ¿Cuántos pedazos de pizza puede obtener una persona haciendo cortes rectos con un cuchillo?

❚ O más formal: ¿Cuál es el número máximo de regiones definidas por n líneas en el plano?

32

❚ Una vez más comencemos resolviendo unos casos simples (empezar con el más simple de todos).

❚ El plano sin líneas tiene una región, el plano con una línea tiene dos regiones y con dos líneas tiene cuatro regiones.

33

L0 = 1 L1 = 2 L2 = 4

1 12 1

2

3

4

Cada línea se extiende hasta el infinito en ambas direcciones

34

❚ Nuestra primera tentación podría ser suponer que Ln = n2. O sea, agregar una nueva línea dobla el número de regiones.

❚ Desafortunadamente, esto no es así.

❚ Una nueva línea divide una región antigua en, a lo más, dos regiones, ya que cada región antigua es convexa.

35

❚ Una línea recta puede dividir una región convexa en, a lo más, dos nuevas regiones, que también serán convexas.

❚ Una región es convexa si incluye todos los segmentos existentes entre dos puntos cualesquiera de la región (esto no es lo que aparece en mi diccionario, pero es lo que los matemáticos creen).

36

Volviendo al ejemplo...

❚ Cuando agregamos una tercera línea, nos damos cuenta que podemos dividir a lo más tres de las regiones antiguas, no importa cómo coloquemos las dos primeras líneas.

37

1

2

3

4

38

1a

2

3b

4b

1b 3a4a

Así, L3 = 4 + 3 = 7 es lo mejor que podemos hacer.

39

Vamos viendo la generalización

❚ La n-ésima línea (para n > 0) aumenta el número de regiones en k, ssi divide k de las regiones antiguas, y esto ocurre ssi intersecta las líneas previas en k-1 puntos.

❚ Dos líneas pueden intersectarse en, a lo más, un punto, por lo tanto, una línea nueva puede intersectar las n-1 líneas antiguas en, a lo más, n-1 puntos diferentes.

40

Tenemos el límite superior

❚ Ln Ln-1 + n, para n > 0

❚ Para obtener la igualdad en la fórmula, simplemente colocamos la n-ésima línea de tal forma que no sea paralela a ninguna de las anteriores (o sea, las intersecta a todas) y tal que no pase por algún punto de intersección ya existente (o sea, las intersecta a todas y en diferentes lugares).

41

La recurrencia

❚ L0 = 1

❚ Ln = Ln-1 + n, para n > 0

❚ Conocemos valores para L0, L1, L2, L3 y encajan perfectamente.

❚ Ahora, lo que necesitamos es la forma cerrada de la solución.

42

❚ Tenemos la secuencia 1, 2, 4, 7, 11, 16...

❚ Que no nos parece muy familiar

❚ Una de las formas de entender una recurrencia es “desandando” el camino.

43

Ln = Ln -1 + n

= Ln -2 + (n-1) + n

= Ln -3 + (n-2) + (n-1) + n

...

= L0 + 1 + 2 + 3 + 4 + ... + (n-1) + n

= 1 + Sn

en que Sn = 1 + 2 + 3 + 4 + 5 + ... + (n-1) + n

En otras palabras, Ln es 1 más la suma de los n primeros enteros positivos

44

La cantidad Sn es muy popular

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Sn 1 3 6 10 15 21 28 36 45 55 66 78 91 105

Estos valores se llaman también números triangulares

...

45

❚ Para evaluar Sn podemos usar el truco de Gauss

Sn = 1 + 2 + 3 + 4 + ... + (n-1) + n

Sn = n + (n-1) + (n-2) + (n-3) + + 2 + 1

Sumando:

2Sn = (n + 1) + (n + 1) + (n + 1) + ... + (n + 1) + (n + 1)

46

La solución

❚ Ln = [n·(n + 1)/2] + 1, para n 0

❚ Sólo falta demostrar que la recurrencia es correcta

47

❚ Usando inducción

❚ Ln = Ln-1 + n = [½(n - 1)·n + 1] + n

❚ = ½ n·(n+1) + 1

❚ Ahora sí. O sea, estamos hablando de O(n2)