18 de mayo - 24 de mayo

Algoritmos iterativos avanzados y eficiencia

Dos punteros · Ventana deslizante · Sumas prefijas · Complejidad espacial · Generadores

[Holístico] CPython y bytecode  ·  Planificación de procesos

Durante las primeras semanas del curso construimos un repertorio iterativo básico: recorrer una secuencia con un índice, buscar linealmente, ordenar con bucles anidados, acumular un total. Estos patrones resuelven correctamente una variedad enorme de problemas, pero comparten una característica que termina siendo limitante: no aprovechan la estructura particular del problema. Si los datos están ordenados, los recorremos como si no lo estuvieran. Si calculamos sumas consecutivas de ventanas contiguas, recalculamos cada ventana desde cero. Si una expresión se repite en bucles anidados, la repetimos.

Esta semana cambiamos la óptica. La pregunta deja de ser «¿cómo recorro la entrada?» y pasa a ser «¿qué propiedad del problema puedo explotar para evitar trabajo redundante?». Bajo esta luz aparecen patrones algorítmicos que mejoran —a veces en un orden de magnitud— la eficiencia temporal o espacial sin recurrir a estructuras de datos más sofisticadas. Son refinamientos de la iteración elemental, no técnicas distintas: los bucles siguen siendo while y for, las condiciones de corte siguen apoyándose en invariantes; lo que cambia es la idea de avance.

Las dos secciones holísticas conectan lo aprendido con el resto del sistema computacional. El bytecode muestra que Python no es un lenguaje «mágico» sino una capa de abstracción sobre operaciones simples ejecutadas por una máquina virtual: cada for, cada +, cada yield tiene una contraparte concreta en una lista de instrucciones de pila. La planificación de procesos muestra que el SO toma decisiones algorítmicas a nuestro alrededor todo el tiempo, con los mismos trade-offs que estudiamos aquí: tiempo promedio versus latencia individual, eficiencia versus equidad, simplicidad versus óptimo teórico.

Este documento profundiza un tema mencionado al pasar en clases anteriores: las pilas y colas como ejemplos paradigmáticos de Tipos Abstractos de Datos (TAD). No forma parte del temario evaluable del curso, no se aborda en clases teóricas ni de laboratorio, y su lectura es enteramente opcional. Se ofrece a quienes quieran ampliar su comprensión de estructuras de datos más allá de los temas curriculares. La motivación y los conceptos están autocontenidos: no requiere material extra más allá de lo visto hasta la Semana 10.

Los problemas de esta semana introducen los patrones iterativos avanzados que aprovechan la estructura particular de cada problema (orden, contigüidad, monotonía, recurrencia) para reducir el costo asintótico de algoritmos cuya versión ingenua es O(n²). El eje temático es la actualización incremental: al avanzar un paso del bucle no se descarta lo computado, se ajusta en tiempo constante. Sobre esa base se introduce la noción de complejidad espacial auxiliar como segunda dimensión del análisis algorítmico, y los generadores como recurso para procesar colecciones más grandes que la memoria disponible.