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

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

  • ОСОБЕННОСТИ РЕАЛИЗАЦИИ ИНТЕРПРЕТАТОРА ПАРАЛЛЕЛЬНЫХ ПРОГРАММ В СРЕДЕ PARJAVA

    АВЕТИСЯН А.И., АКОПЯН М.С., ГАЙСАРЯН С.С., ИВАННИКОВ В.П. — 2009 г.

    В работе рассматриваются особенности реализации системы программирования ParJava, которая позволяет разрабатывать параллельные приложения на современном языке Java, оставаясь в рамках промышленного стандарта MPI. Описывается внутреннее представление модели SPMD-программы, построенное таким образом, чтобы возложить как можно большую часть процесса интерпретации параллельной Java-программы на JavaVM. Рассматриваются особенности генерации модели и ее подготовки к интерпретации. Генератор модели преобразует абстрактное синтаксическое дерево каждого метода моделируемой программы в модель потока управления, формирует модель вычислений, которая будет выполняться на JavaVM, и модуль оценки времени выполнения базовых блоков. Интерпретация модели, выполняющейся на p узлах параллельной вычислительной системы (кластера), реализуется в p логических процессах, каждый из которых выполняется в отдельном потоке. Интерпретация логического процесса состоит в интерпретации составляющих его методов, начиная со стартового. Интерпретация каждого метода заключается в выполнении модели вычислений этого метода на JavaVM, при этом порядок интерпретации базовых блоков, входящих в состав метода, определяется системным интерпретатором модели указанного метода. В системе реализована возможность редукции частей модели и интерпретация модели по частям. Обсуждаются проблемы моделирования и интерпретации коммуникационных функций. Коммуникационные функции описываются с помощью девяти базовых операций обмена. Для оценки времени передачи данных между процессами используется эмпирическая зависимость между объемом передаваемых данных и временем передачи данных, получаемая на тестах. Приводится краткое описание графического интерфейса системы ParJava. Система обеспечивает как платформо-независимость разрабатываемых приложений, так и существенное уменьшение накладных расходов на разработку, доводку и сопровождение. Тем самым решается важная проблема разработки высокопродуктивных параллельных приложений.

  • ПАМЯТИ МИХАИЛА РОМАНОВИЧА ШУРА-БУРА

    2009

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

    ВАСИЛЬЕВ Н.Н., ПАВЛОВ Д.А. — 2009 г.

    Целью настоящей работы является анализ различных классов конечных и бесконечных мономи-альных упорядочений. Понятие мономиального упорядочения играет ключевую роль в теории базисов Гребнера: каждый базис определяется некоторым допустимым упорядочением. В то же время, для того, чтобы определить базис Гребнера, не обязательно знать упорядочение всех мономов - достаточно знать только конечный отрезок данного упорядочения. Мы рассматриваем комбинаторику конечных мономиальных упорядочений и ее связь с ячейками универсального базиса Гребнера. Для каждого рассмотренного класса упорядочений (слабодопустимых, выпуклых и допустимых) представлен алгоритм перебора конечных упорядочений и получены комбинаторные числовые последовательности. Представлен алгоритм, позволяющий для произвольного базиса Гребнера вычислить все минимальные конечные упорядочения, которые полностью определяют этот базис. Представлен алгоритм, вычисляющий расширенный универсальный базис Гребнера произвольного нульмерного идеала.

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

    БУРДОНОВ И.Б., КОСАЧЕВ А.С. — 2009 г.

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

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

    КУЗЬМИН Е.В., СОКОЛОВ В.А., ЧАЛЫЙ Д.Ю. — 2009 г.

    В статье рассматриваются перспективы использования метода формальных утверждений о трассах [1] как средства спецификации и верификации программ, построенных в автоматном стиле [2-4]. Метод формальных утверждений о трассах позволяет точно определить внешнее поведение автоматной программы, абстрагируясь от деталей ее реализации, и применяется на этапе определения технических требований (requirements specification) для создаваемой системы. В статье показано, как на основе созданной спецификации можно определять семантику некоторых элементов автоматной программы, прежде всего тех, которые используются при взаимодействии с объектом управления, а также описан формальный подход, помогающий задать множество состояний автоматной программы. Кроме рассмотрения способов построения автоматных программ, приведены результаты исследований, касающихся верификации требований, представленных в построенной спецификации.

  • ПРОГРАММА НА ЯЗЫКЕ MATHEMATICA ДЛЯ "ИНТЕГРАТОРА БЕДНЯКА", РЕАЛИЗУЮЩЕГО ИДЕИ РИША И НОРМАНА

    КРАГЛЕР Г.Р. — 2009 г.

    В настоящей работе путем компьютерных экспериментов исследуются достоинства и недостатки эвристического подхода, лежащего в основе метода "параллельного интегрирования". Для этой цели описывается и используется реализация данного метода на языке Mathematica, которая в ряде случаев сопоставляется также с первоначальной реализацией метода на языке Maple.

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

    АЧАСОВА С.М. — 2009 г.

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

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

    АБРАМОВ С.А., БОГОЛЮБСКАЯ А.А., ЕДНЕРАЛ В.Ф., РОСТОВЦЕВ В.А. — 2009 г.

    Годовой отчет о работе научно-исследовательского семинара по компьютерной алгебре

  • СИСТЕМЫ АГЕНТОВ, УПРАВЛЯЕМЫХ ЛОГИЧЕСКИМИ ПРОГРАММАМИ: СЛОЖНОСТЬ ВЕРИФИКАЦИИ

    ВАЛИЕВ М.К., ДЕХТЯРЬ М.И., ДИКОВСКИЙ А.Я. — 2009 г.

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

  • СИСТЕМЫ С ПРИОРИТЕТАМИ: КОНФОРМНОСТЬ, ТЕСТИРОВАНИЕ, КОМПОЗИЦИЯ

    БУРДОНОВ И.Б., КОСАЧЕВ А.С. — 2009 г.

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

  • DOCLINE: МЕТОД РАЗРАБОТКИ ДОКУМЕНТАЦИИ СЕМЕЙСТВ ПРОГРАММНЫХ ПРОДУКТОВ

    КОЗНОВ Д.В., РОМАНОВСКИЙ К.Ю. — 2008 г.

    В работе представляется метод DocLine, предназначенный для разработки документации семейств программных продуктов. Метод обеспечивает повторное использование фрагментов документов с адаптации под контекст использования. Метод состоит из языка DRL (Documentation Reuse Language), имеющего графическую (для проектирования структуры пакета документов) и текстовую (для реализации документации) части, включает процесс разработки документации и архитектуру программных средств на базе DSM-подхода и технологии Eclipse GMF.

  • АВТОМАТИЗАЦИЯ МАССОВОГО СОЗДАНИЯ ТЕСТОВ РАБОТОСПОСОБНОСТИ

    ЗЫБИН Р.С., КУЛЯМИН В.В., ПОНОМАРЕНКО А.В., РУБАНОВ В.В., ЧЕРНОВ Е.С. — 2008 г.

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

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

    2008

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

    ТУРЛАПОВ В.Е., ЮСОВ Е.А. — 2008 г.

    Предлагается метод аппаратнореализуемой адаптивной триангуляции ландшафта (ААТЛ), основанный на оценке статической погрешности узлов квадрадерева с помощью вейвлет-преобразований и представлении итогового квадрадерева вспомогательной вершинной текстурой. Характерными особенностями метода ААТЛ являются следующие: соседние узлы порождаемой алгоритмом адаптированной сетки могут отличаться на любое число уровней иерархии; процесс триангуляции не ограничен размерами сегмента разбиения, что решает проблему сшивки сегментов без вставки дополнительных узлов; многомасштабное представление рельефа, используемое методом, позволяет хранить уровни детализации в памяти графического процессора как многоуровневую вершинную текстуру, благодаря чему наиболее ресурсоемкая часть алгоритма эффективно реализуется в вершинном шейдере. Алгоритм учитывает при построении триангуляции как локальные особенности поверхности, так и положение камеры, естественным образом поддерживает геоморфинг.

  • ВЫЧИСЛЕНИЕ ДОМИНИРУЮЩИХ ВЕЩЕСТВЕННЫХ КОРНЕЙ МНОГОЧЛЕНОВ

    ШТЕФАНЕСКУ Д. — 2008 г.

    Вычисление доминирующих положительных корней многочленов от одной переменной играет ключевую роль в алгоритмах изоляции вещественных корней. Мы предлагаем новый аппарат для вычисления доминирующих вещественных корней и сравниваем его с другими методами. Полученные нами результаты для корней, больших единицы, лучше, чем классические оценки Лагранжа и Лонгшампа. Мы также обсуждаем новое улучшение результата о границах для положительных корней, которое может применяться ко всем многочленам с переменами знаков.

  • ДИАЛОГОВАЯ ОТЛАДКА ПАРАЛЛЕЛЬНЫХ ПРОГРАММ: РАСПРЕДЕЛЕННАЯ СХЕМА ВЗАИМОДЕЙСТВУЮЩИХ КОМПОНЕНТОВ

    БУГЕРЯ А.Б. — 2008 г.

    В статье предложена общая схема организации распределенного диалогового отладчика параллельных программ и рассказано о практике применения данной схемы при создании отладчика для программ на языке НОРМА и для создания системы исследования МР1-программ

  • ДИСКРЕТНЫЕ ДИНАМИЧЕСКИЕ СИСТЕМЫ С СИММЕТРИЯМИ: КОМПЬЮТЕРНЫЙ АНАЛИЗ

    КОРНЯК В.В. — 2008 г.

    Дискретные динамические системы и мезоскопические решеточные модели рассматриваются с точки зрения их групп симметрии. Указаны универсальные особенности поведения детерминистических динамических систем, обусловленные наличием нетривиальных симметрии. Выявлена групповая природа солитоно-подобных движущихся структур типа "космических кораблей" в клеточных автоматах. Изучение решеточных моделей также существенно облегчается при учете групп их симметрии. Для группового анализа систем обоих типов написана программа на языке Си. Программа, в частности, строит и исследует фазовые портреты по модулю группы симметрии дискретных динамических систем, ищет динамические системы, обладающие особыми свойствами, такими, как, например, обратимость. В случае мезоскопических решеточных моделей программа вычисляет микроканонические распределения и ищет фазовые переходы. Представлены некоторые вычислительные результаты и наблюдения.

  • ИНВОЛЮТИВНЫЕ ДЕЛЕНИЯ И МОНОМИАЛЬНЫЕ УПОРЯДОЧЕНИЯ. ЧАСТЬ 2

    ЗЮЗИКОВ П.А., СЕМЕНОВ А.С. — 2008 г.

    Статья продолжает исследования авторов в области классификационных свойств инволютивных делений, начатые в [1]. Приводится пример, когда минимальный инволютивный базис конкретного мономиального идеала для ^-деления "антипод Жане" не является ни инволютивным базисом Жане, ни минимальным базисом Janet-like деления для любого из п\ упорядочений переменных. Этот пример опровергает гипотезу о том, что минимальный инволютивный базис для непрерывных и конструктивных делений всегда совпадает с базисом Жане при некотором упорядочении переменных.

  • ИНВОЛЮТИВНЫЙ МЕТОД ВЫЧИСЛЕНИЯ БАЗИСОВ ГРЕБНЕРА НАД F2

    ГЕРДТ В.П., ЗИНИН М.В. — 2008 г.

    В работе рассматривается инволютивный алгоритм вычисления базисов Гребнера для полиномиальных идеалов в кольце многочленов от многих переменных над конечным полем F2 и со значениями переменных в F2. Алгоритм использует деление Жане и специализирован для градуированного обратного лексикографического порядка мономов. Мы сравниваем эффективность данного алгоритма и его реализации на С-\-Ь с аналогичными показателями алгоритма Бухберге-ра, а также со встроенными алгоритмами вычисления базисов Гребнера в системах компьютерной алгебры Singular, C0C0A и в библиотеке FGb для Maple. В качестве примеров для сравнений взяты адаптированные к F2 некоторые серии примеров, широко используемые для вычисления базисов Гребнера над Q. Полиномиальные системы над IF 2 и со значениями переменных в F2 представляют интерес, в частности, для моделирования квантовых вычислений и ряда задач криптоанализа.

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

    ДЕМАКОВ А.В., ЗЕЛЕНОВ С.В., ЗЕЛЕНОВА С.А. — 2008 г.

    В статье представлен подход к автоматической генерации тестовых данных сложной структуры (таких, как XML-документы, программы на языках программирования и т.п.), основанный на использовании абстрактных моделей, которые отражают различные срезы структуры требуемых данных. Подход позволяет получать небольшие множества тестовых данных, нацеленных на тестирование заданной функциональности целевой системы. Использование абстрактных моделей делает процесс конфигурирования генерации легким и понимаемым, а также облегчает сопровождение и переиспользование существующих конфигураций генератора тестовых данных. Подход реализован в генераторе тестовых данных Pinery и успешно применялся в ряде проектов, в том числе в проектах по тестированию промышленных компиляторов языков C/C++.