Matemáticas
Grado y Doble Grado. Curso 2026/2027.
AUTÓMATAS Y COMPUTABILIDAD - 800616
Curso Académico 2026-27
Datos Generales
- Plan de estudios: 0803 - GRADO EN MATEMÁTICAS (2009-10)
- Carácter: Optativa
- ECTS: 6.0
SINOPSIS
COMPETENCIAS
ACTIVIDADES DOCENTES
Seminarios
Resolución de dudas y problemas. Aproximadamente una hora semanal.
Otras actividades
Tutorías: las tutorías estarán a disposición de los alumnos para resolver dudas.
Presenciales
6
Semestre
1
Breve descriptor:
Lenguajes formales y su clasificación en orden creciente de complejidad.
Autómatas reconocedores y gramáticas generadoras.
Fundamentos básicos de la teoría de la computabilidad.
Requisitos
Se recomienda un primer curso de álgebra.
Objetivos
Clasificación de lenguajes, autómatas y gramáticas: nivel avanzado.
Máquinas de Turing: nivel Medio.
Computabilidad: nivel elemental.
Contenido
1. Introducción a los autómatas y lenguajes formales.
2. Lenguajes regulares: autómatas finitos y expresiones regulares. Lema de bombeo.
3. Lenguajes independientes del contexto: autómatas con pila y gramáticas independientes del contexto. Lema de bombeo.
4. Lenguajes recursivos y recursivamente enumerables: máquinas de Turing.
5. Introducción a la teoría de la computabilidad.
Evaluación
El 10% se obtendrá de la calificación en un examen parcial a mitad de cuatrimestre.
El 90% restante se obtendrá de la calificación en el examen final de la convocatoria ordinaria o bien en el de la extraordinaria.
El 90% restante se obtendrá de la calificación en el examen final de la convocatoria ordinaria o bien en el de la extraordinaria.
Bibliografía
1. J.E. Hopcroft, R. Motwani y J.D. Ullman. Introducción a la Teoría de Autómatas, Lenguajes y Computación, 3ª edición. Pearson 2008.
2. H.R. Lewis y C.H. Papadimitriou. Elements of the Theory of Computation. Second Edition. Pearson Prentice Hall, 1997.
3. J.C. Martin. Introduction to Languages and the Theory of Computation, 5th editions. Jones & Bartlett 2011.
2. H.R. Lewis y C.H. Papadimitriou. Elements of the Theory of Computation. Second Edition. Pearson Prentice Hall, 1997.
3. J.C. Martin. Introduction to Languages and the Theory of Computation, 5th editions. Jones & Bartlett 2011.
Otra información relevante
Material disponible en el Campus Virtual.
COMPETENCIAS
Generales
Entender los fundamentos de los lenguajes informáticos.
Específicas
Comprender los límites de la computación: por mucho que avance la tecnología hay problemas que no pueden ser resueltos por el ordenador.
ACTIVIDADES DOCENTES
Clases teóricas
Sesiones académicas teóricas.
Clases prácticas
Sesiones académicas de problemas.
Estructura
| Módulos | Materias |
|---|---|
| CIENCIAS DE LA COMPUTACIÓN | AUTÓMATAS Y COMPUTABILIDAD |
Grupos
| Clases teóricas y/o prácticas | ||||
|---|---|---|---|---|
| Grupo | Periodos | Horarios | Aula | Profesor |
| Grupo único | 07/09/2026 - 15/12/2026 | LUNES 12:00 - 13:00 | S-106 | MIGUEL PALOMINO TARJUELO |
| MARTES 10:00 - 11:00 | S-106 | MIGUEL PALOMINO TARJUELO | ||
| MIÉRCOLES 11:00 - 12:00 | B04 | MIGUEL PALOMINO TARJUELO | ||
| JUEVES 11:00 - 12:00 | S-106 | MIGUEL PALOMINO TARJUELO | ||