Autómatas y lenguajes formales

Introducir los conceptos de la teoría de autómatas y de los lenguajes formales, y estudiar sus aplicaciones. En la asignatura se realizará el estudio de los diferentes modelos de máquinas computacionales, gramáticas y lenguajes formales, así como la correspondencia entre autómatas, lenguajes y gramáticas. También se estudiarán los conceptos de decidibilidad y complejidad computacional.

PROGRAMA DE TEORÍA

1. Introducción: lenguajes, gramáticas formales, autómatas


2. Autómatas finitos

Autómatas finitos deterministas (AFD)
Autómatas finitos no deterministas (AFN)
Transformación de AFN en AFD
Minimización de AFD


3. Lenguajes regulares

Expresiones regulares
Autómatas finitos y expresiones regulares
Álgebra de expresiones regulares
Lema de bombeo para lenguajes regulares


4. Gramáticas independientes del contexto (GIC)

Definición de gramáticas
Derivaciones
Árboles de derivación
Ambigüedad
Formas normales para GIC


5. Autómatas con pila

Autómatas con pila no deterministas
Reconocimiento por vaciado de pila y por estado final
Transformación de gramáticas a autómatas con pila
Autómatas con pila deterministas
Lema de bombeo para lenguajes independientes del contexto (LIC)


6. Máquinas de Turing

Máquina de Turing básica
Extensiones a la máquina de Turing básica
Máquinas de Turing restringidas


7. Decidibilidad y complejidad

Lenguajes recursivos y recursivamente enumerables
Problemas indecidibles
Problemas intratables: las clases P y NP
Problemas NP-completos


PROGRAMA DE PRÁCTICAS

El programa de prácticas se divide en tres bloques:

1. Autómatas de estados finitos y expresiones regulares

2. Autómatas con pila y gramáticas independientes del contexto

3. Máquinas de Turing

Básica

LINZ, Peter. Introduction to formal languages and automata. Ed. 3, Boston: Jones and Bartlett Publishers, 2006. ISBN 978-0-7637-3798-6.

HOPCROFT, John E., MOTWANI, Rajeev, ULLMAN, Jeffrey D. Teoría de Autómatas, Lenguajes y Computación. Ed. 3, Madrid: Pearson Educación, 2008. ISBN 978-84-7829-088-8.


Complementaria


ALFONSECA CUBERO, Enrique, ALFONSECA MORENO, Manuel, MORIYÓN SALOMÓN, Roberto. Teoría de Autómatas y Lenguajes Formales. Ed. 1, Madrid: McGraw Hill, 2007. ISBN 978-84-481-5637-4.

SUDKAMP, Thomas A. Languages and machines: an introduction to the theory of computer science. Ed. 3, Boston: Pearson, 2006. ISBN 978-0-321-32221-0.

BÁSICAS Y GENERALES
CG1 - Capacidad para concebir, redactar, organizar, planificar, y desarrollar modelos, aplicaciones y servicios en el ámbito de la inteligencia artificial, identificando objetivos, prioridades, plazos recursos y riesgos, y controlando los procesos establecidos.
CG2 - Capacidad para resolver problemas con iniciativa, toma de decisiones, autonomía y creatividad.
CG3 - Capacidad para diseñar y crear modelos y soluciones de calidad basadas en Inteligencia Artificial que sean eficientes, robustas, transparentes y responsables
CG4 - Capacidad para seleccionar y justificar los métodos y técnicas adecuadas para resolver un problema concreto, o para desarrollar y proponer nuevos métodos basados en inteligencia artificial.
CG5 - Capacidad para concebir nuevos sistemas computacionales y/o evaluar el rendimiento de sistemas existentes, que integren modelos y técnicas de inteligencia artificial.
CB2 - Que los estudiantes sepan aplicar sus conocimientos a su trabajo o vocación de una forma profesional y posean las competencias que suelen demostrarse por medio de la elaboración y defensa de argumentos y la resolución de problemas dentro de su área de estudio
CB3 - Que los estudiantes tengan la capacidad de reunir e interpretar datos relevantes (normalmente dentro de su área de estudio) para emitir juicios que incluyan una reflexión sobre temas relevantes de índole social, científica o ética.
CB4 - Que los estudiantes puedan transmitir información, ideas, problemas y soluciones a un público tanto especializado como no especializado.
CB5 - Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía.

TRANSVERSALES
TR2 - Capacidad de trabajo en equipo, en entornos interdisciplinares y gestionando conflictos.
TR3 - Capacidad para crear nuevos modelos y soluciones de forma autónoma y creativa, adaptándose a nuevas situaciones. Iniciativa y espíritu emprendedor.

ESPECÍFICAS
CE2 - Capacidad para resolver problemas de inteligencia artificial que precisen algoritmos, aplicando correctamente metodologías de desarrollo software y diseño centrado en usuario/a.
CE3 - Capacidad para comprender y dominar los conceptos básicos de lógica, gramáticas y lenguajes formales para analizar y mejorar las soluciones basadas en inteligencia artificial.

Clases de teoría.

Se elaborará material de estudio para cada uno de los temas, de tal forma que el alumnado pueda seguir la clase. En las transparencias también se incluyen problemas, algunos de los cuales serán resueltos en clase, mientras que otros deberá solucionarlos el propio alumnado dentro de su tiempo de estudio de la asignatura. Muchos de los ejercicios han sido extraídos de exámenes de años anteriores.


Sesiones de prácticas.

Las sesiones de prácticas serán de dos horas de duración, y se propondrán boletines a modo de guía de las mismas. Antes de acudir a cada sesión de prácticas es imprescindible haber estudiado la teoría correspondiente. También es aconsejable que el/la alumno/a haya resuelto por su cuenta algún problema del tema.

La evaluación de las competencias se realizará en las siguientes prácticas/examen:

[CG1, CG2, CG3, CG4, CG5, CB2, CB5, TR3, CE3] Prácticas y el examen.
[CB3, CB4, TR2, CE2] Prácticas.

La evaluación de la materia se realizará en dos partes: evaluación continua y examen final. Para aprobar la materia es imprescindible superar ambas partes por separado.

La evaluación continua se realizará mediante la entrega de los boletines de prácticas correspondientes la cada sesión, así como por medio de test con preguntas relativas a los boletines entregados. Estos test se realizarán de forma presencial durante las clases de prácticas. La nota máxima que se puede obtener en la evaluación continua será de 10 puntos.

En el examen final escrito el alumno podrá lograr un máximo de 10 puntos.

La nota final de la materia será la suma ponderada de ambas partes, con un peso del 30% de la evaluación continua y del 70% del examen final, excepto en aquellas situaciones en las que no se aprobara alguna de las dos partes, en cuyo caso la nota final será el mínimo entre la evaluación continua y el examen final, debiendo volver la examinarse según se indica posteriormente.

La entrega de alguno de los boletines de prácticas o de alguna de las pruebas de evaluación continua supondrá que el alumno optó por presentarse a la materia. Por tanto, a partir de ese momento aún no presentándose al examen final consumirá una oportunidad.

En la segunda oportunidad (julio) se conservará la nota de la evaluación continua obtenida durante el cuatrimestre, en el caso de tener una cualificación de la misma de 5 o más puntos. En otro caso el estudiante tendrá que ser evaluado de nuevo de la parte de prácticas de la materia. La realización del examen final es obligatoria en esta segunda oportunidad, independientemente de la nota en la primera oportunidad. La calificación global se calculará igual que en la primera oportunidad.

En el caso de realización fraudulenta de ejercicios o pruebas, será de aplicación el recogido en la normativa de evaluación del rendimiento académico de los estudiantes y de revisión de cualificaciones (https://www.xunta.gal/dog/publicados/2011/20110721/AnuncioG2018-190711-…). En aplicación de la normativa de la ETSE sobre plagio (aprobada por la Xunta de la ETSE el 19/12/2019), la copia total o parcial de algún ejercicio de prácticas o teoría supondrá el suspenso en las dos oportunidades del curso, con la cualificación de 0,0 en ambos casos (https://www.usc.es/etse/files/u1/NormativaPlagioETSE2019.pdf).

El tiempo de trabajo del alumno en la materia a lo largo del curso se desglosa de la siguiente forma:

(1) 20 horas de asistencia a las clases teóricas (2h/semana).

(2) 30 horas de asistencia la clases de prácticas (2h/semana).

(3) 99 horas de trabajo personal del alumno (estudio, realización de ejercicios, prácticas, etc.) (6h/semana).

(4) 1 hora de tutorización individual.

Se recomienda llevar el estudio de la teoría y la realización de prácticas y problemas al día, puesto que la evaluación mediante test así lo requiere. Igualmente se considera importante hacer un uso intenso de las tutorías para la resolución de dudas.

Requisitos previos recomendados: Cálculo y Análisis Numérico, Álgebra, Programación II, Algoritmos.

Se utilizará el Campus Virtual de la USC como herramienta de apoyo al proceso de aprendizaje en los siguientes aspectos: repositorio de materiales (transparencias, ejercicios, textos complementarios...), entrega y evaluación comentada de trabajos obligatorios y tutorización virtual (correo electrónico y foros).

Para la realización de parte de las prácticas se empleará el software JFLAP, que permite el diseño de autómatas y gramáticas, o aplicar el lema de bombeo, entre otras funcionalidades.