![]() |
Guia docente | |||||||||||||||||||||||||||||||||||||||
DATOS IDENTIFICATIVOS | 2022_23 | |||||||||||||||||||||||||||||||||||||||
Asignatura | COMPLEJIDAD COMPUTACIONAL | Código | 00709033 | |||||||||||||||||||||||||||||||||||||
Enseñanza |
|
|||||||||||||||||||||||||||||||||||||||
Descriptores | Cr.totales | Tipo | Curso | Semestre | ||||||||||||||||||||||||||||||||||||
6 | Obligatoria | Cuarto | Primero |
|||||||||||||||||||||||||||||||||||||
Idioma |
|
|||||||||||||||||||||||||||||||||||||||
Prerrequisitos | ||||||||||||||||||||||||||||||||||||||||
Departamento | MATEMATICAS |
|||||||||||||||||||||||||||||||||||||||
Responsable |
|
Correo-e | amunc@unileon.es jahera@unileon.es |
|||||||||||||||||||||||||||||||||||||
Profesores/as |
|
|||||||||||||||||||||||||||||||||||||||
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 |
|
|||||||||||||||||||||||||||||||||||||||
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.- MODELOS | Tema 2.1.- Autómatas finitos Tema 2.2.- Máquinas de Turing Tema 2.3.- Aplicaciones |
Bloque 3.- LENGUAJES FORMALES | Tema 3.1.- Conceptos básicos Tema 3.3.- Ejemplos |
Bloque 4.- DECIBILIDAD Y 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 |
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 |
|
|
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:
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 | |
|
|
Complementaria | |
|
Recomendaciones |
Asignaturas que se recomienda haber cursado previamente | |||
|