Full transcript
0:09Buenos días.
0:10Bienvenidos a la clase.
0:14Vamos a continuar hoy día con el
0:15análisis
0:22de árboles de búsqueda binaria
0:27más mediana de tres.
0:31habíamos eh llegado, a ver, para
0:34recapitular
0:36que teníamos una ecuación
0:41vectorial
0:43eh de la forma
0:56ya
1:04Okay. Donde
1:07Au n
1:11Z es el vector
1:15del número
1:18e
1:22esperado
1:25de hojas.
1:29de tipo
1:310 1 y 2 respectivamente, ¿no es cierto?
1:40Y donde Hz
1:44es una matriz que es -1
1:500 - 2 2
1:5506z - 3. [suspiro]
2:02Okay. Y eso es para número esperado de
2:07hojas. de cada tipo. para la función
2:12generatriz de probabilidad
2:17es de la forma 1 parido por n + 1 por un
2:21vector cd
2:25por a sub nz
2:38CDZ
2:42vector es un vector fila
2:46que tiene eh
2:49verlo aquí
2:59uno
3:04z y z + 2z².
3:11Okay.
3:13Y esto lo solucionamos
3:15y llegamos a que eh la solución que
3:18encontramos para esto
3:22es de la forma
3:25p z
3:27= 1/ n + 1
3:32c z por un coeficiente binomial
3:35simétrico de la matriz HDZ.
3:41y por la condición inicial.
3:44Ya. Y
3:49para
3:52calcular
3:57Hz n
4:00usamos
4:02diagonalización.
4:11Entonces,
4:19entonces
4:22si lambda 1
4:25es z, lambda 2 de z, lambda 3 de zon
4:32los valores propios.
4:39de HDZ
4:42y E
4:44es la matriz
4:49de los vectores propios.
4:58Entonces,
5:11Pz
5:14se puede escribir como 1 di por N + 1
5:19por C de Z
5:22por la matriz G.
5:25Luego una matriz diagonal
5:29que contiene los coeficientes binomiales
5:31simétricos lambda 1 de z n,
5:36lambda 2 de z n,
5:40lambda 3 de z n
5:44y entre esto es una matriz diagonal
5:48y luego
5:50tenemos g a la men1 uno
5:59y finalmente la ponencia inicial.
6:08Ya, esa es la solución que que
6:11encontramos y hasta ahí más o menos
6:12llegamos en la en la clase pasada. Ah,
6:16entonces eh
6:19antes de seguir adelante,
6:23esta expresión que vamos a trabajar con
6:26ella, ¿no? Y que es más o menos
6:30eh
6:31intimidatoria,
6:34eh no es tan feroz como parece,
6:37porque
6:39miren lo que ocurre.
6:42Esto aquí es un vector fila.
6:47vector fila C por una matriz E es un
6:49vector fila de funciones que dependen de
6:51Z, no dependen de N, dependen de Z.
6:56Esto de acá es un vector columna
7:00también de funciones que dependen de Z.
7:03Entonces, si yo tengo un vector fila por
7:06esta matriz diagonal, por este vector
7:08columna, lo que va a pasar es que este
7:10vector fila, la primera componente va a
7:12multiplicar a esto, la segunda va a
7:14multiplicar a esto, la tercera va a
7:16multiplicar a esto, ¿ya? Y vamos a tener
7:18un vector fila. Entonces que eh son tres
7:23componentes. La primera que es alguna
7:26función multiplicando a este binomial
7:28simétrico. La segunda alguna función de
7:31Z multiplicando este coeficiente bomal
7:32simétrico y así. Y luego ese vector fila
7:35se va a multiplicar por este vector
7:37columna. Y eso va a hacer que cada
7:39componente aquí se multiplique por
7:40alguna función de Z, ¿ya? Y luego todo
7:43eso se sume. O sea, que después de hacer
7:46todas esas operaciones,
7:49eh lo que va a quedar es algo de la
7:50siguiente forma.
7:54Esto tiene la forma
8:02pes
8:04por n + 1
8:07por un alfa 1 de z. una función que
8:09puede ser muy complicada
8:11por lambda 1 de z n
8:17más
8:18una función que puede ser muy complicada
8:20importa
8:22por lambda 2 de z n.
8:26Y por último,
8:37eso ya esa es la forma que tiene. Es una
8:40suma de tres términos,
8:42cada uno de los cuales es alguna función
8:44multiplicando a un coeficiente binomial
8:46simétrico. ¿Ya? Nosotros vamos a poder
8:49calcular la forma exacta de estas
8:51funciones alfa 1, alfa 2, alfa 3, pero
8:53para esta discusión eso no es muy
8:55importante por lo que les voy a decir a
8:59continuación, ah, que es que eh,
9:05para z = 1
9:11se debe tener
9:15que p sub n de 1 es =
9:17Eso es necesariamente así porque eso es
9:20una función de generatriz de
9:23probabilidad, ¿no es cierto?
9:27Porque Pu Z es una función generatriz de
9:33probabilidad.
9:34Entonces, ¿qué pasa si yo sustituyo z =
9:371 en la forma que acabo de decir que
9:41tiene que tener p?
9:43Entonces va a quedar p sub n de 1
9:47va a ser igual a 1/ido por n + 1 por un
9:51alfa 1 de 1. Algún valor va a ser ese
9:55por eh,
10:00a ver, aquí me faltó eh aquí tengo un
10:03pequeño error en la forma como escribí
10:05esto. Vamos aquí esto es la onda 1 de z
10:08n.
10:10Ya. Entonces va a ser de Z. Aquí se
10:13cierra y el coma N está ahí. Eso. Había
10:16que cerrar primero. Ya. E
10:20a ver, quizás podríamos volver atrás,
10:23eh, porque nosotros sabemos qué formas
10:26tienen exactamente los escribos aquí.
10:29Alfa 1 por lambda 1 de 1, n, ¿no es
10:33cierto? alfa 1, perdón, alfa 2 de 1 *
10:38lambda 2 de 1, n
10:42más alfa 3 de 1
10:45por lambda 3 de 1, n, ¿no es cierto? Ya.
10:49Y recordemos,
10:53porque eso lo calculamos la clase
10:54pasada,
10:57que nosotros conocemos la forma exacta
11:00de estas eh de estos
11:07de estos valores propios, ¿no? A ver, lo
11:10tengo por ahí. Aquí está.
11:13Okay. La forma exacta es que eh
11:20que lambda 1 de z
11:23era eh igual a -1.
11:28Lambda 2 de z
11:31sería -5/
11:36y más
11:391/2 í 1 + men 1 + 48z
11:48y lambda 3 de z
11:52-5
11:54- 1/2√ 1 + 48 Z. Eso lo calculamos
12:00resolviendo la ecuación característica,
12:03¿no es cierto? Y
12:06para z = 1
12:10tenemos,
12:12por supuesto, que lambda 1 de 1 es ig a
12:15-1.
12:18¿Cuánto vale lambda 2 de 1?
12:20Vale, la raíz de 1 + 48 z es 7 - 5 + 7
12:26es 2/ 2 es 1
12:30y lambda 3 de 1 es -5 - 7 es -1/ 2 es
12:38-6.
12:40Así que para z = 1 yo tengo un valor
12:45propio que vale 1 y dos valores propios.
12:51negativos. Okay. Entonces, ahora, por lo
12:56tanto,
12:57¿qué forma tiene p N1? Ah, lo tenemos
13:00ahí, ¿no es cierto? Va a ser 1 parido
13:03por 1 di por n + 1
13:08por alfa 1 de 1.
13:12Y acá vamos a tener 1, n,
13:15perdón, no, -1, n.
13:22Ya.
13:24Maj alfa 2 de 1
13:27por 1, n
13:29+ alfa 3 de 1
13:32por -6, n.
13:36¿Okay? Entonces, ahora hagamos un
13:38pequeño paréntesis porque
13:41nosotros hemos
13:43trabajado con estos coeficientes
13:45binomiales simétricos, ¿no es cierto?
13:47sabemos eh
13:49lo hemos definido en función del
13:51coeficiente binomial normal, ya tenemos
13:55varias otras
13:57definiciones equivalentes, pero hasta
13:59ahora me da la impresión que nunca
14:00habíamos visto qué eh significaba tener
14:04un coeficiente binal simétrico en que
14:06uno de los dos argumentos era un entero
14:09negativo. ¿Qué significa eso? Ah eh
14:13siempre pensamos que esos coeficientes
14:15son
14:17no negativos, o sea, esos argumentos
14:19para el coeficiente unal simétrico son
14:20no negativos. Pero, ¿qué pasa cuando
14:22algo es negativo?
14:24Eh, entonces la pregunta es, ¿qué
14:25significa
14:33- k
14:38mayor o igual que 1?
14:40Eh,
14:43ej, ponga un ejemplo. Ah, bueno, antes
14:45de poner el ejemplo,
14:50recordemos que
14:57e x n
15:02ya
15:03eh de las varias maneras que tengo para
15:05definirlo,
15:07una es que es x + 1 a la n ascendente
15:10dividido por n factorial.
15:13¿Okay?
15:15Entonces, eh ahora sí pongamos un
15:17ejemplo.
15:23Pongamos, por ejemplo, si fuera -3 n.
15:26Ah,
15:34eh, eso,
15:38eh, bueno, pero no tengo aquí poner un
15:40interrogativo.
15:42Yo sé lo que va el -3 n es -3
15:48a la ncendente partiido por n factorial,
15:50¿no es cierto?
15:53Entonces, hagamos una pequeña tablita
15:55aquí.
15:58Eh, ¿cuánto es -3,0?
16:01Porque el ní es mayor o igual que 0
16:02siempre. Ya. - 3,0
16:05es -3 a la 0 ascendente
16:10partido por 0 factorial, ¿no es cierto?
16:13Y -3 a la 0 ascendente es 1. Así es que
16:16y 0 factorial es 1. O sea, esto vale 1.
16:19Ya. -3,1. ¿Qué significa eso? Eso es -3.
16:25a la 1 ascendente partido por 1
16:27factorial y eso es -3 a la 1 ascendente
16:31es -3
16:33dividido por 1 -3 o se el primero era 1
16:37el segundo es negativo -3 cuánto vale
16:40-3,2
16:43sería -3 a la 2 ascendente parido por 2
16:46factorial
16:48y eso sería, digamos, ya dejémoslo con 1
16:51por 2 factorial, que bueno, es 2 eh
16:53multiplicado por -3 3 a la 2 ascendente.
16:55Eso va a ser
16:57-3.
17:00Eh, bueno, demasiados paréntesis
17:04va a ser -3.
17:08A ver, espérense. No, no, no estoy
17:10equivocado. No estoy me he equivocado en
17:12casi todo. Ya borremos, borremos bien
17:15borrado porque parte
17:19ya
17:24porque es x + 1 a la ncendente.
17:28H.
17:29Entonces, en realidad
17:32esto va a ser eh
17:39va a ser -2
17:42a la cero ascendente partido por 0
17:45factorial. Va a ser -2 porque eso está
17:49bien o no.
17:55Eh,
18:00ah, sí, sí, está bien. Ya, listo. Eh, va
18:03a ser -2.
18:05Eh, acá esto va a ser eh
18:09-2
18:11* -1 parido por 1, o sea, va a ser +2
18:17y este acá va a ser
18:24-2.
18:29De nuevo estoy mal que sea demasiado
18:31temprano.
18:34Ya vamos, vámonos. Eh,
18:39ya va a ser -2 no más partido por uno.
18:48Claro, por eso por por eso está mal,
18:50porque incluso ese está mal. Ya, ahora
18:52sí, disculpen. Esto es uno siempre. -2
18:54la 0 ascendente es 1. Así es que eh y
18:58esto este sí es -2 y este va a ser -2 *
19:02-1,
19:04¿cierto? Porque es ascendente partido
19:06por 2 factorial,
19:09o sea, va a ser
19:12eh más 1.
19:14Fíjense que alternando los signos y
19:17cuánto va a ser -3,3
19:22va a ser -2.
19:24por -1 * 0 dividido por 3 factorial,
19:29¿ya? Y eso es cer0.
19:33Ya.
19:35¿Y qué es -3,4?
19:40va a ser -2 * -1 * 0 * 1
19:464 factorial, pero eso es cerivamente
19:51de aquí para adelante
19:57ya de de aquí hacia adelante son todos
20:00ceros.
20:04Entonces, eh si a partir de este ejemplo
20:08tan confusamente desarrollado podemos
20:11general generalizar, vamos a decir que
20:15en general
20:21- k n
20:28- k n
20:31igual
20:33a
20:34valores
20:37con signos
20:40alternados
20:45para n
20:54- 1
20:58y 0
21:01para n mayor o igual que k.
21:07O sea,
21:09si volvemos a nuestra forma de la
21:12función aquí pes de 1,
21:16tenemos esto, ¿okay?
21:20Esto de aquí va a ser 0 para n mayor o
21:23igual que 1 y de ahí para adelante, o
21:25sea, 0 mayor igual que 1. Este de acá va
21:28a ser 0 para n mayor o igual que 6.
21:31O sea, el principio para valores
21:33pequeños de n, vamos a ver que este no
21:36mucho, pero este sí en particular aporta
21:38un término tranciente que cambia de
21:41signo para cada uno. Así es que eso
21:43genera algunas oscilaciones al
21:44principio, pero de n igual a 6 para
21:47adelante aporta cero y este aporta cero,
21:51¿ya? Eh, y así que el único que se salva
21:54es este
21:57y este es eh 1, n es siempre es igual a
22:01n + 1.
22:03¿Ya?
22:05Entonces,
22:08por lo tanto,
22:14para n mayor o igual que 6
22:18peso n de 1 es simplemente 1/ n + 1
22:23por
22:25alfa 2 de 1
22:28por
22:30eh
22:32n1.
22:34Ya, pero n1 es ig a n + 1.
22:46Esto de aquí es igual a n + 1, por lo
22:50tanto se cancela con esto, ¿ya? Y todo
22:54esto
22:56resulta ser igual a alfa 2 de 1.
23:01Eso implica que alfa 2 de 1
23:04necesariamente
23:10tiene que ser igual a 1
23:16para que
23:20peso n de 1 sea igual a 1. ¿Ya?
23:24Entonces, hay mucho que no a esta altura
23:27todavía, mientras no lo calculemos, hay
23:29mucho que no sabemos
23:32de
23:34hay mucho que no sabemos
23:36de de la forma de todas estas funciones.
23:38Ahí van a ser funciones tremendamente
23:40complicadas,
23:42pero no importa porque para n = 1 eh el
23:47primer y el tercer término desaparecen.
23:49El segundo, el 1+ n cancela el n + 1 el
23:52denominador.
23:54Y lo único sobrevive es el alfa 2 de un
23:56y el alfa 2 de 1 tiene que ser uno
23:57necesariamente. Así que sabemos bastante
24:00sobre esto sin haber resuelto nada
24:02todavía.
24:03Eh, esto nos dice varias cosas. Eh, si
24:08pensamos en este problema un poquito más
24:09general, incluso
24:11eh un problema con una solución de este
24:13tipo,
24:15tiene que haber siempre un valor propio
24:19que en z = 1 sea igual a 1. Tiene que
24:22haber ah, o sea, tiene que haber algo
24:24siempre que aporte un término de la
24:27forma 1, n, porque eso para cancelar a
24:31eso.
24:32y y como p sub n de 1 es 1,
24:36esto no puede depender de n, así que
24:38todo lo que dependa de n se tiene que
24:39cancelar, se tiene que ir, ¿ya? Así que
24:42tiene que haber siempre un término eh un
24:45valor propio que evalúan z = 1 sea igual
24:48a 1. Ya. Eh,
24:53no puedo dar ninguno que en Z 1 sea
24:55mayor que un porque si fuera mayor que
24:57uno, por ejemplo, fuera igual a 2,
24:59estaría aportando un término cuadrático
25:02que a lo más esto le cancela un una
25:05potencia, pero sobreviviría términos que
25:07dependen de n y eso no puede ser. Ah,
25:10así que tiene que haber uno que en z = 1
25:13valga uno y no puede haber ninguno que
25:14en z = 1 valga tenga un valor mayor que
25:17uno. Ah, todos los demás tienen que ser
25:18menores que uno.
25:20Y
25:22así es que eh eso nos eh acota bastante
25:25lo que podemos hacer y eso va a resultar
25:28eh finalmente muy útil eh más adelante,
25:32como vamos a a ver. Ya. Entonces, creo
25:36que ahora ya estamos como listos para
25:39empezar a a calcular un poquito más ya
25:43aquí.
25:45Entonces,
25:48ahí
25:52vamos a a calcular.
25:58Vamos a cambiar de pantalla.
26:17Muy bien.
26:19Vamos. Entonces,
26:21vamos a necesitar
26:24para
26:26dos variables
26:29z y n como variables formales.
26:44Ahora vamos a definir la matriz H.
26:58Ya. Y esa matriz es una lista de filas.
27:04Entonces, tengo aquí una lista. Ya. La
27:06primera fila
27:10tiene la forma -100.
27:18La segunda fila,
27:20eh,
27:25la segunda fila es 1 - 2 6z.
27:38La tercera fila es 0 2 - 3.
27:52Y pongamos que nos muestre la matriz H.
27:57Ahí la tenemos.
28:02Entonces vamos a calcular los valores,
28:04los valores propios. Entonces eso lo
28:06vamos a dejar los lambda, con la letra
28:08L, por l L por lambda. Entonces van a
28:11ser los Hig
28:13values
28:18y que me muestre la lista L.
28:23Ahí están nuestros valores propios, ¿se
28:25acuerdan? Ahí está el -1 que va en
28:27tercer lugar, ¿eh? Y está el menos
28:32el -5/ men 1/ raí de 1+ 48 z queo
28:35apareció primero y el -5/
28:40raíz de de 1 + 48 z que apareció en
28:44segundo lugar en este caso. Ya
28:48aquí ahí los tenemos lo que calculamos a
28:51mano el otro día y ahora voy a pedir los
28:56vectores propios.
28:59Bueno, corta
29:01eh h punto igen vectors
29:08right.
29:12Eso. ¿Por qué right?
29:16Porque por alguna razón
29:19el
29:21default de
29:27Sage no es calcular vectores propios
29:31resolviendo la ecuación a * x = lambda
29:34x, ah, sino que multiplicando el x a la
29:37izquierda x a = lambda x. Esos son.
29:41Entonces, si uno quiere que sea al
29:44estilo que los necesitamos, hay que
29:46ponerle X vectors por la derecha,
29:49vectors right. Ahí está. Eso. Ahora,
29:51fíjese lo que es cada una de estas
29:53cosas. Ah, bueno, esto no solo podría me
29:56ahorrado haber calculado los valores
29:58propios porque aquí me los volvió a dar,
29:59¿se fij? Entonces, esto es una lista en
30:03que cada una de estas listas contiene
30:05una tupla
30:06y la tupla, la primera componente es el
30:11valor propio y la segunda componente es
30:16una lista que en su interior contiene
30:18una tupla
30:20que son los eh
30:24los eh [carraspeo] que es el vector
30:27propio, ¿no?
30:29tres componentes. Ya.
30:32Entonces, eh
30:36ya qué hacemos después? Eh armamos la
30:41matriz E. Entonces,
30:45de hecho, voy a hacer un poquito de
30:46trampa
30:50y voy a copiar esto porque ya lo tenía
30:52preparado de antes, un poquito latoso
30:54escribir
30:58porque esto es como una lista que en su
31:00interior una tupla, que en su interior
31:01tiene una lista que se que ir extrayendo
31:03cosas ahí.
31:05Ya. Eh,
31:10y esa es la matriz resultante.
31:14Aquí está la primera columna 01 con
31:16esto. Segunda columna 0 1 esto y la
31:21tercera columna es el 1 menos eso y eso
31:25otro. Esa es. Ah, ¿y por qué transpose?
31:28Porque en realidad me la había dado
31:29transpuesta, tuve que transponerla para
31:31que quedara como tenía que quedar.
31:35Ya.
31:37Y ahora eh puede calcular la inversa.
31:42Ponemos
31:43e subrayado uno como la e a la men por
31:46decir de E a la men 1, que es el e pun
31:49inverse,
31:53¿ya? Y que me muestre la matriz.
32:00Ah, no, no la matri la matri la men1.
32:05Eso ya
32:08ahí está mejor
32:10bien corchudo como pueden ver.
32:15Pero así es esto.
32:17Ya estamos listos con la inversa.
32:20Eh, de hecho, podríamos
32:23aprovechar de chequear de que está bien
32:24calculada la inversa, ¿no es cierto?
32:26Entonces, vamos a multiplicar e * a la
32:28-1. Y eso sale una cosa bien enredosa
32:31porque como son cada cada término ahí.
32:35Así que le vamos a pedir que factorice
32:36cada término y al factorizarlo lo va a
32:38simplificar.
32:43E* e a la men 1
32:48y como debe ser y afortunadamente
32:52es la identidad. Ah, así que está bien,
32:54está bien invertida la matriz.
32:57Ya.
32:58Ahora, eh,
33:04¿cuál era el rol de esta de estas
33:07función de estas matrices e a la -1? Es
33:11porque la matriz H se factoriza como e
33:15por la diagonal de los valores propios
33:18por e a la men 1, ¿no es cierto?
33:21Entonces, podríamos aprovechar de, esto
33:23no es necesario para la solución, pero
33:25para podríamos aprovechar de chequear de
33:27que está bien factorizada la matriz H.
33:30Ah, que si yo hago e por la diagonal de
33:33los valores propios por la e a la men 1,
33:37eso tiene que
33:40resultar la matriz H original. Hagamos
33:44eso. Entonces, voy a formar una matriz
33:47diagonal.
33:51de la diagonal matrix
33:59don
34:01yo le doy la lista de los valores
34:04propios y me arma una matriz diagonal
34:06que que tiene esos valores propios en la
34:08diagonal.
34:09Ahí está. ¿Se fijan? Ahí están
34:11exactamente los valores propios en la
34:12diagonal y el resto es cero. Entonces
34:15ahora le voy a decir que eh
34:21voy a hacer e * d por e a la -1 y que lo
34:24factorice como hicimos antes,
34:28eh por d * e a la -1. Eso debería ser la
34:33matriz h.
34:34Ya.
34:36Eh,
34:40bueno, hagamos eso
34:43y veamos qué sale. Ya se parece a
34:47la matriz H, ¿se acuerdan? Era -1 la
34:51primera columna -2 2 06z - 3.
34:56Esta casi me le falta un pelito, va a
34:58estar bien simplificado, ¿no es cierto?
35:00Entonces, le vamos a agregar aquí que
35:02expanda cada término y eso va a ser
35:05resultar lo que le faltaba para que
35:07terminara de recuperar la matriz H. Así
35:09es que check. Ah, o sea, tenemos bien
35:13nuestra matriz eh
35:16tenemos bien nuestra matriz H bien
35:18factorizada. Entonces, si la matriz H
35:20está bien factorizada, yo puedo seguir
35:22adelante.
35:24Y eh para el cálculo que ahora requiere
35:27que yo
35:30defina mi vector C,
35:34es un vector
35:38que tiene 1
35:41coma 2* z,
35:46coma es z + 2*
35:54cuadrado.
36:03Ahí está mi vector fila. Okay, vamos.
36:08Eh, necesito también definir mi vector
36:13de condición original, eh, cierto,
36:17acero.
36:20Acero también va a ser un vector
36:25que va a tener eh
36:291,0,0.
36:31Eso es.
36:37Eh, ya.
36:41¿Qué más? Eh,
36:44ah, ahora voy a
36:49definir
36:52lo que es un coeficiente simétrico
36:56X N.
36:58Ya,
37:00¿qué retorna eso?
37:04Retorna el factorial ascendente que en
37:07que en se existe. Se llama rising
37:10factorial,
37:13de la potancia factorial ascendente
37:16que parte de x + 1 en adelante. Es lo
37:19que yo me equivocado. X + 1, n.
37:24Entonces, eso significa que + 1 a la
37:26ncendente y dividido por el factorial de
37:29n.
37:35Ya,
37:37esto. Entonces ahora
37:41nuevamente voy a hacer un poquito
37:42trampa. Voy a escribir, voy a copiar
37:45donde ya lo tengo preparado
37:48lo que es.
38:01es el P va a ser C por E por la matriz
38:07diagonal que tiene el coeficiente bineal
38:10simétrico del lambda 0 n. Eso
38:15tiene el coeficiente simétrico lambda 1,
38:18n, tiene el coeficiente simétrico lambda
38:202, n eso es lo que tiene en la diagonal,
38:22¿ya?
38:23Y luego todo eso por e a la -1 y por a0
38:26y finalmente dividido por n + 1. Ya.
38:37Y ahí, como pueden ver ustedes, salió
38:39algo más o menos complicado.
38:46[suspiro]
38:54E
38:56esto no lo tenía preparado, así que no
38:57estoy seguro que me vaya a funcionar a
38:59la primera, pero por curiosidad
39:01podríamos chequear de ver de en P
39:05sustituir Z = 1, ¿no es cierto?
39:10Debería ser uno,
39:20¿eh?
39:30Eh, está bien eso
39:37no parece estar muy bien. Ah,
39:40¿por qué dice? Debería
39:43este en mi versión correcta debería
39:45haber dicho 12.
39:49A ver,
39:51vamos a ver. que me equivoqué.
39:53Ah, mira, pues dice Z cubo aquí. ¿Y por
39:56qué dice Z?
39:58Ah, claro, porque esto es Z.
40:04Mir, ninguno de ustedes lo había
40:05detectado. Ah, cuando dije z + 2 * Z cu,
40:09erróneamente escribí z por 2 z cu. Ahí
40:13salió un ZQ, no hay que ver ZQ. Ya, todo
40:16nuevo, o sea, a partir de ahí, ¿no es
40:18cierto? Entonces, ehamos
40:22eso ya
40:24este no debería no seía afectado. Esto
40:26tampoco, pero igual mira, por suerte che
40:29sequea
40:30eh
40:32ya ahí dice 12. Claro. Y ahora
40:40y
40:44todavía no está del todo bien porque hay
40:46un cuatro.
40:49Me equivoqué en algo más.
41:00A ver, hasta ahí.
41:16Ese estaba bien.
41:20Hasta ahí. Ese ese chequeo dio bien, ¿no
41:22es cierto?
41:24un el c vector
41:271 2 z z + 2 z²
41:35la sub es claro pues miren
41:39eso es culpa de ustedes que no me
41:41corrigen mis errores. Esto es cero. Si
41:44yo dije 1 y escribí 101.
41:54Hay profesores que dicen que que se
41:57equivocan de esta manera
41:58intencionalmente para ver si los alumnos
41:59están poniendo atención. Ah, no es mi
42:02caso. Ah, yo me equivoco porque me
42:03equivoco.
42:06También había un profesor eh muy famoso
42:10y respetado eh físico Igor Saavedra, que
42:14hacía clases todos los semestres con los
42:16mismos apuntes y sus apuntes tenían
42:19algunos errores y él no los corregía.
42:22Ah, pues yo decía que de esa manera eso
42:24lo obligaba a él a estar atento mientras
42:26estaba haciendo clase para darse cuenta
42:28de los errores.
42:30Eh, así es que ya
42:331 pues obviamente.
42:35Ah, entonces ahora eh
42:40eso se ve bastante mejor. Si ahora
42:42venimos si tuvimos 7 = 1 ahí
42:47eh
42:50ahí estamos. ¿Estás? ¿Ustedes saben qué
42:52cosa es gama de n + 2, ¿no es cierto?
42:56Ah,
42:57¿saben qué cosa es gama de n + 2?
43:01Gama de n + 2 es n + 1 factorial
43:06y lo que hay en el denominador es n + 1
43:09factorial.
43:10Así es que está bien, vale uno. Que
43:14estuvo bien haber hecho el esta este
43:17chequeo. Ah.
43:19Eh,
43:20bueno, y aquí cuesta un poco darse
43:23cuenta, pero aquí está lo que yo les
43:24había dicho. Aquí hay todo este corcho
43:28está multiplicando
43:30a
43:31al
43:35factorial ascendente,
43:37fondo al coeficiente binomal simétrico.
43:40Ah, y entre esto y esto hacen un
43:43coeficienteal simétrico. Y este otro
43:45corcho al otro y este otro corcho al
43:47otro. Ah, así que, perdón,
43:52eh, ¿cuántos términos tengo aquí?
44:020 1 2 A. Un poquito raro, pero parece
44:05que está bien. A ver.
44:10P.
44:18Ah, es que hay dos que están combinados,
44:20parece.
44:23Raro.
44:24Bueno, por lo menos este chequeo dio
44:25bien. Ah, ya. Eh, sigamos mejor.
44:30Ya, ¿para qué quería todo esto yo, por
44:32ejemplo,
44:34porque quiero calcular el valor
44:36esperado,
44:39el mu
44:41eh de para la función generatriz P es el
44:45costo esperado de búsqueda infructuosa.
44:49El costo esperado de búsqueda infructosa
44:50para los árboles de búsqueda en área
44:51común y corriente es 2 multiplicado por
44:55hn + 1 - 1, ¿ya? O sea, dos veces un
44:58armónico. Okay. Eh,
45:02esto debiera ser mejor
45:05porque eh de alguna manera los árboles
45:08van quedando mejor balanceados,
45:10ya a medida que se construyen, porque el
45:13que va quedando de raíz en cada subárbol
45:15no es un elemento aleatorio, es la
45:17mediana de tres elementos.
45:19Entonces
45:21ese que va quedando como raíz está es
45:24una mejor aproximación de la mediana del
45:26conjunto que lo que sería tomar un
45:27elemento cualquiera al azar, ¿ya?
45:30Eh, así que esto debería quedar mejor
45:32balanceado. ¿Cuánto mejor balanceado? Es
45:35lo que vamos a descubrir ahora cuando
45:37terminemos de hacer este cálculo. Ya. El
45:40punto de comparación es que para los ABs
45:42común y corrientes el coeficiente es
45:45dos. dos por el armónico. Vamos a ver
45:48qué coeficiente nos resulta aquí. Ah. E
45:51entonces para eso vamos a tomar eh vamos
45:55a calcular el mu,
45:58¿ya? Que va a ser el pf
46:06respecto de Z. Derivamos respecto de Z.
46:10Ya. Y luego yo tendría que sustituir eh
46:14z = 1. Eh, lo podría hacer, pero voy a
46:18tener problemas. Como no sé porque ya lo
46:20hice y tuve problema porque al al poner
46:247 = 1 eh quedan algunos
46:29eh algunas algunas cosas la forma cero
46:33dividido por cero. Ah. Eh, y para que
46:37entonces para pero que no pero son eh
46:40singularidades removibles. Entonces,
46:43para que lo calcule bien, no voy a no
46:45voy a hacer una simple sustitución, sino
46:48que le voy a pedir que me calcule el
46:50límite
46:53cuando z es ig a 1. Cuando z tiende a 1.
46:56Ya. Y eso va a resolver el problema de
46:59esta de estas singularidades que
47:02aparecen, que como le digo son
47:06eh son aparentes nada más. Eh, y a esto
47:10le voy a pedir que lo expanda.
47:16Bueno, y que después me muestre el bu.
47:21Entonces, demorar un poquito ese
47:22asterisco ahí indica que está
47:23calculando,
47:25¿eh?
47:27Por cálculo en límite, supongo.
47:30Hay que darle un poquito de tiempo.
47:39Ojalá que no tanto.
47:42Mientras esto calcula,
47:45aparte de los errores que he cometido,
47:46que a lo mejor espero que hayan servido
47:48para para que pongan más atención,
47:51[risas]
47:54no no no es una estrategia intencional,
47:56pero así resultó. Ya espero que vayan
47:59siguiendo esto, ¿no es cierto? Ya ahí la
48:00ahí lo tenemos. Esa es la solución ya.
48:05Eh,
48:08y pero se un poquito sucia porque está
48:11ese famoso gama N +2 que en realidad es
48:12n +1 factorial.
48:15Entonces, lo que le voy a pedir es que
48:18para limpiarlo un poquito
48:20me eh al mu
48:23le aplico una sustitución.
48:26Las sustituciones en general eh las
48:29sustituciones simples sustituyen una
48:31variable por un valor, ¿ya? E si yo
48:35podría decir sustituir n por tal cosa,
48:37ya. Pero aquí lo que yo quiero es
48:38sustituir una una expresión, la
48:41expresión gama de n + 2 quiero ponerle
48:43que que es eh que es el factorial de n +
48:471. Entonces para eso est investigando un
48:50poco porque como les digo yo s no sé
48:53mucho eh todo caso ya sé más que al
48:56comienzo del semestre.
48:58Eh en una sustitución a Sage se le puede
49:01poner un diccionario de Python.
49:04Y entonces el diccionario consta de una
49:07llave, bueno, muchas no puedes puede ser
49:09varios, pero consta de pares llave coma
49:12valor, ¿ya? O llave dos puntos valor se
49:14escribe en el diccionario.
49:17Eh, entonces esa llave puede ser en el
49:21caso de Sage una
49:24expresión, una subexpresión.
49:26Entonces, eso hace que dentro de la
49:28fórmula busque esa su expresión y la
49:30sustituya por lo que uno dijo. Entonces,
49:32le voy a pedir entonces el diccionario
49:34se escribe entre llaves
49:36y primero se escribe la lo que yo quiero
49:39sustituir, que sería el gama
49:42de n + 2.
49:46Y eso dos puntos, ¿ya? Y ahí le digo,
49:50¿qué es lo que voy a poner en su lugar?
49:52En realidad, como les digo, gama n + 2
49:54es n + 1 factorial. Pero para hacerle la
49:56vida simple, lo voy a escribir como n +
49:591
50:01por el factorial
50:04de
50:06de n, ¿no es cierto? n + 1 por n
50:10factorial es n + 1 factorial, pero lo
50:12escribo así y ustedes se dan cuenta por
50:14qué, ¿no es cierto? Para que cancele con
50:15lo que hay el denominador.
50:19Y ahí lo tenemos.
50:21Falta solamente un pequeño paso, pero
50:23ese creo que lo voy a hacer a mano. Este
50:26gama su es la constante de Oiler. Ah.
50:30Eh,
50:32y de la tarea uno, ustedes se deben
50:36acordar que ustedes tenían que explorar
50:38la relación entre los números armónicos
50:41y y la función sí, ya que se llama
50:44digama.
50:46Y
50:48la relación que hay es que el armónico
50:53de n es igual, no es una aproximación,
50:56es igual así de n + 1 + gama.
51:01es el armónico de n, como está escrito
51:03aquí, esto va a ser el armónico de n +
51:051. Entonces, eh, este si de n + 2 + gama
51:10va a ser armónico de n + 1. Así que esto
51:13es igual a 127 por el armónico de n + 1
51:18- 7549,
51:21¿ya? Y ese 127 es la es la constante que
51:26se compara con dos.
51:29era 2 HN + 1 para los ABB comunic y
51:32corrientes, va a ser 127 HN + 1 para los
51:37armonio, para los eh árboles de busca
51:40binaria con mediana de tres, o sea, el
51:42coeficiente dos lo hemos bajado a 12,
51:45¿ya? Lo cual en la práctica es bien eh
51:48importante ah porque el coeficiente dos
51:51no puede bajar demasiado eh porque el
51:54límite son los
51:56árboles perfectamente balanceados. Ah,
51:59así que esto de hecho esto el exceso por
52:03sobre ese mínimo lo reduce como a la
52:05mitad, así que no no es no es no es
52:07poco.
52:08Solo por hacer esta pequeña eh este
52:11pequeño balanceo local en los árboles de
52:13tamaño menor igual que que tres. ¿Ya?
52:17Así que con esto
52:19vamos a volver a nuestra pizarra.
52:40Okay.
52:42Y por lo tanto,
52:44entonces ahora
52:51calculando en seis
53:06que el
53:09musu para mediana de tres.
53:13que es igual al average
53:16del peso n z
53:20es igual a 127
53:23por h + 1
53:27- 7549
53:32y eso ese cálculo no lo hice, pero
53:36créanme que es aproximadamente igual a
53:391.19.
53:41log 2n
53:45y esto
53:56loss regulares
53:59sin sin la sin estabística de balanceo
54:01local en que el mus n para los abb
54:08era 2 HN + 1 - 2, que es aproximadamente
54:15igual a 1.38
54:19log 2 de n.
54:21¿Ya? Entonces, se fijan ustedes que
54:25eh
54:28aquí la constante es 119, acá la
54:30constante era 138, ¿no? Y el mínimo que
54:34puede tener es uno. El mínimo es un
54:37árbol perfectamente balanceado, tiene un
54:39costo de búsqueda infructuosa de de uno
54:44por los 2 DN. Ya. Así que eh el piso es
54:48uno y esto lo que hace el 1.38 lo reduce
54:51a 1.19 que es la mitad. Ah, así que es
54:56eh una mejora bastante significativa
55:00con eh
55:02con un trabajo que es eh bien que
55:09simple, ¿cierto? No es no es una cosa
55:12muy difícil.
55:13Okay.
55:16Eh,
55:21okay.
55:30Preguntas o comentarios sobre estos
55:33árboles con mediana de tres.
55:41Ahora, todo esto se traduce finalmente,
55:44bueno, no es que se traduce, también me
55:48permite
55:50analizar métodos de ordenación porque a
55:54través del árbol de partición de un
55:56método de ordenación tipo Quicksort eh
55:59las dos cosas están conectadas.
56:01Así que esto lo vamos a a ver más
56:04adelante, pero
56:06a partir de esto eh yo lo que yo tengo
56:10sin buscarlo un análisis también del
56:12costo esperado de ordenación de
56:14Quicksort con la heurística de mediana
56:16de tres, en donde cada vez que yo quiero
56:20ordenar un conjunto, lo que yo hago
56:21escojo tres elementos al azar, escojo la
56:24mediana de los tres y ese es el que uso
56:26de eh pivote.
56:29Ya. Y y con eso puedo
56:37ordenar mucho más rápido que sin hacer
56:39esa ese pequeño trabajo al comienzo. Y
56:43la constante es 12 céntimos.
56:47El quicksort sin el quort original su
56:51costo de búsqueda es del orden de 2
56:56n * hn. Eh, 2n log n. fondo, eh, y con
57:03esto baja a 127 N por HN, el mismo 127
57:08se acarrea al quicksort.
57:11Ya, pero eh
57:18vamos al siguiente tema. ¿Qué piensa
57:20ustedes que viene después de esto?
57:25¿Cuál es la continuación natural de este
57:28de este estudio?
57:34A ver,
57:37¿qué qué piensan que podría venir
57:39después? Entonces, me dice, "Ya que
57:41pudimos resolver esto y lo resolvimos
57:44con bastante
57:48eh
57:50detalle, ¿no es cierto? Ah, o sea, esta
57:53fórmula que encontramos finalmente, que
57:54es el 127 HN + 1 - 75av
57:58es exacta, ¿no? No es una aproximación a
58:00la a la media, es el valor exacto.
58:05E,
58:08¿qué vendría después?
58:11A ver, a partir de esto te proponga
58:13alguna continuación de este estudio.
58:33General, ya que en clase resolvimos
58:35esto, ¿qué les podríamos dar de tarea?
58:51Ah, ¿alguna ide?
58:55[suspiro]
59:06Vamos a tratar de generalizar esto.
59:09Generalización
59:11de mediana de tres
59:15a
59:17¿Cómo se puede generalizar mediana de
59:19tres?
59:29Porque este método dice,
59:33antes de que antes de decidir quién va a
59:35ser raíz del subárbol, esperamos que
59:37haya un quórum de de tres elementos. Ahí
59:40elegimos la mediana de los tres. A ese
59:42lo ponemos de raíz y los restantes
59:44elementos quedan uno a cada lado, ¿no es
59:46cierto?
59:48Entonces, si no le dijera ya tratemos de
59:50generalizar esto,
59:53¿de qué manera lo podríamos generalizar?
1:00:09Hm.
1:00:33En lugar de elegir una pequeña muestra
1:00:36de tres elementos para encontrar su
1:00:38mediana, podríamos elegir una muestra
1:00:41más grande. una de cinco, mediana una de
1:00:44siete.
1:00:46Mientras más grande sea la muestra,
1:00:49el elemento que elegimos como raíz va a
1:00:51ser cada vez una mejor aproximación a la
1:00:54mediana del conjunto
1:00:56y por lo tanto la partición va quedando
1:00:58cada vez más balanceada.
1:01:00En el límite,
1:01:02eh, esto debiera tender a ser un árbol
1:01:05perfectamente balanceado. Ya, ahora eso
1:01:08a lo mejor no queremos porque es
1:01:09demasiado trabajo, ¿no es cierto?
1:01:11encontrar medianas de muestras muy
1:01:13grandes y a lo mejor no vale la pena eh
1:01:16aumentar mucho el tamaño de la muestra,
1:01:18pero a lo mejor sí vale la pena aumentar
1:01:19la muestra de tamaño tres a c, por
1:01:21ejemplo, o a siete. Entonces, eso es
1:01:23algo que podemos estudiar.
1:01:27Entonces, lo que vamos a hacer es vamos
1:01:29a generalizar el tamaño de la muestra a
1:01:32otros números impares. ¿Por qué impares?
1:01:33Para que la mediana esté bien definida,
1:01:35¿no es cierto?
1:01:37Entonces va a ser en lugar de ser la
1:01:39mediana de tres, va a ser la mediana de
1:01:412t + 1
1:01:44con t mayor o igual que 0.
1:01:47Fíjense
1:01:51con t = 1, esto sería mediana de 3, ¿no
1:01:55es cierto? Yo escojo, tomo una muestra
1:01:57de tamaño 3 y escojo la mediana. ¿Qué
1:02:01sería con t = 0?
1:02:04Es caso no lo mencionamos.
1:02:06¿Qué pasaría cuando t es igual a 0?
1:02:12¿Qué sería m1 en vez de m3?
1:02:30M1 significaría
1:02:33tomar una muestra de tamaño uno,
1:02:36elegir la medida de la muestra de tamaño
1:02:37uno, que por supuesto es el único
1:02:39elemento que hay y ese queda como raíz.
1:02:42O sea, tomamos un elemento al azar y se
1:02:44el que apareció va a ser raíz al tiro
1:02:46sin esperar a nadie más.
1:02:48Esos son los ABB comunicorrientes,
1:02:51los APB de busqua eninaria originales.
1:02:55Así es que esta familia de métodos
1:02:59incluyen
1:03:01con el caso T = 0 incluyen a los ABS
1:03:05originales y para t = 1 es mediana de 3
1:03:09y para t = 2 vendría a ser mediana de 5
1:03:11y así sucesivamente. Ya.
1:03:14Así que vamos a ver cómo lo podemos
1:03:18analizar esto.
1:03:21E
1:03:24y antes de eso,
1:03:26eh, examinemos de nuevo el caso T = 1,
1:03:29mediana 3,
1:03:32antes de entrar al caso general.
1:03:55Ahí lo que teníamos era un ciclo de esta
1:03:58forma, ¿cierto?
1:04:22Ya.
1:04:24Y esto ocurre con probabilidad 1 parido
1:04:27por n + 1.
1:04:30Mejor escriblo de otra manera.
1:04:34para que no haya dado ambigüedad.
1:04:37Esto es 1/o por n + 1. Esto va a ser 2
1:04:40par por n + 1.
1:04:42Esto va a ser 3 par por n + 1, ¿no es
1:04:45cierto?
1:04:47Y aquí yo pierdo una hoja de este tipo y
1:04:51gano una hoja de este tipo. Acá pierdo
1:04:53una hoja de este tipo y gano una hoja de
1:04:56este tipo. Aquí pierdo una hoja de este
1:04:59tipo
1:05:00y gano dos hojas de ese tipo, pero
1:05:03además un nivel más abajo, así que se
1:05:04multiplica por Z.
1:05:07Okay.
1:05:09Eh, ya no. Esto eh
1:05:15yo lo puedo
1:05:17modelar de la siguiente manera.
1:05:20Observemos
1:05:25el efecto
1:05:29de una inserción aleatoria.
1:05:45Eh,
1:05:50desde el punto de vista
1:05:58de una hoja
1:06:03de cada tipo.
1:06:06tipo 0
1:06:101 2. Ya. Entonces, supongamos que yo
1:06:14tuviera,
1:06:16recuerden que el vector
1:06:18es el número esperado de hojas de tipo
1:06:22cer, tipo uno, tipo dos, ¿ya? Pero
1:06:24supongamos que nosotros estuviéramos
1:06:25concentrados en observar solamente lo
1:06:27que pasa en una hoja de tipo cero
1:06:31y y solo una hoja solitaria de tipo cero
1:06:33que está en el nivel K.
1:06:38Ya podría haber quedado mejor dibujado,
1:06:40¿no es cierto?
1:06:44Entonces,
1:06:46supongamos que yo tengo una hoja de tipo
1:06:48cero en el nivel K y viene una inserción
1:06:50aleatoria. esa inserción aleatoria
1:06:54con probabilidad uno partido por n + 1
1:06:59eh
1:07:02cae exactamente encima de de esta hoja,
1:07:08¿cierto? Y con probabilidad 1 - 1/ por n
1:07:12+ 1 cae en alguna otra parte, ¿ya?
1:07:15Entonces, eh
1:07:19esto,
1:07:21esta hoja de tipo cer que está en el
1:07:24nivel k probabilidad 1 - 1 parido por n
1:07:29+ 1
1:07:33sigue siendo una hoja de tipo cero que
1:07:36está en el nivel k ya
1:07:42pero con probabilidad
1:07:451 parido por n + 1
1:07:49pasa a ser una hoja
1:07:52eh de tipo uno en el nivel k.
1:07:58Entonces, esos son los dos destinos que
1:07:59tiene esta hoja. Ya, si la inserción cae
1:08:03justo en esta hoja, eso en la siguiente
1:08:07generación, digamos, genera una hoja de
1:08:11tipo uno en el mismo nivel.
1:08:14En cambio, si eh esta inserción cae en
1:08:17cualquier otro lugar, lo cual ocurre con
1:08:19probabilidad 1 - 1/ por n + 1, esta hoja
1:08:22de tipo cer sigue siendo una hoja de
1:08:23tipo cer en el nivel K. Ya,
1:08:27¿qué pasa?
1:08:31Si yo tengo una hoja de tipo uno en el
1:08:34nivel K
1:08:37y viene una inserción, ¿qué hay en la
1:08:39siguiente generación?
1:08:42Esto es una hoja de tipo uno en el nivel
1:08:45K.
1:08:47Si la inserción ca en
1:08:51¿Cuál es la probabilidad que caiga justo
1:08:52aquí? La probabilidad que caiga justo
1:08:55aquí es 2 partidos por n + 1. Ya lo
1:08:58bueno ustedes ahí arriba, ¿no es cierto?
1:09:00La probabil de que justo ahí es 2
1:09:02partidos por n + 1. Y en ese caso en la
1:09:06siguiente generación lo que yo veo es
1:09:08una hoja de tipo 2 en el mismo nivel.
1:09:12Entonces aquí abajo escribo que 2 par
1:09:14por n + 1,
1:09:17ya eh
1:09:20una hoja del mismo nivel.
1:09:23y con la probabilidad complementaria 1 -
1:09:262/ por n + 1,
1:09:29esa hoja sigue estando en el nivel k la
1:09:31hija de tipo 2 y cer porque no afecta
1:09:35para nada las hojas de tipo cero.
1:09:37¿Y qué pasaría si yo tuviera
1:09:41una hoja que está en el nivel de tipo
1:09:43dos que está en el nivel K?
1:09:46Serían estas hojas ahí de tipo dos.
1:09:50Bueno,
1:09:54eh
1:09:56comprob vamos debajo hacia arriba. Esto
1:09:59la inserción puede caer en esa hoja o
1:10:01no. La probabilidad que caiga justo en
1:10:03esa hoja es 3 par por n + 1. ¿Ya?
1:10:06Entonces, con probabilidad
1:10:09complementaria 1 - 3/ por n + 1,
1:10:15esa hoja de tipo 2 sigue estando en el
1:10:18nivel K, no le pasó nada,
1:10:21pero con probabilidad 3 parido por n +
1:10:231,
1:10:26si la inserción cayó justo en esa hoja,
1:10:28en la siguiente generación eso genera
1:10:30dos hojas de tipo dos en el nivel k + 1.
1:10:34Entonces, esto ocurrió con probabilidad
1:10:363 ya partido por n + 1 y se generan dos
1:10:42hojas. Entonces, al multiplicar ya
1:10:43llevamos seis, o sea, aparece un seis.
1:10:50A ver,
1:10:566/ por n + 1
1:10:59por z a la k + 1,
1:11:04¿cierto? Porque esas dos hojas están en
1:11:05el siguiente nivel
1:11:07y cero aquí arriba.
1:11:10Ya.
1:11:12Bueno, esto
1:11:14se puede escribir como
1:11:34saquemos un Z a la capa afuera.
1:11:37Entonces, aquí
1:11:41está, perdón,
1:11:47hay un 100,
1:11:51que es ese uno de aquí,
1:11:57ese uno que se nos está dividido por n +
1:11:591, ¿no es cierto?
1:12:03Má
1:12:051/o por n + 1 por
1:12:10-1.
1:12:17Okay.
1:12:18Este yo lo puedo escribir de manera
1:12:20parecida.
1:12:23Z la cada aquí afuera.
1:12:27Entonces hay un
1:12:300
1:12:321 0
1:12:37+ 1/ n + 1 por
1:12:42-0
1:12:44-2.
1:12:50Ya. Y acá
1:13:01001
1:13:04+ 1/ por n + 1
1:13:100
1:13:126z
1:13:14importante el z - 3
1:13:19¿est
1:13:21y un Z acá aquí acá afuera.
1:13:24Y
1:13:30si ahora eh yo
1:13:35ahora esto era lo que pasaba a una hoja
1:13:37de un cierto tipo en un cierto nivel,
1:13:40¿ya? Entonces, si ahora yo cada uno de
1:13:44esto lo multiplico por el número de
1:13:45hojas de cada tipo,
1:13:48¿ya? Perdón,
1:13:52acá por el número de dos hojas de cada
1:13:55tipo, aquí, acá, acá y sumo ya lo que
1:13:59voy a tener es el vector a sub n de z. Y
1:14:04si hago lo mismo aquí y acá, aquí lo que
1:14:08voy a tener es una matriz de identidad.
1:14:11Y acá lo que voy a obtener es una matriz
1:14:13que tiene -1
1:14:15primera columna, 0 - 2 segunda columna,
1:14:1806z - 3 tercera columna. O sea,
1:14:21exactamente
1:14:22esta matriz que yo tengo acá,
1:14:26esa.
1:14:28Ya. Entonces, una manera de obtener esta
1:14:30matriz es ver,
1:14:37o sea, a partir de aquí, y me voy a
1:14:40saltar los los detalles, ah, pero a
1:14:45partir de aquí yo puedo escribir una
1:14:46ecuación que me dice que en la siguiente
1:14:48generación
1:14:51lo que yo voy a obtener es
1:14:54una matriz identidad que viene de esas
1:14:56tres columnas 1001001
1:15:01y luego 1/ido por n + 1. Y aquí voy a
1:15:04obtener una matriz donde está visto el
1:15:08efecto que tiene una inserción sobre
1:15:10cada tipo en la en la primera y esto se
1:15:14acá
1:15:16la hoja de tipo cero, yo pierdo uno y
1:15:18gano uno del nivel siguiente. Entonces
1:15:20eso dice acá -1.
1:15:24En la segunda
1:15:27yo pierdo una
1:15:30del tipo uno, pero con probabilidad dos
1:15:33participa.
1:15:35Y gano una en el nivel siguiente.
1:15:37Entonces eso va a ser un 0 - 2 y 2.
1:15:46-2 y 2 significa que yo pierdo una con
1:15:49probabilidad 2 par + 1 y gano una de
1:15:52tipo 2 con la misma probabilidad.
1:15:55Y en el siguiente y es el el que es más
1:15:57complicado es que yo pierdo una con
1:16:01probabilidad 3 parido por n + 1 y eso me
1:16:04da un -3 aquí abajo.
1:16:07Ya,
1:16:09pero gano una de tipo dos. En realidad
1:16:12gano dos de tipo dos. Entonces, eso va a
1:16:16ser un va a ser un
1:16:203 * 2, ¿no es cierto? 6
1:16:23y además z y eso en el tipo dos
1:16:32cer
1:16:34y todo eso está multiplicando a la sub
1:16:36de z.
1:16:38Ya. Entonces, esto me da otra manera de
1:16:42de generar esta matriz a viendo eh cómo
1:16:47se van combinando estos números aquí.
1:16:49Ah, cuánto aquí yo pierdo una, gano uno,
1:16:51pierdo uno, gano uno, pero con esa
1:16:52probabilidad, perdón, est marcando con
1:16:55el dedo y ustedes no veían. Hay que yo
1:16:57pierdo una, gano uno, con esa
1:16:58probabilidad. Pierdo una, gano uno con
1:17:01esa probabilidad. Entonces,
1:17:03pierdo uno
1:17:06y gano dos. con esa probabilidad.
1:17:09Entonces, eso se multiplica el 3 por el
1:17:102 y además el siguiente nivel, por lo
1:17:12tanto se multiplica por Z. Ya. Y eso es
1:17:15lo que me da la última columna. Acá
1:17:22se entiende ya. Entonces, ahora, ¿a qué
1:17:25viene todo esto? ya que en el caso
1:17:29general
1:17:48con hojas de tipo cero. En vez de poner
1:17:50puntito dentro, voy a poner el número.
1:17:53Entonces
1:17:55llega uno y ahora tengo una objetivo
1:17:58uno, ¿cierto?
1:18:00Y esto sigue ya
1:18:04sigue sigue sigue. ¿Hasta cuándo?
1:18:07hasta que eh yo tengo aquí hojas de tipo
1:18:12t - 1.
1:18:16Es una hoja con t- un puntito en su
1:18:18interior,
1:18:21luego una hoja de tipo t,
1:18:24etcétera. Ah, siempre es que llega un
1:18:27dato, se inserta en la hoja y la hoja
1:18:30pasa a ser del nivel siguiente, pero
1:18:32siempre del mismo nivel. ¿Y esto hasta
1:18:34cuándo sigue? Ah.
1:18:36Como esto es una urística [resoplido]
1:18:38de
1:18:40eh mediana de 2+ 1, esto va a llegar
1:18:43hasta que en algún momento tengamos 2 T
1:18:47datos
1:18:49dentro de la hoja. 2T
1:18:52y cuando llegue el siguiente
1:18:55ya se
1:18:58eh con eso se completa el cuer 2 + 1,
1:19:02¿ya? Y ahí yo puedo elegir la mediana.
1:19:05Entonces va a quedar ahí va a quedar
1:19:07elegida la mediana
1:19:10y
1:19:13a la izquierda van a quedar T elementos
1:19:16y a la derecha van a quedar los otros T
1:19:18elementos. Sumado los T de la izquierda,
1:19:21los T de la derecha y el y el de la raíz
1:19:24me da los dos t + 1. Y con eso yo estoy
1:19:28de vuelta y el ciclo se cierra aquí.
1:19:33Entonces, todo lo que había aquí al
1:19:34inicio
1:19:36son hojas transcientes.
1:19:40Después que paso a ese nivel, solamente
1:19:42vamos a ver hojas de estos tipos, desde
1:19:44el T hasta el 2 T. Desde el T hasta el
1:19:462T. ¿Sí?
1:19:50Y
1:19:51bueno, y ahí vamos a poder hacer las
1:19:53mismas anotaciones que hicimos antes.
1:19:59Aquí pierdo una, gano una. Pierdo una,
1:20:06gano uno, ¿cierto? Pierdo uno, gano uno,
1:20:11pierdo uno, etcétera, gano uno, pierdo
1:20:15uno y acá gano
1:20:19dos
1:20:21en el siguiente 2 Z.
1:20:25Y aquí las probabilidades son 1/ n + 1.
1:20:30Acá la probabilidad es 2/ por n + 1. Ya.
1:20:35Este va a ser t/ido por n + 1.
1:20:39Este otro va a ser t + 1/ n + 1.
1:20:44Ya este va a ser 2t + 1
1:20:49divido por n + 1.
1:20:52Entonces, a partir de ahí vamos a poder
1:20:56escribir la
1:20:58generar la matriz H,
1:21:01¿ya?
1:21:02Eh,
1:21:05pero creo que eso mejor lo voy a dejar
1:21:06para la clase que viene, ¿eh? Entonces,
1:21:09vamos a ver
1:21:13cómo podemos a partir de aquí escribir
1:21:15la matriz H, que va a ser lo mismo que
1:21:18hicimos aquí en realidad, ¿no es cierto?
1:21:20Ya. Eh,
1:21:23se fijan ustedes que todas las e
1:21:29todas las columnas son de la forma -1 -2
1:21:332. Si si esto siguiera sería -3 -4 + 4 y
1:21:37así todo eso por la diagonal y la
1:21:38subdiagonal
1:21:41y al final final en el rincón abajo
1:21:44extremo derecho.
1:21:46Ahí recién eso me genera algo que está t
1:21:50niveles antes, ah, que es este caso
1:21:53cuando el 2 T se transforma en dos hojas
1:21:55de tipo T en el nivel siguiente.
1:21:58Así que en realidad no va a ser tan
1:21:59complicado,
1:22:00pero como digo, mejor lo hacemos en la
1:22:02clase que viene. Así que por hoy día
1:22:04quedaríamos hasta aquí.
1:22:12Entonces
1:22:16eso
1:22:23y que tengan una muy buena semana.