🧮 Computational Mathematics

Inicio · Parte 04 — Matemática discreta para computación

100 — Capstone: modelar dependencias con grafos

intermedio clase 20 de 20 4 horas demostración capstone_dependency_graph

Planificar dependencias es ordenar topológicamente y agrupar por niveles para paralelizar.

Fórmulas

nivel(v) = 1 + máx(nivel(u)) sobre los predecesores u
pasos secuenciales mínimos = máximo nivel + 1

Desarrollo

El capstone monta el problema real que resuelve cualquier sistema de construcción o de orquestación: dado un grafo de dependencias, decidir en qué orden ejecutar las tareas, cuáles pueden ir en paralelo y qué hacer si hay un ciclo.

El orden topológico da la secuencia válida. Agrupar por niveles —donde el nivel de una tarea es uno más que el máximo de sus predecesores— da algo más útil: todas las tareas del mismo nivel son independientes entre sí y pueden ejecutarse simultáneamente. El número de niveles es el número mínimo de pasos secuenciales, sin importar cuántos trabajadores haya.

Ese número es el camino crítico, y es la cota que ninguna cantidad de paralelismo puede superar. Si un pipeline tiene cinco niveles, tardará al menos cinco pasos aunque se disponga de mil máquinas. Es la versión discreta de la ley de Amdahl.

La detección de ciclos completa la herramienta. Un grafo con ciclo no admite orden topológico, y el algoritmo lo detecta contando cuántos vértices consiguió emitir. Los vértices no emitidos son exactamente los que están en el ciclo o dependen de él, lo que convierte el fallo en un diagnóstico útil en lugar de en un error opaco.

Ejemplo trabajado

Planificar el pipeline y detectar un ciclo.

Orden de ejecución:
  entrada, limpieza, features, split, entrenamiento, evaluacion

Niveles paralelizables:
  nivel 0: entrada
  nivel 1: limpieza
  nivel 2: features, split      ← pueden ir en paralelo
  nivel 3: entrenamiento
  nivel 4: evaluacion

Tareas: 6
Pasos secuenciales mínimos: 5    (camino crítico)
Con 2 trabajadores: sigue siendo 5 pasos

Con arista evaluacion → limpieza:
  ciclo detectado, 5 nodos bloqueados

Qué calcula el laboratorio

Capstone: planificar un pipeline con grafos y detectar dependencias rotas.

python classes/part-04-matematica-discreta-para-computacion/100-capstone-modelar-dependencias-con-grafos/lab.py
compmath run 100

Salidas del laboratorio (6)

Muestra de la ejecución real

{
  "orden_de_ejecucion": [
    "entrada",
    "limpieza",
    "features",
    "split",
    "entrenamiento",
    "evaluacion"
  ],
  "niveles_paralelizables": {
    "0": [
      "entrada"
    ],
    "1": [
      "limpieza"
    ],
    "2": [
      "features",
      "split"
    ],
    "3": [
      "entrenamiento"
    ],
    "4": [
      "evaluacion"
    ]
  },
  "pasos_secuenciales_minimos": 5,
  "tareas": 6,
  "grafo_con_ciclo_detectado": true,
  "nodos_bloqueados_por_el_ciclo": 5
}

Errores comunes

Dónde se usa

Sistemas de construcción, orquestadores de flujos (Airflow, Dagster), resolución de dependencias de paquetes, planificación de proyectos y ejecución de grafos de cómputo.

Idea rectora de la parte

El principio del palomar demuestra colisiones sin construir un ejemplo.

Error a evitar

Confundir implicación con equivalencia lógica.

Conexión con IA

Los grafos de cómputo, la búsqueda en árbol y las GNN son estructuras discretas; el conteo sostiene la probabilidad que después usa todo modelo generativo.

Bibliografía de la clase

Archivos de la clase

← 099 Números primos y máximo común divisor 101 Escalares, vectores y matrices →