TEORÍA DE LA COMPUTACIÓN

Destacamos aquí algunos recursos de Teoría de la Computación. Los contenidos son acordes al temario actual correspondiente a la carrera de Ing. en sistemas computacionales en los Institutos Tecnológicos, DGEST (excepto por las secciones indicadas con * que se incluyen para complementar o enriquecer el programa) Le invitamos también a visitar las sugerencias de aprendizaje.

(Actualizado: 2010.06.11)

1. Introducción

[1.1] Autómatas, computabilidad y complejidad: (ver bibliografía en sección [B*])

[1.2] Nociones Matemáticas

  • [FPST] Max Fernández de Castro, Asunción Preisser, Luis Felipe Segura y Yolanda Torres Falcón. “Lógica Elemental“. UAM, 1996. [acc. 2008.09.04]
  • [Z] Elias Zakon. “Basic concept of Mathematics” (pdf, 208 pp.) The Trillia Group. [acc. 2008.09.03]

[1.A*] Demostraciones matemáticas (en general)

[1.3] Inducción matemática (I.M.)

2. Lenguajes Regulares

  • [2.4] Lenguajes no regulares
    • [ADU] The Pumping Lema (video) [acc. 2009.10.16]
  • [2.A] Aplicaciones selectas

3. Lenguajes Libres[/Independientes] de Contexto

  • [3.1] Gramáticas Libres[/Independientes] de Contexto
  • [3.2] Árboles de derivación
  • [3.3-6] Formas Normales [y procedimientos de normalización]

  • [3.7] Eliminación de la ambigüedad
  • [3.8] Autómatas Push-Down [Autómatas a Pila]
  • [3.9] Lenguajes no Libres de Contexto

4. Máquina de Turing

[4.1] Problemas de Hilbert

[A*] Cursos selectos

[B*] Bibliografía recomendada

[C*] Herramientas software recomendadas

[D*] Código BFC de referencia (experimental)

  • ♦rbinarios.at2 ; código para aceptar un número racional binario (con .) Cortesía: Héctor Ayala [acc. 2009.10.14]

[E*] Código Scheme básico de referencia (experimental)

  • sets.scm : código para operaciones básicas con conjuntos
  • decide.scm: código elemental que muestra operaciones lógicas
  • frp.scm: código básico para ejercicio de funciones rec. primitivas
  • afd.scm ; implementa un autómata finito determinista
  • afn.scm ; implementa un autómata finito no-determinista
  • kleene.ss ; implementa de forma básica la unión de Σ^n, desde n=0 hasta n
  • mt01.scm ; código preliminar para complementar una MT
  • nsa.scm + blib.scm ; implementa un autómata a pila no determinístico (non-deterministic stack automaton. Incluye conversión básica GIC a NSA) [rev. 2009.11.21]

[F]* Información específica para Curso en el ITT (2010-1 Grupo 1W4A)

  • Aviso: Calificaciones finales en el SII [Junio 10, 7am. Gracias]
  • Sugerencias:
    • [*] Disfrutar las vacaciones (por ejemplo con el libro The Unravelers: Mathematical Snapshots)
    • [3] Avanzar en la lectura, traducción e interpretación del artículo de Martin Davis sobre el H10, según el bloque que seleccione.
    • [2] Experimentar con Gramáticas GIC y Autómatas a Pila mediante JFLAP
    • [1] Revisar el ejemplo de ambigüedad (pp. 34-35) en libro de Cases y Màrquez (si-entonces)
  • Examenes/evaluaciones próximas:
    • Ø (gracias por su dedicación)
  • Exámenes prototipo: (2009-1:  unid-1 | unid-2 | unid-3 | 4 | 5 | 6)
  • Calificaciones Parciales: { Unid-1 | Unid-2 | Unid-3 | } [rev. 2010.06.02.  Gracias por su paciencia ]
  • Tarea 1.1 Ejercicios 1-12 [Brena, pp. 20-21]
  • Tarea 1.2 Ejercicios 13-18 [Brena, p. 21-22]
  • Tarea 1.3 Ejercicios 19-24 [Brena, p. 22]
  • Investigación 1.α Décimo Problema de Hilbert y Julia Robinson
  • Reseña 1.A Video de Julia Robinson por ZALA Films
  • Recomendaciones: {  Para revisar temas de lógica y conjuntos, se recomienda  Uzcátegui-Aylwin, C. (2009) y el capítulo 1 de Brena (2003) }
  • Tarea 2.1 Ejercicio 2.2.1 [Hopcroft, et al. p. 58] {Due: viernes 12 mzo }
  • Tarea 2.2 Ejercicio 2.2.4 y 2.2.5 [Hopcroft, et al. p. 59] {Due: miércoles 17 mzo }
  • Exposición 2.α Expresiones regulares (por equipos, 10 min.) {lunes 22 mzo}
  • Tareas 3.i (i=1..3, ver notas de clase)
  • Cuestionario sobre Decidibilidad y Reducibilidad [Ref. 2009-1] (Ref. Cap. 9 Libro de HMU). [add. 2009.06.08]
  • [Evaluación parcial de unidades 5 y 6] Distribución de bloques para las exposiciones del artículo de Martin Davis “Hilbert’s tenth problem is unsolvable“:  (Gracias por enviar su selección de su número de bloque vía email del 13-17 de mayo; actualizado: 2010.05.17)
    1. [ECB, may 18] pp. 233-239 {Introduction, 1.Diophantine Sets} 
    2. [ECB, may 20] pp. 239-240 {2. Twenty-four easy lemmas} 
    3. [Miguel, Ezequiel y Arturo; may 20] pp. 241-242 {Lemma 2.6 …} 
    4. [Jesús, Jim y Enrique; may 21] pp. 242-244 {Lemma 2.13 …} 
    5. [Adriana, Iván y Salvador; may 21] pp. 244-246 {3. The exponential function} 
    6. [Fernando y Emmanuel, may 25] pp. 246-248 {Theorem 3.3 …}
    7. [Diana y Melina; may 25] pp. 248-249 {4. The language of Diophantine predicates} 
    8. [Salvador y Octavio; may 27] pp. 250-252 {Lemma 4.2 …} 
    9. [Michael y ..; may 27] pp. 252-255 {5. Bounded quantifiers}
    10. [select; may 28] pp. 255-256 {To prove the → implication …} 
    11. [Arlenne, Javier Andres y Pedro Ossiris; may 28] pp. 257-260 {6. Recursive functions}
    12. [Raymundo y Jesús Antonio; may 31] pp. 260-262 {7. A universal Diophantine set}
    13. [select; jun 01] pp. 262-264 {Naturally this result …}
    14. [Nadia, Neilz y Areli; jun 01] pp. 264-264 {8. Recursively enumerable sets}
    15. [Juan Francisco y Luis Fernando; jun 02] pp. 264-265 {9. Historical appendix}
    16. [select; jun 02] pp. 265-267 {In [27], Julia Robinson …}

(Desde: 2008.08.28)

  1. Recent Posts

    1. Digital Library of Mathematical Functions
    2. Martin Gardner (1914-2010)
    3. Johann Carl Friedrich Gauss (Aniversario)
    4. Henri Poincaré (aniversario)
    5. Poema de Michael Atiyah
    6. Creatividad en Matemáticas, IBL y el Método de Moore
    7. Competencia matemática, mediación y fluidez
    8. Eventos Matemáticos 2010
    9. Medicina y matemáticas
    10. Recursos Interactivos para Cálculo
    11. Película HARD PROBLEMS
    12. Membresía verde de la MAA
    13. Licenciatura en Matemáticas ESAD
    14. Open Calculus
    15. The Mathematical Intelligencer
    16. Escritura Matemática y Graficación
    17. L’Enseignement Mathématique
    18. Conferencia ¿Por qué No entiendo Matemáticas?
    19. Recursos para Primaria-Secundaria
    20. Recursos para precálculo
    21. Invitación a resolver problemas de matemáticas
    22. Paul Halmos y La Enseñanza de la Solución de Problemas
    23. Feliz Día del Estudiante
    24. ¿Hiciste alguna buena pregunta hoy?
    25. Feliz Día del Maestro
    26. Trío Gödel-Poincaré-Gauss
    27. SAGE Journals 1999-2009
    28. Erdös 96
    29. Einstein 130
    30. SAGE Education Journals
    31. Recursos para Teoría de la Computación
    32. Recursos para Cálculo Univariable
    33. La docena del fraile de planeación específica
    34. Competencias
    35. Felices Fiestas
    36. Pláticas sobre Teoría de Números
    37. Las Cinco Mentes para el Futuro
    38. Cursos estilo OCW
    39. SAGE Journals Free Access
    40. XLI Congreso Nacional de la SMM
    41. 15a Semana Nacional de CyT
    42. Página de áreas matemáticas y afines
    43. Numerical Recipes en Open Access
    44. SAGE Journals Online
    45. ¿Por qué las matemáticas?
    46. Libros en PDF del Profesor Carlos Ivorra
    47. 1ra. Escuela de Geometría Algebraica y Sistemas Dinámicos
    48. Frase de Kurt Friedrichs
    49. Recursos en Video
    50. Joint Mathematics Meetings 2008
    51. Decálogo del Dr. Pedro Puig Adam
    52. Un pensamiento de Sydney J. Harris
    53. nota de Serge Lang
    54. un pensamiento de Albert Einstein
    55. Los diez mandamientos de matemáticas
    56. Los diez mandamientos del maestro de matemáticas
    57. Página de recursos selectos
    58. Página Aprendizaje+Fluir+Felicidad
    59. Mensaje SEP Josefina Vázquez Mota
    60. Bienvenidos

  2. Categories

    Archives


  3. Search Website