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

БОГОЛЕПОВ Д.К., СОПИН Д.П., ТУРЛАПОВ В.Е. — 2011 г.

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

ШЕМЯКОВА E.C. — 2011 г.

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

ЖУРИХИН Д.М. — 2011 г.

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

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

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

КУЗНЕЦОВ С.Д., ТУРДАКОВ Д.Ю. — 2010 г.

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

СТАМАТОВИЧ Б. — 2010 г.

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

2010

КЫТМАНОВ А.А. — 2010 г.

В настоящей работе приводится алгоритм вычисления степенных сумм корней для класса систем нелинейных неалгебраических уравнений, основанный на многомерных рекуррентных формулах, полученных автором ранее.

ВОЛОБОЙ А.Г., ГАЛАКТИОНОВ В.А., ЛОБАЛЗО Н.А. — 2010 г.

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

КОНДРАТЬЕВА М.В. — 2010 г.

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

БЕССМЕРТНЫЙ И.А. — 2010 г.

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

ВИРБИЦКАЙТЕ И.Б. — 2010 г.

КОРНЫХИН Е.В. — 2010 г.

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

КАПЦОВ О.В. — 2010 г.

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

2010

КУЛЯМИН В.В. — 2010 г.

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

БЛИНКОВ Ю.А., ГЕРДТ В.П., ЗИНИН М.В. — 2010 г.

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

ДРАГАЛОВ К.В., ИЛЬИН Д.В., МОРОЗОВ С.В., СЕМЕНОВ В.А., СИДЯКА О.В. — 2010 г.

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

ГЕРДТ В.П., ПРОКОПЕНЯ А.Н. — 2010 г.

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

АБРАМОВ С.А. — 2010 г.

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