UniversidaddeCádiz

Programas Docentes de Asignaturas

Programa docente (2025-26) | <21714024 | COMPLEJIDAD COMPUTACIONAL>

Asignatura: 21714024 | COMPLEJIDAD COMPUTACIONAL

Titulación: 1725 | GRADO EN INGENIERÍA INFORMÁTICA

Centro: 17 | ESCUELA SUPERIOR DE INGENIERÍA

Departamento: C137 | INGENIERIA INFORMATICA

Área: 075 | CIENCIA DE LA COMPUTACION E INTELIGENCIA ARTIF.

Compartidas:

Tipo estudio: GRADO

Ofertada: SÍ

Vigencia: VIGENTE

Créd. Teoría: 2,25

Créd. Prácticas: 5,25

Créd. ECTS: 6,00

Tipo asignatura: OPTATIVA

Módulo: MODULO IIIA - TECNOLOGÍA ESPECÍFICA COMPUTACIÓN

Materia: MATERIA IIIA.1 COMPUTABILIDAD Y COMPLEJIDAD

Matriculados 2024-25: 20

Matriculados 2025-26: 13

Duración: PRIMER SEMESTRE

Curso: 3, 4

Idioma: CASTELLANO

Mostrar información

Primer apellido	Segundo apellido	Nombre	Categoría/Empresa
GUERRERO	CONTRERAS	GABRIEL JOSE	PROFESOR/A AYUDANTE DOCTOR/A
PALOMO	LOZANO	FRANCISCO	TEU
SANCHEZ-ROSELLY	NAVARRO	ALFREDO	PROFESOR/A TITULAR DE UNIVERSIDAD

Resultado formación y aprendizaje	Competencia
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.	GENERAL
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	GENERAL
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	ESPECÍFICA
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	GENERAL
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	GENERAL
Que los estudiantes hayan desarrollado aquellas habilidades de aprendizaje necesarias para emprender estudios posteriores con un alto grado de autonomía	GENERAL
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	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.

Código	Descripción	Horas	Detalle
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	Actividades formativas no presenciales	86	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	Actividades de evaluación	4	Presentaciones orales y exámenes escritos.
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.
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.

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	Tema	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.

Volver

UniversidaddeCádiz

Programas Docentes de Asignaturas

Programas Docentes de Asignaturas

Programa docente (2025-26) | <21714024 | COMPLEJIDAD COMPUTACIONAL>

Servicio de Organización Académica y Planificación PDI