El objetivo de este proyecto es poner en prácticas las habilidades de modelación, diseño, y análisis de algoritmos aprendidas durante toda la carrera y formalizadas en este curso. Por este motivo, el proyecto es notablemente flexible y totalmente ajustable a los intereses de los estudiantes.
Deberán buscar un problema interesante a resolver en la práctica, suficientemente complicado como para poder demostrar algunas de las habilidades a medir en el curso. Mientras más interesante y complejo sea el problema, mejor.
Una vez escogido el problema, deben formalizar los subproblemas más importantes y proponer una o más estrategias de solución para los mismos. En todos los casos deben intentar demostrar correctitud de los algoritmos propuestos y hacer un análisis de complejidad. Además, donde sea posible, demostrar cotas mínimas para los problemas, o argumentar la imposibilidad de hacerlo.
En un primer momento, se deberá entregar una primera definición del problema a resolver, argumentando su relevancia y su complejidad. Posteriormente, se entregará un informe escrito y, opcionalmente, una implementación parcial o total de la solución. La evaluación final del proyecto será una exposición oral.
El proyecto se puede hacer en equipos de cualquier tamaño, teniendo en cuenta que los requerimientos serán proporcionales al tamaño del equipo.
En el proyecto se deben demostrar las siguientes habilidades:
- Formalización de problemas
- Análisis de complejidad
- Demostración de correctitud de algoritmos
Adicionalmente, algunas de las siguientes habilidades:
- Diseño de algoritmos por las técnicas:
- Greedy
- Divide & Conquer
- Programación dinámica
- Algoritmos de aproximación
- Demostración de cota mínima en problemas P
- Demostración de problemas NP-duros y NP-completos
- Modelación de problemas de optimización como problemas de flujo
Es importante que el problema escogido tenga relevancia práctica. Aunque usted puede escoger un problema de cualquier área, se espera que el problema tenga una aplicación práctica en algún ámbito. No es válido inventar un problema ficticio para el cual no exista una aplicación práctica, aunque usted puede moldear el problema de modo que aparezcan oportunidades para aplicar las técnicas y habilidades aprendidas en el curso.
Como sugerencia, escoja un problema suficientemente ambicioso y abstracto, aunque luego en la formalización tenga que reducir el problema a un caso más concreto.
Aquí tienes algunas sugerencias de problemas NP-Duros realistas que podrían ser interesantes para tus estudiantes de diseño y análisis de algoritmos:
Este problema se centra en determinar las rutas más eficientes para una flota de vehículos que deben realizar entregas a un conjunto de clientes. Se deben considerar múltiples factores, como la capacidad de carga de cada vehículo, las ventanas de tiempo en las que los clientes están disponibles para recibir sus pedidos y las restricciones geográficas. El objetivo es minimizar el costo total del transporte, que puede incluir la distancia recorrida, el tiempo de viaje y los costos operativos. La complejidad aumenta significativamente cuando se tienen múltiples depósitos y vehículos.
Este problema implica seleccionar la combinación óptima de activos financieros para maximizar el rendimiento esperado mientras se minimiza el riesgo asociado. Los inversores deben considerar la correlación entre diferentes activos, así como sus rendimientos históricos y volatilidad. La optimización se complica debido a la necesidad de cumplir con diversas restricciones, como límites en la cantidad invertida en cada activo y requisitos de liquidez.
En este contexto, la planificación de horarios implica asignar recursos limitados (como aulas y profesores) a un conjunto de actividades (clases o exámenes) dentro de un marco temporal específico. El objetivo es crear un horario que minimice conflictos (como solapamientos entre clases) y maximice la utilización eficiente del espacio y del tiempo. Este problema presenta múltiples restricciones, como la disponibilidad de los profesores y las preferencias de los estudiantes. Se pueden considerar también condiciones aleatorias como la posibilidad de que se pierdan clases por eventos.
El diseño óptimo de una red de comunicación busca establecer conexiones entre nodos (como servidores o estaciones base) para garantizar un flujo eficiente de datos. Este problema implica decidir sobre la topología de la red, la ubicación de los nodos y la capacidad necesaria para cada enlace. Se deben considerar factores como el costo total del diseño, la latencia en las comunicaciones y la resiliencia ante fallos.
Este problema abarca la gestión eficiente del flujo de productos desde los proveedores hasta los consumidores finales. Implica decisiones sobre el almacenamiento, transporte y distribución, considerando factores como costos operativos, tiempos de entrega y niveles óptimos de inventario. La planificación debe adaptarse a variaciones en la demanda y a interrupciones en el suministro, lo que complica aún más las decisiones logísticas.
La distribución eficiente de energía eléctrica implica diseñar una red que minimice pérdidas energéticas mientras se asegura que todos los consumidores reciban electricidad dentro del marco normativo. Esto incluye decisiones sobre la ubicación y capacidad de las subestaciones y líneas eléctricas. Se deben considerar factores como la demanda variable a lo largo del tiempo y las limitaciones físicas del sistema eléctrico.
La programación de proyectos con recursos limitados (RCPS) es un enfoque que busca optimizar la asignación de recursos escasos a diversas actividades dentro de un proyecto. En un contexto práctico, imagina una empresa farmacéutica que debe lanzar un nuevo medicamento. Debe coordinar múltiples tareas como pruebas de laboratorio, ensayos clínicos y trámites regulatorios, todo mientras respeta restricciones de tiempo y presupuesto. La asignación eficiente de recursos humanos y materiales es crucial para minimizar la duración del proyecto y cumplir con las fechas límite.
El diseño óptimo de circuitos electrónicos busca minimizar el tiempo y los recursos necesarios para desarrollar circuitos complejos. Este proceso implica tomar decisiones sobre la disposición y el tipo de componentes electrónicos, considerando restricciones como el costo, el tamaño y el rendimiento del circuito. La optimización se convierte en un desafío cuando se trata de circuitos no lineales con múltiples variables interdependientes, y hay que considerar condiciones físicas de riesgo, como la temperatura y la humedad. La solución óptima debe equilibrar el rendimiento del circuito con la eficiencia de los recursos utilizados.
La planificación del uso del suelo implica asignar diferentes tipos de uso (residencial, comercial, industrial) a parcelas dentro de una región urbana o rural. Este problema es difícil por la necesidad de equilibrar múltiples factores, como la demanda económica, las regulaciones ambientales y las necesidades sociales. Por ejemplo, al diseñar un nuevo desarrollo urbano, se deben considerar aspectos como la accesibilidad al transporte público, la infraestructura existente y el impacto ambiental. Las decisiones deben optimizarse para maximizar el uso eficiente del espacio mientras se minimizan los conflictos entre diferentes usos del suelo.
La entrega del proyecto consiste exclusivamente en un reporte escrito en LaTeX. El reporte debe incluir:
- motivación del problema,
- formalización,
- propuestas de solución,
- demostraciones relevantes, y
- discusión y limitaciones.
Adicionalmente, pueden entregar implementaciones computacionales que ayuden a entender mejor el problema y las soluciones propuestas, así como resultados computacionales relevantes, estadísticas, ejemplos de uso, etc.
La evaluación del proyecto se hará en base a los siguientes criterios:
- Correctitud de las demostraciones.
- Claridad y precisión de la formalización.
- Originalidad y complejidad del problema.
- Calidad de la exposición.
| Entrega del problema | 20 de diciembre |
| Entrega final | 7 de febrero |
| Revisiones | 10 al 14 de febrero |
- El reporte debe ser escrito en LaTeX y entregado en formato PDF.
- El reporte, y todo el código y datos complementarios, debe ser entregado en un único repositorio en Github.
- El repositorio debe incluir un archivo README que explique cómo compilar el documento y cómo ejecutar el código complementario.