Divide and Conquer, punto 2

Comenté hace un par de publicaciones que algún día os haría unos apuntes rápidos sobre el Divide and Conquer que se utiliza en el sector de la programación. Pues bien, creo que ha llegado el momento.

Por tanto, he de avisaros que hoy nos adentraremos en los patrones de diseño algorítmico - entre los que podemos encontrar está el ya citado Divide and Conquer - . D&C es un paradigma algorítmico de la familia de estrategias descendentes o Top Down. ¿Qué significa esto? Significa que descompondremos el problema inicial (jerárquicamente) en subproblemas menores hasta encontrar el que sea más sencillo de resolver. Esto implica la simplificación del problema y de cada subproblema en cada descomposición, las diferentes partes del problema pueden ser programadas de modo independiente y el programa final queda estructurado modularmente lo que hace más sencilla su lectura y mantenimiento.
Resumiendo todo esto, Divide and Conquer es una técnica que permite resolver un problema general mediante la combinación parcial de las soluciones de sus subproblemas. Un apunte, los subproblemas han de ser independientes entre si para conseguir un resultado eficiente.

Esta estrategia se resuelve mediante la siguiente organización:

1.Divide: es la etapa en la que se divide el problema en uno o más subproblemas.
2.Conquer: es la etapa en la que cada caso (subproblema) es resuelto independientemente.
3.Combination: es la etapa en la que se combinan las soluciones de los subproblemas para poder conseguir la solución del problema general.

Generalmente se implementa utilizando recursividad para cada subproblema. Lo que no significa que todos los problemas que puedan tener un algoritmo recursivo tengan que pertenecer a los que pueden resolverse con Divide and Conquer. Como por ejemplo, la serie de Fibonacci no seria un ejemplo de buen uso de esta estrátegia ya que los subproblemas no son independientes entre ellos; en cambio puede ser muy útil en estrategias de ordenación (MergeSort, QuickSort o ordenación básica).

Aquí os dejo una imagen del UML del patrón método template. En otro momento os subiré un código de muestra, que pensaba que tenía uno en el ordenador pero no le he encontrado. Espero que os sirva alguna vez de ayuda.