1. Grafos y algoritmos de tiempo polinomial. Ejemplos. Problemas hard. Ejemplos. Reducción de un problema a otro.
   
   
2. Método de Backtracking. Método Branch & Bound. Ejemplos de aplicación.
   
   
3. Programación Dinámica. Estados, decisiones y transformaciones. Principio de Optimalidad. Problema del camino más corto. Problema del mochilero. Problema del viajante. Método del multiplicador de Lagrange.
   
   
4. Complejidad Computacional. Ejemplos de problemas combinatorios. Alfabetos y palabras. Codificación. Tamaño del problema. Máquina de Turing. Problemas de tiempo polinomial. Certificado y clase de problemas NP. Clase de problemas NP-completos. Teorema de Cook. Otros problemas NP-completos: 3sat, camino hamiltoniano y problema del viajante.
   
   
5. Soluciones con garantía de aproximacion. Job scheduling. Bin Packing. Node Cover. TSP: Algoritmo de Chrisofides.
   
   
6. Métodos heurísticos: Local Search, Recocido Simulado, Tabu search, Algoritmos Genéticos. Ejemplos de aplicación.
   
   

[1]

Papadimitriou C., Steiglitz K., Combinatorial Optimization, Dover,1998.

[2]

Garey M., Johnson D., Computers and Intractability, Freeman, 1997.

[3]

Aarts E., Lenstra J.K. Ed., Local Search, Wiley, 1997.

A la página de la materia