Universidad Nacional de San Juan
Facultad de Ciencias Exactas, Físicas y Naturales
Carrera: Licenciatura en Ciencias de la Computación
Materia: Estructuras de Datos y Algoritmos
Tema: Técnicas de Diseños de Algoritmos
Técnica de Diseño: Divide y Vencerás
Autores:
● Rebollo Gonzalo
● Vargas Pablo
● Yuste Gabriel
15 de Noviembre de 2024
1)Técnica de Diseño: Divide y Vencerás
Divide y Vencerás es una técnica de diseño de algoritmos que consiste en resolver
un problema a partir de la solución de subproblemas del mismo tipo, pero de menor
tamaño. Si los subproblemas son todavía relativamente grandes se aplicará de
nuevo esta técnica hasta alcanzar subproblemas lo suficientemente pequeños para
ser solucionados directamente. Esto naturalmente
sugiere el uso de la recursión en las implementaciones de estos algoritmos.
Un algoritmo Divide y Vencerás típico resuelve un problema siguiendo estos 3
pasos.
● Dividir
En primer lugar ha de plantearse el problema de forma que pueda ser
descompuesto en k sub-problemas del mismo tipo, pero de menor tamaño.
Es decir, si el tamaño de la entrada es n, hemos de conseguir dividir el
problema en k subproblemas (donde 1 < = k < = n), cada uno con una
entrada de tamaño nk y donde 0 < = nk < n. A esta tarea se le conoce como
división.
● Vencer
Resolver los sub-problemas recursivamente. Este paso recibe un gran
conjunto de sub-problemas a ser resueltos. Generalmente a este nivel, los
problemas se resuelven por sí solos.
● Combinar
Cuando los sub-problemas son resueltos, esta fase los combina
recursivamente hasta que estos formulan la solución al problema original.
Este enfoque algorítmico trabaja recursivamente y los pasos de conquista y
fusión trabajan tan a la par que parece un sólo paso
Uso de recursión en la técnica
Por el hecho de usar un diseño recursivo, los algoritmos diseñados mediante la
técnica de Divide y Vencerás van a heredar las ventajas e inconvenientes que la
recursión, esto es:
● Por un lado el diseño que se obtiene suele ser simple, claro, robusto y
elegante, lo que da lugar a una mayor legibilidad y facilidad de depuración y
mantenimiento del código obtenido.
● Sin embargo, los diseños recursivos conllevan normalmente un mayor tiempo
de ejecución que los iterativos, además de la complejidad espacial que puede
representar el uso de la pila de recursión.
Ejemplos y mejoras de complejidad
Usualmente esta técnica nos permite hacer una reducción bastante significativa en
la complejidad del tiempo del algoritmo a emplear.
Por ejemplo, el método de la burbuja conlleva una complejidad de O(n^2), mientras
que el Quicksort (una aplicación de Dividir y Vencer) reduce la complejidad a
O(nlog(n)). La búsqueda lineal tiene una complejidad de O(n), mientras que la
búsqueda binaria(otra aplicación de dividir y vencer) reduce la complejidad a
O(log(n)).
2) Descripción de la problemática: Moda de un Vector
La moda de un conjunto de datos es el valor que más se repite, actuando como una
medida de tendencia central que identifica el valor de mayor frecuencia en una
muestra o estudio. En este caso, queremos implementar un algoritmo basado en la
técnica de Divide y Vencerás para encontrar la moda de un vector, es decir, el
elemento que se repite más veces en el conjunto de datos. La implementación de
este algoritmo nos permitirá abordar el problema de forma eficiente, dividiendo el
vector en subproblemas más pequeños, resolviendo la moda en cada parte y luego
combinando los resultados. Así, buscamos optimizar el proceso y reducir el tiempo
de ejecución en comparación con métodos más sencillos.
Moda 1
La primera solución consiste en hacer uso de la propia definición de moda. Se
calcula, para cada uno de los elementos del vector, la frecuencia de aparición en el
mismo. Luego se elige el elemento que mas apariciones tuvo.
def frecuencia(a, p, prim, ult):
if prim > ult:
return 0
suma = 0
for i in range(prim, ult + 1):
if a[i] == p:
suma +=1
return suma
def moda1(a, prim, ult):
if prim==ult:
return a[prim]
moda=a[prim]
maxfrec = frecuencia(a, a[prim], prim, ult)
for i in range(prim+1, ult):
frec = frecuencia(a, a[i], i, ult)
if frec>maxfrec:
maxfrec = frec
moda = a[i]
return moda
Evidentemente esta solución tendrá una complejidad de O(n^2), ya que por cada
elemento del vector se realizara una búsqueda mediante la función Frecuencia, la
cual tiene una complejidad de O(n). Esto se realiza a través de todo el vector para
contar cuántas veces aparece el elemento.
Moda 2
Partiendo del caso particular en el que el vector esté ordenado, se puede
aprovechar el concepto de rellano para calcular la moda. Un rellano es una
secuencia de elementos consecutivos idénticos dentro del vector ordenado. Así, al
recorrer el vector, cada vez que encontramos un rellano, podemos contar su
longitud y compararla con la del rellano más largo hallado hasta el momento. De
esta manera, el rellano de mayor longitud representará la moda del vector, ya que
será el conjunto de valores idénticos que aparece con mayor frecuencia. Esta
estrategia reduce la necesidad de realizar múltiples comparaciones, simplificando el
proceso de identificación de la moda en un vector ya ordenado y optimizando la
eficiencia del algoritmo.
def moda2(a,prim,ult):
i=prim+1
p=1
moda=a[prim]
while i<=ult:
if a[i-p]==a[i]:
p+=1
moda=a[i]
i+=1
return moda
La complejidad de este algoritmo por sí solo es O(n). Sin embargo, como es preciso
ordenar primero el vector antes de invocar a esta función, la complejidad del
algoritmo resultante sería de orden O(nlog(n)).
Moda 3
Existe una solución que aplica plenamente la técnica de Divide y Vencerás y es
capaz de mejorar la complejidad de O(nlog(n)). Este algoritmo utiliza dos conjuntos,
llamados homog y heterog, que contendrán en cada paso diferentes subvectores del
vector original. El conjunto homog contendrá sólo aquellos subvectores con todos
sus elementos iguales, mientras que heterog almacenará aquellos con elementos
diferentes.
Para implementar se utiliza un tipo abstracto de datos que representa conjuntos de
subvectores, el cual proporciona las operaciones necesarias sobre estos elementos.
Los subvectores se representan como ternas, donde el primer elemento es el vector
y los otros dos indican las posiciones de inicio y fin de sus elementos.
class Subvector:
__vector: list
__prim:int
__ult=int
def __init__(self,vector,prim, ult):
self.__vector=vector
self.__prim=prim
self.__ult=ult
def getPrim(self):
return self.__prim
def getUlt(self):
return self.__ult
def getVector(self):
return self.__vector
class Conjuntos:
__subvectores:list
def __init__(self):
self.__subvectores = []
def insertar(self, subvector):
self.__subvectores.append(subvector)
def long_mayor(self):
if not self.__subvectores:
return 0
return max([Link]() - [Link]() + 1 for
subvector in self.__subvectores)
def mayor(self):
if not self.__subvectores:
return None
long_max = -1
max_subvector = None
for subvector in self.__subvectores:
longitud = [Link]() - [Link]() + 1
if longitud > long_max:
long_max = longitud
max_subvector = subvector
self.__subvectores.remove(max_subvector)
return max_subvector
def es_vacio(self):
return len(self.__subvectores) == 0
def destruir(self):
self.__subvectores.clear()
def mostrar(self):
for subvector in self.__subvectores:
print([Link]())
Inicialmente, el conjunto homog está vacío, y heterog contiene el vector completo.
En cada iteración, se selecciona el subvector más largo de heterog, se calcula su
mediana, y se divide en tres partes: p1, con los elementos menores que la mediana;
p2, con los elementos iguales a la mediana; y p3, con los elementos mayores que la
mediana. A continuación, se actualizan los conjuntos: p2 se añade a homog,
mientras que p1 y p3 se añaden a heterog.
def moda3(a, prim, ult):
homog = Conjunto()
heterog = Conjunto()
p = Subvector(a, prim, ult)
[Link](p)
while heterog.long_mayor() > homog.long_mayor():
p = [Link]()
mediana = kesimo([Link](),[Link](),[Link](),([Link]()-
[Link]()+2)/2)
izq, der = pivote2([Link](),mediana,[Link](),[Link]())
p1=Subvector([Link](),[Link](),izq-1)
p2=Subvector([Link](),izq,der-1)
p3=Subvector([Link](),der,[Link]())
if [Link]() < [Link]():
[Link](p1)
if [Link]() < [Link]():
[Link](p3)
if [Link]() < [Link]():
[Link](p2)
if homog.es_vacio():
return a[prim]
p = [Link]()
return [Link]()[[Link]()]
Este proceso se repite hasta que la longitud del subvector más largo en heterog sea
menor o igual a la longitud del más largo en homog. En ese punto, el subvector más
largo en homog contendrá la moda del vector original.
Las funciones Kesimo y Pivote2 empleadas, son las propuestas en el capítulo 2 del
libro “Técnicas de diseño de algoritmos”, y se utilizan para calcular la mediana del
vector y dividirlo luego en tres partes, según el esquema general descrito.
def intercambia(a, i, j):
temp = a[i]
a[i] = a[j]
a[j] = temp
def pivote(a, p, prim, ult):
i = prim
l = ult
b=True
while b:
while i <= ult and a[i] <= p:
i += 1
while l >= prim and a[l] > p:
l -= 1
if i < l:
intercambia(a, i, l)
else:
b=False
pivote_index = [Link](p)
intercambia(a, pivote_index, l)
return l
def kesimo(vector,prim,ult,k):
if prim<ult:
l=pivote(vector,vector[prim],prim,ult)
if l>(prim+k-1):
return kesimo(vector,prim,l-1,k)
elif l<(prim+k-1):
return kesimo(vector,l+1,ult,k-1+prim-1)
return vector[l]
else:
return vector[ult]
La función kesimo se utiliza para encontrar el k-ésimo elemento en un subvector, lo
cual permite determinar la mediana en el rango especificado por prim y ult. Llama a
la función pivote para dividir el subvector y luego realiza llamadas recursivas hasta
localizar el k-ésimo elemento. Esta función es fundamental en moda3 para dividir el
subvector en tres partes alrededor de la mediana, facilitando el proceso de partición
homogénea y heterogénea.
def pivote2(a, p, prim, ult):
i = prim
l = ult
k = prim
while i <= l:
if a[i] < p:
a[i], a[k] = a[k], a[i]
k += 1
i += 1
elif a[i] > p:
a[i], a[l] = a[l], a[i]
l -= 1
else:
i += 1
return k, l
La función pivote2 organiza un subvector dividiéndolo en tres partes en torno a un
valor pivote p. Pero, a diferencia de la función pivote, durante la ejecución, dos
índices (k y l) marcan los límites de las zonas con elementos menores y mayores al
pivote. Finalmente, la función devuelve k y l, que delimitan las secciones del
subvector reorganizado: k marca el final de la zona con elementos menores y l el
inicio de la zona con elementos mayores.
Seguimiento
Dado un vector a = [7, 2, 2, 7, 2, 7, 3, 3, 7, 3] y el rango inicial: prim = 0, ult = 9:
Inicialización
p [7, 2, 2, 7, 2, 7, 3, 3, 7, 3]
homog heterog
Vacio Vacio
Se crean los conjuntos homog, y heterog ambos vacíos aun. Se crea p; una
instancia de la clase subvector y se almacena en ella el vector a. Luego se
almacena p en heterog
Iteración 1
Condición (heterog.long_mayor > homog.long_mayor) True
p [7, 2, 2, 7, 2, 7, 3, 3, 7, 3]
mediana 3
pivote2(p) [2, 2, 2, 3, 3, 3, 7, 7, 7, 7]
homog heterog
[3, 3] [2, 2, 2]
[3, 7, 7, 7, 7]
En la primera iteración se extrae el mayor elemento de el conjunto heterog y se
calcula la mediana mediante kesimo. Luego se procesa mediante la función pivote2.
Esto reorganiza el vector, quedando seccionado en tres partes: Los elementos
menores a la media, los elementos iguales a la media y los elementos mayores a la
media. Seguidamente se almacenan estas tres partes en p1, p2 y p3
respectivamente. Finalmente se guardan el subvector cuyos elementos son iguales
entre sí en homog y los subvectores cuyos elementos son distintos entre sí en
heterog
Iteración 2
Condición (heterog.long_mayor > homog.long_mayor) True
p [3, 7, 7, 7, 7]
mediana 7
pivote2(p) [3, 7, 7, 7, 7]
homog heterog
[3, 3] [2, 2, 2]
[7, 7, 7]
En la segunda iteración se repite nuevamente el proceso, ya que la condicion del
bucle nuevamente es verdadera. Nótese como en el conjunto homog van quedando
subvectores candidatos a ser la moda
Iteración 3
Condición (heterog.long_mayor > homog.long_mayor) False
p [3, 7, 7, 7, 7]
mediana 7
pivote2(p) [3, 7, 7, 7, 7]
homog heterog
[3, 3] [2, 2, 2]
[7, 7, 7]
Finalmente la condición del bucle resulta ser falsa, ya que la longitud del mayor
vector de heterog es igual a la longitud del mayor vector de homog. Para obtener la
moda, simplemente se extrae del conjunto homog el vector mas largo, es decir el
subvector cuyo elemento tuvo mas apariciones en el vector original.
Conclusión
El análisis de la complejidad de este algoritmo no es tarea sencilla. Según
Guerequeta y Vallecillo (2000), en su libro Técnicas de diseño de algoritmos, el
algoritmo moda3 presenta una complejidad de O(nlog(n/m)), donde 𝑚 es la
multiplicidad de la moda, lo que lo hace más eficiente que el algoritmo Moda2
debido a sus menores constantes multiplicativas. Sin embargo, es importante
considerar que su diseño y implementación presentan desafíos significativos, lo que
puede complicar su codificación y mantenimiento.
Este equilibrio entre eficiencia y complejidad es característico de los algoritmos que
emplean Divide y Vencerás. Aunque estos algoritmos logran mejorar el tiempo de
ejecución, su implementación tiende a ser más compleja, lo que incrementa la
dificultad de su desarrollo y mantenimiento.
Bibliografía
“Significado del algoritmo divide y vencerás: Explicado con ejemplos”
[Link]
venceras/
Guerequeta, R.; Vallecillo, A. Técnicas de diseño de algoritmos. Servicio de
Publicaciones de la Universidad de Málaga. 2° Ed. 2000.
[Link]