ПРОГРАММНЫЕ СИСТЕМЫ: ТЕОРИЯ И ПРИЛОЖЕНИЯ

12+

Электронный научный журнал Института программных систем имени А.К. Айламазяна Российской академии наук

Титульная страница
О журнале
Редакция
Процесс публикации
Научная этика
Авторам
Выпуски журнала
Архив выпусков

Статьи представлены в формате PDF

Для чтения файлов в формате PDF рекомендуется
программа Adobe Reader

 


• Содержание выпуска •
• Искусственный интеллект, интеллектуальные системы, нейронные сети •
• Программное и аппаратное обеспечение распределенных и суперкомпьютерных систем •
• Математические основы программирования •
• Информационные системы в культуре и образовании •
• Информационные системы в медицине •
• Методы оптимизации и теория управления •
• Математическое моделирование •

Математические основы программирования

Ответственные за рубрику: д.ф.-м.н. Непейвода Н.Н.

Слева для каждой статьи показаны: присвоенный статье порядковый номер; дата поступления статьи в редакцию; количество страниц статьи в формате А5; ссылка на полный текст статьи в формате PDF .

 

16

Поступила в редакцию 05.10.2018

Подписана в печать 14.11.2018

24 с.

PDF

С. В. Знаменский
Численная оценка точности интерполяции несложных элементарных функций
 

Сравнение точности восстановления элементарных функций по значениям в узлах проведено для алгоритмов интерполяции низкой степени. Результаты тестирования представлены в графическом виде, наглядно демонстрирующем преимущества и недостатки широко используемых кубических интерполяционных сплайнов.
Сравнение выявило, что вопреки распространённому мнению гладкость интерполянт не связана непосредственно с точностью аппроксимации. На рассмотренных 20 разнородных примерах кусочно-квадратичная интерполяция редко и ненамного уступает в точности используемым классическим кубическим сплайнам, зачастую на порядки превосходя в точности многие из них.
В нескольких примерах высокая погрешность интерполяции несложных элементарных функций по фиксированной сетке оказалась практически независимой от степени алгоритма и гладкости интерполянты, в одном из них точнее всех неожиданно оказалась кусочно-линейная интерполяция.
Поставлена задача поиска локального алгоритма интерполяции, точно восстанавливающего рациональные функции второго порядка.

Ключевые слова:  локальная интерполяция, рациональная интерполяция, интерполяция сплайнами, точность восстановления.

Ссылка на статью обязательна

 http://psta.psiras.ru/read/psta2018_4_69-92.pdf

цифровой идентификатор статьи DOI

https://doi.org/10.25209/2079-3316-2018-9-4-69-92

17

Поступила в редакцию 05.10.2018

Подписана в печать 14.11.2018

24 с.

PDF

С. В. Знаменский
Численная оценка точности интерполяции несложных элементарных функций (англ)
 

Сравнение точности восстановления элементарных функций по значениям в узлах проведено для алгоритмов интерполяции низкой степени. Результаты тестирования представлены в графическом виде, наглядно демонстрирующем преимущества и недостатки широко используемых кубических интерполяционных сплайнов.
Сравнение выявило, что вопреки распространённому мнению гладкость интерполянт не связана непосредственно с точностью аппроксимации. На рассмотренных 20 разнородных примерах кусочно-квадратичная интерполяция редко и ненамного уступает в точности используемым классическим кубическим сплайнам, зачастую на порядки превосходя в точности многие из них.
В нескольких примерах высокая погрешность интерполяции несложных элементарных функций по фиксированной сетке оказалась практически независимой от степени алгоритма и гладкости интерполянты, в одном из них точнее всех неожиданно оказалась кусочно-линейная интерполяция.
Поставлена задача поиска локального алгоритма интерполяции, точно восстанавливающего рациональные функции второго порядка.

Ключевые слова:  локальная интерполяция, рациональная интерполяция, интерполяция сплайнами, точность восстановления.

Ссылка на статью обязательна

 http://psta.psiras.ru/read/psta2018_4_93-116.pdf

цифровой идентификатор статьи DOI

https://doi.org/10.25209/2079-3316-2018-9-4-93-116

36

Поступила в редакцию 25.11.2018

Подписана в печать 30.12.2018

16 с.

PDF

А. В. Климов
К автоматическому порождению программ трафаретных вычислений с улучшенной временной локальностью
 

Трафаретные (stencil) алгоритмы широко используются в задачах математического моделирования на регулярных сетках, эволюции клеточных автоматов (типа игры «жизнь»), обработки изображений, анализа последовательностей и т.п. Такие алгоритмы хорошо параллелятся, но обычные подходы к распараллеливанию имеют низкую временную локальность, что ограничивает их масштабируемость. Избавление от этого недостатка возможно при использовании различных схем переупорядочения обработки точек, когда пространство разбивается на небольшие области, помещающиеся в кэш, в которых удается продвинутся сразу на несколько итераций. Однако, такие схемы трудно программируются и отлаживаются. Есть несложный метод пирамид, но он плохо масштабируется, поскольку влечет дублирование вычислений. Наш подход состоит в использовании более сложных схем
переупорядочения без дублирования, для которых код может генерироваться автоматически из относительно несложной спецификации схемы. При этом сами схемы задаются путем назначения функций распределения вычислительных узлов по пространству и времени. В этой статье излагается подход, и рассматриваются на простом примере различные варианты кода, порождаемые по различным функциям распределения.

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

Ссылка на статью обязательна

 http://psta.psiras.ru/read/psta2018_4_493-508.pdf

цифровой идентификатор статьи DOI

https://doi.org/10.25209/2079-3316-2018-9-4-493-508

37

Поступила в редакцию 15.10.2018

Подписана в печать 30.12.2018

52 с.

PDF

С. Д. Мешвелиани
Построение доказательных программ арифметики натуральных чисел в двоичном представлении
 

Описывается опыт построения разработанной автором библиотеки доказательных программ арифметики натуральных чисел в двоичном представлении. Программа содержит машинно-проверяемые доказательства необходимых и главных свойств применённых алгоритмов. Используется язык программирования Agda — чисто функциональный язык, поддерживающий зависимые типы. Наличие зависимых типов даёт возможность включать в программу машинно-проверяемые доказательства. Арифметика реализована обычными алгоритмами «в столбик», действующими над списками двоичных разрядов. Построение соответствующих данной арифметике формальных и полных доказательств в программе оказывается не столь простым, как может показаться. Полученная программа исправляет и существенно дополняет часть Bin Стандартной библиотеки lib-0.16 языка Agda.

Ключевые слова: 
компьютерная алгебра, арифметика двоичных кодов, доказательное программирование, язык Agda.

Ссылка на статью обязательна

 http://psta.psiras.ru/read/psta2018_4_509-560.pdf

цифровой идентификатор статьи DOI

https://doi.org/10.25209/2079-3316-2018-9-4-509-560

38

Поступила в редакцию 17.04.2018

Подписана в печать 28.12.2018

18 с.

PDF

С. В. Знаменский
Устойчивая оценка качества алгоритмов сходства символьных строк и их нормализаций (англ.)
 

Выбор средств поиска скрытой общности в данных новой природы требует устойчивых и воспроизводимых сравнительных оценок качества абстрактных алгоритмов близости символьных строк. Обычные оценка на основе искусственно сгенерированных или вручную размеченных тестов существенно разнятся, надёжнее оценивая метод этой искусственной генерации по отношению к алгоритмам сходства, а оценки на базе данных пользователей не могут быть точно воспроизведены.
Предложена простая, прозрачная, объективная и воспроизводимая численная оценка качества метрики на строках. Используются параллельные тексты переводов книг на разные языки. Качество меры оценивается процентом ошибок в возможных различных попытках определения перевода данного абзаца среди двух абзацев книги на другом языке, один из которых действительно является переводом. Устойчивость оценок верифицируется независимостью от выбора книги и пары языков.
Численный эксперимент устойчиво отранжировал по качеству абстрактные алгоритмы сравнения символьных строк и показал сильную зависимость от выбора нормализации.

Ключевые слова:  сходство строк, анализ данных, метрика подобия, метрика расстояния, числовая оценка, оценка качества.

Ссылка на статью обязательна

 http://psta.psiras.ru/read/psta2018_4_561-578.pdf

цифровой идентификатор статьи DOI

https://doi.org/10.25209/2079-3316-2018-9-4-561-578

39

Поступила в редакцию 17.04.2018

Подписана в печать 28.12.2018

18 с.

PDF

С. В. Знаменский
Устойчивая оценка качества алгоритмов сходства символьных строк и их нормализаций
 

Выбор средств поиска скрытой общности в данных новой природы требует устойчивых и воспроизводимых сравнительных оценок качества абстрактных алгоритмов близости символьных строк. Обычные оценка на основе искусственно сгенерированных или вручную размеченных тестов существенно разнятся, надёжнее оценивая метод этой искусственной генерации по отношению к алгоритмам сходства, а оценки на базе данных пользователей не могут быть точно воспроизведены.
Предложена простая, прозрачная, объективная и воспроизводимая численная оценка качества метрики на строках. Используются параллельные тексты переводов книг на разные языки. Качество меры оценивается процентом ошибок в возможных различных попытках определения перевода данного абзаца среди двух абзацев книги на другом языке, один из которых действительно является переводом. Устойчивость оценок верифицируется независимостью от выбора книги и пары языков.
Численный эксперимент устойчиво отранжировал по качеству абстрактные алгоритмы сравнения символьных строк и показал сильную зависимость от выбора нормализации.

Ключевые слова:  сходство строк, анализ данных, метрика подобия, метрика расстояния, числовая оценка, оценка качества.

Ссылка на статью обязательна

 http://psta.psiras.ru/read/psta2018_4_579-596.pdf

цифровой идентификатор статьи DOI

https://doi.org/10.25209/2079-3316-2018-9-4-579-596

• Содержание выпуска •
• Искусственный интеллект, интеллектуальные системы, нейронные сети •
• Программное и аппаратное обеспечение распределенных и суперкомпьютерных систем •
• Математические основы программирования •
• Информационные системы в культуре и образовании •
• Информационные системы в медицине •
• Методы оптимизации и теория управления •
• Математическое моделирование •

 

Адрес редакции: 152021, Ярославская обл., Переславский район, село Веськово, ул. Петра Первого, д. 4 "а"
Тел.: (4852) 695-228.       E-mail: info@psta.psiras.ru.      Сетевой адрес издания: http://psta.psiras.ru

© Электронный научный журнал «Программные системы: теория и приложения» (дизайн) 2010-2017
© Институт программных систем имени А.К. Айламазяна РАН  2010-2018