Encabezado Facultad de Ciencias
Presentación

Ciencias de la Computación (plan 1994) 2021-2

Optativas, Complejidad Computacional

Grupo 7009, 60 lugares. 17 alumnos.
Profesor María de Luz Gasca Soto lu mi 16 a 17:30
Ayudante José Luis Vázquez Lázaro ma ju 15 a 16

 

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. Se revisaran Algoritmos de Aproximación y Heurísticas.

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

*** *** Tendrán Prioridad Inscripciones Ordinarias *** ***

*** *** *** Sólo se aceptaran extra-largos si hay lugar

Haremos una lista para la Inscripción *** *** ***

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

La página del curso:

***---*** Solo se le dará acceso a aquellos incritos oficialmente ***---***

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

Liga de la Primera Reunión y de la Primera Clase :

https://meet.google.com/lookup/armpz2s733?authuser=0&hs=179

***---*** Es importante usar su cuenta @ciencias ***---***

***---*** La primera reunión será el Lunes 01 de Marzo a la hora de clase ***---***

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

Dinámica del curso en línea

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)

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

Recursos Didácticos a usar en el 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:

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 Articulos de Investigación del área +++

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

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

Evaluación:

30% Tareas
30% Programas
40% Exposiciones

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

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

3-SAT; Clan; Cubierta de Vértices; Conjunto Dominante;

3-coloración; Circuito Hamiltoniano; Partición...

B. Técnicas para Demostrar Problemas NP-C

(Restricción, Reemplazo y 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.