Novosibirsk State University Journal of Information Technologies
Scientic Journal

ISSN 2410-0420 (Online), ISSN 1818-7900 (Print)

Switch to
Russian

All Issues >> Contents: Volume 10, Issue No 2 (2012)

Three faces of dynamic programming
N. V. Shilov

A.P. Ershov Institute of Informatics Systems of the SB RAS
Novosibirsk State University
Novosibirsk State Technical University

UDC code: 519.6 + 519.7

Abstract
The paper discusses some methodological issues of Dynamic Programming by study of some programming contest problem A methodological novelty consists in treatment (interpretation) of ascending Dynamic Programming as least fixpoint computation (according to Knaster – Tarski fix-point theorem). This interpretation leads to an uniform approach to classical optimization problems as well as to problems where optimality is not explicit (Cocke – Younger – Kasami parsing algorithm for example). This interpretation leads also to an opportunity to design a unified template for imperative Dynamic Programming in a form of algorithm design template.

Key Words
context-free parsing, solution of a finite game, Knaster – Tarski fixpoint theorem, iterative ascending dynamic programming,, memoization of recursive programs, recursive descending dynamic programming, Dynamic programming

How to cite:
Shilov N. V. Three faces of dynamic programming // Vestnik NSU Series: Information Technologies. - 2012. - Volume 10, Issue No 2. - P. 76-84. - ISSN 1818-7900. (in Russian).

Full Text in Russian

Available in PDF

References
1. Shilov N. V. Zametki o trekh paradigmakh programmirovaniya // Kompyuternyye instru-
menty v obrazovanii. 2010. № 2. S. 24–37.
2. Shilov N. V. Zametki o paradigmakh programmirovaniya // Potentcial. 2010. № 4. S. 33–
38.
3. Bellman R. Dinamicheskoye programmirovaniye. M.: Inostr. lit., 1960.
4. Shcherbina O. A. Metodologicheskiye aspekty dinamicheskogo programmirovaniya // Dinamicheskiye sistemy. 2007. Vyp. 22. S. 21–36.
5. Astapov D. Rekursiya + memoizatciya = dinamicheskoye programmirovaniye // Praktika funktcionalnogo programmirovaniya. 2009, № 3. S. 17–33. URL: http://fprog.ru/2009/issue3/dmitry-astapov-recursion-memoization-dynamic-programming (data obrashcheniya: 18.02.2011).
6. Gris D. Nauka programmirovaniya. M.: Mir, 1984.
7. Shilov N. V. Osnovy sintaksisa, semantiki, translyatcii i verifikatcii programm: Ucheb. posobiye. Novosibirsk, 2011.
8. Knaster B., Tarski A. Un théorème sur les fonctions d'ensembles // Ann. Soc. Polon. Math. 1928. Vol. 6. P. 133–134.
9. Ouen G. Teoriya igr. M.: Mir, 1979.
10. Akho A. V., Ulman Dzh. D. Teoriya sintaksicheskogo analiza, perevoda i kompilyatcii: V 2 t. M.: Mir, 1978. T. 1.
11. Akho A. V., Lam M. S., Seti R., Ulman Dzh. D. Kompilyatory: printcipy, tekhnologii i instrumentary. 2-e izd. M.: Vilyams, 2008.
12. Lange M., Leiß H. To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm // Informatica Didactica. 2009. Vol. 8. URL: http://www.informatica-didactica.de/cmsmadesimple/index.php?page=LangeLeiss2009_en (data obrashcheniya: 18.02.2011).

Publication information
Main title Vestnik NSU Series: Information Technologies, Volume 10, Issue No 2 (2012).
Parallel title: Novosibirsk State University Journal of Information Technologies Volume 10, Issue No 2 (2012).

Key title: Vestnik Novosibirskogo gosudarstvennogo universiteta. Seriâ: Informacionnye tehnologii
Abbreviated key title: Vestn. Novosib. Gos. Univ., Ser.: Inf. Tehnol.
Variant title: Vestnik NGU. Seriâ: Informacionnye tehnologii

Year of Publication: 2012
ISSN: 1818-7900 (Print), ISSN 2410-0420 (Online)
Publisher: Novosibirsk State University Press
DSpace handle


|Home Page| |All Issues| |Information for Authors| |Journal Boards| |Ethical principles| |Editorial Policy| |Contact Information| |Old Site in Russian|

inftech@vestnik.nsu.ru
© 2006-2017, Novosibirsk State University.