Saltar a contenido

Clase 2. Invariantes de ciclo y divide y vencerás

Viernes 21 de agosto de 2026.

Esta semana los dos grupos van en puntos distintos del tema: el grupo A ya trabajó invariantes de ciclo en la sesión del miércoles con el profesor titular, y el grupo B no tuvo esa sesión por el festivo. La clase del viernes atiende esa diferencia con dos rutas, así que esta nota se divide en dos páginas: entre por la de su grupo.

  • Invariantes de ciclo


    Grupo B. El tema desde el comienzo: la especificación de un problema (entrada y salida), la pareja de invariantes I₀ e I₁ de un ciclo, y la demostración de correctitud por inicialización, estabilidad y terminación.

    Entrar

  • Divide y vencerás


    Grupo A. Un repaso corto de los invariantes I₀ e I₁ y la primera técnica de diseño recursivo: dividir, conquistar y combinar, con el máximo, el ordenamiento por mezcla y la recurrencia T(n) = 2·T(n/2) + Θ(n).

    Entrar

Apéndices

Tres páginas que sirven a los dos grupos y que quedaron de preguntas de clase y de correo:

  • El arreglo en el invariante y la inducción estructural — qué pasa con el invariante cuando el algoritmo modifica el arreglo (tres ejercicios resueltos, uno con dos ciclos anidados y sus dos parejas de invariantes) y la demostración por inducción estructural del máximo recursivo, escrita completa.
  • Resolver recurrencias por expansión — el álgebra que hay detrás del árbol de llamadas, con \(T(n) = 2\,T(n/2) + \Theta(1)\) y \(T(n) = 2\,T(n/2) + \Theta(n)\) desarrolladas paso a paso: las sustituciones, el patrón, la sumatoria y el aterrizaje en el caso base.
  • Recursión: qué pasar en la llamada y dónde parar — las dos preguntas que más cuestan al escribir una función recursiva, descubiertas sobre la pila de llamadas con la suma hasta \(n\), los dígitos de un número, la suma de un rango y la potencia; después la definición formal, la demostración por inducción de suma_arreglo en cuatro partes, el costo y el límite de la pila de Python. Con seis ejercicios y el código en codigo/recursion.py.

Ejercicios interactivos

Las dos rutas comparten la página de ejercicios interactivos: dos ejercicios de invariantes (sumar y factorial) y dos de divide y vencerás (mezclar y ordenar). Cada uno sigue el mismo camino de la clase: ver el patrón primero, generalizarlo después y cerrar con la demostración o el análisis paso a paso.