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

БУДЬКО Д.А., ПРОКОПЕНЯ А.Н. — 2013 г.

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

КУЗНЕЦОВ К.А. — 2013 г.

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

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

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

КОРОЛЬКОВА А.В., КУЛЯБОВ Д.С., СЕВАСТЬЯНОВ Л.А. — 2013 г.

В статье рассмотрены три вида тензорных расчётов. В соответствии с ними авторы попытались сформулировать критерии, которым должна удовлетворять система компьютерной алгебры для работы с тензорами. Сделан краткий обзор текущего состояния тензорных вычислений в разных системах компьютерной алгебры. Тензорные расчёты проиллюстрированы соответствующими примерами, реализованными в конкретных системах: Cadabra и Maxima.

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

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

ГРУШИН Д.А., КУЗЮРИН Н.Н. — 2013 г.

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

ДЖЕКОБСОН А., КАЙКО - МЭТСОН М., МАКМЭХОН П., СЕЙМУР Э., ХУАН Ш. — 2012 г.

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

2012

КАЛЕНКОВА А.А. — 2012 г.

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

САПОЖНИКОВ А.В. — 2012 г.

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

КОВАЛЕНКО Н.С., ПАВЛОВ П.А. — 2012 г.

Предлагается алгоритм оптимальной компоновки блоков структурированного программного ресурса в системах распределенных конкурирующих процессов.

ВИТЯЕВ Е.Е., ДЕМИН А.В., ПОНОМАРЕВ Д.К. — 2012 г.

В работе предлагается индуктивный вероятностный подход к «анализу формальных понятий» (англ. Formal Concept Analysis), в котором рассматривается вероятность на «формальных контекстах»; определяются вероятностные формальные понятия, обладающие прогностической силой - неклассифицированные объекты возможно отнести к ранее обнаруженным вероятностным формальным понятиям; из вероятностных формальных понятий исключаются случайные признаки; вероятностные формальные понятия устойчивы к шумам в данных. Приведен результат машинного эксперимента, в котором формальные понятия (в их стандартном определении из «анализа формальных понятий») были искажены наложением случайного шума, а затем восстановлены с помощью обнаружения вероятностных формальных понятий.

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

Восьмая международная Ершовская конференция по информатике (ПСИ'11) была проведена с 27-го июня по 4-е июля 2011 г. в Новосибирском Академгородке. ПСИ - это форум, на котором собираются ученые, разработчики и пользователи программного обеспечения, работающие как в науке, так и в промышленности. Цель форума - наведение мостов между сообществами, интересы которых затрагивают такие области, как разработка и анализ программ и систем, методология и технология программирования, информационные технологии. Конференции ПСИ позволяют обсудить современные методы и подходы и тем самым помочь специалистам в повышении надежности и эффективности методов, алгоритмов и инструментария разработки программных и информационных систем.

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

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

СИЛАКОВ Д.В — 2012 г.

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

ФАККА ФЕДЕРИКО М., ФЕНСЕЛЬ АННА, ФЕНСЕЛЬ ДИТЕР, ФРИД МИХАЕЛЬ А.Х. — 2012 г.

Мы совмещаем автоматическую радиочастотную идентификацию и веб-технологии в кастомизируемой системе для улучшения коммуникаций для участников и организаторов конференций. Наша система позволяет пользователям авторизоваться при помощи RFID-меток и получить доступ к интерактивным онлайн сервисам при помощи карманного компьютера. Разработанные сервисы служат для поддержки социального взаимодействия участников и подтверждают перспективность совмещения в эксплуатации оффлайновых и онлайновых социальных сетей. Основная гипотеза нашей работы такова: сенсорная информационная система может значительно улучшить уровень коммуникаций на конференциях. Технически, мы исследовали применение технологий Web 2.0 в социальных, сенсорных и мобильных системах на конференциях и других подобных мероприятиях. Данная статья является обзором системы и ее оценки путем опросов пользователей и анализа данных, собранных во время проведения Extended Semantic Web Conference (ESWC) 2010 и иных схожих международных конференциях, в которых было задействовано несколько сотен участников.

МАНДРЫКИН М.У., МУТИЛИН В.С., НОВИКОВ Е.М., ХОРОШИЛОВ А.В., ШВЕД П.Е. — 2012 г.

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

ДОРОФЕЕВА М., ЕВТУШЕНКО Н., ЭЛЬ-ФАКИ К. — 2012 г.

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

2012

23 мая 2012 года исполняется 80 лет Виталию Александровичу Ростовцеву, известному специалисту в области системного программирования и компьютерной алгебры.

ГАЛИМУЛЛИН Р.Ф., ШАБАЛДИНА Н.В. — 2012 г.

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