Algoritmo de Karger para Cortes Mínimos en Red de Distribución
Visión general
De qué trata este proyecto.
Implementa Karger básico (contracción aleatoria de aristas) y Karger-Stein (recursión con dos contracciones independientes). Para garantizar probabilidad de éxito mayor o igual a 0,999 calcula el número de repeticiones necesarias y justifícalo matemáticamente. Compara contra Stoer-Wagner determinista sobre el grafo de 4.200 nodos. Reporta: tamaño del corte mínimo encontrado, número de cortes alternativos del mismo tamaño (aristas críticas), tiempo de ejecución y número de repeticiones. Entrega código en Python con NetworkX, un informe de 10 páginas y un visualizador del corte sobre un mapa interactivo.
El Briefing
Lo que harás y lo que demostrarás.
Encontrar el corte mínimo de un grafo logístico de 4.200 nodos con probabilidad de éxito mayor o igual a 0,999 usando Karger-Stein y validarlo frente a Stoer-Wagner.
Earning criteria — what you'll demonstrate
- Implementar y analizar algoritmos randomizados Monte Carlo en grafos reales
- Calcular cotas de probabilidad de éxito desde la teoría
- Comparar enfoques randomizados vs deterministas con criterios objetivos
- Traducir un resultado algorítmico en una recomendación de negocio
Encaje académico
Dónde encaja esto en tus estudios.
Afina las mismas habilidades que tu titulación espera de ti.
Habilidades
Habilidades que demostrarás.
Cada una aparece en tu credencial verificada.
Carreras
Roles para los que esto te prepara.
Títulos reales. Puentes de habilidades reales. Elige el que más se acerque a tu trayectoria.
Trayectorias profesionales que esto construye
Roles canónicosInvestigador Científico
Aplicar algoritmos randomizados clásicos a un grafo real de 4.200 nodos y justificar la cota de éxito con la teoría es el tipo de trabajo aplicado que un investigador científico junior necesita en su porfolio.
Este proyecto afina
- randomized-algorithms
- karger-stein
- probabilistic-analysis
Ingeniero de Backend
Los ingenieros de backend que pueden implementar algoritmos avanzados de grafos sobre datos reales pasan el filtro de las entrevistas de empresas de logística e infraestructura cloud.
Este proyecto afina
- graph-algorithms
- python
- algorithm-analysis
Ingeniero de Datos
Modelar redes logísticas como grafos y encontrar puntos críticos con algoritmos clásicos es el día a día de un ingeniero de datos en operaciones de transporte multimodal.
Este proyecto afina
- graph-algorithms
- python
- randomized-algorithms