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 y jueves de 12:00 a 13:00, salón 1 de Instituto de Matemáticas. Clases de ejercicios: viernes a las 12:00.

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):

• Sebastián Bejos
  
• Instituto de Matemáticas, Cubículo ?, UNAM
• email: jbejos@uxmcc2.iimas.unam.mx
  

Regresar a Contenido

Clases

1. 3 de febrero.  Presentación del curso, en powerpoint. (impartida por Sergio)
   
2. 5 de febrero. Modelos de cómputo y Tesis de Church-Turing. Tarea 1. (impartida por Sergio).
   
3. 6 de febrero. Ayudantía, notación asintótica. (impartida por Sebastián)
   
4. 10 de febrero. Modelo RAM, funciones primitivas recursivas y recursivas, función de Ackerman. (impartida por Sergio)
5. 12 de febero. Máquinas de Turing, y máquina universal de Turing (impartida por Sergio)
6. 13 de febrero. Tarea 1 y dudas de clases anteriores. (impartida por Sebastián)
7. 17 de febrero. modelo de cómputo DNA. (impartida por Dino)
8. 19 de febrero. modelo de cómputo DNA. (impartida por Dino)
9. 20 de febrero. Tarea 1 y dudas de clases anteriores. (impartida por Sebastián)
10. 24 de febrero. Problema de la detención. (impartida por Sergio)
11. 26 de febrero. Máquinas enumeradoras, problemas reconocibles vs. decidibles, 10o problema de Hilbert (impartida por Sergio)
    
12. 3 de marzo. Cardinalidad, más problemas que máquinas de Turing. (impartida por Sergio)
13. 5 de marzo. Proyección de la película Julia Robinson and Hilbert's Tenth Problem.
14. 10 de marzo. Reducciones Turing y Many-one, grados. (impartida por Sergio)
15. 12 de marzo. Grados, problema de Post. (impartida por Sergio)
16. 17 de marzo. cómputo DNA (impartida por Dino)
17. 19 de marzo. cómputo DNA (impartida por Dino)
18. 24 y 26 de marzo. Lecture 1: The complexity of computations,  del Kozen (impartida por Diego Rábago Arredondo)
19. 31 de marzo y 2 de abril. Lecture 2: Time and Space Complexity,  del Kozen (impartida por Cecilia Chávez  Aguilera y Marco Hernández Ramírez)
20. 14 y 16 de abril. Lecture 5: Logspace Computability,  del Kozen (impartida por Ernesto Román González y Hugo Rodríguez Peña)
21. 21 y 23 de abril. Invitado especial, Michel Raynal: modelo de cómputo distribuido, orden parcial de eventos.
    
22. 12 y 14 de mayo. Lecture 6: The Circuit Value Problem,  del Kozen (impartida por Carlos Alegría  y Guillermo Guadarrama González)
23. 19 y 21 de mayo. Lecture 7: Alternation,  del Kozen (impartida por Lazaro Clapp)
24. 26 y 28 de mayo. Lecture 8: Problems Complete for PSPACE  y primera mitad de Lecture 9: The Polynomial-Time Hierarchy, del Kozen (impartida por Arturo Curiel Díaz y Felipe Gayosso Martínez)
25. 2 y 4 de junio. Segunda mitad de Lecture 9: The Polynomial-Time Hierarchy  y Lecture 10 More on the Polynomial-Time Hierarchy: del Kozen (impartida por Ángel Zúñiga Chávez y Alin Hernández Paredes)
26. 9 de junio. Lecture 11: Parallel Complexity  del Kozen (impartida por Zamora Fuentes Jose Maria)
27. 11 de junio. Modelo de computación molecular (impartida por Andrés Gomez Urquiza)
    
28. 16  de junio. Un modelo fuerte de DNA (impartida por olkin Garduño Alvarado y Laura Leonides)
    
29. 18 de junio. Implementaciones físicas de cómputo con DNA (impartida por Verena Moock)

Tareas

Las tareas estarán disponibles:

1. Tarea 1: Tema: fundamentos, modelos de cómputo, y lecturas: On Computable Numbers by A. M. Turing, Turing's Ideas and Models of Computation by Peter Wegner, The Myth of Hypercomputation by Martin Davis.
   Asignada: 13 de febrero 2009. Entrega: 24 de febrero 2009.
   
2. Tarea 2: Tema: modelos de cómputo, y lectura "Who Can Name the Bigger Number?".
   Asignada: 28 de febrero 2009. Entrega: 12 de marzo 2009.
3. Tarea 3: Tema: complejidad de tiempo y espacio, reducibilidad, y lecturas: On Computational Complexity and the Nature of Computer Science de Juris Hartmanis.
   Asignada ? 2009. Entrega: 7 de mayo 2009.
4. Tarea 4: Tema: circuitos y Teorema de Cook-Levin.
   Asignada ? 2009. Entrega: 28 de mayo 2009.
5. Tarea 5: Tema: Máquinas de Turing alternantes. Lectura capítulo de Stephen Cook y Leonid Levin del libro Out of Their Minds
   Asignada: 4 de junio 2009. Entrega: 11 de junio 2009.

Proyectos (lista tentativa)

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