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 ] |
Módulo: Mención Computación y Sistemas Inteligentes
Materia: Sistemas Inteligentes
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
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.
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.
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 |
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:
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
Acceda a la bibliografía que el profesorado de la asignatura ha solicitado a la Biblioteca.
Aula asignada por la ETSIIT; laboratorio asignado por el servicio informático de la Universidad.