Complejidad Computacional
(Curso Académico 2022 - 2023)
Mostrar Todo


Nota informativa: Atendiendo a la normativa de Protección de Datos y propiedad intelectual en la que se limita la publicación de imágenes de terceras personas sin su consentimiento, aquellos que difundan grabaciones de las sesiones de clase sin previo consentimiento de las personas implicadas, serán responsables ante la ley del uso prohibido de las citadas grabaciones.



1. Datos descriptivos de la asignatura
  • Código: 139264113
  • Centro: Escuela Superior de Ingeniería y Tecnología
  • Lugar de impartición: Escuela Superior de Ingeniería y Tecnología
  • Titulación: Grado en Ingeniería Informática
  • Plan de Estudios: 2010 (publicado en 21-03-2011)
  • Rama de conocimiento: Ingeniería y Arquitectura
  • Itinerario/Intensificación: Computación
  • Departamento/s:
  • Área/s de conocimiento:
    • Ciencia de la Computación e Inteligencia Artificial
    • Lenguajes y Sistemas Informáticos
  • Curso: 4
  • Carácter: Obligatoria
  • Duración: Primer cuatrimestre
  • Créditos ECTS: 6,0
  • Modalidad de impartición: Presencial
  • Horario: Ver horario
  • Dirección web de la asignatura: Ver web de la asignatura
  • Idioma: Español e Inglés
2. Requisitos para cursar la asignatura
No existen requisitos para cursar la asignatura
3. Profesorado que imparte la asignatura

Profesor/a Coordinador/a: LUZ MARINA MORENO DE ANTONIO

General:
Nombre:
LUZ MARINA
Apellido:
MORENO DE ANTONIO
Departamento:
Ingeniería Informática y de Sistemas
Área de conocimiento:
Lenguajes y Sistemas Informáticos
Grupo:
1, PA101, PE101, TU101, PE102, TU102
Contacto:
Teléfono 1:
922319908
Teléfono 2:
Correo electrónico:
lmmoreno@ull.edu.es
Correo alternativo:
Tutorías primer cuatrimestre:
DesdeHastaDíaHora incialHora finalLocalizaciónPlantaDespacho
27-09-2022 12-01-2023 Martes 10:30 13:30 Escuela Superior de Ingeniería y Tecnología - Módulo A - AN.4A ESIT 2 P2.031
27-09-2022 12-01-2023 Miércoles 16:30 19:30 Escuela Superior de Ingeniería y Tecnología - Módulo A - AN.4A ESIT 2 P2.031
13-01-2023 29-01-2023 Martes 10:30 13:30 Escuela Superior de Ingeniería y Tecnología - Módulo A - AN.4A ESIT 2 P2.031
13-01-2023 29-01-2023 Miércoles 10:30 13:30 Escuela Superior de Ingeniería y Tecnología - Módulo A - AN.4A ESIT 2 P2.031
Observaciones: El horario y lugar de tutorías es orientativo y prevalecerá la información que aparezca en el aula virtual de la asignatura. Se establecerá un sistema de cita previa para las tutorías. La reserva de una cita deberá realizarse al menos una hora antes del inicio de la tutoría.
Tutorías segundo cuatrimestre:
DesdeHastaDíaHora incialHora finalLocalizaciónPlantaDespacho
30-01-2023 05-03-2023 Lunes 16:00 20:00 Escuela Superior de Ingeniería y Tecnología - Módulo A - AN.4A ESIT 2 P2.031
30-01-2023 05-03-2023 Miércoles 16:00 18:00 Escuela Superior de Ingeniería y Tecnología - Módulo A - AN.4A ESIT 2 P2.031
06-03-2023 11-05-2023 Lunes 16:30 19:30 Escuela Superior de Ingeniería y Tecnología - Módulo A - AN.4A ESIT 2 P2. 031
06-03-2023 11-05-2023 Miércoles 16:30 19:30 Escuela Superior de Ingeniería y Tecnología - Módulo A - AN.4A ESIT 2 P2. 031
12-05-2023 31-07-2023 Martes 10:30 13:30 Escuela Superior de Ingeniería y Tecnología - Módulo A - AN.4A ESIT 2 P2. 031
12-05-2023 31-07-2023 Miércoles 10:30 13:30 Escuela Superior de Ingeniería y Tecnología - Módulo A - AN.4A ESIT 2 P2. 031
Observaciones: El horario y lugar de tutorías es orientativo y prevalecerá la información que aparezca en el aula virtual de la asignatura. Se establecerá un sistema de cita previa para las tutorías. La reserva de una cita deberá realizarse al menos una hora antes del inicio de la tutoría.
General:
Nombre:
JORGE
Apellido:
RIERA LEDESMA
Departamento:
Ingeniería Informática y de Sistemas
Área de conocimiento:
Ciencia de la Computación e Inteligencia Artificial
Grupo:
1, PA101, PE101, TU101, PE102, TU102
Contacto:
Teléfono 1:
922845040
Teléfono 2:
922319455
Correo electrónico:
jriera@ull.es
Correo alternativo:
Tutorías primer cuatrimestre:
DesdeHastaDíaHora incialHora finalLocalizaciónPlantaDespacho
Todo el cuatrimestre Miércoles 09:00 10:00 Escuela Superior de Ingeniería y Tecnología - Módulo A - AN.4A ESIT 3 P3.012
Observaciones: El horario y lugar de tutorías es orientativo y prevalecerá la información que aparezca en el aula virtual de la asignatura. Se establecerá un sistema de cita previa para las tutorías.
Tutorías segundo cuatrimestre:
DesdeHastaDíaHora incialHora finalLocalizaciónPlantaDespacho
Todo el cuatrimestre Miércoles 09:00 10:00 Escuela Superior de Ingeniería y Tecnología - Módulo A - AN.4A ESIT 3 P3.012
Observaciones: El horario y lugar de tutorías es orientativo y prevalecerá la información que aparezca en el aula virtual de la asignatura. Se establecerá un sistema de cita previa para las tutorías.
4. Contextualización de la asignatura en el plan de estudio
  • Bloque formativo al que pertenece la asignatura: Itinerario 1: Computación
  • Perfil profesional: Ingeniero Técnico en Informática
5. Competencias

Tecnología Específica / Itinerario: Computación

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

Competencias Generales

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

Transversales

  • 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.
6. Contenidos de la asignatura

Contenidos teóricos y prácticos de la asignatura

- 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-Levin
* Demostración de los 6 primeros problemas NP-completos
* Técnicas de Resolución de problemas difíciles

Actividades a desarrollar en otro idioma

- 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.
7. Metodología y volumen de trabajo del estudiante

Descripción

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

Actividades formativas en créditos ECTS, su metodología de enseñanza-aprendizaje y su relación con las competencias que debe adquirir el estudiante

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
8. Bibliografía / Recursos

Bibliografía básica

[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

Bibliografía complementaria

[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

Otros recursos

Campus virtual de la ULL
9. Sistema de evaluación y calificación

Descripción

La Evaluación de esta asignatura se rige por el Reglamento de Evaluación y Calificación de la Universidad de La Laguna (CG de 21 de junio de 2022), o el que la Universidad tenga vigente, además de por lo establecido en la Memoria de Verificación inicial o posteriores modificaciones de la titulación. Se contemplan dos modalidades de evaluación alternativas: evaluación continua y evaluación única.

Todo el alumnado matriculado en la asignatura está sujeto a la evaluación continua en la primera y segunda convocatoria, salvo quienes se acojan a la evaluación única según se dispone en el artículo 5.4 del Reglamento de Evaluación y Calificación de la Universidad de La Laguna (CG de 21 de junio de 2022). 

Modalidad de evaluación continua:

Se realizarán las siguientes actividades de aprendizaje (que pueden ser individuales o grupales):

1. [LAB]: Realización de prácticas de laboratorio. Cada práctica consta de una o varias sesiones de laboratorio 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. La calificación se calculará como la media entre la nota de prácticas del módulo 1 y del módulo 2, será un nota entre 0 y 10 y se corresponde con el 25% de la calificación final. 

2. [INF]: Desarrollo de trabajos y en su exposición oral. Tienen lugar a lo largo de las semanas de docencia, durante el cuatrimestre. En estas actividades se evalúa 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 trabajos incluye un apartado que recoge este aspecto. La calificación se calculará como la media entre la nota de los trabajos 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.

3. [TEO]: 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 problemas. Se realizará en la fecha de la primera convocatoria. 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.

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

En cada una de las tres partes 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. 

Se entenderá agotada la primera convocatoria desde que el alumnado se presente a cualquier conjunto de actividades cuya ponderación compute al menos el 50% de la evaluación continua, salvo en los casos recogidos en el artículo 5.5 del Reglamento de Evaluación y Calificación de la Universidad de La Laguna (CG de 21 de junio de 2022).

En la segunda convocatoria, el alumnado que no haya superado la asignatura podrá optar por recuperar cualquiera de las partes anteriores, de uno o de ambos módulos de contenidos:

1. [LAB]: Consistirá en un examen escrito con preguntas relacionadas con los contenidos de las prácticas de la asignatura.

2. [INF]: Consistirá  en un examen escrito con preguntas relacionadas con los contenidos de los trabajos de la asignatura.

3. [TEO]: Consiste en un examen escrito con preguntas teóricas y/o problemas.

 La calificación final de la asignatura se calculará aplicando los mismos porcentajes que en la primera convocatoria.


Modalidad de evaluación única:

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 asocados 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 Escuela Superior de Ingeniería y Tecnología 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.

En el artículo 5.4 del Reglamento de Evaluación y Calificación de la Universidad de La Laguna (CG de 21 de junio de 2022) se establece que el alumnado podra optar a la evaluación única comunicándolo al coordinador o coordinadora de la asignatura a través del procedimiento habilitado en el aula virtual de la misma, en el plazo de un mes a partir del inicio del cuatrimestre correspondiente.

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

[PRA] : Prueba con preguntas relacionadas con los contenidos trabajados en las prácticas de los dos módulos de la asignatura. Esta parte se evalúa con una calificación entre 0 y 4.

La calificación final en modalidad de evaluación única se obtiene como la suma de las dos partes:
[CF] = [TEO] + [PRA]

Estrategia Evaluativa

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 %
10. Resultados de Aprendizaje
Conocer los modelos de computación y la complejidad computacional de un problema, aplicando técnicas, modelos y estrategias adecuadas para resolverlo.
En el contexto del grupo de trabajo, recopilar, analizar y discutir los contenidos teóricos de la asignatura.
Realizar aplicaciones informáticas para aplicar diferentes técnicas y modelos de computación
Realizar trabajos sobre la complejidad computacional de un problema, usando técnicas algorítmicas para su resolución.
11. Cronograma / calendario de la asignatura

Descripción

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

Primer 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 4.00 2.00 6.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 4.00 8.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 7.00 11.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 7.00 11.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 6.00 10.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 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 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 4.00 6.00 10.00
Semana 14: 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 7.00 11.00
Semana 15: Semanas 15 a 16 Evaluación y trabajo autónomo del alumnado 4.00 8.00 12.00
Total 60.00 90.00 150.00
Fecha de última modificación: 11-07-2022
Fecha de aprobación: 15-07-2022