Encabezado Facultad de Ciencias
Presentación

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

Optativas, Complejidad Computacional

Grupo 7096, 40 lugares. 6 alumnos.
Grupo especial para extraordinarios largos
Profesor María de Luz Gasca Soto lu mi 8:30 a 10 Taller de Lenguajes de Programación
Ayudante ma 8 a 10 Taller de Lenguajes de Programación

 

Observaciones.

*** *** *** Curso Especial: Extraordinario por Etapas *** *** ***

*** Curso dirigido a estudiantes que ya han llevado el curso varias veces.

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

*** Sólo se aceptaran extra-largos ***

*----- NO SE ACEPTARAN INSCRIPCIONES ORDINARIAS ----*

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

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.

La página del curso

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

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

Dinámica del Curso:

Habrá varias exposiciones 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,
20% Exámenes
30% Programas
20% 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.