Complejidad Computacional
(Curso Académico 2026 - 2027)

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

MÓDULO 1. Profesora: Luz Marina Moreno de Antonio
Tema 1. Modelos de computación
* Máquinas de Turing
* Funciones recursivas primitivas
* Funciones parcialmente recursivas (o 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

MÓDULO 2. Profesor: Jorge Riera Ledesma
Tema 3. Complejidad
* Las clases P y NP
* NP-completitud. Teorema de Cook-Levin
* Demostración de los 6 primeros problemas NP-completos
* 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 impartirán clases teóricas donde el profesorado hará una exposición oral de los contenidos teóricos de la materia, y se utilizarán las clases prácticas en aula y laboratorio para afianzar los conocimientos, mediante resolución de problemas y casos prácticos. El resto de las horas presenciales 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 de forma autónoma y defender en sesiones de laboratorio.

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

La IA puede ser usada únicamente como una herramienta de apoyo para la comprensión de la asignatura y debe hacerse referencia de su uso. En ningún caso, la evaluación de la asignatura se basará en contenido generado mediante IA.

En caso de situaciones de riesgo derivadas de fenómenos meteorológicos adversos, se seguirán las siguientes directrices:
- Si se declara en la Universidad de La Laguna nivel 2 (amarillo), las actividades docentes se desarrollarán conforme a las directrices marcadas por la Universidad de La Laguna.
- Si se declara en la Universidad de La Laguna nivel 3 (naranja) o 4 (rojo), se suspenderán las actividades docentes presenciales, y previa información al alumnado por los canales disponibles, se actuará para garantizar la continuidad del aprendizaje y la atención al alumnado mientras se mantengan estos niveles de alerta.

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

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

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

Sipser, M. "Introduction to the theory of computation". ISBN: 978-1133187813. Editorial: Course Technology Inc; Edición: International edition. 2012

Arora, S., Barak, B. "Computational Complexity: A Modern Approach". Editor Cambridge University Press, 2009. ISBN: 1139477366, 9781139477369

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

Boolos, G.S., Burgess J.P., Jeffrey R.C. "Computability and Logic". Editorial: Cambridge University Press. 2007. ISBN:
9780511804076

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

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

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

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

Campus virtual de la ULL

La Evaluación de esta asignatura se rige por el Reglamento de Evaluación y Calificación de la Universidad de La Laguna (REC), además de por lo establecido en la Memoria de Verificación inicial o posteriores modificaciones de la titulación y por lo establecido en la presente Guía Docente (GD). Se contemplan dos modalidades de evaluación alternativas: evaluación continua (EvC) y evaluación única (EvU).

Todo el alumnado matriculado en la asignatura está sujeto a la evaluación continua en la primera convocatoria, salvo quienes se acojan a la evaluación única, según se dispone en el REC. El alumnado que no supere la asignatura en la primera convocatoria dispondrá de una segunda que se realizará en todos los casos en la modalidad de EvU. Esta segunda convocatoria constará de dos evaluaciones, a realizar en las fechas publicadas por la Escuela Superior de Ingeniería y Tecnología (ESIT). El alumnado podrá concurrir a cualquiera de las dos evaluaciones o a ambas, siempre que no hubiera superado la asignatura en la primera evaluación. La calificación en el acta correspondiente a esta segunda convocatoria será la obtenida en la última de las evaluaciones efectuadas.

Modalidad de evaluación continua (EvC):

La evaluación continua se ha de entender como una modalidad de evaluación basada en un proceso sistemático de recogida y análisis de información objetiva que permita conocer y valorar los procesos de aprendizaje y los niveles de avance en el desarrollo de las competencias del alumnado. Se basa en la combinación de distintos tipos de actividades o pruebas que deberán estar relacionadas con las competencias, conocimientos y resultados de aprendizaje recogidos en esta guía docente para la asignatura. 

La evaluación continua consistirá en la realización de las siguientes actividades (que pueden ser individuales o grupales):
- [LAB]: Realización de prácticas de laboratorio. Cada práctica constará de una o varias sesiones de laboratorio y finalizará con la entrega de un informe de la práctica realizada. La calificación se calculará como la media entre la nota de prácticas del módulo 1 y del módulo 2: será una nota entre 0 y 10 y se corresponde con el 25% de la calificación final. 
- [INF]: Desarrollo de informes escritos y su exposición oral. En estas actividades se incluirá la evaluación de la comprensió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 informes incluirá un apartado que recoge este aspecto. La calificación se calculará como la media entre la nota de los informes del módulo 1 y del módulo 2: será una nota entre 0 y 10 y se corresponde con el 25% de la calificación final.
- [TEO]: Realización de la prueba final de la evaluación continua. Se calculará como la media entre la nota de teoría del módulo 1 y del módulo 2: será una nota entre 0 y 10 y se corresponde con el 50% de la calificación final. En el módulo 1, la evaluación consistirá en un examen escrito con preguntas teóricas y problemas, que se realizará en la fecha oficial de la primera convocatoria. En el módulo 2, la evaluación consistirá en uno o varios cuestionarios realizados durante el periodo de docencia del cuatrimestre. La calificación correspondiente al módulo 2 se calculará como la media de los cuestionarios realizados.

Los contenidos incluidos en los módulos 1 y 2 se encuentran definidos en la tabla Contenidos de la asignatura (apartado 6 de esta guía docente).

La calificación final se calculará mediante la siguiente fórmula:

[EvC] = 25% [LAB] + 25% [INF] + 50% [TEO]

En cada una de las tres partes será necesario alcanzar una nota mínima de 3.0 sobre 10 para que dicha nota sea incluida en el cómputo total de la calificación. Una nota menor a un 3.0 en una parte implica que esa parte puntuará como 0 en la calificación final. 

Se entenderá agotada la convocatoria cuando el estudiante se presente a actividades evaluativas cuya ponderación conjunta compute al menos el 50% de la evaluación continua. En caso contrario, figurará en acta como “No Presentado”.


Modalidad de evaluación única (EvU):

La modalidad de evaluación única deberá incluir las pruebas necesarias para acreditar que el alumnado ha adquirido las competencias, conocimiento y resultados de aprendizaje asociados a la asignatura, de acuerdo con lo establecido en la Memoria de Verificación inicial o posteriores modificaciones de la titulación. En ningún caso la evaluación única podrá entenderse como parte de la evaluación continua. Las fechas oficiales para la realización de las pruebas de la evaluación única correspondiente a cada convocatoria serán aprobadas por la ESIT dentro del calendario académico que apruebe el Consejo de Gobierno de la Universidad. Estas fechas estarán publicadas en la web institucional del centro antes del inicio del periodo ordinario de matrícula.

La modalidad de EvU será de aplicación a todo el alumnado en la segunda convocatoria de la asignatura. También podrá ser de aplicación en la primera convocatoria, siempre y cuando el alumnado haya comunicado su renuncia a la modalidad de EvC, comunicándolo al coordinador o coordinadora de la asignatura a través del procedimiento habilitado en el aula virtual de la misma, antes de haberse presentado a un conjunto de actividades cuya ponderación conjunta compute, al menos, el 40% de dicha modalidad de evaluación. Si no hubiera alcanzado dicho porcentaje, podrá renunciar a la EvC en el procedimiento habilitado en el aula virtual, siempre antes del inicio de la EvU.

La prueba de evaluación única consistirá en una prueba teórico-práctica que se realizará en las fechas de las convocatorias oficiales. La prueba constará de dos partes:

[TEO]: Prueba con preguntas teóricas y problemas de los dos módulos de la asignatura. Esta parte se evalúa con una calificación entre 0 y 10, que se calculará como la media de las calificaciones de teoría de los dos módulos de la asignatura. Si el alumnado obtuvo una calificación igual o superior a 3.0 sobre 10 en evaluación continua se podrá guardar la nota obtenida y no tendrá que realizarla. No obstante, el alumnado tiene derecho a renunciar a la calificación obtenida en EvC y volver a realizar esta prueba. 

[PRA] : Prueba con preguntas relacionadas con los contenidos trabajados en las prácticas y/o informes de los dos módulos de la asignatura. Esta parte se evalúa con una calificación entre 0 y 10, que se calculará como la media de las calificaciones de los dos módulos de la asignatura.. Si la media de las calificaciones [LAB] e [INF], obtenidas por el alumnado en evaluación continua, es igual o superior a 3.0 sobre 10, esta nota media será la calificación de [PRA] en evaluación única y no tendrá que realizarla. No obstante, el alumnado tiene derecho a renunciar a la calificación obtenida en EvC y volver a realizar esta prueba. 

La calificación final en modalidad de evaluación única se calculará:
[EvU] = 50% [TEO] + 50% [PRA]

En cada una de las dos partes es necesario alcanzar una nota media mínima de 3.0 sobre 10 para que dicha nota sea incluida en el cómputo total de la calificación. Una nota menor a un 3.0 en una parte significa que esa parte puntúa como 0 en la calificación final. 


En cumplimiento del Reglamento de Convivencia de la Universidad de La Laguna (art. 16.4), se informa al estudiantado de que durante las pruebas de evaluación presenciales podrán utilizarse dispositivos detectores pasivos de radiofrecuencia y campos magnéticos. Estos dispositivos no emiten señales, no interfieren con las comunicaciones y no registran datos personales. La tenencia y/o uso de dispositivos electrónicos no autorizados podrá constituir infracción disciplinaria conforme a la Ley 3/2022 y al Reglamento de Régimen Disciplinario del Estudiantado de la ULL . Los estudiantes portadores de dispositivos médicos electrónicos deberán comunicarlo antes del inicio de la prueba.

Verificación de autoría y autenticidad: Con el fin de garantizar la originalidad y la autoría de las pruebas y trabajos, conforme a los artículos 7.3 y 11 del Reglamento de Evaluación y Calificación de la ULL, cuando concurran indicios objetivos y motivados que cuestionen la autoría de una prueba o trabajo entregado (incluido el empleo no autorizado de herramientas de inteligencia artificial), el profesorado podrá convocar al estudiante a una entrevista de verificación de autoría sobre el trabajo realizado. Dicha entrevista tiene por objeto exclusivo verificar la autoría y no constituye una nueva prueba de evaluación. Si de ella resultara acreditada la falta de autoría o el uso de medios no autorizados, se aplicará la calificación de cero en la prueba o trabajo correspondiente, sin perjuicio del traslado a los órganos competentes a los efectos previstos en la Ley 3/2022, de 24 de febrero, de convivencia universitaria. Lo dispuesto en este apartado no resulta de aplicación a las pruebas objetivas tipo test, cuyo control de autoría se efectúa mediante la acreditación de identidad y la supervisión durante su desarrollo.

Tipo de prueba	Competencias	Criterios	Ponderación
Pruebas objetivas	[T1], [T2], [T9], [T14], [T20], [T22], [T25], [CG9], [C41], [C39]	Se valorará la adecuación de las respuestas a las preguntas planteadas.	50,00 %
Informes memorias de prácticas	[T1], [T2], [T9], [T12], [T14], [T16], [T19], [T20], [T22], [T25], [CG10], [CG9], [T6], [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	[T1], [T2], [T9], [T12], [T14], [T16], [T19], [T20], [T22], [T25], [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 asignatura 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.
La docencia se distribuye en cuatro sesiones semanales para el alumnado, tres de ellas en un aula de teoría y una en un laboratorio de ordenadores. La hora en el laboratorio se impartirá a grupos pequeños.
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	2.00	1.00	3.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 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	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 6:	Temas 1 / 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 de trabajos / Estudio autónomo	4.00	6.00	10.00
Semana 8:	Temas 1/ 2 / 3	Clases teóricas / Clases prácticas (aula o lab) / Realización de trabajos / Estudio autónomo	4.00	7.00	11.00
Semana 9:	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 10:	Tema 3	Clases teóricas / Clases prácticas (aula o lab) / Preparación clases teóricas / Estudio autónomo	4.00	6.00	10.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	4.00	6.00	10.00
Semana 12:	Tema 3	Clases teóricas / Clases prácticas (aula o lab) / 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	2.00	6.00	8.00
Semana 14:	Tema 3	Clases teóricas / Clases prácticas (aula o lab)  / Realización de trabajos / Estudio autónomo /  Realización seminarios o actividades complementarias	4.00	7.00	11.00
Semana 15:	Tema 3	Clases teóricas / Clases prácticas (aula o lab) / Realización de trabajos / Estudio autónomo	4.00	7.00	11.00
Semana 16 a 18:	Evaluación	Pruebas finales de la evaluación continua. Pruebas de evaluación única.	4.00	8.00	12.00
Total			60.00	90.00	150.00