Encabezado Facultad de Ciencias
Presentación

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

Optativas, Complejidad Computacional

Grupo 7008, 56 lugares. 42 alumnos.
Profesor María de Luz Gasca Soto lu mi vi 11 a 12 102 (Yelizcalli)
Ayudante José Luis Vázquez Lázaro ma ju 11 a 12 102 (Yelizcalli)
Ayudante Antonio César Álvarez García ma ju 11 a 12

 

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 utiles para otras materias teóricas.

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

*** *** Pasaremos Lista de Asistencia Diario *** ***

*** *** No se aceptaran extra-largos *** ***

*** Tendrán prioridad inscripciones ordinarias***

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

La página del curso ...

https://sites.google.com/a/ciencias.unam.mx/cco-2019-1/

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

Dinámica del Curso:

Habrá exposiciones, al menos dos, por parte de los estudiantes.

Se programarán algunos Algoritmos No-deterministicos, Algoritmos de Aproximación y Heurísticas

Se revisaran Articulos de Investigación del área

Habrá, al menos, una tarea por Tema

--- --- ---

Evaluación:

30% Exposiciones,
10% Exámenes
30% Programas
30% Tareas

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

Temario

I. Introducción y Conceptos Básicos

  1. Motivación

  2. Problemas, Algoritmos y Complejidad

  3. Notación asintótica y Modelos de Cómputo.

II. La Teoría de los Problemas NP-Completos

  1. Máquinas de Turing y la Clase P

  2. La Clase NP

  3. Transformaciones Polinomiales

  4. Definición de NP-Completez

  5. El Teorema de Cook

  6. Jerarquía de Complejidad

III. Demostraciones de Problemas NP-Completos

A. Problemas Básicos

  1. 3-SAT; Clan.

  2. Cubierta de Vértices; Conjunto Dominante

  3. 3-coloración

  4. Circuito Hamiltoniano

  5. Partición

B. Técnicas

  1. Restricción

  2. Reemplazo

  3. Diseño de componentes

IV. Temas Selectos

1. Algoritmos de Aproximación

2. Heurísticas

3. Aplicaciones

Bibliografía

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

 


Hecho en México, todos los derechos reservados 2011-2016. Esta página puede ser reproducida con fines no lucrativos, siempre y cuando no se mutile, se cite la fuente completa y su dirección electrónica. De otra forma requiere permiso previo por escrito de la Institución.
Sitio web administrado por la Coordinación de los Servicios de Cómputo de la Facultad de Ciencias. ¿Dudas?, ¿comentarios?. Escribenos. Aviso de privacidad.