Universidad Pública de Navarra



Año Académico: 2023/2024 | Otros años:  2022/2023  |  2021/2022  |  2020/2021  |  2019/2020 
Graduado o Graduada en Ingeniería Informática por la Universidad Pública de Navarra
Código: 240802 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

Idiomas

Castellano. Algunas lecturas recomendadas en inglés.

Subir

Evaluación

 

Resultados de
aprendizaje		 Actividad de
evaluación		 Peso (%) Carácter
recuperable		 Nota mínima
requerida
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 No
R01, R02 y R10 Trabajo teórico/práctico a realizar en grupo durante las últimas semanas del semestre; presentación ante el profesor. 15% Recuperable mediante reentrega corregida No
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. 40% Recuperable mediante examen de laboratorio 5 sobre 10
R01 a R13 Prueba escrita sobre conceptos de teoría. 40% Recuperable 5 sobre 10

 

Los supuestos prácticos forman la parte de evaluación continua de la asignatura.

Cuando la nota final de la evaluación continua no alcance los 5 puntos sobre 10, el estudiante podrá superar esa parte de evaluación de la asignatura realizando un examen de laboratorio en el periodo de recuperación.

Si la nota del examen o la nota de la evaluación continua no cumple la condición de nota mínima requerida, la calificación final de la asignatura será como máximo 4,5 sobre 10 (suspenso).

Subir

Temario

Tema 1: Clases de complejidad de problemas

  • Concepto de problema
  • Modelos de computación
  • Medidas de complejidad
  • Complejidad de algoritmos

Tema 2: Clases de Complejidad Determinista

  • Reducciones con recursos acotados
  • Clases de complejidad determinista
  • Relaciones entre tiempo y espacio
  • Completitud

Tema 3: Clases de Complejidad Probabilista

  • Concepto de algoritmo probabilista
  • Algoritmos de tipo Montecarlo
  • Algoritmos de tipo Las Vegas
  • Clases de complejidad probabilista

Tema 4: Clases de Complejidad No Determinista

  • Concepto de algoritmo no determinista
  • Espacio no determinista
  • Tiempo no determinista
    • Verificación en tiempo polinómico
    • Problemas NP-completos
    • Teorema de Cook-Levin
  • Clases de complejidad no determinista

Tema 5: Complejidad de Aproximación de Problemas de Optimización

  • Problemas de optimización NP-duros
  • Algoritmos de aproximación en tiempo polinómico
  • Esquemas de aproximación en tiempo polinómico
  • Clases de complejidad de aproximación

Tema 6: Computabilidad

  • Equivalencia computacional entre modelos de computación
  • Lenguajes recursivamente enumerables y lenguajes recursivos
  • Propiedades de lenguajes recursivamente enumerables
  • Problemas algorítmicamente irresolubles

Subir

Programa de prácticas experimentales

El trabajo de laboratorio de la asignatura se articula en tres bloques:

  • Resolución exacta de problemas NP-duros mediante reducción al problema SAT
  • Resolución mediante algoritmos probabilistas
  • Resolución aproximada de problemas de optimización NP-duros

Subir

Bibliografía

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


  • Básica:
  1. T. H. Cormen, Ch. E. Leiserson, R. L. Rivest. "Introduction to Algorithms (2nd ed.)". MIT Press, 2001.
  2. G. Brassard, P. Bratley. "Fundamentos de Algoritmia". Prentice-Hall. 1997.
  3. 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. D. C. Kozen. "The Design and Analysis of Algorithms". Texts and Monographs in Computer Science. Springer-Verlag, 1992.

Subir

Lugar de impartición

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

Subir