Grafos y complejidad Código:  75.569    :  6
Consulta de los datos generales   Descripción   La asignatura en el conjunto del plan de estudios   Campos profesionales en el que se proyecta   Conocimientos previos   Información previa a la matrícula   Objetivos y competencias   Contenidos   Consulta de los recursos de aprendizaje de la UOC para la asignatura   Información adicional sobre los recursos de aprendizaje y herramientas de apoyo   Informaciones sobre la evaluación en la UOC   Consulta del modelo de evaluación  
Este es el plan docente de la asignatura para el segundo semestre del curso 2022-2023. Podéis consultar si la asignatura se ofrece este semestre en el espacio del campus Más UOC / La universidad / Planes de estudios). Una vez empiece la docencia, tenéis que consultarlo en el aula. El plan docente puede estar sujeto a cambios.

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.

Amunt

Grafos y Complejidad es una asignatura obligatoria del grado en Ingeniería Informática.

Antes de cursarla, se recomienda haber cursado previamente las asignaturas de Prácticas de programación (para estar familiarizado con el desarrollo de algoritmos) y Lógica (para estar familiarizado con la notación lógica).

El uso de grafos para modelar problemas es muy habitual en el campo de la informática. Por este motivo, utilizaréis los conceptos de grafos en múltiples asignaturas dentro del grado, como por ejemplo las asignaturas de redes de computadores o las asignaturas del itinerario de Computación.

Algunos de los problemas complejos que hemos estudiado en esta asignatura también aparecen en otras asignaturas:

  • En las asignaturas, de Inteligencia Artificial y Aprendizaje Computacional se presentan estrategias para calcular soluciones aproximadas a problemas complejos de forma eficiente.
  • En Criptografía se utilizan problemas computacionalmente complejos para garantizar la seguridad de los mecanismos de cifrado y autenticación.
  • La asignatura Diseño de Estructuras de Datos aplica de forma práctica los conceptos de grafos y complejidad al campo de la programación. Diseño de Estructuras de Datos estudia como desarrollar programas eficientes: presenta diferentes estructuras de datos y algoritmos para problemas frecuentes (algunos de ellos, problemas sobre grafos), así como los criterios para elegir el más adecuado a cada situación.
  • La asignatura Modelado de Sistemas estudia cómo resolver problemas de optimización complejos en el ámbito de la logística y la planificación, también conocido como investigación operativa (operations research).

Amunt

Los conceptos de grafos se utilizan de forma transversal en muchos ámbitos de la informática, para modelar circuitos, redes, organizaciones jerárquicas, etc.

En cuanto a la complejidad, los conceptos de coste temporal y espacial son fundamentales para cualquier programador.

Los problemas más complejos presentados en la asignatura son relevantes por profesionales en el ámbito de la investigación operativa y la inteligencia artificial. También son importantes por profesionales de la seguridad informática, para saber evaluar la seguridad de algunos criptosistemas.

Amunt

La asignatura requiere conocimientos básicos de algorítmica: la comprensión de algoritmos en pseudocódigo y la capacidad de proponer algoritmos que resuelvan problemas nuevos. También son muy útiles nociones sobre el cálculo del coste temporal de un algoritmo, aunque estos conceptos en el primer módulo de la asignatura.

Además, para el correcto seguimiento de la asignatura es importante entender la notación matemática y conocer los conceptos de conjunto y función.

Amunt

Antes de cursar esta asignatura, es muy recomendable haber cursado previamente las asignaturas siguientes:

  • Prácticas de programación
  • Lógica
  • Álgebra

Amunt

Las competencias generales del Grado que se ponen de manifiesto en esta asignatura son:

  • Capacidad para utilizar los fundamentos matemáticos, estadísticos y físicos para comprender los sistemas TIC.

  • Capacidad para analizar un problema en el nivel de abstracción adecuado a cada situación y aplicar las habilidades y conocimientos adquiridos para resolverlo.

 Las competencias específicas de esta asignatura son:

  • Conocer el concepto de grafo y los diferentes tipos de grafo  (grafos orientados, grafos ponderados, pseudografos, multigrafos, ...). 

  • Conocer las principales propiedades de los grafos y saber analizarlas en un grafo concreto.

  • Conocer los problemas más usuales sobre grafos (busca de caminos, distancia mínima, árbol de expansión mínim, ..), los algoritmos que los resuelven y saber aplicarlos en un grafo concreto.

  • Ser capaz de representar y analizar un problema en términos de la teoría de grafos.

  • Conocer el concepto de complejidad temporal y espacial de un algoritmo y saber analizarla en algoritmos concretos.

  • Saber explicar los límites prácticos de cálculo en un ordenador (tratable vs intratable) y la jerarquía de clases de complejidad.

  • Ser capaz de clasificar un problema dentro de la clase de complejidad apropiada.

  • Ser capaz de comparar la complejidad de un problema con la otros problemas conocidos.

  • Saber reconocer los problemas intratables más conocidos y frecuentes, especialmente en el campo de la teoría de grafos.

Amunt

La asignatura se estructura en siete módulos:

Módulo 1. Conceptos previos: funciones y algoritmos

  1. Funciones
  2. Algoritmos

Módulo 2. Fundamentos de grafos

  1. Caracterización de un grafo
  2. Estructura y manipulación  de grafos

Módulo 3. Recorrido y conectividad

  1. Recorridos
  2. Algoritmos de exploración de grafos
  3. Conectividad
  4. Distancias de un grafo

Módulo 4. Árboles

  1. Conceptos básicos
  2. Árboles generadores
  3. Árboles con raíz

Módulo 5. Grafos eulerianos y grafos hamiltonianos

  1. Grafos eulerianos
  2. Grafos hamiltonianos

Módulo 6. Complejidad computacional

  1. El concepto de problema
  2. Medidas de complejidad
  3. Reducción y completitud

Módulo 7. Problemas intratables

  1. Problemas intratables sobre grafos
  2. Otros problemas intratables

Amunt

Lógica de enunciados PDF
Recorridos y conectividad PDF
Grafos eulerianos y grafos hamiltonianos PDF
Fundamentos de grafos PDF
Árboles PDF
Conceptos previos: funciones y algoritmos PDF
Complejidad computacional PDF
Los números PDF
Elementos de álgebra lineal y geometría PDF
Problemas intratables PDF

Amunt

La asignatura se ha estructurado en siete módulos, cada uno de los cuales se desarrolla en estos apartados: la introducción, los objetivos, el cuerpo teórico con los ejercicios y los ejemplos correspondientes, una colección de ejercicios de autoevaluación, y bibliografía específica recomendada.

En cuanto a la forma en que se presentan estos contenidos, se utilizan tres tipos de material esencial y un material opcional pero recomendado:

  1. Módulos didácticos. Este material está constituido por los 7 módulos de la asignatura disponibles en formato PDF en el aula de la asignatura.
  2. Guía de estudio, disponible en el aula, proporciona un calendario detallado de estudio de los módulos y de realización de actividades de aprendizaje.
  3. Libro de problemas que podéis encontrar en la apartado Herramientas de soporte - Resumen de ejercicios de grafos y complejidad del espacio del aula Recursos. Es un material de especial interés con problemas de toda la asignatura, algunos totalmente resueltos y el resto con la solución indicada (gran parte de estos problemas han sido propuestos en las PECs y Exámenes Finales de ediciones anteriores de la asignatura).

Además, la asignatura dispone al espacio Recursos, consultable on-line desde el aula, varios tipos de material, organizados según su importancia y tipología. A lo largo del curso se darán estrategias para un uso adecuado de todos estos materiales y un mejor aprovechamiento de sus posibilidades.

Amunt

El proceso de evaluación se fundamenta en el trabajo personal de cada estudiante y presupone la autenticidad de la autoría y la originalidad de los ejercicios realizados.

La falta de autenticidad en la autoría o de originalidad de las pruebas de evaluación; la copia o el plagio; el intento fraudulento de obtener un resultado académico mejor; la colaboración, el encubrimiento o el favorecimiento de la copia, o la utilización de material o dispositivos no autorizados durante la evaluación, entre otras, son conductas irregulares que pueden tener consecuencias académicas y disciplinarias graves.

Por un lado, si se detecta alguna de estas conductas irregulares, puede comportar el suspenso (D/0) en las actividades evaluables que se definan en el plan docente - incluidas las pruebas finales - o en la calificación final de la asignatura, ya sea porque se han utilizado materiales o dispositivos no autorizados durante las pruebas, como redes sociales o buscadores de información en internet, porque se han copiado fragmentos de texto de una fuente externa (internet, apuntes, libros, artículos, trabajos o pruebas del resto de estudiantes, etc.) sin la correspondiente citación, o porque se ha practicado cualquier otra conducta irregular.

Por el otro, y de acuerdo con las normativas académicas, las conductas irregulares en la evaluación, además de comportar el suspenso de la asignatura, pueden dar lugar a la incoación de un procedimiento disciplinario y a la aplicación, si procede, de la sanción que corresponda.

La UOC se reserva la potestad de solicitar al estudiante que se identifique o que acredite la autoría de su trabajo a lo largo de todo el proceso de evaluación por los medios que establezca la universidad (síncronos o asíncronos). A estos efectos, la UOC puede exigir al estudiante el uso de un micrófono, una cámara u otras herramientas durante la evaluación y que este se asegure de que funcionan correctamente.

La verificación de los conocimientos para garantizar la autoría de la prueba no implicará en ningún caso una segunda evaluación.

Amunt

Esta asignatura puede superarse únicamente mediante la realización de un examen final (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.

 

Amunt