Responsable: | (-) |
Otros: | (-) |
Créditos | Dept. | Tipo | Requisitos |
---|---|---|---|
7.5 (6.0 ECTS) | CS |
|
ADA
- Prerequisito para la EI TC - Prerequisito para la EI |
Responsable: | (-) |
Otros: | (-) |
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.
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 |
|
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. |
|
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. |
|
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. |
|
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. |
|
T | P | L | Alt | L Ext. | Est | O. Ext. | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
6,0 | 4,0 | 0 | 0 | 0 | 10,0 | 0 | 20,0 | |||
Problemas completos. |
|
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. |
|
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 |
(-)
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}
(-)