PONTIFICIA UNIVERSIDAD CATOLICA DEL ECUADOR FACULTAD DE INGENIERIA ESCUELA DE INGENIERIA DE SISTEMAS 1. DATOS INFORMATIVOS MATERIA: DISEÑO DE LENGUAJES Y AUTOMATAS: CARRERA: INGENIERÍA DE SISTEMAS NIVEL: 4 No. CREDITOS: 4 PROFESOR: ING. ALBERTO PAZMIÑO PROAÑO SEMESTRE ACADEMICO: Segundo 2007 – 2008
2. DESCRIPCION DEL CURSO Es un primer curso dentro del campo de la teoría de la computación, en el que se presentan los modelos computacionales básicos asociados con el tratamiento de lenguajes categorizados por Chomsky: lenguajes regulares, lenguajes independientes del contexto y lenguajes estructurados por frases y sus respectivas máquinas teóricas: Autómatas finitos, autómatas con pila (pushdown automata), y máquinas de Turing. Se estudian igualmente las gramáticas asociadas a cada tipo de lenguaje. 3. OBJETIVOS Al terminar el curso el estudiante comprenderá los fundamentos teóricos de la ciencia de la computación, y los diferentes modelos y enfoques básicos para la definición y el tratamiento de los lenguajes formales en los cuales se basa la teoría de la computabilidad y complejidad algorítmica. Los estudiantes alcanzarán una clara comprensión de los procesos subyacentes en los analizadores léxicos y sintácticos, reforzarán sus habilidades para el diseño de soluciones computacionales simples y eficientes. 4. CONTENIDOS Semana 1: Del 18 al 22 de febrero Capítulo 0: PRELIMINARES
-
Encuadre del tema y aspectos logísticos del curso Repaso de la teoría de conjuntos Concepto de relación, función Lenguajes Formales: Definiciones básicas: Símbolo, alfabeto, lenguaje, lenguaje universal
-
Análisis léxico Ejercicios de aplicación Semana 2: Del 25 al 29 de febrero Capítulo 1: AUTOMATAS FINITOS Y LENGUAJES REGULARES
-
Diagramas de transiciones: estados y transiciones Tablas de transiciones Análisis de casos y ejercicios aplicativos pág. 27 Autómatas finitos deterministas (AFD): definiciones, AFD: formalización. La función de transición Casos y ejercicios Semana 3: Del 3 al 7 de marzo
-
Limitaciones de los AFD Un lenguaje que no es regular. Teorema 1.1 El lema de bombeo. Teorema 1.2 Análisis de casos y ejercicios aplicativos Semana 4: del 10 al 14 de marzo
-
Autómatas finitos no deterministas Gramáticas regulares Casos y ejercicios aplicativos Semana 5: del 17 al 21 de marzo (20 y 21 vacaciones s.s)
-
Expresiones regulares Expresiones, gramáticas y lenguajes regulares y autómatas finitos Ejercicios aplicativos Semana 6 : del 24 al 28 de marzo (lunes 24 vacación) [1er. Examen]
-
Repaso del Capítulo previo al examen Semana 7: del 31 de marzo al 4 de abril Capítulo 2: AUTOMATAS DE PILA (AP) y LENGUAJES INDEPENDIENTES DEL CONTEXTO (LIC)
-
Autómatas de pila, definición y generalidades Autómatas que vacían la pila Casos y ejercicios aplicativos Semana 8: del 7 al 11 de abril
-
Revisión 1er examen Gramáticas independientes del contexto Equivalencia de modelos AF GIC Forma normal de Chomsky Semana 9: del 14 al 18 de abril
-
Limitaciones de los autómatas de pila El lema de bombeo Un lenguaje que no es independiente del contexto Semana 10: del 21 al 25 de abril
-
El determinismo en los AP Ejercicios aplicativos Problemas de repaso Semana 11: del 28 de abril al 2 de mayo (jueves 1 vacación)
-
Autómatas de Pila y Gramáticas Ind. Del contexto Casos prácticos Ejercicios aplicativos Semana 12: del 5 al 9 de mayo [2do. Examen Cap. 2]
-
Revisión de los temas del capítulo previa al 2do. examen Semana 13: del 12 al 16 de mayo Capítulo 3: MAQUINAS DE TURING
-
Definición y propiedades básicas de las MT Los orígenes de las MT Máquinas de Turing básicas Semana 14: del 19 al 23 de mayo
-
Construcción modular de MT Combinación de MT Bloques básicos de construcción de MT Semana 15: del 26 al 30 de mayo
-
MT como aceptadores de lenguajes Procedimientos de evaluación de cadenas Máquina que genera un lenguaje enumerable recursivamente Máquina que suma 1 a una cantidad binaria El simulador Visual Turing de Cheran
-
Planteamiento de Proyecto de fin de curso Semana 16: del 2 al 6 de junio LABORATORIO
-
Máquina que copia una cadena. Máquina que borra una cadena Máquina Shift Left Semana 17: del 9 al 13 de junio LABORATORIO
-
Comparación de cadenas en alfabeto unario Máquina de Turing que invierte una cadena binaria M de T que halla el bit de paridad deuna cantidad binaria Máquina de Turing que ordena una cadena en binario Semana 18: del 16 al 20 de junio
-
Entrega y revisión del proyecto de fin de curso Tercer examen
5. METODOLOGIA, RECURSOS Se exponen los principios fundamentales de cada tema y se plantean cuestiones y problemas básicos para el desarrollo y comprensión de los estudiantes, en los cuales lo que deben hacer es aplicar y extrapolar los conceptos subyacentes para llegar a generalizaciones universales. Se promoverá el trabajo en grupo y la investigación de simuladores de los diferentes tipos de máquinas, así como el tema de analizadores sintácticos, acerca de los cuales los estudiantes realizarán exposiciones. Se promoverá y evaluará la participación de los estudiantes. Al final del semestre se estudiarán en el laboratorio implementaciones de modelos computacionales basados en máquinas de Turing mediante el uso de simuladores como Visual Turing. Se entregará a los estudiantes el simulador de máquinas de Turing Visual Turing de Cheran Software, versión freeware, para que desarrollen casos prácticos. 6. EVALUACION La evaluación bimestral comprende:
Trabajos y deberes: 50% Examen de fin de bimestre: 50% Participación creativa en clase: 0,2 por cada participación con un máximo de 1.0 (5 participaciones) por bimestre. Los dos primeros bimestres se evalúan sobre 15 puntos, el tercero sobre 20 para obtener una nota final sobre 50 puntos. 6.1
CRONOGRAMA DE EVALUACIONES
PRIMER EXAMEN, SOBRE CAPITULO 1
Cuarto 1: miércoles 26 de marzo-08 Cuarto 2: viernes 26 de marzo-08 SEGUNDO EXAMEN, SOBRE CAPITULO 2
Cuarto 1: miércoles 7 de mayo-08 Cuarto 2: viernes 9 de mayo-08 TERCER EXAMEN, SOBRE CAPÍTULO 3
Cuarto 1: miércoles 18 de junio-08 Cuarto 2: viernes 20 de junio-08 7. BIBLIOGRAFIA: Textos de referencia:
Brookshear J. Glenn. Teoría de la Computación: Lenguajes Formales, Autómatas y Complejidad. Sipser, Michael. Introduction to the Theory of Computation, PWS Publishing Company, 1997 Textos recomendados:
Hopcroft & Ullman. Introducción a la Teoría de Automatas , Lenguajes y Computación. (001.602/H77i) Kelly, Dean. Teoría de Autómatas y Lenguajes Formales, Prentice Hall, madrid (001.62/K287t) Internet: Varios sitios de diferentes universidades, que se darán a conocer actualizados en el transcurso del semestre. El sitio para descargar el simulador de Visual Turing es www.visualturing.com/ 8. DATOS DEL PROFESOR Horario de atención: Lunes de 7 a 9 am; de lunes a viernes de 17:30 a 19:30 Lugar: Cubículo no. 11 Dirección electrónica:
[email protected] Teléfono: ofi. 223 16 12 / cel. 09 902 44 46
Aprobado: Por el Consejo de Escuela
_____________________ f) Director de Escuela
fecha: ________________
Por el Consejo de Facultad:
______________________ f) Decano
fecha: ________________