[SER222] Recurrences (4/7): Guessing a Growth Function

Summary

En este video, se analiza cómo formular una función de crecimiento para el algoritmo de la Torre de Hanói. El presentador comienza explicando cómo f(n) representa el número de movimientos requeridos para resolver el problema con n discos, destacando que f(1) es igual a 1. Luego, explora la recurrencia f(n) = 2f(n-1) + 1, explicando el comportamiento recursivo del algoritmo. Se sugiere una solución cerrada aproximada, f(n) = 2^n - 1, y se introduce el concepto de usar la inducción matemática para probar que esta conjetura es correcta en el siguiente video.

Takeaways

• 🔍 El video trata de descubrir la función de crecimiento del algoritmo de pseudocódigo del Torre de Hanoi.
• 📐 La función f(n) representa el número de movimientos necesarios para resolver el problema del Torre de Hanoi con n discos.
• 👉 f(1) se define como 1, ya que mover un disco de un lado a otro requiere un solo movimiento.
• 🔄 La función f(n) para n > 1 se describe como f(n) = 2 * f(n-1) + 1, basada en los pasos recursivos del algoritmo.
• 💡 Se sugiere que f(n) podría ser una función cerrada que resulte en un número de movimientos que se asemeje a una potencia de dos.
• 📊 Se utiliza una tabla en Excel para calcular valores de f(n) y buscar patrones que ayuden a formular una función cerrada.
• 🤔 Se plantea la posibilidad de que f(n) = 2^n - 1, basándose en los patrones observados en los cálculos manuales.
• 🔄 El algoritmo es de tiempo exponencial, ya que cada llamada recursiva duplica la cantidad de trabajo.
• 🧮 Se menciona que la función propuesta f(n) = 2^n - 1 es solo una suposición y requiere prueba matemática para verificar su corrección.
• 📘 Se anuncia que en el próximo video se probará matemáticamente que f(n) = 2^n - 1 y f(n) = 2 * f(n-1) + 1 son equivalentes utilizando la inducción matemática.

Q & A

¿Qué es la función de crecimiento que se busca analizar en el video?

La función de crecimiento que se busca analizar es f(n), donde n es el número de discos en el problema de la Torre de Hanoi, y f(n) representa el número de movimientos necesarios para resolverlo.

¿Cuál es el valor de f(1) y por qué?

El valor de f(1) es 1, ya que con un solo disco, el algoritmo de la Torre de Hanoi requiere solo un movimiento para completarse.

¿Cómo se puede expresar f(n) en el caso general?

El caso general de f(n) se expresa como f(n) = 2 * f(n - 1) + 1, lo que indica que se deben hacer dos movimientos recursivos para un subconjunto de discos, más un movimiento adicional.

¿Qué representa el término '2 * f(n - 1)' en la fórmula recursiva?

El término '2 * f(n - 1)' representa dos movimientos necesarios para mover las torres de tamaño n-1 dos veces, una para mover la torre al destino intermedio y otra para moverla al destino final.

¿Qué se busca lograr con una función en forma cerrada para f(n)?

Se busca una función en forma cerrada para f(n) que permita calcular directamente el número de movimientos sin recurrencia, simplificando así el cálculo y obteniendo una solución más eficiente.

¿Cómo se identifica un patrón en los valores calculados de f(n)?

El patrón en los valores calculados de f(n) muestra que parecen seguir una secuencia de potencias de dos, lo que sugiere una función exponencial debido al hecho de que el algoritmo realiza el doble de trabajo en cada llamada recursiva.

¿Cuál es la propuesta inicial para la forma cerrada de f(n)?

La propuesta inicial para la forma cerrada de f(n) es f(n) = 2^n - 1, basada en el patrón observado en los cálculos.

¿Por qué no es suficiente con adivinar la función cerrada?

No es suficiente con adivinar la función cerrada porque, aunque la propuesta parece correcta para valores pequeños de n, no hay garantía de que sea precisa para valores más grandes, y se necesita una prueba formal para confirmarlo.

¿Qué método se sugiere para probar la corrección de la función propuesta?

Se sugiere usar inducción matemática para probar que la función propuesta f(n) = 2^n - 1 es correcta y coincide con la fórmula recursiva original.

¿Por qué se dice que el algoritmo de la Torre de Hanoi es de tiempo exponencial?

Se dice que el algoritmo es de tiempo exponencial porque el número de movimientos necesarios crece de forma exponencial a medida que aumenta el número de discos, ya que en cada paso se duplican los movimientos requeridos.