Encabezado Facultad de Ciencias
Presentación

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

Optativas, Complejidad Computacional

Grupo 7013, 40 lugares. 11 alumnos.
Profesor Oscar Hernández Constantino lu mi vi 16 a 17 O127
Ayudante Francisco Javier Ortíz Medrano ma ju 16 a 17 O127

 

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.