Estudia
- Artes y humanidades
- Ciencias
- Ciencias de la salud
- Ciencias sociales y jurídicas
-
Ingeniería y arquitectura
- Doble Grado en Ingeniería Civil e Ingeniería de los Recursos Mineros y Energéticos
- Doble Grado en Ingeniería en Tecnologías y Servicios de Telecomunicación / Grado en Ciencia e Ingeniería de Datos
- Doble Grado en Ingeniería Informática del Software / Grado en Matemáticas
- Doble Grado en Ingeniería Informática en Tecnologías de la Información / Grado en Ciencia e Ingeniería de Datos
- Grado en Ciencia e Ingeniería de Datos
- Grado en Ingeniería Civil
- Grado en Ingeniería de los Recursos Mineros y Energéticos
- Grado en Ingeniería de Organización Industrial
- Grado en Ingeniería de Tecnologías Industriales
- Grado en Ingeniería de Tecnologías Mineras
- Grado en Ingeniería Eléctrica
- Grado en Ingeniería Electrónica Industrial y Automática
- Grado en Ingeniería en Geomática
- Grado en Ingeniería en Tecnologías y Servicios de Telecomunicación
- Grado en Ingeniería Forestal y del Medio Natural
- Grado en Ingeniería Forestal y del Medio Natural (En extinción)
- Grado en Ingeniería Informática del Software
- Grado en Ingeniería Informática en Tecnologías de la Información
- Grado en Ingeniería Mecánica
- Grado en Ingeniería Química
- Grado en Ingeniería Química Industrial
- Grado en Marina
- Grado en Náutica y Transporte Marítimo
- Información, acceso y becas
Autómatas y Matemáticas Discretas
- Clases Expositivas (28 Hours)
- Prácticas de Aula/Semina (7 Hours)
- Tutorías Grupales (2 Hours)
- Prácticas de Laboratorio (21 Hours)
La asignatura de Autómatas y Matemáticas Discretas (AMD) compone, junto con la de Computabilidad, la materia de Fundamentos de Computación (FC) que se integra en el Módulo de Fundamentos de Ingeniería (FI) junto con las materias de Fundamentos Físicos y Fundamentos Matemáticos. Por su carácter fundamental, sus contenidos y competencias serán utilizados en la mayor parte del resto de las materias repartidas a lo largo de los distintos cursos, o bien como herramienta o bien como fuente de ejemplos y aplicaciones.
Servirá de apoyo a multitud de asignaturas, particularmente las de Estructuras de Datos y Algoritmia, proporcionando al estudiante una adecuada base conceptual sobre los principios teóricos relevantes que se utilizan en estas asignaturas. El estudio de los Lenguajes Formales, así como los correspondientes dispositivos reconocedores ó generadores, resulta de gran utilidad a la hora de comprender algunas de las tareas presentes en todo proceso de compilación de un programa, y más concretamente el análisis sintáctico y semántico del mismo. En lo que respecta a asignaturas del mismo curso, la materia de Autómatas y Matemáticas Discretas tiene interrelación con la asignatura de Álgebra. Los conceptos básicos sobre funciones, como el dominio, rango, las propiedades de inyectividad y suprayectividad, así como propiedades básicas sobre conjuntos y relaciones, resultan de gran utilidad para la asignatura de Autómatas. Sin embargo, como es lógico, la asignatura que constituye su continuación natural es la de Computabilidad. La materia que forman estas dos asignaturas constituye la justificación teórica de aspectos importantes de la Informática y debería hacer reflexionar al alumno sobre cómo se produjo el origen y desarrollo de la misma.
Para un correcto seguimiento de esta asignatura es recomendable que el alumno esté familiarizado con algunos conceptos asociados a las funciones, como es el dominio y el rango, así como con cuestiones básicas de teoría de conjuntos y relaciones. En cualquier caso con la formación que aporta el bachillerato por la rama tecnológica es suficiente para el seguimiento de la asignatura.
Como asignatura de carácter fundamental, Autómatas y Matemáticas Discretas contribuirá activamente a la adquisición de competencias básicas para el estudiante que le proporcione las habilidades de aprendizaje necesarias para emprender estudios posteriores o mejorar en su formación con un cierto grado de autonomía. Así, contribuirá a potenciar su capacidad para resolver problemas dentro de su área de estudio; de abstraer lo suficiente como para crear y utilizar modelos que reflejen situaciones reales; de actuar autónomamente así como de planificar y organizar su trabajo personal pero también fomentará la adquisición de competencias relativas al trabajo en entornos multidisciplinares y a la comunicación oral y escrita de documentación técnica poniendo énfasis especial en el cuidado de la calidad, la superación y el rigor que serán necesarios para el desarrollo profesional (GTR1 a GTR8).
Además, la asignatura desarrolla la siguiente competencia específica:
EFB3.1 - Capacidad para comprender y dominar los conceptos básicos de matemática discreta y su aplicación para la resolución de problemas propios de la ingeniería.
Dicha competencia específica comprende los resultados de aprendizaje detallados en la siguiente tabla:
Competencia | Resultado de aprendizaje | |
EFB3.1 | FC1 | Expresar alguna situación o problema real mediante un grafo |
EFB3.1 | FC2 | Construir caminos Eulerianos y Hamiltonianos en los correspondientes grafos |
EFB3.1 | FC3 | Utilizar los árboles y sus propiedades como estructura de datos |
EFB3.1 | FC4 | Resolver problemas reales utilizando la teoría de grafos |
EFB3.1 | FC5 | Construir un autómata finito reconocedor de un sencillo lenguaje dado y describir el lenguaje regular asociado a un pequeño autómata finito dado |
EFB3.1 | FC6 | Relacionar los lenguajes regulares con las expresiones regulares y autómatas equivalentes |
EFB3.1 | FC7 | Reconocer los límites de los lenguajes que pueden ser reconocidos por autómatas finitos |
EFB3.1 | FC8 | Describir alguna aplicación de los autómatas finitos |
EFB3.1 | FC9 | Construir gramáticas sencillas generadoras de un lenguaje dado y determinar el lenguaje generado por una gramática |
EFB3.1 | FC10 | Simplificar una gramática libre de contexto dada y pasar a cualquiera de las formas normales |
EFB3.1 | FC11 | Reconocer los lenguajes libres de contexto y conocer sus propiedades formales |
EFB3.1 | FC12 | Describir alguna aplicación de las gramáticas libres de contexto |
EFB3.1 | FC13 | Diseñar una Máquina de Turing sencilla asociada a un lenguaje dado |
EFB3.1 | FC14 | Reproducir la jerarquía de Chomsky relativa a los lenguajes formales |
Los contenidos de esta asignatura se desarrollarán en los siguientes 4 temas:
1. Grafos.
- Conceptos básicos y representación
- Accesibilidad y conexión
- Grafos y relaciones
- Caminos Eulerianos y Hamiltonianos
- Árboles
- Planaridad y coloreado
2. Autómatas y lenguajes regulares.
- Cadenas, alfabetos y lenguajes
- Autómatas Finitos Deterministicos (AFD)
- Autómatas Finitos No Determinísticos (AFN) y su equivalencia con los AFD
- AFN con lambda-movimientos (AFN-λ) y su equivalencia con los AFN
- Expresiones regulares (ER) y su equivalencia con los Autómatas Finitos
- Propiedades formales de los Lenguajes regulares
3. Autómatas, gramáticas y lenguajes libres de contexto.
- Gramáticas regulares y su equivalencia con los Autómatas Finitos
- Gramáticas y lenguajes libres de contexto (GLC, LLC)
- Árboles de derivación y ambigüedad
- Simplificación de GLC
- Formas Normales de Chomsky y Greibach
- Propiedades formales de los LLC
- Introducción al análisis léxico y sintáctico en compiladores
- Autómatas de Pila
4. Lenguajes recursivos y recursivamente enumerables.
- Jerarquía de Chomsky
- Gramáticas generales o de tipo 0
- Máquinas de Turing
Como se detalla en las tablas siguientes, se propone la siguiente tipología de modalidades organizativas, incluyendo los porcentajes correspondientes estimados en función del número total de créditos europeos de la asignatura:
- Presenciales (total 40%)
- Clases expositivas 18.7%
- Prácticas de aula/Seminarios/Talleres 4.7%
- Prácticas de laboratorio/campo/aula de informática/aula de idiomas. 14%
- Tutorías grupales 1.3%
- Sesiones de evaluación 1.3%
- No presenciales (total 60%)
- Trabajo autónomo: (48%)
- Trabajos individuales 21.0%
- Estudio personal 26.0%
- Tutorías individuales 1.0%
- Trabajo en grupo (12%)
- Trabajo autónomo: (48%)
Trabajo Presencial:
Introd. | Grafos | Lenguajes Regulares | Leng. Libres de Contexto | Lenguajes Recursivos y R.E. | Evaluación | Total | |
Clase Expositiva | 1 | 10 | 8 | 7 | 2 | 0 | 28 |
Prácticas de aula / Seminarios / Talleres | 0 | 2 | 2 | 3 | 0 | 0 | 7 |
Prácticas de laboratorio / campo / aula de informática / aula de idiomas | 0 | 6 | 8 | 7 | 0 | 0 | 21 |
Prácticas clínicas hospitalarias | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Tutorías grupales | 0 | 0 | 1 | 1 | 0 | 0 | 2 |
Prácticas Externas | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Sesiones de Evaluación | 0 | 0 | 0 | 0 | 0 | 2 | 2 |
Total | 1 | 18 | 19 | 18 | 2 | 2 | 60 |
Trabajo No Presencial:
Introd. | Grafos | Lenguajes Regulares | Leng. Libres de Contexto | Lenguajes R. y R.E. | Evaluación | Total | |
Trabajo grupo | 0 | 5 | 5 | 5 | 3 | 0 | 18 |
Trabajo autónomo | 0 | 22 | 22 | 23 | 5 | 0 | 72 |
Total | 0 | 27 | 27 | 28 | 8 | 0 | 90 |
Resumen:
MODALIDADES | Horas | % | Totales | |
Presencial | Clases Expositivas | 28 | 18.67 | 60 (40%) |
Práctica de aula / Seminarios / Talleres | 7 | 4.67 | ||
Prácticas de laboratorio / campo / aula de informática / aula de idiomas | 21 | 14.00 | ||
Prácticas clínicas hospitalarias | ||||
Tutorías grupales | 2 | 1.33 | ||
Prácticas Externas | ||||
Sesiones de evaluación | 2 | 1.33 | ||
No presencial | Trabajo grupo | 18 | 12.00 | 90 (60%) |
Trabajo autónomo | 72 | 48.00 | ||
Total | 150 | 150 |
Evaluación en la convocatoria ordinaria
En la evaluación ordinaria se utilizarán diversos procedimientos que permitirán el seguimiento del proceso de aprendizaje del alumno.
Los diferentes procedimientos evaluadores serán los siguientes:
- Evaluación de los controles realizados al finalizar cada uno de los temas.
- Evaluación de cuestionarios y ejercicios prácticos propuestos.
- Examen final de la asignatura.
- Prácticas de laboratorio: En las prácticas de laboratorio se plantearán ejercicios y cuestionarios para realizar en la sesión y las soluciones propuestas podrán ser evaluadas al final de la misma.
- Controles: se realizarán en el aula los controles pertinentes tras la impartición de los contenidos fijados.
Los dos apartados anteriores constituyen el proceso de evaluación continua y tienen un peso del 50% en la calificación final de la asignatura. Dicho peso se obtiene considerando un 10% para las actividades en las sesiones de prácticas y un 40% para los controles.
- Examen final: Consistirá en una o más pruebas con un peso del 50% de la calificación final de la asignatura.
Resumen de la evaluación
Procedimientos de evaluación | Valoración en % |
Prueba final escrita | 50 |
Controles | 40 |
Actividades y cuestionarios realizados en las sesiones de prácticas de laboratorio | 10 |
Consideraciones importantes:
- El peso en cada ítem de la evaluación de cada uno de los temas del programa (véase Sección 5: Contenidos) será proporcional al número de horas presenciales dedicadas a dicha parte.
- La nota final de cada tema de la asignatura será la máxima de las calificaciones obtenidas en el correspondiente control y en la parte correspondiente del examen final. Cada alumno/alumna decidirá a qué temas desea presentarse en el examen final.
- La calificación final de la asignatura se calculará sumando las notas ponderadas obtenidas en cada uno de los temas impartidos, en caso de que se haya alcanzado un mínimo de 4 puntos sobre 10 en cada tema. En otro caso, la nota final de la asignatura será el mínimo entre 4 y esa media ponderada.
- Para superar la asignatura, la calificación final deberá ser igual o superior a 5 puntos.
Evaluación en las convocatorias extraordinarias
En las convocatorias de carácter extraordinario el alumno debe realizar un examen escrito, que representará el 100% de la calificación final y que incluirá la evaluación de las sesiones teóricas y prácticas con la misma ponderación que en la prueba escrita de la convocatoria ordinaria.
La calificación final de la asignatura en la convocatoria extraordinaria se calculará sumando las notas ponderadas obtenidas en el examen en cada tema, en caso de que se haya alcanzado un mínimo de 4 puntos sobre 10 en cada uno de ellos. En otro caso, la nota de la asignatura será el mínimo entre 4 y esa media ponderada.
Evaluación diferenciada
Aquellos alumnos con derecho a evaluación diferenciada serán evaluados del mismo modo que en las convocatorias extraordinarias.
Las tablas siguientes incluyen las referencias bibliográficas básicas y complementarias que se utilizan en la asignatura. Sin embargo los estudiantes dispondrán también de otros recursos en forma de apuntes, transparencias, boletines de problemas, exámenes tipo, etc que tendrán a su disposición en el Campus Virtual en el que, además, se incluirán avisos, applets, otros enlaces interesantes, etc.
Bibliografía básica | ||
Título | Autor | Editorial |
Introducción a la Teoría de Autómatas, Lenguajes y Computación. | Hopcroft, J.E.; Motwanni, R.; Ullman, J.D. | Addison-Wesley |
Teoría de Autómatas y Lenguajes Formales | Kelley, D. | Prentice Hall |
Análisis de Algoritmos y Teoría de Grafos | Abellanas, M.; Lodares, D. | Ra-ma |
Introduction to Discrete Structures | Preparata, Y. | Addison-Wesley |
Bibliografía complementaria | ||
Título | Autor | Editorial |
Teoría de Lenguajes, Gramáticas y Autómatas | Alfonseca, M.; Sancho, J.; Martínez, M. | Universidad y Cultura |
Theory of Finite Automata | Carroll, J.; Long, D. | Prentice Hall |
Mathematical Theory of Computation | Manna, Z. | McGraw-Hill |