1. Propósito del proyecto
El proyecto integrador reúne los conceptos del curso para resolver un problema de combinatoria relacionado con programación o informática. La meta no es solo obtener un resultado, sino explicar el modelo matemático, justificar el algoritmo y analizar sus límites.
El trabajo debe mostrar la relación entre una situación concreta, su representación abstracta, el conteo de posibilidades y una solución verificable.
2. Competencias que se integran
- Identificar principios de suma, producto, complemento e inclusión-exclusión.
- Seleccionar entre permutaciones, variaciones y combinaciones.
- Modelar recurrencias y aplicar programación dinámica.
- Generar configuraciones con backtracking y poda.
- Interpretar caminos, grafos, estructuras de datos y espacios de búsqueda.
- Verificar resultados mediante ejemplos y simulaciones.
3. Elegir un problema
El problema debe tener un conjunto de posibilidades suficientemente claro y una pregunta que pueda responderse mediante conteo, decisión, enumeración u optimización.
Algunas opciones son: rutas en una cuadrícula, asignación de tareas, generación de contraseñas, coloración de grafos, selección de subconjuntos, planificación de recorridos o colocación de elementos sin conflictos.
4. Etapas de trabajo
5. Definir los objetos
El primer paso matemático es identificar qué elementos intervienen: personas, tareas, posiciones, vértices, símbolos, pasos o valores.
También se debe aclarar si los objetos son distinguibles, si pueden repetirse y si el orden importa. Estas decisiones determinan la técnica de conteo adecuada.
6. Especificar las restricciones
Una restricción indica qué configuraciones no son válidas. Puede impedir repeticiones, exigir adyacencias, limitar cantidades, bloquear posiciones o establecer relaciones entre elementos.
Una especificación precisa debe responder: ¿qué se puede elegir?, ¿qué está prohibido?, ¿cuándo se completa una solución?
7. Elegir la técnica combinatoria
La técnica debe corresponder a la estructura del problema:
- Principio del producto para decisiones independientes.
- Combinaciones cuando el orden no importa.
- Permutaciones cuando se ordenan todos los elementos.
- Variaciones cuando se ordena solo una parte.
- Complemento e inclusión-exclusión para restricciones.
- Recurrencias y Catalan para estructuras recursivas.
8. Diseñar el algoritmo
El algoritmo debe indicar qué información mantiene, qué decisiones toma y cómo termina. Si se enumeran soluciones, debe evitar duplicados; si solo se cuenta, puede guardar cantidades en lugar de construir cada objeto.
function contarConfiguraciones(opciones, esValida) {
let total = 0;
function explorar(indice, parcial) {
if (indice === opciones.length) {
if (esValida(parcial)) total++;
return;
}
for (const valor of opciones[indice]) {
parcial.push(valor);
explorar(indice + 1, parcial);
parcial.pop();
}
}
explorar(0, []);
return total;
}
console.log(contarConfiguraciones([[0, 1], [0, 1]], function () {
return true;
})); // 49. Incorporar poda o programación dinámica
Si el espacio de búsqueda es grande, el proyecto debe explicar cómo se reduce el trabajo. La poda descarta estados imposibles; la programación dinámica reutiliza resultados; una fórmula directa evita enumerar soluciones.
La elección debe justificarse comparando el tamaño del problema y el tipo de respuesta que se necesita.
10. Casos de prueba
Los casos pequeños permiten enumerar manualmente las soluciones y verificar el algoritmo. También deben incluirse casos límite: conjunto vacío, longitud cero, tablero mínimo, ausencia de obstáculos o restricciones incompatibles.
11. Comparar con una fórmula
Cuando exista una fórmula conocida, se debe comparar su resultado con el algoritmo para varios tamaños. Si difieren, hay que revisar índices, casos iniciales, repeticiones y condiciones de validez.
Esta comparación es una forma de conectar la implementación con la demostración combinatoria.
12. Medir la eficiencia
El informe debe indicar cómo crece el trabajo del algoritmo. Se pueden medir configuraciones generadas, estados visitados, memoria utilizada o tiempo aproximado.
Preguntas útiles: ¿el crecimiento es lineal, polinómico, exponencial o factorial? ¿Qué efecto tiene una restricción? ¿Cuánto reduce la poda?
13. Visualizar el resultado
Una representación visual facilita la comprensión del modelo. Puede ser una tabla de conteos, un árbol de decisiones, una cuadrícula, un grafo, una lista de soluciones o un gráfico del crecimiento.
La visualización debe complementar la explicación y mostrar una relación relevante, no reemplazar la definición matemática.
14. Simulación: planificar el proyecto
Selecciona el tipo de problema, el tamaño de entrada y la estrategia principal. La herramienta estima el espacio de configuraciones y propone los componentes que debería incluir el proyecto.
| Componente | Recomendación |
|---|
15. Estructura del informe final
- Introducción y motivación del problema.
- Definición formal de objetos y restricciones.
- Modelo combinatorio y fórmulas utilizadas.
- Descripción del algoritmo y decisiones de diseño.
- Pruebas, resultados y visualizaciones.
- Análisis de complejidad, limitaciones y mejoras posibles.
- Conclusiones y relación con informática.
16. Criterios de evaluación
Se puede evaluar la claridad del planteo, la corrección del modelo combinatorio, la calidad del algoritmo, la cobertura de las pruebas, el análisis de eficiencia y la capacidad de explicar los resultados.
Un proyecto completo debe permitir que otra persona reproduzca el razonamiento y compruebe sus conclusiones.
17. Resumen del curso
La combinatoria aplicada a informática permite contar posibilidades, modelar restricciones y diseñar algoritmos para explorar o evitar espacios de búsqueda. En el proyecto integrador se conectan principios de conteo, recurrencias, grafos, estructuras, probabilidad y seguridad.