Metodo: Divide y venceras

En las ciencias de la computación, el término divide y vencerás (DYV) hace referencia a uno de los más importantes paradigmas de diseño algorítmico. El método está basado en la resolución recursiva de un problema dividiéndolo en dos o más subproblemas de igual tipo o similar. El proceso continúa hasta que éstos llegan a ser lo suficientemente sencillos como para que se resuelvan directamente. Al final, las soluciones a cada uno de los subproblemas se combinan para dar una solución al problema original.

Esta técnica es la base de los algoritmos eficientes para casi cualquier tipo de problema como, por ejemplo, algoritmos de ordenamiento, multiplicar números grandes, análisis sintácticos y la transformada discreta de Fourier.

¿En que problemas se utiliza?

1. Multiplicacion rapida de enteros largos
2. multiplicacion rapida de matrices
3. Ordenacion por mezcla y ordenacion rapida
4. Problema de seleccion.

 Un ejemplo:

Multiplicación de enteros grandes

Enunciado del problema 
las operaciones aritméticas entre números enteros suelen considerarse operaciones elementales siempre y cuando los números que intervienen no superen los límites de representación. Cuando esto ocurre, hay que acudir a otro tipo de representación, por ejemplo los arrays, y utilizar los algoritmos clásicos de las operaciones aritméticas. El problema planteado consiste en saber si existe alguna forma de reducir el coste en el caso de la multiplicación, ya que el algoritmo clásico de multiplicación es de orden cuadrático. Como alternativa, se podría utilizar el esquema de multiplicación por duplicación, pero no ofrece mejoras en cuanto a tiempo de ejecución.

Solución
considérense dos números enteros, u y v, de n dígitos cada uno.

1. Algoritmo básico: la idea a seguir es descomponer los dos números en la suma de otros dos. Más concretamente, sea S la parte entera de n/2, la descomposición consiste en dividir los números entre 10S:

u → w representa el cociente y x el resto → u = 10S·w + x

v → y representa el cociente y z el resto → v = 10S·y + z

Luego:

u·v = (10S·w + x)·(10S·y + z) = 102S·w·y + 10S·(w·z + x·y) + x·z

A continuación, se calculan las suboperaciones w·y, w·z, x·y y x·z. Si los operandos (w, x, y, z) son:

- “pequeños”, entonces se multiplican de la forma clásica.

- “suficientemente grandes”, se aplica de nuevo el algoritmo y se calculan recursivamente las multiplicaciones de los respectivos sumandos.

2. Algoritmo mejorado: al realizar cuatro multiplicaciones de tamaño mitad en cada llamada, el coste resultante es T(n) = 4·T(n/2) + g(n), donde g(n) es el tiempo invertido en sumas, desplazamientos y operaciones adicionales sencillas, por lo que el algoritmo sigue siendo de orden cuadrático.

Dado que se necesitan realizar cuatro multiplicaciones de tamaño mitad, no se mejora el tiempo de ejecución respecto a los algoritmos clásicos. Para intentar reducirlo, es preciso evitar alguna de esas multiplicaciones. La clave de la mejora consiste en advertir que no es necesario calcular w·z y x·y, si no la suma de ambos. Así, se considera r = (w + x)·(y + z) = w·y + (w·z + x·y) + x·z , con los que las multiplicaciones a realizar son:

p = w·y

q = x·z

r = (w + x)·(y + z)

, hallando la suma de la siguiente forma:

(w·z + x·y) = r – p - q

Así, volviendo al producto anterior:

u·v = (10S·w + x)·(10S·y + z) = 102S·w·y + 10S·(w·z + x·y) + x·z = 102S·p + 10S·(r – p - q) + q

, teniendo que calcular las multiplicaciones p, q y r. Si sus operandos (w, x, y, z) son:

- “pequeños”, entonces se multiplican de la forma clásica.

- “suficientemente grandes” se aplica de nuevo la descomposición anterior, y calculamos recursivamente las multiplicaciones de los respectivos sumandos.

¿Cuando conviene utilizarlo y cuando no?

Principalmente este método nos conviene utilizarlo en problemas muy complejos, ya que como se menciona en la descripción se divide un problema en varios sub-problemas para hacerlo más sencillo y estos a su vez se pueden dividir si es necesario.

No nos conviene utilizarlo cuando el resultado final del problema original no es la suma de los resultados de los sub-problemas.

El método esta diseñado para problemas complejos pero no es conveniente sub-dividir tanto el original ya que el método es muy lento y entre más dividamos el problema más tiempo tomara llegar a la solución.

Ejemplo

Primeramente lo que tenemos que hacer en ese caso de divide y venceras es lo siguiente

1. Sabes de lo que se tratara el problema que tenemos que resolver y después sacar ciertos subproblemas (mas pequeños ) pero que sea el mismo resultado.
2. Resolver cada problema de manera independiente
3. Por ultimo hacer las combinaciones posibles , hasta que el resultado sea el buscado