Encabezado Facultad de Ciencias
Presentación

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

Optativas, Complejidad Computacional

Grupo 7014, 60 lugares. 28 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
Ayudante Eric Giovanni Miguel Torres 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 útiles para otras materias teóricas.

Revisar Algoritmos de Aproximación y Heurísticas, con el objetivo de lidiar con problemas NP-Completos.

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

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

*** *** *** Haremos una lista para la Inscripción de Extra-ordinarios Largos*** *** ***

*** *** *** *** *** ***

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

Liga de la Primera Reunión y Primera Semana de Clases:

https://meet.google.com/nke-hvem-mwc?authuser=0

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

***---*** Iniciaremos clase desde el primer día de clases: ***---***

Lunes 14 de Febrero del 2022

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

Dinámica del curso en línea

Plataforma en línea: Classroom y Meet

Sesiones de clases síncronas: 5 Clases; 3 con la profesora y 2 con el ayudante.

Sesiones de clases asíncronas: Se dejará material en el Classroom

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

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

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

Evaluación:

30% Tareas

30% Programas

40% Exposiciones

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

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

(Algoritmos de Aproximación, Heurísticas y Aplicaciones)

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

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

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

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

 


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.