Encabezado Facultad de Ciencias
Presentación

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

Optativas, Complejidad Computacional

Grupo 7012, 60 lugares. 56 alumnos.
Profesor Oscar Hernández Constantino ma ju 16 a 17:30
Ayudante Christian Rafael García García lu mi 15 a 16
Ayudante Malinali Gónzalez Lara lu mi 15 a 16

 

[CC 2022-1] Presentación del curso

Martes, 31 agosto · 16:00 hrs
Información para unirse a la reunión de Google Meet
Vínculo a la videollamada: https://meet.google.com/twd-jhse-tbf

Primera sesión de clases 21 de septiembre a las 16:00 hrs

Enlace para la primera reunión:

Se les hará llegar la página del curso al correo registrado.

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.