El Principio De Divide Y Venceras

El principio de 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.

Recursión

Los algoritmos de “divide y vencerás” están naturalmente implementados, como procesos recursivos. En ese caso, los subproblemas parciales encabezados por aquel que ya ha sido resuelto se almacenan en la pila de llamadas de procedimientos.

Pila explícita

Los algoritmos de divide y vencerás también pueden ser implementados por un programa no recursivo que almacena los subproblemas parciales en alguna estructura de datos explícita, tales como una pila, una cola, o una cola de prioridad. Este enfoque permite más libertad a la hora de elegir los subproblemas a resolver después, una característica que es importante en algunas aplicaciones, por ejemplo en la búsqueda en anchura y en el método de ramificación y poda para optimización de subproblemas. Este enfoque es también la solución estándar en lenguajes de programación que no permiten procedimientos recursivos.

Tamaño de la pila

En implementaciones recursivas de algoritmos de DyV, debe asegurarse que hay suficiente memoria libre para la pila de recursión, sino la ejecución puede fallar por desbordamiento de la pila. Afortunadamente, los algoritmos DyV que son eficientes temporalmente tienen una profundidad recursiva relativamente pequeña. Por ejemplo, el algoritmo quicksort puede ser implementado de forma que nunca requiere más de log_2n llamadas recursivas para ordenar n elementos.

Eligiendo los casos base

En cualquier algoritmo recursivo, hay una libertad considerable para elegir los casos bases, los subproblemas pequeños que son resueltos directamente para acabar con la recursión.

Elegir los casos base más pequeños y simples posibles es más elegante y normalmente nos da lugar a programas más simples, porque hay menos casos a considerar y son más fáciles de resolver. Por ejemplo, un algoritmo FFT podría parar la recursión cuando la entrada es una muestra simple, y el algoritmo quicksort de ordenación podría parar cuando la entrada es una lista vacía. En ambos casos, sólo hay que considerar un caso base, y no requiere procesamiento.

Compartir sus problemas repetidos

Para algunos problemas, la recursión ramificada podría acabar evaluando el mismo subproblema muchas veces. En tales casos valdría la pena identificar y guardar las soluciones de estos subproblemas solapados, una técnica comúnmente conocida como memoización. Llevado al límite, nos lleva a algoritmos de “divide y vencerás” de bottom-up tales como la programación dinámica y análisis gráfico.EDF

Desventajas

La principal desventaja de este método es su lentitud en la repetición del proceso recursivo: los gastos indirectos de las llamadas recursivas a la resolución de los subproblemas, junto con el hecho de tener que almacenar la pila de llamadas (el estado en cada punto en la repetición), pueden empeorar cualquier mejora hasta entonces lograda. Esta tarea, sin embargo, depende del estilo de la implementación: con casos base lo suficientemente grandes, se reducen los gastos indirectos de la repetición de las llamadas.

Otra desventaja o inconveniente importante, es la dificultad o incluso inconveniencia de aplicar el método a situaciones en las que la solución al problema general no se deriva de la suma directa y simple de los subproblemas (partes). Esto se presenta por ejemplo cuando son relevantes las interacciones o efectos mutuos entre los subproblemas, lo que genera nuevos subproblemas, al considerar cada una de estas interacciones, incrementando exponencialmente el número de subproblemas a considerar, al incrementarse la complejidad de la situación general y de sus componentes.

De modo similar, el algoritmo puede no ser aplicable cuando las interacciones no son predecibles de preciso.

Ejemplo de Algoritmo Recursivos

Ejercicio 1.

Programar un algoritmo recursivo que calcule el factorial de un número.

Solución:

view plainprint?

int factorial(int n){

if(n==0){

return 1; //Caso Base

}

else {

return n * factorial(n-1); //Fórmula Recursiva

}

}

Ejercicio 2:

Programar un algoritmo recursivo que calcule un número de la serie fibonacci.

Solución:

view plainprint?

int fibonaci(int n){

if(n==1 || n==2) {

return 1;

}

else{

return fibonaci(n-1)+fibonaci(n-2);

}

}

Ejercicio 3:

Programar un algoritmo recursivo que permita hacer la división por restas sucesivas. ver mas...

Solución:

view plainprint?

int division (int a, int b) {

if(b > a) {

return 0;

}

else {

return division(a-b, b) + 1;

}

}

Ejercicio 4:

Programar un algoritmo recursivo que permita invertir un número. Ejemplo: Entrada 123 Salida 321

Solución:

view plainprint?

int invertir (int n) {

if (n < 10) { //caso base

return n;

}

else {

return (n % 10) + invertir (n / 10) * 10;

}

}

Ejercicio 5:

Programar un algoritmo recursivo que permita sumar los dígitos de un número.Ejemplo: Entrada:123 Resultado:6

Solución:

view plainprint?

int sumar_dig (int n) {

if (n == 0) { //caso base

return n;

}

else {

return sumar_dig (n / 10) + (n % 10);

}

}

...