Transcription
El siguiente contenido se proporciona bajo una licencia Creative Commons. Su apoyo ayudará a MIT OpenCourseWare a seguir ofreciendo recursos educativos de alta calidad de forma gratuita. Para hacer una donación o ver materiales adicionales de cientos de cursos del MIT, visite MIT OpenCourseWare en ocw.mit.edu.
PROFESOR: Hola. Soy Srini Devadas. Soy profesor de ingeniería eléctrica y ciencias de la computación. Voy a co-enseñar 6.006-- Introducción a los Algoritmos-- este semestre con el profesor Erik Domane. Eric, saluda.
ERIK DOMANE: Hola. [RÍE]
PROFESOR: Y esperamos que se diviertan en 6.006 aprendiendo una variedad de algoritmos. Lo que quiero hacer hoy es pasar literalmente un minuto o menos en detalles administrativos. Me gustaría que visiten el sitio web que está listado arriba y lo lean. Allí encontrarán toda la información que necesitan sobre de qué trata esta clase desde el punto de vista del syllabus; lo que se espera de ustedes; el calendario de tareas; el calendario de exámenes; y así sucesivamente. Quiero sumergirme de inmediato y hablarles sobre cosas interesantes, como algoritmos y la complejidad de los algoritmos. Quiero dedicar un tiempo a darles una visión general del contenido del curso. Luego nos sumergiremos y veremos un problema particular de búsqueda de picos-- tanto la versión unidimensional como la bidimensional-- y hablaremos sobre algoritmos para resolver este problema de búsqueda de picos-- ambas variedades. Y verán que realmente hay una diferencia entre estos varios algoritmos que analizaremos en términos de su complejidad. Y lo que quiero decir con eso es que tendrán diferentes tiempos de ejecución de estos algoritmos dependiendo del tamaño de la entrada, basado en cuán eficientes son estos algoritmos. Y un requisito previo para esta clase es 6.042. Y en 6.042 aprendieron sobre complejidad asintótica. Y verán que en esta conferencia analizaremos algoritmos relativamente simples hoy en términos de su complejidad asintótica. Y podrán comparar y decir que este algoritmo es más rápido que este otro-- suponiendo que tienen entradas grandes-- porque es asintóticamente menos complejo. Así que vamos a sumergirnos y hablar sobre la clase.
Así que el resumen en una oración de esta clase es que se trata de procedimientos eficientes para resolver problemas con entradas grandes. Y cuando digo entradas grandes, me refiero a cosas como el sistema de carreteras de EE. UU., un mapa de todas las carreteras en los Estados Unidos; el genoma humano, que tiene mil millones de letras en su alfabeto; una red social como Facebook, que supongo tiene alrededor de 500 millones de nodos. Así que estas son entradas grandes. Ahora, nuestra definición de grande realmente ha cambiado con el tiempo. Y así, realmente la definición del siglo XXI de grande es, supongo, un billón. ¿Verdad? Cuando yo tenía su edad, grande era como 1,000. [RÍE] Supongo que me estoy delatando aquí. Cuando Eric tenía su edad, era un millón. ¿Verdad? [RÍE] Pero lo que está sucediendo es que el mundo se mueve más rápido, las cosas están creciendo. Tenemos la capacidad de computar sobre entradas grandes, pero eso no significa que la eficiencia no sea de suma importancia. La realidad es que puedes, tal vez, escanear mil millones de elementos en cuestión de segundos. Pero si tuvieras un algoritmo que requiere complejidad cúbica, de repente no estás hablando de 10 elevado a 9, estás hablando de 10 elevado a 27. Y ni siquiera las computadoras actuales pueden manejar esos tipos de números, así que la eficiencia es una preocupación. Y a medida que las entradas se vuelven más grandes, se convierte en una preocupación aún mayor. ¿Está bien? Así que nos preocupamos por-- --procedimientos eficientes-- para resolver problemas a gran escala en esta clase. Y nos preocupa la escalabilidad, porque-- así como, ya saben, 1,000 era un gran número hace un par de décadas, y ahora es un número pequeño-- es bastante posible que para cuando ustedes sean profesores enseñando esta clase en alguna universidad, un billón va a ser un número pequeño. Y estaremos hablando de-- no sé-- 10 elevado a 18 como algo que nos preocupa desde el punto de vista de una entrada común para un algoritmo. Así que la escalabilidad es importante. Y queremos poder rastrear cómo se comportarán nuestros algoritmos a medida que las entradas se vuelvan cada vez más grandes.
Van a aprender un montón de estructuras de datos diferentes. Las llamaremos estructuras de datos clásicas, como árboles de búsqueda binaria, tablas hash-- que se llaman diccionarios en Python-- y estructuras de datos-- como árboles de búsqueda binaria balanceados-- que son más eficientes que solo los árboles de búsqueda binaria regulares. Y todas estas son estructuras de datos que fueron inventadas hace muchas décadas. Pero han resistido la prueba del tiempo y siguen siendo útiles. Vamos a aumentar estas estructuras de datos de varias maneras para hacerlas más eficientes para ciertos tipos de problemas. Y aunque no van a hacer mucho diseño de algoritmos en esta clase, sí harán algo de diseño y mucho análisis. La clase que sigue a esta, 6.046 Diseño y Análisis de Algoritmos, es una clase que deberían tomar si les gusta esta. Y podrán hacer mucho más diseño de algoritmos en 6.046. Pero verán estructuras de datos clásicas y algoritmos clásicos para estas estructuras de datos, incluyendo cosas como ordenamiento y emparejamiento, y así sucesivamente. Y una de las cosas agradables de esta clase es que estarán haciendo implementaciones reales de estas estructuras de datos y algoritmos en Python. Y en particular, cada uno de los conjuntos de problemas en esta clase tendrá tanto una parte teórica como una parte de programación. Así que, con suerte, todo se conectará. Las cosas de las que vamos a hablar en las conferencias y recitaciones estarán directamente conectadas a las partes teóricas de los conjuntos de problemas. Y estarán programando los algoritmos de los que hablamos en la conferencia, o aumentándolos, ejecutándolos. Averiguando si funcionan bien con entradas grandes o no.
Así que déjenme hablar un poco sobre los módulos en esta clase y los conjuntos de problemas. Y esperamos que estos conjuntos de problemas sean divertidos para ustedes. Y por divertido no me refiero a fácil. Me refiero a desafiante y valioso, para que al final sientan que han aprendido algo y se han divertido en el camino. ¿Está bien? Así que, en términos de contenido-- --tenemos ocho módulos en la clase. Cada uno de los cuales, a grandes rasgos, tiene un conjunto de problemas asociado. El primero de estos es lo que llamamos pensamiento algorítmico. Y comenzaremos con eso hoy. Veremos un problema particular, como mencioné, de búsqueda de picos. Y como parte de esto, tendrán un conjunto de problemas que se publicará hoy también. Y encontrarán que en este conjunto de problemas algunos de estos algoritmos de los que hablo hoy estarán codificados en Python y se les proporcionarán. Algunos de ellos tendrán errores. Tendrán que analizar la complejidad de estos algoritmos; averiguar cuáles son correctos y eficientes; y escribir una prueba para uno de ellos. ¿Está bien? Así que eso es un ejemplo de conjunto de problemas. Y pueden esperar que la mayoría de los conjuntos de problemas sigan ese tipo de plantilla. Está bien. Así que tendrán una mejor idea de esto al final del día de hoy, sin duda. O una idea concreta de esto, porque habremos terminado con la conferencia y verán su primer conjunto de problemas.
Vamos a hacer un módulo sobre ordenamiento y árboles. El ordenamiento ya lo conocen, ordenar un montón de números. Imaginen si tuvieran un billón de números y quisieran ordenarlos. ¿Qué tipo de algoritmo podrían usar para eso? Los árboles son una estructura de datos maravillosa. Hay diferentes variedades, siendo la más común los árboles binarios. Y hay formas de hacer todo tipo de cosas, como programación y ordenamiento, usando varios tipos de árboles, incluidos los árboles binarios. Y tenemos un conjunto de problemas sobre simular una red lógica usando un tipo particular de algoritmo de ordenamiento en una estructura de datos. Ese será su segundo conjunto de problemas. Y más rápidamente, tendremos módulos sobre hashing, donde hacemos cosas como comparación de genomas. En términos anteriores comparamos un genoma humano con un genoma de rata, y descubrimos que eran bastante similares. 99% similares, lo cual es bastante asombroso. Pero nuevamente, estas cosas son tan grandes que deben tener eficiencia en los métodos de comparación que utilizan. Y encontrarán que si no logran que la complejidad sea lo suficientemente baja, simplemente no podrán completar-- su programa no podrá terminar de ejecutarse dentro del tiempo que se debe entregar su conjunto de problemas. ¿Está bien? Lo cual es un poco problemático. Así que eso es algo a tener en cuenta mientras prueban su código. La realidad es que recibirán entradas grandes para ejecutar su código. Y quieren tener en cuenta la complejidad mientras codifican y piensan en el pseudocódigo, si se quiere, de su algoritmo.
Hablaremos sobre numéricos. Muchas veces hablamos de números tan grandes que 32 bits no son suficientes. O 64 bits no son suficientes para representar estos números. Estos números tienen miles de bits. Un buen ejemplo es la encriptación RSA, que se utiliza en SSL, por ejemplo. Y cuando usan https en sitios web, RSA se utiliza en el backend. Y típicamente trabajan con números primos que tienen miles de bits de longitud en RSA. Así que, ¿cómo manejan eso? ¿Cómo maneja Python eso? ¿Cómo escriben algoritmos que pueden lidiar con lo que se llaman números de precisión infinita? Así que tenemos un módulo sobre numéricos a mitad del semestre que habla sobre eso. Gráficas, realmente una estructura de datos fundamental en toda la ciencia de la computación. Puede que hayan oído hablar de la famosa tarea del cubo Rubik de 6.006, un cubo Rubik de 2 por 2 por 2. ¿Cuál es el número mínimo de movimientos necesarios para ir de una configuración inicial dada a la configuración final, donde todas las caras-- cada una de las caras tiene un color uniforme? Y eso se puede plantear como un problema de gráfica. Probablemente haremos eso este semestre. En semestres anteriores hemos hecho otras cosas como el rompecabezas de 15. Así que algunos de estos son tentativos. Definitivamente sabemos cómo es el primer conjunto de problemas, pero el resto de ellos son, en este momento, tentativos. Y para terminar, caminos más cortos. Nuevamente en términos anteriores les hemos pedido que escriban código usando un algoritmo particular que encuentra el camino más corto de Caltech a MIT. Esta vez podemos hacer las cosas un poco diferentes. Estábamos pensando que tal vez les daremos un mapa de calles de Boston y averiguaremos si Paul Revere usó el camino más corto para llegar a donde iba, o cosas así. Intentaremos hacerlo divertido. La programación dinámica es una técnica de diseño de algoritmos importante que se utiliza en muchos, muchos problemas. Y se puede usar para hacer una variedad de cosas, incluida la compresión de imágenes. ¿Cómo comprimes una imagen para que el número de píxeles se reduzca, pero aún se vea como la imagen con la que comenzaste, que tenía muchos más píxeles? ¿Está bien? Así que podrías usar programación dinámica para eso. Y finalmente, temas avanzados, teoría de la complejidad, investigación y algoritmos. Con suerte, para este momento en el curso, ya estarán convencidos de los algoritmos. Y la mayoría, si no todos ustedes, querrán seguir una carrera en algoritmos. Y les daremos una idea de qué más hay. Solo estamos rascando la superficie en esta clase, y hay muchas, muchas clases que pueden tomar si quieren continuar aprendiendo sobre algoritmos, o seguir una carrera en algoritmos. ¿Está bien? Así que esa es la historia de la clase, o el resumen de la clase. Y les animo a que pasen unos minutos en el sitio web. En particular, lean la política de colaboración y tengan una idea de lo que se espera de ustedes. Cuáles son las reglas en términos de hacer los conjuntos de problemas. Y la descomposición de calificaciones del curso, las políticas de calificación están todas listadas en el sitio web también. ¿Está bien?
OK. Así que empecemos. Quiero hablar sobre un problema específico. Y hablar sobre algoritmos para un problema específico. Elegimos este problema porque es tan fácil de entender. Y son algoritmos bastante sencillos que no son particularmente eficientes para resolver este problema. Así que este es un tipo de problema de juguete. Pero como muchos problemas de juguete, es muy evocador en el sentido de que señala los problemas involucrados en diseñar algoritmos eficientes. Así que comenzaremos con una versión unidimensional de lo que llamamos búsqueda de picos. Y un buscador de picos es algo en el caso unidimensional. Funciona en un arreglo de números. Y solo estoy poniendo-- --símbolos para cada uno de estos números aquí. Y los números son positivos, negativos. Supongamos que todos son positivos, realmente no importa. Los algoritmos que describimos funcionarán. Así que tenemos este arreglo unidimensional que tiene nueve posiciones diferentes. Y de la a a la i son números. Y queremos encontrar un pico. Así que tenemos que definir qué queremos decir con un pico. Y así, en particular, como ejemplo, la posición 2 es un pico si, y solo si, b es mayor o igual a a, y b es mayor o igual a c. Así que es realmente una propiedad muy local correspondiente a un pico. En el caso unidimensional, es trivial. Mira a tu izquierda. Mira a tu derecha. Si eres igual o mayor que ambos elementos que ves a la izquierda y a la derecha, eres un pico. ¿Está bien? Y en el caso de los bordes, solo tienes que mirar a un lado. Así que la posición 9 es un pico si i es mayor o igual a h. Así que solo tienes que mirar a tu izquierda allí, porque estás todo el camino a la derecha. ¿Está bien? Así que eso es todo. Y la declaración del problema, la versión unidimensional, es encontrar el pico si existe. ¿Está bien? Eso es todo. Les voy a dar un algoritmo sencillo. Y luego veremos si podemos mejorarlo. ¿Está bien? Pueden imaginar que el algoritmo sencillo es algo que simplemente, ya saben, recorre el arreglo. Pero necesitamos eso como un punto de partida para construir algo más sofisticado. Así que digamos que comenzamos desde la izquierda y todo lo que tenemos es un recorrido, realmente. Así que digamos que tenemos 1, 2, y luego tenemos n sobre 2 aquí correspondiente al medio de este arreglo de n elementos. Y luego tenemos n menos 1, y n. Lo que me interesa es no solo proponer un algoritmo sencillo, sino también caracterizar precisamente cuál es su complejidad en relación a n, que es el número de entradas. ¿Sí? ¿Pregunta?
AUDIENCIA: ¿Por qué dices "si existe" cuando los criterios en el [INAUDIBLE] garantizan [INAUDIBLE]?
PROFESOR: Eso es exactamente correcto. Iba a llegar a eso. Así que si miras la definición del pico, entonces lo que tengo aquí es mayor o igual a. ¿Está bien? Y así-- Esa es una gran pregunta que se hizo. ¿Por qué hay "si existe" en este problema? Ahora, en el caso donde tengo mayor o igual a, entonces-- esta es una pregunta de tarea para ustedes, y para el resto de ustedes-- argumenten que cualquier arreglo siempre tendrá un pico. ¿Está bien? Ahora, si no tuvieras el mayor o igual a, y tuvieras un mayor que, entonces ¿puedes hacer ese argumento? No, no puedes. ¿Verdad? Así que gran pregunta. En este caso es solo una cuestión-- Querrías modificar esta declaración del problema para encontrar el pico. Pero si tuviera una definición diferente de un pico-- y esta es parte del pensamiento algorítmico. Quieres poder crear algoritmos que sean generales, así que si la definición del problema cambia, aún tengas un punto de partida para atacar la segunda versión del problema. ¿Está bien? Así que podrías eliminar esto en el caso de la definición de mayor o igual a. El "si existe", porque un pico siempre existirá. Pero probablemente querrás argumentar eso cuando quieras mostrar la corrección de tu algoritmo. Y si de hecho tuvieras una definición diferente, bueno, tendrías que crear un algoritmo que te diga con certeza que un pico no existe, o encontrar un pico si existe. ¿Está bien? Así que ese es realmente el caso general. Muchas veces es posible que te pidan hacer algo, y no puedes realmente dar una respuesta a la pregunta, o encontrar algo que satisfaga todas las restricciones requeridas. Y en ese caso, querrás poder levantar la mano y decir, ya saben qué? Busqué largo y tendido. Busqué exhaustivamente. Aquí está mi argumento de que busqué exhaustivamente, y no pude encontrarlo. ¿Está bien? Si haces eso, puedes mantener tu trabajo. ¿Está bien? De lo contrario, siempre existe el caso de que no buscaste lo suficientemente duro. Así que es bueno tener ese argumento. ¿Está bien? Genial. Gracias por la pregunta. Siéntanse libres de interrumpir. Levanten la mano, y estoy observando a ustedes, y estoy feliz de responder preguntas en cualquier momento. Así que hablemos sobre el algoritmo sencillo. El algoritmo sencillo es algo que comienza desde la izquierda y simplemente camina a través. Y podrías tener algo que se vea así. ¿Está bien? Por eso-- Por esto quiero decir que los números están aumentando a medida que comienzas desde la izquierda, el pico está en algún lugar en el medio, y luego las cosas comienzan a disminuir. ¿Verdad? Así que en este caso, ya saben, este podría ser el pico. También pueden tener una situación donde el pico está todo el camino a la derecha, comenzaste desde la izquierda. Y son 1, 2, 3, 4, 5, 6, literalmente en términos de los números. Y vas a mirar n elementos yendo todo el camino a la derecha para encontrar el pico. Así que en el caso del medio mirarías n sobre 2 elementos. Si estuviera justo en el medio. Y la complejidad, la complejidad en el peor de los casos-- --es lo que llamamos theta n. Y es theta n, porque en el peor de los casos, podrías tener que mirar todos los elementos n. Y ese sería el caso donde comenzaste desde la izquierda y tuviste que ir todo el camino a la derecha. Ahora recuerda que theta n es esencialmente algo que dice del orden de n. Así que te da tanto el límite inferior como el límite superior. Big O de n es solo límite superior. Y lo que estamos diciendo aquí es que este algoritmo que comienza desde la izquierda va a requerir, esencialmente, en el peor de los casos, algo que es una constante por n. ¿Está bien? Y saben que esa constante podría ser 1. Podrías ciertamente configurar las cosas de esa manera. O si tuvieras un tipo diferente de algoritmo, tal vez podrías trabajar en la constante. Pero en resumen, solo nos preocupa, en este momento, la complejidad asintótica. Y la complejidad asintótica de este algoritmo es lineal. ¿Está bien? ¿Eso tiene sentido? ¿Está bien? Así que alguien ayúdame a hacerlo mejor. ¿Cómo podemos hacerlo mejor? ¿Cómo podemos reducir la complejidad asintótica de un buscador de picos unidimensional? ¿Alguien quiere intentarlo? Sí, ¿allí atrás?
AUDIENCIA: Hacer una búsqueda binaria en un subconjunto. Miras el medio, y sea cual sea el lado más alto, entonces cortas eso a la mitad, porque sabes que hay un pico.
PROFESOR: En--
AUDIENCIA: Por ejemplo, si estás en el medio en el lado derecho-- hay un número más alto en el lado derecho-- entonces solo mirarías eso, porque sabes que tu pico está en algún lugar allí. Y continúas cortando a la mitad.
PROFESOR: ¡Excelente! ¡Excelente! Eso es exactamente correcto. Así que puedes-- Puedes hacer algo diferente, que es esencialmente intentar descomponer este problema. Usar una estrategia de divide y vencerás, y recursivamente descomponer este arreglo unidimensional en arreglos más pequeños. Y tratar de reducir esta complejidad. Sí, ¿allí atrás?
AUDIENCIA: ¿Estamos asumiendo que solo hay un pico?
PROFESOR: No, no lo estamos.
AUDIENCIA: Está bien.
PROFESOR: Es encontrar un pico si existe. Y en este caso es, "encontrar un pico", debido a la definición. Realmente no necesitamos esto como se discutió. ¿Está bien? Así que-- Así que esa fue una gran respuesta, y-- Saben, esta clase después de un tiempo se va a volver aburrida. ¿Verdad? Cada clase se vuelve aburrida. Así que, ya saben, intentamos romper un poco la monotonía aquí. Y así-- Y luego lo otro que nos dimos cuenta fue que estos asientos en los que están sentados-- esta es una buena aula-- pero los asientos en los que están sentados son un poco duros. ¿Verdad? Así que lo que Eric y yo decidimos fue ayudarles, especialmente a los que están-- que están interactuando con nosotros. Y tenemos estos-- [RÍE] --cojines que son cojines de 6.006. Y, ya saben, este es un cubo Rubik de 2 por 2 por 2 aquí. Y dado que respondiste la primera pregunta, obtienes un cojín. Esto es un poco como un frisbee, pero no realmente. Así que-- [RÍE] No estoy seguro-- No estoy seguro de que voy a poder dártelo. Pero lo otro que quiero decir es que esto no es un juego de béisbol. ¿Verdad? Donde simplemente agarras la pelota a medida que pasa. Esto es para él, mi amigo de la camiseta roja. Así que aquí tienes. Ah, qué pena. Está bien. Es suave. Así que, ya saben, no les dolerá si les golpea. [RÍE] Así que tenemos un montón de estos. Y levanten las manos, ya saben, voy a preguntar-- Va a haber-- Creo que-- Hay algunas preguntas triviales que vamos a hacer solo para asegurarnos de que estén despiertos. Así que una respuesta a eso no les da un cojín. Pero una respuesta como-- ¿Cuál es tu nombre?
AUDIENCIA: Chase.
PROFESOR: Chase. Una respuesta como la que acaba de dar Chase es-- esa es una buena respuesta a una pregunta no trivial. Eso te da un cojín. ¿Está bien?
Está bien, genial. Así que pongamos el algoritmo de Chase aquí arriba. Voy a escribirlo para la versión 1D. Así que lo que tenemos aquí es un algoritmo recursivo. Así que la imagen que quieren mantener en su cabeza es esta imagen que puse allí. Y este es un algoritmo de divide y vencerás. Van a ver este paradigma una y otra vez en 6.006. Vamos a mirar la posición n sobre 2. Y vamos a mirar a la izquierda, y vamos a mirar a la derecha. Y vamos a hacer eso en secuencia. Así que-- --si a n sobre 2 es menor que a n sobre 2 menos 1, entonces-- --solo mira la mitad izquierda. 1 hasta n sobre 2 menos 1 para buscar un pico-- para un pico. ¿Está bien? Así que ese es el paso uno. Y saben que podría ponerlo en el lado derecho o en el lado izquierdo, no importa. Elegí hacerlo primero en el lado izquierdo, la mitad izquierda. Y así lo que he hecho es, a través de ese paso, si de hecho tienes esa condición-- a n sobre 2 es menor que a n sobre 2 menos 1-- entonces te mueves a la izquierda y trabajas en una mitad del problema. Pero si eso no es el caso, entonces si n sobre-- n sobre 2 es menor que a sobre n sobre-- n por 2 más 1, entonces solo mira n sobre 2 más 1 hasta n para un pico. Así que no me he molestado en escribir todas las palabras. Son exactamente las mismas que el lado izquierdo. Solo miras al lado derecho. De lo contrario, si ambas condiciones no se activan, en realidad has terminado. ¿Está bien? Eso es en realidad el mejor caso en términos de terminar temprano, al menos en este paso recursivo. Porque ahora la posición n sobre 2 es un pico. Porque lo que encontraste es que la posición n sobre 2 es mayor o igual a ambas posiciones adyacentes, y esa es exactamente la definición de un pico. Así que has terminado. ¿Está bien? Así que todo esto es bueno. Quieren escribir un argumento de que este algoritmo es correcto. Y no me voy a molestar con eso. Solo agito un poco las manos, y todos ustedes asintieron, así que hemos terminado con eso. Pero el punto es que verán en su conjunto de problemas un argumento preciso para un algoritmo más complicado, la versión 2D de esto. Y eso debería ser una plantilla para que vayan a escribir una prueba, o un argumento, un argumento formal, de que un algoritmo particular es correcto. Que hace lo que dice que hace. Y en este caso son dos, tres líneas de razonamiento cuidadoso que esencialmente dicen, dada la definición del pico, que esto va a encontrar un pico en el arreglo que se les da. ¿Está bien? Así que todos creemos que este algoritmo es correcto. Hablemos ahora sobre la complejidad de este algoritmo. Porque el objetivo de este algoritmo fue porque no nos gustaba esta complejidad theta n correspondiente al algoritmo sencillo. Así que nos gustaría hacerlo mejor. Así que lo que me gustaría hacer es pedir a uno de ustedes que me dé una relación de recurrencia del tipo, ya saben, T de n es blah, blah, blah. Que correspondería a este algoritmo recursivo, este algoritmo de divide y vencerás. Y luego, usando eso, me gustaría llegar a la complejidad real en términos de cuál es la theta de la complejidad correspondiente. Sí, ¿allí atrás?
AUDIENCIA: Así que el peor escenario si T de n va a ser algún tiempo constante--
PROFESOR: Sí.
AUDIENCIA: --que toma investigar si un cierto elemento es [INAUDIBLE], más-- [TOS] --T de n sobre 2.
PROFESOR: Genial. Exactamente correcto. Eso es exactamente correcto. Así que si miras este algoritmo y dices, desde un punto de vista computacional, ¿puedo escribir una ecuación correspondiente a la ejecución de este algoritmo? Y dices, T de n es el trabajo que este algoritmo hace en-- como entrada de tamaño n. ¿Está bien? Entonces puedo escribir esta ecuación. Y este theta 1 corresponde a las dos comparaciones que haces mirando-- potencialmente las dos comparaciones que haces-- mirando el lado izquierdo y el lado derecho. Así que eso es-- 2 es una constante, así que por eso ponemos theta 1. ¿Está bien? Así que obtienes un cojín también. Cuidado chicos. ¡Whoa! Oh, en realidad eso no fue tan malo. Bien. Se desvía a la izquierda, Eric. Se desvía a la izquierda. Así que si tomas esto y comienzas a expandirlo, eventualmente llegarás al caso base, que es T de 1 es theta 1. ¿Verdad? Porque tienes un arreglo de un elemento, solo por ese arreglo va a devolver eso como un pico. Y así, si haces eso, y lo expandes completamente, entonces puedes escribir T de n igual a theta 1 más theta 1. Y vas a hacer esto log en base 2 de n veces. Y sumando todo esto, te da una complejidad theta log 2 de n. ¿Verdad? Así que ahora comparas esto con eso. Y realmente hay una gran diferencia. Hay una diferencia exponencial. Si codificas este algoritmo en Python-- y lo hice-- ambos estos algoritmos para la versión 1D-- y si lo ejecutas con n siendo 10 millones o más, entonces este algoritmo toma 13 segundos. ¿Está bien? El-- El algoritmo theta 10 toma 13 segundos. Y este toma 0.001 segundos. ¿Está bien? Gran diferencia. Así que hay una gran diferencia entre theta n y theta log n. Es literalmente la diferencia entre 2 elevado a n, y n. Tiene sentido tratar de reducir la complejidad como pueden ver, especialmente si están hablando de entradas grandes. ¿Está bien? Y verán eso más claramente a medida que vayamos a una versión 2D de este problema. ¿Está bien? Así que realmente no puedes hacerlo mejor para la 1D. La 1D es un problema sencillo. Se vuelve un poco más interesante-- los problemas se vuelven un poco-- disculpen, los algoritmos se vuelven un poco más sofisticados cuando miramos una versión 2D de búsqueda de picos. Así que hablemos sobre la versión 2D. Así que como pueden imaginar en la versión 2D tienen una matriz, o un arreglo bidimensional. Y digamos que esta cosa tiene n filas y m columnas. Y ahora tenemos que definir qué es un pico. Y es una colina. Es la definición obvia de un pico. Así que si tuvieran un a aquí, c, b, d, e. Entonces, como pueden adivinar, a es un pico 2D si, y solo si, a es mayor o igual a b; a es mayor o igual a d, c y e. ¿Está bien? Así que es una pequeña colina allí. ¿Está bien? Y nuevamente he usado el mayor o igual a aquí, así que eso es similar a la 1D en el caso de que siempre encontrarán un pico en cualquier matriz 2D. Ahora nuevamente les daré el algoritmo sencillo, y lo llamaremos el algoritmo de Ascenso Codicioso. Y el algoritmo de Ascenso Codicioso esencialmente elige una dirección y, ya saben, intenta seguir esa dirección para encontrar un pico. Así que, por ejemplo, si tuviera esta matriz particular; 14, 13, 12, 15, 9, 11, 17-- Entonces lo que podría suceder es que si comenzara en algún punto medio arbitrario-- Así que el algoritmo de Ascenso Codicioso tiene que tomar decisiones sobre dónde comenzar. Al igual que tuvimos diferentes casos aquí, tienes que tomar una decisión sobre dónde comenzar. Podrías querer comenzar en el medio, y podrías querer trabajar hacia la izquierda primero. O vas a todo-- Solo sigues yendo a la izquierda, o sigues yendo a la derecha. Y si llegas a un borde, bajas. Así que tomas algunas decisiones sobre cuáles son las direcciones de recorrido predeterminadas. Y así, si dices que quieres comenzar con 12, vas a buscar algo a la izquierda. Y si es mayor, seguirás esa dirección. Si no, si es menor, entonces irás en la otra dirección, en este caso, por ejemplo. Así que en este caso irás a 12, 13, 14, 15, 16, 17, 19 y 20. Y encontrarías-- Encontrarías este pico. Ahora no les he dado los detalles específicos de un algoritmo de Ascenso Codicioso. Pero creo que si miran las posibilidades en el peor de los casos aquí, con respecto a una matriz dada, y para cualquier punto de partida dado, y para cualquier estrategia-- en términos de elegir izquierda primero, frente a derecha primero, o abajo primero frente a arriba primero-- tendrán una situación donde-- al igual que tuvimos en el caso 1D-- pueden terminar tocando una gran fracción de los elementos en este arreglo 2D. ¿Está bien? Así que en este caso, terminamos, ya saben, tocando un montón de elementos diferentes. Y es bastante posible que puedan terminar tocando-- comenzando desde el punto medio-- podrían terminar tocando la mitad de los elementos, y en algunos casos, tocando todos los elementos. Así que si hacen un análisis en el peor de los casos de este algoritmo-- un algoritmo particular con elecciones particulares en términos del punto de partida y la dirección de búsqueda-- un algoritmo de Ascenso Codicioso tendría una complejidad theta n m. ¿Está bien? Y en el caso donde n es igual a m, o m es igual a n, tendrías una complejidad theta n cuadrado. ¿Está bien? No voy a pasar mucho tiempo en esto, porque quiero hablarles sobre las versiones de divide y vencerás de este algoritmo para el pico 2D. Pero espero que todos estén conmigo con respecto a cuál es la complejidad en el peor de los casos. ¿Está bien? ¿La gente lo acepta? Sí. Pregunta allí atrás.
AUDIENCIA: ¿Puedes-- es eso una aproximación? ¿O puedes llegar realmente a n veces m recorridos?
PROFESOR: Así que hay algoritmos de Ascenso Codicioso específicos, y matrices específicas donde, si te doy el código para el algoritmo, y te doy una matriz específica, podría hacer que toques todos estos elementos. Eso es correcto. Así que estamos hablando de peor caso. Estás siendo muy paranoico cuando hablas de complejidad en el peor de los casos. Y así, estoy-- agitando un poco las manos aquí, simplemente porque no te he dado los detalles del algoritmo aún. ¿Está bien? Esto es realmente un conjunto de algoritmos, porque no te he dado el código, no te he dicho dónde comienza, y en qué dirección va. Pero tú vas, haces eso, lo fijas, y yo sería la persona que intenta encontrar la complejidad en el peor de los casos. De repente es muy fácil llegar a theta n m en términos de tener alguna constante multiplicando n por m. Pero definitivamente puedes llegar a que esa constante esté muy cerca de 1. ¿Está bien? Si no es 1.
Así que hablemos de divide y vencerás. Y digamos que hice algo así, donde simplemente intenté meter el algoritmo de búsqueda binaria en la versión 2D. ¿Está bien? Así que lo que voy a hacer es-- --voy a elegir la columna del medio, j igual a m sobre 2. Y voy a encontrar un pico 1D usando cualquier algoritmo que quiera. Y probablemente terminaré usando el algoritmo más eficiente, la versión de búsqueda binaria que ha ido todo el camino a la izquierda de la pizarra allí. Y digamos que encuentro un pico binario en (i, j). Porque he elegido una columna, y solo estoy encontrando un pico 1D. Así que esto es j igual a m sobre 2. Eso es i. Ahora uso (i,j). En particular la fila i como un inicio-- --para encontrar un pico 1D en la fila i. Y me pongo aquí, estoy realmente feliz. ¿Está bien? Porque digo, wow. Elegí una columna del medio, encontré un pico 1D, eso es theta m de complejidad para encontrar un pico 1D como argumentamos. Y un lado-- el theta m--
AUDIENCIA: Log n.
PROFESOR: Oh, lo siento. Tienes razón. La complejidad log n, eso es lo que era. Así que lo tengo aquí. Sí. Gracias, Eric. Y luego, una vez que hago eso, puedo encontrar un pico 1D en la fila i. En este caso, la fila i sería de m de ancho, así que sería log m de complejidad. Si n es igual a m, entonces tengo un par de pasos de log n, y he terminado. ¿Está bien? ¿He terminado? No. ¿Puede alguien decirme por qué no he terminado? Precisamente. Sí.
AUDIENCIA: Porque cuando haces la segunda parte para encontrar el pico en la fila i, puede que no haya un pico en la columna.
PROFESOR: Eso es exactamente correcto. Así que este algoritmo es incorrecto. ¿Está bien? No funciona. Y les daré un ejemplo simple aquí donde no funciona. El problema es-- --un pico 2D-- --puede no existir-- --en la fila i. Y aquí hay un ejemplo de eso. De hecho, este es-- Este es exactamente el ejemplo de eso. Supongamos que comencé con esta fila. Dado que es-- estoy comenzando con la fila del medio, y podría comenzar con esta o aquella. Supongamos que comencé con esa. Termino encontrando un pico. Y si esto fuera 10 aquí arriba, elegiría 12 como un pico. Y es bastante posible que devuelva 12 como un pico. A pesar de que 19 es más grande, porque 12 es un pico dado 10 y 11 aquí arriba. Y luego, cuando elijo esta fila particular, y encuentro un pico en esta fila, sería 14. Eso es un pico 1D en esta fila. Pero 14 no es un pico 2D. ¿Está bien? Así que en este ejemplo particular, 14 devolvería 14. Y 14 no es un pico 2D. ¿Está bien? Puedes recoger tu cojín después de la clase. Así que no es tan bueno. Parece un algoritmo eficiente, pero no funciona. ¿Está bien? Así que, ¿cómo podemos llegar a algo que realmente funcione? Así que el último algoritmo que les voy a mostrar-- Y verán cuatro algoritmos diferentes codificados en Python-- no voy a revelar cuáles son esos algoritmos, pero tendrán que reconocerlos. Verán versiones de esos algoritmos ya en la conferencia. Y su trabajo será analizar los algoritmos, como dije antes, probar que uno de ellos es correcto, y encontrar contraejemplos para los que no son correctos. El personal del curso se quedará aquí para responder preguntas-- preguntas logísticas-- o preguntas sobre la conferencia. Y le debo a ese caballero un cojín.