[SER222] Recurrences (4/7): Guessing a Growth Function
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
🤔 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.
🔢 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
💡Torre de Hanoi
💡F de n (f(n))
💡Recursión
💡Función cerrada
💡Algoritmo exponencial
💡Propuesta (Conjetura)
💡Inducción matemática
💡Evaluación de funciones
💡Patrón de potencias 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.
Transcripts
- In this video, we're gonna try
and figure out what exactly would be a growth function,
for the Tower of Hanoi pseudocode algorithm
that we gave before.
So that same code is on the right-hand side.
Let's try analyzing it.
So what we want to write, is an f of n function
where n is the number of disks,
right, that's our problem size,
and the result of it, right,
f of n itself, is the number
of moves that are required to get there.
So think about this for yourself for a second.
What would f of one be?
What might that be said equal to?
So think about that.
So that's actually going to be said equal to
one, and then where that comes from
is we see, f of one corresponds
to this over here, right?
N is equal to one, the algorithm says do this.
Do this happens to be, make one move.
So that one move that's made,
that is what should be used for the f of one function.
So f of one equal one.
When the tower is one high, I make one move.
All right, that's the easy one,
what about the harder one?
How could f of n be written?
Think about that for one second.
All right, this is the more general case,
this is the case that involves the recursive steps.
(deep breathe)
So that will be a little more tricky.
That will be, f of n equal
two
f of n
(computer mouse clicking)
minus one
plus one.
So these lines of code here, right.
I have three lines of code.
On the first line of code, right
is moving a size n minus one tower.
So that would cost me f of n minus one.
But then I move a second tower also
of size n minus one that will also cost me
f of n minus one size.
F of n minus one moves.
So there that's what gets me this term
in front over here, the two of n minus one.
Gets over here, looks like I forgotten my one,
so let me add that in there,
and then the plus one comes from
the fact that I had one move that has to happen here,
so that ends up getting me that plus one there at the end.
Okay, so that's what we have.
F of one equal one, f of n equal 2,
f of n minus one plus one.
So that's what we have, and it's great
because it gives us the right answer,
but it's not great because it's a open solution.
I still have this recurrence there where every time
I want to valuate, you know, a lesser value.
So it makes it hard, basically to--
it make it's difficult for me to use this function.
So what I would like to do is try
and guess from that a closed-loop function, right,
or a closed form function for it.
Although just do this purely by guessing.
Which is something that will work,
if we're very, very lucky,
which isn't very common.
So, we'll just be happy though for this
for this example we can be happy right,
that we can do it this way.
It won't always be the case.
So what we could do, is we could calculate
out by hand some values for f of n.
And so, by hand I don't really mean
on a piece of paper but throw it in Excel, right?
Always, if you have tools for something,
use the tools, make your life easier,
don't make your life harder.
So over here we have a column here.
On the first column I have a table.
The first column I have is basically n, right, problem size.
The next thing I have is actually the evaluation of
our function that we figured out earlier,
our f of n equal two f of n minus one plus one.
I have the valuation of that.
Right so I can kind of put these side by side.
So ideally what I would have is I have
a very simple function that would take in n
and then would produce the values in the right hand side.
So if with something that takes in 10
and then returns 1,023.
That's what I would like, that's what I really, really want.
Here you might notice just a little bit of a pattern,
there's actually something that looks like
a power two number merging on the right-hand side.
This is actually an exponential time algorithm by the way.
It takes really, really long time to run.
Actually, yeah, maybe ask yourself for a second.
Why might look like a power of two?
Why?
Maybe go back and look at the code for a second.
Why might this look like a power of two?
Actually it's not so bad here.
The reason it looks like a power of two is
because it makes two recursive calls.
So every time you run it, it doubles
the amount of work it has to do.
So, if you're doubling, doubling, doubling,
well that's like a power of two.
So, we have something that looks like two of the n.
Okay, so on the right-hand side, maybe from that
kinda sequence, you would guess that,
"Hey, f of n looks like two of the n."
So we might think that for starters,
f of n equals two of the n,
then it looks like each of these numbers is off
by one, so let's throw our negative one there as well.
So our proposal would be from this chart
just guessing the pattern that
f of n equal two n minus one.
This would be our guess.
That's great, but of course there's this little snag here.
That is a guess, and a guess really isn't what we need.
We want to be right, we want to write a growth function
that we know for absolutely certain is
the correct growth function,
because it could be the case when n becomes really large,
oh hey, all of a sudden those things don't match up
by our algorithm computer recursively
doesn't have the same value as this two
of the n minus one over guessing.
That could happen, I don't have any evidence, right?
My chart only goes up so far, only goes up to 16.
Beyond that I don't have any evidence
that this thing is actually correct.
So when I do that in order to verify
this function is actually correct
and that it does actually match the recurrence,
we're going to have to break our induction, okay?
So in the next video, we're going to talk through
is proving mathematically that these two functions
the f of n, two the n minus one
and f of n equal two f of n minus one plus one
are the same, and we'll do that using induction.
So we'll do that next; it will be a little bit
involved from kinda the technical math-y perspective.
関連動画をさらに表示
[SER222] Recurrences (6/7): Proving f(n)
[SER222] Recurrences (3/7): Solving Towers of Hanoi
La antiderivada o integral de una función. Introducción al antidiferencial o primitivas.
[SER222] Analytical Analysis (1/5): Defining f(n)
[SER222] Asymptotics (3/5): Lower Bounds
Demostración 3 de la suma gaussiana (Gauss)
5.0 / 5 (0 votes)