![]() |
Guia docente | |||||||||||||||||||||||||||||||||||||||
DATOS IDENTIFICATIVOS | 2020_21 | |||||||||||||||||||||||||||||||||||||||
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 | rmgarf@unileon.es mmlopc@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 I: LA MÁQUINA DE TURING | Tema 1: ALFABETOS, CADENAS Y LENGUAJES FORMALES. Se introducen los conceptos básicos de la asignatura y sus propiedades. Tema 2: MÁQUINA DE TURING Se introduce el concepto de máquina de Turing (determinista y no determinista) junto con algunas de sus modificaciones (multipista, multicinta, etc). Como caso particular se introducen los autómatas finitos y los de pila. |
Bloque II: LENGUAJES FORMALES Y SU COMPLEJIDAD COMPUTACIONAL. | Tema 3: LENGUAJES RECURSIVOS Y RECURSIVAMENTE ENUMERABLES. Trás introducir ambos conceptos se estudian como casos particulares los lenguajes regulares y los independientes del contexto. Con la máquina universal se introducen diversos ejemplos de problemas no decidibles. El tema finaliza con las gramáticas formales y la jerarquía de Chomsky. Tema 4: COMPLEJIDAD COMPUTACIONAL DE PROBLEMAS DECIDIBLES. Se introduce la complejidad temporal y la espacial de una máquina de Turing. Ello permite establecer la correspondiente jerarquía de lenguajes. Se introducen las clases P y NP junto con algunos ejemplos de problemas NP-completos. |
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 titulacion 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 autonomo.Para el trabajo autonomo del estudiante se le recomienda tener presente las siguientes pautas:
3. Sistema de evaluacion.La evaluacion sera 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. Los estudiantes que no hayan alcanzado el mínimo exigido en alguna de las pruebas escritas o en los trabajos propuestos podrán recuperarlos en la primera semana dispuesta a tal fin. 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 5. Convocatoria Extraordinaria de DiciembrePodrán optar a esta convocatoria aquellos estudiantes que tengan pendiente una asignatura y/o el TFG para finalizar sus estudios. Consistira en en un examen de caracter practico entre cero y diez puntos, en el que para superarlo habra que obtener 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 |
ADENDA |
Plan de contingencia para una situación de emergencia que impida actividades docentes presenciales |
Enlace de acceso a la Adenda de la Guia docente por el COVID-19 |
Fuentes de información |
Acceso a la Lista de lecturas de la asignatura |
Básica | |
|
|
Complementaria | |
|
Recomendaciones |
Asignaturas que se recomienda haber cursado previamente | |||
|