Guía Docente 2023-24 LENGUAJES FORMALES |
DATOS BÁSICOS DE LA GUÍA DOCENTE:
Materia: | LENGUAJES FORMALES | ||
Identificador: | 30052 | ||
Titulación: | GRADUADO EN INGENIERÍA INFORMÁTICA. PLAN 2008 (BOE 15/12/2008) | ||
Módulo: | TEORIA DE LA COMPUTACION | ||
Tipo: | OBLIGATORIA | ||
Curso: | 2 | Periodo lectivo: | Primer Cuatrimestre |
Créditos: | 3 | Horas totales: | 75 |
Actividades Presenciales: | 33 | Trabajo Autónomo: | 42 |
Idioma Principal: | Castellano | Idioma Secundario: | Inglés |
Profesor: | Correo electrónico: |
PRESENTACIÓN:
Esta asignatura introduce modelos abstractos y matemáticos sobre los fundamentos de la computación. El estudio formal de la relación entre máquinas, lenguajes y gramáticas produce varios modelos de computación. Nos centraremos en tres clases de modelos: aquellos con una cantidad finita de memoria (autómatas finitos), modelos con memoria de tipo pila (autómatas de pila) y modelos no restringidos (máquinas de Turing).
COMPETENCIAS PROFESIONALES A DESARROLLAR EN LA MATERIA:
Competencias Generales de la titulación | G05 | Capacidad para adaptarse a diferentes entornos con una actitud positiva y optimista y orientar su conducta a la consecución de metas |
G09 | Capacidad para tomar decisiones de manera imparcial y desde un punto de vista racional | |
G15 | Capacidad para estructurar la realidad relacionando objetos, situaciones y conceptos a través del razonamiento lógico matemático | |
Competencias Específicas de la titulación | E02 | Capacidad para aplicar los principios intrínsecos de la ingeniería basados en las matemáticas y en una combinación de disciplinas científicas |
E03 | Capacidad para reconocer los principios teóricos y aplicar satisfactoriamente los métodos prácticos apropiados para el análisis y la resolución de problemas de ingeniería | |
Resultados de Aprendizaje | R01 | Controlar los diferentes aspectos de la gramática formal |
R02 | Componer expresiones regulares y derivar los autómatas formales que las analicen | |
R03 | Comprender las gramáticas libres de contexto | |
R04 | Conocer las nociones básicas de teoría de la complejidad y las clases de problemas según su coste |
REQUISITOS PREVIOS:
Sistemas Lógicos
PROGRAMACIÓN DE LA MATERIA:
Contenidos de la materia:
1 - Autómatas |
1.1 - Definición |
1.2 - AFD y AFN |
1.3 - Epsilon-transition |
1.4 - Equivalencia y simplificación |
1.5 - Conversión de AFN en AFD |
2 - Expresiones Regulares y Lenguajes |
2.1 - Expresiones Regulares. Definición. |
2.2 - Autómatas y expresiones regulares |
2.3 - Propiedades de los lenguajes regulares |
3 - Gramáticas |
3.1 - Definición |
3.2 - Ambigüedad y propiedades |
3.3 - Forma normal y de Chomsky |
4 - Autómatas de pila y máquinas de Turing |
4.1 - Introducción |
4.2 - Autómatas de pila en lenguajes regulares |
4.3 - Introducción a máquinas de Turing |
La planificación de la asignatura podrá verse modificada por motivos imprevistos (rendimiento del grupo, disponibilidad de recursos, modificaciones en el calendario académico, etc.) y por tanto no deberá considerarse como definitiva y cerrada.
METODOLOGÍAS Y ACTIVIDADES DE ENSEÑANZA Y APRENDIZAJE:
Metodologías de enseñanza-aprendizaje a desarrollar:
Volumen de trabajo del alumno:
Modalidad organizativa | Métodos de enseñanza | Horas estimadas |
Actividades Presenciales | ||
Clase magistral | 14 | |
Resolución de prácticas, problemas, ejercicios etc. | 15 | |
Actividades de evaluación | 4 | |
Trabajo Autónomo | ||
Asistencia a tutorías | 3 | |
Estudio individual | 18 | |
Preparación de trabajos individuales | 16 | |
Lecturas obligatorias | 5 | |
Horas totales: | 75 |
SISTEMA DE EVALUACIÓN:
Obtención de la nota final:
Pruebas escritas: | 60 | % |
Trabajos individuales: | 35 | % |
Participación: | 5 | % |
TOTAL | 100 | % |
*Las observaciones específicas sobre el sistema de evaluación serán comunicadas por escrito a los alumnos al inicio de la materia.
BIBLIOGRAFÍA Y DOCUMENTACIÓN:
Bibliografía básica:
KELLEY, D. (1995). Teoría de autómatas y lenguajes formales. Madrid: Prentice Hall, D.L. (ISBN 9780135187050) |
MARTIN, J. (2004). Lenguajes Formales y Teoría de la Computación. México: McGraw-Hill. (ISBN 9789701045947) |
ISASI, P., MARTÍNEZ, P., BORRAJO, D. (2001). Lenguajes, Gramáticas y Autómatas. Un enfoque práctico. Madrid: Addison-Wesley Iberoamericana, D. L. (ISBN 9788478290147) (con ejercicios resueltos) |
Bibliografía recomendada:
HOPCROFT, J. E., MOTWANI, R., ULLMAN, J. D. (2002). Introducción a la teoría de autómatas, lenguajes y computación, 2ª edición. Madrid: Pearson Educación. (ISBN 9788478290567) |
ALFONSECA, M., SANCHO, J., MARTÍNEZ ORGA, M. (1997). Teoría de lenguajes, gramáticas y automátas. Madrid: Universidad y Cultura, D.L. (ISBN 8460560929) |
Páginas web recomendadas:
JFLAP: graphical tools useful for basic concepts of Formal Languages and Automata Theory. | http://www.jflap.org/ |
* Guía Docente sujeta a modificaciones