Guia docente
DATOS IDENTIFICATIVOS 2024_25
Asignatura COMPLEJIDAD COMPUTACIONAL Código 00709033
Enseñanza
0709 - GRADO EN INGENIERÍA INFORMÁTICA
Descriptores Cr.totales Tipo Curso Semestre
6 Obligatoria Cuarto Primero
Idioma
Castellano
Prerrequisitos
Departamento MATEMATICAS
Responsable
MUNOZ CASTANEDA , ANGEL LUIS
Correo-e amunc@unileon.es
jahera@unileon.es
Profesores/as
HERMIDA ALONSO , JOSÉ ÁNGEL
MUNOZ CASTANEDA , ANGEL LUIS
Web http://
Descripción general Introducir al alumno la Complejidad Computacional, a través de la teoría de NP-completitud. Dar herramientas para que el alumno pueda continuar a cursos más avanzados de Complejidad y Teoría de la Computación. Contribuir a la formación del alumno en Teoría de la Computación y a aumentar su comprensión de los fundamentos de la Computación.
Tribunales de Revisión
Tribunal titular
Cargo Departamento Profesor
Presidente MATEMATICAS GRANJA BARON , ANGEL
Secretario MATEMATICAS PISABARRO MANTECA , MARIA JESUS
Vocal MATEMATICAS CARRIEGOS VIEIRA , MIGUEL
Tribunal suplente
Cargo Departamento Profesor
Presidente MATEMATICAS GOMEZ PEREZ , JAVIER
Secretario MATEMATICAS LOPEZ CABECEIRA , MONTSERRAT
Vocal MATEMATICAS GARCIA FERNANDEZ , ROSA MARTA

Competencias
Código  
A18099 709CE12 Conocimiento y aplicación de los procedimientos algorítmicos básicos de las tecnologías informáticas para diseñar soluciones a problemas, analizando la idoneidad y complejidad de los algoritmos propuestos.
A18117 709CE3 Capacidad para comprender y dominar los conceptos básicos de matemática discreta, lógica, algorítmica y complejidad computacional, y su aplicación para la resolución de problemas propios de la ingeniería.
A18127 709ULE1 Capacidad para evaluar la complejidad computacional de un problema, en particular ser capaz tanto de discriminar las distintas clases de complejidad como de reconocer problemas computacionalmente equivalentes y conocer estrategias algorítmicas que puedan conducir a su resolución y recomendar, desarrollar e implementar aquella que garantice el mejor rendimiento.
A18137 709ULE2 Capacidad para adquirir, obtener, formalizar y representar el conocimiento humano en una forma computable para la resolución de problemas mediante un sistema informático en cualquier ámbito de aplicación, particularmente los relacionados con aspectos de computación, percepción y actuación en ambientes o entornos inteligentes.
B5611 709CG1 Capacidad para concebir, redactar, organizar, planificar, desarrollar y firmar proyectos en el ámbito de la ingeniería en informática que tengan por objeto, de acuerdo con los conocimientos adquiridos, la concepción, el desarrollo o la explotación de sistemas, servicios y aplicaciones informáticas.
B5612 709CG2 Capacidad para dirigir las actividades objeto de los proyectos del ámbito de la informática de acuerdo con los conocimientos adquiridos.
B5618 709CG8 Conocimiento de las materias básicas y tecnologías, que capaciten para el aprendizaje y desarrollo de nuevos métodos y tecnologías, así como las que les doten de una gran versatilidad para adaptarse a nuevas situaciones.
B5619 709CG9 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.
B5623 709CT1 Capacidad para el análisis, síntesis, resolución de problemas y la toma de decisiones.
B5624 709CT2 Capacidad para interpretación de resultados con iniciativa, creatividad y razonamiento crítico y autocrítico.
B5625 709CT3 Capacidad para comunicar y transmitir de forma oral o por escrito conocimientos y razonamientos derivados de su trabajo individual o en grupo de forma clara y concreta.
B5626 709CT4 Capacidad para el aprendizaje autónomo e individual en cualquier campo de la ingeniería.
C2 CMECES2 Que los estudiantes sepan aplicar sus conocimientos a su trabajo o vocación de una forma profesional y posean las competencias que suelen demostrarse por medio de la elaboración y defensa de argumentos y la resolución de problemas dentro de su área de estudio.
C3 CMECES3 Que los estudiantes tengan la capacidad de reunir e interpretar datos relevantes (normalmente dentro de su área de estudio) para emitir juicios que incluyan una reflexión sobre temas relevantes de índole social, científica o ética.
C4 CMECES4 Que los estudiantes puedan transmitir información, ideas, problemas y soluciones a un público tanto especializado como no especializado
C5 CMECES5 Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía

Resultados de aprendizaje
Resultados Competencias
- Entender el efecto que tiene el análisis de complejidad en el diseño de algoritmos. A18099
A18117
A18127
B5623
B5624
B5626
C2
- Conocer los métodos usados para calcular la complejidad computacional de un algoritmo. A18099
A18117
A18127
B5623
B5624
B5626
C2
C3
- Aplicar los métodos anteriores a varios algoritmos con el fin de determinar cuál es más eficiente A18099
A18117
A18127
B5612
B5618
B5619
B5624
B5625
- Seleccionar las estructuras de datos y técnicas de programación apropiadas para diseñar un algoritmo eficiente desde el punto de vista de su complejidad computacional A18099
A18117
A18127
A18137
B5611
B5612
B5618
B5619
B5623
B5624
B5626
C2
C3
C4
- Ser capaz de seguir cursos más avanzados de Complejidad y Teoría de la Computación. A18099
A18117
A18127
A18137
B5618
C2
C4
C5

Contenidos
Bloque Tema
Bloque 1.- INTRODUCCIÓN Tema 1.1.- Objetivos

Tema 1.2.- Conceptos básicos
Bloque 2.- LENGUAJES FORMALES Tema 2.1.- Conceptos básicos

Tema 2.2.- Ejemplos
Bloque 3.- COMPUTACIÓN Tema 3.1.- Autómatas finitos

Tema 3.2.- Máquinas de Turing

Tema 3.3.- Aplicaciones
Bloque 4.- COMPLEJIDAD Tema 4.1.- Complejidad temporal y espacial

Tema 4.2.- P contra NP

Tema 4.3.- Problemas NP-completos

Tema 4.4.- Ejemplos

Planificación
Metodologías  ::  Pruebas
  Horas en clase Horas fuera de clase Horas totales
Resolución de problemas/ejercicios en el aula ordinaria 25 30 55
 
 
Sesión Magistral 25 35 60
 
Realización y exposición de trabajos. 10 13 23
Pruebas prácticas 4 8 12
 
(*)Los datos que aparecen en la tabla de planificación són de carácter orientativo, considerando la heterogeneidad de los alumnos

Metodologí­as
Metodologías   ::  
  descripción
Resolución de problemas/ejercicios en el aula ordinaria Se resolverán ejercicios y problemas con carácter práctico donde se aplicarán los conocimientos teóricos impartidos en las clases magistrales.
Sesión Magistral El profesor impartirá los conocimientos teóricos correspondientes a los contenidos de esta guía docente.

Tutorías
 
Sesión Magistral
Resolución de problemas/ejercicios en el aula ordinaria
Realización y exposición de trabajos.
Pruebas prácticas
descripción
El desarrollo de las competencias en el estudiante, exige el seguimiento tutorizado, por parte del profesor. Para ello el profesor atenderá al estudiante en grupos, y/o individualmente tanto presencialmente, como virtualmente en cualquiera de las metodologías utilizadas.

Evaluación
  descripción calificación
Sesión Magistral Se valorará, en las pruebas escritas, el nivel de comprensión teórico y la capacidad de análisis. Supondrá el 10% de la calificación final.
Resolución de problemas/ejercicios en el aula ordinaria Se realizarán 2 pruebas escritas donde se valorará el dominio de los conocimientos teóricos y operativos de la materia. Supondrán el 60 % de la calificación final.
Realización y exposición de trabajos. En la entrega y exposición de trabajos, incluyendo ejercicios resueltos, se valorará:

- Estructura del trabajo.
- Correcta resolución de los ejercicios.
- Precisión en el uso del lenguaje.
- Presentación.
- Originalidad.
Supondrá un 30 % de la calificación final.
 
Otros comentarios y segunda convocatoria

1. Caracter de la asignatura.

El papel de la asignatura en la titulación es eminentemente conceptual por lo que es importante la inclusión de ejemplos y problemas de carácter eminentemente práctico. Es primordial que el estudiante tenga las suficientes herramientas para poder descomponer un problema  (o equivalentemente el reconocimiento de un lenguaje) en problemas más simples. Igualmente es importante que conozca la complejidad de resolución de diferentes tipos de problemas. 

2. Recomendaciones para el trabajo autónomo.

Para el trabajo autónomo del estudiante se le recomienda tener presente las siguientes pautas:

  • La bibliografía de la asignatura proporciona un material insustituible en el estudio.
  • Previo a las clases teóricas, trabajar sobre la bibliografía y recursos indicados por el profesor. De esta forma se facilita la participación activa del estudiante.
  • Análogamente, previo a las clases practicas, tratará de resolver los ejercicios o cuestiones planteadas previamente por el profesor.
3. Sistema de evaluación.

La evaluación será continua  a través de las dos pruebas escritas y de los trabajos  que se propongan (que podrán ser presenciales e individuales). 

Esta evaluación será de tipo aditivo y la asignatura se supera obteniendo: a) al menos 50% de  la totalidad posible de puntos y b) obteniendo en cada una de las pruebas escritas al menos el 25% del máximo asignado. 

Durante el desarrollo de las pruebas no se permitirá manejar ningún material a excepción del que indique el profesor. En los trabajos presenciales individuales se permitirá el uso de las notas tomadas en clase por el estudiante. 

Queda terminantemente prohibida la tenencia y el uso de dispositivos móviles y/o electrónicos durante la celebración de las pruebas. La simple tenencia de dichos dispositivos así como de apuntes, libros, carpetas o materiales diversos no autorizados durante las pruebas de evaluación, supondrá la retirada inmediata del examen, su expulsión del mismo y su calificación como suspenso, comunicándose la incidencia a la Autoridad Académica del Centro para que realice las actuaciones previstas en las Pautas de Actuación en los Supuestos de Plagio, Copia o Fraude en Exámenes o Pruebas de Evaluación, aprobadas por la Comisión Permanente del Consejo de Gobierno de 29 de enero de 2015

4. Segunda convocatoria.

Aquellos estudiantes que hayan suspendido la primera convocatoria  tendrán derecho a una segunda convocatoria  consistente en un examen de carácter práctico de toda la Asignatura en el que se podrá obtener de cero a diez puntos. Este examen se supera obteniendo al menos cinco puntos.

Durante el desarrollo de las pruebas no se permitirá manejar ningún material a excepción del que indique el profesor. Queda terminantemente prohibida la tenencia y el uso de dispositivos móviles y/o electrónicos durante la celebración de las pruebas. La simple tenencia de dichos dispositivos así como de apuntes, libros, carpetas o materiales diversos no autorizados durante las pruebas de evaluación, supondrá la retirada inmediata del examen, su expulsión del mismo y su calificación como suspenso, comunicándose la incidencia a la Autoridad Académica del Centro para que realice las actuaciones previstas en las Pautas de Actuación en los Supuestos de Plagio, Copia o Fraude en Exámenes o Pruebas de Evaluación, aprobadas por la Comisión Permanente del Consejo de Gobierno de 29 de enero de 2015.


Fuentes de información
Acceso a la Lista de lecturas de la asignatura

Básica
  • Michael Garey , David Johnson , "Informática y la dificultad-una guía para la teoría de NP-completitud", Freeman and Company, 1979 
  • Brassard, G. y P. Bratley; Fundamentos de Algoritmia; Prentice Hall, 1997.
  • Sara Baase, Allen Van Gelder, " Computer Algorithms. Introduction to Design and Analysis". Addison-Wesley, 2000. 
  •  John E.Hopcroft,Rajeev Motwani,Jeffrey D. Ullman, "Introducción a la Teoría de Autómatas, Lenguajes y Computación"; Addison Wesley,2002  
  • Dean Kelly, "Teoría de autómatas finitos y lenguajes formales", Prentice Hall 1998
  • Oded Goldreich, "P, NP, and NP-Completeness. The basics of computational complexity"; Cambridge University Press 2010
Complementaria
  • C. Papadimitriou Computational Complexity, Addison-Wesley, 1995.

Recomendaciones


Asignaturas que se recomienda haber cursado previamente
ALGEBRA / 00709006
ALGORITMOS Y GRAFOS / 00709014