Profesor | María de Luz Gasca Soto | 10/nov/2021 | 10:00 | |||
Profesor | Oscar Hernández Constantino |
El Examen consta de dos partes: una teórica (examen) y otra práctica (dos programas).
Usaremos la Plataforma Classroom para contactarnos; ahí pondré el examen y las descripciones de los programas.
Parte Teórica:
Consta de un examen sobre los temas del curso. El alumno tendrá 48 horas para entregar el examen
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 entregar los programas
Fecha del Examen Teórico: Miércoles 10 de noviembre a las 10am
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