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

12+

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

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

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

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

 


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

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

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

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

 

17

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

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

14 с.

PDF

В. В. Бурховецкий
Оптимизация и распараллеливание упрощенного алгоритма Балаша-Кристофидеса для задачи коммивояжера
 

В работе описывается точный параллельный алгоритм для задачи коммивояжера, основанный на упрощенном алгоритме Балаша-Кристофидеса, его оптимизация и увеличение эффективности распараллеливания. За счет нового метода передачи заданий между параллельными потоками алгоритм способен решать задачи с 3000 вершинами (со случайными весами дуг), в среднем, за минуту, а задачи с 10000 вершинами — за 50 минут. Возможность решать задачи с более чем 3000 вершинами появилась благодаря проведенной автором оптимизации расхода памяти.

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

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

http://psta.psiras.ru/read/psta2020_4_3-16.pdf

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

http://doi.org/10.25209/2079-3316-2020-11-4-3-16

21

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

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

25 с.

PDF

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

Простой пример иллюстрирует недостаточность известных подходов к интерполяции в задаче восстановления функции по немногим заданным отчётливо передающим форму частным значениям.
Известные подходы дополняет локальный выбор между полиномиальной
и рациональной локальными интерполянтами, минимизирующий ошибки локальной интерполянты в ближайших внешних узлах c одной или разных сторон. Новый подход сочетает предельную вычислительную простоту локальных интерполянт с тщательностью их подбора.
Принципы построения алгоритма сформулированы в общем виде для
отображений метрических пространств. Они обеспечивают точное (за редкими исключениями) восстановление отображений, локально совпадающих с какими-то из заданных возможных интерполянт.
В одномерном случае двухэтапный алгоритм гарантирует непрерывность
интерполянты и точное восстановление одновременно
(1) полиномов малой степени,
(2) несложных рациональных функций с линейным знаменателем,
(3) ломаных из длинных звеньев с узлами на концах
в типичных ситуациях, когда эти требования не противоречат друг другу.
Дополнительный параметр позволяет заменить точное восстановление
ломаных требуемой гладкостью интерполяции.

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

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

http://psta.psiras.ru/read/psta2020_4_73-97.pdf

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

https://doi.org/10.25209/2079-3316-2020-11-4-73-97

22

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

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

24 с.

PDF

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

Простой пример иллюстрирует недостаточность известных подходов к интерполяции в задаче восстановления функции по немногим заданным отчётливо передающим форму частным значениям.
Известные подходы дополняет локальный выбор между полиномиальной
и рациональной локальными интерполянтами, минимизирующий ошибки локальной интерполянты в ближайших внешних узлах c одной или разных сторон. Новый подход сочетает предельную вычислительную простоту локальных интерполянт с тщательностью их подбора.
Принципы построения алгоритма сформулированы в общем виде для
отображений метрических пространств. Они обеспечивают точное (за редкими исключениями) восстановление отображений, локально совпадающих с какими-то из заданных возможных интерполянт.
В одномерном случае двухэтапный алгоритм гарантирует непрерывность
интерполянты и точное восстановление одновременно
(1) полиномов малой степени,
(2) несложных рациональных функций с линейным знаменателем,
(3) ломаных из длинных звеньев с узлами на концах
в типичных ситуациях, когда эти требования не противоречат друг другу.
Дополнительный параметр позволяет заменить точное восстановление
ломаных требуемой гладкостью интерполяции.

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

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

http://psta.psiras.ru/read/psta2020_4_99-122.pdf

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

https://doi.org/10.25209/2079-3316-2020-11-4-99-122

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

 

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

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