DSpace Repository

Три лика динамического программирования

Show simple item record

dc.contributor.author Шилов, Н. В. ru_RU
dc.contributor.author Shilov, N. V. en_EN
dc.creator Институт систем информатики им. А. П. Ершова СО РАН ru_RU
dc.creator Новосибирский государственный университет ru_RU
dc.creator Новосибирский государственный технический университет ru_RU
dc.creator A.P. Ershov Institute of Informatics Systems of the SB RAS en_EN
dc.creator Novosibirsk State University en_EN
dc.creator Novosibirsk State Technical University en_EN
dc.date.accessioned 2015-02-08T06:44:29Z
dc.date.available 2015-02-08T06:44:29Z
dc.date.issued 2012
dc.identifier.issn 1818-7900
dc.identifier.uri https://lib.nsu.ru/xmlui/handle/nsu/5880
dc.description.abstract Работа посвящена некоторым методическим аспектам динамического программирования и решению одной олимпиадной задачи с использованием динамического программирования. Новым является интерпретация метода восходящего динамического программирования в терминах вычисления наименьшей неподвижной точки монотонных функционалов. Такая трактовка позволяет единообразно решать как классические оптимизационные задачи, так и задачи, в которых оптимизационная составляющая не просматривается явно (например, задача синтаксического анализа контекстно-свободных языков алгоритмом Коукера – Янгера – Касами). Она же позволяет унифицировать общую схему динамического программирования в виде шаблона проектирования алгоритмов. ru_RU
dc.description.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. en_EN
dc.language.iso ru
dc.publisher Новосибирский государственный университет ru_RU
dc.subject context-free parsing en_EN
dc.subject solution of a finite game en_EN
dc.subject Knaster – Tarski fixpoint theorem en_EN
dc.subject iterative ascending dynamic programming, en_EN
dc.subject memoization of recursive programs en_EN
dc.subject recursive descending dynamic programming en_EN
dc.subject Dynamic programming en_EN
dc.subject синтаксический анализ контекстно-свободных языков ru_RU
dc.subject решение конечных игр ru_RU
dc.subject теорема о неподвижной точке Тарского – Кнастера ru_RU
dc.subject итеративное восходящее динамическое программирование ru_RU
dc.subject мемоизация рекурсивных программ ru_RU
dc.subject рекурсивное нисходящее динамическое программирование ru_RU
dc.subject динамическое программирование ru_RU
dc.title Три лика динамического программирования ru_RU
dc.title.alternative Three faces of dynamic programming en_EN
dc.type Article
dc.description.reference 1. Шилов Н. В. Заметки о трех парадигмах программирования // Компьютерные инстру- менты в образовании. 2010. № 2. С. 24–37. 2. Шилов Н. В. Заметки о парадигмах программирования // Потенциал. 2010. № 4. С. 33– 38. 3. Беллман Р. Динамическое программирование. М.: Иностр. лит., 1960. 4. Щербина О. А. Методологические аспекты динамического программирования // Динамические системы. 2007. Вып. 22. С. 21–36. 5. Астапов Д. Рекурсия + мемоизация = динамическое программирование // Практика функционального программирования. 2009, № 3. С. 17–33. URL: http://fprog.ru/2009/issue3/dmitry-astapov-recursion-memoization-dynamic-programming (дата обращения: 18.02.2011). 6. Грис Д. Наука программирования. М.: Мир, 1984. 7. Шилов Н. В. Основы синтаксиса, семантики, трансляции и верификации программ: Учеб. пособие. Новосибирск, 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. Оуэн Г. Теория игр. М.: Мир, 1979. 10. Ахо А. В., Ульман Дж. Д. Теория синтаксического анализа, перевода и компиляции: В 2 т. М.: Мир, 1978. Т. 1. 11. Ахо А. В., Лам М. С., Сети Р., Ульман Дж. Д. Компиляторы: принципы, технологии и инструментарий. 2-е изд. М.: Вильямс, 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 (дата обращения: 18.02.2011). ru_RU
dc.subject.udc 519.6 + 519.7
dc.relation.ispartofvolume 10
dc.relation.ispartofnumber 2
dc.relation.ispartofpages 76-84


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account