Equipo Tarea 2

Diseño de algoritmo divide y vencerás

Descripción

Divide y vencerás es una técnica de diseño de algoritmos que ayuda a reducir la complejidad de el problema planteado, con base en resolver problemas más pequeños derivados del problema principal, todos de misma índole pero con un grado de complejidad mucho menor, que casi lleva a la solución obvia.

Problemas que conviene resolver

Conviene usarlo en problemas de lata complejidad en donde el tiempo de solución es excesivo siempre y cuando se conozca la solución más simple y rápida para los subproblemas derivados, como algoritmos de búsqueda y otros cuya solución sea exponencial.

Cuando conviene usarlo

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 divide 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.

Cuando no conviene usarlo

Cuando la solución del problema esta explicita o es de baja complejidad.

Diseño e implementación

La resolución de un problema mediante esta técnica consta fundamentalmente de los siguientes pasos:

Primero que nada el problema presentado ha de ser divisible en problemas de menor complejidad y éstos, a su vez y de igual manera, han de ser divisibles en problemas de menor complejidad. 

Después se tiene que resolver por si mismo todoos los subproblemas , que también son elementales o bien se va definiendo en si mismo. El tamaño de los subproblemas sea obligatoria mente menor que el tamaño original del problema nos da la seguridad de la convergencia hacia los casos elementales, también denominados casos base 

cuando concluyamos este procedimiento debemos combinar las soluciones obtenidas en el paso anterior para construir la solución del problema original.

Ejemplo de la implementación del algoritmo

Caso de un problema factorial

Es un problema que se puede resolver utilizando la técnica de divide y vencerás.

El factorial de un numero N  es presentado como el producto de todos los numeros naturales que existen desde uno hasta N.

ejemplo:

 4!= 4x3x2x1=24

Implementando el algoritmo tenemos lo siguiente:

• Inicio 
• Recibe N
• Llamar función factorial(N)
• Fin
• Inicio Función factorial(N);
• if N<2 Resultado=1;
• else Resultado=N*factorial(N-1)
• Retorna Resultado
• Fin Función factorial