Profesor | María de Luz Gasca Soto | lu mi vi | 11 a 12 |
Ayudante | José Luis Vázquez Lázaro | ma ju | 11 a 12 |
*** *** *** Sólo se aceptaran extra-largos si hay lugar
Haremos una lista para la Inscripción *** *** ***
----------------------------------------------------------------------------------------------
----------- ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------
***---*** La primera reunión será el Lunes 21 de Septiembre a la hora de clase ***---***
------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------
Plataforma en línea: Classroom y Meet
Sesiones de clases síncronas: 4 Clases; 2 con la profesora y 2 con el ayudante.
Sesiones de clases asíncronas: Se dejará material en el Classroom y en el Drive (página del curso)
------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------
Herramientas digitales: Jamboard, Google Chat, Google Slides, Google Drive y Meet
Además de la Página del curso y el Correo electrónico.
Material didáctico digital:
------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------
+++ Habrá, al menos, una Tarea por tema +++
+++ Se programarán Algoritmos No-deterministicos, Algoritmos de Aproximación y Heurísticas +++
+++ Se revisaran Articulos de Investigación del área +++
+++ Habrá exposiciones, al menos dos, por parte de los estudiantes +++
------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------
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