Técnicas de Programación: Divide y Vencerás y Programación Dinámica

"DIVIDE Y VENCERÁS" ¿En qué consiste esta técnica en términos informáticos?

Resolver el problema a través de subproblemas, así hasta que los problemas sean lo bastante pequeños para encontrar mejores soluciones.

Mencione y explique los 3 pasos que debe realizar para aplicar esta técnica.

1. Se plantea el problema de forma que se pueda dividir en k subproblemas del mismo tipo pero de menor tamaño.
2. Cada subproblema debe resolverse independientemente.
3. Combinar las soluciones.

Explique cómo se aplica esta técnica en el algoritmo de búsqueda binaria.

Existe un elemento dado x en un vector de enteros “ordenados”. El valor x se compara con el término central del vector. En caso de que coincida, hemos solucionado nuestro problema. De lo contrario, se dan dos condiciones: que x sea mayor que el término central o que sea menor. En cualquiera de los dos casos, podemos descartar uno de ellos, repitiendo el paso con el subvector elegido de forma recursiva, hasta encontrar el valor buscado.

De los ejemplos dados en el texto: explique cómo se aplica esta técnica en al menos 2 algoritmos distintos a búsqueda binaria.

Búsqueda ternaria

Consideremos un valor x que queremos comparar con el elemento de la posición n/3 del vector. Si este elemento es menor al valor x, entonces comparamos con el elemento en la posición 2n/3, y si no coincide con x, busca recursivamente en el correspondiente subvector del tamaño 1/3 del original.

La subsecuencia de suma máxima

Dividiremos este problema en 3 subproblemas sobre cuyas soluciones constituiremos la solución final. En este caso, la subsecuencia de suma máxima se puede encontrar en 3 partes: al principio del vector, en el medio, o en el final. Por esto, dividiremos el problema en tres subproblemas. Los dos primeros casos pueden resolverse recursivamente. Respecto al tercero, podemos calcular la subsecuencia de suma máxima de la primera mitad que contenga al último elemento de esa primera mitad, y la subsecuencia de suma máxima de la segunda mitad que contenga al primer elemento de esa segunda mitad.

Programación Dinámica

Es una técnica que parte del principio de no calcular dos veces la misma información. Por lo tanto, se utilizan estructuras de almacenamiento como vectores, tablas, arreglos, archivos, con el fin de almacenar los resultados parciales que contribuyan a la solución final.

Este algoritmo evita calcular dos veces la misma información, manteniendo una tabla de resultados conocidos, la cual se va llenando a medida que se resuelven los subcasos. Es una técnica ascendente que normalmente empieza por los subcasos más pequeños y más sencillos. Combinando sus soluciones, obtenemos las respuestas para los subcasos cada vez mayores, hasta que llegamos a la solución del caso original.

La programación dinámica se aplica no solo por razones de eficiencia, sino porque permite resolver de manera eficiente problemas que no se pueden resolver por otras metodologías.

El mayor número de aplicaciones se encuentra en problemas que requieren optimización, ya que se pueden hallar múltiples soluciones y así evaluarlas para hallar la óptima.

Al contrario del método divide y vencerás, que es de tipo descendente, ya que divide los problemas de grandes a pequeños, la programación dinámica es de tipo ascendente, ya que soluciona los problemas pequeños y los va guardando para solucionar los más grandes.

Forma General

La forma general de las soluciones desarrolladas mediante programación dinámica requiere de los siguientes pasos:

1. Planteamiento de la solución, mediante una serie de decisiones que garanticen que la solución será óptima.
2. Encontrar una solución recursiva de la definición.
3. Calcular la solución teniendo en cuenta una tabla en la que se almacenen soluciones a problemas parciales para su reutilización y así evitar el nuevo cálculo.