Teoría de autómatas y lenguajes formales
GUÍA DOCENTE Curso 2014-15
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 | Duración: | 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: | Benito Clavijo, María Del Pilar | Responsable de la asignatura |
Teléfono: | 941299457 | Correo electrónico: | pilar.benito@unirioja.es |
Despacho: | 211 | Edificio: | EDIFICIO VIVES | Tutorías: | Consultar |
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.
Requisitos previos de conocimientos y competencias para poder cursar con éxito la asignatura
Recomendados para poder superar la asignatura.
Se aconseja conocer fundamentos de teoría de conjuntos.
Asignaturas que proporcionan los conocimientos y competencias:
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.
CG12-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.
CG15-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.
CG17-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.
Competencias específicas
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 | No Recup. |
Pruebas escritas | 70% | |
Trabajos y proyectos | 10% | 20% |
Total | 100% |
Comentarios
La evaluación continua consistirá en trabajos y proyectos.
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."
Los trabajos y proyectos deberán ser entregados en tiempo y forma; la no entrega supondrá una reducción de la calificación final (% no recuperable).
El material didáctico (ejercicios prácticos, cuestiones, actividades ...etc), si lo hubiera, se encontrará disponible en el aula virtual para todos los alumnos matriculados en esta asignatura.
Criterios críticos para superar la asignatura
La copia de prácticas de laboratorio y otras tares supondrá el suspenso automático en la asignatura.
Para aprobar la asignatura, el alumno ha de demostrar un mínimo de conocimientos de las distintas partes del temario de la asignatura.