RESULTADOS DE APRENDIZAJE



1- Conoce los principales modelos abstractos de cómputo



2- Conoce los problemas NP-completos y las reducciones polinómicas



3- Conoce y emplea diferentes técnicas para abordar problemas difíciles



4- Conoce los problemas indecidibles y los límites de la computación.

TEMA 1 Introducción. Máquinas de Turing. Tesis de Church extendida. Análisis de algoritmos. Notación O.



TEMA 2 Problema SAT. NP-completos. Reducciones polinómicas. La cuestión P ≠ NP.



TEMA 3 Técnicas para abordar problemas difíciles. Soluciones aproximadas. Soluciones aleatorias.



TEMA 4 Límites de la computación. Más sobre problemas indecidibles.

La mayor parte del temario se verá en las horas lectivas en lo que llamamos horas presenciales. El alumnado tendrá que responsabilizarse de trabajar el temario fuera de las horas de clase (horas no presenciales), mediante trabajos prácticos y ejercicios.



En las horas de clase, y de manera sistemática, se desarrollarán trabajos prácticos, momentos de discusión y presentaciones de ejercicios, con el objetivo de incentivar la participación en clase.

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





Evaluación continua

------------------

La evaluación continua se oferta al alumnado que pueda realizar el seguimiento continuo de la asignatura en el marco establecido de dedicación y asistencia a las actividades presenciales. El alumnado puede renunciar a la evaluación continua si dicha renuncia se hace explícita antes de transcurrido el 80% del curso. El alumnado no podrá ser evaluado mediante evaluación continua si no se presenta a todas las actividades evaluables y no cumple los mínimos establecidos para dicha modalidad de evaluación y que se detallan a continuación. En este último caso, pasará a evaluación global.



La evaluación continua se realizará mediante las siguientes pruebas en las que se debe obtener una nota mínima (30%) en cada una de ellas:

- Tres pruebas escritas: 25% + 35% + 20%

El 20% restante de la nota viene determinado por trabajos prácticos de programación.



Las condiciones para aprobar mediante evaluación continua son:

- Obtener una nota mínima del 30% en cada una de las pruebas escritas

- Entrega de todos los trabajos prácticos

- Sumar una nota de al menos 5 tras aplicar las ponderaciones descritas sobre las notas obtenidas en cada prueba o actividad





Evaluación global

------------------

Examen escrito en la convocatoria ordinaria, en el cual entra todo lo trabajado en la asignatura y que debe aprobarse para superar la asignatura (mínimo de 5 sobre 10).

Bibliografía básica

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. “Introducción a la teoría de Autómatas, Lenguajes y Computación: 2ª edición”. Pearson educación, 2002



Michael Sipser. “Introduction to the Theory of Computation: second edition”. PWS Publishing Company, Boston, 2006.



Michael Sipser. “Introduction to the Theory of Computation: third edition”. CENGAGE, 2013.



Susan.H. Rodger and Thomas.W. Finley. “JFLAP: an interactive formal languages ans automata package”. Jones & Bartlett Publishers, 2006.

Bibliografía de profundización

Sanjeev Arora and Boaz Barak. "Computational Complexity: A Modern Approach", Cambridge University Press, 2009

Efim Kinber and Carl Smith. "Theory of Computing: a gentle introduction", Prentice Hall, 2001

J. IBAÑEZ; A. IRASTORZA; A. SANCHEZ. "LOS PROGRAMAS WHILE. Bases para una
teoría de la Computabilidad”. Informe interno. UPV/EHU / LSI / TR 5-96.

J. IBAÑEZ; A. IRASTORZA; A. SANCHEZ. "Técnicas básicas de computabilidad". Informe Interno. UPV/EHU / LSI / TR 3-2003.

J. IBAÑEZ; A. IRASTORZA; A. SANCHEZ. "“Algunas demostraciones de incomputabilidad usando la técnica de diagonalización”. UPV/EHU / LSI / TR 8-2000.