RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Модел. и анализ информ. систем:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Модел. и анализ информ. систем, 2018, том 25, номер 5, страницы 549–560 (Mi mais648)  

Синтез и преобразования программ

Etude on recursion elimination

[Этюд об устранении рекурсии]

N. V. Shilov

Autonomous noncommercial organization of higher education "Innopolis University", 1 Universitetskaya str., Innopolis, Tatarstan Republic, 420500, Russia

Аннотация: Трансформационный подход к верификации программ был очень популярной темой исследований в первые десятилетия теории программирования. Многие выдающиеся пионеры теории программирования внесли свой вклад в разработку данного направления исследований: Джон Маккарти, Амир Пнуели, Дональд Кнут ... Много интересных примеров трансформационного подхода было тщательно изучено, что привело к методам устранения рекурсии, известным как хвостовая рекурсия и как ко-рекурсия. В данной работе мы подробно исследуем (мы надеемся, новый) пример устранения рекурсии, основанный на трансформациях программы и анализе задачи, решаемой этой программой. Наш пример является частным случаем нисходящего динамического программирования, но не является ни примером хвостовой рекурсии, ни кo-рекурсии. Этот пример можно рассмотреть с разных точек зрения: как пример преобразования нисходящего динамического программирования к восходящему (с использованием только статической памяти фиксированного размера), или как доказательство функциональной эквивалентности между рекурсивной и итеративной программами (которое в дальнейшем может послужить примером для автоматического доказательства), или как захватывающую алгоритмическую головоломку либо задачу дизайна, анализа и верификации алгоритмов. Статья публикуется в авторской редакции.

Ключевые слова: рекурсивные и стандартные схемы программ, рекурсивные и итеративные программы, функциональная эквивалентность программ и схем программ, восходящее и нисходящее динамическое программирование, устранение рекурсии, ассоциативные и стандартные массивы, статическая и динамическая память.

DOI: https://doi.org/10.18255/1818-1015-549-560

Полный текст: PDF файл (666 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.68
Поступила в редакцию: 26.09.2018
Язык публикации: английский

Образец цитирования: N. V. Shilov, “Etude on recursion elimination”, Модел. и анализ информ. систем, 25:5 (2018), 549–560

Цитирование в формате AMSBIB
\RBibitem{Shi18}
\by N.~V.~Shilov
\paper Etude on recursion elimination
\jour Модел. и анализ информ. систем
\yr 2018
\vol 25
\issue 5
\pages 549--560
\mathnet{http://mi.mathnet.ru/mais648}
\crossref{https://doi.org/10.18255/1818-1015-549-560}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mais648
  • http://mi.mathnet.ru/rus/mais/v25/i5/p549

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Моделирование и анализ информационных систем
    Просмотров:
    Эта страница:43
    Полный текст:21
    Литература:6
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019