Teoría de autómatas y lenguajes formales
GUÍA DOCENTE Curso 2014-15
Titulación: | Grado en Matemáticas | 701G |
Asignatura: | Teoría de autómatas y lenguajes formales | 478 |
Materia: | Teoría de autómatas y lenguajes formales |
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. Estos objetos suelen ser introducidos con un cierto nivel de abstracción matemática que resulta de interés en la formación de los estudiantes del grado de matemáticas.
Competencias
Competencias generales
CG 1. Comprender el lenguaje matemático, enunciados y demostraciones, identificando razonamientos incorrectos, y utilizarlo en diversos problemas y aplicaciones.
CG 6. Relacionar el conocimiento especializado de Matemáticas con el conocimiento general en el que se inserta y con las herramientas que utiliza cuando se aplica en diversas opciones profesionales, especialmente en el marco de las TIC.
CG 7. Saber abstraer las propiedades estructurales de objetos de la realidad observada y de otros ámbitos, distinguiéndolas de aquellas puramente ocasionales, comprobando la aplicabilidad de las Matemáticas.
CG 8. Capacitar para el aprendizaje autónomo de nuevos conocimientos y técnicas.
Competencias específicas
CE 2. Utilizar aplicaciones informáticas de análisis estadístico, cálculo numérico y simbólico, visualización gráfica, optimización, u otras, para experimentar en Matemáticas y resolver problemas.
CE 3. Proponer, analizar, validar e interpretar modelos de situaciones reales sencillas, utilizando las herramientas matemáticas más adecuadas a los fines que se persigan.
CE 4. Encontrar soluciones algorítmicas de problemas matemáticos y de aplicación (de ámbito académico, técnico, financiero o social), sabiendo comparar distintas alternativas, según criterios de adecuación, complejidad y coste.
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.