Syllabus Del Curso Automatas Lenguajes Formales.docx

Universidad Nacional Abierta y a Distancia Vicerrectoría Académica y de Investigación Formato de syllabus de curso 1. IDENTIFICACIÓN DE CURSO Escuela o unidad: Escuela de Ciencias Básicas, Tecnología e Ingeniería Nivel: Profesional Curso: Autómatas y lenguajes formales Tipología de curso: Teórico Diseñador de curso: Ángela María González Amarillo Fecha de elaboración: 15 de Noviembre de 2016

Sigla: ECBTI Campo de formación: Formación disciplinar Código: 301405 N° de créditos: 3 Actualizador de curso: Ángela María González Amarillo Fecha de actualización: 15 de Noviembre de 2018

Descripción del curso: El curso de Autómatas y lenguajes formales hace parte del campo de formación profesional específico del programa de Ingeniería de Sistemas y afines que oferta la UNAD (Universidad Nacional Abierta y a Distancia) y corresponde a la red curricular de programación y algoritmia. El curso se ocupa del estudio de las máquinas de estados finitos que se utilizan como reconocedores de lenguajes. El tipo de curso es teórico y se ha estructurado en tres (3) unidades que corresponden a 3 créditos académicos, la primera unidad está orientada a lenguajes regulares y sus máquinas, aborda conceptos y mecanismos fundamentales para la definición de lenguajes, expresiones regulares, autómatas y sus tipos y gramáticas regulares, la segunda unidad aborda los lenguajes independientes del contexto y sus máquinas, aquí se estudian las propiedades fundamentales de los autómatas a pila y los lenguajes que estos definen y la tercera unidad maneja los lenguajes estructurados por frases, se abordan las máquinas de Turing los cuales son fundamentales para el estudio de la computabilidad y complejidad de problemas De acuerdo con el mapa curricular del programa de Ingeniería de Sistemas, el curso de Autómatas y lenguajes formales, es un curso avanzado donde se recomienda que el estudiante tenga las competencias de los cursos de programación y lógica matemática.

2. INTENCIONALIDADES FORMATIVAS Propósitos de formación del curso: Proporcionar los conocimientos de la teoría clásica de la computación mediante el estudio de modelos matemáticos en máquinas de estados finitos asociándolo a contextos reales, con el fin de valorar diferentes formas de resolución de problemas y hacer uso ingenieril para la toma de decisiones. Competencias del curso: El estudiante conoce los distintos tipos de autómatas, gramáticas y lenguajes que reconocen con el fin de comprender y resolver diferentes tipos de problemas. El estudiante construye gramáticas y autómatas mediante los mecanismos de representación formal de los diferentes autómatas, comprendiendo el tipo de problemas que cada uno puede resolver. El estudiante asocia las aplicaciones de los autómatas llevados a contextos reales y a problemas computacionales. 3. CONTENIDOS DEL CURSO Unidades/te mas 1. UNIDAD 1: Lenguajes Regulares y sus máquinas Lenguajes Regulares Autómatas Finitos Expresiones Regulares

Recursos educativos requeridos Carrasco, R., Calera, R., Forcada, M. (2016). Teoría De Lenguajes, Gramáticas Y Autómatas Para Informáticos. (pp. 127 - 142). Recuperado de http://bibliotecavirtual.unad.edu.co:2051/login.aspx?direct=true&d b=nlebk&AN=318032&lang=es&site=edslive&ebv=EB&ppid=pp_Cov er Hernández, R. (2010). Practique la teoría de autómatas y lenguajes formales. (pp. 1 124). Recuperado de http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action? docID=10566114&ppg=10

Gramáticas Regulares

Alfonseca, C., Alfonseca, M., Mariyón, S. (2009). Teoría de autómatas y lenguajes formales. (pp. 71 - 115). Recuperado de http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action? docID=10498456&ppg=6 Millán, J., Antonio J. (2009). Compiladores y procesadores de lenguajes. (pp. 28 62). Recuperado de http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/detail.action?d ocID=10844351 Ferrando, J.C., and Gregori, V. (2012). Matemática discreta (2a. ed.). (pp. 207 232). Recuperado de http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action? ppg=260&docID=10751543&tm=1481476339478 Alemán. H. [Helena]. (2017, Junio 19). Conceptualización de automáta [Archivo de video]. Recuperado de https://www.youtube.com/watch?v=zMhwYlXAHE4&index=6&list=P LYIk_3YB0nVyiNMAdrCPgiv0EoSHZtNto Alemán. H. [Helena]. (2018, mayo 23). Expresión Regular [Archivo de video]. Recuperado de https://youtu.be/65B5QUNHfaM González, A. [Ángela]. (2016, mayo 30). Conversión de Autómata Finito No Determinista a Autómata Finito Determinista [Archivo de video]. Recuperado de https://www.youtube.com/watch?v=29Qp_AWXFt4 González, A. [Ángela]. (2016, mayo 30). Conversión de Autómata Finito No Determinista a Autómata Finito Determinista con transiciones vacías – Método 1. [Archivo de video]. Recuperado de https://www.youtube.com/watch?v=NF47BSorRfU González, A. [Ángela]. (2016, junio 6). Conversión de Autómata Finito No Determinista a Autómata Finito Determinista con

transiciones vacías – Método 2. [Archivo de video]. Recuperado de https://www.youtube.com/watch?v=KhgMam0DMmM González, A. [Ángela]. (2016, junio 6). Conversión de Autómata Finito No Determinista a Autómata Finito Determinista con transiciones vacías – Ejemplo 2. [Archivo de video]. Recuperado de https://www.youtube.com/watch?v=uLOXjZUTYyc OVI - Unidad I – Lenguajes Regulares González, A. [Ángela]. (2018, junio 1). Lenguajes Regulares. [Archivo web]. Recuperado de http://hdl.handle.net/10596/18315 González, A. [Ángela]. (2017, noviembre 5). Autómatas Finitos. [Archivo de video]. Recuperado de http://hdl.handle.net/10596/10470 CK-12, (2015). Operations with Sets. [OVA]. Recuperado de http://www.ck12.org/probability/Operations-with-Sets/plix/LetsRoll-the-Dice56e1fc1f8e0e0813d4b14128/?referrer=concept_details. CK-12, (2015). Operations with Sets Practice. [OVA]. Recuperado de http://www.ck12.org/probability/Operations-withSets/asmtpractice/Operations-with-SetsPractice/?referrer=concept_details 2. Unidad 2 Lenguajes Independiente s del Contexto y sus máquinas

Carrasco, R., Calera, R., Forcada, M. (2016). Teoría De Lenguajes, Gramáticas Y Autómatas Para Informáticos. (pp. 119 - 127). Recuperado de http://bibliotecavirtual.unad.edu.co:2051/login.aspx?direct=true&d b=nlebk&AN=318032&lang=es&site=edslive&ebv=EB&ppid=pp_Cov er

Gramáticas y lenguajes

Hernández, R. (2010). Practique la teoría de autómatas y lenguajes formales. (pp. 1 124). Recuperado de

libres de contexto Autómatas de pila

http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action? docID=10566114&ppg=10 Alfonseca C, E., Alfonseca M, M., Mariyón S, R. (2009). Teoría de autómatas y lenguajes formales. (pp. 249 - 276). Recuperado de http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action? docID=10498456&ppg=6 Millán, J., Antonio J. (2009). Compiladores y procesadores de lenguajes. (pp. 73 126). Recuperado de http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/detail.action?d ocID=10844351 González, A. [Ángela] (2017, mayo 16). Minimización de un autómata. [Archivo de video]. Recuperado de https://www.youtube.com/watch?v=eOynYG8Ibk0&t=9s OVA - Unidad 2 – Lenguajes Independientes del Contexto González, A. [Ángela]. (2018, junio 1). Lenguajes Independientes del Contexto. [Archivo web]. Recuperado de http://hdl.handle.net/10596/18317 CK-12, (2014). Connecting Science and Mathematics to Engineering. [OVI]. Recuperado de http://www.ck12.org/book/Engineering%3AAn-Introduction-for-High-School/section/5.3/

3. Unidad 3 Lenguajes Estructurados por Frases Máquinas de Turing y sus lenguajes

Carrasco, R., Calera, R., Forcada, M. (2016). Teoría De Lenguajes, Gramáticas Y Autómatas Para Informáticos. (pp. 11 - 80). Recuperado de http://bibliotecavirtual.unad.edu.co:2051/login.aspx?direct=true&d b=nlebk&AN=318032&lang=es&site=edslive&ebv=EB&ppid=pp_Cov er Hernández, R. (2010). Practique la teoría de autómatas y lenguajes formales. (pp. 1 -124). Recuperado de

http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action? docID=10566114&ppg=10 Alfonseca C, E., Alfonseca M, M., Mariyón S, R. (2009). Teoría de autómatas y lenguajes formales. (pp. 19 - 65). Recuperado de http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action? docID=10498456&ppg=6 Rosenfeld, D. (2016). Computabilidad, Complejidad computacional y verificación de programas. (pp. 7 - 27). Recuperado de http://bibliotecavirtual.unad.edu.co:2077/lib/unadsp/reader.action? docID=11201616&ppg=12 Bonilla, L. [Luis] (2018, mayo 23). Códigos Convolucionales Tellis y Viterbi. [Archivo de video]. Recuperado de https://www.youtube.com/watch?v=Oe9WEAOLeyc&t=1218s Bonilla, L. [Luis] (2018, mayo 23). Diagrama de árbol. [Archivo de video]. Recuperado de https://www.youtube.com/watch?v=HNS4IQw64Sk Bonilla, L. [Luis] (2018, mayo 23). Diagrama de estados. [Archivo de video]. Recuperado de https://www.youtube.com/watch?v=JTJkNco2tjQ&t=5s Bonilla, L. [Luis] (2018, mayo 23). Diagrama de trellis. [Archivo de video]. Recuperado de https://www.youtube.com/watch?v=21JKzST2ZJY OVA - UNIDAD 3 - Lenguajes Estructurados por Frases González, A. [Ángela]. (2018, junio 1). Lenguajes Estructurados por Frases. [Archivo web]. Recuperado de http://hdl.handle.net/10596/18316

CK-12, (2012). Case History: How Math, Science, and Engineering Led to the First Pocket Radio. [OVI]. Recuperado de http://www.ck12.org/book/Engineering%3A-An-Introduction-forHigh-School/section/5.2/ Recursos educativos adicionales para el curso: Unidad 1: Moral, S., Teoría de Autómatas y Lenguajes Formales, 2006. Universidad de Granada: Departamento de ciencias de la computación. P 118. Unidad 2: Brookshear, G. (1993). Teoría de la Computación, Addison Wesley Iberoamericana. Hopcroft, E., Motwani, R., Ullman, J. (2002). Introducción a la teoría de autómatas, lenguajes y computación. Addison Wesley. Unidad 3: Kelley, D. (1995). Teoría de Autómatas y Lenguajes Formales, Prentice Hall Hispanoamericana. Brookshear, G. (1993). Teoría de la Computación, Addison Wesley Iberoamericana. Hopcroft, E., Motwani, R., Ullman, J. (2002). Introducción a la teoría de autómatas, lenguajes y computación. Addison Wesley. 4. ESTRATEGIA DE APRENDIZAJE Descripción de la estrategia de aprendizaje: Estrategia de aprendizaje basada en problemas (ABP): “El aprendizaje basado en problemas representa una estrategia eficaz y flexible que, a partir de lo que hacen los estudiantes, puede mejorar la calidad de su aprendizaje universitario en aspectos muy diversos”. Así, el ABP ayuda al alumno a desarrollar y a trabajar diversas Competencias”. Dentro de estas competencias tenemos: Resolución de problemas, Toma de decisiones, Trabajo en equipo, Habilidades de comunicación (argumentación

y presentación de la información), Desarrollo de actitudes y valores: precisión, revisión, tolerancia. 5. DISTRIBUCIÓN DE LAS ACTIVIDADES ACADÉMICAS DEL CURSO Semana 1y2

3, 4, 5 y 6

7, 8, 9 y 10 11, 12, 13 y 14 15 y 16

Contenidos a desarrollar Pre saberes.

Actividad a desarrollar según la estrategia de aprendizaje Fase 1: Pre saberes. El estudiante de forma individual realiza una contextualización técnica y operativa de los componentes computacionales de un autómata. Lenguajes Regulares y sus Fase 2: Conocer formalismos usados para máquinas definir lenguajes formales. El estudiante realiza de manera grupal ejercicios de Lenguajes formales mediante lenguajes y expresiones regulares, autómatas finitos, o gramáticas. Lenguajes Independientes Fase 3: Modelar problemas de Lenguajes del Contexto y sus Independientes del Contexto. El estudiante máquinas realiza de manera grupal ejercicios de máquinas abstractas (Autómata de Pila). Lenguajes Estructurados Fase 4: Modelar problemas de Lenguajes por Frases Estructurados por Frases. El estudiante realiza de manera grupal ejercicios de máquinas abstractas (Maquinas de Turing). Autómatas y sus Fase 5: Desarrollar aplicaciones con aplicaciones Autómatas. El estudiante desarrolla e implementa la teoría de autómatas al ejercicio planteado.

6. ESTRATEGIAS DE ACOMPAÑAMIENTO DOCENTE Descripción de las estrategias de acompañamiento docente a utilizar en este curso. El acompañamiento tutorial que se efectúa en el Curso Autómatas y lenguajes formales, tomando en cuenta el Proyecto Académico Pedagógico de la UNAD, en donde se establece como una acción comunicativa efectiva, provista de un conjunto de estrategias encaminadas a potenciar de manera efectiva el aprendizaje, la formación integral del estudiante y el desarrollo del pensamiento autónomo y crítico.

Dentro del curso de Autómatas y lenguajes formales, se contempla las siguientes acciones: Estrategias Sincrónicas: 1. Acompañamiento vía Skype: se establece una atención de acuerdo con la agenda de acompañamiento docente publicada en el curso. 2. Acompañamiento vía Webconference: de acuerdo a la programación establecida en el curso. 3. Llamadas telefónicas a los estudiantes Estrategias asincrónicas: 1. Acompañamiento vía correo interno del curso 2. Acompañamiento y retroalimentación en los foros de aprendizaje colaborativo 3. OVAS y OVIS de cada una de las unidades 4. Canal de YouTube del curso donde se comparten video tutoriales. 7. PLAN DE EVALUACIÓN DEL CURSO Númer o de seman a 1y2

Momento s de la evaluació n Inicial

3, 4, 5 y Intermedi 6 a Unidad 1

7, 8, 9, 10

Intermedi a Unidad 2

Productos a entregar según la estrategia de aprendizaje Fase 1: Pre saberes. El estudiante realiza trabajo individual de pre saberes del curso mediante el resultado se entrega en un PDF Fase 2: Conocer formalismos usados para definir lenguajes formales. Informe grupal en PDF con el desarrollo de los problemas ejercicios planteados sobre lenguajes y expresiones regulares. Fase 3: Modelar problemas de Lenguajes Independientes del Contexto. Informe grupal en PDF con el desarrollo de los problemas ejercicios

Puntaje máximo/500 puntos

Ponderaci ón/500 puntos

25 5%

24% 350

23%

11, 12, 13 y 14

Intermedi a Unidad 3

15 y 16

Final

planteados sobre autómatas con pila y gramáticas. Fase 4: Modelar problemas de Lenguajes Estructurados por Frases. Informe grupal en PDF con el desarrollo de los problemas ejercicios planteados sobre Máquinas de Turing. Fase 5: Desarrollar aplicaciones con Autómatas. Informe grupal en PDF con el desarrollo de los problemas planteados. Puntaje Total

23%

125 500 puntos

25% 100%