Análisis de algoritmos, programación dinámica

[pic 1]

TAREA 5

TECNICAS DE DIVIDE Y VENDERAS Y PROGRAMACIÓN DINÁMICA

[pic 2][pic 3]

TECNICA DE DIVIDE Y VENCERÁS

El término Divide y Vencerás en su acepción más amplia es algo más que una técnica de diseño de algoritmos. De hecho, suele ser considerada una filosofía general para resolver problemas y de aquí que su nombre no sólo forme parte del vocabulario informático, sino que también se utiliza en muchos otros ámbitos.

Es una técnica de diseño de algoritmos que consiste en resolver un problema a partir de la solución de subproblemas del mismo tipo, pero de menor tamaño. Si los subproblemas son todavía relativamente grandes se aplicará de nuevo esta técnica hasta alcanzar subproblemas lo suficientemente pequeños para ser solucionados directamente. Ello naturalmente sugiere el uso de la recursión en las implementaciones de estos algoritmos.

Sirve para lograr solucionar programas grandes a partir de la división de él, en programas más pequeños, los cuales a su vez serán divididos (si es posible). Esto es de gran ayuda al optimizar tiempos de programación.

Su forma de implementación es sencilla, se hace un análisis cual es el problema en general.

Dicho problema será dividido en grandes bloques de tareas que deben realizarse para poder solucionar un problema, posteriormente estas tareas serán divididos en algoritmos atómicos, es decir, que ya no son divisibles o que el dividirlos haría que la implementación fuera más complicada.

Un ejemplo de ello:

Realizar la multiplicación de 2 números complejos

Descripción del problema:

El programa deberá capturar 2 números complejos, y luego procederá a multiplicarlos, mostrando el resultado en su forma rectangular y trigonométrica.

División en bloques:

• Lectura de los datos
• Realización de multiplicación
• Conversión a forma trigonométrica

División de los bloques en tareas más sencillas

• Lectura de bloques

•  No es recomendable dividir esta tarea

• Realización de multiplicación

• Obtención de término real
• Obtención de término imaginario

• Conversión a forma trigonométrica

• No es recomendable dividir esta tarea

PROGRAMACIÓN DINÁMICA

Es una técnica de programación la cual aborda la forma más óptima de solucionar un problema. Principalmente es el resultado de la falta de eficiencia de otras técnicas de programación como son: divide y vencerás.

En algunos casos, la técnica anteriormente mencionada no es factible ya que las sub tareas se solapan y es complicado hacer la división.

También soluciona los problemas de las ejecuciones recursivas, dado que la programación dinámica busca la forma más eficiente de realizar un algoritmo y un algoritmo recursivo es de forma exponencial, dando como resultado una solución inviable a problemas de gran magnitud.

Esta técnica de programación se basa en la frase: “En una secuencia de decisiones óptima toda sub secuencia ha de ser también óptima”.

Sirve para realizar algoritmos de forma óptima que cumplan con los siguientes requisitos:

• La solución al problema ha de ser alcanzada a través de una secuencia de decisiones, una en cada etapa.
• Dicha secuencia de decisiones ha de cumplir el principio de óptimo.

Para modelar un algoritmo bajo esta forma de implementación se siguen los siguientes puntos:

• Planteamiento de la solución como una sucesión de decisiones y verificación de que ésta cumple el principio de óptimo.
• Definición recursiva de la solución.
• Cálculo del valor de la solución óptima mediante una tabla en donde se almacenan soluciones a problemas parciales para reutilizar los cálculos.
• Construcción de la solución óptima haciendo uso de la información contenida en la tabla anterior.

Un ejemplo de ello:

Serie de Fibonacci

Descripción del problema:

Se obtendrá el término N de la serie, teniendo solo 2 variables en un proceso cuadrático (ciclo for) evitando la recursividad y la exponenciación del problema.

BIBLIOGRAFIA

[1] http://www.lcc.uma.es/~av/Libro/CAP5.pdf, fecha de consulta: 30/10/2015

[2] http://www.lcc.uma.es/~av/Libro/CAP3.pdf, fecha de consulta: 30/10/2015

...