75.

569 · Grafos y Complejidad · PEC3

2023-24-Sem. 2 · Grado en Ingerierı́a Informática
Estudios de Informática, Multimedia y Telecomunicación

Presentación

Esta PEC profundiza en el concepto de complejidad computacional que cubre los contenidos es-
tudiados en los módulos 6 y 7 de la asignatura. Los ejercicios trabajan los conceptos de medida
de complejidad, la reducción y completitud, la clase NP-completo y algunos de los problemas
intratables más importantes que se conocen.

Competencias

En esta PEC se trabajan las siguientes competencias del Grado de Ingenierı́a Informática:

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 en cada situación

y aplicar las habilidades y conocimientos adquiridos para resolverlo.

Objetivos

Los objetivos concretos de esta PEC son:

Entender los conceptos de intratabilidad y no-determinismo.

Conocer las diferentes clases de complejidad y saber clasificar los problemas en cada una de
estas.
Entender el concepto de reducción entre problemas y saber demostrar cuando un problema
es NP-completo.
Reconocer problemas intratables que aparecen de forma habitual en informática y en inge-
nierı́a.
Entender y saber aplicar las técnicas básicas de reducción polinómica de los problemas NP-
completos.

1
 75.569 · Grafos y Complejidad · PEC3
2023-24-Sem. 2 · Grado en Ingerierı́a Informática
Estudios de Informática, Multimedia y Telecomunicación

Descripción de la PEC a realizar

1. (Valoración de un 25 % = (10 %+10 %+(2,5 %+2,5 %))

a) Expresar en FNC la siguiente fórmula booleana (detallar los pasos seguidos):

(¬(d ∨ ¬e) ∧ c) ∨ ¬(a ∨ ¬b).

b) Tenemos una fórmula booleana f en las variables a, b y c de la que sabemos que los
únicos valores de verdad de estas variables que nos hacen f verdadera son

(a, b, c) = (0, 0, 1)

(a, b, c) = (1, 1, 0), (a, b, c) = (0, 1, 0)

y
(a, b, c) = (1, 1, 1).
Calcular una formal normal conjuntiva de f .
c) Decir si son verdaderas o falsas las siguientes afirmaciones, justificando las respuestas.
1) La fórmula booleana ¬a ∧ b está en FNC.
2) La fórmula booleana
(¬a ∨ ¬c) ∧ (a ∨ c)
está en FNC.

2. (Valoración de un 20 % = (2 % + 2 % + 2 % + 2 % + 2 %+ 2 %+ 2 %+ 2 %+ 2 %+ 2 % )

a) Sean A un problema cualquiera y B un problema que pertenece a la clase de complejidad

P . Justificar si las siguientes afirmaciones son ciertas o falsas, suponiendo que P ̸= NP .

1) Si 3SAT ≤p A entonces A ≤p B.
2) Si A ≤p B, se deduce que A ∈ P .
3) Si A ≤p B, se tiene que A nunca puede ser NP -completo.
4) Si A está en la clase NP entonces A nunca puede resolverse en tiempo polinómico.
5) Si A es NP -completo entonces nunca puede ocurrir que B ≤p A.
6) Existen problemas de la clase EXP que no están en la clase P .

b) Una empresa quiere mejorar los siguientes procesos:

2
 75.569 · Grafos y Complejidad · PEC3
2023-24-Sem. 2 · Grado en Ingerierı́a Informática
Estudios de Informática, Multimedia y Telecomunicación

7) Cargar un contenedor de transporte: Esto es, cargar un contenedor con objetos a

enviar de forma que proporcione el mayor beneficio a la empresa sin exceder su
carga (peso) máxima autorizada. Cada objeto a cargar tiene asociado un peso y el
beneficio que obtiene la empresa con el mismo.
8) Determinar el número de repartidores necesarios: La empresa tiene un grafo en
el que los nodos representan entregas a realizar. Dos nodos están conectados por
una misma arista si ambas entregas tienen el mismo horario. Sabiendo que para
cada horario son necesarios tantos repartidores como entregas a realizar, calcular el
número mı́nimo de repartidores requeridos para realizar todas las entregas.
9) La empresa dispone de otro grafo en el que cada nodo representa a un repartidor,
y hay una arista entre dos nodos si ambos repartidores han repartido juntos alguna
vez. La empresa quiere saber cuál es el mayor grupo de repartidores tal que cualquier
pareja de ese grupo haya trabajado junta alguna vez.
10) A partir del grafo del ı́tem anterior, la empresa quiere averiguar cuál es el grupo con
menor número de empleados tal que tengamos asegurado que cualquier repartidor
de la empresa ha trabajado alguna vez con algún repartidor de este grupo.
Para cada uno de ellos, establece un paralelismo con algún problema estandard tratado
durante el curso, detallando este paralelismo.

3. (Valoración de un 25 % = 7 %+7 %+11 %)

Consideramos los dos problemas siguientes:
1. El primer problema, que denotaremos como IT , consiste en calcular la matriz inversa de
una matriz cuadrada triangular superior no singular de tamaño arbitrario n × n. Recordamos
que una matriz cuadrada se dice triangular superior si por debajo de la diagonal principal
todos sus elementos son ceros (en la diagonal puede aparecer cualquier número).
2. El segundo problema, que denotaremos como IT 2, consiste en calcular la matriz inversa
de una matriz cuadrada triangular superior no singular cuyo tamaño es una potencia de 2.
Se pide:

a) Expresar ambos problemas como problemas de cálculo (conjunto de instancias, de solu-

ciones y definiciones de los problemas).
b) Expresar ambos problemas como problemas decisionales (conjunto de instancias, de
soluciones y definiciones de los problemas).
c) Probar que el problema decisional IT se puede reducir polinómicamente al problema
decisional IT 2 dando de manera explı́cita la función de reducción.

3
 75.569 · Grafos y Complejidad · PEC3
2023-24-Sem. 2 · Grado en Ingerierı́a Informática
Estudios de Informática, Multimedia y Telecomunicación

4. (Valoración de un 30 %) Cuestionario de evaluación Moodle

Dentro del aula de la asignatura, en el Campus Virtual, encontraréis la herramienta Moodle
en la parte derecha. En este Moodle hay un cuestionario con diversas preguntas que debéis
resolver como último ejercicio de esta PEC.
Leed atentamente las siguientes instrucciones antes de abrir el cuestionario:
Los contenidos que se evalúan en este cuestionario corresponden a los módulos 6 y 7 de
la asignatura. Es importante que hayáis asimilado estos conocimientos antes de abrir
el cuestionario.
Para visualizar correctamente el cuestionario, utilizad Chrome o Firefox.
El cuestionario estará abierto durante el plazo de la PEC y lo podéis resolver cuando
queráis. De todas formas, una vez lo abráis tendréis un tiempo limitado para resolverlo
(40 minutos).
Importante: El cuestionario quedará cerrado a las 23:59 de la fecha lı́mite de entrega.
Si empezáis a hacerlo después de las 23:19 del último dı́a, ¡tendréis menos de cuarenta
minutos para hacerlo!
Las respuestas a las preguntas se tienen que introducir directamente en el cuestionario
Moodle. No es necesario que las entreguéis junto con el resto de respuestas de la PEC.
Las preguntas del cuestionario son aleatorias: cada estudiante recibirá un enunciado
diferente.
En algunas preguntas tendréis que introducir la respuesta en un formato especı́fico (p. ej.
con los valores ordenados de una determinada forma y sin espacios). Es muy importante
seguir fielmente el formato indicado a la hora de introducir vuestra respuesta.
Disponéis de 2 intentos para resolver el cuestionario. El objetivo de tener dos intentos es
poder solventar posibles problemas que hayáis tenido en la realización del cuestionario,
ya sean problemas técnicos o bien que hayáis abierto el cuestionario por error. Por tanto,
debéis tener en cuenta que:
• La nota que obtendréis en el cuestionario será la de vuestro último intento.
• Después del 1r intento, no recibiréis la calificación obtenida ni recibiréis feedback
sobre vuestra propuesta de solución. Por lo tanto, no recomendamos usar el 2o
intento para intentar mejorar nota, ya que puede ser que obtengáis una nota inferior.
• Si usáis el 2o intento, el enunciado que encontraréis será diferente del del 1r intento.
• Podéis realizar los dos intentos en dı́as diferentes, siempre que sea dentro del plazo
de la PEC. Dispondréis de 40 minutos para cada intento.
• Cada vez que iniciéis el cuestionario contará como un intento, aunque no enviéis
la respuesta. Por ejemplo, si habéis hecho el 1r intento y volvéis a abrir el
cuestionario, invalidaréis vuestro 1r intento y os quedaréis con la nota
del 2o.

4
 75.569 · Grafos y Complejidad · PEC3
2023-24-Sem. 2 · Grado en Ingerierı́a Informática
Estudios de Informática, Multimedia y Telecomunicación

Recursos

Recursos Básicos
Módulo didáctico 6. Complejidad computacional.
Módulo didáctico 7. Problemas intratables.
Colección de problemas

Recursos Complementarios
Ejemplos de aplicaciones de la teorı́a de grafos.

Applets interactivos sobre algoritmos de grafos.

Criterios de valoración
La PEC se tiene que resolver de forma individual. En caso que hayáis consultado recursos
externos, es necesario referenciarlos.
Es necesario justificar la respuesta de cada apartado. Se valorará tanto el resultado final como
la justificación dada.

En los apartados donde sea necesario aplicar algún algoritmo, se valorará la elección del
algoritmo apropiado, los pasos intermedios, el resultado final y las conclusiones que se deriven.

Formato y fecha de entrega

Hay que entregar un único documento PDF con las respuestas de todos los ejercicios. El nombre
del fichero tiene que ser: PEC3 [Link].

Este documento se tiene que entregar en el espacio Entrega y Registro de EC del aula antes
de las 23:59 del dı́a 29/05/2024. No se aceptarán entregas fuera de plazo.