Grafos y Complejidad.

Dificultad (1-4):

2,77

Temática:

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

Opiniones Generales:

La opinión de este alumno ha sido confirmada por varios más, así que directamente la pongo:
En general es una asignatura a la que debes dedicarle un cierto tiempo, pues hay partes que son complicadas de asimilar y debes asimilarlas poco a poco. Pero a pesar de esto, es una asignatura fácil de aprobar.

Materiales:
Los materiales están más o menos bien, aunque siempre hay algunas pegas.
Módulo 1. Funciones y algoritmos – Un poco de combinatoria (funciones), saber el nº de operaciones que hace un algoritmo y en función de las operaciones,
saber si crece linealmente, exponencialmente,…
Módulos 2, 3, 4, 5. Grafos, árboles y algoritmos para recorrerlos. Es la parte más fácil de la asignatura, pero en algunos casos hay que recopilar la información por varios módulos.
Modulos 6 y 7. Complejidad computacional y problemas intratables. Esta es la parte más difícil, de hecho debería llamarse problemas infumables Very Happy. Pero en el examen se portan muy bien con la pregunta de estos temas, pues ponen un ejercicio de verdadero/falso. Eso sí, razonando la respuesta.

PACS: Hay tres PACS en las que dan 3 semanas para hacerlas, con lo que hay tiempo suficiente. Normalmente, las preguntas contienen varios apartados fáciles, pero hay veces que te ponen un apartado en el que te quedas con esta cara eeeeek Pero son pocos, así que la PAC se supera siempre.

Examen: El examen en lo más fácil que tiene esta asignatura (siempre que hayas seguido la evaluación continua y hayas estudiado). Consta de 4 ejercicios con varios apartados. El ejercicio 1, normalmente del módulo 1. No suele ser una pregunta fácil, pero de la que puedes rascar siempre algo de algún apartado. Los ejercicios 2 y 3, sobre grafos y árboles. Estas 2 preguntas son las que hacen que el examen se pueda aprobar, pues ponen algún algoritmo de recorrido de grafos o de árboles o alguna pregunta sobre un tipo de grafo. Suelen ser relativamente fáciles de contestar.
El ejercicio 4, sobre complejidad y problemas intratables. Suele ser un poco de lotería, pero siempre hay alguna que sabes contestar, ya que son parecidas a las de otros años o las de las PACS