Guía docente de Modelos Avanzados de Computación (Especialidad Computación y Sistemas Inteligentes) (296113D)

Se recomienda la superación de los contenidos y adquisición de competencias de las materias de formación básica y de rama. En particular, es esencial haber superado la asignatura de 'Lógica y Métodos Discretos' y tener un grado de madurez suficiente para entender el lenguaje matemático y seguir razonamientos abstractos complejos.

• Máquinas Turing
• Máquinas RAM
• Otros modelos de cómputo
• Computabilidad de problemas
• NP Completitud

Objetivos Formativos Particulares

• Conocer el modelo de la Máquina de Turing, su alcance y limitaciones.
• Conocer otros modelos de computación (máquinas RAM, lenguajes algorítmicos sencillos, modelos funcionales) y las relaciones existentes (tesis de Church-Turing).
• Conocer los conceptos de funciones recursivas y parcialmente recursivas.
• Conocer los conceptos de conjuntos recursivos y recursivamente enumerables. Problemas decidibles y semidecidibles.
• Comprender el teorema de Rice y sus implicaciones prácticas.
• Relacionar la computabilidad con la incompletitud de las matemáticas.
• Adquirir madurez matemática. Conocer la técnica de diagonalización para demostraciones.
• Conocer las clases de complejidad computacional más importantes y las relaciones entre ellas.
• Comprender la NP-completitud. Ser capacer de comprobar si un problema es NP-completo.
• Conocer las clases de complejidad para aproximar problemas. Saber clasificar problemas concretos en dichas clases.
• Conocer la jerarquía polinómica. Saber ubicar problemas dentro de dicha jerarquía. Conocer problemas PESPACIO completos.
• Conocer y relacionar los modelos de computación paralela: máquinas PRAM y circuitos booleanos.
• Conocer las clases de complejidad de resolver los problemas en paralelo. Determinar problemas P-completos. Relacionar la complejidad en tiempo paralelo con la complejidad en espacio secuencial.

Objetivos Formativos de Carácter General

• Ser capaz de tener un conocimiento profundo de los principios fundamentales y modelos de la computación y saberlos aplicar para interpretar, seleccionar, valorar, modelar, y crear nuevos conceptos, teorías, usos y desarrollos tecnológicos.

• Tema 1: Máquinas de Turing. Funciones y lenguajes calculables
• Tema 2: Otros Modelos de Cálculo. Tesis de Church Turing
• Tema 3: Clases de Complejidad
• Tema 4: NP-Completitud
• Tema 5: Complejidad de problemas de optimización aproximados
• Tema 6: Otras clases de complejidad: La jerarquía polinómica, PESPACIO y P.

Resolución de problemas de los siguientes temas:

• Relación 1: Máquinas de Turing
• Relación 2: Computabilidad
• Relación 3: Equivalencia de de Modelos de Computación
• Relación 4: Clases de Complejidad
• Relación 5: Demostración de NP-completitud
• Relación 6: Complejidad de problemas aproximados
• Relación 7: Problemas PESPACIO completos y P-completos

Seminarios:

• Seminario 1: Programas en Python sobre computabilidad del libro “What Can Be Computed” (J. MacCormick)
• Seminario 2: El problema P – NP. Importancia, implicaciones filosóficas y prácticas.

• M.D. Davis, R. Sigal, E.J. Weyujer. Computability, Complexity, and Languages (2nd. Ed.): Fundamentals of theoretical Computer Science. Academic Press (1994)
• J.E. Hopcroft, R. Motwani, J.D. Ullman. Introducción a la Teoría de Autómatas, Lenguajes y Programación, 3ª Ed. Addison Wesley (2010)
• M.R. Garey, D.S. Johson. Computers and Intractability. A Guide to the theory of NP-Completeness. Freeman (1979)
• C.H. Papadimitriou. Computational Complexity. Addison Wesley (1995)
• C. Moore, S. Mertens. The Nature of Computation. Oxford University Press (2011)

• S. Arora, B. Barak. Computational Complexity: A Modern Approach.Cambridge University Press (2009)
• G. Ausiello, P. Creszendi et al. Complexity and Approximation. Springer-Verlag, Berlin (1999)
• R. Greenlaw, H.J. Hoover, W.L. Ruzzo. Limits to Parallel Computation: P-Completeness Theory (1995) Oxford University Press.
• J. MacCormick. What Can Be Computed (2018) Princeton University Press.
• M. Sipser. Introduction to the Theory of Computation, 2nd Ed. (2005) Course Technology

• Complejidad de Kolmogorov
• Libro de Ahora-Barak
• Página de Lance Fortnow sobre complejidad
• Página dedicada a Alan Turing
• Libro de J. MacCormick con programas Python
• The Complexity Zoo

• MD01. Lección Magistral (Clases Teóricas-Expositivas) 
• MD02. Actividades Prácticas (Resolución de Problemas, Resolución de Casos Prácticos, Desarrollo de Proyectos, Prácticas en Laboratorio, Taller de Programación, Aula de Informática, Prácticas de Campo). 
• MD03.  Seminarios (Debates, Demos, Exposición de Trabajos Tutelados, Conferencias, Visitas Guiadas, Monografías). 
• MD04. Actividades no presenciales Individuales. 
• MD05. Actividades no presenciales Grupales. 
• MD06. Tutorías Académicas. 

Porcentajes de evaluación

La evaluación continua de los estudiantes se llevará a cabo con los siguientes apartados:

• Para la parte teórica se realizará un examen final con una valoración del 50% de la asignatura. Para superar la asignatura se requerirá un mínimo de 3.5 en esta parte. En el caso de que un estudiante no supere esa nota y la media de la teoría y práctica sea superior a 4.5, la calificación final de la asignatura será de 4.5.
• Para la parte práctica se realizarán prácticas de resolución de problemas, y se valorarán a través de pequeñas pruebas de clase, entregas y defensas realizadas por los alumnos, así como la participación en clase. La ponderación de este bloque será del 50%.

La calificación global corresponderá por tanto a la puntuación ponderada de los diferentes aspectos y actividades que integran el sistema de evaluación. Por tanto, el resultado de la evaluación será una calificación numérica obtenida mediante la suma ponderada de las calificaciones correspondientes a una parte teórica, una parte práctica que incluye la participación en los seminarios y clases teórico/prácticas.

En la evaluación extraordinaria habrá un examen de teoría y problemas, cada parte ponderará con un 50% en la nota final. El alumno que haya realizado evaluación continua en ese mismo curso y haya superado una de las partes, teoría o prácticas, podrá pedir examinarse solo de la parte no superada.

De acuerdo a lo establecido en la normativa de evaluación y de calificación de los estudiantes de la Universidad de Granada vigente, la evaluación será preferentemente continua. No obstante, el estudiante que no pueda acogerse a dicho sistema por motivos laborales, estado de salud, discapacidad, programas de movilidad o cualquier otra causa debidamente justificada podrá acogerse a la evaluación única final. Para ello deberá solicitarlo al Director del Departamento o al Coordinador del Máster en las dos primeras semanas de impartición de la asignatura o, excepcionalmente, en las dos primeras semanas tras la matriculación en la asignatura.

Esta modalidad de evaluación se realizará en un único acto académico en la fecha establecida por el Centro y consistirá en Un examen escrito (evaluado de 0 a 10) que incluirá preguntas tanto de tipo teórico como práctico que garanticen que el alumno ha adquirido la totalidad de las competencias descritas en esta misma guía docente.