Los contenidos de esta asignatura pertenece a una ramas clásicas de la informática teórica.

Autómatas, gramáticas, lenguajes formales, computabilidad, complejidad, paradigmas de programación, sistemas inteligentes

Computación sin memoria Autómatas y traductores finitos. Lenguajes y expresiones regulares. Aplicaciones: análisis léxico

Memoria con restricciones Autómatas con pila. Gramáticas y lenguajes incontextuales. Autómatas lineales acotados. Aplicaciones: análisis sintáctico.

El modelo general de computador y sus limitaciones Máquinas de Turing. Universalidad computacional y Tesis de Church-Turing. Incomputabilidad. Introducción a la complejidad computacional. Aplicaciones: criptografía de clave pública.

Alternativas al modelo de computacion Modelos de máquina y paradigmas de programación. Circuitos y máquinas ¿reales¿. Programas imperativos, funcionales y lógicos. Aplicaciones: razonamiento automático

Alternativas al modelo de problema Especificaciones no funcionales. Árboles de decisión. Clasificadores. Programación probabilística. Aplicaciones: sistemas que aprenden.

En las clases magistrales (M) se describen los diferentes fundamentos teóricos de la asignatura, introduciéndose algoritmos a modo de ejercicios resueltos en clase. Se proponen nuevos ejercicios a ser resueltos en grupos de dos en los laboratorios (PL), cuya comprobación se realizará mediante simuladores de autómatas (JFLAP).

• Azken Ebaluazioaren Sistema
• Kalifikazioko tresnak eta ehunekoak:
  • Garatu beharreko proba idatzia (%): 75
  • Praktikak egitea (ariketak, kasuak edo buruketak) (%): 25

Para aprobar la asignatura es necesario obtener al menos cinco puntos sobre 10.

Se realizará un examen parcial del 30% de la nota de la asignatura.

Se valorará opcionalmente con un 10% de la nota los informes de laboratorios por grupos, atendiéndose principalmente a si se han realizado y finalizado. La evaluación podrá individualizarse mediante preguntas sobre ejercicios concretos. Podrá renunciarse en cualquier momento a ser evaluados en este apartado.

Se realizará un examen final del 60% de la nota, salvo si se renuncia a la evaluación de los laboratorios en cuyo caso valdrá el 70%.

En el examen final se podrá volver a evaluarse del bloque correspondiente al examen parcial en cuyo caso se pierde la nota anterior. Este apartado será obligatorio para quienes hayan obtenido menos del 25% del primer control.

Se realizará un examen final del 100% de la nota.

Apuntes de la asignatura y simulador JFLAP.

Oinarrizko bibliografia

J.E. HOPCROFT, R. MOTWANI, J.D. ULLMAN: "Teoría de Autómatas, Lenguajes y Computación" 3ª ed. Pearson educación, 2007

R. BRENA; "Autómatas y Lenguajes. Un enfoque de diseño" Tec de Monterrey, 2003. [on line] Disponible en http://lizt.mty.itesm.mx/~rbrena/AyL.html

S. RUSSELL, P. NORVIG: "Artificial Intelligence: A Modern Approach" 2ª ed. Prentice Hall, 2003

Gehiago sakontzeko bibliografia

S.H. RODGER, T.W. FINLEY; "JFLAP: An Interactive Formal Languages and Automata Package". Jones and Bartlett, 2006
D. WOOD; "Theory of computation". John Wiley & Sons, 1987.
S. ARORA, B. BARAK: "Computational Complexity: A Modern Approach" Cambridge University, 2009.
T. MITCHELL: "Machine Learning" McGraw Hill, 1997
G.F. LUGER, W.A. STUBBLEFIELD: "Artificial Intelligence. Structures and Strategies for Complex Problem Solving." Benjamin/Cummings Publishing Company, Inc, 1998.

Web helbideak

Java Computability Tool kit (JCT): http://humboldt.sunyit.edu/jct/
Visual and interctive tools (JFLAP): http://www.jflap.org/
Machine Learning theory and examples: http://www.cs.cmu.edu/~avrim/ML07/index.html
Implementación de algoritmos de IA en Java: http://code.google.com/p/aima-java/