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

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

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

    БАРАНОВ М.И. — 2014 г.

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

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

    МАЗАЛОВ В.В., НИКИТИНА Н.Н. — 2014 г.

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

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

    КОЛЕСОВ Н.В., ТОЛМАЧЕВА М.В., ЮХТА П.В. — 2014 г.

    Предлагаются алгоритмы планирования вычислительного процесса в однопроцессорных системах реального времени. Предполагается, что продолжительность решения задач известна неточно и определяется временным интервалом, что порождает неточность временной привязки (джиттер) решаемых задач.

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

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

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

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

    ЖОЖИКАШВИЛИ А.В. — 2014 г.

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

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

    ФУРУГЯН М.Г. — 2014 г.

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

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

    ГАВРИЛОВ Н.И., ТУРЛАПОВ В.Е. — 2014 г.

    Предложен новый подход к разработке алгоритмов объемного рендеринга на основе измерения качества визуализации. Анализ артефактов и исследование методов выполнены на примере 3D реконструкции медицинских томограмм. Выполнен анализ работ по объемной визуализации, посвященных методам повышения качества 3D визуализации и методам измерения качества. Предложен метод измерения (количественной оценки) артефактов и качества 3D визуализации, не требующий эталонного изображения и, следовательно, являющийся универсальным подходом к измерению качества реконструкции любым методом 3D визуализации. Метод основан на генерации эталонного изображения как математического ожидания 3D визуализаций, полученных путем зашумления старта луча в пределах одного шага вдоль луча. Для оценки отклонения от матожидания выбрана традиционная для сигналов и изображений величина PSNR в dB. Обсуждены условия корректности применения этой оценки. Предложен новый метод виртуальных выборок с предынтегрированием для подавления артефактов постклассификации в алгоритме RayCasting, отличающийся использованием предынтегрированной классификации в методе виртуальных выборок вместо постклассификации. Новый подход к разработке алгоритмов 3D визуализации, основанный на исследовании метода в осях качество-производительность и таком же сравнительном исследовании с другими методами, продемонстрирован на примере сравнительного исследования нескольких современных методов. Сравнительное исследование в осях качество-производительность показало преимущество метода предынтегрированной классификации, в случае трилинейной интерполяции исходных данных без освещения и теней, и нового метода виртуальных выборок с предынтегрированием, в случае трикубической фильтрации исходных данных с освещением и тенями.

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

    ОСИПОВ Н.Н. — 2014 г.

    В статье предлагается элементарный подход к механическому доказательству планиметрических теорем рационального типа. Этот подход реализован в виде программных модулей geom и его модифицированной версии geom_zeta, созданных в системе компьютерной алгебры Maple. Приводятся примеры механических доказательств сложных теорем планиметрии (как хорошо известных, так и сравнительно новых) на основе удобных рациональных параметризаций.

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

    БЕССМЕРТНЫЙ И.А., КОРОЛЕВА Ю.А. — 2014 г.

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

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

    ЕВТУШЕНКО Н.В., КУЛЯМИН В.В., КУШИК Н.Г. — 2014 г.

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

  • ОКТО-ДЕРЕВЬЯ СО МНОЖЕСТВЕННЫМИ ССЫЛКАМИ В ПРИМЕНЕНИИ К РЕАЛИЗАЦИИ ФОТОННЫХ КАРТ И КЭША ОСВЕЩЕННОСТИ НА GPU

    ВОСТРЯКОВ К.А., ГАЛАКТИОНОВ В.А., ФРОЛОВ В.А., ХАРЛАМОВ А.А. — 2014 г.

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

  • ОСТАНОВКА АЛГОРИТМА F5

    ГАЛКИН В.В. — 2014 г.

    Алгоритм F5, вычисляющий базис Грёбнера порождённого однородными многочленами идеала, был предложен в 2002г. Фожером одновременно с обоснованием его корректности при условии остановки. Но сама остановка была показана только для регулярной последовательности многочленов. В этой работе будет доказано, что алгоритм останавливается на любых входных данных. Вначале выводится, что если алгоритм не остановится, то он получит пару многочленов, в которой первый может редуцировать второй. При этом не утверждается, что такая редукция будет разрешена всеми критериями из F5. Далее показывается, что при существовании такой пары найдётся и пара, в которой редукция разрешена критериями, что невозможно.

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

    ГОРОДИЛОВ М.А., ДОЛГОВЕСОВ Б.С., МАЗУРОК Б.С., МОРОЗОВ Б.Б. — 2014 г.

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

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

    ШЕМЯКОВА Е.С. — 2014 г.

    Рассматриваются факторизуемые операторы Лапласа вида L = d xd y + ad x + bd y + в, где коэффициенты a, b, в могут не быть константами. Для них рассматриваются преобразования Дарбу L -> Li, M € K[d x\, определенные сплетающим соотношением NL = LiM. Показано, что возможны только следующие случаи: (1) либо ker M П ker d x + b = {0} и L i тоже факторизуем, (2) либо в ker M П ker d x + b есть ненулевой элемент. Для каждого случая мы доказываем, что преобразования Дарбу можно представить в виде произведения преобразований Дарбу порядка один. В случае L преобразований Дарбу операторов первых порядков.

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

    КАМКИН А.С., СЕРГЕЕВА Т.И., СМОЛОВ С.А., ТАТАРНИКОВ А.Д., ЧУПИЛКО М.М. — 2014 г.

    Создание тестовых программ и анализ результатов их выполнения - основной подход к функциональной верификации микропроцессоров на системном уровне. Имеется множество методов автоматизации разработки тестовых программ, начиная от генерации случайного кода и заканчивая нацеленным построением тестов на основе моделей, однако панацеи не существует: на практике применяются комбинации различных техник, дополняющих друг друга. К сожалению, в настоящее время нет решения, позволяющего интегрировать имеющиеся методы генерации тестовых программ в единую среду. Для верификации микропроцессоров инженеры вынуждены использовать большое число разнообразных генераторов тестов, что приводит к ряду трудностей: (1) необходимость обеспечения согласованности конфигураций инструментов (в каждом из них задейству-ется свое описание целевого микропроцессора, в результате чего часть информации дублируется); (2) необходимость разработки вспомогательных утилит для интеграции инструментов друг с другом (разные средства имеют разные интерфейсы и используют разные форматы данных). В статье описывается концепция расширяемой среды генерации тестовых программ для микропроцессоров: среда предоставляет единую методологию создания генераторов тестовых программ, поддерживает распространенные методы генерации тестов и допускает расширение новыми средствами тестирования. Предложенная концепция была частично реализована в системе MicroTESK (Microprocessor TEsting and Specification Kit).

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

    АБРАМОВ С.А., ХМЕЛЬНОВ Д.Е. — 2014 г.

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

  • РЕКОНСТРУКЦИЯ НЕПРОЗРАЧНЫХ ВКЛЮЧЕНИЙ В ОБЪЕКТАХ С ВЫСОКИМ ПОКАЗАТЕЛЕМ ПРЕЛОМЛЕНИЯ

    ГАГАНОВ В.А., ИГНАТЕНКО А.В., ЛЕБЕДЕВ А.С. — 2014 г.

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

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

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

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

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

    ГУТНИК С.А., САРЫЧЕВ В.А. — 2014 г.

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

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

    БУДЬКО Д.А., ЩЕРБА С.А. — 2014 г.

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