DESCRIPCIÓN: En las ciencias de la computación, la tarea de desarrollar sistemas capaces de llevar a cabo de manera automática todo tipo de tratamiento de la información se ha visto parcialmente obstaculizada por la dificultad de hallar soluciones a algunos problemas (problemas no resueltos o problemas no resolubles) y por la dificultad de hallar soluciones eficientes a otros problemas (problemas considerados intratables porque aun habiéndose encontrado un procedimiento para hallar la solución, tal procedimiento es inviable por la cantidad de tiempo y/o espacio requerido para ejecutarlo). Ello ha conducido, por un lado, al estudio teórico de la "computación" con el objetivo de clasificar los problemas en computables y no computables (teoría de la computación) y, por otro lado, al estudio de la complejidad de los problemas computables (teoría de la complejidad computacional) para poder clasificarlos en tratables e intratables (diferenciándose además distintos grados de tratabilidad o intratabilidad). Para poder estudiar la computabilidad y la complejidad computacional, se han definido distintos modelos de computación (máquinas de Turing, lambda-cálculo, teoría de la recursión, cálculo de predicados de la lógica de primer orden, etc.). En esta asignatura, para iniciar el estudio de la computabilidad, se introducirá el concepto de lenguaje formal. La computación se entenderá como la búsqueda o diseño de estrategias o algoritmos que sirvan para detectar las propiedades que puedan caracterizar a grupos de lenguajes formales. Para la formalización de esos algoritmos, se utilizarán el lambda-cálculo y las máquinas de Turing. En concreto, utilizaremos el lambda-cálculo para estudiar la computabilidad y utilizaremos las máquinas de Turing para estudiar la complejidad computacional.

CONTEXTUALIZACIÓN: Antes de cursar esta asignatura (primer cuatrimestre del segundo curso) se ha estudiado en varias asignaturas el diseño de procedimientos que resuelven problemas computacionales. Una vez que se ha adquirido el conocimiento y la habilidad para diseñar procedimientos que realizan tareas computacionales, es el momento de presentar los límites de la computación (computabilidad en general y tratabilidad de problemas computables en particular). Después de conocer los límites básicos de la computabilidad, se está en disposición de proseguir con el perfeccionamiento y la profundización del diseño de procedimientos automáticos para el tratamiento de la información (en las distintas asignaturas tanto de segundo curso como de cursos posteriores), pero ahora con una perspectiva más amplia y adecuada.

COMPETENCIAS PROPIAS DE LA ASIGNATURA:



M02CM06: Conocimiento y aplicación de los procedimientos algorítmicos básicos de las tecnologías informáticas para diseñar soluciones a problemas, analizando la idoneidad y complejidad de los algoritmos propuestos.



M02CM015: Conocimiento y aplicación de los principios fundamentales y técnicas básicas de los sistemas inteligentes y su aplicación práctica.

BREVE DESCRIPCIÓN DE CONTENIDOS:

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



CONTENIDOS:

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.

Durante el desarrollo de las clases se llevarán a cabo, actividades de trabajo en grupo, discusión y presentación de resultados de ejercicios, con el fin de impulsar la participación directa del alumno en el desarrollo del curso y de fomentar la motivación y aprendizaje cooperativo y dinámico del alumno.

• Sistema de Evaluación Continua
• Sistema de Evaluación Final
• Herramientas y porcentajes de calificación:
  • Prueba escrita a desarrollar (%): 60
  • Realización de prácticas (ejercicios, casos o problemas) (%): 40

EVALUACIÓN CONTINUA:

A lo largo del cuatrimestre se realizarán pruebas (exámenes parciales que constarán de varios ejercicios) para evaluar las distintas competencias trabajadas en cada tema. La superación de un ejercicio supone la liberación de la materia correspondiente y guardar su nota para todo el curso. A la hora de contabilizar puntos solo se tienen en cuenta los ejercicios aprobados (aquellos en los que se ha alcanzado la mitad de la puntuación correspondiente al ejercicio). Se realizarán cinco exámenes parciales. Mediante estos exámenes parciales se podrán obtener 10 puntos. Es decir, se podrán obtener todos los puntos de la asignatura. En total, la asignatura se evalúa sobre 10 puntos. La asignatura se aprueba si se alcanzan 5 puntos de estos 10 puntos.



En el examen o prueba final (tanto en la convocatoria ordinaria como en la extraordinaria) se evaluarán los temas no liberados y los pendientes de evaluación.



EVALUACIÓN FINAL:

En caso de no elegir la "evaluación continua", al final del cuatrimestre habrá que realizar un examen final que valdrá 10 puntos. Para superarlo bastará con conseguir 5 puntos. También aquí solo se tendrán en cuenta los ejercicios aprobados (aquellos en los que se ha alcanzado la mitad de la puntuación correspondiente al ejercicio).



NO PRESENTADO:

Se tendrán en cuenta las siguientes normas para decidir cuándo se obtiene "No Presentado": Los alumnos que habiendo optado por la evaluación continua no hayan superado la asignatura mediante las pruebas realizadas durante el cuatrimestre y no se presenten a la prueba o examen final ordinario, tendrán un "No Presentado". Los alumnos que habiendo optado por la evaluación final no se presenten a la prueba o examen final ordinario, tendrán un "No Presentado". En la prueba o examen extraordinario se seguirá el mismo criterio.



CAMBIO EN LA MODALIDAD DE EVALUACIÓN. DE EVALUACIÓN CONTINUA A EVALUACIÓN FINAL:

Los alumnos que hayan optado inicialmente por la "evaluación continua" pueden cambiar a la modalidad de "evaluación final" en cualquier momento previo al examen final (ordinario o extraordinario).





Lo indicado arriba, se ajusta a la "Normativa de Evaluación del Alumnado":

https://www.ehu.eus/es/web/estudiosdegrado-gradukoikasketak/ebaluaziorako-arautegia

Se mantienen los mismos criterios y condiciones indicados para la convocatoria ordinaria.

Material disponible en la plataforma eGela (apuntes, ejercicios, etc.).

Bibliografía básica

- 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

- Blas C. Ruiz, Francisco Gutiérrez, Pablo Guerrero, José E. Gallardo: "Razonando con Haskell. Curso sobre Programación Funcional". Thomson - Paraninfo, 2004

- Simon Thompson: "Haskell. The Craft of Functional Programming" Third Edition. Adison-Wesley, 2011

- Richard Bird; traducción, Ricardo Peña Marí; revisión técnica, María Alpuente Frasnedo, Salvador Lucas Alba: "Introducción a la programación funcional con Haskell" 2ª ed. Prentice Hall, 2000

Bibliografía de profundización

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

Revistas

(No se proponen.)

Direcciones web

- 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/
- Tutorial de Haskell en castellano: http://aprendehaskell.es
- Tutorial de Haskell en inglés: http://learnyouahaskell.com/chapters