Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I heard the term "dynamic programming" and naively assumed it had to do with programming in the sense of computer programming (as that's the only way I've heard the word used before. Used to work with software engineers a lot). I was told (after being laughed at a bit) that when a math/econ person says "dynamic programming" it has nothing to do with computer programming, and it is just a technique for solving complicated problems in a dynamic setting. However, I have read the wikipedia page and I don't understand the difference. Isn't the computational approach the same at the mathematical one, just wisely using the computer as an assist to execute the algorithm?

If it's not too much to ask, what exactly do the terms "programming" and "control" mean in this area?

share|improve this question
4  
Bellman used to work for RAND, which worked closely with and was partly funded by the military. In the military sense, "programming" is synonymous with "planning" or "scheduling", which exactly was one of the intended applications of Bellman's theory. A similar situation exists with linear programming, as Dantzig worked for RAND as well. –  J. M. Oct 16 '11 at 16:43
3  
@J.M. Have you seen this: link? You can learn about the birth of the name in the words of the master himself. See the section titled "Choice of the name Dynamic Programming". (I love the ending: "It was something not even a Congressman could object to.") –  Srivatsan Oct 18 '11 at 13:51
2  
Quite nice! Thanks @Sri! (I know the bit about making the mathematical research more palatable for the military brass, but it's nice to get it straight from the creator.) –  J. M. Oct 18 '11 at 14:11
add comment

2 Answers

up vote 9 down vote accepted

I think it's confusing because it's both at the same time. The origin of the name is a pre-computer sense of "programming" where the world simply meant the concrete planning of actions (say, deciding which vehicles to go where when you have a given amount of goods to transport from some points to other points). "Programming" is still used in that sense in combinatorial optimization.

Of course, nowadays such planning problems are solved by having a computer execute a program, though this program exists on a different meta-level than the plan for which vehicles to send where.

Also, some techniques originally developed for "programming" in the old sense have turned out to be useful for constructing computer programs, independently of the naming coincidence. So "dynamic programming" is now also an algorithmic technique that consists of solving and remembering smaller instances of a problem first and then building up to the problem you're actually interested in. This can be useful even in cases where the eventual problem is not a "programming" (in the planning/optimization sense) problem. So you use the technique while you program computers, but that's not why its name contains "programming".

share|improve this answer
3  
The use of the word "programming" for computer programming developed from the same idea of "planning". Oxford English Dictionary's first citation for "programming" in this context is a paper by Mauchly (one of the inventors of ENIAC) in 1942. –  Robert Israel Oct 16 '11 at 20:50
add comment

I don't have a source for this, but I would say that "algorithm" is a more precise synonym for "program" in the non-math sense than is "planning."

You also asked about "control." This implies a process that accepts inputs. Search "control theory."

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.