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.
-
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).
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_arregloen cuatro partes, el costo y el límite de la pila de Python. Con seis ejercicios y el código encodigo/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.