Full transcript
0:00Muy
0:17buenos días. Vamos a a comenzar esta
0:20clase.
0:32Okay. En la clase pasada introdujimos la
0:38estructura de datos que resulta al
0:41aplicar a los árboles de búsqueda
0:44binaria
0:46la eurística de mediana de tres.
0:55Esta es una turística de balance local
0:59que no garantiza que
1:02los árboles no puedan
1:05eh desbalancearse mucho, pero sí vamos a
1:08ver que hace que en promedio andén
1:10bastante mejor que un árbol de búsqueda
1:12binaria sin esta modificación. Ah
1:17que vimos fue que e
1:20en el borde del árbol, ¿no es cierto?
1:24Tenemos
1:27tenemos aquí nuestro estructura y acá en
1:31el borde donde antes solo teníamos hojas
1:35comunes y corrientes, ahora también
1:37vamos a tener hojas que tienen un dato
1:39en su interior y otras hojas que tienen
1:42dos datos en su interior. Ya vamos a
1:45decir que eh una hoja es de tipo J
1:49cuando tiene J datos en su interior.
1:52Entonces,
1:54la evolución
1:57de estas hojas en el borde eh son de que
2:01cuando yo tengo una hoja vacía
2:05y llega un dato, ese dato se almacena en
2:08su interior.
2:10Cuando yo tengo una hoja que tiene un
2:12dato en su interior y llega otro,
2:14eso se agrega
2:17y cuando llega el siguiente, con eso ya
2:20tengo un quórum de tres. Y con un quórum
2:22de tres yo puedo elegir a la raíz que va
2:24a ser la mediana de los tres. Entonces
2:28ahí la raíz
2:30eh ya quedan en su lugar definitivo, no
2:32la vamos a tocar nunca más. Y a cada
2:35lado quedan los otros dos elementos. A
2:38la izquierda el que es menor que la
2:40mediana y a la derecha el que es mayor
2:41que la mediana. Y con eso estamos de
2:43vuelta aquí. Ahí se cierra el ciclo, ¿no
2:46es cierto? Entonces, las hojas vacías
2:48son super transientes, existen al
2:50principio, luego se transforman en hojas
2:52de tipo uno y de ahí para adelante nunca
2:55más vemos hojas de tipo cero, ¿no? Así
2:58que de alguna manera nuestra solución va
3:00a tener que eh incorporar esa. Y lo otro
3:05que ocurre es que antes ya habíamos
3:08visto que la probabilidad de que una
3:10inserción caiga en una hoja vacía es 1
3:14parido por n + 1.
3:16Pero cuando las hojas ya no son vacías,
3:20cuando hay una hoja que tiene un dato en
3:21su interior,
3:23ya, ese esa hoja con un dato en su
3:27interior es una forma de visualizar lo
3:29que sería un pequeño arbolito que tiene
3:32una raíz y dos hojas a cada lado. Por lo
3:36tanto, la probabilidad de caer aquí es
3:37la suma de la probabilidad que en
3:39cualquiera de esas dos hojas
3:40tradicionales. Ah, o sea, esto va a ser
3:422 par por n + 1. Y de la misma manera,
3:46la probabilidad de caer en una hoja de
3:49tipo 2
3:51va a ser 3 parid por n + 1. ¿Ya? Y a
3:54partir de ahí escribimos ecuaciones que
3:58eran
4:01nos dicen cuál es la cuál es el número
4:03esperado,
4:05ya la el a sub n k de tipo jado
4:17de hojas
4:20de tipo J
4:23en el nivel K.
4:28en un árbol
4:33con n llaves,
4:36¿no? Entonces, aquí están los niveles.
4:39Este es el nivel cero, nivel uno, nivel
4:43dos y así sucesivamente.
4:46Entonces, a las hojas de tipo cero que
4:50existen después de una inserción son las
4:52mismas que habían antes a su n de tipo
4:55cero, menos las que se pierden. ¿Cuándo
4:58yo pierdo una hoja? Cuando cae una
5:00inserción justo en una hoja de tipo
5:01cero, en ese nivel, ¿no es cierto? Eh, y
5:04en ese caso yo pierdo una hoja y esto
5:07ocurre con probabilidad 1 parido por n +
5:081
5:10ponderado por el número de hojas de tipo
5:12cero que hay en ese nivel. Ya. Ahora,
5:15esto es eh esta es una ecuación super
5:17general.
5:18En la práctica solo se va a aplicar al
5:20nivel cero porque ahí es donde está la
5:23única hoja de tipo cero que hay al
5:24inicio y después nunca más aparecen.
5:26Pero esta la esta es la ecuación general
5:29que hay que escribirla así para que sea
5:31compatible con las otras ecuaciones que
5:34sí se aplican a todos los niveles.
5:37Entonces las hojas de tipo uno son las
5:40mismas que habían antes,
5:43¿ya? menos las que se pierden y más las
5:47que se ganan. Eh, cuando yo pierdo una
5:50hoja de tipo uno, cuando cae una
5:53inserción justo en una hoja de tipo uno
5:55y ahí pierdo una hoja y eso ocurre con
5:58probabilidad 2 parido por n + 1
6:00ponderado por el número esperado de
6:03hojas de tipo uno en ese nivel. ¿Cuándo
6:06yo gano hojas de tipo uno?
6:09Yo gano una hoja de tipo uno.
6:13En este caso, en realidad gano dos aquí.
6:16Cuando acabe una inserción en una hoja
6:19de tipo dos, yo gano dos hojas de tipo
6:22uno en el siguiente nivel, ¿cierto?
6:25Entonces eso va a ser
6:29eh yo gano dos hojas
6:32y la probabilidad que yo ocurra es 3 par
6:34por n + 1 porque esa es la probabilidad
6:36de caer en una hoja de tipo dos.
6:38ponderado por el número esperado de
6:40hojas de tipo todos
6:44que hay, pero en el nivel anterior,
6:47¿cierto?
6:48Porque las hojas que aparecen, si yo
6:50quiero saber cuántas hojas aparecen en
6:52el nivel K, esa hoja de tipo dos que fue
6:55donde cayó la inserción tiene que estar
6:58un nivel más arriba, que es nivel menos
7:00un y la otra y el otro caso en que yo
7:03gano hojas de tipo uno es cuando una
7:05hoja de tipo cero muta y se transforma
7:07en una hoja de tipo uno y ahí gano una,
7:10¿no es cierto? una con la probabilidad
7:131/o por n + 1
7:16y ponderado por el número de hojas de
7:18tipo cer0 que hay en ese nivel.
7:20Y las hojas de tipo dos.
7:25Hojas de tipo dos nuevamente son las
7:28mismas que había antes,
7:33menos las que se pierden, más las que se
7:34ganan. ¿Cuándo yo pierdo una hoja de
7:38tipo dos? Bueno, cuando cae la inserción
7:40justo en una hoja de tipo dos y ahí
7:42pierdo una.
7:43Entonces yo pierdo una hoja con
7:46probabilidad 3 par n + 1
7:50por a n coma k de tipo 2.
7:55Y cuando gano hojas de tipo dos, cuando
7:58la inserción cae en una hoja de tipo uno
8:03aquí y esa hoja muta y se transforma en
8:05una hoja de tipo dos. Ahí yo gano una
8:07hoja de tipo dos, ¿no es cierto? En el
8:08mismo nivel. Entonces en ese caso ya no
8:11hay k - 1, ¿no es cierto?
8:14Entonces, esto sería gano eh una hoja
8:19eh con probabilidad 2 par n + 1
8:24ponderado
8:26por el número esperado de hojas que hay
8:28en ese nivel que sean de tipo uno.
8:33Y aquí tengo mi sistema de de ecuaciones
8:37de recurrencia. Hm. Que necesito
8:41resolver. Okay. Eh,
8:46¿cómo las voy a Ah, bueno, y lo otro que
8:50hay antes de terminar esto es la
8:54condiciones iniciales. O sea, ¿qué pasa
8:56cuando n es igual a 0? ¿No es cierto?
8:58Cuando n = a 0, el número de hojas
9:04de tipo cero que hay en el nivel K,
9:07bueno, hay una hoja de tipo cero en el
9:09nivel cero
9:12y no hay más hojas de tipo cero en
9:14ninguna otra parte, por lo tanto, esto
9:16es e n = 0,
9:20la función indicatriz, ¿ya? Y las hojas
9:23de tipo uno
9:27que hay en cualquier nivel cuando hay
9:29cero llaves y las hojas de tipo dos que
9:33hay en cualquier nivel cuando hay cero
9:36llaves son cero.
9:39Porque al principio lo único que hay es
9:40una hoja tipo cero, nada más. Ya. Así
9:42que ahí tengo mis condiciones iniciales.
9:44Entonces, lo que voy a hacer es voy a
9:47introducir función generatriz en la
9:49variable K.
10:10en la variable K. Entonces, ¿cómo va a
10:12quedar eso? Eh,
10:16la
10:21aquí va a quedar un a sub n + 1 de tipo
10:240 de z. Acá a sub n de tipo 0 de z. Acá
10:29-1 parido por n + 1 * a sub n de tipo 0
10:33d z y así sucesivamente. La única parte
10:36donde ocurre algo eh distinto es aquí,
10:40porque aquí como hay k - 1 al meter
10:42función generatriz lo que va a quedar es
10:442z, ¿no es cierto? Aparece un z por un k
10:47- 1. Así es que aquí vamos a tener
10:50nuestras ecuaciones,
10:54¿ya? que van a ser entonces
10:58eh
11:01a sub n + 1 de tipo 0 de z.
11:08Ya va a ser a sub n de tipo 0 de z
11:15menos
11:181 * 1/ n + 1
11:22por a sub n de tipo 0 de z.
11:28A sub n + 1 tipo 1 de z
11:32va a ser a sub n de tipo 1 de z.
11:38[suspiro]
11:39Eh,
11:41y aquí menos lo que se pierde más lo que
11:43se gana, ¿no es cierto? Todos ellos
11:45están divididos por n + 1. Así es que eh
11:48pongamos el tiro del n + 1 afuera. 1
11:51paro por n + 1.
11:54Factor de, ¿ya? Entonces va a quedar eh
11:59-2.
12:01A ver, ¿en qué orden lo ponemos?
12:04Pongamos 0 1 2. Entonces no va a ser
12:07Vamos, ya vamos primero la de tipo cero.
12:10Eso va a ser eh
12:131 por a sub n de tipo 0 z.
12:18Ya, de tipo 1 va a ser -2
12:33y las de tipo dos van a ser más 6.
12:45Ahí.
12:47Ya. Y a sub n + 1 de tipo 2 de z
12:53va a ser a sub n de tipo 2 de z
12:57+ 1 por 1. A ver,
13:041/ por n + 1 factor de
13:09eh la de tipo uno va a ser dos
13:15a su n. de tipo 1 de z
13:19y -3
13:24a su n de tipo 2
13:27de z.
13:33Perfecto. Y ahora
13:36estas tres ecuaciones las vamos a
13:38escribir de manera vectorial.
13:42Definamos
13:49el vector
13:51eh a sub n
13:54vector de tipo z,
13:59que va a ser el a n de tipo 0 de z,
14:04a su n de tipo 1 de z,
14:07a su n de tipo 2 de z. Entonces ahí
14:11tengo un vector, ¿cierto?
14:14Y con eso yo puedo escribir entonces
14:17aquí
14:19todo esto a la izquierda es el vector
14:22que acabo de definir, pero para n + 1,
14:23¿no es cierto? Acá va a estar el mismo
14:25vector
14:26y acá va a haber eh
14:30estas combinaciones lineales de de las
14:32componentes del vector. Pero eso lo
14:34puedo escribir a través de un producto
14:36matricial, ¿no es cierto? Entonces va a
14:38quedar así.
14:41A la izquierda va a quedar el a sub n +
14:441
14:46z vector
14:49y a la derecha va a quedar el a sub n
14:52vector de zido
14:57por n + 1, ¿cierto? Y aquí va a haber
15:01una matriz
15:04que va a estar multiplicando al a sub n
15:06de z vector.
15:10Entonces, ¿qué va a haber en esta
15:14matriz?
15:16A ver,
15:20aquí. Ya. Entonces, en la primera línea
15:23lo único que hay es un -1 multiplicando
15:24a la a la componente cero del vector,
15:27¿no es cierto? Entonces, aquí va a haber
15:29-1 0.
15:32En la segunda línea va a haber eh 1 - 2
15:376.
15:40Ah, aquí cometí un error. Dije, se los
15:44dije antes y después se me olvidó y
15:46nadie me ha corregido. Nadie me ha
15:48corregido. Ya. ¿Qué es lo que faltó
15:52en hint? En la segunda ecuación faltó
15:55algo super importante.
16:04Recuerde, de hecho, en la casa pasada se
16:05me había olvidado.
16:07Ahí dice que -1, por lo tanto, al meter
16:09función ge va a aparecer un z, ¿no es
16:11cierto?
16:13Entonces no va a ser seis, por eso va a
16:14ser 6.
16:16Super importante.
16:21Pongámoslo en otro color rojo. Que se
16:24note que faltaba 6 Z. Ahí
16:32están de acuerdo. Sí.
16:35Ya. Entonces acá va a ser e
16:411 - 2 6z.
16:47Y en la última línea eh va a ser 0
16:532 - 3.
16:58Eso. Okay.
17:01Ya. Llamemos a esto la función HZ,
17:06digamos, ¿no?
17:11Entonces yo lo puedo escribir así. Lo
17:14puedo escribir como que a sub n + 1
17:18vector de z
17:21igual a la identidad
17:25+ 1/ por n + 1 * h dez
17:31y todo eso multiplicado por a sub n
17:34vector de z
17:37y ah y yo tengo la condición inicial
17:41sub n,
17:43perdón, no es a sub n, a sub0.
17:47A sub de z vector es.
17:58Esta es la ecuación que vamos a querer
18:01eh resolver para encontrar
18:06el número esperado de eh
18:12hojas de cada tipo por nivel. Okay,
18:17vamos bien. Hasta aquí se entiende todo
18:19lo que hemos hecho hasta ahora. Sí. ¿Den
18:21alguna señal de vida?
18:24¿Sí
18:25o no?
18:27Sí, sí.
18:29Okay, perfecto. Entonces, ahora tengo
18:31que ver. Ah, bueno, pero una última cosa
18:34antes de entrar a ver cómo resolvemos
18:36esta
18:37esta ecuación,
18:39ya eh
18:42lo que nosotros queremos, por ejemplo,
18:45es estudiar el costo esperado de
18:46búsqueda infructuosa. ¿Ya? Entonces,
18:50el costo esperado de búsqueda
18:51infructuosa, ¿cómo es una búsqueda
18:52infructuosa? Yo parto desde la raíz y
18:56bajo y bajo, bajo hasta que llegó una
18:57hoja y el número de niveles que que bajé
19:01es el costo, ¿no es cierto? Pero eso es
19:04cuando yo cuando esa hoja está vacía.
19:08Eso fue lo que hicimos antes al estudiar
19:09los ABB. Pero si ahora dentro de esa
19:11hoja hay un dato, mi búsqueda todavía no
19:14ha terminado, ¿no es cierto? Tengo si
19:15hay un dato, tengo que parar contra ese
19:17dato y como va a ser una búsqueda
19:19infructuosa tampoco va a ser ese y voy a
19:21bajar un nivel porque esta hoja con un
19:24dato en su interior representa es una
19:26forma de visualizar lo que sería un
19:27pequeño arbolito que tiene una una raíz
19:30y dos hojas colgando, ¿no es cierto? Ah,
19:32entonces al interior de la hoja hay ese
19:35pequeño arbolito y yo tengo que hacer
19:37una comparación extra. Entonces, cuando
19:39yo llego a esa hoja, todavía no
19:41terminado, tengo que hacer una
19:42comparación extra. Por lo tanto, voy a
19:43tener que multiplicar por Z. ¿Ya? ¿Y eso
19:46con qué probabilidad? E, bueno, en
19:48realidad más que por Z, por dos
19:52[resoplido] Z, porque yo puedo ir a la
19:53hoja izquierda o a la hoja derecha. Ya
19:56la hay dos casos en donde yo llego ahí y
20:01cuando es una hoja que tiene dos datos
20:02en su interior, al al número de niveles
20:06que yo he tenido que bajar hasta ahora,
20:08tengo que sumarle una comparación extra,
20:12¿ya?
20:13Eh, que si ese ese
20:17a lo que estoy hablando es se refiere a
20:20esto. A ver, eh esta hoja vacía,
20:24es una hoja vacía. Ya esta hoja con un
20:28dato en anterior, si yo la mirara con
20:30una lupa, lo que vería adentro es esto.
20:38Ya.
20:40Y y esta hoja con dos, si yo la mirara
20:44con una lupa,
20:46lo que vería sería algo así como esto.
20:57Entonces,
20:59cuando yo llego a una hoja de tipo cero,
21:00estoy listo. Cuando yo llego a una hoja
21:02de tipo uno, todavía tengo que seguir y
21:04terminar en esta hoja en esta hoja. O
21:05sea, tengo dos
21:08maneras de continuar y eh y eso le
21:11agrego un costo de uno. Entonces, yo voy
21:13a tener que multiplicar por 2 Z en este
21:16caso para sumarle uno en en dos casos. Y
21:20acá si llego hasta aquí de partida tengo
21:24que que multiplicar por Z cuando me voy
21:27al lado izquierdo, pero tengo que
21:29multiplicar por Z cuadrado cuando me voy
21:30al lado derecho y ahí tengo dos casos.
21:32Entonces sería z + 2z². Ese es un costo
21:35extra. ¿Ya? Eh, entonces la
21:40la probabilidad,
21:44la función
21:47de probabilidad
21:49del costo de búsqueda infructuosa, que
21:51es lo mismo que el costo de inserción
21:57de búsqueda infructuosa
22:04es,
22:06llamémoslo
22:11pz.
22:13¿Ya? Entonces, primero tengo que ver eh
22:16todas las maneras como yo puedo llegar a
22:18una hoja. ¿Okay? Entonces, yo llego a
22:21una hoja eh es posible que yo llegue a a
22:25una hoja de tipo cero,
22:30¿ya? Pero también es posible que yo
22:32llegue a una hoja
22:35de tipo
22:371 de Z. Y en ese caso tengo que
22:41multiplicar por 2 Z
22:45para sumarle uno en dos casos.
22:50Y si yo llego
22:55a una hoja
22:58de tipo dos,
23:01en ese caso tengo que sumar
23:05uno en un caso
23:10y dos en dos casos.
23:13Pues eso es 2 z cuad. Y con eso tengo ya
23:16cubierto la totalidad de las hojas que
23:18son n + 1. Entonces para ver el costo
23:21promedio, el costo en realidad el costo
23:23esperado
23:25tengo que dividir por n + 1.
23:30Profe,
23:30sí.
23:32¿Por qué es 2 z² y no solamente z cuado?
23:36Ahí no he entendido eso
23:37porque tengo dos hojas aquí, una aquí y
23:41otra acá.
23:43Entonces si yo yo puedo llegar aquí y
23:44puedo llegar acá, por eso es 2 por Z
23:47cuad.
23:49La misma que aquí fue dos porque yo
23:52podía llegar a la hoja izquierda o a la
23:53hoja derecha. Ese es el mismo motivo de
23:55S2. Ya.
23:57Ah, ya ya sé si entiendo.
24:00Entonces esto último también lo puedo
24:01escribir de manera matricial
24:04o vectorial, como quiera. Ah, o sea, P
24:06sub N de Z.
24:09Puedo decir que es 1 paro por n + 1
24:14por un vector fila c
24:18multiplica al vector columna a su n de z
24:23donde
24:27c de z
24:30vector 1 2 z
24:35+ 2 z² cuadrado.
24:39Ahí está. Ya ahí tengo mi problema
24:43completo. Okay.
24:47Eh,
24:49ahora
24:51hay que resolver esto, ¿no? Entonces,
24:54para resolver esta ecuación,
25:00esta ecuación no es difícil de resolver.
25:03Eh, solo que la forma de la solución no
25:06puede pillar desprevenido, pero que es
25:09que es fácil de resolver es fácil porque
25:11esta es una ecuación
25:14eh en que para pasar de nen + 1 se
25:18multiplica por algo. Entonces, es
25:20superfácil de desenrollar, ¿cierto?
25:23eh
25:26a sub n va a ser esto con n aquí por el
25:29a sub n - 1. Entonces n -1 va a ser esto
25:33mismo, pero ahora para n - 1 eh
25:36multiplicado para la sub n - 2 y así
25:38sucesivamente ah hasta llegar a la suber
25:41entonces va a ser una un producto de de
25:44estos términos. ¿Ya? Entonces eh lo que
25:49queremos ver es qué tipo de solución
25:50vamos a encontrar. Pero la forma de
25:53encontrar esas soluciones es superfácil.
25:54Desenrollando la ecuación nada más. No
25:56tiene mayor complicación.
25:59Pero como les digo, lo que nos puede
26:01complicar un poco es el tipo de de
26:03solución que vamos a encontrar.
26:04Entonces, para resolver esta ecuación
26:07como precalentamiento,
26:16ya vamos a resolver la versión escalar.
26:22No, la versión vectorial.
26:33Ya. Eh, ¿cuál sería la versión escalar?
26:36sería algo que me dice que a sub n + 1
26:41de zo,
26:44no identidad, sino que uno. Eh, y en vez
26:47de la función h pongamos un digamos un
26:49lambda, que es un escalar.
26:51Después van a entender por qué le estoy
26:53poniendo lambda
26:56por el aun de z, ¿no es cierto? Y y el a
26:59n vector, es una función escalar. y con
27:03a sub0 de z = 1. Ya, esa sería la la
27:08versión escalar de esta ecuación.
27:10Entonces, eh, ¿cómo se
27:13cómo se resuelve esto desenrollando?
27:16Entonces, escribo desenrollando.
27:24Ya, eh, voy a escribir la para su n
27:29que es e de z.
27:33que va a ser entonces 1 + lambda de z
27:38partido por n por a sub n - 1 de z. Ya,
27:45antes de seguir adelante
27:48me conviene esto escribirlo como poner
27:53el nominador
27:56común, por lo tanto, esto va a ser
27:58lambda de z + n, ¿cierto?
28:02en el numerador. ¿Ya?
28:06Okay. Entonces, ahora con eso voy a
28:09seguir desenrollando.
28:11Entonces, aquí me va a quedar lambda de
28:14z + n parido por n
28:18desenrollar una vez más va a ser lambda
28:21de z ahora más n - 1 parido por n - 1
28:27por a su n - 2, ¿cierto?
28:31Y si seguimos así,
28:34eh, va a ser lambda de z + n parido por
28:40n
28:42lambda de z + n - 1 partido por n - 1 ta
28:48ta ta t hasta cuál.
28:52Fíjense ustedes que
28:55este subíndice que hay aquí, el n - 2,
28:58uno menos que este otro o el de acá es
29:01uno más que, ¿no es cierto?
29:03Y aquí también es uno más ya que ese.
29:08Entonces, si yo sigo desenrollando,
29:09desarrollando hasta que llego a que en
29:11su índice de acá es cero, eso quiere
29:14decir que este de acá va a ser uno y
29:15este de acá también va a ser uno. O sea,
29:18de desenrollar y desenrollar vamos a
29:20terminar llegando hasta lambda de z + 1,
29:27perdón, ese último cerrado y uno,
29:32¿cierto? hasta ahí.
29:34Entonces, ahora si yo esto lo leo de
29:38derecha a izquierda, aquí va a ser
29:40lambda de z + 1, lambda de z + 2 hasta
29:42lambda de z + n. O sea, eso es un
29:50eso es un lambda de z
29:54+ 1
29:56a la n ascendente, ¿no es cierto?
30:01Y abajo es más fácil, pues 1 * 2 hasta
30:04por n hasta n es n factorial.
30:09Okay.
30:12Y si ustedes se acuerdan eh de los
30:16coeficientes binomiales simétricos, esto
30:18no es otra cosa que el coeficiente
30:20binomial simétrico lambda de z
30:25coma n.
30:27Coeficiente de binomio simétrico.
30:30Escribámoslo ahí.
30:39Así que la solución,
30:41ah, perdón, se me olvidó una cosa, por a
30:43sub
30:46z ahí, ¿no? C es el último el
30:48desarrollar, pero sub de z es un por eso
30:52es que acá no aparece. Pongamos ahí para
30:56que nadie se pierda leer esto. Esto es
30:59un ya.
31:04Así que la solución es s simple. La
31:06solución de esta ecuación es un
31:08coeficiente binomial simétrico.
31:11Ahora volvamos al caso vectorial.
31:16Ah, todavía no. Estoy mirando mi apunte.
31:18Hay un par de cosas más que que queremos
31:21que que que es útil ver antes de ver el
31:23caso vectorial. Pero adelantándome a mí
31:26mismo, el caso vectorial, la solución
31:30eh, bueno, ¿cuál va a ser la diferencia?
31:32No es cierto aquí va a haber una
31:34identidad, acá en vez de una escalar
31:37lambda de z va a haber una función h
31:39dez.
31:41Eh, pero el resto es lo mismo. Por lo
31:44tanto, la solución va a ser de ese tipo,
31:47pero donde en vez de decir h de z,
31:49lambda de z va a decir h dez.
31:52O sea, va a ser un coeficiente binomial
31:56simétrico
31:58donde uno de los dos argumentos es una
32:00matriz. Ah, eso no lo habíamos visto
32:02hasta ahora.
32:04Eh, porque partimos con coeficientes
32:06binomiales simétricos en que los dos eh
32:09argumentos eran enteros, ¿cierto? Un i
32:13com j. Eh, después vimos que eso se
32:16podía generalizar y que uno de los dos
32:17podía no ser entero, lambda de z en este
32:19caso. Pero ahora lo vamos a generalizar
32:21y vamos a ver que uno de los dos
32:22argumentos puede ser una matriz. Ah, los
32:25voy a dejar que ustedes mediten un poco
32:27sobre qué puede significar eso mientras
32:29seguimos avanzando, pero vamos a llegar
32:32a ese punto. Ah.
32:35Muy bien. Eh, y ya, ¿qué era lo que se
32:38me estaba quedando en el tintero? Eh,
32:42es que e el cálculo de momento
32:48eh para poder calcular la media, la
32:51varianza, ¿no es cierto?
32:53El cálculo
33:03requiere
33:07calcular derivadas
33:12de x n.
33:18Eso requerimos eso porque después por la
33:20regla de la cadena yo tomo la derivada
33:21del otro, pero tengo que partir
33:23derivando esto, ¿no es cierto? Entonces,
33:26¿qué es eh qué es xa n?
33:31Ya, bueno, eso significa de a de x de x,
33:36¿no es cierto?
33:38y eso es de adx
33:42de x + 1 a la n ascendente
33:46partido por n factorial
33:49y eso es 1 parido por n factorial
33:52de de x de la pitatoria
33:57ya para 1 menor o igual que j menor o
33:59igual que n de x + j.
34:03Entonces, llegamos finalmente. Ah,
34:05bueno, y la derivada de eso.
34:09Ah, bueno, está puesta ahí la derivada
34:10de eso. Eh, entonces llegamos a la
34:12derivada de un producto, ¿ya? Eh, ¿cómo
34:15se dería un producto? Si si el producto
34:17fuera f* g, sería f prima gg, ¿no es
34:23cierto? Pero cuanto el producto no es eh
34:28con un número fijo de términos sino que
34:31o de factores en realidad. eh sino que
34:33es F1 * F2 hasta por Fn, ¿no es cierto?
34:37Que vendría a ser esa sería la forma de
34:39esto. ¿Cuál es el el producto de una
34:42pitatoria de de un largo variable? Ya,
34:46eso es difícil de escribir porque lo que
34:49hay que hacer es que en cada una suma de
34:52términos, ¿no es cierto?, donde cada uno
34:54de los términos tiene exactamente una de
34:56las funciones derivadas y todas las
34:57demás en su forma eh original, ¿ya? Y
35:01eso, como les digo, es difícil de
35:04escribir en forma cerrada. Ah. Eh, pero
35:10pero tenemos un pequeño truco para para
35:12eso. Ah, tenemos que ver qué pasa con la
35:15derivada de un producto.
35:27La derivada de un producto. Si yo tengo
35:30fg al cual quiero derivar, ustedes saben
35:32que eso es f prima gg.
35:36Ya. Y como les decía, el problema que
35:38eso tiene es que es difícil de
35:39generalizar cuando en vez de ser el
35:41producto dos factores es el producto de
35:44n factores. ¿Ya? Eh, pero eh el truco
35:48que me salva es el siguiente. Eh, en
35:51cada uno de estos términos yo puedo eh
35:55multiplicar por el factor que falta. Por
35:57ejemplo, el primero, como no aparece la
36:00función f, sino que derivada, yo puedo
36:03multiplicar por f y dividir por f. En el
36:07segundo, yo puedo multiplicar por g y
36:08dividir por g. ¿Y qué es lo que gano?
36:11Que al hacer eso, yo completo el
36:14producto total y lo puedo después
36:16factorizar hacia fuera. O sea, esto lo
36:18puedo escribir así. FG
36:21por F prima parido por F más G prima
36:25parido por G.
36:29Es lo mismo, ¿no es cierto? Chequeen
36:31mentalmente ahí que
36:34esa identidad está correcta, ¿no es
36:36cierto? Pero la gracia entonces que
36:38entonces el FG yo lo puedo sacar para
36:39fuera completamente y lo que queda
36:42adentro es una sumatoria fácil de
36:44escribir. Ah, en el caso general,
36:53si yo tengo una pitatoria de funciones
36:56F, ¿ya? y quiero derivarla.
37:01Eso es la misma pitatoria de funciones
37:04fi multiplicado por una sumatoria
37:08de las funciones fi prima partido por
37:10fi.
37:14Y eso eso sí lo puedo escribir y
37:16trabajar con e con con esto sin
37:18problema. ¿Ya? Entonces, en nuestro
37:22caso,
37:27ya el dx
37:31de la pitatoria de x + j
37:36para 1 menor o igual que j menor o igual
37:38que n, que es nuestro coeficiente
37:40binomial simétrico, ¿no es cierto?
37:43E por lo menos el numerador,
37:45¿ya?
37:46Eh,
37:48la derivada de eso va a ser la el mismo
37:52producto producto de x + j
37:56menor o igual que j menor o igual que n,
37:59¿no es cierto? Ese x para afuera por
38:01esta sumatoria
38:04para 1 menor o igual que j menor igual
38:06que n. Y en esa sumatoria,
38:09en cada término, yo voy a poner en el
38:12numerador la derivada.
38:16de esto y en el denominador
38:20esto mismo. Entonces, ¿cuánto es la
38:22derivada de x + j? Es 1. Y y eso dividió
38:26por x + j. Que va a quedar así. 1
38:32dividido por
38:34x + j.
38:46Eh, por lo tanto,
38:49eso implica que el
38:53x coma
38:57n derivado, yendo ahora al coeficienteal
39:02simétrico, lo que le falta al anterior
39:04es dividir por n factorial, ¿ya?
39:08Entonces va a ser
39:10eh la pitatoria
39:14de x + j
39:17para 1 menor o igual que j menor igual
39:19que n y todo eso divido por n factorial,
39:22¿cierto? por esta sumatoria
39:34y esto entonces xa n
39:43este que este paréntesis que acabo de
39:45poner aquí no es otra cosa que x n
39:50y lo que hay acá es una diferencia de
39:52armónicos, porque esto llega para el
39:56caso j = n, llega hasta eh 1/ x + n
40:04y hay que restarle todos los que estaban
40:05antes de comenzar con el x + 1, o sea,
40:09va a ser h
40:13de x + n
40:16men h
40:19de X.
40:23Aquí tengo mi
40:32Ahora,
40:34eh en el caso de los ABBs
40:45teníamos
40:47teníamos
40:50una ecuación escalar
40:58con lambda de z = 2 z - 1. Ese era
41:02nuestro
41:03factor.
41:06Por lo tanto,
41:09eh
41:11el
41:14eso implica que el peso n de z
41:17era 1/ido por n + 1
41:21por
41:232z - 1 n solución.
41:27Ya es este de aquí. El 2Z - 1 es el el
41:31lambda de z y por lo tanto el mu n que
41:36sería el average de p z,
41:42¿cómo se consigue? Se consigue derivando
41:45este coeficiente binomial simétrico,
41:48¿ya? Eh, y ¿cómo sería la derivada? Las
41:53la derivada sería eh de la forma que
41:57tenemos ahí dentro de ese rectángulo,
41:59¿no es cierto? Pero el x sería 2z - 1.
42:03Entonces sería eh 1/ por n + 1
42:09eh 2z - 1
42:12coma n
42:15por
42:17eh hz
42:22- 1
42:25+ n
42:27- h2z - 1.
42:33y estaríamos listos, salvo que por la
42:36regla de la cadena ahora tenemos que
42:39multiplicar por la derivada de 2 z - 1
42:43respecto de z y esa derivada es 2.
42:46Entonces hay un factor dos que aparece
42:49aquí.
42:51Ese factor dos es por la regla de la
42:53cadena.
42:54Lo voy a conectar aquí para que también
42:56quede constancia. ¿De dónde aparece este
43:00factor dos?
43:02Por la regla de la cadena
43:13ya ese dos de ahí.
43:21Eh. Ah, y falta una cosa. Ojalá que me
43:24quepa todo esto en el espacio que tengo
43:27aquí. Ah, esto lo puedo chequear un
43:29poquito. Sí, ya.
43:33Todo esto
43:35evaluado en Z = 1, eso faltaba ahí.
43:41Claro, todo eso hay que evaluarlo en z =
43:431
43:47y por lo tanto al evaluarlo en z = 1,
43:49¿qué es lo que me queda? Me queda 1/ por
43:51n + 1.
43:53[suspiro]
43:542z- 1 z = 1 es 2- 1, o sea, 1 n.
44:03Y acá sería h de n + 1
44:07menos h de 1
44:12y todo eso por dos.
44:16Ahora
44:221, n otra cosa que n + 1,
44:28por lo tanto se cancela. con eso
44:32ya.
44:33Y esto finalmente implica
44:38que eh mub
44:42es 2
44:46hn + 1 - 1 porque h1 es 1.
44:53Ya.
44:55Para los árboles de búsqueda binaria
44:59sin medianidad tres los árboles de
45:00búsqueda binaria común y corriente. Y
45:02con eso completamos
45:05el precalentamiento.
45:13Ya.
45:23Okay. Seguimos bien hasta aquí. Sí.
45:27Ya. E entonces volvamos a nuestro
45:31problema.
45:47Que es resolver una ecuación de la forma
45:50a su n + 1
45:53vector de z.
45:57igual i + 1/ n + 1 por h dez
46:06por a su n
46:09vector de z.
46:16Entonces, eh desenrollando
46:24ya
46:26pueda pasar lo mismo que acá, lo mismo
46:27que pasaba con lambda de z aquí.
46:35Si
46:39si aquí en vez de tener lambda de Z
46:42tengo una matriz H de Z, todo esto de ir
46:45desenrollando, desenrollando,
46:46desenrollando va a ser lo mismo. Ya. Y
46:48yo voy a llegar finalmente a esto. Ah,
46:51pero hay una diferencia que esto es una
46:52identidad. Aquí donde dice uno es una
46:54identidad, ¿no es cierto?
46:56Entonces, ah, y al ponerlo aquí, al
46:59hacer esto, ya no va a ser H de Z + N,
47:02no de sentido sumar una matriz con un
47:03escalar. Lo que pasa es que al tomar eh
47:06poner un denominador con un n, esta
47:08identidad que hay aquí va a quedar
47:09multiplicada por n, o sea, va a ser n
47:11veces la identidad, ¿ya? Y y todo esto
47:15donde parece n -1, qué sé yo, va a ser
47:17la n -1 veces la identidad. Una vez la
47:21identidad acá, ¿ya? Eh, entonces eh
47:26esto va a ser HDZ más identidad. H
47:31Entonces, eh hagámoslo rápidamente para
47:34que se esa es la diferencia.
47:40Ya. Entonces, eh esto va a quedar así
47:46a su n
47:48eh
47:52de
47:56Bueno, escribamos la sub n de z. Ya va a
48:00quedar identidad
48:02+ 1/ por n + 1 h dez.
48:06No, no, no, no, no, no, no.
48:131 partido por NHZ porque estoy corriendo
48:15en uno.
48:21Ya,
48:22pero esto me va a convenir ponerlo como
48:27denominador común N. Y aquí va a quedar
48:30eh HZ
48:33más n veces la identidad.
48:38Ya. Entonces, al ir desenrollando
48:42va a quedar HDZ
48:45más n veces la identidad partido por N.
48:49Se va a ser uno
48:51HDZ
48:54+ n - 1 veces la identidad divido por n
48:58- 1
49:00ta t
49:02hasta llegar finalmente a HZ
49:07más la identidad. Una vez la identidad
49:09partio por 1
49:12por el a sub0 de Z.
49:16Ya. Entonces, e
49:20lo que va a quedar en el en el numerador
49:23lo voy a escribir de lo voy a pasar en
49:27limpio como que fuera de derecha a
49:29izquierda, ah, comenzando por el de más
49:31a la derecha y y moviéndote más a la
49:32izquierda. Entonces va a quedar HD de Z
49:37más la identidad
49:41HDZ
49:43más dos veces la identidad
49:46hasta HDZ
49:50más n veces la identidad
49:54dividido por n factorial
49:57por el a0 de Z.
50:01Ya. Entonces, el numerador
50:10es un polinomio
50:17en la matriz Z,
50:19HD Z.
50:24Ya. Pregunta es, ¿qué significa un
50:26polinomio de una matriz?
50:36Ya, si
50:39f(x) es un polinomio
50:47e entonces f(x) va a ser de la forma
50:51sumatoria sobre i de f i por x a la i,
50:56¿no es cierto? hacer la forma del
50:57polinomio.
50:59Si es una matriz,
51:06ya eh
51:12se define su potencia.
51:18Una matriz cuadrada tiene que ser,
51:23que es el caso, su potencia.
51:28A a la i se define
51:33como
51:36a a la 0 es la identidad
51:40y a a la i va a ser
51:44a la i - 1 multiplicado por a, ¿cierto?
51:49Esa es la definición de una potencia,
51:51pero a a la cer es una identidad. Ah.
51:55Eh, y por eso si cuando aparece x a la 0
52:01en un polinomio, yo digo eso es uno,
52:03pero cuando es un polinomio de una
52:04matriz y aparece a a la cer eh yo digo,
52:08eso es una identidad. Por eso ahí por
52:11eso aparece la identidad ahí. Entonces,
52:13eh y y
52:17entonces eh
52:22f de a ahora ya no f de x va a ser la
52:26sumatoria sobre i de f i multiplicado
52:30por a a la i. Y así es como se define un
52:32polinomio de una de una matriz. ¿Ya?
52:36Eh, bueno, y este polinomio que tenemos
52:39en el numerador aquí,
52:43ya no hay ningún problema, por lo tanto,
52:45de que esté bien definido cuando H de Z
52:47es una matriz y al dividirlo por n
52:50factorial, lo que queda es exactamente
52:53el coeficiente binomial simétrico de
52:55HDZ, com N. Ya, así es que eh
53:02y eso ahí, perdón,
53:04y ahí llegamos a lo que les había
53:06adelantado antes, que e que la solución
53:11va a ser que el a n de zficiente
53:17binomial simétrico H de Z, com N
53:22eh por A0 de Z.
53:27Ya.
53:29Y
53:34P sub NZ Z,
53:38¿no es cierto? Nosotros habíamos visto
53:39ya que el P sub N
53:44iba a ser
53:49acá 1/ido por n + 1 eh c de z vector por
53:54a sub n de z, ¿no es cierto? Pero ahora
53:56tengo una fórmula para la sub, así que
53:58la sustituyo
54:00y me va a quedar que
54:06pudido
54:08por n + 1 por el a, pero el azu n el que
54:11está allí arriba, o sea, coeficiente
54:14binomial simétrico h dez n.
54:19Ah, perdón, antes de eso,
54:25por todo eso. Bien porrado, ya. Eh, sí,
54:29pues se me está quedando en el tintero
54:30el
54:33Estamos.
54:35Ay, quézaba. Aquí se me está quedando en
54:39el tintero el C el Perdón, no era la
54:42idea aquí.
54:45Eh, se me estaba quedando en el tintero
54:47el vector fila C de Z. Ya, así que
54:52vamos.
54:58Entonces va a ser
55:011 par por n + 1 por el vector fila C de
55:05Z por el A N de Z, que sabemos ahora que
55:08tiene esta forma. Coeficiente simétrico
55:12H de Z n
55:15por a sub0 de Z.
55:21Ya.
55:24Eh, perfecto.
55:27Tenemos la solución
55:32ya, pero todavía no no hemos llegado a
55:35puerto
55:36porque eh
55:40una cosa es saber que yo tengo ese
55:42polinomio HZN y otra es poder ser capaz
55:46de calcularlo. Y no solo eso, sino que
55:48también su derivada, ¿no es cierto? Así
55:51es que e la pregunta es, ¿cómo calcular
56:03cómo calcular
56:05HZ
56:06com N?
56:09Ya,
56:12más en general.
56:19¿Cómo calcular
56:25F de A,
56:29donde F es un polinomio
56:37y a una matriz cuadrada.
56:54¿Qué opinan ustedes?
56:58Yo les doy a ustedes una matriz. De
57:00hecho, la matriz ya la vieron, ¿no es
57:01cierto? es una matriz de 3* 3
57:04y quiero calcular el coeficiente
57:07coeficienteal simétrico de esa matriz,
57:09coma n.
57:12Eh,
57:13ese eso yo lo puedo calcular con e,
57:18o sea, o sea, el coeficiente número
57:20simétrico lo puedo expresar como un
57:22factorial ascendente, ¿no es cierto? Y
57:24un factorial ascendente es una pitatoria
57:26y por lo tanto eso es un polinomio, ¿ya?
57:29No se daba un polinomio. ¿Cómo voy a
57:31calcular el polinomio de una matriz?
57:32¿Qué sugerirían ustedes
57:38en general? Porque decirme, si yo tengo
57:40una matriz y me dicen, "Calcule usted,
57:42qué sé yo, el polinomio
57:44para una matriz a 3a² + 2a menos la
57:49identidad, no tengo ningún problema en
57:51calcularlo.
57:53Pero cuando me dicen que es un polinomio
57:54de grado n,
57:57ya, donde el n pues cualquier cosa,
58:02eh, ¿cómo calculo eso? Ah
58:07eh, simbólicamente, ah porque una vez si
58:10a mí me fija en el n, no tengo ningún
58:11problema en calcularlo, pero cuando el n
58:14fijo, ¿qué qué se les ocurre
58:25una aproximación o quizás como una cota
58:29superior?
58:30Ah,
58:33podría ser, pero en este caso no me
58:34sirve mucho porque mi patriz es es
58:38simbólica, tiene Z. Ah, tiene una
58:40variable Z. Por lo tanto, ahí no puedo
58:43yo acotar. No, no es como que estoy
58:45haciendo una aproximación numérica
58:47porque necesito el resultado simbólico
58:50exacto
58:52porque después voy a ir a derivar y
58:53poner 7 = 1 o derivar dos veces y poner
58:567 = 1 para calcular la varianza, ¿no?
58:59Entonces, no me sirve tener una
59:01aproximación del polinomio. Yo necesito
59:03el polinomio exacto para poder
59:04derivarlo.
59:12Hay una parte de la materia de álgebra
59:14lineal que a veces eh
59:18no se
59:19no no se alcanza mucho a pasar en plan
59:22común o a veces a esa altura los
59:24estudiantes ya están
59:27en otra porque calcularon que estaban
59:29exhibidos, entonces no tienen para qué
59:30ponerle mucha atención a la materia
59:31final del curso.
59:34Pero es super útil
59:37y ustedes seguramente se van a acordar
59:40cuando yo les diga. Lo que vamos a usar
59:43es diagonalización.
59:46Vamos a diagonalizar la matriz HDZ. ¿Se
59:49les suena conocido?
59:55¿Sí o no?
59:58A mí solamente me suena conocido de
59:59máquinas de touring, pero no con
1:00:01números. Ah, no es que ellas alcance
1:00:03nombre. Es cierto que se usa
1:00:07es cierto que se usa diagonalización en
1:00:09en la demostración de
1:00:12de demostración de indecidibilidad,
1:00:15pero esa ese uso del término
1:00:17diagonalización
1:00:18viene de otro lado, viene de la forma
1:00:21como se demuestra que los reales no son
1:00:23enumerables. ¿Se acuerdan? Si yo tengo
1:00:26si yo supongo que los números reales son
1:00:27enumerables, entonces yo los puedo poner
1:00:29en una lista. Ya. Y luego yo recorro esa
1:00:32lista
1:00:34y para el primer número le cambio el
1:00:37primer decimal, al segundo le cambio el
1:00:40segundo decimal, al tercero le cambio el
1:00:42tercer decimal y así voy recorriendo la
1:00:44lista. Por eso se llama diagonalización,
1:00:46porque yo voy por la diagonal. Ah, y el
1:00:49resultado es que yo estoy construyendo
1:00:52un número que no está en la lista, ¿no
1:00:55es cierto? Porque como siempre yo fui y
1:00:58y le cambié un dígito a a cada uno de
1:01:00los números que me fui encontrando y el
1:01:02el número resultante de todos esos
1:01:04dígitos que yo cambié es un número real,
1:01:07pero por construcción no está en la
1:01:09lista, por lo tanto, contradicción, los
1:01:13reales no son enumerables. Ese es un
1:01:14argumento de diagonalización, ¿okay? Y
1:01:17eso mismo después se aplica en la
1:01:19demostración para máquinas de tuning.
1:01:20Pero esto es otro tipo de
1:01:21diagonalización. Es una manera de
1:01:24transformar la matriz en una matriz
1:01:25diagonal.
1:01:27¿Le suena eso,
1:01:29Pablo? ¿Te suena a ti?
1:01:36A Camil le suena poco, ¿no?
1:01:38Ya es que quiero para con qué nivel de
1:01:41detalle hay que ver esto. Ah. Eh,
1:01:44¿lesenan los términos valores y vectores
1:01:46propios?
1:01:51tampoco, no mucho. Ya, entonces vamos
1:01:54desde el principio.
1:01:56Ya. Eh,
1:02:00vamos a usar diagonalización.
1:02:13Entonces, la idea es la siguiente.
1:02:17Eh, para una matriz A
1:02:25e cuadrada.
1:02:29E entonces, mejor pongamos que es
1:02:31cuadrada.
1:02:38Su ecuación característica
1:02:49es
1:02:51determinante
1:02:53de
1:02:59A menos lambda i
1:03:02igual 0.
1:03:11Ya, eso
1:03:15es lo que se llama la ecuación
1:03:17característica.
1:03:20Eh,
1:03:22a ver, a mí me va a convenir escribirlo
1:03:23al revés. Da lo mismo porque es igual a
1:03:25cero, ¿no es cierto? Pero me va a
1:03:26convenir escribirlo al revés.
1:03:32escribir
1:03:34que el determinante de lambda y - a es
1:03:39ig a 0.
1:03:42Ya las raíces
1:03:46esto es una
1:03:49esto es una ecuación la función de la
1:03:52izquierda es polinomial
1:03:55y
1:03:58por lo tanto tiene raíces que pueden ser
1:04:00reales o complejas.
1:04:02Entonces, las raíces
1:04:10esta ecuación,
1:04:13las soluciones para lambda
1:04:15se llaman
1:04:20los valores propios
1:04:27de A,
1:04:29¿ya?
1:04:31Y
1:04:33eh
1:04:36por ejemplo
1:04:40nuestro caso la matriz HDZ
1:04:45dijimos que era
1:04:50-1
1:04:55- 2 6z
1:04:590 2 - TR.
1:05:03Ya, esa es la matriz.
1:05:06El determinante, la la ecuación
1:05:08característica sería determinante de
1:05:11lambda i - a.
1:05:13Entonces sería el determinante
1:05:18o estoy usando como cuadrado.
1:05:23Sería lambda + 1
1:05:2700.
1:05:29Ya sería -1 lambda + 2
1:05:34- 6z. Pues estoy poniendo - a, o sea, -
1:05:37h de z. Eh, 0 - 2 lambda + 3
1:05:46sería el determinante de esa matriz
1:05:48igual 0.
1:05:50Ya.
1:05:52Y
1:05:54ustedes vieron determinantes, ¿sí? ¿Sí o
1:05:56no? ¿Se acuerdan como calcular
1:05:59determinante o nunca subieron?
1:06:02Era como sumar y restar intercalado y
1:06:08multiplicandoado. Es como bien rara la
1:06:10fórmula. CL uno expande por la uno va
1:06:13recorriendo, por ejemplo, la primera
1:06:14fila y expandiendo. Ya. Entonces va a
1:06:16ser cuánto
1:06:17va a ser Vamos para la primera fila, va
1:06:19a ser lda lambda + 1,
1:06:23¿ya? Por el determinante de esta
1:06:27submatriz que queda aquí.
1:06:30Ya. Por el determinante,
1:06:33¿se acuerdan usted que el determinante
1:06:35también se escribe con
1:06:37así con con barras verticales en vez de
1:06:39paréntesis, ¿no es cierto? Entonces
1:06:41sería el determinante de lambda + 2 - 6z
1:06:46eh -2 y lambda + 3.
1:06:51Eso es un determinante, ¿ya? Y después
1:06:53sigo recorriendo por la misma fila y va
1:06:56a ser cerminante
1:06:58de aquí, pero es cer y sería menos
1:07:01porque van alternando los signos más
1:07:04cerminante de acá, pero es certo no más.
1:07:08Ya, así que queda
1:07:12queda lambda + 1
1:07:15ya por el determinante de esa pequeña
1:07:17matriz y ese determinante es este por
1:07:21este menos este por este, ¿ya? lambda -
1:07:252 * - 3 - -2 * -6, o sea,
1:07:36lambda + 2*
1:07:38lambda + 3
1:07:42- -2* -6, o sea, -1z.
1:07:50Ya. Y esto ahí, todo eso igual a cer.
1:07:56Ya.
1:07:58Y esto va a quedar como lambda + 1.
1:08:02¿Ya? ¿Cuánto es lambda + 2* lambda + 3?
1:08:04el lambda²ad
1:08:07eh
1:08:09+ 2 l + 3 l sería + 5 lambda
1:08:17más 6 - 12z.
1:08:25Ya. Y ahora viendo cuáles son las
1:08:27raíces,
1:08:29eso implica que hay una raíz lambda
1:08:32igual -1, ¿no es cierto?
1:08:35Ya
1:08:36que porque
1:08:39si todo esto igual a cer quiere decir
1:08:41que el primer factor es igual a 0 o el
1:08:43segundo igual a 0. Con el primero igual
1:08:44a 0 l + 1 = 0 me da que lambda es -1. Y
1:08:48para el segundo tengo que encontrar las
1:08:49raíces de esta de esta ecuación de
1:08:52segundo grado. Ya. Así es que va a ser
1:08:56lambda igual a - b que es -5
1:09:00más men raí de b² que sería 25.
1:09:06- 4ac.
1:09:09C es 6 - 2 es z.
1:09:11Entonces sería -24
1:09:15+ 12
1:09:16+ 48 zodo
1:09:23partido por 2a, que es 2.
1:09:27Así es que eh
1:09:31y esto es igual a -5
1:09:35+ -√ 1 + 48z,
1:09:39¿cierto? porque es 25
1:09:42partido por 2. Entonces ahí tengo mis
1:09:44tres raíces. Ya, estos son los valores
1:09:47propios de la matriz H de Z.
1:09:51Okay. Eh,
1:09:55es interesante. Eh, por lo tanto, estas
1:09:58lambdas son lambdas de Z, son funciones
1:10:01de Z.
1:10:03E es interesante
1:10:06eh ver qué pasa en Z = 1.
1:10:10¿Por qué? Porque de dónde salió la
1:10:12matriz HZ. La matriz HZ salió al pasar
1:10:18de a sub n a sub n + 1, ¿no es cierto?
1:10:22Entonces, los a sub n están contando
1:10:24eh
1:10:26el número de no número de hojas por
1:10:28nivel.
1:10:31Cuando yo pongo z = 1, ahí estoy
1:10:33contando número de hojas de todos los
1:10:35niveles, ¿ya?
1:10:38Eh,
1:10:39y la suma de todas las hojas de todos
1:10:42los niveles tiene que ser n + 1.
1:10:45¿Okay?
1:10:47Eh, y si la solución incluye factores,
1:10:52eh, coeficientes binomiales, de alguna
1:10:55manera tiene que aparecer un n + 1 que
1:10:57cancele al n + 1 que va a ver en el
1:10:58denominador más adelante cuando yo
1:10:59calcule PU N, porque el PU N zo,
1:11:05es una probabilidad, ¿ya? Entonces,
1:11:07tiene que haber algo que cancele al n +
1:11:091, tiene que haber un factor lineal. Eh,
1:11:11y
1:11:12aquí yo tengo un la si pongo 7 = 1,
1:11:15tengo el primero, no depende de eso,
1:11:19ya es -1. Y es y acá, ¿qué pasa? Tengo
1:11:23dos posibilidades, signo menos o signo
1:11:25más, ¿no es cierto? Pongamos signo menos
1:11:27primero.
1:11:28Si es signo menos sería menos y z = 1 me
1:11:32da 1 + 48, me da 7. Ya. Una posibilidad
1:11:37sería -5 - 7/ 2 sería -1.
1:11:41y el otro -5 + 7, eso sería 2 par 2 es
1:11:45ig a 1. O sea, hay de los tres lambdas
1:11:50de z al evaluar de ser igual 1, hay uno
1:11:53que es -1, otro que es -6 y otro que es
1:11:55+1.
1:11:57Vamos a ver más adelante que ese que es
1:11:59igual a +1 resulta ser críticamente
1:12:02importante porque es el que me permite
1:12:05que haya un factor lineal que cancele al
1:12:06n + 1. Eso lo vamos a ver, pero ya a
1:12:08esta altura me parece que no en esta
1:12:11clase. Okay. Ya. Entonces, estos serían
1:12:14los valores propios para una matriz en
1:12:18particular que es esta. Una vez que uno
1:12:21encuentra los valores propios,
1:12:23ya eh
1:12:27se encuentran eh luego se encuentran los
1:12:29vectores propios.
1:12:46¿Qué son las soluciones?
1:12:52de la ecuación
1:12:59a por a * x =
1:13:03lambda por x,
1:13:05donde
1:13:07lambda es un valor propio.
1:13:15Y de ahí uno encuentra los X
1:13:17y la matriz
1:13:22cuyas columnas
1:13:31son los vectores. Estos vectores propios
1:13:34que acabo de encontrar.
1:13:39se llama la matriz de cambio de base.
1:13:43Digamos la matriz E, pongámosle nombre
1:13:45al tiro. La matriz E, cuyas columnas son
1:13:48los vectores propios, se llama la matriz
1:13:50de cambio de base
1:14:02y se tiene
1:14:06la propiedad
1:14:11de que
1:14:17a la matriz A
1:14:21se puede factorizar de la siguiente
1:14:22manera. La matriz E, que es la matriz de
1:14:25cambio base,
1:14:27por una matriz diagonal que tiene los
1:14:30valores propios.
1:14:34Esa es diagonal
1:14:37y acá a la men1.
1:14:43Ya, o sea, todo esto que se está
1:14:46haciendo aquí de encontrar los valores
1:14:48propios, encontrar los vectores propios,
1:14:50for, encontrar la matriz de cambio de
1:14:51base, es porque una vez que yo los
1:14:53tengo, la matriz A se puede factorizar
1:14:56de esta manera. Eh, y eso va a ser
1:15:01superútil. Vamos a, como digo, ya prob
1:15:04creo que en esta clase ya no, pero vamos
1:15:06a vamos a hacer, bueno, aquí ya
1:15:09calculamos los valores propios ao. Ah.
1:15:11Vamos a ver en la próxima clase que eso
1:15:13yo lo puedo calcular con seis, por
1:15:14supuesto, ya que ya sabemos cuáles son
1:15:17los valores propio. Con seis también
1:15:21podemos calcular la matriz E, que son
1:15:24los vectores propios puestos como
1:15:26columnas. H y
1:15:31bueno, y enal se demuestra que teniendo
1:15:34eso eh yo puedo tener esta
1:15:35factorización. Eh, un detalle que en
1:15:38este caso no es problema.
1:15:41Los valores propios para que esto sea
1:15:42así tienen que ser todos distintos. Ya.
1:15:45Si son todos distintos, esto está
1:15:46garantizado que se puede diagonalizar
1:15:49así. Si no son todos distintos, puede
1:15:51que todavía se pueda, pero puede que no.
1:15:53En cuyo caso hay otra forma que se puede
1:15:56utilizar que se llama la forma normal de
1:15:58Jordán. Ah, pero aquí no lo vamos a
1:16:00necesitar porque ya ustedes ven que en
1:16:02nuestro ejemplo, en nuestro problema en
1:16:04particular, los tres valores propios son
1:16:07distintos, ya así que la matriz es
1:16:10diagonalizable así. ¿Y por qué esto es
1:16:14útil? Porque eh
1:16:19recuerden que todo esto lo estamos
1:16:20haciendo para calcular un polinomio de
1:16:21de la matriz A. ¿Ya? Entonces, para
1:16:24calcular un polinomio en la matriz A, lo
1:16:26primero que tengo que hacer yo es e
1:16:30saber calcular potencias de la matriz A,
1:16:32a A la I. ¿Cómo calculo A a la I? Ah,
1:16:36miren, miren lo que pasa con A la I. Si
1:16:39yo quiero calcular A a la I,
1:16:42eh, yo sé que a se factoriza. [risas]
1:16:45Bueno, a a la I a por a por a
1:16:51y veces, ¿no es cierto?
1:16:54Pero como la matriz A, yo sé que se
1:16:55factoriza así, pongamos, llamemos a esto
1:16:58la matriz D por diagonal, ¿ya?
1:17:02Eh,
1:17:04yo sé que A se puede escribir como e * D
1:17:07* E a la -1, entonces el primer A lo
1:17:08escribo como e * D * E a la -1, donde,
1:17:13bueno, no lo dije, pero E a la -1 es la
1:17:15inversa de E, ¿no es cierto? Ya, todo
1:17:17eso sí, sí está claro. Ya, eso.
1:17:21Después el segundo a lo mismo, e * D * E
1:17:24a la -1
1:17:26y así hasta el último a que es E * D * E
1:17:30a la -1.
1:17:32Okay.
1:17:34Pero ahora esto yo lo puedo agrupar
1:17:35distinto. Yo lo puedo agrupar así, e *
1:17:39D. Y aquí agrupo el e a la -1 * e
1:17:44y el siguiente me va a aparecer de nuevo
1:17:47eh
1:17:49un d
1:17:52e a la men 1 por e y así sucesivamente
1:17:55hasta que me va a aparecer finalmente un
1:17:57d y un e a la men1.
1:18:02¿Ya?
1:18:07¿Y por qué hice eso?
1:18:10Porque
1:18:13esto es una identidad y esto es una
1:18:17identidad y así todas las que aparecen
1:18:18al medio son identidades. Entonces, si
1:18:22yo
1:18:24eh ignoro todas esas identidades que
1:18:26están multiplicando al medio, lo que
1:18:27queda finalmente es e*
1:18:31d a la i por e a la -1.
1:18:35¿Ya?
1:18:36Entonces, el problema de calcular a a la
1:18:38i lo he reducido al problema de calcular
1:18:41una potencia, pero de una matriz
1:18:43diagonal. Y calcular potencias de
1:18:45matrices diagonales es s simple. Si yo
1:18:48tomo esta matriz
1:18:52y la multiplico por sí misma, lo que va
1:18:54a quedar en la diagonal es lambda 1
1:18:55cuad, lambda 2 cuadrad, etcétera. Y si
1:18:58la multiplico por esta misma matriz de
1:18:59nuevo, va a quedar lambda 1 al cubo,
1:19:01lambda 2 al cubo, etcétera,
1:19:03sucesivamente. O sea, eh calcular una
1:19:07potencia de una matriz diagonal es muy
1:19:09fácil, ¿ya?
1:19:12donde
1:19:16de
1:19:18a la i va a ser una matriz donde aquí
1:19:21está lambda 1 a la i, lambda 2 a la i y
1:19:25así sucesivamente.
1:19:30Ya.
1:19:33Y ahora
1:19:38para calcular
1:19:43un polinomio
1:19:49f de a
1:19:52donde f(x)
1:19:55es la sumatoria sobre i de f * x a la i.
1:20:00¿Ya?
1:20:02Entonces, f a
1:20:09va a ser la sumatoria.
1:20:14Aquí,
1:20:16aquí tengo que multiplicar esto por f
1:20:18sub y sumar. Entonces, aquí esto lo
1:20:21tengo que multiplicar por fui y sumar.
1:20:24Eh, pero bueno, el e sale para fuera,
1:20:26para un lado, el e- un para el otro. lo
1:20:28que queda es fui i * d a la i y sumar. Y
1:20:31al sumar f * d a la i lo que queda es
1:20:34fd.
1:20:36Ya. Pero fd es simplemente
1:20:40eh la el polinomio de los valores
1:20:43propios. Ya.
1:20:46Eh, lo que queda es que f de a
1:20:50termina siendo
1:20:52simplemente e
1:20:55por una matriz diagonal
1:20:57en que queda f de lambda 1, f de lambda
1:21:022, el polinomio aplicado a los valores
1:21:04propios y eso no es problema porque esos
1:21:07son escalares por la -1.
1:21:11Entonces, esa es la gracia que tiene el
1:21:15haber diagonalizado.
1:21:17Ah, que eso hace que el cálculo
1:21:22de los eh
1:21:25de de de este polinomio sea muy simple.
1:21:28Ya, en nuestro caso
1:21:38el polinomio f(x) es x n.
1:21:46Por lo tanto,
1:21:48a n se calcula como e por la matriz
1:21:52diagonal
1:21:54eh
1:21:57lambda 1, n lambda 2 coma n
1:22:06por e a la men 1. Ya.
1:22:12Y por lo tanto
1:22:17el pes de Z que teníamos,
1:22:21que habíamos escrito por acá, est Pu N Z
1:22:27este PS NZ que está en el rectángulo.
1:22:29Ahora yo ya sé cómo calcular el
1:22:32coeficiente binomeral simétrico
1:22:35Hz Z n va a ser e a la men1 por la
1:22:39matriz diagonal de los coeficientes
1:22:40binomiales simétricos por e perdón aquí
1:22:43e por la diagonal de los coeficientes
1:22:45binomiales simétricos por e a la men 1 y
1:22:48va a quedar así
1:22:53peso n de z va a quedar como 1/ido por n
1:22:56+
1:23:00por C de Z. CDZ es un vector conocido,
1:23:03¿no es cierto? Por E
1:23:06por la matriz diagonal
1:23:10lambda 1 de Z n,
1:23:14lambda 2 de Z, n,
1:23:17lambda 3 de Z, n,
1:23:22ya.
1:23:25Y esto sigue sigue aquí por e a la -1
1:23:31y por a0 de z,
1:23:36¿ya?
1:23:37donde
1:23:40HZ
1:23:42es la matriz
1:23:46-1
1:23:490 - 2
1:23:53y 0z
1:23:56- 3
1:23:59ya.
1:24:00y c z
1:24:03es 1
1:24:062 z
1:24:08z + 2 z²
1:24:13y el acero de z para tener todo junto
1:24:17es 1 así que están todos los datos
1:24:23para poder calcular, pero eso queda para
1:24:28la clase que viene.
1:24:30Muy bien.
1:24:32¿Alguna pregunta?
1:24:35¿No quedaron demasiados perdidos con
1:24:37toda esta parte de álgebra lineal?
1:24:41Repásenlo
1:24:42poquito, pero hay que repasarlo.
1:24:43Claro. Ah, pero no no es mucho más lo
1:24:46que hay que saber sobre diagonalización.
1:24:48que eh eh o sea, además como los valores
1:24:52como los vectores propios no los van a
1:24:54calcular a mano, sino que con algún
1:24:56software es que no tiene para qué
1:24:58recordarse en tanto detalle, pero sí hay
1:25:02que tener eh entender lo que son los
1:25:05valores y los vectores propios. Ya con
1:25:08eso quedamos hasta hoy día. Concluimos
1:25:11la clase
1:25:12y e
1:25:16y nos vemos el el lunes. Hasta luego,
1:25:24profe. Co?