Programa Docente de 21714024 - COMPLEJIDAD COMPUTACIONAL

Asignatura:

Titulación:

Centro:

Dep./Área:

Compartidas:

Tipo estudio:

Ofertada:

Vigencia:

Créd. teoría:

Créd. práctica:

Créd. ECTS:

Tipo Asignatura:

Módulo:

Materia:

Curso:

Matric. 2024-25:

Matric. 2025-26:

Duración:

Idioma:

Mostrar asignatura

Requisitos Previos

Es preciso que el alumno haya adquirido las competencias correspondientes a las materias de los dos primeros cursos, así como que sepa expresarse con fluidez, corrección y precisión en español.

Además, es necesario poseer conocimientos suficientes de lengua inglesa para leer y comprender los materiales y bibliografía recomendados.

Recomendaciones

Haber superado el módulo de formación básica y, al menos, las siguientes asignaturas adicionales, además de mantener la destreza necesaria en las materias objeto de su estudio.

    - Análisis de Algoritmos y Estructuras de Datos
    - Diseño de Algoritmos
    - Estructuras de Datos no Lineales
    - Modelos de Computación
    - Programación Orientada a Objetos
    - Sistemas Operativos

En particular, el alumno debe poseer una práctica fluida en el análisis de algoritmos y estructuras de datos, las técnicas de diseño de algoritmos, la programación en lenguaje C++ y el manejo de las herramientas básicas de programación disponibles a través de un intérprete de órdenes en un sistema operativo GNU/Linux.

Documento	Primer Apellido	Segundo Apellido	Nombre	Categoria
25599958S	GUERRERO	CONTRERAS	GABRIEL JOSE	PROFESOR/A AYUDANTE DOCTOR/A
31673026W	PALOMO	LOZANO	FRANCISCO	TEU
26481765W	SANCHEZ-ROSELLY	NAVARRO	ALFREDO	PROFESOR/A TITULAR DE UNIVERSIDAD

Id. Compentencia	Orden	ID	Resultado formación y aprendizaje	Competencia
29030	2	CG09	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.	COMPETENCIA GENERAL
29040	2	CG08	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	COMPETENCIA GENERAL
29042	3	CO03	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	COMPETENCIA ESPECÍFICA
33139	2	CB1	Que los estudiantes hayan demostrado poseer y comprender conocimientos en un área de estudio que parte de la base de la educación secundaria general, y se suele encontrar a un nivel que, si bien se apoya en libros de texto avanzados, incluye también algunos aspectos que implican conocimientos procedentes de la vanguardia de su campo de estudio	COMPETENCIA GENERAL
33140	2	CB2	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	COMPETENCIA GENERAL
33143	2	CB5	Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía	COMPETENCIA GENERAL
33144	4	CT1	Trabajo en equipo: capacidad de asumir las labores asignadas dentro de un equipo, así como de integrarse en él y trabajar de forma eficiente con el resto de sus integrantes	COMPETENCIA TRANSVERSAL

ID/ Orden	Resultado
1	Conocer los límites de la potencia de cálculo y sus consecuencias para la programación.
2	Comprender que existen problemas con una complejidad intrínseca.
3	Conocer distintos recursos computacionales y la medida de la complejidad espacio-temporal.
4	Conocer distintos tipos de problemas y sus aplicaciones en ingeniería.
5	Distinguir la complejidad de los algoritmos de la de los problemas a través del concepto de cota inferior de complejidad de un problema.
6	Conocer las clases de problemas fundamentales y sus relaciones.
7	Conocer algunos problemas abiertos y su estado actual.
8	Saber aplicar estrategias para la resolución de problemas complejos.
9	Ser capaz de programar soluciones a problemas complejos clásicos.

Tipo actividad formativa	Código	Descripción	Horas	Detalle
1	01	Teoría	18	En las clases de teoría se aprenderán los fundamentos teóricos de la materia y se ilustrarán sus conceptos mediante ejemplos paradigmáticos.
2	02	Prácticas, seminarios y problemas	18	En las clases de problemas se aplicarán los conocimientos aprendidos en las clases de teoría a la resolución de problemas relacionados.
3	03	Prácticas de informática	24	En las clases de prácticas de informática, que se desarrollarán en un laboratorio de informática, se proporcionará un guion de las actividades a realizar. Cada guion, disponible a través del campus virtual, podrá abarcar varias sesiones de laboratorio y contendrá ejercicios en los que se deberán programar los algoritmos pertinentes y realizar experimentos para resolver los problemas planteados.
10	10	Actividades formativas no presenciales	86,00	Estas actividades engloban la dedicación personal al estudio del alumno, que debe incluir tanto el estudio de los materiales suministrados y la consulta de la bibliografía recomendada, como la resolución de problemas y la realización de prácticas de programación.
12	12	Actividades de evaluación	4,00	Presentaciones orales y exámenes escritos.

ID/ Orden	Tarea / Actividad	Medios, Técnicas e Instrumentos	Ponderación
1	Presentaciones	Presentaciones sobre los materiales de teoría desarrollados en las distintas unidades, observación directa y rúbricas de evaluación	50 %
2	Prácticas de laboratorio	Informes técnicos escritos sobre las prácticas de laboratorio desarrolladas en las distintas unidades, revisiones y escalas numéricas	50 %

ID/ Orden	Temario	Descripción
1	Unidad 1. Introducción. - Recursos computacionales: medidas de complejidad y jerarquía asintótica. - Complejidad de los problemas: cotas inferiores y ejemplos. - Tipos de problemas y clases de complejidad. - Otros modelos (modelos no uniformes): complejidad de circuitos.
2	Unidad 2. Clases P y NP. - Problemas de búsqueda frente a problemas de decisión. - P y NP vistas como clases de problemas de búsqueda. - P y NP vistas como clases de problemas de decisión. - Equivalencia de ambas visiones. - Por qué es probable que P sea distinta de NP. - Breve bosquejo de otras clases: complementarias, espaciales...
3	Unidad 3. Reducciones polinómicas - Noción general de reducción. - Reducción de problemas de optimización a problemas de búsqueda. - Reducciones polinómicas (en tiempo): ejemplos.
4	Unidad 4. Clase NPC. - Existencia de problemas NPC. - Ejemplos de problemas NPC. - Problemas NP que no son P ni NPC (si P es distinta de NP).
5	Unidad 5. Técnicas para la resolución de problemas complejos. - Parametrización. - Aproximación. - Aleatorización. - Heurísticas.

UniversidaddeCádiz

Programa Docente de 21714024 - COMPLEJIDAD COMPUTACIONAL