Enlaces relevantes:
- Trabajos prácticos:
- Trabajos teóricos:
Los problemas de optimización son aquellos en los que el objetivo es encontrar una solución que maximice o minimice un determinado valor objetivo. Encontramos estos problemas en la Informática (e.g. acceso a recursos computacionales, planificación de tareas, enrutamiento,satisfactibilidad, etc), pero también fuera de ella (reparto de recursos, subastas, logística, marketing, desarrollo de teorías científicas a partir de observaciones, etc).
La dificultad teórica de muchos problemas reside en las raíces mismas de los límites de la Informática, concretamente en el famoso problema P vs NP. Estudiaremos algoritmos para resolver problemas de optimización de manera aproximada, así como la dificultad inherente de dichos problemas independientemente de cómo se resuelvan. Algunos algoritmos serán específicos del problema en consideración, mientras que otros serán estrategias genéricas que copian mecanismos existentes en la Naturaleza (genética, comportamiento animal, Geología, etc). Se tratarán principalmente los problemas de optimización discretos.
- a. Límites teóricos a la posibilidad de optimizar. Dureza de la aproximación.
- b. Algoritmos específicos que garantizan ratios de rendimiento conocidas (constantes o no) para sus respectivos problemas: algoritmos de aproximación.
- c. Algoritmos genéricos que no garantizan una ratio de rendimiento: métodos inspirados en la Naturaleza (Algoritmos Genéticos, Optimización por Colonias de Hormigas, Optimización por Enjambre de Partículas, Dinámica de Formación de Ríos, etc).