научный журнал по математике Программирование ISSN: 0132-3474

Архив научных статейиз журнала «Программирование»

  • СЕМИНАР ПО КОМПЬЮТЕРНОЙ АЛГЕБРЕ В 2013-2014 Г

    АБРАМОВ С.А., БОГОЛЮБСКАЯ А.А., РОСТОВЦЕВ В.А. — 2015 г.

    В семинаре рассматриваются новые результаты в области компьютерной алгебры - символьные алгоритмы и их реализация, соответствующие вопросы системного программирования. В 2012-2013 учебном году семинар собирался раз в месяц по третьим средам на факультете вычислительной математики и кибернетики МГУ, а в мае 2014 г. в Дубне, в Объединенном институте ядерных исследований (ОИЯИ) состоялось традиционное заседание, организованное совместно с Лабораторией информационных технологий ОИЯИ. Январский семинар был посвящен памяти Евгения Александровича Гребеникова (20.01.1932-29.12.2013).

  • СИСТЕМЫ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ С ВЫДЕЛЕННОЙ ЧАСТЬЮ НЕИЗВЕСТНЫХ

    ПАНФЕРОВ А.А. — 2015 г.

    Пусть дифференциальная система A 1y'' + А оу = 0 с возможно вырожденной матрицей А 1 имеет полный ранг. Пусть выделена часть неизвестных, т. е. часть компонент вектора у. Предлагается алгоритм, который в этой ситуации позволяет получить для некоторой части у компонент вектора у систему вида у'' = By, при этом те выделенные компоненты у, которые не вошли в у, линейно выражаются через вошедшие в у выделенные компоненты.

  • СРАВНЕНИЕ ЭФФЕКТИВНОСТИ МНОГОСЕТОЧНОГО МЕТОДА НА СОВРЕМЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ АРХИТЕКТУРАХ

    ЖУКОВ В.Т., КРАСНОВ М.М., НОВИКОВА Н.Д., ФЕОДОРИТОВА О.Б. — 2015 г.

    Исследована производительность современных процессорных архитектур при использовании масштабируемого компьютерного кода, представляющего ультрапараллельную реализацию многосеточного алгоритма решения параболических и эллиптических дифференциальных уравнений на трехмерных декартовых сетках. Показано, что код сохраняет эффективность при его функционировании на серверных многоядерных процессорах, графических ускорителях Nvidia и 60-ядерных сопроцессорах Xeon Phi архитектуры Intel MIC.

  • СУПЕРКОМПИЛЯЦИЯ ДЛЯ ТЕОРИИ ТИПОВ МАРТИНА-ЛЁФА

    КЛЮЧНИКОВ И.Г., РОМАНЕНКО С.А. — 2015 г.

    Описывается структура и реализация сертифицирующего суперкомпилятора ТТ Lite, преобразующего исходную программу в пару, содержащую остаточную программу и доказательство того, что остаточная программа эквивалентна исходной. Насколько можно судить по существующим публикациям, сертифицирующая суперкомпиляция для нетривиального функционального языка высшего порядка реализована впервые. Доказательства, порождаемые суперкомпилятором ТТ Lite, могут быть верифицированы проверялыциком типов, который независим от суперкомпилятора и не основан на суперкомпиляции. Это существенно в ситуациях, когда решающее значение имеет надежность результатов, полученных с помощью суперкомпиляции.

  • ТРАНСФОРМАЦИЯ ДИНАМИЧЕСКИХ ПРЕДСТАВЛЕНИЙ В ПРЕДМЕТНО-ОРИЕНТИРОВАННОМ ВИЗУАЛЬНОМ МОДЕЛИРОВАНИИ

    КОЗНОВ Д.В., ЛАРЧИК Е.В., ТЕРЕХОВ А.Н. — 2015 г.

    Навигационные сервисы являются важной составляющей модельно-ориентированных средств, предоставляя пользователям возможности просмотра и изучения больших моделей. В данной статье даётся формальные определения динамического представления, трансформации динамического представления (v''2v-трансформацпям) и навигационного сервиса. Для задания v2v-трансформации предлагается использовать язык ATL. В работе также представлена апробация данного подхода - описан прототип программного решения, реализующего предложенный подход в среде Eclipse GMF и использующий для автоматизации раскладки результатов трансформации технологию KIELLER. Представлен также графический редактор, содержащий базовые навигационные сервисы для диаграмм классов.

  • ЭКСПОНЕНЦИАЛЬНО-ЛОГАРИФМИЧЕСКИЕ РЕШЕНИЯ ЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ СИСТЕМ С КОЭФФИЦИЕНТАМИ В ВИДЕ СТЕПЕННЫХ РЯДОВ

    РЯБЕНКО А.А. — 2015 г.

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

  • 3D SLAM ПО СТЕРЕОИЗОБРАЖЕНИЯМ

    БОБКОВ В.А., КУДРЯШОВ А.П., МАШЕНЦЕВ В.Ю., РОНЬШИН Ю.И. — 2014 г.

    Предлагается метод визуальной навигации автономного подводного аппарата по стереоизображениям. Рассмотрены две модификации метода. Первая модификация основана на интеграции данных измерений бортовой навигационной системы с визуальными данными, вторая - на применении 6-облачной схемы вычислений. Приведены сравнительные результаты вычислительных экспериментов с модельными данными.

  • CONTROLLED EXECUTION WITH EXPLICIT MODEL

    BETELIN V.B., GALATENKO V.A., KOSTYUKHIN K.A. — 2014 г.

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

  • HENLM-LA: ЛОКАЛЬНО-АДАПТИВНЫЙ АЛГОРИТМ НЕЛОКАЛЬНОГО СРЕДНЕГО НА ОСНОВЕ РАЗЛОЖЕНИЯ ПО ФУНКЦИЯМ ЭРМИТА

    ЛУКИН А.С., МАМАЕВ Н.В., ЮРИН Д.В. — 2014 г.

    Предлагается алгоритм подавления шума (HeNLM-LA), представляющий собой модификацию алгоритма нелокального среднего на основе разложения локальных окрестностей пикселя по функциям Эрмита. Параметр, определяющий силу фильтрации, выбирается пропорциональным уровню шума в локальной окрестности. На основе анализа модельной задачи разработан алгоритм локальной оценки среднеквадратичного отклонения шума, идея которого состоит в подавлении в локальной дисперсии яркости больших значений, обусловленных скачком яркости на границе объектов.

  • INFLUENCE OF REGULAR SYSTEM INTERRUPTS ON PERFORMANCE OF PARALLEL STENCIL COMPUTATIONS

    KALGIN K.V. — 2014 г.

    В работе исследуется влияние наиболее затратных по ресурсам регулярных системных прерываний на производительность параллельных программ. Эти прерывания, в зависимости от аппаратной архитектуры и настроек операционной системы, занимают 0.1-5% времени работы CPU [1], [2], но могут стать причиной 10-100% ухудшения производительности параллельной программы, например, в массовых операциях [3]-[10]. Исследуется влияние этих прерываний на время работы класса параллельных программ с синхронизацией между соседними процессами на каждой итерации таких, как трафаретные вычисления, синхронный клеточный автомат, явная разностная схема. Приводятся результаты тестирования на вычислительных кластерах. Формулируются меры по уменьшению влияния прерываний на производительность параллельной программы

  • LANGUAGE OF DYNAMIC-REAL AND HIS APPLICATION FOR VERIFICATION OF SDL-SPECIFICATIONS DISTRIBUTED SYSTEMS

    NEPOMNYASHCHY V.A., VBODIN E., VERETNOV S.O. — 2014 г.

    Представлен язык спецификаций распределенных систем Dynamic-REAL (dREAL), который расширяет разработанный ранее язык Basic-REAL посредством динамических конструкций порождения и уничтожения экземпляров процессов. Описан программный комплекс SRDSV2 (SDL/REAL Distributed Systems Verifier), предназначенный для моделирования, анализа и верификации SDL-спецификаций распределенных систем. Этот комплекс включает транслятор из языка SDL в язык dREAL, систему автоматического моделирования dREAL-спецификаций и транслятор из языка dREAL во входной язык Promela системы верификации SPIN. Описано применение этого комплекса для верификации динамической системы управления сетью касс-терминалов.

  • OPERATING SYSTEMS OF THE BAGUETTE FAMILY (LIKENESS, DIFFERENCES AND PERSPECTIVES)

    GODUNOV A.N., SOLDATOV V.A. — 2014 г.

    В работе рассматриваются основные принципы построения отечественных операционных систем реального времени ОСРВ Багет 2.0 и ОСРВ Багет 3.0, отмечается, в чём их сходство и чем они отличаются друг от друга, говорится о перспективах дальнейшего развития.

  • PERFORMANCE ANALYSIS OF CONCURRENT SYSTEMS IN ALGEBRA DTSIPBC

    MACIA H., TARASYUK I.V., VALERO V. — 2014 г.

    Исчисление боксов Петри РВС - известная алгебра параллельных процессов с семантикой сетей Петри. В статье рассматривается расширение РВС дискретным стохастическим временем и мгновенными мультидействиями, названное дискретно-временным и мгновенным РВС (dtsiPBC). В рамках этой алгебры стохастических процессов исследуются методы анализа производительности параллельных и распределенных систем со случайными временными задержками. Устанавливается, что оценка производительности возможна не только на основе полумарковских цепей, соответствующих выражениям dtsiPBC, но и с использованием соответствующих дискретно-временных цепей Маркова, что является более оптимальной техникой анализа.

  • USE OF PROGRAM MODELS FOR DIAGNOSING MANAGEMENT INFORMATION SYSTEMS

    BEZMEN G.V., KOLESOV N.V. — 2014 г.

    Рассматривается одна из проблем, возникающих при создании системного программного обеспечения - проблема разработки диагностических процедур. Чаще всего эти процедуры заключаются в использовании программ тестового диагностирования. Однако для информационно-измерительных и информационно-управляющих систем оказываются полезными и значимыми программы функционального диагностирования, проверяющие систему в процессе решения задач. Предлагается подход к разработке таких программ, основанных на использовании модели системы.

  • АВТО-РАСПАРАЛЛЕЛИВАТЕЛЬ И ВЕКТОРИЗАТОР ПРОГРАММ, РЕАЛИЗОВАННЫЙ НА ОСНОВЕ УНИВЕРСАЛЬНОЙ БИБЛИОТЕКИ ТРАНСЛЯЦИИ И ТЕХНОЛОГИИ LLVM

    ВЛАДИСЛАВЛЕВ В.Е., ДРОЗДОВ А.Ю., ИЛЬИН П.В., КОЧЕТКОВ Е.Л., НОВИКОВ С.В. — 2014 г.

    Работа посвящена интеграции компилятора на основе библиотеки LLVM и инструментария, созданного с использованием Универсальной Библиотеки Трансляции (УБТ) - авто-распараллеливателя и векторизатора. Проведен сравнительный анализ промежуточных представлений, используемых в интегрируемых библиотеках. Приведено описание механизмов, которые потребовалось реализовать для интеграции. Также описаны наиболее важные компоненты УБТ. Наконец, были выполнены сравнительные замеры производительности системы трансляции, которая получилась в результате этой интеграции, и существующих компиляторов. Замеры производились на многоядерных системах на основе архитектур ARM и х86 на ряде задачах из пакетов SPEC/CPU2006 и NAS Parallel Benchmarks.

  • АВТОРСКИЙ УКАЗАТЕЛЬ СТАТЕЙ, ОПУБЛИКОВАННЫХ В 2013 ГОДУ

    2014

  • ЗАДАЧА ПРОВЕРКИ СУЩЕСТВОВАНИЯ РЕШЕНИЙ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ В ЧАСТНЫХ ПРОИЗВОДНЫХ В ПОЛЯХ ЛОРАНОВЫХ РЯДОВ

    ПАРАМОНОВ С.В. — 2014 г.

    Доказывается алгоритмическая неразрешимость задачи проверки существования решений в поле лорановых рядов для линейных дифференциальных уравнений в частных производных с полиномиальными коэффициентами. Дополнительно устанавливается разрешимость задачи проверки существования мономиальных решений с вещественными и комплексными показателями степеней

  • ИЗВЛЕЧЕНИЕ АДАПТИВНЫХ ПРИЗНАКОВ ДЛЯ ГЕНДЕРНОЙ КЛАССИФИКАЦИИ ИЗОБРАЖЕНИЙ ЛИЦ ЛЮДЕЙ

    ПРИОРОВ А.Л., ХРЯЩЕВ В.В., ШЕМЯКОВ А.М., ШМАГЛИТ Л.А. — 2014 г.

    Описан алгоритм автоматического распознавания пола людей по изображению лица, основанный на методах машинного обучения. Синтезированный алгоритм состоит из двух этапов: извлечение адаптивных признаков, классификация методом опорных векторов. Проведен сравнительный анализ работы предложенного алгоритма, представлена методика его обучения и тестирования.

  • ИССЛЕДОВАНИЕ ДВУХПАРАМЕТРИЧЕСКОЙ АЛГЕБРАИЧЕСКОЙ МОДЕЛИ ПРОГРАММ ПО МЕТОДИКАМ, РАЗРАБОТАННЫМ ДЛЯ ОДНОПАРАМЕТРИЧЕСКИХ МОДЕЛЕЙ

    ПОДЛОВЧЕНКО Р.И. — 2014 г.

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

  • ЛОГИЧЕСКИЕ И МНОЖЕСТВЕННЫЕ ВЫЧИСЛЕНИЯ В РАМКАХ ПАРАДИГМЫ ГЕОМЕТРИЧЕСКОЙ ИНФОРМАТИКИ

    СКОПИН И.Н., ТРИБИС Д.Ю. — 2014 г.

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