Encabezado Facultad de Ciencias
Presentación

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

Optativas, Complejidad Computacional

Grupo 7015, 21 lugares. 7 alumnos.
Profesor Oscar Hernández Constantino lu mi 16 a 17:30 P208
Ayudante Malinali Gónzalez Lara ma ju 15 a 16 P208

 

Enlace para la primera reunión:

Se les hará llegar la página del curso al correo registrado.
Lunes 14 de febrero 2022, 16:00 hrs
https://cuaieed-unam.zoom.us/j/82273231970

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. Notación Asintótica

    4. Modelos de Cómputo y Esquemas de Codificación

    5. Máquinas de Turing

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