Los contenidos de esta asignatura pertenecen a una rama clásica de la informática teórica, anterior a los ordenadores modernos. Parte de la teoría de autómatas y lenguajes formales, que se aplica directamente a la definición de lenguajes de programación y la construcción de compiladores.



Los formalismos abordados permiten abstraer el concepto computador/computación para analizar la computabilidad, complejidad y tratabilidad de los algoritmos, utilizados en áreas actuales como la optimización de algoritmos y la criptografía.



Se utiliza el álgebra de conjuntos y la especificación/descripción formal de los lenguajes por lo que es interesante haber cursado la asignatura de Metodología de la Programación del primer curso de este Grado y en particular la especificación.



Se introducen reconocedores y generadores de lenguajes. Se estudian algoritmos que muestran la relación/transformación entre autómatas, Máquinas de Turing, expresiones regulares y gramáticas, así como sus propiedades. La utilización de simuladores permiten visualizar y verificar su ejecución en equipo, comprobando los resultados obtenidos en papel.



Se introducen conceptos de Inteligencia Artificial como modelos alternativos de computación. Estos aspectos se ven con mayor profundidad en la asignatura de Sistemas de Apoyo a la Decisión del tercer curso de este Grado.

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

Utilizar gramáticas y expresiones regulares para definir lenguajes formales.

Utilizar software de reconocimiento y procesamiento de patrones.

Comprensión de la existencia de límites intrínsecos a los procesos computacionales y de sus consecuencias.

Conocer y utilizar diferentes paradigmas de programación y modelos alternativos de computación.

Trabajar y analizar problemas y sus soluciones computacionales haciendo uso del lenguaje verbal, matemático y gráfico

Computaci¿in memoria Aut¿as y traductores finitos. Lenguajes y expresiones regulares. Aplicaciones: an¿sis l¿co

Memoria con restricciones Aut¿as con pila. Gram¿cas y lenguajes incontextuales. Aut¿as lineales acotados. Aplicaciones: an¿sis sint¿ico.

El modelo general de computador y sus limitaciones M¿inas de Turing. Universalidad computacional y Tesis de Church-Turing. Incomputabilidad. Introducci¿ la complejidad computacional. Aplicaciones: criptograf¿de clave p¿blica.

Alternativas al modelo de computaci¿odelos de m¿ina y paradigmas de programaci¿Circuitos y m¿inas reales. Programas imperativos, funcionales y l¿os. Aplicaciones: razonamiento autom¿co

Alternativas al modelo de problema Especificaciones no funcionales. ¿rboles de decisi¿Clasificadores. Programaci¿robabil¿ica. Aplicaciones: sistemas que aprenden.

En las clases magistrales (M) se describen los diferentes fundamentos te¿os de la asignatura, introduci¿ose 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¿e realizar¿ediante simuladores de aut¿as (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án 3 exámenes parciales del 25% de la nota de la asignatura cada uno. Para la convocatoria ordinaria se realizará una repesca opcional de cada uno de los dos primeros bloques para mejorar la nota.

Se valorará con un 25% de la nota los laboratorios, realizándose pruebas individualizadas tras su finalización.

Si se renuncia a la evaluación continua se realizará un examen final del 100% de la nota. Esta renuncia deberá ser notificada al profesor antes de la 9ª semana de acuerdo con la normativa existente.

Si no se asiste a la prueba final se considerará no presentado.



* Evaluación no presencial

Si no se puede realizar una evaluación presencial de la asignatura, se realizarán los cambios pertinentes para hacerlo online mediante la utilización de las herramientas informáticas existentes en la UPV/EHU. Las características de esta evaluación online serán hechas públicas en eGela.

Para la convocatoria extraordinaria se realizar¿n examen final del 100% de la nota. No se guarda ninguna nota de evaluaciones anteriores.



* Evaluaci¿o presencial

Si no se puede realizar una evaluaci¿resencial de la asignatura, se realizar¿los cambios pertinentes para hacerlo online mediante la utilizaci¿e las herramientas inform¿cas existentes en la UPV/EHU. Las caracter¿icas de esta evaluaci¿nline ser¿hechas p¿blicas en eGela.

Presentaciones de la asignatura Ejemplos resueltos de la asignatura Ejercicios de la asignatura Simulador JFLAP proporcionado

Oinarrizko bibliografia

Ram¿. BRENA; "Aut¿as y Lenguajes. Un enfoque de dise¿ Tec de Monterrey, 2003.



Elaine RICH, "Automata, Computability and Complexity. Theory and Applications", Pearson/Prentice Hall, 2008



V. MATHIVET, "Inteligencia Artificial para desarrolladores. Conceptos e implementaci¿n Java", ENI Ediciones, 2017



J.E. HOPCROFT, R. MOTWANI, J.D. ULLMAN: "Teor¿de Aut¿as, Lenguajes y Computaci¿3¿ ed. Pearson educaci¿2007



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



S.H. RODGER, T.W. FINLEY; "JFLAP: An Interactive Formal Languages and Automata Package". Jones and Bartlett, 2006

Gehiago sakontzeko bibliografia

S. ARORA, B. BARAK: "Computational Complexity: A Modern Approach" Cambridge University, 2009. D. WOOD; "Theory of computation". John Wiley & Sons, 1987. 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¿e algoritmos de IA en Java: https://github.com/aima-java/aima-java