Teoría de autómatas y lenguajes formales
GUÍA DOCENTE Curso 2013-14
Titulación: | Grado en Ingeniería Informática | 801G |
Asignatura: | Teoría de autómatas y lenguajes formales | 478 |
Materia: | Computación |
Módulo: | Optativas |
Carácter: | Optativa | Curso: | 4 | Semestre: | Semestral |
Créditos ECTS: | 6,00 | Horas presenciales: | 60,00 | Horas estimadas de trabajo autónomo: | 90,00 |
Idiomas en que se imparte la asignatura: | Español |
Idiomas del material de lectura o audiovisual: | Inglés, Francés, Español |
Departamentos responsables de la docencia
MATEMÁTICAS Y COMPUTACIÓN | R111 |
Dirección: | C/ Luis de Ulloa, s/n | Código postal: | 26004 |
Localidad: | Logroño | Provincia: | La Rioja |
Teléfono: | 941299452 | Fax: | 941299460 | Correo electrónico: | |
Profesorado previsto
Profesor responsable de la asignatura: | Benito Clavijo, María Del Pilar |
Teléfono: | 941299457 | Correo electrónico: | pilar.benito@unirioja.es |
Despacho: | 211 | Edificio: | Edificio Vives |
Horario de tutorías: | |
Descripción de los contenidos
- Lenguajes regulares y autómatas finitos. Equivalencia entre expresiones regulares y autómatas. Lema de Bombeo.
- Lenguajes libres de contexto y autómatas con pila. Gramáticas
- Máquinas de Turing. Tesis de Church. Máquinas de Turing universales
- Problemas insolubles. Problema de la parada.
Se aconseja conocer fundamentos de teoría de conjuntos.
Relación de asignaturas que proporcionan los conocimientos y competencias requeridos
Matemática discreta
Contexto
Los fundamentos teóricos de la informática descansan en los lenguajes formales y el concepto de autómata, herramientas imprescindibles para adentrarse en muchos campos de las Ciencias de la Computación. Lenguajes y autómatas y los algoritmos que los relacionan son necesarios para comprender el funcionamiento de compiladores y procesadores, la descripción de datos, la especificación de interfaces y las capacidades de los procesos de cálculo.
Competencias
Competencias generales
CG1 Estar capacitado para analizar, razonar y evaluar de modo crítico, lógico y, en caso necesario, formal, sobre problemas que se planteen en su entorno.
CG2 Estar capacitado para, utilizando el nivel adecuado de abstracción, establecer y evaluar modelos que representen situaciones reales.
CG7 Haber desarrollado aquellas habilidades de aprendizaje necesarias para continuar su formación.
Competencias específicas
CE5 Capacidad para concebir, desarrollar y mantener sistemas, servicios y aplicaciones informáticas empleando los métodos de la ingeniería del software como instrumento para el aseguramiento de su calidad.
CE8 Conocimiento de las materias básicas y tecnologías, que capaciten para el aprendizaje y desarrollo de nuevos métodos y tecnologías, así como las que les doten de una gran versatilidad para adaptarse a nuevas situaciones.
CE10 Conocimientos para la realización de mediciones, cálculos, valoraciones, tasaciones, peritaciones, estudios, informes, planificación de tareas y otros trabajos análogos de informática.
Resultados del aprendizaje
- Conocer los conceptos fundamentales de lenguajes, sus propiedades, su jerarquía y su relación natural con los lenguajes de programación.
- Manejar y diseñar máquinas de cómputo de diferentes tipos como reconocedoras de lenguajes de complejidad distinta.
- Comprender las limitaciones de los ordenadores y sus capacidades.
Temario
-
PRELIMINARES: Conjuntos y relaciones. Clausura Alfabetos y lenguajes. Descripción de lenguajes. Operaciones. Expresiones regulares.
-
LENGUAJES REGULARES Y SUS MÁQUINAS: Autómatas finitos deterministas y no deterministas. Métodos de diseño. Equivalencia entre autómatas finitos y expresiones regulares. Algoritmos de conversión. Lema de bombeo. Minimización.
-
LENGUAJES LIBRES DE CONTEXTO Y SUS MÁQUINAS: Gramáticas y generación de lenguajes. Jerarquía de Chomsky. Lenguajes libres de contexto. Autómatas con pila. Equivalencia entre autómatas con pila y lenguajes libres de contexto. Algoritmos de conversión.
-
INTRODUCCIÓN A MÁQUINAS TURING: Definición y funcionamiento de Máquinas Turing. Computación y decidibilidad Turing. Diseño de máquinas. Tesis de Church. Problemas insolubles.
Bibliografía
Tipo: | Título |
Básica | Elements of the Theory of Computation Absys Biba |
Básica | Introducción a la Teoría de Autómatas, Lenguajes y Computación Absys Biba |
Básica | Lenguajes Formales y Teoría de la computación Absys Biba |
Recursos en Internet |
JFLAP. Paquete Java diseñado como asistente para el aprendizaje de conceptos básicos en lenguajes y autómatas. Incluye edición gráfica y los algoritmos básicos de diseño y conversión que desarrollaremos a lo largo del curso. |
Página de wikipedia de presentación de autómatas y lenguajes |
Página web del profesor Arno Fornella de la Universidad de Vigo con material teórico-práctico sobre lenguajes y autómatas. |
Metodología
Modalidades organizativas
Clases teóricas
Seminarios y talleres
Clases prácticas
Tutorías
Estudio y trabajo en grupo
Estudio y trabajo autónomo individual
Métodos de enseñanza
Método expositivo - Lección magistral
Estudio de casos
Resolución de ejercicios y problemas
Aprendizaje orientado a proyectos
Aprendizaje cooperativo
Organización
Actividades presenciales | Tamaño de grupo | Horas |
Clases prácticas de aula | Reducido | 18,00 |
Clases prácticas de laboratorio o aula informática | Informática | 10,00 |
Clases teóricas | Grande | 32,00 |
Total de horas presenciales | 60,00 |
Trabajo autónomo del estudiante | Horas |
Estudio autónomo individual o en grupo | 40,00 |
Preparación de las prácticas y elaboración de cuaderno de prácticas | 20,00 |
Resolución individual de ejercicios, cuestiones u otros trabajos, actividades en biblioteca o similar | 30,00 |
Total de horas de trabajo autónomo | 90,00 |
Evaluación
Sistemas de evaluación | % | ¿Recuperable? |
Cuaderno de prácticas | 30 | No |
Examen Final | 50 | Sí |
Trabajos y proyectos | 20 | Sí |
Total | 100% | |
Comentarios
Para aprobar la asignatura, debe haber un cierto equilibrio entre las notas de distintos items de evaluación.
La asistencia a prácticas de laboratorio es obligatoria excepto para los alumnos semipresenciales. Para estos alumnos se aplicará la normativa vigente:
"Para los estudiantes a tiempo parcial (reconocidos como tales por la Universidad), las actividades de evaluación no recuperable podrán ser sustituidas por otras, a especificar en cada caso. Esta posibilidad se habilitará siempre y cuando la causa que le impida la realización de la actividad de evaluación programada sea la que ha llevado al reconocimiento de la dedicación a tiempo parcial."
Criterios críticos para superar la asignatura
La copia de prácticas de laboratorio supondrá el suspenso automático en la asignatura.