Universidad Pública de Navarra



Año Académico: 2021/2022 | Otros años:  2020/2021 
Graduado o Graduada en Ingeniería Informática por la Universidad Pública de Navarra (Programa Internacional)
Código: 250802 Asignatura: COMPLEJIDAD Y COMPUTABILIDAD
Créditos: 6 Tipo: Optativa Curso: 4 Periodo: 2º S
Departamento: Estadística, Informática y Matemáticas
Profesorado:
ALDAZ ZARAGUETA, MIGUEL ANGEL (Resp)   [Tutorías ]

Partes de este texto:

 

Módulo/Materia

Módulo: Mención Computación y Sistemas Inteligentes

Materia: Sistemas Inteligentes

Subir

Descripción/Contenidos

La asignatura tiene un doble objetivo: enriquecer los conocimientos del estudiantes sobre complejidad y realizar una introducción a la computabilidad.
 
La parte dedicada a complejidad complementa el enfoque cuantitativo presentado al estudiante en asignaturas previas con un enfoque de naturaleza cualitativa. Esa parte toma como punto de partida los conocimientos sobre análisis de algoritmos deterministas adquiridos en asignaturas previas por el estudiante y amplia esos conocimientos con la introducción de algoritmos probabilistas como nueva técnica de solución de problemas. En paralelo, se ensayan y aplican tecnicas para analizar la complejidad de ambos tipos de algoritmos.
 
El estudio cualitativo de la complejidad considera tres tipos de modelos de computación: determinista, probabilista (con error acotado) y no determinista. Considerando cada modelo, clasifica los problemas como tratables o intratables según sea posible o no resolver cualquier instancia de un problema mediante un algoritmo que realice una cantidad polinomial de operaciones respecto al tamaño de la instancia. Como resultado,  quedan definidas las clases P, BPP y NP, y el estudio que sigue se centra en dar sentido a conceptos como el de problema completo dentro de una clase.
 
En la parte de computabilidad se hace una introducción clásica a los resultados más elementales pero relevantes. Operando en el contexto de lenguajes como conjuntos de cadenas, se demuestra que hay lenguajes que no pueden ser reconocidos mediante algoritmos y que si se permite que el mecanismo de reconocimiento sólo asegure respuesta en el caso de que sea afirmativa, entonces hay lenguajes que pueden ser reconocidos de esa forma pero no mediante algoritmos. Se realizan demostraciones que presentan ejemplos de lenguajes de ambos tipos. Se estudia la decibilidad de propiedades definidas sobre lenguajes.
 
Por otra parte, se ha hecho esfuerzo en convertir una asignatura tradicionalmente teórica en una asignatura de métodos aplicados. Por esa razón, el trabajo en las sesiones de laboratorio tiene una importancia fundamental tanto para la formación del estudiante como para su evaluación.
 
 

Subir

Competencias genéricas

Competencias generales:

 

G4 - Capacidad para definir, evaluar y seleccionar plataformas hardware y software para el desarrollo y la ejecucio¿n de sistemas, servicios y aplicaciones informa¿ticas.

 

G9 - Capacidad para resolver problemas con iniciativa, toma de decisiones, autonomi¿a y creatividad. Capacidad para saber comunicar y transmitir los conocimientos, habilidades y destrezas de la profesio¿n de Ingeniero Te¿cnico en Informa¿tica.


G10 - Conocimientos para la realizacio¿n de mediciones, ca¿lculos, valoraciones, tasaciones, peritaciones, estudios, informes, planificacio¿n de tareas y otros trabajos ana¿logos de informa¿tica.


G11 - Capacidad para analizar y valorar el impacto social y medioambiental de las soluciones te¿cnicas, comprendiendo la responsabilidad e¿tica y profesional de la actividad del Ingeniero Te¿cnico en Informa¿tica.

 

T1 - Capacidad de análisis y síntesis

 

T3 - Comunicación oral y escrita

 

T4 - Resolución de problemas

 

T7 - Razonamiento crítico

 

T8 - Aprendizaje autónomo

Subir

Competencias específicas

C1 - Capacidad para interpretar, seleccionar, valorar, modelar, y crear nuevos conceptos, teorías, usos y desarrollos tecnológicos relacionados con la informática en base a un profundo conocimiento de los principios y modelos fundamentales de computación.

 

C3 - Capacidad para evaluar la complejidad computacional de un problema, conocer estrategias algorítmicas que puedan conducir a su resolución, y recomendar, desarrollar e implementar aquella que garantice el mejor rendimiento de acuerdo con los requisitos establecidos.

 

Subir

Resultados aprendizaje

R01 - Analizar la complejidad de algoritmos deterministas y probabilistas.
R02 - Aplicar algoritmos probabilistas para obtener soluciones en tiempo polinomial o subexponencial a ciertos problemas.

R03 - Comprender el valor de las máquinas de Turing como modelo universal de computación determinista, así como sus variantes no-determinista y probabilista.

R04 - Conocer la equivalencia computacional entre las tres variantes de máquinas de Turing, y entre éstas y el modelo de computador de Von Neumann.

R05 - Comprender el significado de las clases de complejidad P, NP y BPP.

R06 - Saber aplicar el concepto de reducción en tiempo polinomial como medio para establecer relaciones entre problemas.

R07 - Comprender los conceptos de problema completo y problema difícil en relación a una clase de complejidad.

R08 - Conocer problemas NP-completos.

R09 - Conocer los conceptos de problema de aproximación absoluta y problema de aproximación relativa referidos a un problema de optimización.

R10 - Conocer y ser capaz de aplicar esquemas algorítmicos de aproximación que permitan obtener aproximaciones relativas arbitrariamente buenas a soluciones de problemas de optimización.

R11 - Conocer la existencia de lenguajes no recursivamente enumerables y de lenguajes no recursivos.

R12 - Saber aplicar los teoremas sobre propiedades de lenguajes recursivamente enumerables para extraer conclusiones sobre su naturaleza no recursiva.

R13 - Conocer la existencia de problemas algorítmicamente irresolubles.

Subir

Metodología

Metodología - Actividad
Horas Presenciales
Horas no presenciales
A-1 Clases magistrales
30 (aula)
0
A-2 Sesiones prácticas en grupos reducidos
15 (laboratorio)
0
A-3 Aprendizaje basado en problemas y/o casos en grupos reducidos
7,5 (laboratorio)
 
A-4 Tutorías en grupos muy reducidos
3 (consultas individuales)
0
A-5 Actividades de evaluación
4,5 (exámenes)
0
A-6 Estudio autónomo
0
30 (estudio de teoría)
A-7 Elaboración de trabajos y/o proyectos y escritura de memorias
0
15
A-8 Programación/experimentación u otros trabajos en ordenador/laboratorio
0 22,5 (para completar tareas de laboratorio)
A-9 Resolución de problemas, ejercicios y otras actividades de aplicación
0 15
A-10 Preparación de presentaciones de trabajos,proyectos, etc.
0
7,5
Total
60
90

Subir

Evaluación

Resultado de aprendizaje Sistema de evaluación Peso (%) Carácter recuperable
 R01 y R02 Trabajo teórico/práctico a realizar en grupo durante las últimas semanas del semestre; presentación ante el profesor.   Nota mínima para que pondere en la calificación final: 4 sobre 10.  15% No recuperable
 R01 a R13 Asistencia a sesiones de laboratorio y participación activa en la asignatura.   Intervención y aportaciones. Entrega de actividades voluntarias.  5% No recuperable
 R01, R02 y R10 Realización individual de cada supuesto práctico propuesto al final de los bloques temáticos de la parte práctica de la asignatura.   Nota mínima para que pondere en la calificación final: 4 sobre 10 en cada supuesto práctico.  40% Recuperable mediante examen de laboratorio
 R01 a R13 Prueba escrita sobre conceptos de teoría.   Nota mínima para superar la asignatura: 5 sobre 10.  40% Recuperable mediante prueba escrita

La nota final que corresponde a los supuestos prácticos recuperables es el resultado de calcular la media de las notas obtenidas en los diferentes trabajos propuestos; al calcular esa media se tendrá en cuenta la condición individual de nota mínima para ponderación de cada supuesto práctico.

Cuando la nota final de los supuestos prácticos recuperables así calculada no alcance los 5 puntos, el estudiante podrá realizar un examen de laboratorio en el periodo de recuperación para superar esa parte de evaluación de la asignatura.

Sobre la puntuación que se traslada al acta de la asignatura:

  • En el caso de haber superado tanto el examen de teoría como los supuestos prácticos de realización individual, la nota final de la asignatura será la suma ponderada de los supuestos (40%), del examen de teoría (40%), de la nota conseguida en asistencia y participación (5%) y del trabajo en grupo (15%).
  • En el caso de haber suspendido tanto el examen de teoría como la parte práctica, la nota final será la media aritmética de la nota obtenida en el examen de teoría y en la parte práctica.
  • En el caso de haber superado únicamente el examen de teoría o únicamente la parte práctica, la nota que se traslade al acta será la obtenida en la parte no superada.

Subir

Temario

Tema 1: Clases de complejidad de problemas

- Clases de problemas

- Modelo de computación determinista

- Medidas de complejidad

- Clases de complejidad determinista

Tema 2: Complejidad probabilista

- Concepto de algoritmo probabilista

- Algoritmos de tipo Montecarlo

- Algoritmos de tipo Las Vegas

- Clases de complejidad probabilista

Tema 3: Resolución y verificación en tiempo polinómico

- Verificación en tiempo polinómico

- Problemas NP-completos

- Teorema de Cook-Levin

- Demostraciones de NP-completitud

- Taxonomía de clases de complejidad

Tema 4: Complejidad de aproximación

- Problemas de aproximación

- Esquemas de aproximación en tiempo polinómico

- Clases de complejidad de aproximación

Tema 5: Computabilidad

- Equivalencia computacional entre modelos de computación

- Lenguajes recursivamente enumerables y lenguajes recursivos

- Propiedades de lenguajes recursivamente enumerables

- Problemas algorítmicamente irresolubles

Subir

Bibliografía

Acceda a la bibliografía que el profesorado de la asignatura ha solicitado a la Biblioteca.


  • Básica:
  1. G. Brassard, P. Bratley. "Fundamentos de Algoritmia". Prentice-Hall. 1997.
  2. J. E. Hopcroft, R. Motwani, J. D. Ullman. "Introducción a la Teoría de Autómatas, Lenguajes y Computación (2ª ed.)". Addison-Wesley, 2001.
  • Complementaria:
  1. T. H. Cormen, Ch. E. Leiserson, R. L. Rivest. "Introduction to Algorithms (2nd ed.)". MIT Press, 2001.
  2. D. C. Kozen. "The Design and Analysis of Algorithms". Texts and Monographs in Computer Science. Springer-Verlag, 1992.

Subir

Idiomas

Castellano. Algunas lecturas recomendadas en inglés.

Subir

Lugar de impartición

Aula asignada por la ETSIIT; laboratorio asignado por el servicio informático de la Universidad.

Subir