Programacion dinamica

Programación Dinámica
como Solución al Problema
de la Eficiencia en la
Recursividad
Autor:
Jorge Jiménez Muñoz 1ºA Gestión2
INDICE:
1. Introducción al trabajo.
2. Recursividad.
i. Introducción a la recursividad.
ii. Conceptos de Recursividad.
iii. Propiedades de las definiciones o algoritmos
recursivos.
iv. Programación recursiva,
v. Diseño de algoritmos recursivos.
vi.Recursividad directa e indirecta.
vii. Recursividad Vs Iteración.
3. Programación Dinámica.
i. Introducción a la programación dinámica.
ii. Concepto de programación dinámica.
iii. Procesos polietapicos de decisión.
4. Conclusiones
5. Bibliografía3
1. Introducción al trabajo.
El siguiente trabajo trata del análisis, de la programación dinámica. Siendo esta
una solución de mejora a la pocaeficiencia de la programación recursiva. La manera de
afrontar este trabajo, y explicar en un modo sencillo, que entienda todo el mundo, tras
consultar muchas fuentes, es el siguiente, primero veremos a grandes rasgos, en que
consiste la programación recursiva, sus propiedades, definiciones, ventajas e
inconvenientes, y todo ello acompañado de ejemplos, y uno en común junto a la
programacióndinámica, de manera que podamos observar el mismo problema desde las
dos perspectivas, que es, el calculo de los números de Fibonacci. El por que de hablar
extendidamente de la programación recursiva es, porque esta, junto con algunas
técnicas de programación como “el divide y vencerás, algoritmo voraz, o backtracking”,
la programación dinámica no es mas que una mejora bastantesignificativa basada en la
programación recursiva, aprovechando los cálculos que generan las llamadas, e ir
almacenándolos para su posterior uso, no teniendo que volver a calcularlo, aunque lo
veremos con mas extensión mas adelante.
2. Recursividad
2.i. Introducción a la Recursividad.
El área de la programación es muy amplia y con muchos detalles. Los
programadores necesitan ser capaces de resolvertodos los problemas que se les presente
a través del computador aun cuando en el lenguaje que utilizan no haya una manera
directa de resolver los problemas. En los lenguajes de programación, se puede aplicar
una técnica que se le dio el nombre de recursividad por su funcionalidad. Esta técnica es
utilizada en la programación estructurada para resolver problemas que tengan que ver
conel factorial de un número, o juegos de lógica. Las asignaciones de memoria pueden
ser dinámicas o estáticas y hay diferencias entre estas dos y se pueden aplicar las dos en
un programa cualquiera.
2.ii Conceptos de Recursividad.
La recursividad es una técnica de programación importante. Se utiliza para
realizar una llamada a una función desde la misma función. Como ejemplo útil se puedepresentar el cálculo de números factoriales. Él factorial de 0 es, por definición, 1. Los
factoriales de números mayores se calculan mediante la multiplicación de 1 * 2 * ...,
incrementando el número de 1 en 1 hasta llegar al número para el que se está calculando
el factorial.
El siguiente párrafo muestra una función, expresada con palabras, que calcula un
factorial.4
"Si el número es menorque cero, se rechaza. Si no es un entero, se redondea al
siguiente entero. Si el número es cero, su factorial es uno. Si el número es mayor que
cero, se multiplica por él factorial del número me nor inmediato."
Para calcular el factorial de cualquier número mayor que cero hay que calcular
como mínimo el factorial de otro número. La función que se utiliza es la función en la
que seencuentra en estos momentos, esta función debe llamarse a sí misma para el
número menor inmediato, para poder ejecutarse en el número actual. Esto es un ejemplo
de recursividad.
La recursividad y la iteración (ejecución en bucle) están muy relacionadas,
cualquier acción que pueda realizarse con la recursividad puede realizarse con iteración
y viceversa. Normalmente, un cálculo determinado se...