Reducciones y NP-completitud aplicadas a un puzzle operativo
Visión general
De qué trata este proyecto.
Reduce un puzzle operativo de turismo a un problema NP-completo, implementa soluciones exactas y con SAT, y obtén un certificado verificable.
El escenario
El operador (180 K turistas/año, fuerte estacionalidad de junio a septiembre) necesita el solver listo antes del pico para liberar 2-3 horas/día del responsable de operaciones.
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.
Algorithm Design and Analysis
Bachelor · Algorithms
Strong alignment
This challenge maps to Algorithm Design and Analysis at the Bachelor level. It sharpens the same practical skills your coursework expects — but in a real industry context with actual constraints and deliverables.
Habilidades
Habilidades que demostrarás.
Cada una aparece en tu credencial verificada.
- Np Completeness
Apply np completeness to solve real industry problems and demonstrate production-level capability.
- Reductions
Apply reductions to solve real industry problems and demonstrate production-level capability.
- Sat Solving
Apply sat solving to solve real industry problems and demonstrate production-level capability.
- Algorithm Analysis
Apply algorithm analysis to solve real industry problems and demonstrate production-level capability.
- Python
Write clean, efficient Python for data processing, automation, and backend services.
- Problem Modeling
Apply problem modeling to solve real industry problems and demonstrate production-level capability.
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.
Software 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