Teoría de la Computación

• Esta sección

  Información que debes conocer

  COMPETENCIAS TRANSVERSALES/GENÉRICAS

  1. - Desarrolla capacidad de análisis y síntesis para abordar los problemas.
  2. - Construye soluciones a los problemas utilizando el nivel de abstracción de los formalismos matemáticos para cada tipos de lenguajes
  3. - Realiza razonamiento crítico
  4. - Toma decisiones para determinar la mejor forma de resolver un problema.
  5. - Coopera para el trabajo en equipo.
  6. - Comunica de forma escrita la explicación y justificación de los modelos empleados
  7. - Diseña automatización de procesos

  COMPETENCIAS GENERALES:

  1. - Diseña,  desarrolla  y  aplica  modelos  computacionales  para  solucionar  problemas,  mediante la selección y uso de herramientas matemáticas.
  2. - Implementa  aplicaciones  computacionales  para  solucionar  problemas  de  diversos  contextos, integrando diferentes tecnologías, plataformas o dispositivos.

  INDICADORES:

  1. - Conoce los conceptos fundamentales de lenguajes, sus propiedades, su jerarquía y su relación natural con los lenguajes de programación.
  2. - Evalúa cómo debe abordar un problema de reconocimiento de palabras.
  3. - Utiliza diferentes tipos de modelos matemáticos (autómatas finitos, expresiones regulares, autómatas de pila, gramáticas generativas y máquinas de Turing) para reconocer y generar lenguajes de distinta complejidad.
  4. - Diseña e implanta, en un lenguaje de programación de alto nivel, soluciones de problemas de mediana complejidad utilizando los modelos de reconocimiento y generación de lenguajes formales..
  5. - Valora la eficiencia de un autómata determinado para el reconocimiento de un lenguaje concreto (valorar si el autómata es mínimo, sus equivalencias a otros modelos).
  6. - Transforma enunciados informales de un problemas a enunciados formales en términos de los modelos de la Teoría de la Computación.
  7. - Considera la calidad y la cantidad de los recursos que utiliza el modelo solución según el  tipo de problema
  8. - Reconoce los distintos tipos jerárquico de lenguajes en los problemas que tienen solución.
  9. - Comprende la correspondencia entre gramáticas, lenguajes y máquinas reconocedoras de cada tipo de Lenguaje.
  10. - Comprende las limitaciones de los computadores y sus capacidades.
  11. - Usa estándares de desarrollo para  la implementación de soluciones.

  • Programa del curso Teoría de la Computación
    

  • Plan de Evaluación Teoría de la Computación B2018
    

  • Herramientas:

    • JFLAP 5.0
    • JFLAP 6.2
    • JFLAP 8 beta
• Tema 0: Introducción

  El objetivo de este tema es describir e identificar la historia, importancia y origen de la Teoría de la Computación, así como los elementos que conforman la especificación de un lenguaje: símbolo, alfabeto, cadenas o palabra, lenguaje y problema.

  • 

  • Comprende el origen de las bases matemáticas de la Teoría de la Computación y los conceptos básicos que utiliza.

    Indicadores:

    • Reflexiona sobre el origen de la Teoría de la Computación y su importancia
    • Aprecia el aporte de los investigadores en el área para construir la Teoría.
    • Conoce la jerarquía de Chomsky sobre Lenguajes.
    • Repasa los conceptos de conjuntos, relaciones, árboles, recursividad, entre otros.
    • Obtiene un alfabeto a partir de un lenguaje.
    • Define los símbolos, alfabetos, cadenas o palabras, lenguajes y problema en varios problemas de dominios de aplicación conocidos.

     

  • 

  • • Apuntes Tema 0: Introducción y conceptos preliminares
    • Presentación Tema 0: Introducción a Teoría de la Computación
    • Presentación Tema 0: Conceptos preliminares
    • Video Tema 0: Introducción a Teoría de la Computación
    • Video Tema 0: Conceptos preliminares
  • 

  • • Ejercicios propuestos del Tema 0
• Tema 1: Autómatas de Estados Finitos

  El objetivo de este tema es dar a conocer el modelo matemático de los Autómatas Finitos aplicados a los lenguajes regulares, los cuales representan a los lenguajes más simples de la Jerarquía de Chomsky y por tanto es el modelo básico de todas las máquinas reconocedoras

  • 

  • Crea, diseña, reconoce y programa Autómatas de Estados Finitos (AF) en un lenguaje de programación para la solución de un problema.

    Indicadores:

    • Identifica la notación formal de un autómata finito.
    • Diseña, especifica y ejecuta una máquina de estados finitos (AF).
    • Expresa el AF en diagrama de estados, tabla de transiciones y función de transición, comprendiendo sus equivalencias.
    • Conoce la diferencia entre un Autómata Finito No Determinista (AFND) y un Autómata Finito Determinista (AFD).
    • Identifica las características de cada tipos de AF y sus equivalencias.
    • Define el lenguaje reconocido por cada tipo de AF.
    • Implementa un AF usando el paradigma de la programación basada en Autómatas.
  • 

  • • Apuntes Tema 1: Autómatas de Estados Finitos
    • Presentación Tema 1: Autómatas de Estados Finitos
    • Archivos JFLAP del Tema 1
    • Tutorial: Programación Orientada a Autómata (Wikipedia)
    • Video Tema 1: Autómatas de Estados Finitos

  • 

  • • Ejercicios propuestos del Tema 1
  • 

  • Actividad evaluada Tema 1: Diseño e implementación de un AF Tarea
• Tema 2: Expresiones Regulares y Autómatas con Salida

  El objetivo de este tema es dar a conocer dos modelos matemáticos aplicados a los lenguajes regulares que son muy particulares: (1) Las Expresiones Regulares que son modelos declarativos del lenguajes regulares muy utilizados y con equivalente formal a los demás modelos de este tipo de lenguajes (2) Los Autómatas con Salidas que son autómatas finitos con la posibilidad adicional de generar salidas dependiendo del problema, extendiendo y dando valor agregado al modelo básico de reconocimiento haciendo mas útil su aplicación.

  • 

  • • Crea, reconoce y utiliza Expresiones Regulares para solucionar problemas del entorno en diferentes escenarios tecnológicos
    • Diseña, reconoce y programa Autómatas con Salida para solucionar problemas del entorno.

    Indicadores:

    • Aplica las expresiones regulares y sus operaciones.
    • Genera cadenas a partir de una expresión regular.
    • Obtiene una expresión regular a partir de un grupo de cadenas o viceversa.
    • Define una expresión regular ER para un lenguaje regular
    • Establece relación entre los modelos sobre lenguajes regulares: una expresión regular ER y un autómata finito AF
    • Comprende el uso y aplicación de las expresiones regulares en problemas de la vida real
    • Implementa las Expresiones Regulares en el POSIX (Portable Operating System Interface) de Linux
    • Diseña, especifica y ejecuta autómatas con salidas
    • Identificar ejemplos de problemas que pueden resolverse usando los autómatas con salidas
    • Comprende y reconoce a los Autómata de Moore y Autómata de Mealy
    • Construye la equivalencia entre una Máquina de Moore y una Máquina de Mealy
    • Implementa un Autómata con Salidas para un problema dado.
  • 

  • • Apuntes Tema 2: Expresiones Regulares y Autómatas con Salida
    • Presentación Tema 2 - Sesión 1: Expresiones Regulares
    • Presentación Tema 2 - Sesión 2: Autómatas con Salida
    • Archivos JFLAP del Tema 2
    • Video Tema 2 - sesión 1: Expresiones Regulares (parte 1)
    • Video Tema 2 - sesión 1: Expresiones Regulares (parte 2)
    • Video Tema 2 - sesión 2: Autómatas con Salida
    • Website Regular-Expressions.info
  • 

  • • Ejercicios propuestos del Tema 2
  • 

  • Actividad evaluada Tema 2: Diseño e Implementación de un Autómata con Salida Tarea
• Tema 3: Propiedades de los Lenguajes Regulares

  El objetivo de este tema es aportar herramientas que permitan identificar dentro de los problemas conocidos dónde existen lenguajes regulares para poder aplicar sus modelos de reconocimiento AF, y declaración ER. En otras palabras, saber identificar lenguajes regulares de los problemas comunes pero que desconocía su abstracción como lenguaje para optar por otra forma de solución.

  • 

  • Utiliza las diferentes propiedades de los lenguajes regulares para caracterizar, describir y discriminar este tipo de lenguaje formal que está presente en diversos problemas reales.

    Indicadores:

    • Aplica el Lema del Bombeo o Sondeo (Pumping Lemma) para demostrar que un lenguaje no es regular
    • Distingue, reconoce, calcula y aplica las operaciones cerradas sobre lenguajes regulares
    • Comprende, identifica y resuelve los problemas decidibles para este tipo de lenguajes
    • Aplica el Algoritmo de Minimización de Autómatas Finitos
  • 

  • • Apuntes Tema 3: Propiedades y algoritmos de los Lenguajes Regulares
    • Presentación Tema 3: Propiedades y algoritmos de los Lenguajes Regulares
    • Archivos JFLAP del Tema 3
    • Video Tema 3: Propiedades de los Lenguajes Regulares
  • 

  • • Ejercicios propuestos del Tema 3
  • 

  • • Actividad evaluada Tema 3: Implementación de un tokenizador con Lex de linux
• Tema 4: Gramáticas Generativas

  En este tema se tiene como objetivos entender y obtener un conocimiento profundo de los modelos generativos de la Teoría de los Lenguajes Formales presentando todas las formas de utilización de una gramática. Representa el tema mas importante, útil y con mayor aplicación en el desarrollo, modelado y programación de sistemas.

  • 

  • Conoce, construye y utiliza convenientemente Gramáticas Libres de Contexto para resolver problemas.

    Indicadores:

    • Identifica la notación formal de una gramática generativa enumerando sus elementos
    • Discrimina los distintos tipos de Gramáticas Generativas de la jerarquía de Chomsky: Gramática Regular (GR), Gramática Libre de Contexto (GLC), Gramáticas Sensibles al Contexto (GSC), Gramáticas Irrestrictas (GI)
    • Establece la equivalencia entre una GR y un AF
    • Genera cadenas de un Lenguaje a partir de una gramática
    • Obtiene una GLC ante la descripción de un Lenguaje
    • Aplica procedimientos para simplificar cualquier GLC
    • Transforma cualquier gramática libre de contexto a las formas normales de Chomsky y/o de Greibach.
    • Identifica la ambigüedad en una gramática y sus consecuencias en el reconocimiento de lenguajes.
    • Reconoce la importancia del mecanismo de parsing en las Gramáticas Generativas
    • Reconoce la ambigüedad de una gramática
  • 

  • • Apuntes Tema 4: Gramáticas Libres de Contexto
    • Presentación Tema 4: Gramáticas Regulares
    • Presentación tema 4: Gramáticas Libres de Contexto
    • Archivos JFLAP y Prolog del Tema 4
    • Sitio Web de Swi-Prolog
    • Video Tema 4: Gramáticas Regulares
    • Video Tema 4: Gramáticas Libres de Contexto
  • 

  • • Ejercicios propuestos del Tema 4
  • 

  • • Actividad evaluada Tema 4: Gramática Libre de Contexto en JFLAP y Prolog
• Tema 5: Autómatas de Pila

  Este tema tiene como objetivo presentar la extensión de una Autómata Finito utilizando una memoria (estructura de datos Pila) permitiéndole reconocer cadenas de lenguajes mas complejos como los Lenguajes Libres de Contexto. El Autómata de Pila (AP) es la máquina reconocedora de los lenguajes tipo 2 con sus equivalencias en GLC.

  • 

  • Conoce, construye y utiliza convenientemente Autómatas de Pila para realizar reconocimiento de lenguajes en diversos problemas.

    Indicadores:

    • Identifica características y componentes de un Autómata de Pila (AP)
    • Ejecuta un AP para reconocer Lenguajes
    • Diferencia los dos tipos de AP: por Pila Vacía y por Estado Final
    • Aplica y ejecuta los procedimientos para obtener equivalencia entre AP y GLC
    • Considera la importancia de los AP Deterministas
    • Obtiene AP equivalentes desde una AP de Pila Vacía a un AP por Estado Final y viceversa
    • Reconoce un AP No determinista y ejecuta las secuencia de descripciones instantáneas
  • 

  • • Presentación Tema 5: Autómatas de Pila
    • Archivos JFLAP del Tema 5
  • 

  • • Ejercicios propuestos del Tema 5
  • 

  • • Actividad evaluada Tema 5: Autómata de Pila en JFLAP
• Tema 6: Propiedades de los Lenguajes Libres de Contexto

  El objetivo de este tema es aportar herramientas que permitan identificar dentro de los problemas conocidos dónde existen Lenguajes Libres de Contexto para poder aplicar sus modelos generativos GLC y de reconocimiento AP. En otras palabras, saber identificar lenguajes libres de contexto dentro de los problemas del entorno, haciendo énfasis en el problema típicos como la Compilación en un lenguajes de programación, o de la interpretación en un lenguaje de marcado.

  • 

  • Utiliza las diferentes propiedades de los Lenguajes Libres de Contexto para caracterizar, describir y discriminar este tipo de lenguaje formal que está presente en diversos problemas frecuentes en computación

    Indicadores:

    • Aplica la herramienta del Lema del Bombeo para demostrar que un lenguaje no es libre de contexto (LLC)
    • Distingue las operaciones cerradas sobre LLC y reconoce su importancia
    • Identifica y resuelve los problemas decidibles para LLC. Descartando los no decidibles.
    • Ejecuta un algoritmo para decidir la pertinencia en LLC, denominado parser (CYK), comprendiendo sus entradas, procedimiento y salidas
  • 

  • • Presentación Tema 6: Propiedades de los Lenguajes Libres de Contexto
    • Video Tema 6: Propiedades de los Lenguajes Libres de Contexto - (Video local MP4)
  • 

  • • Ejercicios propuestos del Tema 6
    • Presentación del Taller básico de XML - [Archivos del taller XML] - (Video local de la Introducción del taller XML)
  • 

  • • Actividad evaluada Tema 6: Validar un archivo XML
• Tema 7: Máquinas de Turing

  Este tema tiene como objetivo conocer los fundamentos y el funcionamiento de la máquina de Turing y los distintos tipos de máquinas de Turing.

  • 

  • Diseña, construye y ejecuta una Maquina de Turing (MT), para el reconocimiento de cadenas propias de lenguajes.

    Indicadores:

    • Identifica la notación formal de una MT.
    • Describe los componentes del modelo básico y de las extensiones de la Máquina de Turing (MT)
    • Comprende y utiliza las técnicas de programación de Máquina de Turing (MT)
    • Construye, diseña y ejecuta una MT para reconocer un lenguaje
    • Ejecuta formalmente una MT realizando pasos de computación generando descripciones instantáneas.
    • Relaciona la MT con el tipo de lenguaje recursivamente enumerables
    • Construye MT para calcular operaciones algebraicas y enumerar lenguajes
    • Conoce las propiedades de los lenguajes reconocidos por una MT
    • Diferencia las Gramáticas sensibles al contexto de las Gramáticas sin restricciones
  • 

  • • Presentación Tema 7: Máquinas de Turing
    • Archivos JFLAP del Tema 7
    • Video Tema 7: Máquinas de Turing
  • 

  • • Ejercicios propuestos del Tema 7
  • 

  • • Actividad evaluada Tema 7: Máquina de Turing en JFLAP