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

Ruben Acuna

22 Sept 201705:55

Summary

TLDREn 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.

Outlines

00:00

🤔 Introducción al problema de la función de crecimiento en Tower of Hanoi

En este video, se analiza la función de crecimiento del algoritmo de pseudocódigo de Tower of Hanoi previamente presentado. Se busca definir una función f(n) donde 'n' es el número de discos, y f(n) es el número de movimientos necesarios. Se parte del caso base f(1) = 1, ya que para un solo disco, se realiza un único movimiento. Luego, se plantea el desafío de encontrar una expresión para f(n) en el caso general, que incluye pasos recursivos. El orador sugiere que la función para f(n) es 2*f(n-1) + 1, ya que implica mover torres de tamaño n-1 en cada paso.

05:04

🔢 De una solución recursiva a una posible función cerrada

Aunque la fórmula recursiva es correcta, no es ideal ya que implica una solución abierta. Para simplificar, se intenta obtener una función cerrada que evite la recurrencia, lo cual no siempre es posible. El orador propone calcular algunos valores de f(n) utilizando herramientas como Excel. A partir de los resultados, se observa un patrón que sugiere que f(n) podría estar relacionado con potencias de dos debido a las llamadas recursivas dobles del algoritmo, lo que lleva a la conjetura de que f(n) podría ser 2^n - 1.

📊 Verificación de la conjetura mediante inducción

Aunque se ha conjeturado que f(n) = 2^n - 1, esto solo es una hipótesis basada en un patrón observado para valores pequeños de n. El orador enfatiza la necesidad de verificar que esta fórmula es correcta para cualquier valor de n. Para hacerlo, se utilizará una prueba por inducción en el siguiente video, donde se demostrará que la conjetura coincide con la fórmula recursiva planteada. Esto requerirá un análisis matemático más técnico y detallado.

Mindmap

Keywords

💡Función de crecimiento

Una función de crecimiento describe cómo aumenta la cantidad de recursos o tiempo necesarios para resolver un problema a medida que aumenta el tamaño del mismo. En el video, la función de crecimiento busca calcular el número de movimientos necesarios para resolver el problema de la Torre de Hanoi, en función del número de discos.

💡Torre de Hanoi

La Torre de Hanoi es un famoso problema matemático y de algoritmos, donde el objetivo es mover una torre de discos de una varilla a otra, siguiendo reglas específicas. En el video, el pseudocódigo del algoritmo de la Torre de Hanoi se usa como ejemplo para explorar la función de crecimiento de un problema recursivo.

💡F de n (f(n))

f(n) es una función matemática que representa el número de movimientos necesarios para resolver la Torre de Hanoi con 'n' discos. La función f(1) es igual a 1, ya que mover un solo disco requiere un solo movimiento. Para valores mayores de n, la función incluye un enfoque recursivo, y el video explora cómo se puede definir f(n) de manera más general.

💡Recursión

La recursión es una técnica de programación en la que una función se llama a sí misma para resolver subproblemas más pequeños. En este caso, la función f(n) depende de la solución de f(n-1), lo que genera una recurrencia en la resolución del problema de la Torre de Hanoi.

💡Función cerrada

Una función cerrada es una expresión matemática que permite calcular el resultado de manera directa, sin recurrencia. En el video, se busca transformar la definición recursiva de f(n) en una función cerrada que facilite el cálculo del número de movimientos sin necesidad de computar todas las llamadas recursivas.

💡Algoritmo exponencial

Un algoritmo exponencial es aquel cuyo tiempo de ejecución crece de manera exponencial con respecto al tamaño del problema. En el video, el algoritmo de la Torre de Hanoi se clasifica como exponencial, ya que el número de movimientos se duplica con cada incremento en el número de discos.

💡Propuesta (Conjetura)

Una propuesta o conjetura en matemáticas es una suposición que se basa en observaciones y que aún no se ha demostrado formalmente. En el video, se hace una conjetura sobre la forma de la función f(n), sugiriendo que podría ser 2^n - 1, basada en la observación de patrones en los resultados.

💡Inducción matemática

La inducción matemática es una técnica utilizada para probar que una afirmación es verdadera para todos los números naturales. En el video, se menciona que se usará la inducción para demostrar que la conjetura de f(n) = 2^n - 1 es correcta para todos los valores de n.

💡Evaluación de funciones

La evaluación de funciones consiste en calcular el valor de una función para un número específico de entradas. En el video, se usan herramientas como Excel para calcular manualmente los valores de f(n) y compararlos con los resultados obtenidos por el algoritmo recursivo, a fin de verificar patrones.

💡Patrón de potencias de dos

El patrón de potencias de dos se refiere a la observación de que los valores de f(n) parecen seguir la forma 2^n. Esto ocurre porque el algoritmo de la Torre de Hanoi duplica el trabajo en cada nivel de recursión, lo que genera un crecimiento exponencial, similar a una potencia de dos.

Highlights

The goal is to find a growth function for the Tower of Hanoi pseudocode algorithm.

f(n) represents the number of moves required for n disks.

For n = 1, the number of moves is 1, since only one move is needed.

The recursive case is expressed as f(n) = 2 * f(n-1) + 1.

The recursive process involves moving a smaller tower of size n-1 twice.

The algorithm calculates the total moves recursively, making it difficult to solve directly.

A closed-form function for f(n) is desired to avoid the complexity of recursive calculations.

The speaker suggests calculating values for f(n) manually, possibly using Excel.

A pattern emerges where f(n) resembles powers of two, indicating exponential growth.

The speaker hypothesizes that f(n) could be approximated by 2^n - 1.

The recursive structure of the algorithm results in exponential time complexity.

The guess for the closed-form function f(n) = 2^n - 1 needs verification through mathematical proof.

The next step involves using mathematical induction to verify that the proposed function is correct.

The speaker acknowledges that a guess is insufficient without rigorous proof, especially for large n.

The video concludes by promising a deeper dive into proving the function through induction in the next segment.