Algoritmo divide y vencerás

En la cultura popular, divide y vencerás hace referencia a un refrán que implica resolver un problema difícil, dividiéndolo en partes más simples tantas veces como sea necesario, hasta que la resolución de las partes se torna obvia. La solución del problema principal se construye con las soluciones encontradas.

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 ( quicksort, mergesort, entre muchos otros), multiplicar números grandes ( Karatsuba), análisis sintácticos ( análisis sintáctico top-down) y la transformada discreta de Fourier.

Por otra parte, analizar y diseñar algoritmos de DyV son tareas que lleva tiempo dominar. Al igual que en la inducción, a veces es necesario sustituir el problema original por uno más complejo para conseguir realizar la recursión, y no hay un método sistemático de generalización.

El nombre divide y vencerás también se aplica a veces a algoritmos que reducen cada problema a un único subproblema, como 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”. El nombre decrementa y vencerás ha sido propuesta para la subclase simple de problemas.

La corrección de un algoritmo de “divide y vencerás”, está habitualmente probada una inducción matemática, y su coste computacional se determina resolviendo relaciones de recurrencia.

Precedentes históricos

La búsqueda binaria, un algoritmo de divide y vencerás en el que el problema original es partido sucesivamente en subproblemas simples de más o menos la mitad del tamaño, tiene una larga historia. La idea de usar una lista ordenada de objetos para facilitar su búsqueda data de la antigua Babilonia en el 200 a. C., mientras que una descripción del algoritmo en ordenadores apareció en 1946 en un artículo de John Mauchly. Otro algoritmo de “divide y vencerás” con un único subproblema es el algoritmo de Euclides para computar el máximo común divisor de dos números (mediante reducción de números a problemas equivalentes cada vez más pequeños), que data de muchos siglos antes de Cristo.

Un ejemplo antiguo de algoritmo de “divide y vencerás” con múltiples subproblemas es la descripción realizada por Gauss en 1805 de lo que se le llama ahora algoritmo de la rápida transformación de Fourier Cooley- Tukey (FFT), aunque él no analizó su conjunto de operaciones cuantitativamente y los FFT no se difundieron hasta que se redescubrieron casi un siglo después.

Otro problema antiguo de 2 subdivisiones de “divide y vencerás” que fue específicamente desarrollado para ordenadores y analizado adecuadamente es el algoritmo de merge-sort, inventado por John von Neumann en 1945.

Otro ejemplo notable es el algoritmo inventado por A. Karatsuba en 1960 que puede multiplicar dos números de n dígitos en . El algoritmo refutó la conjetura de Andréi Kolmogórov en 1956 que esa tarea requería Ω(n2) operaciones. Otro ejemplo de algoritmo de divide y vencerás que originalmente no se usaba en ordenador, Knuth dio el método que habitualmente una oficina de correos usa para dirigir las cartas: las cartas se ordenan en diferentes bolsas en función de su área geográfica, cada una de estas bolsas a su vez se ordena en diferentes lotes para subregiones más pequeñas, y así sucesivamente hasta que son repartidas. Esto está relacionado con el ordenamiento Radix, descrito para las máquinas de ordenación de tarjetas perforadas a los comienzos .

Other Languages