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

ЕРМОЛОВИЧ А.В., СОКОЛОВ Р.А. — 2012 г.

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

ГАРАНИНА НАТАЛЬЯ ОЛЕГОВНА — 2012 г.

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

КАЛИНИЧЕНКО Л.А. — 2012 г.

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

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

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

СОСНИН М.В. — 2011 г.

Работа посвящена теории декомпозиции дифференциальных многочленов (в дальнейшем, для краткости, д. м.). Для данного дифференциального алгебраического уравнения P(x, y(x), y'(x),..., y(n)(x)) = 0 исследуется возможность представления дифференциального многочлена P в виде композиции д. м. Q и R: P = Q(x, R, R',..., R(q), R = R(x, y(x),..., y(r)(x)). Показано, что проблема декомпозиции сводится к проблеме факторизации линейных обыкновенных дифференциальных операторов (ЛОДО). Приводится общий алгоритм декомпозиции д. м., основанный на дифференциальной теореме Вандермонда.

КОНОНОВ В.А., КОНУШИН А.С., КОНУШИН В.С. — 2011 г.

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

НИКЕШИН А.В., ПАКУЛИН Н.В., ШНИТМАН В.З. — 2011 г.

Статья посвящена разработке тестового набора для проверки соответствий реализаций узлов Интернет спецификациям нового протокола безопасности IPsec v2 [1-7]. Для построения тестового набора использовалась технология автоматического тестирования UniTESK [8] и программный пакет CTesK [9], реализующий эту технологию. Работа выполнялась в Институте системного программирования РАН в рамках проекта «Верификация функций безопасности протокола нового поколения IPsec v2» при поддержке гранта РФФИ 07-07-00243. В ходе ее выполнения были выделены требования к реализациям IPsec v2, разработаны формальные спецификации и прототип тестового набора для верификации реализаций IPsec v2, в том числе реализаций протокола автоматического создания контекстов безопасности IKEv2. В статье описаны метод формализации требований IPsec v2, процесс создания тестового набора, а также результаты тестирования существующих реализаций. Эти результаты показывают, что предложенный в данной работе метод верификации позволяет эффективно автоматизировать тестирование таких сложных протоколов, как протоколы безопасности.

КОНОНОВ В.А., КОНУШИН А.С., КОНУШИН В.С., МИЗИН И.С., ЯКУБЕНКО А.А. — 2011 г.

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

АРАНСОН А.Б. — 2011 г.

Продолжается вычисление степенных разложений решений системы ОДУ Н.Ковалевского алгоритмами степенной геометрии. Система Н.Ковалевского это система двух нелинейных неавтономных ОДУ. Ранее А.Брюно, В.Лунёв, И.Гашененко алгоритмами степенной геометрии вычислили различные разложения решений этой системы во всех случаях, когда независимая переменная стремится к нулю и бесконечности. Теперь рассматриваются случаи, когда независимая переменная стремится к отличной от нуля и бесконечности константе. Для этого в независимой переменной выделена постоянная часть, являющаяся новым параметром, а разложение ведётся по оставшейся переменной части. Алгоритмами степенной геометрии вычислены степенные разложения решений такой системы. Также сделана реализация применённых алгоритмов на языке системы символьных вычислений Maxima и на языке программирования C++.

ГЕЙН А.Г. — 2011 г.

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

МАШЕЧКИН И.В., ПЕТРОВСКИЙ М.И., ПОПОВ Д.С., ЦАРЁВ Д.В. — 2011 г.

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

БЕССМЕРТНЫЙ И.А., КАТЕРИНЕНКО Р.С. — 2011 г.

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

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

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

СИЛАКОВ Д.В., ХОРОШИЛОВ А.В. — 2011 г.

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

ГАЛАХОВ И.В., ПОЗИН Б.А. — 2011 г.

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

КОНОНОВ А.И., ПАДАРЯН В.А., СОЛОВЬЕВ М.А. — 2011 г.

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

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

Предлагается компьютерно-алгебраический алгоритм неопределенного суммирования рациональных функций, основанный на полной факторизации знаменателей. Для данной f алгоритм находит пару рациональных функций g, r таких, что f = g(x + 1) - g(x) + r, и степень знаменателя r минимальна. Также предлагается модификация алгоритма, дополнительно минимизирующая степень знаменателя g. Доказано, что без учета затрат на факторизацию знаменателя алгоритмы имеют вычислительную сложность O(m2), где m - степень знаменателя f.

ЕДНЕРАЛ В.Ф., РОМАНОВСКИЙ В.Г. — 2011 г.

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

АРТАМОНОВ Н.И., КОЗНОВ Д.В., ЛАРЧИК Е.В., ПЛИСКИН М.М. — 2011 г.

В данной работе представлено решение задачи слияния карт памяти (Mind Maps) в контексте процесса коллективной Интернет-разработки таких карт. Эта задача актуальна, например, в ситуации, когда один из разработчиков теряет Интернет-соединение, но продолжает изменять карту памяти локально, и его товарищи также меняют ее. Таким образом, при восстановлении Интернет-соединения возникает потребность в слиянии локальной и серверной копий карты памяти. Задача решена на основе известного алгоритма слияния XML-файлов 3DM, модифицированного в соответствии с особенностями нашей задачи: (1) необходимость двух режимов работы -по умолчанию и с предоставлением пользователю возможности самостоятельно разрешать конфликты; (2) необходимость максимального сохранения изменений, сделанных в поддеревьях при разрешении конфликтов Update/Delete; (3) несимметричность сливаемых деревьев (серверная копия считается более приоритетной); (4) необходимость применения edit-скрипта к исходной версии для сохранения истории изменений; (5) наличие уникальных идентификаторов у узлов сливаемых деревьев (то есть более упрощенная процедура идентификации) и потребностью „разносить" узлы с одним и тем же значением идентификатора, но сильно разным содержанием.

САДОВНИЧИЙ В.А. — 2011 г.

Статья подготовлена по материалам доклада ректора МГУ имени М.В.Ломоносова, вице-президента РАН, академика В.А.Садовничего на Всероссийском съезде учителей информатики 24 марта 2011 года.