Algoritmos recursivos avanzados e integración

Semana 12 — Divide y vencerás profundizado, backtracking, integración del recorrido del curso, análisis crítico de IA generativa y preparación del proyecto final

1. ¿Qué cierra esta semana?

Durante once semanas el curso fue construyendo un repertorio cada vez más rico de herramientas para pensar problemas computacionales. Empezamos con variables y secuencias (Semanas 1–3), pasamos a la modularización con funciones (Semana 4), nos hicimos preguntas sobre eficiencia con la introducción a la complejidad (Semana 5), aprendimos a ordenar y a manipular archivos de texto (Semana 6), entendimos qué pasa por debajo cuando un programa accede a memoria (Semana 7), trabajamos con archivos binarios y registros de tamaño fijo (Semana 8), descubrimos la recursividad como modo natural de razonar sobre problemas autosimilares (Semana 9), incorporamos estructuras de datos compuestas (Semana 10) y refinamos los patrones iterativos para hacerlos eficientes (Semana 11).

Esta semana cierra el ciclo de contenidos del curso con dos ideas algorítmicas que reúnen, de manera natural, casi todo lo aprendido: divide y vencerás y backtracking. La primera profundiza algoritmos que ya entrevimos —merge sort, quick sort— analizando con rigor por qué funcionan, cuál es su costo y bajo qué condiciones se cumple su comportamiento ideal. La segunda incorpora una técnica nueva: la exploración sistemática de un espacio de soluciones con poda, donde la recursión deja de ser una mera estructura de cálculo para convertirse en una herramienta de búsqueda exhaustiva. Ambas heredan, profundizan y combinan los conceptos previos.

Las dos preguntas centrales de la semana. ¿Qué hace que un problema sea naturalmente divisible, y cómo se traduce esa divisibilidad en un algoritmo eficiente? ¿Qué hace que un problema sea naturalmente combinatorio (donde hay que explorar muchas alternativas), y cómo se evita que la exploración resulte computacionalmente inviable? Las respuestas conectan recursividad, complejidad, estructuras de datos y casi todos los patrones del curso en un mismo marco.

1.1. Lo que se conecta hacia atrás

Esta clase se apoya en varios pilares construidos a lo largo del curso:

1.2. Lo que se prepara hacia adelante

El recorrido didáctico de esta semana cumple además una función específica: alistar al estudiante para el proyecto final integrador de las Semanas 13 a 16. Los temas se eligieron no sólo por su valor algorítmico intrínseco sino porque ofrecen, en combinación con todo lo anterior, un repertorio suficiente para encarar problemas de alcance realista. La introducción al proyecto que cierra la clase no es un anexo: es la consecuencia natural de haber completado el recorrido.

2. Divide y vencerás: el paradigma

El paradigma divide y vencerás (divide and conquer) ya apareció en el curso como motivación para merge sort. Esta semana lo formalizamos como una estrategia general de diseño de algoritmos, identificable y aplicable más allá del ordenamiento. La estructura es siempre la misma:

  1. Dividir el problema en subproblemas de la misma naturaleza, pero de menor tamaño.
  2. Vencer cada subproblema recursivamente, hasta llegar a un caso base trivial.
  3. Combinar las soluciones parciales en la solución del problema original.

La elegancia del paradigma reside en que cada paso es independiente del tamaño: el algoritmo se describe en términos genéricos, y la recursión se ocupa de aplicarlo a todas las escalas. Pero la elegancia tiene un costo conceptual: para analizar la complejidad temporal de un algoritmo divide y vencerás necesitamos pensar simultáneamente en dos magnitudes: cuántos subproblemas se generan por nivel, y cuánto trabajo no recursivo se hace en cada nivel.

2.1. La recurrencia maestra: intuición sin álgebra avanzada

Para los algoritmos divide y vencerás que estudiamos en este curso, el costo temporal se describe con una recurrencia de la forma:

T ( n ) = a · T ( n / b ) + f ( n ) T(n): costo total del problema de tamaño n f(n): trabajo NO recursivo por nivel (división + combinación) a: cantidad de subproblemas por nivel T(n/b): costo de cada subproblema b: factor de reducción del tamaño

Para merge sort, por ejemplo, a = 2 (dos mitades), b = 2 (cada mitad es n/2) y f(n) = O(n) (la fusión recorre n elementos). Para búsqueda binaria recursiva (Semana 9), a = 1 (un solo subproblema), b = 2, f(n) = O(1).

Sin entrar en el master theorem formal, hay una intuición geométrica que basta para reconocer los tres casos típicos:

Forma de la recurrencia Trabajo por nivel Complejidad total Ejemplo
T(n) = T(n/2) + O(1) constante en cada nivel O(log n) búsqueda binaria
T(n) = 2·T(n/2) + O(n) O(n) en cada nivel O(n log n) merge sort
T(n) = 2·T(n/2) + O(1) crece geométricamente hacia las hojas O(n) recorrido recursivo de árbol binario
La intuición geométrica. El árbol de recursión tiene logb(n) niveles de profundidad (porque cada nivel divide el tamaño por b). En cada nivel, el trabajo total se determina sumando f(n/bi) a lo largo de los nodos de ese nivel. Si f(n) es lineal y a = b, ese trabajo es el mismo en todos los niveles ⇒ multiplicar por log n niveles ⇒ O(n log n). Si f(n) es constante y a = 1, el trabajo total se vuelve constante por nivel ⇒ sólo log n ⇒ O(log n). La complejidad final depende, esencialmente, de quién gana: el costo por nivel o la cantidad de niveles.

2.2. ¿Cuándo es razonable elegir divide y vencerás?

No todos los problemas se benefician de un enfoque divide y vencerás. Hay tres condiciones que vale la pena verificar antes de comprometerse con el paradigma:

  1. Autosimilitud: el problema sobre una entrada de tamaño n debe poder formularse en términos del mismo problema sobre entradas menores. Esto excluye, por ejemplo, problemas donde una mitad de los datos depende fuertemente del orden o presencia de la otra.
  2. Combinación tratable: debe existir una manera eficiente de combinar las soluciones de los subproblemas. Si la combinación cuesta O(n²), el algoritmo entero degrada a O(n²), y dividir no aporta nada.
  3. Reducción significativa: los subproblemas deben ser estrictamente más pequeños. Si un subproblema es de tamaño n-1 (por ejemplo, recursión lineal), el paradigma no se aplica: estaríamos hablando de recursividad lineal, no de divide y vencerás.
Conexión con la Semana 9. La recursividad lineal (factorial, suma de elementos) y la recursividad logarítmica (potencia rápida, búsqueda binaria) son patrones de la misma familia conceptual. Divide y vencerás extiende la idea: en lugar de una llamada recursiva sobre una entrada menor, hay varias llamadas recursivas, cada una sobre una porción de la entrada. La pila de ejecución sigue siendo la misma estructura; lo que cambia es la forma del árbol de llamadas.

3. Merge sort profundizado

Merge sort apareció por primera vez en la Semana 6 como contraejemplo de los algoritmos cuadráticos: una manera de ordenar en O(n log n) basada en dividir y fusionar. En la Semana 9 lo mencionamos al hablar de recursividad. Esta semana lo escribimos por completo, lo trazamos paso a paso y lo comparamos empíricamente con sus alternativas.

3.1. Análisis (Pólya)

Problema. Dada una lista secuencia de elementos comparables, devolver una nueva lista con los mismos elementos en orden no decreciente.

Casos de análisis y de prueba:

3.2. Diseño (pseudocódigo)

algoritmo merge_sort(secuencia): si longitud(secuencia) ≤ 1: devolver secuencia # caso base: ya está ordenada medio ← longitud(secuencia) // 2 mitad_izq ← merge_sort(secuencia[0 .. medio-1]) mitad_der ← merge_sort(secuencia[medio .. fin]) devolver fusionar(mitad_izq, mitad_der) algoritmo fusionar(izq, der): resultado ← lista vacía i ← 0; j ← 0 mientras i < longitud(izq) Y j < longitud(der): si izq[i] ≤ der[j]: agregar izq[i] a resultado i ← i + 1 sino: agregar der[j] a resultado j ← j + 1 agregar los elementos restantes de izq a resultado agregar los elementos restantes de der a resultado devolver resultado

3.3. Codificación (Python)

def merge_sort(secuencia): """Ordena una secuencia comparándola por divide y vencerás. Precondición: secuencia es una lista de elementos comparables entre sí. Postcondición: devuelve una nueva lista con los mismos elementos en orden no decreciente; secuencia no se modifica. Complejidad: O(n log n) en tiempo, O(n) en espacio auxiliar. """ # --- Prólogo: caso base de la recursión ------------------------- if len(secuencia) <= 1: return list(secuencia) # copia defensiva # --- Resolución: dividir, recurrir, combinar -------------------- medio = len(secuencia) >> 1 # división por 2 a nivel ALU mitad_izq = merge_sort(secuencia[:medio]) mitad_der = merge_sort(secuencia[medio:]) resultado = _fusionar(mitad_izq, mitad_der) # --- Epílogo: devolver la solución del problema ----------------- return resultado def _fusionar(izq, der): """Fusiona dos listas ordenadas en una sola lista ordenada. Precondición: izq y der están ordenadas en forma no decreciente. Postcondición: devuelve una nueva lista con todos los elementos de izq y der, en orden no decreciente y estable. """ # --- Prólogo: estructuras de trabajo ---------------------------- resultado = [] i, j = 0, 0 n_izq, n_der = len(izq), len(der) # --- Resolución: avanzar ambos punteros tomando el menor -------- while i < n_izq and j < n_der: # mientras haya ambos if izq[i] <= der[j]: # ≤ preserva estabilidad resultado.append(izq[i]) i += 1 else: resultado.append(der[j]) j += 1 resultado.extend(izq[i:]) # cola de la izquierda resultado.extend(der[j:]) # cola de la derecha # --- Epílogo: devolver lista fusionada -------------------------- return resultado
Lectura literaria del código. El docstring declara contrato y complejidad. El prólogo separa el caso base; la resolución encapsula los tres pasos del paradigma (dividir, recurrir, combinar); el epílogo devuelve el resultado. La función auxiliar _fusionar es privada (por convención, prefijo subguión) y se documenta con la misma estructura. Notar el uso de >> 1 en lugar de // 2, que apareció por primera vez en la Semana 1 como conexión con la ALU. Notar también que while es la elección correcta porque la cantidad de iteraciones no se conoce de antemano: depende de qué puntero llegue antes a su límite.

3.4. Traza con una lista de 8 elementos

Para visualizar el árbol de llamadas, ordenemos [5, 2, 8, 1, 9, 3, 7, 4]. El esquema siguiente muestra el descenso (división) y el ascenso (fusión):

Merge Sort sobre [5, 2, 8, 1, 9, 3, 7, 4] — descenso y ascenso DIVIDIR ▼ ▲ FUSIONAR [5, 2, 8, 1, 9, 3, 7, 4] [5, 2, 8, 1] [9, 3, 7, 4] [5, 2] [8, 1] [9, 3] [7, 4] [5] [2] [8] [1] [9] [3] [7] [4] [2, 5] [1, 8] [3, 9] [4, 7] [1, 2, 5, 8] [3, 4, 7, 9] [1, 2, 3, 4, 5, 7, 8, 9] 3 niveles de profundidad (log₂ 8 = 3); 8 elementos fusionados por nivel ⟹ 3 × 8 = 24 comparaciones máx.

3.5. ¿Por qué O(n log n)?

La estructura del árbol de recursión hace evidente el costo total:

Total = O(n) × O(log n) = O(n log n)

Esta complejidad es la misma en el mejor, peor y caso promedio. Merge sort no se beneficia de listas ya ordenadas: siempre divide hasta el caso base y siempre fusiona. Es predecible —una virtud cuando se necesita garantizar un comportamiento de peor caso— pero también significa que no aprovecha estructura preexistente en los datos.

El trade-off espacial. Merge sort necesita memoria auxiliar O(n) para las listas fusionadas. En cada nivel, el total de memoria intermedia activa es proporcional a n, y la profundidad de la pila es log n. Es un costo significativo comparado con los algoritmos cuadráticos clásicos (selección, inserción, burbuja) que son in-place —O(1) memoria extra— aunque sean O(n²) en tiempo. La elección entre ambos es un trade-off explícito entre tiempo y espacio.

3.6. Estabilidad: por qué importa

Un algoritmo de ordenamiento es estable si, ante elementos con la misma clave, conserva su orden relativo original. Merge sort, tal como lo escribimos, es estable: la comparación izq[i] <= der[j] garantiza que cuando dos elementos son iguales, gana el de la mitad izquierda —que en la lista original aparecía antes.

La estabilidad importa cuando se ordena por una clave secundaria sin perder el orden de una clave primaria previa. Ejemplo: ordenar una lista de estudiantes primero por nota (descendente) y luego por apellido (ascendente). Si el segundo ordenamiento es estable, los empates de apellido respetan el orden por nota establecido en el paso anterior. Quick sort —que veremos enseguida— no es estable en su versión tradicional.

4. Quick sort con análisis del pivote

Quick sort comparte con merge sort la idea de dividir y vencer, pero invierte el reparto del trabajo. Donde merge sort divide trivialmente y fusiona costosamente, quick sort divide costosamente (particionando) y combina trivialmente (no necesita fusión: la concatenación «menores + pivote + mayores» ya está ordenada). El precio de esta inversión es que la calidad del algoritmo depende críticamente de una decisión: qué elemento se elige como pivote.

4.1. Codificación: quick sort no in-place

Para hacer evidente la estructura del algoritmo —sin mezclarla con los índices de la versión in-place— presentamos primero la variante que construye nuevas listas:

def quick_sort(secuencia): """Ordena una secuencia por el paradigma divide y vencerás. Estrategia: elegir un pivote, particionar en menores/iguales/mayores, ordenar recursivamente las particiones extremas, concatenar. Precondición: secuencia es una lista de elementos comparables. Postcondición: devuelve una nueva lista con los mismos elementos en orden no decreciente; secuencia no se modifica. Complejidad: O(n log n) en promedio, O(n²) en peor caso; O(log n) memoria de pila en promedio. """ # --- Prólogo: caso base de la recursión ------------------------- if len(secuencia) <= 1: return list(secuencia) # copia defensiva # --- Resolución: pivote, partición, recurrencia, combinación ---- pivote = secuencia[len(secuencia) >> 1] # pivote = mediana del índice menores = [x for x in secuencia if x < pivote] iguales = [x for x in secuencia if x == pivote] mayores = [x for x in secuencia if x > pivote] resultado = quick_sort(menores) + iguales + quick_sort(mayores) # --- Epílogo: devolver la solución del problema ----------------- return resultado
Decisión de diseño: el pivote. Elegimos el elemento de la posición media (len(secuencia) >> 1) en vez del primero o del último. La elección de cuál usar como pivote es el corazón del análisis de quick sort y la razón por la cual hay tantas variantes en la literatura: pivote aleatorio, mediana de tres, mediana de medianas, etc. Con la elección «elemento del medio» evitamos el peor caso clásico de listas ya ordenadas (donde elegir el primero o el último genera particiones desbalanceadas), pero seguimos siendo vulnerables a entradas adversariales construidas a propósito.

4.2. Traza con buen pivote

Ordenemos [5, 2, 8, 1, 9, 3, 7, 4] —la misma lista que usamos con merge sort— eligiendo el elemento del medio como pivote en cada llamada:

Quick Sort (pivote = elemento del medio) sobre [5, 2, 8, 1, 9, 3, 7, 4] menores que el pivote pivote (e iguales) mayores que el pivote vacío / singleton Entrada: [5, 2, 8, 1, 9, 3, 7, 4] [5, 2, 8, 1, 3, 7, 4] [9] [ ] pivote = 9 [ ] [1] [5, 2, 8, 3, 7, 4] pivote = 1 [2] [3] [5, 8, 7, 4] pivote = 3 [5, 4] [7] [8] pivote = 7 [ ] [4] [5] pivote = 4 Cómo leer el diagrama Cada fila es una partición: la lista se separa en menores, pivote y mayores. Sólo las sublistas compuestas (más de un elemento) se vuelven a particionar: de ellas parten las tres flechas hacia la fila siguiente. Las sublistas vacías y los singletons son caso base y no generan recursión. La concatenación final, recorriendo de izquierda a derecha: [1, 2, 3, 4, 5, 7, 8, 9].

Cada nivel particiona aproximadamente a la mitad. La estructura no es perfectamente balanceada como en merge sort (porque el pivote rara vez es la mediana exacta), pero se mantiene «cerca» del balance, y la profundidad global crece como log2(n). El trabajo por nivel es O(n) —recorrer los elementos para comparar con el pivote—, y por lo tanto el costo total es O(n log n) en el caso promedio.

4.3. El peor caso: pivote sistemáticamente malo

El peor caso de quick sort se produce cuando el pivote elegido divide el problema de la manera más desbalanceada posible: un lado vacío y el otro con n-1 elementos. En esa situación la recursión profundiza n veces en lugar de log n, y el trabajo total se vuelve O(n²).

¿Cuándo ocurre? Depende de la regla de elección del pivote:

Regla de pivote Peor caso (O(n²)) ocurre con... Caso promedio
Primer elemento Lista ya ordenada o inversamente ordenada O(n log n)
Último elemento Lista ya ordenada o inversamente ordenada O(n log n)
Elemento del medio (índice) Patrones específicos donde el medio es siempre el extremo O(n log n)
Elemento aleatorio Entradas adversariales (improbable en práctica) O(n log n) con alta probabilidad
Mediana de tres Entradas construidas para ese esquema (raro) O(n log n) muy robusto
Por qué el «primer elemento» es mala idea en aplicaciones reales. Muchas entradas del mundo real ya están parcial o totalmente ordenadas: logs cronológicos, archivos exportados de bases de datos, listas de identificadores. Una implementación de quick sort que use el primer elemento como pivote, sobre datos así, degrada a O(n²) y puede tardar horas en ordenar lo que merge sort ordena en segundos. La elección del pivote no es una decisión menor.

4.4. Comparación analítica: merge sort vs. quick sort

Aspecto Merge sort Quick sort
Mejor caso O(n log n) O(n log n)
Caso promedio O(n log n) O(n log n)
Peor caso O(n log n) (garantía) O(n²)
Espacio auxiliar O(n) O(log n) en promedio (pila)
Estable Sí No (en su versión tradicional)
Trabajo principal Fusionar (combinar) Particionar (dividir)
Sensible al orden inicial No Sí (vía elección de pivote)
Adecuado para... Garantía de peor caso, estabilidad, datos enlazados Promedio rápido, in-place, contigüidad en memoria
El criterio real de elección. En la práctica industrial, ninguno de los dos algoritmos «puros» se usa tal cual. Las bibliotecas estándar suelen implementar híbridos: Timsort (Python, Java) combina merge sort con inserción para aprovechar segmentos ya ordenados; introsort (C++ STL) usa quick sort hasta que detecta profundidad excesiva, momento en el que cambia a heap sort para garantizar O(n log n) de peor caso. Lo que estudiamos en el curso no son productos finales sino los componentes conceptuales a partir de los cuales esos productos se construyen.

5. Comparación empírica: medir, no sólo razonar

El análisis teórico de complejidad anticipa cómo escala un algoritmo cuando n crece, pero no nos dice cuál es más rápido para los datos que efectivamente vamos a procesar. Para n pequeño, las constantes ocultas en la notación O dominan: un algoritmo O(n²) bien implementado puede ser más rápido que un algoritmo O(n log n) con mucha sobrecarga. La única forma de saberlo es medir.

Retomamos las herramientas de la Semana 11 (time.perf_counter, timeit) para diseñar una comparación empírica entre tres algoritmos: nuestra implementación de merge sort, nuestra implementación de quick sort, y la función nativa sorted() (que implementa Timsort).

5.1. Diseño experimental

Un experimento serio requiere fijar las variables que se controlan y las que se varían. En este caso:

5.2. Código del experimento

import random import time def medir_tiempo(funcion, datos, repeticiones=3): """Mide el menor tiempo de ejecución de funcion(datos). Precondición: funcion acepta una lista y devuelve una lista ordenada; datos es una lista de elementos comparables; repeticiones es un entero positivo. Postcondición: devuelve el menor tiempo (en segundos) entre las repeticiones realizadas. """ # --- Prólogo: lista para acumular mediciones -------------------- tiempos = [] # --- Resolución: ejecutar y medir varias veces ------------------ for _ in range(repeticiones): # cantidad conocida ⟹ for copia = list(datos) # sorted() es no-destructivo; # merge/quick devuelven nueva inicio = time.perf_counter() funcion(copia) tiempos.append(time.perf_counter() - inicio) # --- Epílogo: devolver el mejor (menos ruidoso) ----------------- return min(tiempos) def comparar_ordenamientos(tamanios, patron="aleatorio"): """Compara merge_sort, quick_sort y sorted() en varios tamaños. Precondición: tamanios es una lista de enteros positivos; patron ∈ {'aleatorio', 'ordenado', 'inverso'}. Postcondición: imprime una tabla con tiempos por tamaño y algoritmo. """ # --- Prólogo: semilla fija y encabezado de tabla ---------------- random.seed(42) # reproducibilidad print(f"Patrón de datos: {patron}") print(f"{'n':>8} {'merge':>10} {'quick':>10} {'sorted':>10}") # --- Resolución: por cada tamaño, generar y medir --------------- for n in tamanios: # lista finita conocida ⟹ for if patron == "aleatorio": datos = [random.randint(0, n) for _ in range(n)] elif patron == "ordenado": datos = list(range(n)) else: # inverso datos = list(range(n, 0, -1)) t_merge = medir_tiempo(merge_sort, datos) t_quick = medir_tiempo(quick_sort, datos) t_sorted = medir_tiempo(sorted, datos) print(f"{n:>8} {t_merge:>10.4f} {t_quick:>10.4f} {t_sorted:>10.4f}") # --- Epílogo: separador final ----------------------------------- print()

5.3. Resultados típicos esperados

Una corrida representativa sobre una máquina actual (los valores absolutos dependen del hardware, pero las relaciones son estables) muestra el siguiente patrón:

nmerge (aleatorio)quick (aleatorio)sorted (aleatorio)merge (ordenado)quick (ordenado)
1 0000,00210,00140,00010,00190,0011
10 0000,02700,01900,00140,02500,0150
100 0000,35000,27000,01900,32000,2100
Lectura de los resultados. Tres observaciones consistentes en cualquier corrida: (1) sorted() es entre 10× y 20× más rápido que las implementaciones propias, no por ser un algoritmo distinto (Timsort también es O(n log n)) sino por estar implementado en C dentro del intérprete —la sobrecarga de las llamadas a función en Python es lo que paga merge sort y quick sort. (2) El cociente de tiempos entre n y 10·n no es 10 sino aproximadamente 13–15, lo cual es consistente con O(n log n): 10·n·log(10·n) / (n·log(n)) ≈ 10·(1 + log(10)/log(n)). (3) Quick sort es ligeramente más rápido que merge sort en promedio, en parte porque no necesita copiar tanta memoria intermedia. La elección del pivote como elemento del medio mantiene el promedio O(n log n) incluso con datos ordenados.

5.4. La trampa de comparar O notation con relojes

Es tentador concluir, a partir de la tabla, que «sorted() es mejor». Esa conclusión es correcta pragmáticamente pero conceptualmente engañosa: sorted() no es asintóticamente mejor que merge_sort o quick_sort —los tres son O(n log n)—; es constantemente mejor por implementación. Si por alguna razón tuviéramos que escribir un algoritmo desde cero (por ejemplo, en un entorno embebido sin biblioteca estándar, o con un criterio de comparación no soportado), la pregunta interesante deja de ser «¿quién gana frente a sorted()?» y se convierte en «¿qué algoritmo es robusto frente a entradas no aleatorias?», «¿qué algoritmo es estable?», «¿cuánta memoria auxiliar tengo disponible?».

El razonamiento asintótico nos dice cómo escala el algoritmo; la medición empírica nos dice cuánto cuesta efectivamente. Ambas perspectivas son necesarias: la primera para diseñar, la segunda para validar y decidir.

6. Backtracking: explorar con vuelta atrás

Hasta aquí, los algoritmos recursivos que vimos resolvían problemas donde el camino hacia la solución estaba determinado: factorial, suma de elementos, búsqueda binaria, merge sort. La recursión era una manera elegante de expresar un cálculo que, en principio, también podía hacerse iterativamente. Backtracking introduce una clase distinta de problemas: aquellos donde no sabemos de antemano cuál es la solución, y debemos buscarla explorando alternativas.

La idea central. Construir la solución paso a paso tomando decisiones tentativas. En cada paso, si la decisión actual conduce a una situación viable, profundizamos; si conduce a un callejón sin salida, volvemos atrás (de ahí el nombre: back-tracking), deshacemos la última decisión y probamos una alternativa. Continuamos hasta encontrar una solución completa, o hasta agotar el espacio de búsqueda.

6.1. La estructura general

Todo algoritmo de backtracking tiene la misma estructura esquelética, independientemente del problema concreto:

algoritmo backtrack(estado_parcial): si estado_parcial es solución completa: registrar la solución devolver para cada decisión posible desde estado_parcial: si la decisión es válida (poda): aplicar la decisión # ampliar el estado parcial backtrack(nuevo_estado_parcial) deshacer la decisión # restaurar el estado anterior

Los componentes esenciales son cuatro:

  1. Estado parcial: una representación de la solución en construcción. Puede ser una lista, un conjunto, una matriz, una tupla —la elección de la estructura es una decisión de diseño no trivial.
  2. Decisiones disponibles: el conjunto de elecciones posibles desde el estado actual.
  3. Criterio de validez (poda): una verificación rápida que descarta decisiones que necesariamente conducirán a estados sin solución. Esta es la clave de la eficiencia del backtracking.
  4. Criterio de éxito: cómo reconocer que el estado actual es una solución completa.

6.2. La poda: lo que distingue backtracking de fuerza bruta

Si quitáramos la verificación de validez, el algoritmo enumeraría todas las combinaciones posibles —sería fuerza bruta. Con poda, el algoritmo descarta ramas enteras del árbol de búsqueda apenas detecta que no contienen solución. Para muchos problemas combinatorios, la poda transforma un costo exponencial inviable en uno tratable en la práctica.

El árbol de búsqueda. Cada nodo del árbol representa un estado parcial. Cada arista representa una decisión tomada. Los nodos hoja representan estados que son: soluciones completas (registrados), estados inválidos (podados antes de profundizar), o callejones (sin decisiones disponibles). El algoritmo recorre el árbol en profundidad (DFS), con el respaldo automático de la pila de ejecución que estudiamos en la Semana 9.
Backtracking: árbol de búsqueda con poda ∅ A B PODADO C AB AC AD CA CB CD CBA CBD solución parcial válida rama podada solución completa subárbol no mostrado (similar)

6.3. Aplicación 1: generación de permutaciones

Problema. Dada una lista elementos, generar todas las permutaciones posibles (todas las maneras de ordenar sus elementos).

Análisis. Una permutación es una elección secuencial: primero elegir cuál de los n elementos va en la primera posición, luego cuál de los n-1 restantes va en la segunda, y así sucesivamente. La estructura natural es un árbol de profundidad n con factor de ramificación decreciente: n × (n-1) × (n-2) × ... × 1 = n! soluciones completas. Para n=4 son 24; para n=10 son 3,6 millones; para n=15 son más de un billón. El crecimiento factorial nos recuerda que enumerar todas las permutaciones sólo es viable para n pequeño.

Estado parcial: una lista permutacion con los elementos ya elegidos, en orden.
Decisiones disponibles: los elementos de la lista original que aún no fueron usados.
Poda: no hay poda «inteligente» en este problema —todas las elecciones son válidas—, pero la verificación «¿este elemento ya está en la permutación?» evita repeticiones.
Criterio de éxito: longitud(permutacion) = longitud(elementos).

Codificación

Optamos por la versión con parámetros explícitos en la función recursiva, en lugar de la versión con función interna y captura por closure. Es ligeramente más larga pero hace visible qué se pasa en cada llamada, qué se modifica y qué no: el estudiante ve el flujo de datos sin tener que razonar simultáneamente sobre el alcance LEGB.

def permutaciones(elementos): """Genera todas las permutaciones de los elementos dados. Precondición: elementos es una lista; sus elementos son distinguibles. Postcondición: devuelve una lista con todas las permutaciones, cada una representada como una lista del mismo largo que la entrada. Total: len(elementos)! permutaciones. Complejidad: O(n · n!) tiempo, O(n · n!) espacio para el resultado. """ # --- Prólogo: estructuras iniciales para el backtracking -------- soluciones = [] permutacion = [] usados = [False] * len(elementos) # --- Resolución: delegar la exploración al algoritmo recursivo -- _explorar_permutacion(elementos, permutacion, usados, soluciones) # --- Epílogo: devolver todas las soluciones encontradas --------- return soluciones def _explorar_permutacion(elementos, permutacion, usados, soluciones): """Explora recursivamente el árbol de permutaciones. Precondición: elementos es la lista original; permutacion es el estado parcial; usados es una lista paralela a elementos que indica cuáles ya están en permutacion; soluciones acumula las permutaciones completas encontradas. Postcondición: al terminar, soluciones contiene todas las permutaciones completas alcanzables desde el estado parcial dado. """ # --- Caso base: la permutación está completa -------------------- if len(permutacion) == len(elementos): soluciones.append(list(permutacion)) # copia: NO la referencia return # --- Caso recursivo: probar cada elemento no usado -------------- for i in range(len(elementos)): # cantidad conocida ⟹ for if not usados[i]: # poda: ya está incluido permutacion.append(elementos[i]) # aplicar decisión usados[i] = True _explorar_permutacion(elementos, permutacion, usados, soluciones) permutacion.pop() # deshacer usados[i] = False # back-track
Tres detalles importantes. (1) Cuando registramos una solución hacemos list(permutacion) —una copia—, porque permutacion es una lista que sigue siendo modificada durante toda la exploración (aliasing, Semana 7). Si guardáramos la referencia directa, todas las «soluciones» terminarían siendo la misma lista vacía al final. (2) Tanto permutacion como usados y soluciones se pasan por referencia (Semana 7): la función recursiva no recibe copias, sino acceso a las listas originales que se van modificando con cada decisión. (3) El par append/pop y True/False implementa la simetría apilar/desapilar, hacer/deshacer que define al backtracking.

Árbol de búsqueda para permutaciones([1, 2, 3])

Antes de ver la traza paso a paso, conviene visualizar la forma del espacio de búsqueda. El siguiente árbol muestra todos los estados parciales que la función puede alcanzar al permutar [1, 2, 3]. La raíz es la permutación vacía; cada nivel de profundidad agrega un elemento; las hojas (en verde) son las 3! = 6 permutaciones completas.

Árbol de búsqueda de permutaciones([1, 2, 3]) Nivel 0: permutación vacía Nivel 1: elegir 1° Nivel 2: elegir 2° Nivel 3: elegir 3° SOLUCIONES [ ] [1] [2] [3] [1,2] [1,3] [2,1] [2,3] [3,1] [3,2] [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]

Observaciones importantes sobre la forma del árbol: el factor de ramificación decrece con la profundidad —3 hijos en el nivel 1, 2 hijos en el nivel 2, 1 hijo (forzado) en el nivel 3—, lo cual refleja el espacio de decisiones restantes. La cantidad total de hojas es 3 × 2 × 1 = 3! = 6. La función recursiva recorre este árbol en profundidad (DFS), explorando completamente el subárbol izquierdo antes de pasar al siguiente.

Traza paso a paso

El siguiente paso es ver, fila por fila, qué hace la función. La tabla muestra el estado de permutacion y usados después de cada acción significativa: aplicar una decisión, registrar una solución o hacer back-track. El recorrido sigue el árbol anterior en orden de izquierda a derecha y de arriba hacia abajo.

PasoAcciónpermutaciónusadossoluciones
0inicio[ ][F, F, F][ ]
1aplicar 1[1][T, F, F][ ]
2aplicar 2[1, 2][T, T, F][ ]
3aplicar 3[1, 2, 3][T, T, T][ ]
4registrar solución[1, 2, 3][T, T, T][[1,2,3]]
5back-track (pop 3)[1, 2][T, T, F][[1,2,3]]
6back-track (pop 2)[1][T, F, F][[1,2,3]]
7aplicar 3[1, 3][T, F, T][[1,2,3]]
8aplicar 2[1, 3, 2][T, T, T][[1,2,3]]
9registrar solución[1, 3, 2][T, T, T][[1,2,3], [1,3,2]]
10back-track (pop 2)[1, 3][T, F, T]...
11back-track (pop 3)[1][T, F, F]...
12back-track (pop 1)[ ][F, F, F]...
13aplicar 2 (segunda rama de la raíz)[2][F, T, F]...
...(continúa explorando subárboles de [2] y [3]).........
finalfin de exploración[ ][F, F, F][[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Lectura de la traza. Tres observaciones que conectan código y árbol: (1) Después de cada solución registrada hay una cascada de back-tracks consecutivos: la recursión se desenrolla varios niveles hasta encontrar una decisión alternativa pendiente. En la traza, los pasos 5–6 son la cascada que sigue al paso 4. (2) El estado usados = [F, F, F] aparece en el paso 0 y en el paso 12 (después de back-trackear el primer subárbol completo). Al final de la ejecución, todas las variables auxiliares vuelven a su estado inicial: el algoritmo es «no destructivo» respecto a su propio estado. (3) Las 6 hojas del árbol se visitan en el orden lexicográfico [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] —orden que coincide con el recorrido DFS de izquierda a derecha.

6.4. Aplicación 2: subconjuntos

Generar todos los subconjuntos de un conjunto de n elementos es un problema clásico que se presta naturalmente al backtracking. La idea es recorrer los elementos y, en cada paso, tomar una decisión binaria: incluir o no incluir el elemento en el subconjunto en construcción.

Codificación

def subconjuntos(elementos): """Genera todos los subconjuntos de una lista de elementos. Precondición: elementos es una lista con elementos distinguibles. Postcondición: devuelve una lista con 2^n sublistas, una por cada subconjunto posible (incluyendo el vacío y el total). Complejidad: O(n · 2^n) tiempo y espacio. """ # --- Prólogo: estructuras iniciales para el backtracking -------- soluciones = [] subconjunto = [] # --- Resolución: delegar la exploración al algoritmo recursivo -- _explorar_subconjunto(elementos, 0, subconjunto, soluciones) # --- Epílogo: devolver todos los subconjuntos ------------------- return soluciones def _explorar_subconjunto(elementos, indice, subconjunto, soluciones): """Explora recursivamente el árbol binario de decisiones. Precondición: elementos es la lista original; indice es la posición del elemento a considerar a continuación; subconjunto es el estado parcial actual; soluciones acumula los subconjuntos completos encontrados. Postcondición: al terminar, soluciones contiene todos los subconjuntos que extienden al subconjunto parcial dado. """ # --- Caso base: ya consideramos todos los elementos ------------- if indice == len(elementos): soluciones.append(list(subconjunto)) # copia: NO la referencia return # --- Caso recursivo: dos decisiones para el elemento actual ----- # Decisión 1: NO incluir elementos[indice] _explorar_subconjunto(elementos, indice + 1, subconjunto, soluciones) # Decisión 2: SÍ incluir elementos[indice] subconjunto.append(elementos[indice]) # aplicar decisión _explorar_subconjunto(elementos, indice + 1, subconjunto, soluciones) subconjunto.pop() # back-track

El estado parcial no requiere una lista paralela usados como en permutaciones, porque cada elemento se considera exactamente una vez al recorrer los índices en orden. La «decisión» en este problema es binaria (incluir / no incluir), no la elección de un índice entre varios.

Árbol binario para subconjuntos(['A', 'B', 'C'])

El espacio de búsqueda forma un árbol binario perfecto de profundidad n: en cada nivel se toma una decisión sí/no por un elemento, y hay exactamente 2 hijos por nodo. Las 2n = 8 hojas corresponden a los 8 subconjuntos posibles. La rama izquierda de cada nodo es siempre la decisión «no incluir» (la primera que toma el código); la rama derecha es «sí incluir».

Árbol binario de subconjuntos(['A', 'B', 'C']) Nivel 0: subconjunto vacío Nivel 1: decidir sobre A Nivel 2: decidir sobre B Nivel 3: decidir sobre C SOLUCIONES: 2³ = 8 izq: no incluir der: sí incluir [ ] [ ] [A] no A sí A [ ] [B] [A] [A,B] [ ] [C] [B] [B,C] [A] [A,C] [A,B] [A,B,C]
Lectura del árbol. Tres propiedades clave: (1) El árbol tiene exactamente profundidad n = 3 y la cantidad de hojas es 2n = 8 —una por cada subconjunto posible del conjunto original. (2) El recorrido DFS explorando primero «no incluir» genera el orden característico de salida: [], [C], [B], [B,C], [A], [A,C], [A,B], [A,B,C]. (3) Es interesante notar el paralelo con la representación binaria de los enteros 0 a 7: cada subconjunto corresponde a un patrón de bits indicando qué elementos están presentes (000 = vacío, 001 = sólo C, 010 = sólo B, ..., 111 = todos). El backtracking sobre el árbol binario es, esencialmente, una enumeración estructurada de esos patrones.

6.5. Aplicación 3: laberinto simple

Problema. Dado un laberinto representado como una matriz de 0 (libre) y 1 (pared), una celda de inicio y una celda destino, encontrar un camino del inicio al destino moviéndose por celdas libres y respetando los movimientos cardinales (arriba, abajo, izquierda, derecha).

El laberinto de ejemplo

Vamos a trabajar concretamente con un laberinto chico, de 5 filas por 5 columnas, donde el inicio está en la esquina superior-izquierda y el destino en la esquina inferior-derecha:

Laberinto 5×5: inicio (0,0), destino (4,4) INI 0,1 0,3 0,4 1,0 1,1 1,3 2,0 2,1 2,2 2,3 2,4 3,4 4,0 4,1 4,2 4,3 DST Representación: laberinto = [ [0, 0, 1, 0, 0], [0, 0, 1, 0, 1], [0, 0, 0, 0, 0], [1, 1, 1, 1, 0], [0, 0, 0, 0, 0] ] inicio = (0, 0) destino = (4, 4) inicio destino celda libre (0) pared (1)

Análisis. Es un problema de búsqueda en un grafo implícito: cada celda libre es un nodo, cada par de celdas libres adyacentes es una arista. Backtracking sobre este grafo es una búsqueda en profundidad con marcado para evitar ciclos.

Estado parcial: la celda actual y el conjunto de celdas ya visitadas.
Decisiones disponibles: moverse a una celda adyacente libre y no visitada.
Poda: no salirse del laberinto, no atravesar paredes, no revisitar.
Criterio de éxito: llegar a la celda destino.

Codificación

def resolver_laberinto(laberinto, inicio, destino): """Busca un camino de 'inicio' a 'destino' en un laberinto. Precondición: laberinto es una lista de listas de 0 (libre) y 1 (pared); inicio y destino son tuplas (fila, columna) válidas sobre celdas libres del laberinto. Postcondición: devuelve una lista de celdas (camino) si existe; None en caso contrario. El camino, si existe, no se garantiza que sea el más corto: es el primer camino que la búsqueda en profundidad encuentre. """ # --- Prólogo: estructuras iniciales para el backtracking -------- camino = [] visitadas = set() # --- Resolución: delegar la exploración al algoritmo recursivo -- encontrado = _explorar_laberinto(laberinto, inicio, destino, camino, visitadas) # --- Epílogo: devolver el camino o None ------------------------- return camino if encontrado else None def _explorar_laberinto(laberinto, celda, destino, camino, visitadas): """Explora recursivamente el laberinto en profundidad desde 'celda'. Precondición: laberinto y destino son los del problema; celda es la posición actual; camino acumula las celdas del trayecto; visitadas marca las celdas ya consideradas. Postcondición: devuelve True si se encontró un camino al destino (entonces camino contiene ese camino); False en caso contrario (entonces camino queda igual que al entrar). """ # --- Caso base de éxito: llegamos al destino -------------------- if celda == destino: camino.append(celda) return True # --- Aplicar decisión: marcar visitada y agregar al camino ------ visitadas.add(celda) camino.append(celda) fila, col = celda filas, columnas = len(laberinto), len(laberinto[0]) movimientos = [(-1, 0), (1, 0), (0, -1), (0, 1)] # N S O E # --- Probar cada movimiento cardinal ---------------------------- for df, dc in movimientos: # 4 movimientos ⟹ for siguiente = (fila + df, col + dc) sf, sc = siguiente # Poda: dentro del laberinto, libre, no visitada if (0 <= sf < filas and 0 <= sc < columnas and laberinto[sf][sc] == 0 and siguiente not in visitadas): if _explorar_laberinto(laberinto, siguiente, destino, camino, visitadas): return True # profundizó y encontró # --- Back-track: ningún movimiento llevó a la solución ---------- camino.pop() return False
Decisión de diseño: ¿lista o conjunto para 'visitadas'? Usamos set en lugar de list porque las pruebas de pertenencia (siguiente not in visitadas) en un conjunto son O(1) promedio, mientras que en una lista son O(n). En un laberinto chico la diferencia es irrelevante; en uno grande con muchos callejones, la elección de estructura define si el algoritmo termina en milisegundos o en minutos. La idea de elegir la estructura adecuada para cada operación es el TAD revisitado de la Semana 10.

Traza visual: el camino que encuentra la búsqueda

El algoritmo prueba los movimientos siempre en el mismo orden —Norte, Sur, Oeste, Este—, lo cual hace su comportamiento predecible. Empezando en (0,0), el primer movimiento intentado es N pero está fuera del laberinto; entonces prueba S y avanza a (1,0). Desde allí continúa explorando hacia abajo y a la derecha. El siguiente esquema muestra el camino encontrado, las celdas exploradas que terminaron descartadas por back-track, y el orden de visita.

Camino encontrado y celdas back-trackeadas INI 1° 2° 3° 4° 5° 6° 7° 8° DST 9° Camino encontrado: [(0,0), (1,0), (2,0), (2,1), (2,2), (2,3), (2,4), (3,4), (4,4)] Longitud: 9 celdas Orden de movimientos: S, S, E, E, E, E, S, S Este es el primer camino que la búsqueda en profundidad encuentra, no necesariamente el más corto.
Por qué este camino y no otro. El algoritmo prueba siempre los movimientos en el orden N, S, O, E. Por eso, en cada celda, intenta primero subir (a menudo fuera del laberinto o ya visitado), luego bajar —y por eso el camino avanza primero hacia abajo. En (2,0), después de bajar dos veces, intenta nuevamente N (ya visitada), después S (es pared, en (3,0)), después O (fuera del laberinto), y finalmente E hacia (2,1). De ahí sigue avanzando hacia la derecha hasta (2,4), donde puede bajar por (3,4) hasta el destino. Cambiar el orden de los movimientos cambia el camino encontrado. Esta es una diferencia importante con respecto a algoritmos que buscan caminos óptimos (BFS, Dijkstra, A*): el backtracking en profundidad devuelve algún camino, no necesariamente el mejor.

6.6. Complejidad del backtracking

El backtracking no tiene una complejidad única —depende de la estructura del problema. Una cota superior pesimista es el tamaño del espacio de búsqueda completo: 2n para subconjuntos, n! para permutaciones, exponencial en el peor caso para problemas tipo laberinto. La poda es lo que distingue, en cada problema concreto, un backtracking viable de una explosión combinatoria.

El abismo combinatorio. Para n = 20, una enumeración de permutaciones generaría 2,4 × 1018 soluciones. Aun a 109 operaciones por segundo, eso son más de 70 años de cómputo. Para n = 25, son varios millones de años. El crecimiento factorial es el ejemplo paradigmático de por qué algunos problemas «sencillos de plantear» son intratables sin poda inteligente. La famosa pregunta abierta P vs NP de la teoría de la computación tiene exactamente esta forma en su esencia.
Conexión con la Semana 9. Cada llamada recursiva crea un frame en la pila de ejecución. La profundidad de la pila durante el backtracking es a lo sumo la profundidad del árbol de búsqueda —n para permutaciones, n para subconjuntos, hasta filas×columnas para un laberinto. La memoria O(n) de la pila no debe confundirse con el espacio O(2n) del resultado: la primera es el costo de explorar, el segundo es el costo de almacenar las soluciones encontradas.

7. Integración: una mirada al curso completo

Una de las funciones específicas de la Semana 12 es ofrecer una vista de conjunto antes del proyecto final. No se trata de repetir lo dado, sino de articularlo: mostrar cómo los conceptos se sostienen unos a otros, cómo se eligen unos u otros según el problema y cómo, juntos, conforman un repertorio que basta para encarar problemas de complejidad realista.

7.1. Mapa conceptual del recorrido

El curso tuvo cuatro grandes dominios que se desarrollaron en paralelo. Sigue un mapa para visualizar sus interconexiones:

Mapa conceptual del curso: cuatro dominios interconectados Algoritmos y resolución de problemas • Metodología Pólya (S1) • Patrones algorítmicos básicos (S3) • Modularización: funciones (S4) • Búsqueda y complejidad (S5) • Ordenamiento (S6) • Recursividad (S9) • Iterativos avanzados (S11) • D&V y backtracking (S12) Estructuras y representación de datos • Tipos primitivos (S1, S2) • Secuencias y cadenas (S3) • Archivos de texto (S6) • Archivos binarios y registros (S8) • Listas, tuplas, dicts, sets (S10) • Tipos abstractos de datos (S10) • Material complementario: pilas y colas Arquitectura, SO y memoria • Von Neumann (S1) • Lenguajes de máquina (S2) • Funciones del SO (S3) • Compiladores e intérpretes (S6) • Modelo de memoria (S7) • Pila, heap, GC (S9) • Bytecode y scheduling (S11) • Concurrencia, virtualización (S12) Práctica y ética del software • Pseudocódigo y diseño (S1) • Casos de análisis (S1+) • Docstrings, pre/postconds (S4) • Medición empírica (S5, S11) • Modularización y reuso (S4+) • Foros: IA generativa (S1, S12) • Reflexión metacognitiva (S6, S12) • Proyecto integrador (S13–S16) los algoritmos operan sobre las estructuras consumen recursos se almacenan en memoria contexto físico de la calidad del código Proyecto final: integra los cuatro dominios

7.2. Decisiones que recorren todo el curso

A lo largo de doce semanas, ciertas decisiones de diseño se repitieron una y otra vez. Saber identificarlas y poder argumentar a favor o en contra es uno de los aprendizajes centrales del curso, y será evaluado en el proyecto final.

Decisión Alternativas Criterios de elección
Estructura para una secuencia list vs. tuple vs. iterador ¿Mutable? ¿De tamaño fijo conocido? ¿Cabe en memoria?
Estructura para una asociación clave→valor dict vs. lista de tuplas ¿Búsqueda por clave frecuente? ¿Orden importa?
Estructura para colección sin duplicados set vs. list con verificación ¿Pertenencia frecuente? ¿Tamaño grande?
Bucle for vs. while ¿Cantidad de iteraciones conocida de antemano?
Algoritmo de ordenamiento Cuadrático vs. O(n log n) vs. sorted() ¿Tamaño? ¿Estabilidad? ¿Garantía de peor caso?
Algoritmo de búsqueda Lineal vs. binaria vs. heurística ¿Ordenado? ¿Cuántas búsquedas? ¿Distribución?
Estilo de resolución Iterativo vs. recursivo ¿Problema autosimilar? ¿Profundidad acotada?
Manejo de archivos Texto vs. binario; lectura completa vs. línea por línea ¿Tamaño respecto a la RAM? ¿Formato esperado?
Modularización Una función grande vs. varias chicas ¿Cada parte tiene un propósito claro? ¿Es reutilizable?
Documentación Comentarios vs. docstrings vs. ambos ¿Quién va a leer el código? ¿Es interfaz pública?
El criterio común. Detrás de cada una de estas decisiones hay una pregunta única: ¿qué hace el problema natural y qué hace mi solución elegante?. La elegancia algorítmica no es estética: es la propiedad de que el código exprese fielmente la estructura del problema. Cuando la estructura elegida calza con la del problema, el código se vuelve más corto, más legible y, casi siempre, más eficiente. El criterio profesional para tomar estas decisiones se construye con experiencia —y el proyecto final es la primera oportunidad real para ejercitarlo.

8. Análisis crítico del uso de IA generativa

El curso comenzó, en la Semana 1, con un foro abierto sobre el rol de la IA generativa en el aprendizaje de la programación. Cerramos el ciclo con una segunda mirada sobre el tema, ahora con la experiencia y el repertorio técnico acumulados durante doce semanas. La pregunta ya no es «¿qué pueden hacer estas herramientas?» sino «¿cómo conviene usarlas y bajo qué condiciones?».

Esta sección no busca prescribir un uso correcto único. Busca instalar un marco de análisis que permita a cada estudiante tomar decisiones informadas, individuales y responsables, tanto durante el proyecto final como en su trayectoria profesional posterior.

8.1. Lo que cambió en doce semanas

En la Semana 1, sin todavía haber escrito un programa, los estudiantes podían reflexionar sobre la IA generativa sólo desde la imaginación o el comentario externo. Esta semana, en cambio, contamos con experiencia directa: cada uno ha escrito (probablemente) decenas o cientos de líneas de código, ha cometido errores diagnosticables, ha entendido por qué un algoritmo funciona y por qué otro no escala. Esa experiencia transforma profundamente la calidad de la reflexión.

El cambio fundamental. En la Semana 1, una respuesta de una IA generativa a una consigna de programación podía parecer «mágica»: aparece código, parece funcionar, el ejercicio queda hecho. En la Semana 12, esa misma respuesta es interpretable: podemos leer el código, identificar el algoritmo subyacente, evaluar su complejidad, detectar bugs sutiles, proponer mejoras. La diferencia es la capacidad de ejercer juicio técnico —y ese juicio sólo se construye con práctica humana.

8.2. Marco conceptual: cuatro modos de uso

Para analizar el uso de IA generativa en programación, distinguimos cuatro modos de interacción, ordenados por nivel de delegación cognitiva:

Modo Qué hace la IA Qué hace el estudiante Riesgo formativo
1. Consulta de referencia Responde preguntas conceptuales o de sintaxis Formula la pregunta, evalúa y aplica la respuesta Bajo
2. Co-pensamiento Discute alternativas de diseño, plantea preguntas Conduce el razonamiento, decide los pasos Bajo-Medio
3. Asistencia de codificación Genera fragmentos de código a partir de especificaciones Especifica con precisión, lee, comprende, valida, integra Medio
4. Delegación completa Genera la solución completa Copia y entrega; o, en el mejor caso, lee superficialmente Alto

Los modos 1 y 2 son fundamentalmente compatibles con un aprendizaje sólido: la IA actúa como interlocutor o como recurso de consulta, sin sustituir el proceso cognitivo del estudiante. El modo 3 es ambiguo: puede ser una ayuda legítima (acelerar la codificación de patrones que ya se dominan conceptualmente) o un atajo dañino (saltearse el aprendizaje de esos patrones). El modo 4 es claramente problemático en un contexto formativo: vacía la actividad de su valor pedagógico.

8.3. Tres casos de análisis

El siguiente cuadro presenta tres escenarios y discute, para cada uno, en qué se diferencia un uso constructivo de uno problemático.

Caso 1: el estudiante atascado. Llevás dos horas tratando de hacer funcionar un algoritmo de backtracking para subconjuntos. La recursión está bien pero el resultado siempre devuelve listas vacías.

Uso problemático: «IA, escribime un algoritmo que genere todos los subconjuntos de una lista». Te devuelve código funcionando. Lo copiás y seguís.

Uso constructivo: «IA, mi algoritmo de subconjuntos siempre devuelve listas vacías; ¿qué errores típicos producen ese síntoma?». La IA enumera causas (no copiar el estado parcial al guardarlo, condición de caso base incorrecta, faltar el back-track). Vos revisás tu código a la luz de esas pistas, encontrás el bug (estabas guardando la referencia, no una copia), entendés por qué fallaba (aliasing, Semana 7), y aprendés algo que recordarás.
Caso 2: la especificación nueva. El proyecto final requiere implementar un módulo que lea un archivo binario de registros fijos (Semana 8) y devuelva los registros ordenados por una clave numérica.

Uso problemático: «IA, escribime el módulo completo». Recibís código que tal vez funciona, tal vez no, y que combina técnicas que tu equipo no domina.

Uso constructivo: Vos y tu equipo diseñan el módulo: definen la estructura de cada registro, la función de lectura, la función de ordenamiento. Codifican un primer borrador. Luego usan la IA para revisar: «este código lee registros de 32 bytes con la estructura <Idi30s> y los ordena por el primer campo; ¿qué casos límite no estoy considerando?». La IA sugiere: archivo vacío, archivo con un solo registro, ordenamiento estable si hay claves repetidas, manejo de fin de archivo. Vos los incorporás como casos de análisis y tests.
Caso 3: el código que no entendés. La IA generó una solución usando una técnica que no reconocés (digamos, una expresión generadora encadenada o una comprensión anidada).

Uso problemático: «funciona, lo dejo». Tu código incluye un fragmento que no podrías escribir vos, y que no podrás depurar si después se rompe.

Uso constructivo: «no entiendo esta línea; explicámela paso a paso». Si después de la explicación la idea te parece innecesariamente compleja, la reescribís con herramientas que sí dominás. Si te parece valiosa, la incorporás explícitamente a tu repertorio —y la replicás en otros ejemplos para internalizarla. El código que entregás es el código que entendés.

8.4. Límites técnicos: lo que la IA no puede hacer (todavía) confiablemente

Más allá de las consideraciones éticas y pedagógicas, hay límites técnicos concretos que conviene tener presentes. Las IAs generativas actuales (modelos de lenguaje grandes) son notablemente útiles para muchas tareas, pero exhiben patrones de error recurrentes:

La responsabilidad intelectual. En cualquier código que entregás, vos sos responsable. La IA es una herramienta; no firma el trabajo. Esto es estrictamente análogo a usar una biblioteca de terceros o consultar Stack Overflow: lo que incorporás a tu solución es tuyo, en el sentido de que tenés que entenderlo, defenderlo, mantenerlo y eventualmente repararlo. El criterio operativo para el proyecto final es claro: todo el código que entregás debe ser código que podés explicar línea por línea ante una pregunta del docente. Si no podés, no es tu código todavía: es código pendiente de ser comprendido.

8.5. Una práctica concreta: el registro de interacciones

Como parte del proyecto final, cada equipo lleva un registro de sus interacciones con IA generativa. No es una formalidad: es una herramienta de aprendizaje. El registro incluye, para cada uso significativo:

  1. El prompt exacto utilizado.
  2. La respuesta obtenida (o su esencia, si es muy extensa).
  3. El análisis crítico: ¿qué tomamos, qué descartamos y por qué?
  4. El aprendizaje: ¿qué entendimos mejor a partir de esta interacción?

Este registro cumple dos funciones complementarias. Hacia el equipo, obliga a explicitar la lectura crítica: no basta con copiar, hay que justificar. Hacia la evaluación, permite al docente entender el proceso real de elaboración del proyecto —que es lo que se evalúa, no sólo el resultado final.

9. Introducción al proyecto final

Las últimas cuatro semanas del curso (13 a 16) se dedican íntegramente al proyecto final integrador. La introducción que esta semana ofrece busca presentar la metodología, criterios y dinámica de trabajo —antes del primer encuentro dedicado al proyecto, para que cada equipo llegue ya con una idea preliminar de qué problema abordar.

9.1. Carácter del proyecto

9.2. Criterios para elegir un problema

Un buen problema para el proyecto final cumple, idealmente, los siguientes criterios:

CriterioPregunta a hacerse
Tractabilidad ¿Es realista resolverlo en 4 semanas con las herramientas del curso?
Riqueza ¿Demanda al menos 3 o 4 contenidos diferentes del curso, no sólo uno?
Modularidad ¿Se descompone naturalmente en piezas asignables a distintos integrantes?
Verificabilidad ¿Se pueden definir casos de análisis claros y verificables?
Interés ¿Le importa al equipo? Cuatro semanas son muchas si el problema no engancha.
Especificidad ¿Está acotado? «Hacer una red social» no; «sistema de turnos con archivo binario, búsqueda por DNI y reportes ordenados» sí.

9.3. Dimensiones de la rúbrica de evaluación

La rúbrica completa se discute en la primera clase de la Semana 13. Aquí adelantamos las cinco dimensiones principales para que cada equipo pueda orientar el trabajo desde ya:

  1. Pensamiento algorítmico: calidad del análisis (Pólya), pertinencia de las estructuras elegidas, fundamentación de los algoritmos, manejo explícito de complejidad.
  2. Modularización y reuso: diseño de funciones con responsabilidad clara, interfaces bien definidas, ausencia de duplicación, separación entre lógica y E/S.
  3. Documentación interna: docstrings completos (precondiciones, postcondiciones), comentarios que aportan, nombres elegidos con criterio, casos de análisis documentados.
  4. Calidad del producto: el programa hace lo que debe en los casos normales y maneja apropiadamente los casos límite. Las pruebas previstas pasan.
  5. Ética y reflexión: registro de interacciones con IA, justificación de decisiones, análisis crítico del propio proceso, contribución individual evidenciada en el historial de Git.
Una recomendación de estrategia. Antes de empezar a codificar, dedicar tiempo desproporcionado al análisis y diseño. Un equipo que llega a la Semana 14 con el algoritmo pseudocodificado, los casos de análisis identificados y los módulos esquematizados, codifica en una semana lo que un equipo sin diseño codifica (y re-codifica) en tres. Las semanas 13 y la primera parte de la 14 están específicamente diseñadas para esto. Resistir la tentación de codificar de inmediato.

10. [Holístico] Paralelismo, concurrencia y virtualización

El paradigma de divide y vencerás esconde una propiedad notable: los subproblemas, una vez generados, son independientes entre sí. Ordenar la mitad izquierda no necesita información alguna de la mitad derecha. Esa independencia abre la puerta a una pregunta que no nos hicimos hasta ahora: ¿podrían ejecutarse simultáneamente, en paralelo, en distintos núcleos del procesador?

10.1. Paralelismo y concurrencia: la distinción

Los términos paralelismo y concurrencia suelen confundirse, pero refieren a fenómenos distintos:

Una analogía. Concurrencia es un mozo que atiende cinco mesas alternando entre ellas: una mesa nunca está siendo atendida al mismo instante que otra, pero las cinco mesas progresan. Paralelismo es cinco mozos, cada uno atendiendo su mesa: las cinco mesas son atendidas al mismo instante. Concurrencia y paralelismo no son lo mismo, pero pueden combinarse: cinco mozos atendiendo dos mesas cada uno.

10.2. Por qué divide y vencerás es naturalmente paralelo

En merge sort, las dos llamadas recursivas merge_sort(mitad_izq) y merge_sort(mitad_der) son independientes: ninguna lee ni escribe datos de la otra. Si dispusiéramos de dos núcleos, podrían ejecutarse simultáneamente, y el tiempo de cada nivel del árbol de recursión se reduciría a la mitad. Lo mismo aplica recursivamente: con n núcleos, podríamos paralelizar todo el descenso.

Merge sort secuencial vs. paralelo (2 núcleos) Secuencial: sort izq (50%) sort der (50%) merge tiempo total = 320 unidades Paralelo (2 núcleos): Núcleo 1: sort izq Núcleo 2: sort der merge tiempo total = 200 unidades ≈ 60% del secuencial

10.3. Lo que el paralelismo no mejora

El paso de fusión (merge) en merge sort tiene una propiedad incómoda: depende de tener listas las dos mitades. No puede comenzar antes. Esa es la parte secuencial del algoritmo, y limita el beneficio del paralelismo. La ley de Amdahl formaliza esta intuición: si una fracción p del tiempo total del programa es paralelizable y el resto es necesariamente secuencial, el máximo speedup teórico con N núcleos es:

speedup ≤ 1 / ((1 − p) + p/N)

Aun con infinitos núcleos (N → ∞), el speedup queda acotado por 1 / (1 − p). Si el 10% de un algoritmo es necesariamente secuencial, jamás se puede acelerar más de 10× por más núcleos que se agreguen. Esta ley orienta dónde poner el esfuerzo de optimización: en reducir la parte secuencial, no sólo en agregar núcleos.

10.4. Concurrencia en Python: GIL y un matiz importante

CPython, el intérprete que estamos usando, tiene una particularidad llamada GIL (Global Interpreter Lock): un único hilo Python ejecuta bytecode a la vez, incluso en máquinas multinúcleo. Esto significa que múltiples threads de Python no aprovechan el paralelismo real para tareas que son CPU-intensivas: aunque haya 8 núcleos, el código Python no se ejecuta 8 veces más rápido. Para conseguir paralelismo real en Python existen alternativas (multiprocessing, librerías como NumPy que liberan el GIL para operaciones numéricas, o el reciente «free-threaded Python» experimental).

Por qué importa para el curso. No vamos a usar paralelismo explícito en el proyecto final —no es un curso de programación paralela. Pero la idea de que ciertos algoritmos son intrínsecamente paralelizables y otros no es un componente esencial del juicio profesional sobre la elección algorítmica. Cuando en el futuro tengas que decidir entre dos algoritmos para un problema grande, una de las preguntas legítimas será: «¿cuál de los dos escala mejor cuando agrego cómputo paralelo?». Backtracking, por ejemplo, es típicamente difícil de paralelizar (la búsqueda en profundidad es inherentemente secuencial); divide y vencerás suele ser fácil.

10.5. Virtualización: la abstracción de la abstracción

Si la concurrencia permite que un solo computador ejecute múltiples programas, la virtualización permite que un solo computador ejecute múltiples computadores enteros simulados. La idea es la misma del scheduling pero aplicada a un nivel más alto: el SO huésped (host) gestiona varios SO invitados (guest) como si fueran procesos, cada uno con su propio kernel, su propio sistema de archivos, su propia memoria asignada.

Dos formas principales de virtualización:

Máquina virtual (VM) Contenedor
Qué se virtualiza Hardware completo (CPU, memoria, dispositivos) El espacio de usuario; comparten el kernel del host
Aislamiento Muy fuerte: cada VM cree ser una máquina física Más débil: comparten kernel
Tamaño típico GB (incluye sistema operativo completo) MB (sólo el espacio de usuario)
Tiempo de arranque Decenas de segundos a minutos Milisegundos a segundos
Ejemplos VirtualBox, VMware, KVM Docker, LXC, Podman
Caso de uso típico Ejecutar Windows dentro de Linux; aislar SO Desplegar aplicaciones reproducibles, microservicios
Conexión con la práctica profesional. Cualquier proyecto que trabajen en su vida profesional —ya sea como desarrolladores, científicos de datos, ingenieros de sistemas— va a involucrar virtualización en alguna capa. Los entornos de desarrollo modernos suelen ser contenedores; los servidores en la nube son VMs corriendo en hardware compartido. La idea conceptual es siempre la misma que vimos para procesos: multiplexar un recurso escaso (CPU, hardware, infraestructura) entre múltiples consumidores, con la ilusión para cada uno de tener el recurso completo. Multiplexar es uno de los grandes leitmotivs de la informática.

11. [Holístico] Von Neumann vs. Harvard, en perspectiva

El curso comenzó (Semana 1) con la arquitectura Von Neumann: un único bus, una única memoria que aloja indistintamente datos e instrucciones, un único ciclo fetch-decode-execute. Es la arquitectura sobre la que se construye todo lo que estudiamos. Pero existe una arquitectura alternativa, históricamente paralela: la arquitectura Harvard.

11.1. La diferencia esencial

Aspecto Von Neumann Harvard
Memoria Una sola, almacena datos e instrucciones Dos memorias separadas: una para datos, otra para instrucciones
Buses Un bus compartido Dos buses independientes
Ciclo de instrucción Fetch instrucción y fetch dato compiten por el bus Fetch instrucción y fetch dato simultáneos
Flexibilidad El programa puede modificarse a sí mismo El programa no puede modificarse en ejecución
Costo de hardware Menor (un solo bus, una memoria) Mayor (dos memorias y dos buses)
Donde se usa Computadores de propósito general Microcontroladores, DSPs, sistemas embebidos

11.2. ¿Por qué importa esta distinción hoy?

El procesador de tu computadora —que sigue siendo nominalmente «Von Neumann»— incorpora rasgos de la arquitectura Harvard en su jerarquía de caché. Los chips actuales tienen caché L1 separada para instrucciones (L1i) y datos (L1d). Esto permite que el procesador busque, en un mismo ciclo, la próxima instrucción y un dato a operar —exactamente lo que la arquitectura Harvard prometía. Los niveles superiores (L2, L3, RAM) sí son unificados (Von Neumann).

A esta combinación se la llama arquitectura Harvard modificada o Von Neumann con caché Harvard: estructura lógica Von Neumann (un solo espacio de direcciones, los programas pueden cargarse desde disco, modificarse, etc.), implementación física que aprovecha la velocidad de Harvard donde más cuenta.

Lección de diseño. No hay arquitectura «pura» en los sistemas reales. Hay compromisos de diseño: la flexibilidad de Von Neumann combinada con la velocidad de Harvard. La idea de tomar lo mejor de cada paradigma es recurrente en informática: lenguajes que mezclan paradigmas (Python: imperativo + funcional + orientado a objetos), algoritmos híbridos (Timsort: merge + inserción), sistemas mixtos (Harvard modificada). El criterio profesional no es ser «puro» sino ser eficaz para el problema.

11.3. Cerrando el círculo: la visión de conjunto

Doce semanas atrás, los conceptos de Von Neumann (CPU, memoria, bus, ciclo fetch-decode-execute) podían parecer abstractos y desconectados de «escribir programas en Python». Cerramos ahora con una visión articulada del sistema computacional completo, donde cada nivel sostiene a los superiores:

El sistema computacional: capas de abstracción Hardware CPU (ALU + UC + registros) · memoria · buses · dispositivos arquitectura Von Neumann o Harvard Firmware / BIOS / microinstrucciones Sistema operativo Procesos · scheduling · gestión de memoria · sistema de archivos · drivers multiplexa el hardware entre múltiples programas Runtime de lenguaje (intérprete CPython, JVM, etc.) Bytecode · pila de evaluación · gestión automática de memoria (GC) multiplexa los recursos del SO entre los objetos del programa Programa de usuario (lo que escribimos) Algoritmos · estructuras de datos · funciones · módulos · I/O expresa el problema en términos de las primitivas del lenguaje cada capa abstrae a la inferior cada capa sostiene a la superior Cada capa abstrae los detalles de la inferior y ofrece primitivas a la superior

Esta visión articulada es el aporte propio de un curso «holístico» como el nuestro. Otros cursos enseñan a programar; algunos enseñan arquitectura; algunos otros enseñan sistemas operativos. La pretensión de este curso es que los tres temas se enseñen como un único sistema, porque eso es lo que son. Cuando un programa Python falla con un RecursionError, sabemos por qué (Semana 9, pila del SO). Cuando un algoritmo O(n log n) es 10× más lento que sorted(), sabemos por qué (Semana 11, bytecode). Cuando divide y vencerás se paraleliza bien y backtracking no, sabemos por qué (esta semana, paralelismo). Los conceptos no son anécdotas independientes: son piezas de un mismo cuadro.

12. Síntesis y mirada hacia adelante

Esta clase cierra el ciclo de contenidos del curso. Lo que sigue —cuatro semanas de proyecto integrador— no introduce ideas nuevas: pone en juego, en un mismo escenario, todo lo aprendido. Por eso esta semana funciona como bisagra: termina de instalar las últimas piezas algorítmicas (divide y vencerás profundizado, backtracking) y, al mismo tiempo, vuelve la mirada sobre el recorrido completo para mostrar que las piezas no estaban dispersas: forman un repertorio.

12.1. Dos ideas para llevarse

Si tuviéramos que elegir dos ideas conceptuales centrales de la semana, serían:

Primero, que la recursión admite dos usos cualitativamente distintos. En divide y vencerás, la recursión es cálculo: descomponer un problema grande en problemas chicos cuya solución se combina. En backtracking, la recursión es búsqueda: explorar un espacio de alternativas con la garantía de poder volver atrás. La pila de ejecución es la misma estructura en ambos casos; lo que cambia es la naturaleza del problema y la forma del árbol de llamadas.

Segundo, que la programación madura no es saber sintaxis sino tomar decisiones de diseño justificadas. A esta altura, todos los estudiantes pueden escribir un for o un if. La pregunta interesante es cuándo elegir uno u otro, qué estructura de datos usar, qué algoritmo conviene, qué casos de análisis cubrir, cómo documentar. Esas decisiones —que se ven explícitamente en la tabla integradora de la sección 7— son lo que distingue a un programador profesional de uno aficionado.

Lo que se conectó hacia atrás

Esta semana tomó prestadas, sumó y articuló piezas de prácticamente todo el curso:

Lo que se prepara hacia adelante

El recorrido alimenta directamente las cuatro semanas finales:

Una idea que recorre todo

La programación madura no es saber sintaxis sino tomar decisiones de diseño justificadas. Las cuatro semanas que vienen son la primera oportunidad real para ejercitar ese juicio profesional, sobre un problema que cada equipo eligió, en un equipo que cada estudiante integró, con las herramientas que el curso enseñó. Lo que se evalúa al final no es sólo qué hicieron sino cómo decidieron hacerlo.

Algoritmos recursivos avanzados e integración
Semana 12 — Desarrollo de Contenidos — Fundamentos de Programación — Carrera de Informática — FIUBA