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

Curso 2022/2023
Fecha de aprobación: 14/06/2022

Grado

Grado en Ingeniería Informática

Rama

Ingeniería y Arquitectura

Módulo

Formación de Especialidad 1: Computación y Sistemas Inteligentes

Materia

Modelos de Computación

Curso

3

Semestre

2

Créditos

6

Tipo

Obligatoria

Profesorado

Teórico

Serafín Moral Callejón. Grupo: A

Práctico

  • Serafín Moral Callejón Grupo: 3
  • Gabriel Navarro Garulo Grupos: 1 y 2

Tutorías

Serafín Moral Callejón

Email
  • Primer semestre
    • Lunes de 11:00 a 13:00 (D4 Etsiit)
    • Martes de 11:00 a 13:00 (D4 Etsiit)
    • Jueves de 11:00 a 13:00 (D4 Etsiit)
  • Segundo semestre
    • Lunes de 11:00 a 13:00 (D4 Etsiit)
    • Martes de 11:00 a 13:00 (D4 Etsiit)
    • Miércoles de 11:00 a 13:00 (D4 Etsiit)

Gabriel Navarro Garulo

Email
  • Primer semestre
    • Viernes de 09:00 a 15:00 (Nd Etsiit)
  • Segundo semestre
    • Viernes de 09:00 a 15:00 (D16 Etsiit)

Prerrequisitos y/o Recomendaciones

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.

Breve descripción de contenidos (Según memoria de verificación del Máster)

  • Máquinas Turing.
  • Máquinas RAM.
  • Otros Modelos de Cómputo.
  • Computabilidad de problemas.
  • NP Completitud.

Competencias

Competencias Generales

  • CG09. Capacidad para resolver problemas con iniciativa, toma de decisiones, autonomía y creatividad. Capacidad para saber comunicar y transmitir los conocimientos, habilidades y destrezas de la profesión de Ingeniero Técnico en Informática.

Resultados de aprendizaje (Objetivos)

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

Programa de contenidos Teóricos y Prácticos

Teórico

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

Práctico

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.

Bibliografía

Bibliografía fundamental

  • 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, 2ª Ed. Addison Wesley (2002)
  • 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 (1994)
  • C. Moore, S. Mertens. The Nature of Computation. Oxford University Press (2011)

Bibliografía complementaria

  • 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. Course Technology (2005)

Metodología docente

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

Evaluación (instrumentos de evaluación, criterios de evaluación y porcentaje sobre la calificación final)

Evaluación Ordinaria

Porcentajes de evaluación

Actividades Formativas

Ponderación

Parte Teórica

50.00%

Parte Práctica

50.00%

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.

Evaluación Extraordinaria

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.

Evaluación única final

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.