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

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

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

    ИНЮХИН А.В. — 2008 г.

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

  • К СИНТЕЗУ УСЛОВНЫХ ТЕСТОВ ДЛЯ НЕДЕТЕРМИНИРОВАННЫХ АВТОМАТОВ

    ГРОМОВ М.Л., ЕВТУШЕНКО Н.В., КОЛОМЕЕЦ А.В. — 2008 г.

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

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

    САМАРЕВ Р.С. — 2008 г.

    При разработке параллельных СУБД, как правило, подразумевают специализированные многопроцессорные вычислительные комплексы. Причем чаще всего предполагается монопольная работа СУБД. Однако в классе многопроцессорных вычислительных систем с архитектурой х86, ориентированных на массового потребителя, монопольность СУБД по отношению к другому программному обеспечению часто не обеспечивается. Кроме того, унаследованное программное обеспечение для данного класса вычислительных систем часто не предназначено для массового параллельного выполнения. Игнорирование требования немонопольной работы и неиспользование ресурсов ВС в режимах малой нагрузки СУБД являются причинами неэффективного использования ресурсов вычислительной системы в целом. В статье рассматривается метод программной организации управляемого параллелизма на уровне внутренних операций СУБД, обеспечивающий их контролируемое выполнение с учетом состояния вычислительной системы в целом. Разработанный метод позволил существенно снизить время отклика при малых плотностях поступления запросов в коммерческой объектной СУБД ODB-Jupiter, разработанной в НПЦ "ИНТЕЛТЕК ПЛЮС". Разработанный метод управляемого параллельного выполнения может применяться в широком классе программных систем.

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

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

    С целью упрощения моделирования и верификации коммуникационных протоколов, представленных на языке SDL, вводятся так называемые иерархические временные типизированные сети Петри (ИВТ-сети), которые являются существенной модификацией раскрашенных сетей Петри. Описан метод трансляции языка SDL в ИВТ-сети. Представлен программный комплекс SPV (SDL Protocol Verifier), который включает транслятор из SDL в ИВТ-сети, а также средства для редактирования, симуляции, визуализации и верификации этих сетевых моделей. Для верификации используется метод проверки моделей относительно свойств, представленных формулами мю-исчисления. Описаны эксперименты по применению комплекса SPV для моделирования и верификации двух кольцевых протоколов (RE-протокола и ATMR-протокола), оптимизированной версии протокола скользящего окна (i-протокола), а также динамической версии протокола InRes.

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

    КУЗЬМИН Е.В., СОКОЛОВ В.А. — 2008 г.

    Статья посвящена описанию, спецификации и верификации моделей программ, построенных на основе автоматного подхода к программированию [1-5].

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

    БОБКОВ В.А., БОРИСОВ Ю.С., ИНЗАРЦЕВ А.В., МЕЛЬМАН С.В. — 2008 г.

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

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

    АФАНАСЬЕВ А.Н., ШАРОВ О.Г. — 2008 г.

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

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

    ПОЛЯКОВ С.П. — 2008 г.

    Предлагается алгоритм неопределенного суммирования рациональных функций, строящий для данной функции f(x) пару рациональных функций д(х),г(х) таких, что f(x) = д(х + 1)-д(х)+г(х), степень знаменателя г(х) минимальна, и при выполнении этого условия степень знаменателя д(х) также минимальна.

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

    АНУРЕЕВ И.С., БОДИН Е.В., ШИЛОВ Н.В. — 2008 г.

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

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

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

    Нами рассматривается специального вида алгебраическая модель программ и обсуждается проблема минимизации для схем программ из этой модели.

  • ОБ ОДНОЙ КОМПЬЮТЕРНО-АЛГЕБРАИЧЕСКОЙ ТЕХНОЛОГИИ

    АБРАМОВ С.А., РЯБЕНКО А.А. — 2008 г.

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

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

    БОРИСЕНКО Г.В., ДЕНИСОВ А.М., КРЫЛОВ А.С. — 2008 г.

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

    ПАЛИЙ Ю.Г., ХВЕДЕЛИДЗЕ А.М. — 2008 г.

    Алгоритмические методы коммутативной алгебры, основанные на технике инволютивных базисов и базисов Гребнера, являются эффективным средством приведения уравнений движения динамических систем в инволюцию. В то же время при практической работе с тензорными величинами большой размерности непосредственное использование стандартных функций вычисления базисов Гребнера, встроенных в системы компьютерной алгебры (Maple, Mathematica) приводит к значительным затратам памяти. Однако тензоры, будучи полилинейными формами, допускают введение специальной градуировки, позволяющей классифицировать многочлены по степени однородности. С учетом этой особенности для избежания проблем, связанных с большим объемом вычислений, в работе предлагается использовать специальный однородный базис Гребнера. Такой базис строится поэтапно, в порядке возрастания степени многочленов. В качестве примера приведен алгоритм построения однородного базиса в конечномерной гамильтоновой системе с большим количеством полиномиальных связей, так называемой модели калибровочной механики Янга-Милса.

  • ОБ ОПОРНОМ СУММИРОВАНИИ

    АБРАМОВ С.А., ПЕТКОВШЕК М. — 2008 г.

    Рассматривается суммирование последовательных значений + 1),..., мероморфной функции где v,w 6 Z. Предполагается, что удовлетворяет линейному разностному уравнению Ь(у) = 0 с полиномиальными коэффициентами, и что для L существует суммирующий оператор (если такой оператор существует, то он может быть найден алгоритмом аккуратного суммирования или, в случае ord L = 1, алгоритмом Госпера). Вводится понятие опорного суммирования, охватывающего и тот случай, когда имеет полюсы в множестве Z.

  • ОТ РЕДАКТОРОВ СПЕЦИАЛЬНОГО ВЫПУСКА

    НЕПОМНЯЩИЙ В.А., ПЕТРЕНКО А.К. — 2008 г.

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

    ЯНОВИЧ Д.А. — 2008 г.

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

  • ПАМЯТИ ЕВГЕНИЯ ВАСИЛЬЕВИЧА ПАНКРАТЬЕВА

    АБРАМОВ С.А., КОНДРАТЬЕВА М.В., ЛАТЫШЕВ В.Н., МИХАЛЕВ А.В. — 2008 г.

  • ПОДДЕРЖКА ЭВОЛЮЦИИ СХЕМ ДАННЫХ В XML-РЕЛЯЦИОННЫХ СИСТЕМАХ БАЗ ДАННЫХ

    СИМАНОВСКИЙ А.А. — 2008 г.

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

  • ПОДХОД К СОЗДАНИЮ СРЕД РАЗРАБОТКИ ДЛЯ ШИРОКОГО КЛАССА ЯЗЫКОВ ПРОГРАММИРОВАНИЯ

    ГОМАНЮК С.В. — 2008 г.

    Создание среды разработки для нового языка программирования - нетривиальная и ресурсоемкая задача. Наличие таких универсальных интегрирующих платформ, как Eclipse, NetBeans, MS Visual Studio и др., позволяет частично упростить ее решение. В статье проводится сравнительный анализ подходов к созданию среды разработки на базе универсальной интегрирующей платформы и предлагается авторский подход, устраняющий недостатки и сохраняющий достоинства существующих подходов.

  • ПОИСК ЛИУВИЛЛЕВЫХ РЕШЕНИЙ ЛИНЕЙНЫХ РЕКУРРЕНТНЫХ УРАВНЕНИЙ В СИСТЕМЕ КОМПЬЮТЕРНОЙ АЛГЕБРЫ MAPLE

    ХМЕЛЬНОВ Д.Е. — 2008 г.

    В работе рассматривается реализация в системе компьютерной алгебры Maple алгоритма Зингера-Хендрикса поиска лиувиллевых решений линейных рекуррентных уравнений с коэффициентами в виде рациональных функций.