Encabezado Facultad de Ciencias
Presentación

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

Optativas, Complejidad Computacional

Grupo 7014, 42 lugares. 38 alumnos.
Profesor César Hernández Cruz lu mi vi 9 a 10 O125
Ayudante Humberto Lozano Chávez ma ju 9 a 10 O125

 
Cubriremos los siguientes temas:
  1. Máquinas de Turing: Máquinas de Turing y sus variantes. Codificación de problemas, nociones de algoritmo y computabilidad. Reducciones.
  2. Complejidad en Tiempo: Las clases P y NP. Reducciones polinomiales. Teorema de Cook.
  3. Complejidad en Espacio: Reducciones con espacio logarítmico. Las clases PSPACE, NPSPACE, L y NL.
La evaluación se realizará con tres tareas y tres exámenes. Las tareas se entregarán en equipos de al menos una y a lo más 3 personas. Los exámenes serán individuales en el salón de clase. Aunque este curso es obligatorio para Ciencias de la Computación, los estudiantes de Matemáticas son bienvenidos. Es bastante deseable haber cursado Autómatas y Lenguajes Formales previamente (este curso puede pensarse como una continuación natural del mismo). Una gran cantidad de ejemplos del curso son de teoría de gráficas, por lo que resulta muy conveniente haber cursado Gráficas y Juegos o Teoría de Gráficas. Un curso de Lógica también resulta de gran utilidad, ya que muchos problemas se modelan con lógica proposicional, y con lógica de primer orden.

Usaremos Google Classroom para toda la comunicación referente al curso, incluyendo la publicación de tareas. Se pide a los alumnos inscritos que por favor envíen un correo a japo@ciencias.unam.mx para ser inscritos al Classroom, su correo deberá indicar el nombre de la materia y deberá ser enviado desde una dirección @ciencias.unam.mx. La información detallada del curso estará disponible en Classroom.

 


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.