Full transcript
0:04Muy bien, buenos días. Eh,
0:07en esta clase vamos a continuar viendo
0:10algunos ejemplos que motivan un poco lo
0:13el enfoque que vamos a tener en el
0:15curso. Así que en en estas dos o tres
0:19primeras clases no hay eh un enfoque
0:22generalista, sino que más bien eh por la
0:24vía de presentar algunos problemas que
0:26espero que sean interesantes y que nos
0:27vayan ayudando a a tomar un poco la
0:32práctica que vamos a tener en esta en
0:35esta cátedra. Y bueno, el caso pasado
0:38ustedes ya vieron tomado un problema que
0:39era llenar un álbum así como qui dice el
0:41álbum del de la Copa Mundial, ¿ya?
0:46Y hoy día vamos a tomar un programa
0:48totalmente diferente que es la búsqueda
0:57del máximo
1:03o del mínimo
1:08eh entre neros.
1:21Supongamos que tenemos una lista de
1:22números, por ejemplo, 3
1:265
1:336, ¿no? Y para evitar ambigüedades,
1:36vamos a suponer que tenemos que son
1:38todos distintos
1:40y lo que queremos es encontrar el
1:43máximo. ¿Okay? Entonces, una manera de
1:47encontrar el máximo es
1:52para encontrar el máximo.
2:01Podemos recorrer la lista de izquierda a
2:03derecha.
2:13de izquierda a derecha, ¿no es cierto?
2:16Y
2:18voy a tomar un destacador,
2:23a ver, aquí mejor. Y marquemos en verde
2:30lo que va pasando cuando yo voy
2:32recorriendo la lista de izquierda a
2:33derecha. Si yo voy de izquierda a
2:34derecha buscando el máximo, eh,
2:36obviamente el primer elemento que yo me
2:38encuentro por el camino
2:41e es un candidato a ser el máximo. Ah,
2:44hasta el momento no hemos visto nadie
2:45que sea mayor que él, ¿no es cierto? Eh,
2:49trivialmente. Luego vemos el uno y el
2:51uno eh, no es candidato al máximo porque
2:54es menor que tres, ¿no es cierto? Pero
2:56aparece el cinco. El cinco sí es
2:57candidato a ser el máximo. Ya.
3:00Eh, y desplaza al tres. Ah, le quita su
3:04lugar al tres. El dos, menor que cinco.
3:07El cuatro no menor que cinco. El ocho sí
3:10mayor que cinco, ¿no es cierto?
3:11Entonces, ahora es el ocho. Eh, siete,
3:15no, nueve, sí.
3:18Seis, no, ¿no es cierto? Entonces, el
3:21resultado de todo este proceso fue que,
3:23bueno, obviamente el máximo es el nueve,
3:28¿ya? Eh, pero por el camino encontramos
3:32eh un subconjunto de los elementos que
3:36son los máximos locales de izquierda a
3:38derecha.
3:53ese e y ¿cuántos fueron? Fueron cuatro,
3:56¿no es cierto? Entonces, el número de
3:59máximos locales que encontramos de
4:00izquierda a derecha fueron cuatro en
4:02este caso. Ya. Cada vez que un apareció
4:06un elemento que desplazó al al anterior
4:10máximo. ¿Okay? O sea, son son máximos
4:13tentativos, son candidatos a ser a ser
4:16el máximo. El último de ellos, el que
4:19sobrevive a todo este proceso, ese es el
4:21máximo, ¿no es cierto? Pero los otros
4:23fueron máximos locales eh que encontré
4:26por el camino. Okay. Esto es eh a menudo
4:31eh usamos un una metáfora del tenis para
4:36esto. Eh eh esto es como que yo quiero
4:39encontrar el campeón de un club y lo
4:41hago eh de la siguiente manera. Eh,
4:44supongo que tengo solo una cancha en
4:45donde puedo jugar, no puedo jugar
4:47partidos en paralelo. Entonces, pongo a
4:50un jugador en la cancha y le digo usted,
4:52hasta que no se demuestre lo contrario,
4:53es el campeón. ¿Ya? Y empiezan a
4:55desafiarlo. Entonces, está el tres en la
4:57cancha, aparece el uno y el tres le gana
5:00el uno. Eliminado el uno sigue siendo
5:02campeón el tres, pero ahora aparece el
5:04cinco, que le gana el tres. Entonces
5:07eliminado el antiguo campeón y como
5:10nuevo campeón queda el cinco y aparece
5:12el dos que desafía el cinco eliminado,
5:14el cuatro que desafía el cinco
5:16eliminado, el ocho que desafía al cinco
5:18y le gana. Entonces ahora el cinco del
5:20eliminado y así se fijan. Entonces es
5:22como un campeonato y lo que estamos
5:23marcando en verde ahí son quienes
5:26estuvieron durante algún momento como
5:28campeones de del club. Por supuesto,
5:31cuando se acaban todos los partidos, el
5:32que queda, el que sobrevive en la cancha
5:34es el campeón. ¿Ya? ¿Y qué habría pasado
5:36si yo estuviera encontrando eh el
5:39mínimo? Ya.
5:47Eh,
5:51hacemos lo mismo, tomemos eso otro
5:53color.
5:56Okay. Eh, ya está. Entonces, igual
6:01partimos con el tres, ¿no es cierto?
6:04Hasta que no se muestre lo contrario, el
6:06tres es también el mínimo. Y aparece el
6:08uno que es menor que el tres, así es que
6:11le quita el título.
6:14Y bueno, apareció el uno. Ah, y ustedes
6:17ya, ojo, ven que nadie más le va a
6:19quitar el título de ser el mínimo, ¿no
6:20es cierto? El dos no, porque es mayor,
6:22el cuatro no, el siete no, el seis no. O
6:24sea, en este caso,
6:27el
6:29mínimo es uno
6:33y el número de mínimos
6:41de izquierda a derecha
6:45en este caso fue dos, ¿no es cierto?
6:50Entonces, lo que vamos, lo que queremos
6:52estudiar aquí es son estas últimas eh
6:56estos últimos indicadores, el número de
6:59máximos locales izquierda derecha o el
7:00número de mínimos locales de izquierda
7:02derecha. por simetría, eh, da lo mismo.
7:05Vamos a estudiar el máximo. Entonces, el
7:08problema
7:12estudiar cómo se comporta
7:17el número de máximos locales.
7:29Ya. ¿Cuáles son los valores extremos?
7:37¿Cuánto es el el mínimo valor
7:42que puede tener este parámetro?
7:46Uno.
7:47Uno, ¿no es cierto? Sup está buscando el
7:49máximo. Entonces, cuando el primero que
7:50aparece es el campeón,
7:53nadie le logra ganar. Y hubo solo un un
7:58un mínimo local de izquierda derecha.
8:01Eh, ¿cuánto es el máximo?
8:04El tamaño de la lista.
8:07Exacto. N, digamos, ¿no es cierto? Eh,
8:09¿por qué sería eso?
8:13Porque no hay más de elementos en la
8:15lista y bien puede ser el último que
8:17revisemos.
8:19Eh, y ya, pero si fuera el último que
8:21revisaras ahí podría ser uno, suponte, o
8:24dos, digamos. O sea, si la, digamos, si
8:27la lista fuera
8:29completamente
8:31completamente creciente o completamente
8:33decreciente,
8:35correcto.
8:35Vamos a obtener
8:36correcto. Si si la lista es
8:38completamente creciente, en este caso
8:40que estamos buscando el máximo, cada en
8:42cada partido el desafiante le va a ganar
8:44al campeón, ¿no es cierto? Entonces va a
8:46haber n
8:48jugadores que en algún momento
8:49detentaron el título de ser el campeón
8:52hasta el momento. ¿Ya? ¿De acuerdo?
8:54Entonces, el máximo es n. Ya. Eh, y pero
8:56lo que nos interesa más que nada aquí es
8:59calcular el promedio.
9:04Ya. Si el mínimo es uno, el máximo es n,
9:06uno podría sentirse tentado decir,
9:08bueno, el promedio será n medio. Ah, eh,
9:12en realidad n + 1/2 el promedio entre
9:13los dos extremos. Pero vamos a ver eh si
9:17eso es cierto o no. Ah, entonces para
9:20eso vamos a a usar un enfoque inductivo
9:25o recursivo, según como quieran ustedes
9:29visualizarlo.
9:31Eh, vamos a definir cuando uno no conoce
9:34algún alguna cantidad, algún parámetro,
9:37lo que más ayuda es ponerle nombre.
9:40Entonces, digamos que eh sea
9:45a su n
9:47el número
9:50esperado
9:57de máximos locales
10:00de izquierda a derecha.
10:05Entonces, ¿no es cierto? Esto depende de
10:07n
10:10como notación. Eh, a veces eh vamos a
10:13usar notación como de sucesión, en este
10:16caso a sub n, ¿no es cierto? A sub n es
10:18una sucesión. Eh, pero a veces vamos a
10:21usar una notación como de función. Por
10:23ejemplo, FDN con n entre paréntesis
10:26también es una anotación válida para lo
10:27mismo. Son eh
10:32depende del gusto. Ah eh una sucesión,
10:35por supuesto, ustedes saben que es es
10:37una función de los naturales a al al
10:41a lo que sea el conjunto al cual
10:44pertenecen estos valores. Eh, ya.
10:46Entonces, si bueno, nosotros ya sabemos
10:49algo sobre esto, por ejemplo, sabemos
10:51cuánto vale a sub un,
10:54¿no es cierto?
10:56Eh,
10:59de hecho, quizás nos conviene más eh
11:03comenzar antes incluso. Ah, vamos,
11:08comenzamos con la subcero.
11:12Si el conjunto fuera vacío, ¿cuántos
11:14máximos locales de izquierda a derecha
11:15encontraríamos por el camino?
11:19Cero.
11:19Cero, ¿no es cierto? Ninguno. Así que ya
11:21tenemos un valor inicial. ah una
11:23condición de borde y para encontrar eh a
11:27sub n vamos a buscar una ecuación que en
11:30este caso va a ser una ecuación de
11:31recurrencia, ¿no es cierto? Entonces
11:33vamos a hacer lo siguiente. Mire eh
11:35supongamos que yo tengo una lista
11:38aquí tengo una lista de largo n
11:43ya al a la cual quiero encontrarle el aú
11:48n.
11:50Pero viendo inductivamente, voy a
11:52suponer que si la lista hubiera sido de
11:56largo n - 1,
12:01yo ya sabría cómo encontrar a su n - 1.
12:05Entonces, quiero ver
12:08si eh
12:11en base a ese conocimiento que yo tengo
12:13puedo encontrar cuánto valea su n, ¿no?
12:15Entonces, estoy viendo por inducción,
12:16¿no es cierto? Si ya conozco la solución
12:18para n - 1, ver si puedo eh generar una
12:21solución para su n, para n. Entonces,
12:24conozco la solución para una lista de
12:26tamaño n - 1 y quiero ver si puedo
12:28generar la solución para la lista de
12:29tamaño n. Y como yo tengo la condición
12:32de borde, entonces por inducción yo
12:34podría tener para cualquier n. ¿Okay?
12:37Eh, entonces, ¿qué puedo decir sobre
12:40esto?
12:42Eh,
12:44mi pregunta es, ya supongamos que yo
12:48tengo eh
12:52a sub n - 1. Entonces, ¿cuánto sería sub
12:54n? Bueno, el número de máximos locales
12:57de izquierda a derecha de partida va a
12:59ser eh por lo menos igual a a sub n - 1,
13:03¿no es cierto?
13:04Porque todos los máximos locales que
13:07hubo por el camino,
13:11eh
13:17ya
13:18por ejemplo hubo máximos locales aquí
13:21siempre hay al primero, después por el
13:23camino aquí y aquí y acá todos esos que
13:25fueron máximos locales por el camino no
13:28dejan de serlo por el hecho que aparezca
13:29un competidor más, ¿no es cierto? Así es
13:31que de partida tenemos a sub n -1,
13:35pero eso hay que sumarle
13:38los máximos locales que en promedio
13:40aporta el último que viene llegando ya
13:43el el el enésimo jugador.
13:46E ahí tengo dos posibilidades, que el
13:50jugador que viene recién llegando le
13:52gane al actual campeón y en ese caso
13:55aporta un máximo local adicional o que
14:00no le gane al actual campeón y en ese
14:02caso aporta cero máximos locales de
14:05izquierda a derecha, ¿no es cierto?
14:07Entonces, ¿cuál es la probabilidad?
14:10Vamos a aportar uno
14:12por la probabilidad
14:15de que eh el último jugador
14:21último, a ver, corrijamos eso.
14:26El último jugador
14:30gane
14:33y aporta cero
14:36por la probabilidad que pierda.
14:40Cierto.
14:44Ya.
14:47¿Cuál es la probabilidad de que el
14:48último jugador gane?
14:52Supongamos que todo esto es aleatorio.
14:55En particular, si yo tengo n jugadores
14:57en el club, llegan en cualquier en todos
15:00los órdenes posibles, ¿no es cierto? son
15:01todos los órdenes posibles son equipos
15:03probables, o sea,
15:04entonces sería un medio, profesor,
15:06un medio, ya, eh, o sea,
15:10veamos si si eso hace algún sentido.
15:13Supongamos que hay un un club gigante
15:15ahí con 1000 jugadores. Ah, y
15:19999 ya han jugado y de esos 999
15:23el mejor de todos está como campeón. Y
15:26ahora aparece un jugador aleatorio,
15:27cualquiera, ya aparezco yo, ¿eh? Y tú me
15:31dices que la probabilidad que yo le gane
15:33al que le ha ganado a 999
15:36es un medio.
15:39O sea, el tipo ya le ha ganado a todo el
15:41mundo directa o indirectamente, ¿no? Eh,
15:46¿crees que será un medio?
15:50Sería tal vez uno partido en n-1.
15:54Cerca. Tibio. Tibio.
15:58Uno partido en N.
15:59Uno partido en N. Exacto, porque el
16:02último jugador que llega puede ser
16:03cualquiera de los nes del club, ¿no es
16:05cierto? Entonces, puede ser el peor
16:06jugador del club, ¿ya? O el segundo peor
16:09o el tercero peor. Ah, o o en el otro
16:13extremo. Eh, puede ser el tercero
16:16ranqueado, el cuarto, eh, el segundo,
16:21puede ser incluso el primero del club.
16:23Ya. Entonces, de todos esos casos, el
16:26único eh en que ganaría sería si es que
16:30el último que aparece es el primer
16:32ranqueado del club, el mejor de todo, ya
16:35que le gana al que le había ganado a
16:37todos los demás.
16:38En todos los demás casos, eh, el que
16:41estaba como campeón hasta el momento
16:43sigue estándolo.
16:45Ya, eh, obviamente, porque es muy
16:47difícil ganarle a él si le ganamos a
16:49medio mundo. Ah, no, no mundo, a todo el
16:51mundo. Ya. Así que en realidad es 1
16:54parti por n. Es 1 por 1/ por n.
16:58Ya ustedes lo pueden ver en términos de
17:01permutaciones.
17:02Esto que está por aquí más arriba
17:07es una permutación de los números del
17:09uno al nu, eh, excepto que se me haya
17:11olvidado alguno. Parece que no. Esto es
17:13una permutación de los números del 1 al
17:15nu. Entonces, si todas las permutaciones
17:18son x probables, eh el caso en que el
17:21último que aparece eh gane es cuando el
17:24último que aparece es el nueve,
17:26¿no es cierto? Y de todas las n
17:28factorial permutaciones posibles en 9
17:30factorial en este caso,
17:33¿cuántas de ellas tienen al nueve como
17:34último elemento? Ya. 1 parti por n, ya.
17:39Así es que en realidad es 1 parti por n.
17:41Eh, ¿qué fracción digamos tiene al
17:43último? 1 por n. Entonces, y bueno, y
17:46por supuesto eh el siguiente caso no
17:48aporta nada que es cero por la
17:49probabilidad complementaria que sería 1
17:51- 1/ por n, pero su último da casi lo
17:54mismo porque es un está multiplicado por
17:560. Así que por lo tanto lo que yo tengo
17:59es una ecuación de recurrencia que me
18:01dice que a su n es igual a su n - 1 + 1/
18:06n
18:08con a sub0 = 0. Y aquí yo tengo entonces
18:12una ecuación que puedo resolver.
18:14Estas ecuaciones son superfáciles de
18:17resolver, aunque uno no sepa nada de de
18:20esto, ¿no es cierto? Porque yo las puedo
18:22desenrollar. eh una ecuación de primer
18:24orden. Eh,
18:27así es que yo puedo decir, mire, a sub n
18:30la voy a escribir al revés 1/ido por n
18:34porque así me sale más fácil
18:35desenrollarla más sub n - 1. Entonces va
18:38a ser 1/ por n más a sub n - 1.
18:43Pero ahora el a sub n - 1 yo lo
18:46desenrollo y me da 1/ido por n - 1 más a
18:51sub n - 2.
18:53Ya. Y así sucesivamente.
18:56Y por este camino vamos a llegar a 1/
18:58por n + 1/ por n - 1
19:02+ 1/ por 1
19:05más. Y si ustedes se fijan,
19:10el denominador aquí
19:13es uno más que el que el subíndice de
19:17acá. Ya lo mismo aquí. Si el denominador
19:21era n, acá es n- 1, ¿no? De modo que si
19:25acá el denominador es un al subíndes acá
19:26tiene que ser
19:31y a sub sabemos que es cer. Por lo
19:33tanto, lo que queda como a subn
19:37es esto que es nuestro conocido HN.
19:41Ya. O sea, tenemos la solución.
19:46El número esperado
19:51de
19:53máximo o mínimo, ¿no es cierto? Por
19:56simetría locales
20:00de izquierda a derecha.
20:06es
20:08hn,
20:11o sea, es logarítmico, ya, o sea, la lo
20:17primero que les dije que si los dos
20:18extremos, si un extremo era uno, el otro
20:20extremo era n, entonces el promedio
20:21debería ser como la mitad, era solamente
20:23para confundirlos, porque el verdad la
20:25verdadera respuesta es que el número
20:27promedio es logarítmico, es hn, así es
20:31que Es un resultado bien bien
20:33interesante.
20:35Esto entre paréntesis e si ustedes van a
20:38ver el volumen un de Donald K de Art of
20:41Computer Programming es el primer
20:44problema que él utiliza para para
20:45motivar el el enfoque que tiene su
20:48libro. Ya. Así es que vamos a a a
20:53robarle ahí un ejemplo a a Canut.
20:57Ya. Entonces, ahora vamos a cambiar
20:59completamente de tema.
21:01porque es demasiado temprano para
21:02terminar la clase.
21:04Vamos a completamente de tema,
21:06eh, y vamos a hablar un poquito de
21:10análisis,
21:13poquito, porque más adelante vamos a
21:14hablar harto más. Análisis de árboles de
21:18búsqueda binaria.
21:41Ya. Eh, ustedes conocen bien los ABBs,
21:44¿no es cierto? Ustedes saben que
21:48un árbol de búsqueda binaria es un árbol
21:50que se caracteriza porque eh si yo tengo
21:55una raíz con un valor, digamos, r, eh
21:59todo lo que hay a la izquierda es menor
22:01que r y todo lo que hay a la derecha es
22:04mayor que r.
22:06Y eso mismo se cumple recursivamente al
22:09interior de los de los subárboles. Ah,
22:12si se cumple siempre esa condición, es
22:14un árbol de búsqueda binaria y es una
22:16estructura muy útil en la práctica
22:18porque podemos almacenar y buscar
22:20información eficientemente.
22:23Entonces, en un curso como este en que
22:25nos dedicamos al análisis de algoritmo,
22:26la pregunta es, bueno, ya, ¿cuán
22:28eficientemente?
22:30Eh, los árboles de búsqueda vainaria,
22:33eh,
22:36¿cuál es su mejor caso?
22:40¿A a qué me refiero?
22:42Que en un árbol de búsqueda binaria
22:43apareció una búsqueda de una parte de la
22:44raíz y compara con la raíz, ¿no es
22:46cierto? Eh, si el elemento que busco es
22:49igual a la raíz, lo encontré. Pero si
22:51no, yo sé dónde buscar, dónde seguir
22:54buscando. Si el x, digamos, que yo estoy
22:57buscando es menor que la raíz, tengo que
22:59seguir en el árbol izquierdo. Si es
23:02mayor que la raíz, tengo que seguir en
23:04el árbol derecho. Y así recursivamente
23:06hacia abajo, ¿no es cierto? ¿Hasta
23:08cuándo? ¿Hasta que lo encuentre por el
23:09camino o hasta que se me acabe el árbol?
23:11ya que sería el caso de una búsqueda
23:13infructuosa.
23:15Descendí todo lo que pude en el árbol
23:17hasta que topé fondo y ahí eh declaré
23:20que la búsqueda había sido infructuosa,
23:23el elemento no estaba en el árbol. ¿De
23:24acuerdo? Entonces, la pregunta,
23:26supongamos que concentremos en las
23:27búsquedas infructuosas porque eh si yo
23:31le pregunto el mejor caso de una
23:32búsqueda exitosa, la respuesta es
23:33trivial. Pues uno, el mejor caso, lo
23:35encuentro en la raíz, ¿ya? Pero
23:37supongamos que no está en el árbol.
23:39¿Cuál es el mejor caso? Eh eh, ¿cuál se
23:41cuál es el mejor árbol posible? Eh, el
23:43que me hace que la búsqueda se demore lo
23:45menos posible.
23:47El árbol completamente balanceado.
23:49Perfecto. No es cierto. El mejor caso es
23:51un árbol que es perfectamente
23:52balanceado.
23:54O sea, que
23:59todos los caminos hacia hacia abajo
24:01tienen la misma el mismo largo, ¿no es
24:03cierto? Y este largo
24:06es log 2 dn.
24:09¿cierto?
24:11Ese ese es el mejor caso. Eso deben
24:13haberlo visto en CC 3001 y si no ustedes
24:16ya lo pueden derivar por su cuenta sin
24:19sin mayor problemas porque en este tipo
24:20de árboles en con cada nivel que yo bajo
24:23el número de nodos se va duplicando, ¿no
24:25es cierto? Tengo uno en la raíz, dos que
24:28son los hijos de la raíz, cuatro que
24:30vendrían a ser los nietos de la raíz,
24:32ah, 8, 16, 32, etcétera. Entonces, como
24:35como el número de nodos se va duplicando
24:37cada vez, el entonces el número de
24:41niveles eh tiene que ser logarítmico, si
24:44es que el número total de nod.
24:47Ese es el mejor caso. ¿Cuál es el peor
24:49caso? ¿Cuál sería el peor árbol posible?
24:54Uno desbalanceado,
24:57¿no?
24:57Ya. Sí, pero cuánto balancead.
25:01Sí, perdón.
25:03N.
25:04A ver, Cami, primero
25:07iba a decir lo mismo. El más despanciado
25:10sería casi como una lista, que la raíz
25:12el número más pequeño, más grande toda
25:14la lista y como una
25:15Exacto. Exacto. Eh, ya. Eh, perfecto.
25:19Entonces, por ejemplo, podría ser un
25:21árbol así.
25:23Eso es un árbol, aunque no lo parezca,
25:25¿no es cierto?
25:26Eh, pero también podría ser algún tipo
25:28de zigzag
25:32para el caso lo mismo, ¿no es cierto? Y
25:34en ese caso, ¿cuánto viene a ser la
25:36máxima distancia desde la raíz hasta el
25:38fondo abajo?
25:41La cantidad de nodos.
25:42La cantidad de nodos, ¿no es cierto? N.
25:44Así que el mejor caso es log 2 de n, el
25:47peor caso es n. Y nuevamente, por
25:50supuesto, eh nos preguntamos cuánto es
25:53el promedio.
25:58Ya. Entonces, para fijar las ideas,
26:02eh pongamos un ejemplo específico. Ah eh
26:08supongamos
26:10eh
26:11que tengo una secuencia de datos que
26:13vienen llegando y a medida que van
26:15llegando yo los fui insertando en el
26:17árbol, ¿no es cierto? Entonces,
26:17supongamos que los datos fueran 5 9 6
26:243
26:264 8
26:291 7, por ejemplo, ya
26:36nuevamente una permutación de los
26:38números del uno al nu. Eh, entonces
26:41vamos recorriendo izquierda a derecha
26:42esta lista y y armando el árbol.
26:44Entonces aparece el cinco. Entonces
26:47evidentemente el cinco va a ser la raíz.
26:50Aparece el nueve, va a la derecha del
26:52cinco.
26:53Aparece el seis, eh, va a la derecha del
26:56cinco, para la izquierda del nueve, ¿no
26:57es cierto? Seis.
27:00aparece el tres para la izquierda del
27:02cinco.
27:05El cuatro izquierda del cinco, derecha
27:07del tres.
27:09El ocho sería derecha del cinco. A la
27:13izquierda el nueve, a la derecha el
27:14seis. Ocho.
27:18A ver, es el uno. A la izquierda del
27:20cinco. A la izquierda del tres. 1.
27:23Ya. El siete a la derecha del
27:28cinco, a la izquierda del nueve, a la
27:30derecha del seis, a la izquierda del
27:32ocho, el siete
27:36y el dos. A la izquierda el cinco, a la
27:39izquierda del tres, a la derecha el uno.
27:42Ahí estaría el dos. Ese sería el árbol,
27:45¿no? Y vamos a dibujar también las
27:49hojas,
27:51que son los puntos donde terminan las
27:53búsquedas infructuosas.
28:10Ok.
28:14Muy bien. Entonces tenemos este árbol
28:22como
28:25como precalentamiento, porque lo que nos
28:27interesa es cuánto es el el costo
28:28promedio de búsqueda, ¿no es cierto? Ya.
28:32Eh,
28:34como
28:36precalentamiento para esto, vamos a ver
28:40cuánto costaría buscar un elemento
28:44infructuosamente, ¿no es cierto?
28:47Cuando ese elemento es el mínimo, es es
28:49menor que todos los del árbol, ¿ya? Por
28:52ejemplo, está buscando el cero. Ya.
28:55Entonces, el cer es menor que el 5, es
28:58menor que el tres, es menor que el uno.
29:00Llegamos a una hoja y y digo, el cero no
29:03está. ¿Cierto? ¿Y qué costo tuvo eso? Yo
29:06voy a considerar como costo solamente
29:08las comparaciones con otros elementos.
29:11Voy a dar gratis la comparación que
29:13detecta que estamos en una hoja. Okay.
29:15Son las comparaciones de llave.
29:16Entonces, sería tres, ¿no es cierto?
29:18Entonces, el costo de buscar un elemento
29:19que es menor que todos eh es tres en
29:23este caso, que es el largo de la rama
29:25izquierda. Se fijan que la rama
29:26izquierda partiendo del cinco y llegando
29:29hasta la hoja tiene largo tres. Ya.
29:32Okay. Cuarto aquí es 1 2 3. Ya.
29:37Ahora, ¿qué pasaría si yo estuviera
29:38buscando un elemento que es mayor que
29:40todo? digamos el 10, ¿no? Eh, bueno,
29:44partiría al cinco, voy al nueve, llego a
29:46la hoja y digo, "No está." Este caso
29:48tuvo largo dos, ¿no es cierto? O sea,
29:50tuvo costo dos, que es el largo de la
29:52rama derecha. Entonces, si yo quisiera
29:56calcular cuánto es e el costo esperado
29:59de buscar un elemento que es menor que
30:01todos o buscar un elemento que es mayor
30:02que todos, tendría que estudiar cuánto
30:05es el largo esperado de la rama
30:06izquierda, cuánto es el largo esperado
30:08de la rama derecha, que por simetría son
30:10lo mismo. Ah, entonces vamos a tomar ese
30:13problema como decía, como una especie de
30:14precalentamiento. Hm. Entonces,
30:18problema,
30:21eh, ¿cuál es el largo esperado?
30:31de la rama
30:35izquierda
30:38o derecha.
30:41Ya.
30:42Eh, antes de entrar a esto, entre
30:44paréntesis, ustedes eh
30:50que ya pasaron por C3001, a lo mejor me
30:53pueden decir cuánto es el costo
30:55promedio, ¿se acuerdan? ¿Cuánto es el
30:57costo promedio de búsqueda infructuosa
31:00eh en un árbol de búsqueda binaria?
31:03¿Alguien se lo sabe de memoria?
31:06Probablemente no. No, bueno, yo se lo
31:08fuera recordar. Ese ese llama el C prima
31:12N.
31:13C prima N costo esperado
31:20de búsqueda infructuosa.
31:28Ya. Y en CC3001 se demuestra que eso es
31:33igual a dos veces hn + 1
31:37- 1.
31:40¿Okay? dos veces h + n + 1 - 1. Y y eso
31:47ustedes ya saben, si tuvieron la clase
31:50anterior o si han mirado el enunciado de
31:52la tarea, ya saben que el hn es muy
31:56cercano al logaritmo natural de n, la
31:58diferencia es una constante, ¿ya? Eh,
32:01por lo tanto, esto es como decir dos
32:02veces logaritmo natural de n. Entonces,
32:05¿cómo se compara eso con el mejor caso?
32:08Bueno,
32:09eh el c prima n está escrito en términos
32:12de logaritmo natural. En mejor caso está
32:15escrito en términos de logaritmo base 2.
32:17Entonces, para poder comparar hay que
32:18poner las dos cosas en la misma base,
32:19¿no es cierto? Entonces, si ponemos esto
32:22en base dos
32:24eh, y ignoramos términos de orden
32:26inferior, esto es aproximadamente 1.38
32:30veces
32:32log 2 de n,
32:34¿ya? Entonces
32:37esta
32:41esta constante que multiplica
32:44al logaritmo binario
32:47hay que compararla con la constante que
32:50multiplica a este logaritmo binario.
32:53Aquí
32:56pueden ver mi láser no sé, no estoy
32:59seguro. ¿Pueden ver mi láser? Sí, ya.
33:02Sí. eh
33:05que la contaste es uno, ¿no es cierto?
33:07La contaste que multiplica al logaritmo
33:09binario en el mejor caso es uno y acá es
33:111.38. O sea, en promedio el costo de
33:14búsqueda en estos árboles de búsqueda
33:15binaria construido al azar es 38% peor
33:19que el óptimo, lo cual no está nada de
33:22mal si es que han sido construidos, como
33:24les digo, al azar. ¿Ya? Eh, así es que
33:27yo sé que en un árbol como este, el
33:30costo esperado de búsqueda si hubiera n
33:31elementos sería como 1.38 veces log 2
33:36dn. Entonces, pero la pregunta es, ¿qué
33:38pasa si el elemento que estoy buscando
33:40no es un elemento aleatorio,
33:42sino que es un es menor que todos o es
33:45mayor que todos? Y eso es el problema
33:47que queremos abordar ahora.
33:49Bueno, este problema, no sé si alguno de
33:53ustedes ya se han dado cuenta, ya lo
33:55tenemos resuelto.
33:57¿Por qué? Eh, e si yo veo el largo
34:01esperado de la rama izquierda,
34:04ya,
34:06eh
34:09ese y voy marcando los elementos que yo
34:13visito en esa búsqueda.
34:16Eh, yo parto por el cinco, ¿no es
34:17cierto? Yo visito el cinco,
34:20que es el primero que llegó y luego
34:24visito el tres que está ahí y luego
34:28visito el uno que está aquí y el y el
34:31número de elementos que visité fueron
34:33tres. Fueron tres, ¿no es cierto? Pero
34:34si yo voy ahora y miro a a la secuencia
34:38de elementos de la lista en orden de
34:40llegada que está ahí arriba, voy a ver
34:44que estos tres elementos que están
34:46marcados verdes,
34:49en realidad de por consistencia debería
34:51cambiar de color. Aho,
34:54ya no lo hice. Dejémoslo así ya. Eh, son
34:59eh
35:01los tres elementos que yo visitaría si
35:05estuviera buscando el mínimo del
35:07conjunto.
35:09¿Ya se fijan? Porque parto con el cinco,
35:13el nu es mayor, el se es mayor, pero el
35:15tres es menor que el cinco. Entonces,
35:16cambio. Y el cuatro es mayor, el oo
35:18mayor, pero el uno es menor. Cambio. El
35:20siete es mayor, el dos mayor. Al final
35:22fueron tres mínimos locales de izquierda
35:24a derecha.
35:26Entonces, el largo esperado de la rama
35:28izquierda es igual al número esperado de
35:31mínimos locales de izquierda a derecha.
35:33Y yo ya sé la respuesta. Ya yo sé que la
35:36respuesta
35:39es
35:41HN.
35:43El largo esperado de la rama izquierda
35:44es HN.
35:47Y qué pasa si yo estuviera viendo el
35:51largo esperado de la rama derecha.
35:54Bueno,
35:57yo tengo que visitar el cinco, tengo que
35:59visitar el nueve,
36:01que son exactamente los elementos que yo
36:04visito si es que estoy buscando el
36:06máximo, porque una vez que apareció el
36:08nueve, después de eso nadie le gana.
36:11Okay. Así es que eh también es HN. El
36:16largo esperado de la rama izquierda es
36:18HN. El largo esperado de la rama derecha
36:21es HN.
36:24Pero por otro lado, el costo esperado de
36:27búsqueda de un elemento aleatorio
36:29es dos, básicamente 2 hn porque hn + 1
36:33es casi hn, ¿no es cierto? La diferencia
36:35es 1 parti por n + 1. Así que para
36:37términos para n grande son como lo
36:40mismo. Eh, entonces tengo aquí un
36:43pequeño problema porque el
36:47en un árbol si yo busco un elemento
36:51elegido al azar infructuosamente ya
36:55el costo va a ser 2 HN.
36:59Pero si me voy por la rama izquierda
37:01es solo un HN. Si voy por la rama
37:04derecha, solo un HD.
37:07Ahora la rama izquierda, la rama derecha
37:10no tienen nada de mágico,
37:12eh, porque, o sea, o sea, ¿qué quiere
37:15decir rama izquierda? Que yo parto la
37:16raíz y voy izquierda, izquierda,
37:18izquierda, izquierda, ¿no es cierto? O
37:19parto de la raíz para otro caso y voy
37:22derecha, derecha, derecha, derecha.
37:24Pero, ¿qué pasaría si yo fuera parto de
37:26la raíz y fuera derecha, izquierda,
37:28derecha, izquierda, derecha, izquierda,
37:29derecha, izquierda? ¿Cuál sería el largo
37:31esperado de ese zigzag hacia abajo?
37:34también sería HN,
37:36porque por simetría yo puedo hacer eh
37:40cambiar por imágenes espejo los árboles
37:42a medida que voy bajando y al final todo
37:44este zigzag se puede transformar en rama
37:46derecha o rama izquierda según sea. Ah,
37:48así es que también es HN. Entonces como
37:51una pequeña paradoja que si bajando
37:55izquierda, izquierda, izquierda es HN,
37:57derecha, derecha, derecha es HN, zigzag,
37:59zigzag también es HN. Sin embargo,
38:01cuando yo busco un elemento aleatorio es
38:032 HN.
38:06Raro, ¿no? Ah, pero no es tan raro. ¿Por
38:09qué? Porque cuando yo voy en estas
38:12trayectorias, como las que le digo,
38:14siempre a la izquierda o siempre a la
38:15derecha o siempre izquierda, derecha,
38:17izquierda, derecha en un zigzag, ya la
38:20dirección que yo tomo, eh, ya sé, por
38:23ejemplo, siempre izquierda, izquierda,
38:24izquierda, si estoy buscando el largo
38:25esperador izquierda es independiente de
38:28los tamaños de los subárboles
38:29involucrados. Ya me da lo mismo la forma
38:32que tenga el árbol. Yo siempre voy a
38:33decir izquierda, ¿ya? Sin embargo,
38:36cuando yo estoy buscando un elemento
38:39aleatorio,
38:41¿ya? Eh, la dirección a la que yo me voy
38:45sí depende de la forma del árbol. Miren,
38:49supongamos que yo tengo aquí
38:52un árbol que tiene esta forma, tiene una
38:54raíz,
38:57¿ya?
38:59y y tiene a la izquierda un árbol
39:03eh, sumado super grande,
39:07¿ya? Y a la derecha sumamos un árbol
39:09chiquitito.
39:12Y supongamos que aquí hay
39:15y i elementos y acá hay J elementos,
39:17¿okay?
39:18Y estos árboles, cada uno de ellos
39:20termina con con las hojas aquí abajo.
39:26Si si este si este tiene i elementos, el
39:31número de hojas va a ser i + 1.
39:34Si este tiene j, el número de hojas va a
39:36ser j + 1. ¿Ya?
39:40Eh,
39:42y el número total de hojas va a ser eh I
39:46+ J + 2, ¿no es cierto?
39:50Bueno, entonces cuando yo estoy aquí,
39:53supongo que yo estoy en este punto
39:56y tengo que decidirme si me voy hacia la
39:59izquierda
40:01o hacia la derecha,
40:04¿cuál es la probabilidad de que yo me
40:06vaya a la izquierda o cuál es la
40:07probabilidad que yo me vaya a la
40:09derecha? Hm.
40:11Bueno, si el elemento que yo estoy
40:14buscando infructuosamente
40:16es aleatorio, eso quiere decir que todas
40:19las hojas, las n + 1 hojas, son
40:22igualmente probables. O sea, la búsqueda
40:24puede terminar en cualquiera de las
40:26hojas que ustedes están viendo aquí,
40:29ya en forma equable. Por lo tanto, si
40:32aquí hay + 1 hojas, eh, y el total es i
40:35+ j + 2, la probabilidad
40:38de que yo me vaya hacia la izquierda es
40:41i + 1
40:43parido por i + j + 2.
40:46En cambio, la probabilidad que yo me
40:47vaya a la derecha, si a la derecha hay j
40:49+ 1 hojas de un total de i + j + 2, la
40:53probabilidad va a ser jido
40:56por i + j + 2.
40:59Entonces, si
41:02estos dos árboles están tan
41:04desbalanceados, este árbol está tan
41:06desbalanceado como yo les sugiero en el
41:08dibujo, o sea, el i es mucho más grande
41:10que el J. Cuando yo vaya haciendo una
41:12búsqueda infructuosa y llego a este a
41:15esta raíz, eh la probabilidad que yo me
41:18vaya a la izquierda, o sea, hacia el
41:19árbol más gordo, es mucho mayor que la
41:22probabilidad de que me vaya al árbol más
41:23chico. Ya me puedo ir al árbol más
41:25chico, pero con una probabilidad mucho
41:26menor.
41:28Por lo tanto, las búsquedas siempre van
41:30a estar cargadas hacia el lado del árbol
41:32más grande y eso explica que yo me
41:37demore mucho más en llegar al fondo del
41:39árbol, porque siempre me estoy yendo con
41:40alta probabilidad hacia el árbol más
41:43grande de los dos que tengo enfrente. En
41:46cambio, como les decía, cuando uno sigue
41:49una trayectoria fija, como izquierda,
41:50derecha, izquierda, derecha, izquierda,
41:52derecha, por ejemplo, ahí la dirección
41:54que yo tomo, izquierda o derecha, no
41:56depende para nada de los tamaños de los
41:57árboles involucrados y por eso es que es
42:00HN.
42:01Pero cuando yo siempre le doy
42:03preferencia a irme en dirección al árbol
42:05más gordo, eh claramente en ese caso me
42:08me voy a demorar más en llegar al fondo.
42:10Y matemáticamente se puede ver y eso lo
42:13vamos a ver que eh que uno se pone el
42:15doble. ¿Ya entienden la intuición de
42:18esto? Sí. Ya. Entonces, eh,
42:23claro. Eh, así que vamos a
42:27vamos a ver eh cómo nos va con esto.
42:32Entonces,
42:34eh en este árbol que yo tengo aquí,
42:37supongamos
42:46tiempo.
42:53Supongamos,
43:07supongamos que buscamos un elemento como
43:08el 6.5, C. Ya
43:12recuerda que es una búsqueda
43:12infructuosa. Entonces, eh,
43:17a ver, pero para para esos efectos lo
43:20que me va a servir es dibujar de nuevo
43:21el árbol, así que denme un minuto,
43:24eh, y lo vamos a dibujar.
43:27Entonces tenemos el cinco,
43:33tres
43:34cuar
43:42el nueve,
43:48el seis,
43:52el 8,
43:53el siete.
44:13Ya. Y recuerden que este árbol se
44:18construyó con esta secuencia que es 5
44:239 6
44:263
44:274 8
44:311
44:337.
44:35Okay. Ya.
44:37Entonces, supongamos que buscamos, como
44:39les decía, digo aquí que buscamos 6,5.
44:44Entonces
44:46yo paso por el cinco, ¿no es cierto?
44:49el cinco. Disculpe un segundo.
45:18Okay,
45:20muy bien. Eh,
45:23partimos por el cinco y el cinco es
45:26menor que el 6,5. Entonces, lo voy a
45:27pintar de un color
45:32ya aquí. Okay.
45:35Y ahora voy al nu. Bueno, el 9 es mayor
45:40que el 6.5. Lo voy a pintar de otro
45:43color.
45:45Y ahora me voy al 6.
45:48ya que es menor.
45:53Y ahora me voy al 8, que es mayor que el
45:576.5.
46:03Y ahora me voy al 7, que nuevamente es
46:05mayor que el 6.5. Y luego me voy a esta
46:09hoja de aquí,
46:12que es la hoja donde terminamos.
46:15Ahí estaría el 6.5.
46:18en esa hoja
46:20y eh y esta trayectoria que yo hice aquí
46:27genera una división, ¿no es cierto? Una
46:30separación
46:36ya en que a la izquierda quedan todos
46:40los elementos que finalmente fueron
46:41menores que 6.5 y a la derecha todos los
46:44que son mayores que el 6.5.
46:46Okay. Entonces,
46:49si
46:51yo hubiera eh
46:54de la n elemento que tengo aquí, yo
46:56hubiera extraído los que son menores que
46:59el 6.5,
47:01¿cuáles serían ya? Eh, el serían el
47:05cinco,
47:07el nueve, no, el seis, sí, el tres, sí,
47:12el cuatro sí.
47:14Ya. El ocho no, el uno sí,
47:19el siete no, el dos sí, ¿no es cierto?
47:24Estos son todos los que son menores que
47:276.5.
47:30Y por otro lado, si si extraigo los que
47:33son mayores,
47:35serían el nu,
47:38¿cierto?
47:39C no cierto, el nu sí, el seis no. Tres,
47:41no. CU no. Oo, sí.
47:45Y
47:47uno no, siete sí, dos no. Estos son los
47:53que son mayores que 6.5.
47:57Okay.
47:59Y eh
48:01y dentro de los que son eh menores, ya
48:08si yo marco los elementos que les tocó
48:10compararse directamente contra el 6.5,
48:12cinco, que fueron el cinco y el seis.
48:14Ya, el cinco y el seis son exactamente
48:18los que yo habría eh ido seleccionando
48:22si hubiera ido buscando el máximo eh
48:26elemento de los que son menores.
48:29Si si voy buscando el máximo, tomo el
48:31cinco, después viene el seis, lo
48:32sustituye. El tres no, el cuatro, no, el
48:35uno, no, el dos. ¿Cierto? O sea, el
48:38número de elementos marcados verdes en
48:40la búsqueda es igual al número de
48:43máximos locales de izquierda a derecha
48:45entre los elementos que son menores que
48:46el 6.5.
48:48Y si ahora yo vengo acá, digo, eh, los
48:52elementos que quedaron marcados, que al
48:54final fueron todos, ¿ya? Eh, ¿a qué
48:56corresponde? corresponden a los que yo
48:58habría encontrado. Si yo buscando el
49:00mínimo de izquierda a derecha, parto con
49:02el nueve, aparece el ocho, aparece el
49:04siete. Ya. Por lo tanto,
49:08los elementos
49:12verdes,
49:15los verdes son igual al número esperado
49:26de máximo. locales
49:30de izquierda a derecha
49:36entre
49:39los menores que 6.5.
49:44Y esto de acá es por simetría el número
49:47esperado
49:50de
49:52mínimos locales
49:55de izquierda a derecha
50:00entre
50:01los mayores que el 6.5.
50:06Okay.
50:09Entonces,
50:17entonces el el
50:22costo de la búsqueda, el costo esperado
50:24de la búsqueda
50:31es costo esperado de búsqueda
50:33infructuosa.
50:39de un elemento
50:45que tiene
50:48Kementos
50:52menores que él,
50:56¿no es cierto?
50:58El 6.5 en este caso tenía, ¿cuánto? 1 2
51:013 4 5 6 elementos menores que él. ¿Ya? Y
51:05el número esperado de de el costo
51:07esperado de la búsqueda es el número
51:09esperado de elementos marcados verdes
51:10más el número esperado de elementos
51:12marcados en
51:15en naranja, ¿no es cierto? Ya. Entonces,
51:20eh,
51:22¿cuántos elementos hay marcados verdes
51:23en promedio? Si es que este en este caso
51:27había seis elementos menores, pero se
51:29generalizando, si si hubiera Kementos
51:31menores que el que yo estoy buscando, en
51:34ese caso el costo esperado se busca
51:36sería HK, ¿cierto? Porque sabemos que
51:39ese es el número esperado de mínimos
51:40locales de máximos locales de izquierda,
51:42derecha en un conjunto de tamaño K.
51:45Y a eso hay que sumarle los que están
51:46marcados naranja, que es el número
51:49esperado de mínimos locales de izquierda
51:51a derecha entre los que quedaron a la
51:53derecha de este elemento. Pero si a la
51:55izquierda había k, a la derecha tiene
51:57que haber n - k.
52:01Okay. Así es que
52:06eh
52:08eso es
52:10este es el costo esperado de búsqueda
52:12infructuosa de un elemento que tiene
52:14Kementos que son menores que él. Es hk +
52:17HN- K.
52:18Pero ahora lo que me interesa el costo
52:21esperado de búsqueda de un elemento
52:23aleatorio. ¿Ya? Eh, entonces ahí resulta
52:27que el parámetro acá
52:29eh tiene que poder tomar todos los
52:31valores posibles. O sea, yo tengo que
52:34ver qué pasa cuando un elemento tiene
52:37cero elementos menores que él, ¿ya? O
52:40cuando tiene un elemento menor que él o
52:42dos elementos menores que él o en el
52:43otro extremo cuando todos los elementos
52:45son menores que él. ¿De acuerdo? y hay n
52:48+ 1 casos.
52:50Ya. Entonces yo tengo que promediar
52:52sobre esos n + 1 casos. Así es que el
52:54cima n
52:58lo que yo para obtener ese prima n lo
52:59que tengo que hacer es sumar todos estos
53:01casos
53:08sobre todos los valores posibles de k
53:10van desde 0 hasta n.
53:14Ya. Y esos son n + 1 casos, así que
53:16tengo que dividir por n + 1.
53:19Ahí tengo mi mi
53:21solución. Ya. Y
53:26eso, esta es la solución. Ah, ahora
53:29todavía no está muy presentable, pero
53:30esta es la solución.
53:32Okay. Eh, para que esté más presentable
53:35tengo que trabajar un poquito y estamos
53:38bien.
53:41Lo primero que yo me puedo dar cuenta es
53:43que si yo tomo eh esta sumatoria
53:47y la aplico aquí al HK y por otro lado
53:50tomo la misma sumatoria y lo aplico al
53:51HN - K, esas dos son la misma sumatoria,
53:55eh, solo que aquí los subíndices van
53:57creciendo. K = 0 1 2 hasta N. Y acá los
54:00subíes van decreciendo acá desde n - 1
54:04hasta 0, ¿ya? Eh, pero eh
54:09pero son es la misma sumatoria.
54:12Entonces, esto es igual a si es que
54:16esto es lo mismo que 2 par n + 1.
54:21Sumatoria de hk
54:250 menor o igual que k menor igual que n.
54:32Ya.
54:34Eh, ya se un poquito más más simple,
54:37pero todavía no hemos llegado a lo que
54:39queremos, porque a qué deberíamos
54:41llegar, deberíamos llegar a lo que dije
54:43que era, que es 2hn + 1 - 1, ¿no es
54:46cierto? Así que
54:49vamos a ver. Ya. Entonces, ahora lo que
54:51yo voy a hacer es sustituir la
54:54definición de de números armónicos.
54:57Entonces esto va a ser 2/ por n + 1 por
55:00la sumatoria 0 menor o igual que k men o
55:03igual que n de hk. Pero hk es la
55:07sumatoria
55:091 menor o igual que j menor o igual que
55:11k de 1/ j.
55:14Ya ahí está.
55:17Y ahora intercambio las dos sumatorias.
55:20Entonces va a ser 2 par n + 1
55:24por la sumatoria sobre J.
55:27eh y la sumatoria
55:30sobre K, ¿no es cierto?
55:33Eh, y si la sumatoria sobre J va
55:36primero, entonces aquí va el 1 parido
55:38por J. Y al final, ¿qué queda aquí
55:40adentro? Uno no más. ¿Ya? ¿Y cuál es el
55:44rango de J? Si era J iba de 1 hasta K,
55:48pero K puede llegar hasta N. Esto va a
55:50tener que ser 1 menor o igual que J
55:52menor igual que n. ¿Y cuál es el rango
55:56de K?
55:58Es,
55:59bueno, K es mayor o igual que J, ¿no es
56:01cierto?
56:03Por esta por esta condición de aquí. K
56:05es menor o igual que J y por otro lado
56:07es menor igual que N. Así que el rango
56:09de K es J menor igual que K, menor igual
56:13que N. Eh, ya.
56:18Eh,
56:27¿cuántos términos hay en esa sumatoria?
56:30¿Hay cuántos términos hay en esa
56:32sumatoria?
56:39¿Sí? ¿Quién me lo dice?
56:42Si el rango va desde J hasta N,
56:44¿cuántos? N
56:46- J + 1.
56:47Exactamente. Entonces, eh N - J + 1,
56:55¿cierto? Así que esto es igual a 2
56:57parido por n + 1
57:00por la sumatoria
57:041 menor o igual que j menor o igual que
57:06n de n
57:09- j + 1 parido por j. Ya.
57:18Okay. E
57:22y esto eh lo puedo separar en dos
57:24partes, la que depende de J, la que no
57:26depende de J, ¿no es cierto? Entonces,
57:28eso sería 2 parido por n + 1
57:32eh por
57:35Ya. Entonces, voy a a tomar el n + 1 que
57:38está en el numerador y lo voy a sacar
57:39para fuera.
57:43y me va a quedar la sumatoria 1 menor o
57:47igual que j menor o igual que n de 1/ j.
57:52Ya.
57:54Menos
57:56eh sumatoria
57:59de 1 menor o igual que j menor o igual
58:01que n
58:03de j parido por j, o sea, 1.
58:09Okay.
58:11Así es que
58:14así es que esto, ¿cuánto sería? Esto
58:16sería,
58:18a ver, si voy con la primera sumatoria,
58:21el n + 1 que está multiplicando se
58:23cancela con el n + 1 que está
58:25dividiendo, así es que me queda dos
58:27veces
58:31hn, ¿no es cierto? Porque 1/ jado de 1 a
58:33n es hn.
58:36Esa era la primera sumatoria. Después la
58:38segunda
58:40es eh
58:42-2
58:45y el número sumando es n ahí, así que
58:48sería nido por n + 1.
58:53Ya hay bastante está bastante más
58:55presentable. Ah, pero eh
58:59de hecho eh podemos sacar el factor 2
59:02aquí sería hn - n/ por n + 1.
59:10Ya está bien cercano a lo que teníamos
59:12acá,
59:14pero no idéntico todavía.
59:17Este ahí el 2HN + 1 - 1, pero estamos
59:21super cerca,
59:23¿eh? Entonces, ¿qué puedo hacer aquí? Lo
59:25que puedo hacer, necesito un hn + 1, ¿no
59:27es cierto? Entonces, lo que puedo hacer
59:29es al hn sumarle lo que le falta para
59:32que sea un hn + 1. Tengo que sumarle eh
59:351/ido por n + 1. Entonces, con eso lo
59:38transformo
59:40o hagámoslo explícito para que quede
59:42claro. Hn le sumo 1/ido por n + 1 y con
59:45eso va a ser un hn + 1, ¿no es cierto?
59:47Pero ese 1/ido por n + 1 tengo que que
59:50lo acabo de sumar, lo tengo que restar.
59:53Entonces va a ser - n/ n + 1 - 1/ n + 1.
59:59Ya. Y ahí estamos listo. Esto es hn + 1
1:00:04y esto de acá
1:00:08es un -1
1:00:10y eso implica que c sub su sub n prima
1:00:13es 2
1:00:15hn + 1 - 1, que es exactamente lo que
1:00:20queríamos demostrar. Ya. Así que
1:00:24por esta vida logramos probar lo que ya
1:00:27habíamos en en en
1:00:30C1 esto se muestra pero de una manera
1:00:32totalmente distinta. De hecho, hay
1:00:34muchas maneras de mostrar esto. Vamos a
1:00:36ver varias a lo largo del curso.
1:00:38Esto está basado en esta idea de los de
1:00:42los máximos y mínimos locales de
1:00:43izquierda a derecha. Mm. Así que ustedes
1:00:46pueden ver que partiendo
1:00:49con eh
1:00:53con un problema que era buscar máximo
1:00:55local izquierda, derecha, hemos logrado
1:00:57resolver un problema que parecía que
1:00:59fuera totalmente distinto, que es el
1:01:00análisis de árboles de búsqueda binaria.
1:01:02Hm.
1:01:03Está bien. Eh,
1:01:07y para completar lo que quiero ver en
1:01:09esta clase, quiero mostrarles otro
1:01:10problema que nuevamente no tiene nada
1:01:12que ver con los anteriores, que es el
1:01:15número esperado
1:01:23de ciclos
1:01:29en una permutación.
1:01:40Supongamos que yo tengo una permutación
1:01:43nuevamente de los números del 1 al nu.
1:01:45Entonces, lo puedo escribir así, 1 2 3.
1:01:52Ya. Y supongamos que la permutación es 5
1:01:562 8
1:01:596 1
1:02:024 3
1:02:049 7.
1:02:08Okay. En general, vamos a suponer que
1:02:11que la mutación es de tamaño n.
1:02:15Entonces, eh, ¿qué quiere decir los
1:02:17ciclos? Bueno, eh
1:02:21yo puedo en esta en cualquier
1:02:22permutación yo puedo ver cuál es
1:02:24estructura de ciclos de la siguiente
1:02:25manera. Por ejemplo, yo parto del uno,
1:02:29la permutación el uno lo lleva al cinco,
1:02:31¿no es cierto? Entonces el uno lo lleva
1:02:33al cinco. Entonces, yo voy a ver el
1:02:36cinco y el cinco, ¿a dónde va? El cinco
1:02:37va al uno. Así que ahí volvemos ya. ¿Qué
1:02:42pasa con el dos?
1:02:44El dos
1:02:46va directo al dos. Ahí se cierra el
1:02:49ciclo. El tres.
1:02:54El tres va al oo.
1:02:58El ocho, ¿a dónde va? Al nueve.
1:03:02El nueve, ¿a dónde va? Al siete.
1:03:07Y el siete, ¿a dónde va? al tres.
1:03:10Ahí se cierra el ciclo. Ya me faltó
1:03:13espacio. Pongamos por aquí al ladito
1:03:14abajo el porque falta el cuatro. El
1:03:18cuatro a dónde va al seis.
1:03:21Y el seis, ¿a dónde va? Al cuatro.
1:03:25O sea, en este caso hay cuatro ciclos,
1:03:29¿cierto?
1:03:31Hay digamos cuatro ciclos.
1:03:36E
1:03:38esto eh se puede escribir en notación de
1:03:41ciclos diciendo que eh el primer ciclo
1:03:44es que va el uno al cinco y el cinco
1:03:47vuelve al uno. El dos va directo al dos,
1:03:51el tres va al oo, el cual va al nueve,
1:03:55el cual va al siete, el cual vuelve al
1:03:57tres. Y por último, el cuatro va al
1:03:59seis, el cual vuelve al cuatro. ¿Ya? Eso
1:04:02es en la anotación de cicles.
1:04:12¿Okay?
1:04:13Y la pregunta es, ¿cuánto es el número
1:04:16esperado de ciclos en una permutación?
1:04:21¿Qué me pueden decir ustedes de
1:04:24eh del mínimo y el máximo?
1:04:29¿Cuánto será
1:04:31el número eh
1:04:35mínimo de ciclos que puede tener una
1:04:36permutación?
1:04:44Eh, uno,
1:04:45uno, ¿no es cierto? en que cada número
1:04:47va otro distinto, que va otro distinto,
1:04:49que otro distinto y solo al final vuelve
1:04:51al primero. Eh, un solo gran ciclo,
1:04:53megaciclo. Eh, y en el otro extremo,
1:04:56¿cuánto es el número máximo de ciclos
1:04:58que podría haber?
1:04:59N.
1:05:00N.
1:05:00N, ¿no es cierto? Cada elemento va a sí
1:05:03mismo. La permutación de identidad, ¿no
1:05:05es cierto? Tiene n ciclos. Eh, ya.
1:05:08Entonces, mínimo uno, máximo n. Pero la
1:05:11pregunta es promedio, porque ese es como
1:05:13el tema de esta clase, ¿cuánto es el
1:05:15promedio? ¿Ya? Entonces, si yo voy a
1:05:19contar ciclos, eh tengo que tener eh
1:05:24cuidado de ningún ciclo contarlo más de
1:05:28una vez. Ya. Entonces, para evitar eh
1:05:33que porque lo que pasa es que
1:05:36supongamos que yo digo, ya están estos
1:05:38ciclos, pero digo además está este otro,
1:05:40por ejemplo, el 51,
1:05:44ya digo, 51 es otro ciclo.
1:05:48Eh, bueno, dice, no, pues 51 no es otro
1:05:50ciclo porque es el mismo que el 15, ¿ya?
1:05:53O yo podría decir, "Mira, el ciclo 97 38
1:05:57es otro ciclo." Yo digo, "No, 97 38 no
1:06:00es porque es el mismo que el 3897."
1:06:03Ah, entonces eh para evitar contar las
1:06:06cosas más de una vez, eh lo que uno
1:06:08puede definir es una forma canónica, una
1:06:11forma estándar de escribir los ciclos,
1:06:15de modo que al escribirlo en forma
1:06:18canónica, un ciclo tiene una manera de
1:06:21escribirse y así no nos podemos
1:06:22equivocar. Entonces, la forma canónica
1:06:26que vamos a optar es que para un ciclo
1:06:29específico,
1:06:31yo voy a hacer que comience por el
1:06:32mínimo dentro del ciclo y de ahí crezca.
1:06:37Ya, eso en cada ciclo.
1:06:42De hecho, los que ustedes están viendo
1:06:43ahí, casualmente están escritos de esa
1:06:45manera. Todos comienzan con el mínimo
1:06:47valor posible dentro del ciclo. Así que
1:06:50ahí estamos bien.
1:06:52Y ahora, eh,
1:06:55¿cómo escribo todos los ciclos?
1:06:59Eh, al escribir todos los ciclos, lo que
1:07:02yo voy a hacer es voy a
1:07:06tomar los ciclos y me voy a fijar en su
1:07:08primer elemento, ¿ya? y los voy a
1:07:11ordenar en orden decreciente de primer
1:07:13elemento.
1:07:18Ya s,
1:07:20ya mayor que ese, mayor que ese. Ah, o
1:07:24sea, todos los ciclos ordenados,
1:07:27el primer elemento se suele llamar el
1:07:29líder del ciclo, ordenados en orden
1:07:34de creciente
1:07:38de líder.
1:07:40ya que es el primer elemento.
1:07:45Entonces, en esa con esa
1:07:49convención
1:07:51eh los que yo tengo ahí arriba no están
1:07:53bien, pues de hecho están exactamente al
1:07:54revés. Así es que eh con esta convención
1:07:58de notación canónica habría que partir
1:08:01por el 46.
1:08:05Ya. Luego vendría el 3897,
1:08:13luego vendría el dos y luego vendría el
1:08:1715.
1:08:23Okay.
1:08:25Y déjenme
1:08:27marcar
1:08:30los líderes de los respectivos ciclos.
1:08:35Okay.
1:08:40Muy bien.
1:08:45Y qué gracia tiene haber definido que
1:08:48esta es la notación canónica. La gracia
1:08:51que tiene es que ahora
1:08:58puedo borrar
1:09:01los paréntesis.
1:09:10¿Qué pasa si yo borro los paréntesis y
1:09:12digo 4 6
1:09:168 9
1:09:182 1 5?
1:09:22Ya.
1:09:25Bueno, si yo borro los paréntesis, yo
1:09:28los puedo recuperar.
1:09:31¿Por qué?
1:09:32Porque si yo quiero ver cuál es
1:09:34estructura de ciclos, obviamente el
1:09:37cuatro tiene que ser el líder de un
1:09:38ciclo porque es el que está primero que
1:09:41todo, ¿no es cierto? Y eh el seis, que
1:09:45es mayor que el cuatro tiene que ser
1:09:46parte de su ciclo,
1:09:49pero el tres que viene a continuación no
1:09:51puede ser parte de su ciclo,
1:09:54¿ya? Porque eh si fuera parte del ciclo
1:09:58estaría mal, porque en ese caso el tres
1:09:59habría sido el líder, ¿no es cierto? Así
1:10:01es que el tres tiene que ser el líder
1:10:03del ciclo siguiente y el ocho es mayor
1:10:05que el tres y el nueve es mayor que el
1:10:07tres y el siete mayor que el tres. Todos
1:10:09son parte del ciclo del tres, pero el
1:10:11dos no.
1:10:13Ya. Eh, y el uno no puede ser parte del
1:10:17ciclo del dos porque es menor que él.
1:10:18Así que el uno también es líder de un
1:10:20ciclo y el cinco es parte del ciclo del
1:10:22uno. Así es que aunque yo no eh
1:10:28tenga los paréntesis a la vista, yo los
1:10:30puedo recuperar
1:10:33porque el número
1:10:37o más bien más que el número,
1:10:44los líderes de ciclos
1:10:51Son
1:10:53exactamente
1:10:55los
1:10:57mínimos locales
1:11:06de izquierda a derecha
1:11:12en esta permutación,
1:11:20¿se fijan?
1:11:21Si yo fuera recorriendo esta permutación
1:11:24para encontrar los mínimos locales de
1:11:25izquierda derecha, partiría con el
1:11:27cuatro, el seis no. El tres sí, el ocho
1:11:30no, el nueve, no. El siete no. El dos
1:11:32sí, el uno sí, el cinco no.
1:11:36Pero el número de líderes es lo mismo
1:11:38que el número de ciclos. Por lo tanto,
1:11:40tengo mi respuesta.
1:11:43El número
1:11:46esperado
1:11:48de ciclos
1:11:51en una permutación aleatoria
1:12:03es
1:12:05cuánto,
1:12:09HN.
1:12:10Exactamente, ¿no es cierto?
1:12:12Porque es igual al número esperado de
1:12:14mínimos locales de izquierda derecha en
1:12:16una permutación aleatoria.
1:12:20Así es que esa es la respuesta que
1:12:23esperábamos encontrar
1:12:26eh hoy día y finalmente entonces lo que
1:12:31podemos concluir y creo que a pesar de
1:12:33que todavía nos queda un rato, voy a
1:12:36llegar hasta aquí con esta clase porque
1:12:37después la próxima clase ya es un tema
1:12:39distinto.
1:12:43que eh todos estos problemas que hemos
1:12:46visto, que en principio se veían como
1:12:48nada que ver uno con otro, ¿no es
1:12:49cierto? Encontrar mínimos locales
1:12:51izquierda derecha, encontrar el largo de
1:12:52la rama izquierda o la rama derecha en
1:12:54un árbol de búsqueda binaria o encontrar
1:12:56el costo esperado de búsqueda
1:12:58infructuosa en un árbol de búsqueda
1:12:59binaria o encontrar el número de ciclos
1:13:01en una permutación aleatoria es eh son
1:13:06de una manera otra el mismo problema.
1:13:08Ah, y todos terminan teniendo la misma
1:13:10solución. que que es eh HN. Ya. Así es
1:13:15que espero que les haya gustado esto y
1:13:18nos veremos la clase que viene el el
1:13:21lunes.
1:13:29Ha.