Ciencias de la Computación (plan 1994) 2024-1

Objetivos Principales:

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.

----------- ------------ ------------ ------------ ------------ ------------ ------------

Este Curso es Presencial

----------------------------------------------------------------------------

Requisito:

Haber aprobado Análisis de Algoritmos.

----------------------------------------------------------------------------

*** *** *** 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 14 de agosto del 2023

------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------

Recursos Didácticos a usar en el curso

Herramientas digitales: Classroom, Jamboard, Google Chat, Google Slides, Google Drive, Meet ...

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 +++

------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------

Evaluación:

30% Tareas

30% Programas

30% Exposiciones

10% Exámenes

--- --- --- ---

Temario

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

** Papadimimitriou, Ch. Computational Complexity, Addison Wesley, USA, 1993.

Papadimitriou, Ch.H & Steiglitz, K. Combinatorial Optimization. Algorithms and Complexity. Dover Pu. Inc, 1998

Even, S. Graph Algorithms. Technion Institute, Computer Science Press, 1979

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