Ciencias de la Computación (plan 1994) 2025-1
Optativas, Complejidad Computacional
Grupo 7012, 40 lugares.
Objetivo:
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 útiles para otras materias teóricas.
Revisar Algoritmos de Aproximación y Heurísticas, con el objetivo de lidiar con problemas NP-Completos.
----------- ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------
El Curso es Presencial
---------------------------------------------------------------------------- ------------ ------------
*** *** *** Tendrán Prioridad Inscripciones Ordinarias *** *** ***
----------- ------------ ------------ ------------ ------------ ------------ ------------ ------------
Se mantendrá un Classroom con el objetivo de dejar material y tareas.
***---*** Es importante usar su cuenta @ciencias ***---***
---*** Iniciaremos clase desde el primer día de clases: ***---
..... Lunes 05 de agosto del 2024 .....
------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------
Recursos Didácticos a usar en el curso
Herramientas digitales: Jamboard, Google Chat, Google Slides, Google Drive, Meet ...
Además de la Página del curso y el Correo electrónico.
Material didáctico digital:
Libros de texto, tesis y artículos digitales (Bidi-Unam)
Lectures(material tomado de alguna universidad)
Notas de clase del profesor
Ejercicios y Notas preparadas por el profesor y ayudante.
------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------
Dinámica del Curso:
+++ Habrá, al menos, una Tarea por tema +++
+++ Se programarán Algoritmos No-deterministicos, Algoritmos de Aproximación y Heurísticas +++
+++ Se revisaran Artículos de Investigación del área +++
+++ Habrá exposiciones, al menos dos, por parte de los estudiantes +++
------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------
30% Tareas
30% Programas
40% Exposiciones
--- --- --- --- --- --- --- --- --- --- --- ---
I. Motivación, Introducción y Conceptos Básicos
II. La Teoría de los Problemas NP-Completos
III. Demostraciones de Problemas NP-Completos
A. Problemas Básicos
B. Técnicas para Demostrar Problemas NP-C
C. Otros
IV. Temas Selectos
A. Algoritmos de Aproximación
B. Heurísticas
------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------
Bibliografía
** Garey, M. & Johnson, D. Computer and Intratability: A guide to the Theory NP-Completness. Freeman, 1979
** Even, S. Graph Algorithms. Technion Institute, Computer Science Press, 1979
** Papadimimitriou, Ch. Computational Complexity, Addison Wesley, USA, 1993.
Papadimitriou, Ch.H & Steiglitz, K. Combinatorial Optimization. Algorithms and Complexity. Dover Pu. Inc, 1998
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.
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
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.
Gibbons, A.M. Algorithmic Graph Theory. Cambridge University Press, 1985
Kleingerg, J. & Tardos, E. Algorithm Design. Addison Wesley, 2005
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