Saltar al contingut Menu
Mapa
  • Inicio
  • Información
  • Contacto
  • Mapa

Complejidad (COM)

Créditos Dept. Tipo Requisitos
7.5 (6.0 ECTS) CS
  • Optativa para la EI
ADA - Prerequisito para la EI
TC - Prerequisito para la EI

Profesores

Responsable:  (-)
Otros:(-)

Objectivos Generales

La teoría de la complejidad estudia los problemas computacionales entendidos como objetos matemáticos que se pueden analizar, relacionar y clasificar en función de los recursos computacionales requeridos para su resolución. Es el terreno en el que se analizarán los límites de la computación, representada en clases de complejidad, y se dan cita los problemas y algoritmos. El objetivo del curso es profundizar en el conocimiento de la dificultad inherente de los problemas y potenciar la habilidad del estudiante para clasificar problemas respecto a diferentes criterios basados en la consideración de diferentes recursos computacionales.

Objectivos Específicos

Conocimientos

(Información no introducida)

Habilidades

(Información no introducida)

Competencias

(Información no introducida)

Contenidos

Horas estimadas de:

T P L Alt L Ext. Est O. Ext.
Teoria Problemas Laboratorio Otras actividades Laboratorio externo Estudio Otras horas fuera del horario fijado

1. Clases de Complejidad básicas. Tiempo y Espacio.
T      P      L      Alt    L Ext. Est    O. Ext. Total 
3,0 2,0 0 0 0 5,0 0 10,0
Breve repaso de Máquinas de Turing.

Tiempos de computación y espacio de computación.

Definición de las clases de TIME y SPACE.

Clases L, NL, P, NP PSPACE y EXP.

Relaciones entre clases.

2. Reductibilidad y completitud.
T      P      L      Alt    L Ext. Est    O. Ext. Total 
3,0 2,0 0 0 0 5,0 0 10,0
Reducciones.

Propiedades de cierre de las clases respecto a reductibilidades.

Completitud.

3. NP-completitud.
T      P      L      Alt    L Ext. Est    O. Ext. Total 
6,0 4,0 0 0 0 10,0 0 20,0
Problemas naturales:

-Satisfactibilidad de fórmulas booleanas,

-Subgrafos,

-Particiones,

-Recorridos,

-Repartición de recursos.

4. Problemas de optimización. La Jerarquía Polinómica.
T      P      L      Alt    L Ext. Est    O. Ext. Total 
10,0 5,0 0 0 0 15,0 0 30,0
Problemas naturales.
Turing reducibilidad.
La jerarquía polinómica.
Aproximabilidad.

5. Problemas de juegos y de contaje
T      P      L      Alt    L Ext. Est    O. Ext. Total 
6,0 4,0 0 0 0 10,0 0 20,0
PSPACE-completos.

Complejidad de juegos como Go, Ajedrez, Damas.

La permanente.

6. Algoritmos y Clases probabilistas
T      P      L      Alt    L Ext. Est    O. Ext. Total 
6,0 4,0 0 0 0 10,0 0 20,0



Problemas completos.

7. Sistemas interactivos de demoatraciones
T      P      L      Alt    L Ext. Est    O. Ext. Total 
6,0 4,0 0 0 0 10,0 0 20,0
Protoco para la Permanente.
Protocolo para QBF: IP=PSPACE.
Aplicaciones: información zero en criptografía.
Isomorfismo de grafos i no-completitud.


8. Espacio Logarítmico. Computación Paralela.
T      P      L      Alt    L Ext. Est    O. Ext. Total 
6,0 4,0 0 0 0 10,0 0 20,0
Problemas naturales: Acessibilidad en grafos.
Espacio Logarítmico: L y NL.
Modelos de Computación paralela: PRAM y Circuitos.
Clases NC i AC


Total por tipo T      P      L      Alt    L Ext. Est    O. Ext. Total 
46,0 29,0 0 0 0 75,0 0 150,0
Horas adicionales dedicadas a la evaluación 3,0
Total horas de trabajo para el estudiante 153,0

Metodología docente

(-)

Método de evaluación

Problemas:La parte de problemas consistirá en resolver una pequeña lista de problemas que se asignará a cada estudiante (o a cada pequeño grupo de trabajo) al finalizar cada tema de la asignatura. Los estudiantes podrán discutir en clase de problemas las dudas que se les vayan presentando, pero se considera un trabajo personal (o por grupos) que se deberá completar en las horas de estudio. En general serán problemas cuya solución requerirá, aparte de los conceptos que se han ido introduciendo, la ayuda de bibliografía específica. Después de un margen de tiempo razonable (entre 1 y 2 semanas) deberán entregar sus soluciones y presentar en clase de problemas alguna de ellas, si se considera oportuno (cuando se amplíen los conocimientos introducidos en el tema actual y sobre todo cuando el trabajo es en grupo).



Examen:

También habrá un examen final que evaluará si el estudiante ha alcanzado los conocimientos más generales presentados durante todo el curso.



La nota final de la asignatura se calcula a partir de la nota de problemas P y de la nota del examen final E de la forma siguiente:



Nota Final= MAX {(P+E)/2,E}

Bibliografía básica

  • Papadimitriou, C. Computational complexity, Addison Wesley, 1994.
  • Balcázar J. L., Díaz J., Gabarró J. Structural Complexity I, Springer-Verlag, 1995.
  • Sipser, M. Introduction to the theory of computation, 2nd Edition, PWS publishing Company, 2005.

Bibliografía complementaria

(Información no introducida)

Enlaces web

(Información no introducida)

Capacidades previas

(-)


Compartir

 
logo FIB © Facultad de Informática de Barcelona - Contacto - RSS
Esta web utiliza cookies propias para ofrecerle una mejor experiencia y servicio. Si continúa la navegación, entendemos que acepta nuestra política de cookies. Versión clássica Versión móvil