5 ms·
Dynamic is definitely not meaningless. I am familiar with dynamic programming from the optimal control theory point of view, and it's squarely focused on dynami
by Certhas 1y ago
Dynamic is definitely not meaningless. I am familiar with dynamic programming from the optimal control theory point of view, and it's squarely focused on dynamical systems. The central equation of dynamic programming is the Hamilton-Jacobi-Bellmann equation, a generalization of the Hamilton-Jacobi equations of classical mechanics. And the terminology programming in this context also exists in linear programming and stochastic programming. It's definitely confusing today, but these terms simply predate the modern use of programming, as well as modern computers. I am honestly a bit puzzled by everyone in this comment section talking about recursion + memoization (as a way to efficiently implement backward induction I presume?). It seems like computer science teaches a particular application and implementation of dynamic programming ideas and people mistake that for the whole thing?
- tgma 1y agoWell, to be fair, you are questioning terminology bastardization in "computer science," a field that is named after "computers" and "science" but has little to do with either. One should temper their expectations :) Informatics, a commonly used term in Europe, would have been a much better name.
- eru 1y agoWell, just pretend that the whole discussion happened in German, where despite using your preferred term of Informatik, they still talk about Dynamische Programmierung.
- zelphirkalt 1y agoSome of these terms sound sooo awkward in German. I vote for calling it memoization.
- deleted 1y ago[deleted]
- eru 1y agoWell, memoisation ain't exactly the same as dynamic programming. You can use memoisation to do dynamic programming, but you can also use it in other contexts (and you can implement dynamic programming in different ways, too).
- tuukkah 1y agoHowever, information science (and in Finnish, informatiikka) is a synonym of library science. Computer science isn't too bad a name for a science about computing on (abstract) machines.
- mollerhoj 1y agoI prefer the Danish term: Datalogi
- zahlman 1y agoNaming things is considered one of the hard problems in the field, after all.
- mort96 1y agoI don't understand most of what you wrote. But can you, in simple terms, explain to me why recursion without caching is "static"?
- Certhas 1y agoWhy do you think that what I wrote implies they are static? I didn't say that recursion and caching are the opposite of dynamic, I said they are essentially orthogonal concepts to it. Generally speaking, dynamical systems are systems that have some sort of dependence on time [1]. In dynamic programming we have an optimization/decision problem in which time plays an essential role. The optimality is measured with respect to the whole time evolution. Bellmann showed that you can break this intertemporal optimization down into individual time steps. So the key observation of dynamic programming is how to turn an "all times at once" problem into a "one time at a time" problem. The reason that Hamilton's name shows up next to Bellmann here is that physicists and mathematicians (Lagrange, Hamilton, Jacobi) figured out that you can do the inverse: You can write the dynamical equations of physics as an intertemporal (all times at once) optimization problem. This has been one of the most influential ideas in theoretical physics _ever_, especially after Noether's theorems leveraged this structure to connect symmetries and conserved quantities. In many fields of theoretical physics you no longer write down differential equations to model a dynamical system, you write down a "Lagrangian", and mean that your system follows those trajectories that minimize the integral of the Lagrangian over all time. So the central ideas of dynamic programming are extremely tightly related to physics and dynamical systems. [1] https://en.wikipedia.org/wiki/Dynamical_system https://en.wikipedia.org/wiki/Dynamical_system Edit: After reading a bit more I think I understand why people focus on this. The algorithmic examples with shortest paths sort of show the point. To me the core point of Dynamic Programming is before you start thinking about recursion or memoization. It's when you establish that you have optimal substructures: https://en.wikipedia.org/wiki/Optimal_substructure https://en.wikipedia.org/wiki/Optimal_substructure what is dynamical is that the subproblems depend on each other, in the way that what happens at time t+1 depends on what happens at time t, or, more to the point, what is the optimal decision at time t depends on what the optimal decision at time t+1 is. If your subproblems are ordered by time, then of course you don't need recursion to solve them, you just iterate over time steps, hence my confusion.
- deleted 1y ago[deleted]