Introducción a Teoría de la Computación

Profesor(es): Sergio Rajsbaum,  Ricardo Strausz

Página principal del curso.
Curso impartido en la UNAM en la Facultad de Ciencias y en el Posgrado en Ciencia e Ingeniería de la Computación .

Lugar: Martes de 15:00 a 17:00, salón 3 de Instituto de Matemáticas.

Contenido de esta página

• Contacto con Profesor y Ayudantes
• Clases
  
• Tareas
• Proyectos
  

Contacto con Profesor y Ayudantes

Profesor(es):

• Sergio Rajsbaum
  Instituto de Matemáticas, Cubículo 107, UNAM
  
•  email: rajsbaum@matem.unam.mx
• web: http://www.matem.unam.mx/~rajsbaum/
• Ricardo Strausz
  Instituto de Matemáticas, Cubículo 1??, UNAM
  
•  email: strausz@math.unam.mx
  
• web: http://www.matem.unam.mx/strausz/
  

Ayudante(s):

• Paulina Figueroa
• Instituto de Matemáticas, Cubículo ?, UNAM
• email: figueroa@matem.unam.mx
  

Regresar a Contenido

Clases

1. 14 de febrero. Reunión para fijar horario, presentación del curso.
2. 21 de febrero. Máquinas de Turing. Tarea 1. (impartida por Sergio).
   
3. 28 de febrero. No hay clase por el Coloquio de Gráficas.
4. 7 de marzo. Las clases P y NP. Tarea 2. (impartida por Sergio)
5. 14 de marzo. La clase NP-Completos (impartida por Sergio)
6. 21 de marzo- asueto.
7. 28 de marzo- Teorema de Cook-Levin (impartida por Sergio)
8. 4 de abril - (impartida por Sergio)- Probando problemas NP-Completos; 3SAT (reducción de SAT), VC (reducción de 3SAT).  Complejidad de Circuitos; si un lenguaje esta en TIEMPO(t(n)) entonces se puede reconocer por una familia de circuitos de complejidad O(t^2(n))
   
9. 11 de abril - Semana Santa
10. 18 de abril - (impartida por Dino)
11. 25 de abril - (impartida por Dino)
12. 2 de mayo - (impartida por Dino)
13. 9 de mayo - (impartida por Dino)
14. 16 de mayo - (impartida por Dino)
15. 23 de mayo - (impartida por alumnos)
16. 30 de mayo - (impartida por alumnos)
17. 6 de junio - (impartida por alumnos)
18. 13 de junio - (impartida por alumnos, semana de exámenes)
19. 20 de junio - - (impartida por alumnos, semana de exámenes)

Tareas

Las tareas estarán disponibles:

1. Tarea 1: Tema: máquinas de Turing.
   Asignada: 21 de febrero 2006. Entrega: 7 de marzo 2006.
   
2. Tarea 2: Asignada: 7 de marzo 2006. Entrega: 28 de marzo 2006.
3. Tarea 3: Asignada: 28 de marzo 2006. Entrega: 18 de abril 2006.

Proyectos

1. Algoritmos de aproximación
   
• Algoritmo de 2-aproximación para VC
• Si P distinto de NP no existe algoritmo de d-aproximación polinomial para TSP, para ninguna d
• Para el caso de TSP que satisface la desigualdad del triángulo, hay un algoritmo de 2-aproximación
• Referencias:
  
• Hromkovic Theoretical Computer Science, Springer
  
• Lecture Notes on Approximation Algorithms for Network Problems (Ravi, Cheriyan)
2. SL=L y complejidad de espacio
   
• Teorema de Savitch y corolario PSPACE=NPSPACE
• PATH es NL-completo: Sipser Cap 8.4, 8.5
  
• LOGSPACE, caminos aleatorios en gráficas y secuencias universales de recorido: cap 5 de Gems of Theoretical Computer Science, Springer
  
• O. Reingold, Undirected ST-Connectivity in Log-Space, ACM STOC 2005.  manuscript 2004.
  

Regresar a Contenido