cematî.com (math as poetry)

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*])

• Enderton, Herbert B. (2006) Computability Theory . Preliminary draft [acc. 2010.02.17]
• Grunschlag, Zeph. (2005) Computability Lecture Notes: { Soda Vending Machine (3-14)}. Columbia University [acc. 2009.08.26]
• Kleinberg, Jon, Christos Papadimitriou. “Computability and Complexity“, NAP, 2004. [acc. 2008.09.01]
• Morales-Luna, Guillermo. “Computabilidad y Complejidad“. Depto. de Computación. CINVESTAV-IPN. 2008 [acc. 2008.09.04]
• Navarro, Gonzalo. “Fundamentos de las Ciencias de la Computación: (lenguajes formales, computabilidad y complejidad) Apuntes y Ejercicios“. Univ. de Chile, 2008. [acc. 2008.09.04] <— (Apuntes recomendados)
• [W] Automata Theory. Wikipedia [acc. 2008.09.01]

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

• [-] En honor a Woody W. Bledsoe. “Colección de demostraciones en geometría“. (incluye animaciones, basadas en Java) [acc. 2008.09.10]
• [-] (Serie de artículos sobre demostraciones, presentadas en la excelente revista electrónica +plus magazine [acc. 2008.09.10]
  
  • [M] Kona Macphee. “The origins of proof“
  • [F] J. V. Field. “The origins of proof II: Kepler’s proofs“
  • [W] Jon Walthoe. “The origin of proof III: Proof and puzzles through the ages“
  • [H] Robert Hunt. “The origin of proof IV: The philosophy of proof“
• [-] Algunos sitios con demostraciones visuales:
  • Mehalanobis
    
  • [N] Roger B. Nelsen. “Visual Gems of Number Theory“. (Lewis & Clark College). Math Horizons, Noviembre 2007

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

• Kodara, R. (2008 ) The Ackermann Function [acc. 2010.02.22]
• [MR] Águeda Mata y Miguel Reyes. “Temas básicos: el principio de inducción“. Depto. de Matemática Aplicada, FI-UPM. [acc. 2008.09.10]
• [-] “Mathematical Induction“. Cortesía del excelente sitio de divulgación matemática Cut-the-knot. (se le invita a explorar la extensa lista de proposiciones y teoremas que utilizan I.M. en su demostración)

2. Lenguajes Regulares

• [2.4] Lenguajes no regulares
  • [ADU] The Pumping Lema (video) [acc. 2009.10.16]
• [2.A] Aplicaciones selectas
  • Gunter, E. L., Muscholl, A., Peled, D. (2002) Compositional Message Sequence Charts (PS, 12 pp.) [Protocolos de comunicación] [acc. 2009.09.04]

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]
  
  • [L] “Transforming a Grammar to Chomsky Form“. LARA: Laboratory for Automated Reasoning and Analysis.
  • [P] Prof. T. K. Prasad. “Normal Forms” (notas en PPT)
  • [RR] Edgar Ruiz L., Eduardo Raffo L. “Conversión de un AFN a un AFD“. Industrial Data, Vol. 6 No. 1 (pp. 61-70), Agosto 2003 [Ref. cortesía de Juárez]
    
• [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

• [Yt] Julia Robinson and Hilbert’s Tenth Problem (Video Trailer en Youtube). 2008 [acc. 2008.09.05]
• Davis, Martin (1973). Hilbert’s tenth problem is unsolvable. The American Mathematical Monthly, Vol. 80, No. 3, pp.  233-269 (ver también PDF en MathDL) [acc. 2010.05.12]

[A*] Cursos selectos

• [ADUni] Theory of Computation
• [MIT] 18-404. Theory of Computation
• [Trinity] Great Ideas in Computer Science [acc. 2009.05.28]

[B*] Bibliografía recomendada

• Brena, Ramón. “Autómatas y Lenguajes: un enfoque de diseño“, Tec. de Monterrey, 2003. [acc. 2008.09.04] <— (Libro suplementario)
• Campos, Álvaro E. (1995) “Teoría de Autómatas y Lenguajes Formales“. Pontificia Universidad Católica de Chile. [acc. 2009.04.28]
• Cooper, S. B. (2004) Computability Theory [GB]. Chapman & Hall / CRC Mathematics. [acc. 2010.02.17]
• Enderton, H. B. (2009) Computability Theory Notes (capítulos en PDF) [acc. 2010.02.17]
• Hopcroft, John E., Rajeev Motwani, Jeffrey D. Ullman. “Introducción a la Teoría de Autómatas, Lenguajes y Computación” (2/ed.) Addison-Wesley, 2002. { Link: Solución a los problemas con asterisco * } <— (Libro de Texto)
• [M-L] Guillermo Morales-Luna, “Principios de Autómatas Finitos“. Sección de Computación, CINVESTAV-IPN, Junio 27, 2000
• Navarrete, Isabel, et al. (2008) “Teoría de Autómatas y Lenguajes Formales“. Universidad de Murcia. Septiembre 2008. [acc. 2009.02.09]
• Uzcátegui-Aylwin, C. (2009) Lógica, Conjuntos y Números. Departamento de Matemáticas, Facultad de Ciencias, Univ. de los Andes. [acc. 2009.09.02]

[C*] Herramientas software recomendadas

• BFC Automata [acc. 2008.10.07]
• Chalchalero (Proyecto SEPa!) { editor de diagramas | graphviz (ver dotguide) } [acc. 2008.11.10] Notas: [2009.04.01: Links inactivos para descargas en Proyecto SEPa!]
• JFLAP ( archivos JFF en la página tutorial ) Nota: Requiere Java SE Runtime Environment (JRE) [acc. 2008.10.07; 2009.04.01]
• ♦VTuring v1.0 (freeware de Cristian Cheran) [add. 2009.12.03]

[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 []
  
• 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)
• Exámenes prototipo: (2009-1:  unid-1 | unid-2 | unid-3 | 4 | 5 | 6)
• 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) }
• Cuestionario sobre Decidibilidad y Reducibilidad [Ref. 2009-1] (Ref. Cap. 9 Libro de HMU). [add. 2009.06.08]
• [Ref] artículo de Martin Davis “Hilbert’s tenth problem is unsolvable.

(Desde: 2008.08.28)