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 |
Resultados de aprendizaje |
Actividad de evaluación |
Peso (%) | Carácter recuperable |
Nota mínima requerida |
---|---|---|---|---|
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 | No |
R01, R02 y R10 | Trabajo teórico/práctico a realizar en grupo durante las últimas semanas del semestre; presentación ante el profesor. | 15% | Recuperable mediante reentrega corregida | No |
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. | 40% | Recuperable mediante examen de laboratorio | 5 sobre 10 |
R01 a R13 | Prueba escrita sobre conceptos de teoría. | 40% | Recuperable | 5 sobre 10 |
Los supuestos prácticos forman la parte de evaluación continua de la asignatura.
Cuando la nota final de la evaluación continua no alcance los 5 puntos sobre 10, el estudiante podrá superar esa parte de evaluación de la asignatura realizando un examen de laboratorio en el periodo de recuperación.
Si la nota del examen o la nota de la evaluación continua no cumple la condición de nota mínima requerida, la calificación final de la asignatura será como máximo 4,5 sobre 10 (suspenso).
Tema 1: Clases de complejidad de problemas
Tema 2: Clases de Complejidad Determinista
Tema 3: Clases de Complejidad Probabilista
Tema 4: Clases de Complejidad No Determinista
Tema 5: Complejidad de Aproximación de Problemas de Optimización
Tema 6: Computabilidad
El trabajo de laboratorio de la asignatura se articula en tres bloques:
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.