Complejidad Computacional
(Curso Académico 2021 - 2022)

Mostrar Todo Ocultar Todo

• C39 - Capacidad para tener un conocimiento profundo de los principios fundamentales y modelos de la computación y saberlos aplicar para interpretar, seleccionar, valorar, modelar, y crear nuevos conceptos, teorías, usos y desarrollos tecnológicos relacionados con la Informática.
• C41 - 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.

• CG9 - Capacidad para resolver problemas con iniciativa, toma de decisiones, autonomía y creatividad. Capacidad para saber comunicar y transmitir los conocimientos, habilidades y destrezas de la profesión de Ingeniero Técnico en Informática.
• CG10 - Conocimientos para la realización de mediciones, cálculos, valoraciones, tasaciones, peritaciones, estudios, informes, planificación de tareas y otros trabajos análogos de informática, de acuerdo con los conocimientos adquiridos según lo establecido en el apartado 5 de este anexo.

• T1 - Capacidad de actuar autónomamente.
• T2 - Tener iniciativa y ser resolutivo.
• T6 - Capacidad de comunicación efectiva en inglés.
• T9 - Capacidad para argumentar y justificar lógicamente las decisiones tomadas y las opiniones.
• T12 - Capacidad de relación interpersonal.
• T14 - Poseer las habilidades de aprendizaje necesarias para emprender estudios posteriores o mejorar su formación con un cierto grado de autonomía.
• T16 - Capacidad de planificación y organización del trabajo personal.
• T19 - Capacidad de adaptación a los cambios organizativos o tecnológicos.
• T20 - Capacidad de trabajar en situaciones de falta de información y/o con restricciones temporales y/o de recursos.
• T22 - Capacidad para resolver problemas dentro de su área de estudio.
• T25 - Capacidad de análisis, síntesis y evaluación.

- Temas (epígrafes):

- Profesora: Luz Marina Moreno de Antonio
MÓDULO 1.
Tema 1. Modelos de computación
* Máquinas de Turing
* Funciones recursivas primitivas
* Funciones mu-recursivas

Tema 2. Decidibilidad y Reducibilidad
* Medidas y esquemas de codificación
* Problemas No Decidibles
* Reducibilidad
* Jerarquías de Lenguajes y Problemas
* Universalidad
* Tesis de Church-Turing

- Profesor: Jorge Riera Ledesma
MÓDULO 2.
Tema 3. Complejidad
* Las clases P y NP
* NP-completitud. Teorema de Cook
* Complejidad Espacial
* Técnicas de Resolución de problemas difíciles

- Profesorado: Luz Marina Moreno de Antonio / Jorge Riera Ledesma

- Actividades:
Comentar documentación en inglés relacionados con los contenidos de la asignatura
Redactar parte de los trabajos de la asignatura en inglés.

Se utilizarán las clases teóricas para impartir los contenidos teóricos de la materia, y se utilizarán las clases prácticas para afianzar los conocimientos. El resto de las horas se dedicarán a tutorías académicas, la realización de actividades complementarias o exámenes.

Cada tema incluye una lista de actividades que el alumnado tendrá que realizar y que serán evaluadas. Se plantearán prácticas relacionadas con los temas, que el alumnado deberá desarrollar y defender en sesiones de laboratorio.

El trabajo autónomo se distribuye en la realización de actividades complementarias, realización de trabajos, estudio y preparación de las clases o exámenes.

Las actividades presenciales podrán realizarse en las aulas asignadas o de forma online síncrona, según los grupos, rotaciones y horarios establecidos por la ESIT.

Actividades formativas	Horas presenciales	Horas de trabajo autónomo	Total horas	Relación con competencias
Clases teóricas	28,00	0,00	28,0	[T25], [T22], [T12], [C41], [C39]
Clases prácticas (aula / sala de demostraciones / prácticas laboratorio)	18,00	0,00	18,0	[T25], [T22], [T20], [T19], [T16], [T12], [T9], [T2], [T1], [CG10], [CG9], [C41], [C39]
Realización de seminarios u otras actividades complementarias	3,00	6,00	9,0	[T25], [T22], [T20], [T19], [T16], [T14], [T12], [T9], [T6], [T2], [T1], [CG10], [CG9], [C41], [C39]
Realización de trabajos (individual/grupal)	0,00	40,00	40,0	[T25], [T22], [T20], [T19], [T16], [T14], [T12], [T9], [T6], [T2], [T1], [CG10], [CG9], [C41], [C39]
Estudio/preparación de clases teóricas	0,00	10,00	10,0	[T25], [T22], [T20], [T16], [T14], [T9], [T6], [T2], [T1], [C41], [C39]
Preparación de exámenes	0,00	4,00	4,0	[T25], [T22], [T20], [T19], [T16], [T14], [T2], [T1], [C41], [C39]
Realización de exámenes	4,00	0,00	4,0	[T25], [T22], [T20], [T16], [T9], [T2], [T1], [CG9], [C41], [C39]
Asistencia a tutorías	7,00	0,00	7,0	[T25], [T22], [T20], [T19], [T16], [T14], [T12], [T2], [C41], [C39]
Estudio autónomo individual o en grupo	0,00	30,00	30,0	[T25], [T22], [T20], [T19], [T16], [T14], [T12], [T6], [T2], [T1], [CG10], [CG9], [C41], [C39]
Total horas
Total ECTS

[1]  Garey, M.R.; Johnson, D. S. "Computers and Intractability: A Guide to the Theory of NP-Completeness". A Series of Books in the Mathematical Sciences. Ed: Freeman and Co. ISBN:0-7167-1045-5. 2000

[2] Sipser, M. "Introduction to the theory of computation". ISBN: 113318779X. Wadsworth Publishing Co Inc; Edición: 3rd edition. 2012

[3] Cutland, N. "Computability. An introduction to recursive function theory". ISBN:  0-521-22384-9. Cambridge University Press. 1983

[4] Papadimitriou, H. "Computational Complexity". Ed. Addison Wesley. 1994. ISBN: 0201530821

[5] Bovet, D. P.; Crescenzi, P. "Introduction to complexity". Prentice Hall. 1994. ISBN: 0-13-915380-2

[6] Barthélemy, J. P.; Cohen, P. G., Lobstein, A. “Algorithmic complexity and communication problems”. UCL Press Limited. ISBN: 1-85728-451-8

[7] Davis, M. D.; Sigal, R.; Weyuker, E. J."Computability, Complexity, and Languages". Academic Press. 1994. ISBN: 0-12-206382-1

[8] Lewis, H.R.; Papadimitriou, C. H. "Elements of the Theory of Computation". Prentice Hall; 2nd edition. 1998. ISBN: 0-13-273426-5

Campus virtual de la ULL

La Evaluación de la asignatura se rige por el Reglamento de Evaluación y Calificación de la Universidad de La Laguna (BOC de 19 de enero de 2016), o el que la Universidad tenga vigente, además de por lo establecido en la Memoria de Verificación inicial o posteriores modificaciones.


Se aplica la evaluación continua a todo el alumnado matriculado en la asignatura, realizando las siguientes actividades de aprendizaje (que pueden ser individuales o grupales):

1. Realización de prácticas de laboratorio: Se corresponde con el 25% de la calificación final. Cada práctica consta de una o varias sesiones y finaliza con la entrega de la práctica realizada. Estas actividades prácticas tienen lugar a lo largo de las semanas de docencia, durante el cuatrimeste.

2. Realización de informes: Se corresponde con el 25% de la calificación final. Consiste en el desarrollo de trabajos y en su exposición. Tienen lugar a lo largo de las semanas de docencia, durante el cuatrimestre. En estas actividades se evalúa la compresión de la lectura de diversa documentación en lengua inglesa y la escritura en inglés de parte del informe entregado. La calificación de los trabajos incluye un apartado que recoge este aspecto.

3. Realización de la prueba final de la evaluación continua: Se corresponde con el 50% de la calificación final. Consiste en un examen escrito con preguntas teóricas y ejercicios prácticos. El alumnado tendrá la posibilidad de realizarla en cualquiera de las fechas de las convocatorias oficiales.


En cada una de las partes, la calificación se calcula como la media entre las calificaciones obtenidas en los módulo 1 y 2 que aparecen definidos en la tabla Contenidos de la asignatura (apartado 6 de esta guía docente). Es necesario alcanzar una nota media mínima de 3 sobre 10 para que dicha nota sea incluida en el cómputo total de la calificación. Una nota menor a un 3 en una parte significa que esa parte puntúa como 0 en la calificación final. Las notas obtenidas en cada parte de la evaluación continua se guardan para todas las convocatorias del curso académico.


El alumnado que no supere la asignatura mediante la evaluación continua deberá presentar una prueba alternativa, teórico-práctica para evaluar si han adquirido las competencias, conocimientos y resultados de aprendizaje de la asignatura, que será puntuada de 0 a 10.  En esta prueba se tendrá en cuenta, para cada estudiante, las calificaciones obtenidas en las actividades de evaluación continua si no renuncia a las mismas. Para calcular la calificación final mediante la prueba alternativa se aplica la misma ponderación y notas mínimas necesarias que en el caso de la evaluación continua.

Tipo de prueba	Competencias	Criterios	Ponderación
Pruebas objetivas	[T25], [T22], [T20], [T14], [T9], [T2], [T1], [CG9], [C41], [C39]	Se valorará la adecuación de las respuestas a las preguntas planteadas.	50,00 %
Informes memorias de prácticas	[T25], [T22], [T20], [T19], [T16], [T14], [T12], [T9], [T6], [T2], [T1], [CG10], [CG9], [C41], [C39]	Se valorará la presentación de los informes orales o escritos y la adecuación de las soluciones propuestas a los problemas planteados.	25,00 %
Valoración de las actividades prácticas en el laboratorio	[T25], [T22], [T20], [T19], [T16], [T14], [T12], [T9], [T2], [T1], [CG9], [C41], [C39]	Se valorará la presentación de los informes orales o escritos y la adecuación de las soluciones propuestas a los problemas planteados.	25,00 %

En la guía docente, la planificación temporal de la programación sólo tiene la intención de establecer unos referentes u orientaciones para presentar la materia atendiendo a unos criterios cronológicos, sin embargo son solamente a título estimativo, de modo que el profesorado puede modificar - si así lo demanda el desarrollo de la materia - dicha planificación temporal.


La asignatura se imparte en el primer cuatrimestre y la docencia se distribuye en cuatro sesiones semanales para el alumnado.
Las horas de trabajo autónomo se distribuyen de forma uniforme a lo largo del cuatrimestre.

Semana	Temas	Actividades de enseñanza aprendizaje	Horas de trabajo presencial	Horas de trabajo autónomo	Total
Semana 1:	Tema 1	Clases teóricas / Realización seminarios o actividades complementarias / Preparación clases teóricas / Estudio autónomo	3.00	2.00	5.00
Semana 2:	Tema 1	Clases teóricas / Clases prácticas (aula o lab) / Asistencia a tutorías / Preparación clases teóricas / Estudio autónomo	4.00	3.00	7.00
Semana 3:	Tema 1	Clases teóricas / Clases prácticas (aula o lab) / Realización seminarios o actividades complementarias / Realización de trabajos / Estudio autónomo	4.00	6.00	10.00
Semana 4:	Tema 1	Clases teóricas / Clases prácticas (aula o lab) / Realización de trabajos / Preparación clases teóricas / Estudio autónomo	4.00	6.00	10.00
Semana 5:	Temas 1 / 2	Clases teóricas / Clases prácticas (aula o lab) / Asistencia a tutorías / Realización seminarios o actividades complementarias / Preparación clases teóricas / Estudio autónomo	4.00	6.00	10.00
Semana 6:	Tema 2	Clases teóricas / Clases prácticas (aula o lab) / Realización de trabajos / Estudio autónomo	4.00	6.00	10.00
Semana 7:	Tema 2	Clases teóricas / Clases prácticas (aula o lab) / Realización seminarios o actividades complementarias / Realización de trabajos / Estudio autónomo	4.00	7.00	11.00
Semana 8:	Tema 3	Clases teóricas / Clases prácticas (aula o lab) / Realización seminarios o actividades complementarias / Estudio autónomo	4.00	3.00	7.00
Semana 9:	Tema 3	Clases teóricas / Clases prácticas (aula o lab) / Asistencia a tutorías / Preparación clases teóricas / Estudio autónomo	4.00	6.00	10.00
Semana 10:	Tema 3	Clases teóricas / Clases prácticas (aula o lab) / Realización seminarios o actividades complementarias / Preparación clases teóricas / Estudio autónomo	3.00	6.00	9.00
Semana 11:	Tema 3	Clases teóricas / Clases prácticas (aula o lab) / Asistencia a tutorías / Realización de trabajos / Preparación clases teóricas / Estudio autónomo	3.00	6.00	9.00
Semana 12:	Tema 3	Clases teóricas / Clases prácticas (aula o lab) / Realización seminarios o actividades complementarias / Realización de trabajos / Estudio autónomo	4.00	6.00	10.00
Semana 13:	Tema 3	Clases teóricas / Clases prácticas (aula o lab) / Realización de trabajos / Preparación clases teóricas / Estudio autónomo	3.00	6.00	9.00
Semana 14:	Tema 3	Clases teóricas / Asistencia a tutorías / Realización seminarios o actividades complementarias / Realización de trabajos / Estudio autónomo	4.00	6.00	10.00
Semana 15:	Tema 3	Clases prácticas (aula o lab) / Realización seminarios o actividades complementarias / Realización de trabajos /  Estudio autónomo	4.00	7.00	11.00
Semana 16 a 18:	Evaluación	Evaluación y trabajo autónomo del alumno para la preparación de la evaluación: Realización de exámenes / Preparación de exámenes	4.00	8.00	12.00
Total			60.00	90.00	150.00