Matemáticas
Grado y Doble Grado. Curso 2023/2024.
AUTÓMATAS Y COMPUTABILIDAD - 800616
Curso Académico 2023-24
Datos Generales
- Plan de estudios: 0803 - GRADO EN MATEMÁTICAS (2009-10)
- Carácter: Optativa
- ECTS: 6.0
SINOPSIS
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.
Seminarios
Resolución de dudas y problemas. Aproximadamente una hora semanal.
Clases prácticas
Sesiones académicas de problemas.
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
A lo largo del curso se pedirá la entrega de ejercicios resueltos por el alumno, que puntuarán el 10% de la nota de la asignatura. 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.
Estructura
| Módulos | Materias |
|---|---|
| CIENCIAS DE LA COMPUTACIÓN | AUTÓMATAS Y COMPUTABILIDAD |
Grupos
| Clases teóricas | ||||
|---|---|---|---|---|
| Grupo | Periodos | Horarios | Aula | Profesor |
| Grupo único | 04/09/2023 - 15/12/2023 | LUNES 11:00 - 12:00 | S-106 | MIGUEL PALOMINO TARJUELO |
| MIÉRCOLES 11:00 - 12:00 | S-109 | MIGUEL PALOMINO TARJUELO | ||
| Clases prácticas | ||||
|---|---|---|---|---|
| Grupo | Periodos | Horarios | Aula | Profesor |
| Grupo único | 04/09/2023 - 15/12/2023 | MARTES 10:00 - 11:00 | S-106 | MIGUEL PALOMINO TARJUELO |
| JUEVES 11:00 - 12:00 | S-106 | MIGUEL PALOMINO TARJUELO | ||