Problemas, algoritmos y optimización
3 a 7 de septiembre de 2012
Instructor: Dr. Francisco
Javier Zaragoza Martínez.
Inicio y fin del curso: 3 a
7
de septiembre de 2012.
Horario: 11:00 a 13:00 todos
los días.
Lugar:
Sala
de
juntas del posgrado,
edificio K tercer piso (K-316).
Contenido
En este curso exploraremos diferentes
técnicas computacionales
que se aplican en la solución de problemas de
optimización combinatoria. Comenzaremos con las definiciones
básicas de problema, algoritmo y complejidad. Mostraremos
cómo con frecuencia es imposible o indeseable usar algoritmos
para resolver problemas de optimización combinatoria.
Finalmente, introduciremos el concepto de algoritmo de
aproximación y algunas aplicaciones.
- Problemas computacionales.
- Algoritmos y variantes.
- Complejidad computacional.
- Algoritmos de aproximación.
El curso está dirigido a profesores, investigadores y
profesionales con interés o experiencia en las
matemáticas discretas, las ciencias de la computación
o
la optimización combinatoria.
Calendario
- 3 de septiembre: Problemas computacionales.
- 4 de septiembre: Algoritmos y variantes.
- 5 de septiembre: Complejidad computacional.
- 6 de septiembre: Algoritmos de aproximación.
- 7 de septiembre: Algoritmos de aproximación.
Bibliografía
Artículos
K. Appel, W. Haken, "Solution of the Four Color Map Problem", Scientific
American 237 (4): 108–121, 1977.
T. Asano, K. Hori, T. Ono, T. Hirata, "A theoretical framework of
hybrid approaches to MAX SAT", Lecture
Notes
in Computer Science 1350/1997, 153-162, 1997.
L. Babai, "Monte-Carlo
algorithms
in
graph
isomorphism
testing", Université de
Montréal, D.M.S. No. 79-10, 1979.
A. Church, "An Unsolvable Problem of Elementary Number Theory", American Journal of
Mathematics 58 (58): 345–363, 1936.
W. Gasarch, "The
P=?NP
Poll", SIGACT News Complexity Theory Column 36, 2002.
D. Karger, "Global
Min-cuts in RNC and Other Ramifications of a Simple Mincut
Algorithm",
Proc.
4th
Annual
ACM-SIAM
Symposium
on Discrete Algorithms, 1993.
C. Papadimitriou, M. Yannakakis, "Optimization, approximation, and
complexity classes", J.
Comput.
System
Sci. 43, 425-440, 1991.
M. Rabin, "Probabilistic algorithm for testing primality", Journal
of
Number
Theory 12 (1): 128–138, 1980.
N. Robertson, D. Sanders, P. Seymour, R. Thomas, "The Four-Colour
Theorem", J.
Combin.
Theory
Ser.
B 70 (1): 2-44, 1997.
L. Trevisan, G. Sorkin, M. Sudan, D. Williamson, "Gadgets,
approximation, and linear programming", Proc.
37th
Ann.
IEEE
Symp.
on Foundations of Comput. Sci., IEEE Computer
Society, 617-626, 1996.
A. Wiles, "Modular elliptic curves and Fermat's Last Theorem", Annals
of
Mathematics 141 (3): 443–551, 1995.
Libros
S. Arora, B. Barak, "Computational
Complexity:
A Modern Approach", Cambridge
University
Press, 2009.
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A.
Marchetti-Spaccamela, M. Protasi, "Complexity and
Approximation: Combinatorial optimization problems and their
approximability properties", Springer,
1999.
D. S. Hochbaum (ed.), "Approximation
Algorithms
for
NP-Hard
Problems", PWS Publishing Company, 1997.
R. Motwani, P. Raghavan, "Randomized Algorithms", Cambridge
University
Press, 1995.
I. Parberry. "Problems
on
Algorithms",
Prentice
Hall, 1995.
G. Polya, "How to Solve It", Princeton
University
Press, 1945.
S. Skiena, "The Algorithm Design
Manual", Springer, 2008.
V. V. Vazirani, "Approximation algorithms", Springer,
2001.
D. P. Williamson, D. B. Shmoys, "The Design of
Approximation
Algorithms", Cambridge
University
Press, 2011.
Otros recursos en línea
Problemas computacionales: Computational
Problem, Open
Problem Project, Open
Problem Garden, Computational
Projects.
Algoritmos y variantes: Algorithm, Stony Brook Algorithm
Repository.
Complejidad computacional: Complexity
Zoo, NP
Completeness
Columns, Traveling
Salesman
Problem, Graph
Classes, House of Graphs.
Algoritmos de aproximación: Compendium
of
NP Optimization Problems, Approximation
Algorithms
for
Network
Problems.