Grafos y complejidad UOC
Muchas situaciones se pueden describir en forma de jerarquía o red entre diferentes entidades: red social, red de carreteras, cargos en una organización, red de computadores, conexiones en un circuito... Matemáticamente, esta noción de jerarquía o red se denomina grafo. En esta asignatura, estudiaremos el concepto de grafo, sus propiedades y los problemas más usuales que se pueden plantear. Estos conceptos serán de gran aplicación en muchos problemas del campo de la informática.
Por otro lado, algunos problemas que nos puede interesar resolver sobre un grafo son computacionalmente complejos: un ordenador necesitaría mucho tiempo de cálculo o espacio de memoria para resolverlos. En la segunda parte de la asignatura estudiaremos los límites prácticos de cálculo de un ordenador a partir de este concepto de dificultad computacional. Definiremos diferentes familias de problemas según su complejidad y presentaremos algunos ejemplos de problemas complejos, dentro y fuera de la teoría de grafos. Veremos que algunos de estos problemas complejos son muy frecuentes en el campo de la informática y que tienen aplicaciones a diferentes ámbitos, como por ejemplo la criptografía.
CONTENIDOS
La asignatura se estructura en siete módulos:
Módulo 1. Conceptos previos: funciones y algoritmos
- Funciones
- Algoritmos
Módulo 2. Fundamentos de grafos
- Caracterización de un grafo
- Estructura y manipulación de grafos
Módulo 3. Recorrido y conectividad
- Recorridos
- Algoritmos de exploración de grafos
- Conectividad
- Distancias de un grafo
Módulo 4. Árboles
- Conceptos básicos
- Árboles generadores
- Árboles con raíz
Módulo 5. Grafos eulerianos y grafos hamiltonianos
- Grafos eulerianos
- Grafos hamiltonianos
Módulo 6. Complejidad computacional
- El concepto de problema
- Medidas de complejidad
- Reducción y completitud
Módulo 7. Problemas intratables
- Problemas intratables sobre grafos
- Otros problemas intratables
MODELO DE EVALUACIÓN
Esta asignatura puede superarse únicamente mediante la realización de un examen final (presencial) (EX). La nota final de la evaluación continua (EC) complementa la nota del examen final (EX) mediante el cruce de acuerdo con la fórmula correspondiente. La fórmula de acreditación de la asignatura es la siguiente: EX + EC o EX.