Guía docente de la asignatura

Modelos Avanzados de Computación (Especialidad Computación y Sistemas Inteligentes)

Curso 2021 / 2022
Fecha última actualización: 21/06/2021
Fecha de aprobación: 21/06/2021

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

Teoría

  • Serafín Moral Callejón. Grupos: A

Prácticas

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

Tutorías

Serafín Moral Callejón

smc@ugr.es
  • Jueves de 11:00 a 13:00 (D04 Etsiit)
  • Lunes de 11:00 a 13:00 (D04 Etsiit)
  • Martes de 11:00 a 13:00 (D04 Etsiit)

Gabriel Navarro Garulo

gnavarro@ugr.es
  • Primer semestre
    • Jueves de 9:30 a 12:30 (D14 Etsiit)
    • Miércoles de 11:30 a 14:30 (D14 Etsiit)
  • Segundo semestre
    • de 9:00 a 15:00 (D14 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 Grado)

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

Competencias asociadas a materia/asignatura

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)

 

Enlaces recomendados

  • Complejidad de Kolmogorov: http://www.hutter1.net/ait.htm

  • Libro de Ahora-Barak: http://www.cs.princeton.edu/theory/index.php/Compbook/Draft#model

  • Página web sobre complejidad de problemas de optimización: http://www.nada.kth.se/~viggo/wwwcompendium/

  • Página de Lance Fortnow sobre complejidad: http://blog.computationalcomplexity.org/

  • Página de Peter Cholak sobre computabilidad: http://www.nd.edu/~cholak/computability/computability.html

  • Página dedicada a Alan Turing: http://www.turing.org.uk/turing/

  • Libro de J. MacCormick con programas Python: https://press.princeton.edu/titles/11348.html

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

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

Evaluación ordinaria

 

 

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.

Información adicional

ESCENARIO A (ENSEÑANZA-APRENDIZAJE PRESENCIAL Y TELE-PRESENCIAL)

Horario (Según lo establecido en el POD)

  • Serafín Moral Callejón
    • Lunes 11:00 - 13:00 D04 Etsiit
    • Martes 11:00 - 13:00 D04 Etsiit
    • Miércoles 11:00 - 13:00 D04 Etsiit
  • Gabriel Navarro Garrulo
    • Jueves 16:00 - 17:30 D14 Etsiit
    • Viernes 9:00 - 13:30 D14 Etsiit

 

Herramientas para la atención tutorial (Indicar medios telemáticos para la atención tutorial)

La atención tutorial se realizará preferentemente online mediante las plataformas y herramientas que recomiende la Universidad de Granada.

Medidas de adaptación de la evaluación (Instrumentos, criterios y porcentajes sobre la calificación)

El profesorado de la asignatura adaptará, total o parcialmente, los contenidos para su impartición online en los horarios establecidos por el centro.

Esta adaptación estará sujeta a los condicionantes de infraestructura y medios que existan en el momento de adopción del Escenario A.

Se utilizarán las plataformas y herramientas proporcionadas por la Universidad de Granada.

Los contenidos de la asignatura estarán disponibles mediante vídeos de lecciones grabadas para que los estudiantes los puedan visualizar y estudiar a su conveniencia (aparte de las clases normales en su horario habitual).

 

Evaluación ordinaria

Para todas aquellas actividades evaluables que no se puedan realizar de manera presencial, se aplicará lo establecido en el escenario B. Se priorizará la realización del examen final de teoría de forma presencial.

Evaluación extraordinaria

  • Si el examen de teoría no se puede realizar de manera presencial, se aplicará lo establecido en el escenario B.

  • Si la evaluación de la parte práctica no se puede realizar de manera presencial, se aplicará lo establecido en el escenario B.

No se cambiarán las ponderaciones

Evaluación única final

  • Si el examen de teoría no se puede realizar de manera presencial, se aplicará lo establecido en el escenario B.
  • Si la evaluación de la parte práctica no se puede realizar de manera presencial, se aplicará lo establecido en el escenario B.

No se cambiarán las ponderaciones

ESCENARIO B (SUSPENSIÓN DE LA ACTIVIDAD PRESENCIAL)

Horario (Según lo establecido en el POD)

Serafín Moral Callejón

Lunes 11:00 - 13:00 D04 Etsiit

Martes 11:00 - 13:00 D04 Etsiit

Miércoles 11:00 - 13:00 D04 Etsiit

Gabriel Navarro Garrulo

Jueves 16:00 - 17:30 D14 Etsiit

Viernes 9:00 - 13:30 D14 Etsiit

Herramientas para la atención tutorial (Indicar medios telemáticos para la atención tutorial)

La atención tutorial se realizará online mediante las plataformas y herramientas que recomiende la Universidad de Granada.

Medidas de adaptación de la evaluación (Instrumentos, criterios y porcentajes sobre la calificación)

El profesorado de la asignatura adaptará, total o parcialmente, los contenidos para su impartición online preferentemente en los horarios establecidos por el centro.

Esta adaptación estará sujeta a los condicionantes de infraestructura y medios que existan en el momento de adopción del Escenario B.

Se utilizarán las plataformas y herramientas proporcionadas por la Universidad de Granada.

Los contenidos de la asignatura estarán disponibles mediante vídeos de lecciones grabadas para que los estudiantes los puedan visualizar y estudiar a su conveniencia (aparte de las clases normales en su horario habitual).

Evaluación ordinaria

La evaluación de la teoría y prácticas se realizará mediante un examen multi-pregunta utilizando las herramientas y plataformas provistas por la Universidad de Granada. sobre los contenidos de la materia impartida.

La parte práctica se evaluará de forma continua mediante presentaciones telemáticas de los estudiantes y entregas de trabajos y ejercicios.

No se cambiarán las ponderaciones

Evaluación extraordinaria

La evaluación de la teoría y prácticas se realizará mediante un examen multi-pregunta utilizando las herramientas y plataformas provistas por la Universidad de Granada. sobre los contenidos de la materia impartida.

No se cambiarán las ponderaciones

Evaluación única final

La evaluación de la teoría y prácticas se realizará mediante un examen multi-pregunta utilizando las herramientas y plataformas provistas por la Universidad de Granada. sobre los contenidos de la materia impartida.

No se cambiarán las ponderaciones