2 problemas resueltos de Diseño de algoritmos

MINIPROYECTO II 
Fundamento de Análisis y Diseño de Algoritmos 
 
 
 
 
 
 
 
 
 
ÁLVARO JOSÉ LOBATON RESTREPO 
Código 1130054 
JHON JAIRO PANTOJA ROSERO 
Código 1125572 
JHON FREIDY LOURIDO 
Código 1124153 
 
 
 
 
 
 
 
 
 
 
Presentado a 
ARANDA BUENO JESUS ALEXANDER 
Profesor 
 
 
 
 
 
 
 
 
 
 
 
 
 
UNIVERSIDAD DEL VALLE 
ESCUELA DE INGENIERÍA EN SISTEMAS Y COMPUTACIÓN 
Santiago de Cali I.

ORGANIZACIÓN DE TURNOS DE MONITORIAS 

 
A. Solución exhaustiva 
 
❖ Análisis de la complejidad temporal 
 
La  idea  exhaustiva  consiste  en  obtener todas las posibles combinaciones de estudiantes, descartando aquellas en 
las  que  haya  conflictos  y  obtener  aquella  cuya  utilidad,  es  decir,  la  suma  de  horas  de  todos  los  horarios  de los estudiantes pertenecientes a la solución, sea máxima.  
 
Primero se realiza  un ciclo con r igual 1 hasta N, para obtener los  posibles tamaños de las combinaciones y en su 
interior  calcular  las  combinaciones  a  partir  del  conjunto  de  estudiantes  que  sean   de  tamaño  r.  Es  decir  que 
tendríamos la siguiente sumatoria: 
 
n

n!
∑ i! (n− i)!

(1) 

i=1

Por Teorema del Binomio tenemos: 
 
n

n

i=0

i=0

n

∑ (n i) −(n 0) = ∑ (n i) 1i1n−i − (n 0) = ((1 + 1) − 1) = 2n

(2) 
 

 
Lo  que  se  realiza por  cada  conjunto es, determinar si  hay conflictos, que tiene una complejidad O(n) y si no los  
hay  calcular  el  beneficio  brindado  por  ese  conjunto  que  igualmente  posee  una  complejidad  O(n).  Para  
determinar si hay  conflictos recorro el  tamaño del conjunto combinación, llenando otro arreglo de 24 posiciones 
con  los  índices  de  cada  estudiante  ubicado  en  las  horas donde  tiene turno, si se accede a una posición  que ya ha 
sido  llenada  anteriormente  el  algoritmo  se  detiene  retornando  false,  si  esto  nunca  sucede  retorna  true.  Las 
instrucciones  en  el   ciclo  más  interno se  realiza  n*24,  ya  que  en el  peor  de  los  casos  únicamente  se  llenan  esa cantidad de posiciones, por eso la complejidad es O(n). Luego para calcular el beneficio de una posible solución, 
se suman los horarios de cada estudiante perteneciente al conjunto, esto se realiza n veces.  
 
n​
La complejidad del algoritmo sería entonces exponencial, O(2​
). 
 
❖ Detalles principales de la implementación 
 
La  implementación  se  realizó  en  Java.  Para   lograr  realizar  las combinaciones  se  uso  la  libreria 
combinatoricslib­2.1.jar [1]. 
 
❖ Descripción y análisis de las pruebas realizadas 
 
Los  archivos  de prueba  se  realizaron  con un  generador  de  entradas  para  dos tipos  de distribuciones de  horarios 
en   el  día;  distribución  normal  y  uniforme.  Se  obtuvieron   los  tiempos  de  ejecución  para  5   archivos,  que incrementan su tamaño de 5 en 5, presentados en la TABLA I. 
 
TABLA I. Tiempos de ejecución obtenidos por cada distribución en milisegundos. 
Nombre del 
archivo 

Tamaño del 
archivo 

Distribución 
Normal 

Distribución 
Uniforme 

Students1 

5 

13 

12 

Students2 

10 

28 

47 

Students3 

15 

173 

173 

Students4 

20 

597 

563 

Students5 

25 

14142 

14894 

 
 
❖ Conclusiones y aspectos a mejorar 
 
Podemos apreciar  que  los  tiempos  de  ejecución  no  se  ven  afectados  por  el  tipo  de  distribución,  esto  se debe  a 
que  no  hay una porción en el código en la cual, la  manera en que estén distribuidos los  horarios influya. Además 
es evidente el comportamiento exponencial del tiempo de ejecución. 
 
B. Solución voraz 
 
❖ Análisis de la complejidad temporal 
En  primera  instancia la solución  mediante  programación  voraz  debe  de organizar la  lista de monitores en orden  
creciente  tomando como  parámetro  de  ordenamiento  la  hora  final  del turno de cada monitor, para lograr esto se 
empleó  el  método  de  ordenamiento  heapsort  por  lo  cual  toma  una  complejidad  de  O(nlogn). Luego  por  cada 
monitor  i  se suma la duración  del turno de i y ...