Arcana

La Grieta de Vaelthorn

Se lee en 2 min

Temática: Recursividad · Relaciones de Recurrencia · Teorema Maestro

Contexto

Sos la guardiana del Archivo Arcano de Vaelthorn. Hace siglos se selló entre sus muros a una entidad ancestral, el Devorador de Ecos, pero algo despertó el sello: la entidad encontró la forma de replicarse cruzando grietas entre dimensiones paralelas, dejando ecos de sí misma a su paso. Cada vez que completa un ritual de invocación, el Devorador avanza más cerca del corazón del Archivo. Tu tarea es descifrar cuánto poder consume cada forma del ritual, para anticipar cuándo la Grieta terminará de abrirse.

Primer Presagio

Los primeros informes describen la forma más débil del Devorador: avanza por una cadena de n dimensiones, una por vez. En cada dimensión deja un eco de sí mismo y recién después cruza a la siguiente.

function INVOCAR(dimensiones, n):
    if n <= 1:
        dejar_eco(dimensiones[0])
        return
    dejar_eco(dimensiones[0])
    INVOCAR(dimensiones[1:n], n-1)

a) Trazar la ejecución de INVOCAR para n = 4, identificando claramente el caso base, la pila de llamadas (el “camino de cruces”) y el orden en que se resuelven al volver.

b) A partir del código, plantear la relación de recurrencia T(n) que describe el costo del ritual en función de n (no hace falta resolverla).

Abrir artículo

La Fisura se Abre

El Devorador mutó. En esta nueva forma, cada avatar que domina una región de n dimensiones:

  1. Traza primero un sello de contención sobre toda la región (costo lineal en n), para evitar que el Archivo detecte la fisura antes de tiempo.
  2. Se divide en dos avatares, y cada uno toma el control de la mitad de las dimensiones restantes.

a) Plantear la relación de recurrencia T(n) que modela el costo total del ritual.

b) Resolver la recurrencia por telescopía, mostrando el desarrollo paso a paso.

c) Verificar el resultado construyendo el árbol de recursión correspondiente (niveles, costo por nivel, cantidad de niveles y costo total).

d) ¿Los dos métodos te dieron el mismo orden de crecimiento? Justificá brevemente por qué tiene sentido que así sea.

Abrir artículo

El Despertar

Forma final del Devorador, la más peligrosa. Cada avatar que domina una región de n dimensiones se manifiesta en 2 nuevos avatares, pero cada uno solo logra estabilizarse en un cuarto de las dimensiones restantes (n/4). El ritual de invocación es más costoso cuanto mayor es la porción que intentan controlar. Antes de dividirse, los avatares deben sincronizar un sello maestro que recorre todas las dimensiones de la región original (costo lineal en n).

a) Plantear la relación de recurrencia T(n) que modela este escenario, identificando claramente a, b y f(n).

b) Resolver la recurrencia usando el Teorema Maestro, indicando explícitamente:

  • En qué caso del teorema cae.
  • Por qué se cumplen (o no) las condiciones de ese caso.

c) Comparando con lo que armaste en la fisura se abre, explicá con tus palabras qué representa, en el árbol de recursión, el caso del Teorema Maestro en el que cayó este ejercicio (¿domina el costo de las hojas? ¿el costo de la raíz? ¿están equilibrados?).

d) (Desafío opcional) Los arcanistas más viejos del Archivo sospechan que el sello maestro podría no ser lineal, sino un ritual que se “abarata” a medida que hay más dimensiones en juego, por ejemplo, . Si así fuera, ¿el Teorema Maestro seguiría aplicando tal cual? ¿A qué herramienta de las vistas en el sendero volverías para resolverlo?

Abrir artículo

Conclusión del sendero

A lo largo de las tres formas del Devorador de Ecos recorriste el mismo camino que suele aparecer al analizar el costo de un algoritmo recursivo:

  1. Primer Presagio te obligó a traducir un ritual (código recursivo) en una relación de recurrencia: el paso bisagra sin el cual no se puede aplicar ninguna técnica de resolución.
  2. La Fisura se Abre te mostró que telescopía y árbol de recursión son dos caminos distintos hacia el mismo resultado: uno más algebraico, otro más visual/intuitivo.
  3. El Despertar te presentó el Teorema Maestro como un atajo para resolver rápido una familia amplia de recurrencias… pero un atajo que solo tiene sentido si entendés por qué funciona, es decir, si podés conectarlo con lo que ya sabés del árbol de recursión.

La idea de fondo: el Teorema Maestro no reemplaza al árbol de recursión, lo resume. Cuando el sello maestro no cumpla las hipótesis del teorema, telescopía y árbol siguen siendo las herramientas que te van a sacar del apuro.

Vista Gráfica

Retroenlaces