• Author / Uploaded
• afvelasco

Citation preview

Escuela de Ingeniería de Sistemas y Computación Fundamentos de Análisis y Diseño de Algoritmos Profesor Andrés Fernando Velasco Examen Final – Tiempo: 90 minutos 7 de junio de 2016 1. Considere el ordenamiento:

siguiente

algoritmo

de

SelectionSort(A) 1 for i = 1 to n–1 2 do min_ind = 1 3 for j = i+1 to n 4 do if A[j] < A[min_ind] 5 then min_ind = j 6 exchange(A[min_ind],A[i])  



(10%) Describa el estado del arreglo A cada que el algoritmo va a ejecutar la línea 1, para A = {4, 9, 14, 8, 7} (15%) Sea T(n) el número de comparaciones efectuadas por SelectionSort para entradas de tamaño n en el peor caso. ¿Cuál es el orden de T(n)? Se espera que su respuesta sea lo más exacta posible. (15%) Si usted debe escoger entre InsertionSort visto en clase y el SelectionSort descrito en este punto, ¿Cuál escogería? Justifique su respuesta utilizando para ello no más de 6 líneas.

2. (60%) Optimización En una compañía se desea organizar una fiesta de integración. Para que la fiesta sea todo un éxito y no vaya a haber “desintegración” de ninguna clase, la oficina de recursos humanos h ahecho un estudio muy serio sobre la capacidad que tiene cada empleado de “pasar y hacer pasar rico a otros” en una fiesta. Esta capacidad, que llamaremos el grado de diversión del empleado ha sido medida con un entero positivo entre 1 y 100 para cada empleado. Además, esta oficina, consciente de que las relaciones de que un empleado con su jefe directo pueden ser muy difíciles y que los tragos en las fiestas hacen que las personas sean más “francas”, ha impuesto como regla, que a ninguna fiesta de integración de la compañía puede invitarse a un empleado y su jefe directo. Se supone que la estructura jerárquica de la compañía es un árbol cuya raíz es el presidente, y el padre de cada nodo es el jefe directo en la compañía. La oficina desea realizar una fiesta de integración que cumpliendo esta regla, maximice la posibilidad que la fiesta sea todo un éxito, es decir, tal que la suma de los grados de diversión de los invitados sea máxima.

El problema consiste en confeccionar una lista de invitados que cumpla con este requisito. a. (10%) Suponga que n=8 y que el árbol de la empresa (entre paréntesis el grado de diversión) es el siguiente:

Describa una solución cualquiera y calcule su costo. b. (30%) Describa una solución voraz que resuelva el problema planteado, identificando los elementos de este tipo de algoritmos c. (10%) Demuestre o refute que el algoritmo propuesto en el punto anterior es óptimo.