Versión imprimible Curso Académico
Complejidad Computacional
Curso 2017/18
1. Datos Descriptivos de la Asignatura
ASIGNATURA: Complejidad Computacional CÓDIGO: 139264113
- Centro: 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: Cuatrimestral
- Créditos ECTS: 6.0
- Horario: http://www.ull.es/view/centros/etsii/Cuarto_3/es
- Dirección web de la asignatura: http://www.campusvirtual.ull.es
- 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
- Grupo: 1, PA101, TU101
- Departamento: Ingeniería Informática y de Sistemas
- Área de conocimiento: Lenguajes y Sistemas Informáticos
- Lugar Tutoría: Despacho 2ª planta de la Torre Profesor Agustín Arévalo.
- Horario Tutoría: Primer cuatrimestre: martes y miércoles de 16:00 a 19:00; Segundo cuatrimestre: martes y miércoles de 16:00 a 19:00; Periodos lectivo sin docencia: martes y miércoles de 10:30 a 13:30 (el horario de tutorías es orientativo, el horario definitivo se podrá consultar en el aula virtual de la asignatura)
- Teléfono (despacho/tutoría): 922319908
- Correo electrónico: lmmoreno@ull.edu.es
- Dirección web docente: http://www.campusvirtual.ull.es
Profesor/a: JORGE RIERA LEDESMA
- Grupo: 1, PA101, TU101
- Departamento: Ingeniería Informática y de Sistemas
- Área de conocimiento: Ciencia de la Computación e Inteligencia Artificial
- Lugar Tutoría: Área de Despachos de la ETSII
- Horario Tutoría: Martes, miércoles y jueves de 10:00 a 12:00 (El lugar y horarios de tutoría pueden sufrir variaciones puntuales a lo largo del curso, que serán debidamente comunicadas en tiempo y forma)
- Teléfono (despacho/tutoría): 922845040
- Correo electrónico: jriera@ull.es
- Dirección web docente: http://www.campusvirtual.ull.es


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

- Profesor/a: 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/a: 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
Actividades a desarrollar en otro idioma
- Profesor/a: Luz Marina Moreno de Antonio / Jorge Riera Ledesma

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


7. Metodología y volumen de trabajo del estudiante
Descripción
Se impartirán clases teóricas donde el profesor 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 alumno tendrá que realizar y que serán evaluadas.

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.

La asignatura solicita participar en el Programa de Apoyo a la Docencia Presencial en la modalidad A (Apoyo a la docencia presencial de asignatura y al trabajo autónomo del alumnado). En la asignatura se desarrollarán actividades de tipo colaborativo o grupales, se utilizarán algún material didáctico interactivo y se realizarán las actividades de evaluación utilizando las herramientas del campus virtual.

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      28  [T12], [T22], [T25], [C39], [C41]
Clases prácticas (aula / sala de demostraciones / prácticas laboratorio)  18.00      18  [CG9], [CG10], [T1], [T2], [T9], [T12], [T16], [T19], [T20], [T22], [T25], [C39], [C41]
Realización de seminarios u otras actividades complementarias  3.00   6.00   9  [CG9], [CG10], [T1], [T2], [T6], [T9], [T12], [T14], [T16], [T19], [T20], [T22], [T25], [C39], [C41]
Realización de trabajos (individual/grupal)     40.00   40  [CG9], [CG10], [T1], [T2], [T6], [T9], [T12], [T14], [T16], [T19], [T20], [T22], [T25], [C39], [C41]
Estudio/preparación clases teóricas     10.00   10  [T1], [T2], [T6], [T9], [T14], [T16], [T20], [T22], [T25], [C39], [C41]
Preparación de exámenes     4.00   4  [T1], [T2], [T14], [T16], [T19], [T20], [T22], [T25], [C39], [C41]
Realización de exámenes  4.00      4  [CG9], [T1], [T2], [T9], [T16], [T20], [T22], [T25], [C39], [C41]
Asistencia a tutorías  7.00      7  [T2], [T12], [T14], [T16], [T19], [T20], [T22], [T25], [C39], [C41]
Estudio autónomo individual o en grupo     30.00   30  [CG9], [CG10], [T1], [T2], [T6], [T12], [T14], [T16], [T19], [T20], [T22], [T25], [C39], [C41]
Total horas  60   90   150 
Total ECTS  6 


8. Bibliografía / Recursos
Bibliografía básica

- 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: 113318779X. Wadsworth Publishing Co Inc; Edición: 3rd edition. 2012

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

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

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

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

- 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
Otros recursos
Campus virtual de la ULL


9. Sistema de evaluación y calificación
Descripción
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.

- En la asignatura los alumnos tendrán que realizar las siguientes actividades de aprendizaje, de forma individual o en grupo:
1. Realización de prácticas de laboratorio: 25% de la calificación final.
2. Realización de informes: 25% de la calificación final.
3. Realización de examen: 50% de la calificación final.

Dentro las actividades del punto 2 (realización de informes) se evalúa la compresión de la lectura de diversa documentación en lengua inglesa mediante cuestiones formuladas en la exposición/entrega de los trabajos relativos a dicha documentación. La calificación de los trabajos incluye un apartado que recoge este aspecto.


En cada una de las partes, será necesario alcanzar una nota 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 se guardarán para todas las convocatorias del curso académico.

Los dos primeros tipos de actividades (realización de prácticas y de informes) se realizarán a lo largo de las semanas del cuatrimestre.
El tercer tipo de actividad (realización de exámenes), podrá ser superada mediante dos exámenes parciales (realizados a mitad y a final del cuatrimestre) o bien, mediante una prueba final de evaluación.
· Cada parcial se corresponderá con uno de los dos módulos que aparecen definidos en la tabla Contenidos de la asignatura (apartado 6 de esta guía docente).

En cada una de las fechas oficiales de convocatoria, los alumnos que no hayan aprobado mediante la evaluación continua, tendrán que realizar una prueba 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 la calificación obtenida en las actividades de evaluación continua que el alumno tenga superadas.


Estrategia Evaluativa
TIPO DE PRUEBA COMPETENCIAS CRITERIOS PONDERACIÓN
Pruebas objetivas  [CG9], [T1], [T2], [T9], [T14], [T20], [T22], [T25], [C39], [C41]   Se valorará la adecuación de las respuestas a las preguntas planteadas.   50% 
Informes memorias de prácticas  [CG9], [CG10], [T1], [T2], [T6], [T9], [T12], [T14], [T16], [T19], [T20], [T22], [T25], [C39], [C41]   Se valorará la presentación de los informes orales o escritos y la adecuación de las soluciones propuestas a los problemas planteados.   25% 
Valoración de las actividades prácticas en el laboratorio  [CG9], [T1], [T2], [T9], [T12], [T14], [T16], [T19], [T20], [T22], [T25], [C39], [C41]   Se valorará la presentación de los informes orales o escritos y la adecuación de las soluciones propuestas a los problemas planteados.   25% 


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, 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 / Asistencia a tutorías / Preparación clases teóricas / Estudio autónomo    3.00   5.00   8 
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   6.00   10 
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 
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 
Semana 5:  Temas 1 y 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    3.00   6.00   9 
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 
Semana 7:  Tema 2   Clases teóricas / Asistencia a tutorías / Realización de exámenes / Realización seminarios o actividades complementarias / Realización de trabajos / Preparación exámenes / Estudio autónomo    4.00   7.00   11 
Semana 8:  Tema 2   Clases teóricas / Clases prácticas (aula o lab) / Realización seminarios o actividades complementarias / Realización de trabajos / Estudio autónomo    3.00   6.00   9 
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   5.00   9 
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 
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 
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 
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 
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 
Semana 15:  Tema 3    Clases prácticas (aula o lab) / Realización seminarios o actividades complementarias / Realización de exámenes / Realización de trabajos / Preparación exámenes / Estudio autónomo    4.00   7.00   11 
Semanas 16 a 18:  Evaluación   Evaluación y trabajo autónomo del alumno para la preparación de la evaluación.   4.00   0.00   4 
Total horas 60 90 150


Fecha de última modificación: 27-07-2017
Fecha de aprobación: 27-07-2017