Teoría de la Computación

Semestre:

7°

Fecha de elaboración:

Agosto de 2013

Fecha de revisión:

Septiembre de 2013

Elaborado por:

Nodari Vakhania Maizuradse, Antonio Daniel Rivera López

Ciclo de formación:

Profesional

Área curricular:

Ciencias de la Disciplina

Tipo de unidad:

Teórica

Carácter de unidad:

Obligatoria

Clave:

TM01FP050010

Créditos:

10

Semestre:

7°

Horas Teoría:

5

Horas Práctica:

0

Programas académicos en los que se imparte:

Licenciatura en Ciencias Áreas terminales en Matemáticas, Física, Bioquímica y Biología Molecular, y Ciencias Computacionales y Computación Científica

Prerrequisitos:

Comprende y utiliza las herramientas básicas de análisis de algoritmos.

Antecedentes Recomendadas:

Ninguna

Consecuentes Recomendadas:

  • Ninguna

Presentación de la unidad de aprendizaje:

Se estudian los fundamentos teóricos de las ciencias de la computación. Para saber si un problema se puede resolver o no con una computadora, es necesario formalizar el concepto de algoritmo e introducir un modelo teórico de las computadoras. El estudio de estas máquinas nos ayuda formalizar el proceso y concepto de cómputo y nos va a permitir tener mas idea de lo que se puede calcular, en qué tiempo y qué no se puede calcular en las computadoras. Clasificamos los problemas/lenguajes en decidibles, no-decidibles, reconocibles y no-reconocibles. Los problemas decidibles son los que se pueden resolver en las computadoras, los reconocibles se pueden resolver en condiciones favorables, pero no son resolubles en general. Y los problemas no-reconocibles son todavía mucho más complicados que los problemas reconocibles. En esta unidad de aprendizaje se estudiará la técnica llamada de reducción. Informalmente, un problema/lenguaje se reduce a otro si el primero se puede resolver teniendo la solución del segundo.

Propósito de la unidad de aprendizaje:

Profundizar en los fundamentos teóricos de las ciencias de la computación, comprender los modelos matemáticos de las computadoras y aprender a clasificar los problemas/lenguajes en decidibles, no-decidibles, reconocibles y no-reconocibles.

Competencias profesionales:

Contribución al perfil de egreso:

Secuencia temática:

  1. I Lenguajes regulares y autómatas finitos.
    1. Introducción a la computabilidad.
    2. Gramáticas y lenguajes. Gramáticas regulares.
    3. Autómatas finitos deterministas, con y sin salidas, reconocedores. Autómatas finitos no-deterministas y la equivalencia de autómatas deterministas y no-deterministas.
    4. Expresiones regulares, cerradura sobre expresiones regulares. La equivalencia entre los autómatas de estado finito y expresiones regulares.
    5. Lenguajes no-regulares.
  2. II Lenguajes libres del contexto y autómatas con pila.
    1. La definición de un lenguaje libre del contexto y ejemplos de estos lenguajes. Construcción de lenguajes libres del contexto.
    2. La reducción a la forma normal de Chomsky.
    3. La definición formal de autómatas con pila (pushdown automation) y ejemplos.
    4. Equivalencia entre los lenguajes de libres del contexto y autómatas con pila.
    5. Lenguajes que no son de libres del contexto, lema de bombeo para los lenguajes de libres del contexto.
  3. III Modelo general de computación y la hipótesis de Church-Turing.
    1. Tesis de Church y Turing.
    2. Máquinas de Turing. Lenguajes decidibles y reconocibles. Variaciones de máquinas de Turing con multi-cinta. Máquinas de Turing no deterministas. Equivalencia de las máquinas de Turing deterministas y no-deterministas. Equivalencia de las máquinas de Turing con otros modelos de computación.
    3. Noción de algoritmo.
  4. IV Decidibilidad.
    1. Lenguajes decidibles: lenguajes decidibles del campo de conjuntos regulares, autómatas finitas, lenguajes libres de contexto y autómatas con pila.
    2. Problemas no-decidibles. Problema de parada de una máquina de Turing, el método de diagonalización. Lenguajes no-reconocibles.
  5. V Reducibilidad.
    1. El método de reducción para demostrar que un lenguaje es o no decidible.
    2. Problemas no-decidibles de teoría de lenguajes.
    3. El problema de post-correspondencia.
    4. La definición formal de reducibilidad. Reducibilidad por mapeo, funciones computables.

Criterios de Evaluación:

Bibliografía básica:

  • Sipser, M. 1997. Introduction to theory of computation. Ed. PWS Publishing Company.
  • Cooper, S. 2004. Computability theory. Ed. Chapman & Hall/CRC.
  • Garey, M. y Johnson, D. 1979. Computers and intractabililty: a guide to theory of NP-completeness. Ed. Freeman and Company.

Bibliografía complementaria:

  • Boolos, G. y Jeffrey, R. Computability and logic. Ed. Cambridge University Press.
  • Hopcroft, J., Motwani, R. y Ullman, J. 2000. Introducción a la teoría de autómatas, lenguajes y computación. Ed. Prentice-Hall.
  • Hopcroft, J., Motwani, R. y Ullman, J. Teoría de autómatas, lenguajes y computación. 3a edición. Ed. Pearson.