Profesor | María de Luz Gasca Soto | 12/abr/2023 | 14:00 | O133 | ||
Profesor | Oscar Hernández Constantino |
Parte Teórica:
Consta de un examen presencial sobre los temas del curso y se realizará el día 12 de abril del 2023, de 2pm a 4pm, en el salón O133.
Parte Práctica:
Consiste en realizar dos programas, los cuales se dejaran una vez que entregue el examen teorico.
El alumno tendrá una semana para realizar los programas. Se le citará, de manera presencial, para entregar y defender sus programas.
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