ISIS1105 202320 Examen2 - Solucion

Ingeniería de Sistemas y Computación
ISIS1105 – Diseño y análisis de algoritmos

Sección 1. Profesor: Jorge Duitama
Semestre: 2023-20
Solución Examen 2
Este examen es individual. Tiene una duración de 1 hora 20 min. Está prohibido usar el
libro, apuntes, impresiones y cualquier tipo de dispositivo electrónico (celulares,
agendas electrónicas, cámaras digitales, etc.).
Nombre:_________________________________________________ Código: _____________________
1. Charlie, el dueño de la fábrica de chocolates, descubirió que había dos tipos de

Oompa Loompas. Mientras que algunos solamente dicen la verdad, otros solamente
dicen mentiras. Charlie ideó el siguiente experimento para intentar diferenciar los dos
tipos de Oompa Loompas. Cada vez que veia dos oompa loompas les hacia una
pregunta. Si veia que los dos oompa loompas le daban respuestas diferentes, anotaba
sus nombres. Cada oompa loompa fue entrevistado mas de una vez. Charlie quiere
saber si se puede hacer un programa que a partir de esta información y conociendo un
oompa loompa que siempre dice la verdad, pueda determinar quienes dicen siempre la
verdad y quienes siempre dicen mentiras.
a. [10%] Describir entradas y salidas del problema
E/S Nombre Tipo Descripción
E L List of Oompa Loompa Lista de oompa loompas entrevistados
E E Set of Oompa Loompa Parejas de Oompa Loompas que contestaron

x Oompa Loompa distinto a una pregunta
E v Oompa Loompa Oompa Loompa que siempre dice la verdad
S b Boolean Indica si se puede saber qué Oompa

Loompas siempre dicen la verdad y quienes
siempre dicen mentiras
b. [15%] Diseñar una estructura de grafo que permita resolver el problema. Describir
qué representarían los vértices y qué representarían los ejes. Describir en palabras qué
algoritmo de teoría de grafos se puede utilizar para resolver el problema dado.
Los vértices serían Oompa Loompas. Hay un eje entre cada pareja de oompa Loompas
que hayan dado respuestas diferentews a una pregunta. El problema se reduce a
determinar si el grafo es bipartito y conexo. Las dos propuiedades se pueden verificar
con un recorrido sencillo (BFS o DFS)
c. [30%] Implementar un programa que resuelva el problema con complejidad

algoritmica O(N + P) siendo N el total de oompa loompas entrevistados y P la cantidad
de parejas entrevistadas.
class Pareja {
String ol1;
String ol2;
}
public boolean [] clasifyOL (List<String> L, Set<Pareja> E, String v) {

int N = L.size();
boolean [] answer = new boolean[N];
Map<String,Integer> reverseList = new HashMap<>();

for(int i=0;i<N;i++) reverseList.put(L.get(i), i);
List<Set<Integer>> graph = buildGraph(E, reverseList);
int [] level = new int [N];

Arrays.fill(level, -1);
int s = reverseList.get(v);
level[s] = 0;
answer[s] = true;
Queue<Integer> q = new LinkedList<>();
q.add(s);
int total;
for(total = 0;!q.isEmpty();total++) {
int next = q.poll();
int childLevel = level[next]+1;
for(int child:graph.get(next) ) {
if(level[child] == -1) {
level[child] = childLevel;
answer[child] = childLevel%2==0;
q.add(child);
} else if (level[child]!=childLevel) return null;
}
}
if(total<N) return null;
return answer;
}
private List<Set<Integer>> buildGraph(Set<Pareja> E, Map<String, Integer>
reverseList) {
int N = reverseList.size();
List<Set<Integer>> graph = new ArrayList<>(N);
for(Pareja p: E) {
int o1 = reverseList.get(p.ol1);
int o2 = reverseList.get(p.ol2);
graph.get(o1).add(o2);
graph.get(o2).add(o1);
}
return graph;
}
2. Animado por el resultado del experimento anterior, Charlie tuvo acceso a la red
social de los oompa loompas. De esta red social, pudo saber qué relaciones de amistad
había entre ellos. Charlie quiere seleccionar parejas de oompa loompas y asignarle a
cada pareja el diseño de un tipo nuevo de chocolate. Cada pareja debe cumplir dos
condiciones: 1) Tener una relación de amistad y 2) Uno de los dos debe decir siempre
la verdad y el otro debe decir siempre mentiras. Cada oompa loompa solamente puede
trabajar en el diseño de un tipo de chocolate. Charlie ahora quiere un programa que le
ayude a determinar cuantas parejas puede armar como máximo con estas condiciones.
a. [10%] Describir entradas y salidas del problema
E/S Nombre Tipo Descripción
E L List of Oompa Lista de oompa loompas entrevistados

Loompa
E A Set of Oompa Parejas de Oompa Loompas con relación de

Loompa x Oompa amistad
Loompa
E v List of boolean Indica por cada Oompa Loompa si siempre
dice la verdad
S m int Cantidad máxima de parejas de oompa

loompa que pueden trabajr en el diseño de
un chocolate de acuerdo con las condiciones
b. [10%] Diseñar una estructura de grafo que permita resolver el problema. Describir
qué representarían los vértices y qué representarían los ejes.
Los vértices serían los Ompa Loompas entrevistados. Se haría un eje entre cada par de
Oompa Loompas que cumplan dos condiciones:
1. Que tengan una relación de amistad

2. Que uno diga siempre la verdad y el otro siempre diga mentiras
c. [15%] ¿Se podría utilizar flujo en redes para resolver este problema? En caso de ser
posible, describir un procedimiento para resolver el problema como una instancia de
flujo en redes. Apoyar su explicación con una gráfica.
El problema a resolver correspionde al problema de emparejamiento bipartito máximo,

si se tiene en cuenta que el grafo diseñado es bipartito. Se puede resolver con flujo en
redes si se toman como fuentes los oompa lompas que siempre dicen la verdad, como
destinos los oompa loompas que siempre dicen mentiras y se le da dirección a todos
los ejes, de modo que cada eje va de un oompa loompa que siempre dice verdad a uno
que siempre dice mentiras (ver figura). El siguiente gráfico ilustra el diseño del grafo
para cuatro oompa lompas que siempre dicen la verdad (v1-v4) y 3 que siempre dicen
mentiras (m1 – m³). Las capacidades de todos los ejes serían 1.
v1
m1
v2
m2
s v3 t
m3
v4
Para resolver el inconveniente de múltiples fuentes y múltiples destinos y para

restringir a una sola pareja por vértice, se agrega un nodo fuente conectado a cada
oompa loompa que siempre dice la verdad y un nodo destino al que se conecta cada
oompa lompa que siempre dice mentiras con capacidad 1.
3. [20%] Demostrar que todo prefijo de un camino de costo mínimo es un camino de
costo mínimo
Dada una fuente s, un destino t y un nodo intermedio a en el camino de costo mínimo

L* entre s y t, se razona por contradicción que el prefijo P=<s,…,a> no es un camino de
costo mínimo.
1. L* = <s,…,a,b,…,t> es un camino de costo mínimo entre s y t.

2. P = <s,…,x,…,a> no es un camino de costo mínimo entre s y a.
3. Q = <s,…,y,…,a> ≠ P es un camino de costo mínimo entre s y a.
4. c(Q) < c(P) por definición de camino de costo mínimo
5. c(Q) + c(<b,…,t>) < c(P) + c(<b,…,t>)
6. c(Q) + c(<b,…,t>) < c(L*)
7. c(<s,…,y,…,a,b,…,t>) < c(L*)
7 es contradoctorio con 1 porque si L* es un camino de costo mínimo, entonces ningun

otro camino entre s y t puede tener menor costo.

ISIS1105 202320 Examen2 - Solucion

Cargado por

Copyright:

Formatos disponibles

ISIS1105 202320 Examen2 - Solucion

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

ISIS1105 202320 Examen2 - Solucion

Cargado por

Copyright:

Formatos disponibles

Ingeniería de Sistemas y Computación

ISIS1105 – Diseño y análisis de algoritmos

Nombre:_________________________________________________ Código: _____________________

1. Charlie, el dueño de la fábrica de chocolates, descubirió que había dos tipos de

a. [10%] Describir entradas y salidas del problema

E/S Nombre Tipo Descripción

E L List of Oompa Loompa Lista de oompa loompas entrevistados

E E Set of Oompa Loompa Parejas de Oompa Loompas que contestaron

E v Oompa Loompa Oompa Loompa que siempre dice la verdad

S b Boolean Indica si se puede saber qué Oompa

c. [30%] Implementar un programa que resuelva el problema con complejidad

public boolean [] clasifyOL (List<String> L, Set<Pareja> E, String v) {

Map<String,Integer> reverseList = new HashMap<>();

List<Set<Integer>> graph = buildGraph(E, reverseList);

int [] level = new int [N];

a. [10%] Describir entradas y salidas del problema

E/S Nombre Tipo Descripción

E L List of Oompa Lista de oompa loompas entrevistados

E A Set of Oompa Parejas de Oompa Loompas con relación de

S m int Cantidad máxima de parejas de oompa

1. Que tengan una relación de amistad

El problema a resolver correspionde al problema de emparejamiento bipartito máximo,

Para resolver el inconveniente de múltiples fuentes y múltiples destinos y para

Dada una fuente s, un destino t y un nodo intermedio a en el camino de costo mínimo

1. L* = <s,…,a,b,…,t> es un camino de costo mínimo entre s y t.

7 es contradoctorio con 1 porque si L* es un camino de costo mínimo, entonces ningun

También podría gustarte

Nombre:_____________________________ Código: _