Reducciones y NP-completitud aplicadas a un puzzle operativo
Visión general
De qué trata este proyecto.
Estudia el problema operativo a partir de 6 meses de asignaciones reales. Identifica a qué problema clásico se reduce (graph coloring, bin packing o set cover según el caso) y demuestra la reducción polinómica en una nota técnica. Implementa: (1) un baseline exacto con backtracking sobre instancias pequeñas, (2) una codificación a SAT o ILP que aproveche un solver maduro (Z3 o OR-Tools). Compara escalabilidad y calidad sobre 50 instancias reales. Entrega nota técnica de 6 páginas, código y un informe operativo de 2 páginas para la dirección.
El Briefing
Lo que harás y lo que demostrarás.
Identificar el problema clásico equivalente al puzzle de asignación de grupos a barcos, demostrar la reducción y entregar un solver práctico.
Earning criteria — what you'll demonstrate
- Reconocer estructura NP-completa en un problema operativo real
- Demostrar reducciones polinómicas y entender su utilidad práctica
- Codificar problemas en SAT/ILP y usar solvers maduros
- Comunicar trade-offs (calidad vs tiempo) a la dirección
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ónicosSoftware Engineer
Reconocer estructura NP-completa en un problema operativo y entregar un solver práctico distingue a una Software Engineer capaz de resolver lo que otros postergan.
Este proyecto afina
- np-completeness
- sat-solving
- problem-modeling
Systems Architect
Las Systems Architects que entienden reducciones y solvers pueden decidir cuándo construir vs cuándo apoyarse en herramientas maduras.
Este proyecto afina
- reductions
- np-completeness
- algorithm-analysis
Backend Engineer
Las Backend Engineers que saben empaquetar un solver dentro de un servicio resuelven problemas operativos que otros equipos delegan a planillas.
Este proyecto afina
- sat-solving
- python
- algorithm-analysis