DYV Divide y Vencerás

DYV Divide y Vencerás

El término “Divide y Vencerás” suele considerarse una filosofía general para resolver todo tipo de problemas. Nicolás Maquiavelo en su libro el Arte de la Guerra decía; “Un capitán debe, entre todas sus acciones, procurar con todas sus artes dividir las fuerzas del enemigo, ya sea haciéndole sospechar de los hombres en quien él confía, o dándole motivos para que separe sus fuerzas, y, debido a esto, se debilite” Es decir, la solución de cualquier problema consiste en saber dividirlos en problemas pequeños y vencerlos uno a uno.

En el tema informático se utiliza especialmente para el diseño de algoritmos que consisten en resolver un problema a partir de la solución de subproblemas del mismo tipo, pero de menor tamaño. Cuando los subproblemas son de gran tamaño se aplica la misma técnica hasta alcanzar subproblemas lo suficientemente pequeños para ser solucionados directamente. Al final, las soluciones a cada uno de los subproblemas se combinan para dar una solución al problema original. Ello naturalmente sugiere el uso de la recursión en las implementaciones de algoritmos.

Esta técnica es la base de los algoritmos eficientes para casi cualquier tipo de problema, por ejemplo, algoritmos de ordenamiento (quicksort o mergesort), multiplicar números grandes (Karatsuba), análisis sintácticos (análisis sintáctico top-down) y la transformada discreta de Fourier.

El nombre divide y vencerás también se aplica en la búsqueda binaria para encontrar un elemento en una lista ordenada (o su equivalente en computación numérica, el algoritmo de bisección para búsqueda de raíces). Estos algoritmos pueden ser implementados más eficientemente que los algoritmos generales de “divide y vencerás”; en particular, si es usando una serie de recursiones que lo convierten en simples bucles. Bajo esta amplia definición, sin embargo, cada algoritmo que usa recursión o bucles puede ser tomado como un algoritmo de “divide y vencerás”. 

Información tomada de http://www.lcc.uma.es/~av/Libro/CAP3.pdf