Tecnologias

Unidad temática 1: Introducción a la optimización combinatoria y complejidad computacional


Competencias particulares: Conocer e identificar los algoritmos heurísticos mas conocidos y utilizadosen la solución de problemas de investigación de operaciones asi como Reconocer y distinguir los modelos y estructura matemática de los principales problemas de la optimización combinatoria yrelacionarlos con problemas de la practica profesional y los criterios de calidad requeridos para el desarrollo del algoritmo.



La optimización combinatoria es una rama de la optimización enmatemáticas aplicadas y en ciencias de la computación, relacionada a la investigación de operaciones, teoría de algoritmos y teoría de la complejidad computacional. También está relacionada con otros campos, comola inteligencia artificial e ingeniería de software. Los algoritmos de optimización combinatoria resuelven instancias de problemas que se creen ser difíciles en general, explorando el espacio desoluciones (usualmente grande) para estas instancias. Los algoritmos de optimización combinatoria logran esto reduciendo el tamaño efectivo del espacio, y explorando el espacio de búsqueda eficientemente.Los algoritmos de optimización combinatoria a menudo son implementados en lenguajes imperativos como C y C++, en lenguajes de programación lógicos tales como Prolog, o incluso en lenguajesmulti-paradigma tales como Oz.

Mediante el estudio de la teoría de la complejidad computacional es posible comprender la importancia de la optimización combinatoria. Los algoritmos de optimizacióncombinatoria se relacionan comúnmente con problemas NP-hard. Dichos problemas en general no son resueltos eficientemente, sin embargo, varias aproximaciones de la teoría de la complejidad sugieren que ciertasinstancias (ej. "pequeñas" instancias) de estos problemas pueden ser resueltas eficientemente. Dichas instancias a menudo tienen ramificaciones prácticas muy importantes.



En pocas palabras...