teoria de kuhn


Instituto Tecnológico Superior De Tierra Blanca

Investigación de Operaciones ll

Liliana Fuentes Rosas

Investigación sobre:
¿Quién creó la Programación Dinámica?

Presenta:
RodríguezGaray Deysel

Ingeniería Industrial

504-“A”.

Vo. Bo.


Tierra Blanca, Ver. A 20 de Agosto del 2013.

¿Quién creó la Programación Dinámica?
El matemático Richard Ernest Bellman inventóla programación dinámica en 1953 que se utiliza para optimizar problemas complejos que pueden ser discretizados y secuencializados. La programación dinámica es un método para reducir el tiempo deejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas. La Programación Dinámica (PD) surge como una alternativa de descomposición en la que resolvemossubproblemas más pequeños y luego los ligamos. Así, la programación dinámica consiste en solucionar el presente suponiendo que en cada etapa futura siempre se tomaran las decisiones correctas.
Unasubestructura óptima significa que se pueden usar soluciones óptimas de subproblemas para encontrar la solución óptima del problema en su conjunto. Por ejemplo, el camino más corto entre dos vértices sepuede encontrar calculando primero el camino más corto al objetivo desde todos los vértices adyacentes al de partida, y después usando estas soluciones para elegir el mejor camino de todos ellos. Engeneral, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos:
1. Dividir el problema en subproblemas más pequeños.
2. Resolver estos problemas de manera óptima usandoeste proceso de tres pasos recursivamente. 
3. Usar estas soluciones óptimas para construir una solución óptima al problema original.
Los subproblemas se resuelven a su vez dividiéndolos ensubproblemas más pequeños hasta que se alcance el caso fácil, donde la solución al problema es trivial. Decir que un problema tiene subproblemas superpuestos es decir que se usa un mismo subproblema para...