Universidad Pública de Navarra



Año Académico: 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 expositivas
30 (aula)
0
A-2 Sesiones prácticas en grupos reducidos
30 (laboratorio)
0
A-3 Tutorías en grupos muy reducidos
3 (consultas individuales)
0
A-4 Actividades de evaluación
3 (exámenes)
0
A-5 Estudio autónomo
0
20 (estudio de teoría)
A-6 Elaboración de trabajos y/o proyectos y escritura de memorias
0
7,5
A-7 Programación/experimentación u otros trabajos en ordenador/laboratorio
0 49 (para completar tareas de laboratorio)
A-8 Resolución de problemas, ejercicios y otras actividades de aplicación
0 7,5
Total
66
84

Subir

Evaluación

Resultado de aprendizaje Sistema de evaluación Peso (%) Carácter recuperable
 R01 y R02 Trabajo individual a realizar progresivamente durante las sesiones dedicadas al bloque 1 de la parte práctica de la asignatura.   Nota mínima para que pondere en la calificación final: 5 sobre 10.  20% 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.  10% No recuperable
 R01, R02 y R10 Realización individual de cada supuesto práctico propuesto al final de los bloques temáticos 1, 2 y 3 de la parte práctica de la asignatura.   Nota mínima para que pondere en la calificación final: 5 sobre 10 en cada supuesto práctico.   Nota mínima para poder optar a recuperación: 4 sobre 10 en cada supuesto práctico.  30% Recuperable entregando el trabajo corregido segúnindicaciones y fechas establecidas por el profesor.
 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

 

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, la nota final de la asignatura será la suma ponderada de la puntuaciones de prácticas (incluido el trabajo no recuperable) y del examen, más la nota conseguida en asistencia y motivación.
  • En el caso de haber suspendido tanto el examen de teoría como los supuestos prácticos, la nota final será la suma ponderada de las notas de prácticas (incluido el trabajo no recuperable) y del examen.
  • En el caso de haber superado únicamente el examen o los supuestos prácticos, la nota que se traslade al acta será la obtenida en la parte no superada.

Subir

Temario

Tema 1: Complejidad de algoritmos

- Tipos de complejidad

- Eficiencia algorítmica

- Análisis de eficiencia algorítmica

Tema 2: Algoritmos probabilistas

- Algoritmos de tipo Montecarlo

- Algoritmos de tipo Las Vegas

Tema 3: Computaciones en tiempo polinómico

- Máquinas de Turing

- Clases P, NP y BPP

Tema 4: NP-completitud

- Reducciones polinómicas

- Problemas NP-completos

- Teorema de Cook-Levin

- Demostraciones de NP-completitud

- Taxonomía de clases de complejidad

Tema 5: Algoritmos de aproximación

- Problemas de aproximación absoluta

- Problemas de aproximación relativa

- Esquemas de aproximación

Tema 6: Computabilidad

- Equivalencia computacional entre modelos

- 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