Departamentos

Matemáticas

Grado y Doble Grado. Curso 2024/2025.

AUTÓMATAS Y COMPUTABILIDAD - 800616

Curso Académico 2024-25

Datos Generales

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

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.

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.

Otra información relevante

Material disponible en el Campus Virtual.

Estructura

MódulosMaterias
CIENCIAS DE LA COMPUTACIÓNAUTÓMATAS Y COMPUTABILIDAD

Grupos

Clases teóricas
GrupoPeriodosHorariosAulaProfesor
Grupo único09/09/2024 - 13/12/2024LUNES 11:00 - 12:00S-106FERNANDO RUBIO DIEZ
MIÉRCOLES 11:00 - 12:00B04FERNANDO RUBIO DIEZ


Clases prácticas
GrupoPeriodosHorariosAulaProfesor
Grupo único09/09/2024 - 13/12/2024MARTES 10:00 - 11:00S-106FERNANDO RUBIO DIEZ
JUEVES 11:00 - 12:00S-106FERNANDO RUBIO DIEZ