Encabezado Facultad de Ciencias
Presentación

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

Optativas, Complejidad Computacional

Grupo 7011, 55 lugares. 43 alumnos.
Profesor Oscar Hernández Constantino ma ju 16 a 17:30
Ayudante Malinali Gónzalez Lara lu mi 15 a 16
Ayudante Francisco Javier Ortíz Medrano lu mi 15 a 16

 

Enlace para la primera reunión:

Lunes 15 de agosto, 15 hrs:

https://cuaieed-unam.zoom.us/j/86935362062?pwd=WnlHdjlhd1U2NWpnMDJVdTBHUS83dz09

Temario:

De manera general seguiremos el temario oficial del curso

  1. Introducción y conceptos básicos

    1. Motivación

    2. Problemas, Algoritmos y Complejidad

    3. Esquemas de Codificación

    4. Máquinas de Turing y otros modelos de cómputo

  2. Teoría de NP-Completez

    1. La Clase P

    2. La Clase NP

    3. Transformaciones Polinomiales

    4. NP-Completez

    5. Teorema de Cook

  3. Demostración de Problemas NP-Completos

    1. Problemas Básicos

    2. Técnicas de demostración de problemas NP-Completos

  4. Temas Selectos

    1. Otras Clases de Complejidad

    2. Complejidad en otros modelos de cómputo

    3. Algoritmos de Aproximación

    4. Heurísticas para problemas NP-Difíciles

Evaluación:

- Tareas

- Prácticas

- Exposición

Bibliografía:

  • Garey, Michael R., and David S. Johnson. "Computers and intractability." (1979).

  • Christos H. Papadimitriou, "Computational Complexity". (1993).

  • Sipser, Michael. "Introduction to the Theory of Computation." (1996).

  • Arora, Sanjeev, and Boaz Barak. "Computational complexity: a modern approach." (2009).

 


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.