Algorítmica

Teoría de Algoritmos

Divide y Vencerás
Práctica 2
Crisanto Jiménez López de Teruel [23298392-J] Manuel González Segura [23293054-B] Marco Fuentes García [76423488-P]

Divide y Vencerás

22 de noviembre de 2010

1. Determinación de umbrales
Umbral óptimo
Lo primero que vamos a hacer es determinar el umbral óptimo del algoritmo MergeSort ejecutándolo con pocos elementos y muchasrepeticiones. Para que siempre ejecute el algoritmo con el método “Divide y Vencerás” le pondremos un umbral muy pequeño y para que ejecute siempre un algoritmo básico un umbral muy grande. Haciendo las gráfica de las distintas ejecuciones nos queda los siguiente:

Vemos que se cortan en un elemento cercano a 70. Vamos a hacer el ajuste híbrido para ver cómo queda. De esta forma se verá más claro elcorte entre ellas y podremos determinar una forma de sacarlo.

2

Divide y Vencerás

22 de noviembre de 2010

La siguiente gráfica muestra únicamente los ajustes de las dos gráficas:

3

Divide y Vencerás

22 de noviembre de 2010

Con la ayuda de WxMáxima hemos igualado las ecuaciones de los distintos ajustes para despejar el valor de x:

Vemos que nos da dos soluciones:   x= 4.403 x = 67.115

Ya sabemos que uno de los valores óptimos del umbral es U = 67.115 como vemos más arriba.

4

Divide y Vencerás

22 de noviembre de 2010

Umbrales de tanteo
Ahora seleccionamos distintos umbrales (inferiores y superiores al óptimo) para obtener los tiempos de ejecución reales para distintos casos del problema. Estos son los umbrales de tanteo.      U = 50 U =60 U = 67 => Umbral óptimo U = 80 U = 90

En la gráfica comparativa vemos la evolución de los tiempos de ejecución del algoritmo para los distintos valores del umbral obtenidos. Haciendo la gráfica comparativa de los ajustes híbridos vemos que la del umbral óptimo es la que más constante se mantiene. Aunque nunca sea la que menos tiempo emplea, tampoco es la que más tarda en ningún momento.

5Divide y Vencerás

22 de noviembre de 2010

6

Divide y Vencerás

22 de noviembre de 2010

2. Elemento máximo y mínimo
Algoritmo
El algoritmo lo que hace es devolver el elemento máximo y mínimo de todo el vector. Para ello va partiendo el vector por la mitad dejando la parte izquierda y la parte derecha. De forma recursiva iremos cogiendo los elementos máximo y mínimo de loscuatro devueltos por las distintas partes (izquierda y derecha). En el caso base nos quedará un vector con uno o dos elementos (vector par o impar) en el que devolveremos los dos elementos o uno en el caso más simple. Este código es una función recursiva que acepta como parámetro un vector y devuelve los elementos menor y mayor de todos. Para empezar hay que tener en cuenta si el vector tiene un numerode elementos par o impar, seguidamente tiene varios casos base, en los que si el tamaño del vector es 1 o 2 devuelve los elementos, haciendo (en su caso) que termine la recursividad, en nuestro caso no tenemos return al ser nuestra función void:
void funcion (int & v1, int & v2, int v[], int n, int principio, int fin){ int vl1, vl2, vr1, vr2; int nizq, nder; if(n%2 != 0){ nizq = n/2; nder = n/2+1; } else{ nizq = n/2; nder = n/2; } if(n == 1){ v1 = v[principio]; v2 = v[principio]; } else if ( n == 2 ){ if(v[principio] < v[fin]){ v1 = v[principio]; v2 = v[fin]; } else { v1 = v[fin]; v2 = v[principio]; } }

7

Divide y Vencerás

22 de noviembre de 2010

Si no entras en cualquiera de ellos pasas a la llamada recursiva y más tarde a más comparaciones para, al terminar lasrecurrencias y cuando ya quedan únicamente 4 elementos, compararlos y quedarnos con el más pequeño y el mayor.
if(n!=1 && n!=2){ funcion ( vl1, vl2, v, nizq, principio, n/2); funcion ( vr1, vr2, v, nder, n/2+1, fin); if( vl2 < v2 } else{ v2 } if( vl1 < v1 } else{ v1 } } vr2){ = vr2; = vl2; vr1){ = vl1; = vr1;

Eficiencia

Una vez que lo tenemos implementado calculamos su eficiencia híbrida: Como...