Automatas e linguaxes formais

Introducir os conceptos da teoría de autómatas e das linguaxes formais, e estudar as súas aplicacións. Na materia realizarase o estudo dos diferentes modelos de máquinas computacionais, gramáticas e linguaxes formais, así como a correspondencia entre autómatas, linguaxes e gramáticas. Tamén estudaranse os conceptos de decidibilidade e complexidade computacional.

PROGRAMA DE TEORÍA

1. Introdución: linguaxes, gramáticas formais, autómatas


2. Autómatas finitos

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


3. Linguaxes regulares

Expresións regulares
Autómatas finitos e expresións regulares
Álxebra de expresións regulares
Lema de bombeo para linguaxes regulares


4. Gramáticas independentes do contexto (GIC)

Definición de gramáticas
Derivacións
Árbores de derivación
Ambigüidade
Formas normais para GIC


5. Autómatas con pila

Autómatas con pila non deterministas
Recoñecemento por baleirado de pila e por estado final
Transformación de gramáticas a autómatas con pila
Autómatas con pila deterministas
Lema de bombeo para linguaxes independentes do contexto (LIC)


6. Máquinas de Turing

Máquina de Turing básica
Extensións á máquina de Turing básica
Máquinas de Turing restrinxidas


7. Decidibilidade e complexidade

Linguaxes recursivas e recursivamente enumerables
Problemas indecidibles
Problemas intratables: as clases P e NP
Problemas NP-completos


PROGRAMA DE PRÁCTICAS

O programa de prácticas divídese en tres bloques:

1. Autómatas de estados finitos e expresións regulares

2. Autómatas con pila e gramáticas independentes do 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 E XENERAIS
CG1 - Capacidade para concibir, redactar, organizar, planificar, e desenvolver modelos, aplicacións e servizos no ámbito da intelixencia artificial, identificando obxectivos, prioridades, prazos recursos e riscos, e controlando os procesos establecidos.
CG2 - Capacidade para resolver problemas con iniciativa, toma de decisións, autonomía e creatividade.
CG3 - Capacidade para deseñar e crear modelos e solucións de calidade baseadas en Intelixencia Artificial que sexan eficientes, robustas, transparentes e responsables
CG4 - Capacidade para seleccionar e xustificar os métodos e técnicas adecuadas para resolver un problema concreto, ou para desenvolver e propoñer novos métodos baseados en intelixencia artificial.
CG5 - Capacidade para concibir novos sistemas computacionales e/o avaliar o rendemento de sistemas existentes, que integren modelos e técnicas de intelixencia artificial.
CB2 - Que os estudantes saiban aplicar os seus coñecementos ao seu traballo ou vocación dunha forma profesional e posúan as competencias que adoitan demostrarse por medio da elaboración e defensa de argumentos e a resolución de problemas dentro da súa área de estudo
CB3 - Que os estudantes teñan a capacidade de reunir e interpretar datos relevantes (normalmente dentro da súa área de estudo) para emitir xuízos que inclúan unha reflexión sobre temas relevantes de índole social, científica ou ética.
CB4 - Que os estudantes poidan transmitir información, ideas, problemas e solucións a un público tanto especializado como non especializado.
CB5 - Que os estudantes desenvolvesen aquelas habilidades de aprendizaxe necesarias para emprender estudos posteriores cun alto grao de autonomía.

TRANSVERSAIS
TR2 - Capacidade de traballo en equipo, en contornas interdisciplinares e xestionando conflitos.
TR3 - Capacidade para crear novos modelos e solucións de forma autónoma e creativa, adaptándose a novas situacións. Iniciativa e espírito emprendedor.

ESPECÍFICAS
CE2 - Capacidade para resolver problemas de intelixencia artificial que precisen algoritmos, aplicando correctamente metodoloxías de desenvolvemento software e deseño centrado en usuario/a.
CE3 - Capacidade para comprender e dominar os conceptos básicos de lóxica, gramáticas e linguaxes formais para analizar e mellorar as solucións baseadas en intelixencia artificial.

Clases de teoría.

Elaborarase material de estudo para cada un dos temas, de tal forma que o alumnado poida seguir a clase. Nas transparencias tamén se inclúen problemas, algúns dos cales serán resoltos en clase, mentres que outros deberá solucionalos o propio alumnado dentro do seu tempo de estudo da materia. Moitos dos exercicios foron extraídos de exames de anos anteriores.


Sesións de prácticas.

As sesións de prácticas serán de dúas horas de duración, e proporanse múltiples boletíns a modo de guía. Antes de acudir a cada sesión de prácticas é imprescindible estudar a teoría correspondente. Tamén é aconsellable que o alumno resolva pola súa conta algún problema do tema.

A avaliación das competencias realizarase nas seguintes prácticas/exame:

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

A avaliación da materia realizarase en dúas partes: avaliación continua e exame final. Para aprobar a materia é imprescindible superar ámbalas dúas partes por separado.

A avaliación continua realizarase mediante a entrega dos boletíns de prácticas correspondentes a cada sesión, así como por medio de test con preguntas relativas aos boletíns entregados. Estes test realizaranse de forma presencial durante as clases de prácticas. A nota máxima que se pode obter na avaliación continua será de 10 puntos.

No exame final escrito o alumno poderá lograr un máximo de 10 puntos.

A nota final da materia será a suma ponderada de ámbalas dúas partes, cun peso do 30% da avaliación continua e do 70% do exame final, excepto naquelas situacións nas que non se aprobase algunha das dúas partes, caso no que a nota final será o mínimo entre a avaliación continua e o exame final, debendo volver a avaliarse segundo se indica posteriormente.

A entrega dalgún dos boletíns de prácticas ou dalgunha das probas de avaliación continua supoñerá que o alumno optou por presentarse á materia. Por tanto, a partir dese momento aínda non presentándose ao exame final terá consumida unha oportunidade.

Na segunda oportunidade (xullo) conservarase a nota da avaliación continua obtida durante o cuadrimestre, no caso de ter unha cualificación da mesma de 5 ou máis puntos. Noutro caso o estudante terá que ser avaliado de novo da parte de prácticas da materia. A realización do exame final é obligatoria nesta segunda oportunidade, independentemente da nota na primeira oportunidade. A calificación global calcularase igual que na primeira oportunidade.

No caso de realización fraudulenta de exercicios ou probas, será de aplicación o recollido na normativa de avaliación do rendemento académico dos estudantes e de revisión de cualificacións (https://www.xunta.gal/dog/Publicados/2011/20110721/AnuncioG2018-190711-…). En aplicación da normativa da ETSE sobre plaxio (aprobada pola Xunta da ETSE o 19/12/2019), a copia total ou parcial dalgún exercicio de prácticas ou teoría suporá o suspenso nas dúas oportunidades do curso, coa cualificación de 0,0 en ambos casos (https://www.usc.es/etse/files/u1/NormativaPlagioETSE2019.pdf).

O tempo de traballo do alumno na materia ao longo do curso desglósase do seguinte xeito:

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

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

(3) 99 horas de traballo personal do alumno (estudo, realización de exercicios, prácticas, etc.) (6h/semana).

(4) 1 hora de titorización individual.

Recoméndase levar o estudo da teoría e a realización de prácticas e problemas ao día, xa que a avaliación mediante test así o require. Do mesmo xeito, considérase importante facer un uso intenso das titorías para a resolución de dúbidas.
Requisitos previos recomendados: Cálculo e Análise Numérica, Álxebra, Programación II, Algoritmos.

Empregarase o Campus Virtual da USC como ferramenta de apoio ao proceso de aprendizaxe nos seguintes aspectos: respositorio de materiais (transparencias, exercicios, textos complementarios...), entrega e avaliación comentada de traballos obrigatorios e titorización virtual (correo electrónico e foros).

Para a realización de parte das prácticas empregarase o software JFLAP, que permite o deseño de autómatas e gramáticas, ou aplicar o lema de bombeo, entre outras funcionalidades.