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.

...