Esta asignatura sirve de introducción a la especialidad de Computación, cuyo objetivo es profundizar en los principios y modelos fundamentales de la informática y los lenguajes de programación para su aplicación en nuevos sistemas computacionales, en la evaluación de la complejidad de los problemas y en el planteamiento de estrategias algorítmicas para su resolución.



En asignaturas anteriores (Programación Básica, Programación Modular y Orientada a Objetos, Estructuras de Datos y Algoritmos) se estudia cómo resolver problemas con soluciones algorítmicas, utilizando distintas metodologías y lenguajes de programación concretos. En cambio, en esta asignatura se aprende a distinguir los problemas que permiten solución algorítmica de los que no, independientemente del equipamiento y del software.



Se trabajan desde los contenidos básicos de lenguajes formales y autómatas hasta los principios básicos de computabilidad y complejidad, pero incluyendo también el paso hacia la Inteligencia Artificial que exigen algunos problemas.



Se podrá profundizar en estos temas cursando asignaturas de especialidad como Modelos Abstractos de Cómputo, Compilación, Diseño de Algoritmos, Minería de Datos o Inteligencia Artificial. Para recibir una especialización aún mayor en temas concretos encontrarás también asignaturas en la oferta del grado como Técnicas Avanzadas de Inteligencia Artificial, Procesamiento de Lenguaje Natural, Sistemas Basados en el conocimiento, Heurísticos de Búsqueda, Aprendizaje Automático y Redes Neuronales, Programación Lógica y Programación Funcional.



En cualquier ámbito del desarrollo profesional de la ingeniería informática existen aplicaciones basadas en los modelos de la asignatura. Los lenguajes permiten la comunicación máquina/persona y máquina/máquina. Sin ellos aplicaciones actuales como los protocolos de comunicación de redes, los lenguajes de marcado, etc. no existirían. Por ejemplo:

- el diseño e implementación de los lenguajes de programación modernos se basa en el uso de gramáticas;

- los procesadores de texto y las técnicas usadas en el procesamiento de lenguaje natural basan algunas de sus técnicas en los modelos que verás en la asignatura;

- los protocolos de comunicación, máquinas de “vending” y muchos juegos se describen utilizando autómatas finitos.

Por último, los resultados de complejidad son la base de las técnicas de criptografía.

- 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.

• Sistema de Evaluación Continua
• Sistema de Evaluación Final
• Herramientas y porcentajes de calificación:
  • Los porcentajes y tipos de evaluación se especifican en los apartados posteriores (%): 100

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.

La prueba consistirá en un examen 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 la prueba de evaluación 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)

Direcciones web

- Visual and interactive tools (JFLAP): http://www.jflap.org
- Alan Turing: http://www.turing.org.uk