- Identificar y resolver problemas abordables mediante modelos computacionales restringidos (autómatas) o alternativos (sistemas inteligentes).

- Diseñar autómatas, gramáticas y expresiones regulares para definir lenguajes formales.

- Utilizar software de reconocimiento y procesamiento de patrones.

- Conocer la existencia de límites intrínsecos a los procesos computacionales y de sus consecuencias.

- Analizar problemas y sus soluciones computacionales haciendo uso del lenguaje verbal, matemático y gráfico.

1. Introducción. Palabras y lenguajes.

2. Computación sin memoria.

2.1 Autómatas y transductores finitos. Equivalencias y transformaciones.

2.2 Expresiones regulares. Equivalencias y transformaciones.

2.3 Límites.

3. Computación con memoria restringida.

3.1 Gramáticas independientes del contexto. Ambigüedad.

3.2 Autómatas con pila.

3.3 Límites.

4. Modelo general de computador.

4.1 Autómatas de Turing.

4.2 Máquinas de Turing y diagramas.

4.3 Tesis de Church-Turing.

4.4 Límites. Incomputabilidad.

5. Sistemas Inteligentes.

5.1 Introducción a la complejidad computacional. Necesidad de aproximaciones.

5.2 Especificaciones no funcionales.

5.3 Ejemplo: Árboles de decisión.

Los temas del curso se irán exponiendo en clase y se señalará material de lectura complementario. En las sesiones de clase se realizarán de manera sistemática: exposiciones de los temas de la asignatura y ejercicios de afianzamiento de las técnicas aprendidas.



Se distribuirá una gran colección de enunciados de problemas. Su objetivo es expresarse con soltura en el lenguaje más apropiado en cada contexto: informal (típicamente en lenguaje natural), formal textual (lógica y matemáticas), formal gráfico (diagramas de autómatas, árboles de decisión, etc.).

Se potenciará la colaboración a través de la utilización de los foros en eGela para presentar de manera organizada las soluciones de los problemas que se van proponiendo en colecciones de enunciados por cada tema de la asignatura. Para compartir dichas soluciones de forma rápida y comprensible se hará uso de herramientas gráficas que permiten visualizar el comportamiento de los modelos teóricos y facilitan la comprensión de su funcionamiento.

La asignatura tiene dos modos de evaluación: evaluación final (o de conjunto) y evaluación continua.



EVALUACIÓN CONTINUA: La/el estudiante podrá acogerse voluntariamente a ella, ya que para aprobar la asignatura en esta modalidad, la/el estudiante deberá ofrecerle la dedicación necesaria para estudiar y resolver ejercicios.



Las diferentes actividades de evaluación y sus pesos correspondientes serán las siguientes:

1) Pruebas escritas (80%)

2) Entregas de ejercicios/problemas (20%)



Se realizarán tres pruebas escritas con pesos del 35%, 30% y 15%, sumando el 80% antes indicado para las pruebas escritas en la nota final de la asignatura. Cada una de las pruebas escritas requerirá una nota mínima del 30% para mantenerse en la modalidad de seguimiento continuo. En las entregas de ejercicios/problemas no se requerirá nota mínima.



Se considerará que la/el estudiante cursará en el modo de evaluación continua a menos que renuncie explícitamente. El alumnado que, cumpliendo las condiciones para continuar en el sistema de evaluación continua, decidiese optar por la evaluación global, deberá informar al profesorado responsable de la asignatura antes de la última semana de clases a través eGela. Si en las mencionadas fechas la/el estudiante no renuncia a la evaluación continua se entenderá que confirma la misma.



EVALUACIÓN FINAL: Será aplicable al estudiantado que no desee acogerse al sistema continuo o a quienes no superen las condiciones de continuidad de dicha evaluación. La prueba de conjunto consistirá en un examen escrito que abarcará el 100% de los contenidos de la asignatura, a realizar según el calendario oficial de exámenes de la Facultad.



Durante el desarrollo de cada una de las pruebas de evaluación (continua o final) queda prohibida la utilización de libros, notas o apuntes, así como aparatos o dispositivos telefónicos, electrónicos, informáticos, o de otro tipo.

El conjunto de diapositivas utilizadas por el profesorado para presentar la asignatura y los enunciados de problemas y ejercicios se consideran material de uso obligatorio, y estarán disponibles a través de eGela.

El uso de los siguientes recursos es también necesario para cursar la asignatura:
- eGela
- Cuenta de correo electrónico corporativo
- JFLAP

Bibliografía básica

- TEORÍA DE AUTÓMATAS, LENGUAJES Y COMPUTACIÓN: J.E. Hopcroft, R. Motwani eta J.D. Ullman. Pearson Educación, 3ª edición, 2007.

- AUTÓMATAS Y LENGUAJES. UN ENFOQUE DE DISEÑO: R. Brena. Instituto Tecnológico de Monterrey, 2003. (https://lenguajesformalesyautomatas.files.wordpress.com/2017/11/automatas-y-lenguajes.pdf)

- JFLAP: AN INTERACTIVE FORMAL LANGUAGES AND AUTOMATA PACKAGE: S.H. Rodger eta T.W. Finley. Jones & Bartlett, 2006. (https://www.jflap.org/jflapbook/jflapbook2006.pdf)

- INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO: S. Russell eta P. Norvig. Prentice Hall, 2ª edición, 2003

Bibliografía de profundización

- AUTOMATA, COMPUTABILITY AND COMPLEXITY: E. Rich. Pearson Education, 2008.
- INTRODUCCIÓN A LA TEORÍA DE AUTÓMATAS, GRAMÁTICAS Y LENGUAJES. E. Gaudioso & T. García. Editorial Universitaria Ramón Areces. 2017. (contiene ejercicios y soluciones)