Profesor | María de Luz Gasca Soto | lu mi vi | 10 a 11 | Taller de Ingeniería de Software |
Ayudante | José Luis Vázquez Lázaro | ma ju | 10 a 11 | Taller de Ingeniería de Software |
Comprender y aplicar la Complejidad Computacional, desde la teoría básica de la NP-completez hasta temas más avanzados.
Profundizar la formación del alumno en Computación Teórica, dotándolo de herramientas y conocimientos utiles para otras materias teóricas.
------------------------------------------------------------
Habrá exposiciones, al menos dos, por parte de los estudiantes.
Se programarán algunos Algoritmos No-deterministicos, Algoritmos de Aproximación y Heurísticas
Se revisaran Articulos de Investigación del área
Habrá, al menos, una tarea por Tema
I. Introducción y Conceptos Básicos
Motivación
Problemas, Algoritmos y Complejidad
Notación asintótica y Modelos de Cómputo.
II. La Teoría de los Problemas NP-Completos
Máquinas de Turing y la Clase P
La Clase NP
Transformaciones Polinomiales
Definición de NP-Completez
El Teorema de Cook
Jerarquía de Complejidad
III. Demostraciones de Problemas NP-Completos
A. Problemas Básicos
3-SAT; Clan.
Cubierta de Vértices; Conjunto Dominante
3-coloración
Circuito Hamiltoniano
Partición
B. Técnicas
Restricción
Reemplazo
Diseño de componentes
IV. Temas Selectos
1. Algoritmos de Aproximación
2. Heurísticas
3. Aplicaciones
* Garey ,J. Computer and Intratability: A guide to the Theory NP-Completness. Freeman, 1979
* Papadimimitriou, Ch. Computational Complexity, Addison Wesley, USA, 1993.
* Goldreich, O. Computational Complexity. A Conceptual Perspective. Cambridge, University Press, USA, 2008
* Ausielllo, G. Crescenzi, P. Kann, V. Marchetti-Spaccamela, A. Protasi, M. Complexity and Aproximation. Combinatorial Optimization Problems and their Approximability Properties. Springer, 1999.
Du, Ding-Zhu & Ko, Ker-I. Theory of Computational Complexity. Wiley & Son Inc. 2014
Goldreich, O. P, NP, and NP-Completeness. Cambridge, University Press, USA, 2010.
Papadimitriou, Ch.H & Steiglitz, K. Combinatorial Optimization. Algorithms and Complexity. Dover Pu. Inc, 1998
Even, S. Graph Algorithms. Technion Institute, Computer Science Press, 1979
Gibbons, A.M. Algorithmic Graph Theory. Cambridge University Press, 1985
Chartran, G. And Oellermann, O.R. Applied and Algorithmic Graph Theory. Mc Graw Hill. USA, 1993.
Cormen, T.H; L.C.E. & R.R.L. Introduction to Algorithms, Addison Wesley, USA, 1999
Manber, Udi. Introduction to Algorithms. A Creative Approach, Addison Wesley, USA, 1989.
Neapolitan, R. & Naimipour K. Fundations of Algorithms. 2nd Ed. Jones and Bartlett Pu, 1997
Kleingerg, J. & Tardos, E. Algorithm Design. Addison Wesley, 2005