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

16

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

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

24 с.

PDF

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

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

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

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

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

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

36

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

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

16 с.

PDF

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

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

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

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

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

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

38

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

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

18 с.

PDF

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

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

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

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

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

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