Full transcript
0:03Hola, buenos días, bienvenidos a la
0:05clase.
0:07Hoy día vamos a continuar con nuestra
0:12visión de algunos problemas para motivar
0:15lo que vamos a hacer en el curso y vamos
0:18a abordar un análisis con un enfoque
0:20distinto a lo que hemos hecho en las
0:21clases pasadas. Este va a ser el
0:24análisis
0:26de Merge Sort. Ustedes
0:39deben recordar
0:43en qué consiste el merge sort. La idea
0:47es que eh a nosotros nos dan un conjunto
0:51que está totalmente desordenado,
0:56¿ya? Y lo primero que hacemos es
0:59dividirlo por la mitad,
1:02tan exactamente como se pueda. ¿Ya? Si
1:06el número de elementos es par, no hay
1:07ningún problema en dividirlo por la
1:08mitad. Si es impar, una de las mitades
1:11será un poquito más grande que la otra.
1:13¿Ya?
1:14Eh, y luego le aplicamos merch
1:19recursivamente a cada mitad. Entonces,
1:22hacemos merge sort
1:25de la mitad izquierda,
1:28merge sort de la mitad derecha.
1:32Y el resultado de eso es que ahora
1:37cada mitad está ordenada.
1:45Y finalmente,
1:48se lo que tenemos que hacer es estos dos
1:51subconjuntos que están ordenados,
1:53mezclarlos para formar un solo conjunto
1:55ordenado.
1:56Eso, ¿cómo se hace? Se hace recorriendo
1:58ambos conjuntos de izquierda a derecha.
2:00Uno lleva un dedo apuntando al primer
2:03elemento de cada conjunto y uno compara
2:06cuál de los dos es menor y el que es
2:07menor se va al al área de salida. ¿ya? Y
2:10avanzamos el dedo en ese en ese
2:12conjunto. Y siempre vamos comparando los
2:14dos elementos que estamos apuntando
2:17hasta que eh finalmente todos han
2:20terminado de salir hacia el área de
2:21salida. Ya. Eh, si uno de los conjuntos
2:25terminantes, todos los restantes se
2:27copian hacia afuera. Ya. Peoro, es que
2:30al final van quedando uno de cada uno,
2:33¿ya? Y
2:35y ahí se copia el menor de los dos y
2:37luego el que queda. ¿Ya?
2:40E
2:43por lo tanto, eh, bueno, y ese proceso
2:45se llama merge, no mer. Mer es el la
2:48ordenación, pero el proceso de mezclar
2:50se llama merge.
2:56Ya. Y como se los he descrito,
3:00ese es un proceso.
3:03Bueno, aquí el resultado es que ahora
3:04todo el conjunto está ordenado.
3:09Estamos listos. Ya. Ese es un proceso
3:14que
3:15eh toma tiempo lineal. ¿cierto? Porque
3:18hay que examinar cada uno de los
3:19elementos y cada uno de los elementos se
3:21copian hacia el área de salida. Ah. Eh,
3:25entonces de hecho, digamos que eh
3:29tomemos como medida de
3:32costo el número de de movimientos de
3:35datos. Ah, cada dato que se mueve al
3:37área de salida, eso cuesta uno. Hm.
3:39Entonces, digamos que que TDN
3:46el número de movimientos de datos
3:56y ahí tenemos una ecuación muy simple
4:01que dice que el para ordenar n elementos
4:05yo tengo que ordenar dos subconjuntos de
4:09tamaño n medios, ¿no es cierto?
4:15Más eh
4:17y y luego tengo que hacer un merge y el
4:19merge tiene costo n porque cada uno de
4:22los n elementos se tienen que mover al
4:23área de salida. Ah, y
4:27t de1
4:29es eh es uno, ¿no es cierto?
4:33Bueno, de hecho también podríamos decir
4:34cuánto vale t de cer. Ordenar un
4:36conjunto de tamaño cero cuesta cero. No
4:38tengo nada que mover ya.
4:42Pero la la condición de borde td1 me
4:45sirve eh más porque eh si yo partiera
4:50con t de0 = 0
4:53eh eso no me daría el valor correcto
4:55para t de1.
4:57Porque
5:00si yo parto con t0 igual 0 y lo aplico
5:02aquí, entonces, ¿cuánto vale TD1? A ver,
5:04o sí, no está bien.
5:09Y ya es
5:11claro, lo que me para T de 1 que me dar
5:13T de 1/io y no no hemos dicho que es T
5:15de 1/,
5:20así que no vamos a partir de T1 ig, pero
5:23igual dejamos constancia que t0 vale 0.
5:26Okay, ese problema. Eh, sí, ¿por qué?
5:29¿Por qué no me funcionó esto de
5:30aplicarlo a
5:33a
5:36n = 1? Ah, eh, porque esta esta ecuación
5:49es válida
5:52solo para potencias de dos.
6:00ya no es, o sea, n de la forma 2 a la k
6:06para k mayor o igual que 0.
6:09Entonces eh por [carraspeo] eso es que
6:11t0 no me no calza dentro de ese molde.
6:15Okay. Entonces, eh
6:19ahora, ¿por qué hicimos una ecuación que
6:21solo válida para potencias de dos?
6:22Bueno, en primer lugar porque es más
6:24fácil. Ya. Eh, y segundo, porque el
6:27resultado es suficientemente cercano al
6:31a al resultado para cualquier N, que
6:34como vamos a probar en lo que queda de
6:35la clase, eh, en realidad en la práctica
6:38no hace fal no necesitamos preocuparnos
6:41mucho de de la diferencia que si es o no
6:43potencia de dos, pero eh en esta misma
6:47clase vamos a a ver qué pasa si es que
6:49nosotros queremos hacer un análisis que
6:52realmente corresponda. a
6:55a para que sea válido para todo n. ¿Ya?
6:57Entonces, ¿cómo podemos resolver esta
6:59ecuación? Bueno, por el teorema maestro
7:11sabemos
7:14que tdn
7:16es orden de n log n,
7:20¿ya? Porque corresponde,
7:22si ustedes se acuerdan dela, maestro,
7:26corresponde al caso p = 2, q = 2 con r =
7:311. Ah, y eso da n* log n,
7:36pero eh necesitamos tener una solución
7:39un poquito más más precisa, se el orden
7:42de magnitud, sino que saber cuál es es
7:44la forma exacta. Entonces eso lo podemos
7:47hacer, no es demasiado difícil
7:49desarrollando la ecuación.
7:57Ahora, desenrollar la ecuación no es un
7:59método riguroso de solución, pero nos
8:01permite encontrar cuál es la solución y
8:03una vez que uno encuentra la solución,
8:04no cuesta nada probarla por inducción.
8:06Así es que para estos efectos está bien.
8:10Entonces, eh escribamos la ecuación al
8:13revés n más + 2 tn/ med, ¿no es cierto?
8:20Y ahora el t de n medio lo escribimos
8:22con la misma ecuación, o sea, sería n
8:25+ 2 t de n cu sería ahora, ¿no es
8:28cierto?
8:31Y aquí tengo n + 2n/ 2n/ n, o sea, tengo
8:352n
8:37y tengo 4 tdn cuartos.
8:43Okay.
8:45Y ahora
8:48desenrollo no de 2n más
8:524
8:54e
8:56n cuart
8:59+ 2 de n sería ahora ya
9:05y eso es 3n
9:10+ 8 t de n/ por
9:16Y ustedes probablemente ya están
9:18adivinando que la forma general que esto
9:21tiene es k * n
9:24+ 2 a la k t de n parido por 2 a la k.
9:30Ya.
9:33Ahora, eso es un un carril, ¿no es
9:35cierto? Pero eh da la casualidad que es
9:37correcto, ya que tdn k * n + 2 a la k *
9:42tdn/ 2 la k para todo k mayor o igual
9:47que 0. De hecho, porque para k = 0, esto
9:51me da que tdn igual a tdn, lo cual es
9:54correcto.
9:55Y
9:58esto se podría probar por inducción si
10:00si apareciera de repente en la sala un
10:02profesor de de matemáticas a exigirnos
10:04que seamos rigurosos. Ya no hay ningún
10:06problema en probarlo por inducción, eh,
10:09porque el desenrollar es precisamente el
10:11paso inductivo
10:13y y tenemos el caso base, por supuesto.
10:15Ya. Entonces, e como es válido para todo
10:19K mayor o igual que ceremos.
10:26Sí,
10:27profesor, una duda, eh, ¿por qué ese
10:31método que yo veo que igual es bastante
10:35como explícito, no es una prueba formal?
10:38Porque dice punto, ah punto punto no es
10:42una prueba formal.
10:44Ahí es donde yo estoy
10:47digamos adivinando,
10:49adivino que la solución es. Ah, da la
10:51casualidad comocha
10:54da la casualidad que esa digitanza es
10:55correcta. Ah, pero habría si quisiéramos
10:58ser riguroso.
11:00Ya. Entonces tomemos como es válido para
11:03todo K mayor o igual que 0, vamos a
11:05tomar k tal que 2 a la k es ig a n.
11:11Ya. Eh, porque con eso el t de n par 2
11:16cama queda como t de 1, ¿no es cierto? O
11:18sea, ahora 2 a la k = n es lo mismo que
11:22decir que k es el log 2 de n, ¿no es
11:26cierto?
11:28Eh, entonces, por lo tanto, en ese caso,
11:31tdn va a ser igual
11:34a a
11:40k por n, o sea, n por log 2 de n.
11:47Ya. Más
11:502 a la K, pero 2 a la K es n
11:53y por T de 1 que es eh 1, ¿no es cierto?
11:59T de 1 es 1. Así es que n no más, ¿no? Y
12:04por lo tanto
12:07t de podemos decir que es n * 1 + log
12:122n.
12:13Ahí tengo mi solución.
12:15Esa es la solución
12:18ya detallada, sin la anotación de orden
12:22de magnitud,
12:23ya que eh
12:27que podemos obtener a partir de esta
12:28ecuación. Ahora, esta ecuación, como les
12:31digo, me da valores solamente para
12:34potencias de
12:37de dos. Entonces, tengo para voy a tener
12:39un valor para uno, ¿no es cierto?
12:42Eh, un valor para dos, eh, 1, dos,
12:49eh, para tres no tengo nada. Para cuatro
12:51tengo, ¿no es cierto?
12:54Para cinco, para seis, para siete no
12:56tengo nada. Para ocho, tengo algo por
12:58ahí, etcétera. Y la pregunta que nos
13:02podríamos hacer
13:05es, ¿qué pasa entre medio?
13:11Ya. Y es lo que vamos a tratar de
13:13responder en el resto de la clase.
13:18¿Okay?
13:20Entonces, eh
13:24bueno, de hecho podríamos darle una una
13:27mirada a qué forma tiene esta función,
13:31¿no? Eh, déjenme
13:47ok.
13:54Ya vamos,
13:57vamos a cambiarme la sh No, no quería
14:02decir eso.
14:09Vamos aquí
14:12ya.
14:20Okay, ahora sí voy a hacer lo que
14:22realmente quería hacer,
14:25que es
14:34Okay, están viendo ahora mi planilla de
14:38de Sage, ¿no es cierto? Sí, la están
14:41viendo.
14:44Esperemos que sí. ¿Ya? Entonces, vamos a
14:46definir la función tdn
14:52como
14:54eh vamos a retornar
14:57ya n por
15:011
15:02más log de n en base 2. Esa es la
15:07anotación que usa 6.
15:09Okay.
15:12Y ahora para ver qué forma tiene,
15:15[suspiro]
15:18vamos acá
15:25y vamos a hacer un plot de TDK.
15:33Ah, antes déjenme, se me olvidó hacer
15:37algo. Para visualizar esto, voy a tomar
15:39un cierto rango y y voy a definir una
15:42variable para que el rango sea el mismo
15:44en todos los gráficos que haga. Así que
15:47vamos por aquí que vamos a definir una
15:50función max.
15:53Ah, perdón, variable max. Eh,
15:57129, uno más que 128.
16:01Okay. Y eso lo ejecutamos.
16:05Ya. Y ahora entonces volvemos acá y este
16:09gráfico lo hacemos
16:12entre
16:150 y y
16:17max n - 1.
16:30Ya, ese es el gráfico de la función. Ah,
16:33está la impresión como que crece
16:34linealmente, pero en realidad no es
16:35linealmente. De partida al principio
16:37ustedes ven que no parte linealmente,
16:39parte con una pequeña curva y la verdad
16:42es que aunque no se nota mucho, se va
16:43curvando hacia arriba a porque es n por
16:46log n. Pero eso eso es lo que esa es la
16:49función. Pero esa función que se ve
16:53continua, de hecho, la función n * 1 +
16:55log 2 de n es continua, pero eh los
16:59puntos eh que yo puedo garantizar que
17:04tienen el valor correcto son solamente
17:06las potencias de dos. Todo lo demás es
17:08como una interpolación, pero no es que
17:10sea ese el valor. De hecho, lo que vamos
17:12a hacer a continuación, vamos a tratar
17:14de ver cuál sería el valor exacto eh en
17:18una implementación de eh de Mersort que
17:22funciona para tod. Ya. Entonces vamos a
17:25volver a nuestra otra
17:27pantalla, si es que no, esta vez no me
17:29equivoco.
17:47Okay. Ya. Entonces vamos a ver ahora el
17:50caso general.
17:58Ya
18:01digamos que llamemos a su n
18:05al número de movimientos de datos
18:14que hace
18:22para ordenar en elemento,
18:30pero a diferencia del anterior no le
18:32vamos a poner ninguna condición especial
18:34al al n, ¿no? Para todo n mayor o igual
18:37que 0.
18:39Entonces, ¿cuánto vale a su n?
18:44Si n es par, n se va a dividir por la
18:48mitad y va a dar dos valores exactos y
18:50no hay ningún problema. Problema es
18:51cuando n es impar. Cuando no es impar,
18:54yo divido el conjunto de la manera más
18:58equitativa que pueda, pero no puedo
18:59dejar medio elemento a un lado y medio
19:01elemento al otro. Por lo tanto, a un
19:02lado va a quedar un elemento menos que
19:04al otro.
19:05Entonces, a un lado va va a quedar el
19:08piso de n medios y al otro lado va a
19:10quedar el techo de n medios elemento.
19:13¿Ya? Entonces esto va a ser a sub piso
19:18de n medios
19:20más a sub techo de n medos
19:25más n. Esa es la ecuación que yo tengo
19:29que resolver. Y cuánto vale a sub un
19:31vale 1. ¿Y cuánto vale a sub? vale cero,
19:35¿no es cierto?
19:41Entonces vamos a
19:43volvamos a nuestra
19:47planilla de cálculo
19:50con seis.
20:06Muy bien,
20:08entonces
20:10vamos a
20:12definir,
20:20vamos a definir una una lista
20:23A, ¿ya? O sea, los elementos, los
20:27valores de esta
20:29de esta
20:31función lo vamos a poner como una lista.
20:34Entonces, vamos a definir que a
20:38es eh un
20:41primero vamos a dimensionar la rellena
20:43de ceros, pero después vamos a cambiar
20:44esto.
20:48Okay, ya.
20:51Eh, entonces ahora ya la sub ya vale
20:54cer. Entonces ahora a sub un vale 1.
20:59¿De acuerdo? Y luego
21:11de dos en adelante.
21:22Hacemos que sub n
21:25sea eh
21:29a sub flor de n medios
21:36más a sub
21:39sil de n medio sil es por silín sub
21:41techo
21:46más n
21:49eso.
21:56Okay. Eh,
22:02ya está para definir la lista. De hecho,
22:05podríamos mirar un poquito algunos
22:08valores, eh,
22:22a ver, ya
22:29ahí está. 0 1 4 8 12 17, etcétera.
22:34El 0 1 y el 4 deberían corresponder a
22:43a los valores de correctos. Ah, pero eh
22:48a ver, veamos.
22:58A ver, perdón, es que
23:16si va a salir correcto. Déjenme ver. A
23:17lo mejor,
23:19claro, eh,
23:23volver atrás a mi función
23:34y decirle que me que me dé el valor
23:36evaluado. Ah, porque si no me da un
23:39valor formal.
23:43Ahí está mejor. 1 cu. Miren, fíjense, el
23:47uno, el el uno y el cuatro están bien,
23:50pero el 8o, [carraspeo]
23:51la función t me dice que es 7.75, lo
23:54cual no está correcto, por supuesto. Ah,
23:57y después la
23:59después viene el 12, que está correcto,
24:01pero después 16.6, que que no es
24:03correcto porque sería 17 y así
24:05sucesivamente. ¿Ya? Entonces, de hecho,
24:08nosotros lo que podemos hacer ahora es
24:10eh graficar ambos. Ah, entonces decir eh
24:15que voy a formar eh como la la función a
24:21o la secuencia no está definida para n
24:24continuo, ¿no es cierto? es n discreto.
24:26Entonces voy a hacer un scatter plot
24:27para eso, a diferencia de la función t
24:30que está definida para valores
24:31continuos, ahí donde puedo invocar a
24:33plot directamente. Entonces ahora lo que
24:36yo voy a hacer es decir que voy a formar
24:39una lista
24:42ya que eh contiene todos los valores de
24:46la forma n.
24:49A ver, no contiene pares la lista.
24:52Bueno, ahí está la lista, ¿no es cierto?
24:54Ahora, dentro de la lista lo que yo
24:55tengo son pares de la forma n,
25:01¿ya?
25:03Eh, y cierro el par y eso para n
25:10en range de 0 com max.
25:17Ahí solía estar bien. Ya.
25:21Y luego digo que un S es un scatter plot
25:28de L
25:31y luego que me muestre el S.
25:35Ahí está. Ya,
25:37en realidad son un poquito gordos los
25:39puntos, así es que le vamos a agregar
25:42aquí una
25:46algo que me diga que el marker size
25:52sea de tamaño cinco. El default es como
25:5450, así es que por eso se ve tan grande.
25:57Ahí está. Esa es la esa es la función e
26:03exacta.
26:04Esta de acá. es lo que podríamos ser
26:06aproximada,
26:08suponemos. Ah, y de hecho lo que
26:10podríamos hacer ahora es graficarlo
26:12ambos juntos. Ya. Entonces decir que
26:16queremos un
26:21un plot
26:29acá para acá
26:32en el rango de cer
26:41y superpuesto con eso el
26:50Ups. ¿Qué dice? [suspiro][grito ahogado]
27:07Hm hm.
27:16A ver, no sé si este punto N que puse
27:18está echando perder las cosas.
27:20Saquémoslo porque
27:31a ver, veamos si todavía funciona este
27:34otro. Sí.
27:37Ya.
27:39Y por si faltar, profe, creo que no
27:42enolada en mi pantalla, pero parece que
27:43tiene como un paréntesis diferente, un
27:45paréntesis tipo corcheta arriba en vez
27:47de un paréntesis redondo.
27:50Aquí
27:51no, arriba. Arriba. En donde define t
27:54queiza mi pantalla. Sí,
27:56tú dices dóe quedó definido la función t
28:00sub.
28:01Esa
28:02sí. El último el último paréntesis del
28:05return no es como corchete,
28:06¿no? En realidad es redondo.
28:09Eso funcionó bien lo que es a
28:10continuación, así que no es ese
28:12problema. Gracias. No, déjame ver.
28:14Quizás lo que falta también es
28:20una cosa, yo les dije yo soy nuevo en se
28:22así es que yo más bien usaba. Eh, quizás
28:26hace falta definir, recordarle que acá
28:29es una
28:30es una variable. Sí. Bueno, ahí lo
28:33tenemos. Ya. No sé si ustedes lo
28:36alcanzan a ver. Ah, pero por ejemplo en
28:39este sector, fíjense que las pelotitas
28:41van por encima de la línea, ¿ya? Y en en
28:45algunas partes van exactamente
28:48eh no siempre las pelotitas le aciertan
28:50a la línea y son los puntos en donde
28:53discrepan las dos las dos funciones.
28:56¿Okay? Entonces, lo que de hecho para
28:59poder ver mejor
29:02la
29:03diferencia, lo que podemos hacer eh
29:08es ponemos aquí
29:12graficar la diferencia.
29:14O sea, definir una lista, digamos, un L2
29:20que sea
29:33ya una lista de pares y ahora
29:38for n en range
29:41B1 max.
29:49L2n
29:54va a ser igual
29:57a
29:59n coma a
30:03men t de.
30:10Ahí está.
30:11Okay.
30:15Y ahora entonces es un scatter plot
30:18donde están las diferencias. Y ahora
30:19digo scatter plot
30:23plot
30:29con marker size
30:33igual 5.
30:36Vamos a ver
30:38qué pasó ahora. A ver.
30:43Ah, ya. Eh, T no es una lista, pues T es
30:47una función, así que hay que llamarla.
30:51Ya,
31:00ahí. Eso debería estar bien.
31:04Claro. Miren, miren, miren. Así va. Esta
31:07es la diferencia. Ya, este es el a la
31:11función a menos la función t. Fíjese que
31:14va
31:15son
31:18esto. Y entonces los puntos donde vale
31:22cero son exactamente las potencias de
31:24dos, ¿no es cierto? Aquí está el 16,
31:26aquí está el 32, aquí está el 64, acá
31:28está el 128. Ya. Eh, ahí vale cero. En
31:32esos puntos coincide, pero en el resto
31:34tienen una diferencia. esa diferencia
31:37crece y disminuye para volver a cero. Y
31:40siempre crece y disminuye para volver a
31:41cero. H y además el el valor de la
31:47diferencia
31:48parece ir creciendo
31:51aparentemente de manera lineal el
31:53máximo, ¿no es cierto? Esto mal los
31:56puntos máximos aquí aparentemente va
31:59creciendo linealmente. De hecho,
32:00podríamos tratar de ver si esa última
32:03conjetura es correcta.
32:06eh
32:07tomando la diferencia, pero dividiéndola
32:09por n. Ah, entonces lo que yo podría
32:11hacer es tomar esto
32:14y adaptarlo
32:17para eh
32:21para que sea una lista ahora llamémosla
32:23L3,
32:25donde
32:27L3 es lo que se calcula y L3 es lo que
32:31se grafica.
32:33Ya. Eh, pero en vez de ser a su n, sea a
32:37su n - tdn
32:42dividido por n.
32:44Okay.
32:48Mire, efectivamente parece que era
32:50correcta nuestra nuestra idea de que
32:54esto crecía linealmente, porque al
32:55dividirlo por n ahora parece que todos
32:59estas eh
33:03especie de parábolas ah son
33:07como de la misma altura, ¿no es cierto?
33:10Ya. Así que eh
33:16si algo vamos a probar va a tener que
33:18ser entonces que la diferencia entre las
33:21dos funciones es de la forma n
33:23multiplicado por algo, ¿no es cierto?
33:26donde ese algo son estas funciones.
33:30Ahora, estas funciones
33:32eh no son exactamente periódicas,
33:36se parecen mucho ah eh una a la otra,
33:39pero el ancho se va duplicando cada vez
33:43porque recuerden que el cero va de una
33:46potencia de dos a la siguiente.
33:49Entonces, esta va
33:51el 32 y el 64, pero esto va entre el 64
33:55y el 128, o sea, cada vez es el doble.
33:58¿Okay? Entonces, estas funciones
34:02eh se duplican cada vez que el n,
34:06perdón, se empiezan a repetir cada vez
34:08que el n se duplica.
34:10Una verdadera función periódica se
34:12empezaría a repetir cada vez que que se
34:14avanza en un en una cantidad fija, ¿ya?
34:18Y normalizando siempre podríamos decir
34:20que es cuando se avanza en uno. Okay.
34:22Eh, pero acá no.
34:24es cada vez que se duplica el, o sea, el
34:27periodo se va duplicando, lo podemos
34:29transformar en una verdadera función
34:30periódica si es que decimos que esto
34:32sería una función periódica de log 2 de
34:35n,
34:37porque ahí sí es cierto, cuando el n se
34:39duplica, el log 2 se suma se le suma
34:41uno, ¿ya? Así es que con todo eso vamos
34:44a ir algo que lo vamos a escribir ahora
34:46en un instante apenas cambiemos de de
34:48pantalla, pero quería preguntarle si
34:50hasta aquí vamos. Claro. Sí.
34:53Sí,
34:55ya. E un detalle que en la práctica es
34:59super importante, no hemos mirado para
35:01nada cuál es la escala aquí. Fíjense
35:04esta el la amplitud de esta oscilación
35:09es como 0.08,
35:12un poquito más. Ah, o sea, es muy
35:14pequeña, es muy muy pequeña. Y eso
35:18nosotros lo notamos uno
35:21aquí, pues porque es cierto que a veces
35:25se apartan los las pelotitas de de de la
35:27línea contida, pero se apartan muy poco.
35:30Ah, cuesta, hay que forzar los ojos para
35:32verlo y eso es porque la amplitud que es
35:37tenemos aquí es muy pequeña. Si es que
35:39esta diferencia en la eso es lo que hace
35:41que en la práctica la aproximación del
35:44TDN sea suficiente para trabajar con
35:47ella y no tener que preocuparse de
35:48cuánto es el valor. Exacto, exacto,
35:50exacto. Ah, pero vamos a, ya que tenemos
35:54aquí este problema, vamos a tratar de
35:55resolverlo y ver cuánto es entonces el
35:58valor exacto de la diferencia. ¿Ya?
36:02Okay. Entonces, dicho todo eso, nos
36:04cambiamos de pantalla. A ver.
36:12Okay. A ver.
36:27Okay, entonces
36:31ya entonces aquí hicimos un paréntesis
36:35para trabajar con se
36:38dice ahí.
36:40Ya. Y como consecuencia de eso, tenemos
36:44una conjetura
36:47que dice que eh
36:54que dice que la diferencia
37:00ya a ver que la diferencia entre a sub n
37:05men t de
37:08es
37:11n multiplicado, ¿no es cierto? Ya por
37:15una función periódica, llamémosla teta,
37:20pero es una función periódica de log 2
37:22de n.
37:40de periodo uno,
37:43¿cierto? Porque se repite cada vez que
37:45el n se duplica. Por lo tanto, se repite
37:47cada vez que el que el log n se
37:49incrementa en uno,
37:51que es mayor que mayor o igual que 0.
37:55Y tal que el teta de x es menor o igual
38:00que 0.08
38:02algo. Hm. Esa es nuestra conjetura. No
38:06hemos demostrado nada de eso todavía,
38:07pero es lo que querríamos demostrar.
38:10Okay, ya. Pues entonces sería momento de
38:13remangarse y empezar a trabajar porque
38:16lo que queremos ahora es resolver la
38:18ecuación de AUn de forma exacta. Ya.
38:21Entonces, a continuación,
38:28veamos cómo podemos
38:36resolver
38:39la ecuación
38:44para su nata.
38:55Ya. [grito ahogado]
38:58Entonces definamos
39:04d sub n como la diferencia entre dos
39:06valores consecutivos.
39:11Okay.
39:13Va resultar de que eso eh nos va
39:18a permitir
39:20eh trabajar con una ecuación más
39:22sencilla.
39:24Entonces,
39:26el
39:28que es de su nando
39:31la ecuación, ¿no? Recordemos cuál es la
39:34ecuación, ahí está la ecuación.
39:35Entonces, a sub n es a sub piso n medos
39:39más a subtech n/ med + n. Entonces,
39:42¿cuánto es a su n + 1? Sería a su piso
39:46de n + 1
39:50más a subtecho de n + 1 med
39:56n + 1
39:59menos
40:01a su piso de n medios.
40:06menos a sub techo de n
40:12- n. Ya.
40:15Bueno, por lo menos hay una parte que es
40:17fácil
40:20que es cancelar ese n conn. Ya, algo en
40:24algo vamos avanzando
40:28ya. Y ahora
40:31para poder eh
40:34ver eh avanzar en esto, hagamos una
40:36pequeña tabla de los valores de n
40:43de techo de n + 1 medios,
40:49eh, perdón, piso, techo de n + 1 medo
40:56de n medios
41:00y techo de n medios.
41:03Okay.
41:07Entonces, pongamos 1 2 3 4 5. Ya.
41:14Entonces, ¿qué es el piso de n + 1/2?
41:18Para n = 1, eso sería 2/2, que es 1.
41:22Para 2 sería eh 3/2 piso que sigue
41:27siendo 1.
41:29Para 3 sería 4/2 que es 2. Para cuatro
41:33sería piso de 5 medios que sigue siendo
41:35dos y para 5 ya puede salir ser 3, ¿no
41:39es cierto? Ya. Ahora, el techo n + 1/2
41:42para eh
41:45para 1 da 2/2 que es 1.
41:49Para 2 da 3/ pero se se
41:53redondea hacia arriba, así que es dos.
41:57Para 3 da 4 medios que es 2. Para 4 da 5
42:02rondeado hacia arriba da 2,5 da 3. Para
42:075 6 ter 6 med que es 3. Okay. Ya. Para n
42:11medios 1/2 hacia abajo es 0
42:152 med es 1. 3 medios hacia abajo es 1. 4
42:20medios es 2.
42:22Abajo es 2. Ahora para acá un medio
42:25hacia arriba es uno. Este de acá también
42:28es uno. Este es dos. Este es dos y este
42:32es tres. Okay. Ya.
42:38En base a estos pocos datos
42:41podemos hacer la siguiente observación.
42:45Si fijan ustedes, la columna del n + 1/
42:54esta columna de aquí
42:57es idéntica a esta columna de acá,
43:02o sea,
43:07esta columna y esa columna son lo mismo,
43:11¿ya?
43:15O sea, lo que estamos diciendo es que el
43:18piso de n + 1/2
43:25es igual al techo de n medios.
43:29Okay. Ya.
43:32[grito ahogado]
43:34Y ahora el
43:39¿Qué pasamos las otras dos columnas?
43:42Bueno, si las comparamos,
43:46cuando este es cero, este vale uno.
43:48Cuando este un vale 2. Un vale 2. Vale
43:513. Do vale 3. ¿Ya? O sea, esta columna
43:58eh
43:59de aquí
44:03y esta columna de acá están
44:06relacionadas.
44:11Esto me está quedando en una página
44:12aparte.
44:16están relacionadas por un +s 1. Ah, o
44:20sea,
44:22el techo de n+ 1 medios
44:28es igual al piso n medios
44:33+ 1.
44:36Okay.
44:38Entonces, eh,
44:42¿qué podemos eh decir? A partir de aquí,
44:47como el techo n + 1/2 es lo mismo que
44:51el, perdón, el piso n + 1/2 es igual al
44:54techo de medio, ya la las dos que están
44:57encerradas en naranja,
44:59eso quiere decir que
45:02esto se cancela con esto,
45:07¿okay?
45:10porque el sub índice es exactamente el
45:11mismo. Ahora, eh, por supuesto, entre
45:14paréntesis, hablando de rigurosidad,
45:18esto tampoco una demostración rigurosa,
45:19¿no? Pero una vez que hemos descubierto
45:22la relación, nuevamente, no cuesta nada
45:24demostrarla e
45:27considerando eh dos casos, el caso n
45:30par, el caso n impar, ¿ya? O sea, uno
45:33sustituye n por un número de la forma 2K
45:36o lo sustituye por la forma un número de
45:38la forma 2k + 1 y en cada uno de los
45:41casos uno puede demostrar estas
45:42identidades y y por lo tanto son válidas
45:44siempre, ¿va? Así que eso se los puedo
45:47dejar de ejercicio. Y ¿qué pasa con los
45:49otros dos subíndices?
45:51Bueno, que el
45:54esos dos en ese caso no son iguales,
45:56sino que hay una diferencia de uno, ¿no
45:57es cierto? O sea, lo que ocurre es que
45:58este subíndice de aquí es igual al piso
46:02de n medios,
46:05pero más 1.
46:08Por lo tanto,
46:14por lo tanto, el d sub n
46:19quedó como a su piso de n medios.
46:30+ 1
46:33menos
46:35a su piso de medios,
46:41o sea, es la diferencia de dos valores
46:43consecutivos.
46:46Ah, y me está me está olvidando una
46:49cosa. Hay un más un aquí en la primera
46:52línea aquí.
46:56Hay un más uno ahí que no se canceló con
46:57nada, ¿okay? Así que ese hay que hay que
47:00respetarlo. Más un.
47:04Okay. Bueno, resulta que esta diferencia
47:08entre dos valores de la función A es la
47:10diferencia entre dos valores
47:11consecutivos. Por lo tanto, es un D,
47:14pero es un D sub piso de n medios.
47:19Esto aquí es de sub piso de n medios.
47:26Okay. Por lo tanto, eh
47:31yo tengo que d su n
47:34es igual a 1
47:37más d su piso de n medios.
47:42¿Y cuánto vale? ¿Con qué condición de
47:44borde? ¿Cuánto vale de un?
47:47Ya, de uno es eh
47:54es a sub2 men a sub1, ¿ya? A sub dos,
47:59eso habría que ir a verlo en las
48:00planillas, ¿no es cierto? Eh, a sub era
48:034 y a sub un es un, o sea, de sub un
48:05vale 3. Esa es nuestra condición de
48:07borde.
48:11Entonces, ahora lo que yo necesito es
48:14poder resolver esta ecuación. que es más
48:17simple que la anterior porque tiene la
48:19incógnita aparece una sola vez al lado
48:22derecho. Ya no es trivial, pero tampoco
48:25es imposible.
48:27Entonces vamos a hacer lo siguiente. A
48:29ver, tenemos espacio. Sí, vamos a hacer
48:31lo siguiente. Vamos a hacer una tabla de
48:33valores.
48:36Poner el n
48:39y el t sub n.
48:45Ya. Y vamos a hacer, ya vamos a hacer
48:48del 1 al 15. Hay espacio. Sí. Espero. 1
48:512 3 4 5 6 7 8
48:599 10 11 12 13.
49:09Ya. Entonces,
49:12de sub un vale 3, ¿no es cierto? ¿Cuánto
49:15vale de sub dos? Es 1 + de sub 1.
49:24Ya, porque si n vale 2, n medio vale 1.
49:27Entonces de sub un pero de su un ya lo
49:29sabemos vale tres, o sea, por lo este
49:30vale cuatro.
49:33¿Cuánto vale de sub tres? es eh d sub n
49:37medios en este caso eh sería 1,5 pero se
49:41baja de su 1 + de su 1, o sea, también
49:45vale 4.
49:48¿Cuánto vale de sub 4? De n medios eh
49:52vale 2, ¿no es cierto? Entonces sería 1
49:54+ de sub que sería 5. Ya este vale 5.
49:59Para el 5
50:01esto sería eh el medio sería 2,5 baja 2
50:05sería 1 + 2 sub 2, o sea 5.
50:10Para el 6 sería 1 + d sub 3, pero un sub
50:133 valía 4, o sea, este sigue valiendo 5
50:17y el 7 sería 3,5 baja 3 1 + 2 sub 3
50:21nuevamente 5. Fíjense que se están
50:23formando grupos aquí, ¿no es cierto? Ya,
50:26o sea, tenemos aquí
50:30tenemos aquí un grupo de los que valen
50:32tres,
50:34aquí un grupo de los que valen cuatro,
50:36aquí un grupo de los que valen cinco,
50:40¿ya? Y
50:42el tamaño de cada grupo se va
50:44duplicando. El primero tenía tamaño uno,
50:46el segundo tamaño dos, el otro tamaño
50:48cuatro. Entonces, el que viene tendría
50:49que tener tamaño ocho. Ah, y
50:51efectivamente así va a ser. Pues fíjese
50:53lo que pasa.
50:56El 8 sería 1 + d sub 4, o sea, 6. Para
51:00el 9 es 4,5 bajado 4, o sea, 6. Para el
51:0410 es 5. 1 + de sub 5, pero de sub 5
51:06vale 5. Por lo tanto, esto es 6. Y se
51:10fijan, lo que ocurre es que cada uno de
51:13los que están aquí genera dos acá.
51:17Ya, el cuatro de aquí generó al 8 y al
51:20nu, el cinco va a generar al 10 y al 11.
51:23El 7 va a generar al 14 y al 15. Y todos
51:25valen seis.
51:32Ya, hasta que
51:37hablaríamos un pelito más. 16.
51:41Eh,
51:44el 16 sería eh 1 + d sub 8. Este sería
51:487. Ya. Y ustedes pueden de aquí
51:52generalizar que el grupo de los que
51:54valen siete eh va a tener 16 elementos.
51:58¿Ya? Entonces, tenemos que tener una
52:01forma de de representar esta función,
52:04¿okay?
52:06Y esa forma la vamos a obtener
52:10acudiendo a los números binarios.
52:16Vamos a hacer acá a la izquierda,
52:21vamos a escribir el número n,
52:26pero en binario.
52:29Ya no sé cómo están ustedes,
52:34eh.
52:35defamiliarizados con la anotación
52:37binaria,
52:38pero vamos, si hay alguna duda me
52:43interrumpen y me preguntan. Ya, el uno
52:45en binario se escribe uno, ahí no hay
52:47ningún problema. El dos se escribe 1,
52:50¿no es cierto?
52:52Porque el uno a la izquierda significa 2
52:54y el 0 le agrega 0 y el 3 es 1 1.
53:00El uno a la izquierda significa dos, el
53:01uno a la derecha significa uno. Sumados
53:03dan tres. El cuatro a ese ya necesito un
53:07dígino más. 100
53:10y este sería 10
53:121
53:141
53:18Ya. Y el ocho necesita un dígito más. 1
53:281
53:3010 1
53:3210 1
53:341 1
53:361 1
53:401
53:421 1 1 1 1
53:46y 1 1 1
53:50y el 16 requeriría un dígito más 1
53:57y así sucesivamente.
53:59Ya.
54:03Y ustedes pueden ver que eh se forman
54:07grupos, ¿no es cierto? el grupo de los
54:09que son de tamaño uno más el grupo de
54:12los que son de tamaño dos, el grupo de
54:14los que son de tamaño tres, el grupo de
54:16los que son de tamaño cuatro,
54:20el grupo de los que son de tamaño cinco
54:22y así sucesivamente.
54:24Y esos grupos corresponden exactamente a
54:27los grupos que aparecen en la función de
54:28su n,
54:30¿ya?
54:32Eh,
54:35se suele denotar nudos de n
54:39al número
54:42número de bits
54:46necesarios
54:51para
54:54representar
54:58al número n.
55:05Entonces, N2 de 1 es 1,2 de 2 es 2, de 3
55:09es 2. Nudos de cuatro pasa a ser tres
55:12hasta el siete. Nudos de ocho pasa a ser
55:14cuatro y así sucesivamente. ¿Ya?
55:17Entonces
55:19y eh
55:23y se sabe que n
55:27de n
55:29es el techo
55:32del log 2 de n + 1.
55:41es una función logarítmica porque eh
55:46aumenta en uno cada vez que su argumento
55:48se duplica, ¿no es cierto? Ya. Y la cosa
55:51es cuándo exactamente se produce la la
55:54transición.
55:56Eh,
55:58y
55:59es eh el log 2 de n + 1 porque eh por
56:04ejemplo aquí
56:07eh
56:11el
56:14log 2 de 3
56:17eh con techo, ¿no es cierto?
56:20es mayor que mayor que 1, entonces sube
56:23a 2. El log 2 de 4 es exactamente 2
56:30el
56:32es de + 1. Así que aquí sería el log 2
56:34de 5 que ya es mayor que dos, por lo
56:37tanto sube a 3, etcétera. ¿Ya? O sea, la
56:39transición se produce exactamente donde
56:41esté indicado.
56:43Eh, y por lo tanto,
56:47no,
56:49mejor escribo con el lápiz y no y no con
56:52el láser. Y por lo tanto, eh, D su N
57:00es Ah, bueno. y
57:04y además los valores
57:07e
57:14los valores de su n son dos más que el
57:18n2, ¿no es cierto?
57:21Por ejemplo, este vale tres y y el n2
57:24vale un acá el n2 vale 2 y estos valen
57:26cuatro. Acá el n2 vale tres y la función
57:28vale cinco y así sucesivamente. Siempre
57:31dos más. Ah. Así es que tengo 2
57:36más techo de log 2
57:41de n + 1.
57:54Ya.
57:55Donde esto es nud de n es lo mismo.
57:59Okay.
58:01Fan está ahí.
58:04Entonces ahora
58:07con eso tenemos que el tenemos que
58:10recordar que t sub n era a sub n + 1 men
58:15a su n.
58:17Ya.
58:20Eso implica que el t sub n - 1 es igual
58:24a sub n
58:26menos a su n - 1. ¿Y por qué lo escribo
58:29así? Porque ahora yo puedo despejar a su
58:31n
58:34es de su n - 1
58:41más
58:43a sub n - 1.
58:48Y ahora yo puedo desenrollar.
58:50A ver, mejor lo escribo al revés.
58:56No, no está bien. Ya. Entonces,
58:58desenrollando
59:05a su n va a ser de su n - 1
59:09más a su más su n - 1, pero a su n - 1
59:13es de su n - 2
59:16más a su n - 2.
59:21Esto es d y esto va a ser d sub n - 1 +
59:26d sub n - 2 + t sub n - 3
59:32+ a sub n - 3.
59:37Ya. Y esto yo lo puedo seguir hasta que
59:40sea d sub n - 1
59:46+ d sub n - 2
59:48-2.
59:50más
59:52hasta de 1 más a su
59:59ya y
1:00:02a su uno vale uno.
1:00:06Okay.
1:00:12Por lo tanto,
1:00:16a su n
1:00:19es 1
1:00:21más la suma de los de sub jor
1:00:28igual que j menor o igual que n - 1.
1:00:31Aquí tengo
1:00:34mi solución para a sub n
1:00:38y eso sería igual a 1 más la sumatoria
1:00:44para 1 menor o igual que j menor igual
1:00:46que n - 1
1:00:49de
1:00:50la fórmula que tenemos para el de su
1:00:54ní que es 2 más el nudos de
1:01:15Y eso es 1. La sumatoria aplicada al 2
1:01:19es 2 veces n - 1.
1:01:26¿Ya? Eh, más la sumatoria para 1 menor o
1:01:31igual que j menor igual que n - 1 de
1:01:35nudos de j.
1:01:37Okay, ya. Esto de aquí es eh 1 + 2n - 2,
1:01:45o sea, sería 2n - 1.
1:01:59Okay,
1:02:02ya
1:02:03estamos cerca, pero
1:02:07pero falta un poquito todavía. Ya.
1:02:09Bueno, pero pongámoslo el limpio. A su n
1:02:12va a ser 2n - 1 más la sumatoria de los
1:02:17nudos de j
1:02:20para 1 menor o igual que j menor igual
1:02:22que n - 1. Ya ahí tenemos eso.
1:02:28Y ahora la cosa es cómo calcular esta
1:02:31sumatoria.
1:02:35Si nosotros volvemos a nuestra tabla
1:02:37aquí
1:02:39y vemos un n, ¿ya? Por ejemplo,
1:02:44n
1:02:46= 12,
1:02:48¿ya?
1:02:50Eso eh
1:02:53la sumatoria para ese valor tomar aquí
1:02:56en láser. Entoncesamos n = 12
1:02:59va a tener que ser
1:03:021 + 2 + 2 + 3 + 3 + 3 + 3 + 4 + 4 + 4 +
1:03:094 hasta aquí hasta el 11
1:03:12sin incluir al 12.
1:03:14Ya hay que hacer esa
1:03:17sumatoria fila por fila, ¿no? Ahora, si
1:03:21yo sumo 1 + 2 + 2 + 3 + 3 + 3 + 3 + 4 +
1:03:254 + 4 hasta un cierto punto, lo que
1:03:28estoy calculando es el área el área
1:03:30azul. O sea, si cada bit que aparece ahí
1:03:33en azul es de un lo imaginamos como un
1:03:35cuadrito de uno por un, ¿ya? Lo que yo
1:03:38necesito es calcular el área azul.
1:03:45Supre uno, esto tiene área dos, área 2,
1:03:48área 3, 3 4 4,
1:03:52¿ya? Entonces, veámoslo. Lo vamos a ver
1:03:54en términos de de cálculo de área. ¿Ya?
1:03:58Entonces,
1:04:03esto de aquí.
1:04:15Esto de aquí
1:04:19corresponde al área azul.
1:04:23En el siguiente
1:04:25gráfico es que yo si se fijan lo que
1:04:29tenía era
1:04:311 2 3 etcétera,
1:04:35hasta un cierto n - 1 y un n. Ya.
1:04:42Y aquí
1:04:43yo tengo
1:04:47frente al uno tengo un área de tamaño,
1:04:50perdón, eso esto trata de ayudarme y no
1:04:54ya tengo un área de tamaño uno aquí
1:05:00y frente al dos y frente al tres tengo
1:05:02áreas de tamaño dos.
1:05:09Ya. Y del cuatro en adelante
1:05:13tengo áreas de tamaño tres
1:05:24y así sucesivamente, ¿no es cierto?
1:05:28Hasta llegar a aquí.
1:05:39Entonces, el
1:05:42la suma de los nudos de J es es el es el
1:05:45área azul que está marcada ahí.
1:05:47Entonces,
1:05:49la
1:05:51si yo voy línea por línea subando área,
1:05:55eso resulta super complicado y y no está
1:05:58claro que me vaya a llevar a ninguna
1:05:59parte.
1:06:01Así es que lo que vamos a hacer es
1:06:02calcular el área azul, pero por
1:06:04diferencia. Lo que vamos a hacer, le
1:06:07vamos a agregar todo lo que le falta.
1:06:17Le vamos a agregar
1:06:20eso y luego se lo vamos a quitar.
1:06:23Ya. Entonces el el área azul
1:06:29va a ser igual
1:06:35al área completa. Primero, el área
1:06:37completa tiene ancho los dos de N, ¿no
1:06:41es cierto?
1:06:42Porque el el ancho lo da el último y el
1:06:46último, perdón, tiene techo de log 2 de
1:06:49porque el ancho, como les digo, lo da el
1:06:50último. Como el último es n - 1 e y el
1:06:55ancho es el log 2 de n + 1 con techo,
1:06:59entonces sería techo de log 2 de n
1:07:04y multiplicado por el número de de filas
1:07:08que es n - 1. Así que sería n - 1
1:07:15por techo
1:07:17de log 2 de,
1:07:21perdón,
1:07:25techo.
1:07:27Okay.
1:07:28Y a eso hay que restarle el área
1:07:32naranja.
1:07:34Ya. Y el área naranja es de la forma
1:07:40uno. El área naranja no la vamos a
1:07:43restar horizontalmente, la vamos a
1:07:44restar verticalmente.
1:07:47Entonces
1:07:49vamos a tomar esto
1:07:52y esto y así sucesivamente hacia abajo.
1:07:56¿Ya? Entonces, la verticalmente, si
1:07:59vamos derecha, izquierda, este de aquí
1:08:01tiene tamaño uno, este tamaño tres, el
1:08:03siguiente tendría tamaño siete y así
1:08:05sucesivamente. Son todas potencia 2 - 1,
1:08:08¿ya?
1:08:10Eh,
1:08:11y son exactamente potencias de 2 - 1,
1:08:14así que menos sumatoria
1:08:17de números de la forma 2 a la j - 1, ya
1:08:23desde 0
1:08:30menor o igual que j menor o igual que
1:08:35eh
1:08:38y ahí Les voy a pedir que ustedes lo
1:08:40chequeen con cuidado, eh, porque el
1:08:42límite superior, eh, si uno lo calcula
1:08:45bien, es el log 2 de n
1:08:48- 1. Ah, justamente el el último antes
1:08:52de
1:08:54es el del grupo anterior al grupo en el
1:08:56cual estoy en donde estoy cerrando esto
1:08:59ya. Y por lo tanto y y ahí tengo mi
1:09:02sumatoria.
1:09:06Ah, y
1:09:10esta sumatoria.
1:09:15Okay, veamos aquí. Entonces, por lo
1:09:18tanto, aquí ponemos negro.
1:09:22El a sub n, ¿cómo estamos? Sí, ya.
1:09:27A sub n.
1:09:29Habíamos quedado que a sub n era 2n - 1
1:09:32más la sumatoria. Entonces sería 2n - 1
1:09:37más la sumatoria.
1:09:40La sumatoria
1:09:42es eh
1:09:47si tomamos aquí el
1:09:50este signo menos con este signo menos da
1:09:52signo más, por lo tanto se suma uno,
1:09:55¿cuántas veces? Logos de n veces,
1:09:59¿ya?
1:10:01Eh,
1:10:06ah, bueno, me faltó primero el anterior,
1:10:08el está el
1:10:12que está en negro allí arriba, n - 1,
1:10:15techo de log 2 de n.
1:10:18Ya. Y a continuación,
1:10:23eh, como les decía, si tomamos el el
1:10:26signo menos y el -1 dentro de un y eso
1:10:28se suma los dos de n veces, eso me suma
1:10:31los
1:10:34log los logros de n
1:10:38-2 a la j,
1:10:41¿ya?
1:10:42eh entre 0 y log 2 de n - 1 me va a dar
1:10:472 a la suma de potencia es de 2, ¿no es
1:10:51cierto? es 2 la a la siguiente potencia
1:10:54-1, o sea, 2 a techo de log 2 dn -1,
1:11:00entonces -2 elevado a techo de log 2 dn
1:11:13y todo eso -1, pero está consigo menos,
1:11:15así que es más un.
1:11:19Así es que bueno, eh, ya este -1 se
1:11:22cancela con este + 1. Estos dos se
1:11:25juntan ya. Y por lo tanto
1:11:30hasta al final no está quedando tan tan
1:11:32horrible. A su n es igual a 2n
1:11:38más n
1:11:42techo de los 2n.
1:11:47-2 elevado al techo de log 2 dn.
1:11:56Ya. Eh, se
1:12:01nos
1:12:03y nos está un poquito corto de tiempo,
1:12:05así es que eh voy a dejar que ustedes
1:12:09eh
1:12:11comprobarlo
1:12:12numéricamente
1:12:15porque nosotros tenemos los valores del
1:12:17de la sucesión A, ¿no es cierto? Así que
1:12:20lo podemos comparar con lo que esto
1:12:21predice y debería dar lo mismo
1:12:23numéricamente. Así que es una manera de
1:12:25chequear que no nos hemos equivocado
1:12:27eh en todas estas derivaciones.
1:12:30Y bueno, y ustedes se acuerdan lo que
1:12:32que estudiamos era la diferencia.
1:12:33Entonces queremos estudiar la
1:12:34diferencia.
1:12:48llamémosla delta sub n a la diferencia a
1:12:52sub n - tdn.
1:12:56Ya. Por lo tanto, esto va a ser a su n -
1:13:01n factor de 1 + log 2 de n. Eso es lo
1:13:05que era la función t, ¿no es cierto?
1:13:07Función bien simple. Y ahora sustituyo
1:13:10lo que es a su n. Así que sería
1:13:14eh,
1:13:17a ver, a su n es 2n, pero acá tengo un -
1:13:21n, así que me queda un solo n
1:13:26más
1:13:28eh
1:13:32de la subn poro log 2 de n
1:13:37por log 2 de n sin techo, así que sería
1:13:39n por techo de log 2 dn
1:13:45- log 2 dn sin techo ya y
1:13:52- 2 a la techo de log 2 dn n
1:14:03así me qued [grito ahogado]
1:14:06pero
1:14:09dos al techo de los dos de N.
1:14:15Yo lo puedo escribir de una manera más o
1:14:17menos artificiosa diciendo que es n * 1/
1:14:21por n
1:14:23al techo de los dos de n.
1:14:26¿Ya?
1:14:28¿Y por qué hizo hice eso? Porque el 1
1:14:31partido por noo escribir como 2 a la men
1:14:35log 2 de n.
1:14:38ya eh sin techo
1:14:41y eso va a quedar arriba en el
1:14:43exponente. Entonces va a quedar 2
1:14:45elevado al techo de log 2 de n
1:14:50menos log 2 de n sin techo.
1:14:53y y con todos estos
1:14:57todo esto que hemos hecho,
1:14:59resulta que entonces delta n
1:15:03queda de la siguiente manera, queda como
1:15:05n
1:15:08más n
1:15:11factor de techo de log 2 de n
1:15:16log 2 de n
1:15:20y el y el menos
1:15:25y el -2 al techo de logros de n con esto
1:15:29que hice me queda - n * 2 elevado al
1:15:33techo de log 2 de n
1:15:38- log 2 de n
1:15:42y
1:15:45de inmediato se comprueba una cosa de lo
1:15:48que habíamos de nuestra conjetura, que
1:15:50es que hay un factor de n efectivamente
1:15:52Hay un factor de n
1:15:54porque yo lo puedo sacar de aquí y me va
1:15:56a quedar más el techo de log 2 de n
1:16:01- log 2 de n
1:16:05y - 2 elevado al techo de log 2 de n
1:16:13- log 2 de n,
1:16:17se fijan. Pero hay un factor de n
1:16:19afuera. Y
1:16:22esto
1:16:24yo lo podría escribir
1:16:27de la forma. Fíjense que
1:16:30fíjense que
1:16:35aquí tengo techo de los 2 de n menos
1:16:37logros de n. Acá también tengo techo los
1:16:392 de n menos los 2 de n. Por lo tanto,
1:16:42esto yo lo podría escribir
1:16:47eh
1:16:49como
1:16:57a ver eh
1:17:01cómo como cómo
1:17:06como como una función
1:17:10teta de techo de logros de n
1:17:17menos logr de n
1:17:22donde
1:17:25teta de x es 1 + x - 2 a la x,
1:17:35¿no es cierto?
1:17:37Si yo defino teta como esa función
1:17:41y ahí sería teta de techo de log 2 de n
1:17:44- log 2n. En realidad no debería
1:17:47llamarlo teta porque no es la misma que
1:17:48dije antes. Cambiamos de nombre.
1:17:51Pongámosle fi,
1:17:56no, pongámosle f. Ya corremos eso.
1:18:02Ups.
1:18:04Corremos eso.
1:18:06Okay.
1:18:08Pongámosle
1:18:09F.
1:18:12Ya.
1:18:14Y
1:18:18claro, porque teta era teta de log 2 de
1:18:22n. Ah, eh, una le diferencia. Ya, pero
1:18:26esa es nuestra función f.
1:18:28Entonces, eh
1:18:33tenemos que ver cómo se comporta esta
1:18:34función f(x), ¿ya? Y eso
1:18:39nos alcanza el tiempo para verlo.
1:18:42Volviendo a nuestra
1:18:45a nuestra planilla de cálculo,
1:19:10Entonces
1:19:12vamos aquí
1:19:16defin
1:19:31- 2 elevado x.
1:19:35Okay.
1:19:40Entonces, ahora yo podría decir plot.
1:19:45El argumento de f siempre va a estar
1:19:46entre 0 y 1. Ah, porque es el techo del
1:19:48logaritmo menos el logaritmo y eso la
1:19:51diferencia nunca es más que uno. Puede
1:19:54ser cero si es que es una potencia de
1:19:55dos exacta, pero nunca va a ser más que
1:19:57uno. Entonces, eh, plot de f(x)
1:20:04entre 0 y 1.
1:20:10Y ahí tenemos exactamente la forma de de
1:20:14la de estas funciones. Son esas ya. Y eh
1:20:19y ahora
1:20:23lo que podemos ver es e
1:20:27dónde eh esta función alcanza su máximo.
1:20:35Uno podría pensar que es simétrica, ¿no
1:20:37es cierto? La verdad es que no es
1:20:38exactamente simétrica. Eh, para
1:20:41encontrar el máximo, yo lo que puedo
1:20:42hacer es derivar, ¿no es cierto? Yo digo
1:20:45y es igual a la derivada
1:20:49de
1:20:52f(x)
1:20:54respecto de x.
1:20:57Ya, veamos cuánto vale y
1:21:02vale -2 la x los 2 + 1. Y ahora yo puedo
1:21:07resolver.
1:21:09decir que sol resuelve la ecuación I =
1:21:12ig 0
1:21:16para eh x
1:21:21y está es menos log de log de 2 parido
1:21:26por log de 2 en ese valor es donde
1:21:28alcanza su máximo. ¿Ya?
1:21:31Entonces, e
1:21:34digámosle que, a ver, tomemos esto.
1:21:40No sé si esto va a funcionar muy bien,
1:21:42pero tomemos esto. Anotémoslo aquí
1:21:49no funcionó muy bien, pero puedo
1:21:50arreglar. Aquí se saltó un símbolo de
1:21:52división
1:21:54y me da la impresión que esto no es un
1:21:56menos. Sí. Ya. Punto n para que lo
1:22:01evalúe.
1:22:050.5287,
1:22:07o sea, no está exactamente en el 0.5 el
1:22:10máximo. ¿Ya? ¿Y cuánto es el valor en el
1:22:13punto máximo? Recuerden que habíamos
1:22:15dicho que era algo así como 0.08.
1:22:18Veamos cuánto es el valor del punto
1:22:20máximo. Entonces, eh calculemos f
1:22:25en el anterior. Lo anterior es subrayado
1:22:28aquí en en el último valor calculado es
1:22:32subrayado en eh se en M era por cento
1:22:390.086071.
1:22:43Exactamente. Ya. Así es que con esto
1:22:47hemos comprobado que era era correcta
1:22:49nuestra conjetura. Ya volvamos a a
1:22:53nuestra otra pantalla.
1:23:11Ya. Por lo tanto,
1:23:17entonces eh la función fción
1:23:28de esa forma donde esto está en el 0
1:23:3452
1:23:3687, etcétera.
1:23:39Y esto de acá
1:23:41está en el punto
1:23:430.08607.
1:23:48[carraspeo] Exactamente.
1:23:50Ya. Y por lo tanto se ha comprobado
1:23:53nuestra
1:23:55nuestra conjetura que a su vez n es el t
1:23:59de que es n 1 + log 2 de n.
1:24:04Y la diferencia es una pequeña función
1:24:07de log 2 dn periódica de log 2 dn.
1:24:13Eso. Muy bien. Y con eso hemos
1:24:18encontrado lo que queríamos en esta
1:24:20clase. Nos queda como un 2 minutos para
1:24:23alguna pregunta que tengan,
1:24:29¿no? Muy bien. Pues muchas gracias. Con
1:24:32eso concluimos la clase de hoy.
1:24:38Yeah.