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 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 |
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:
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
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.