Институт проблем информатики Российской Академии наук
Институт проблем информатики Российской Академии наук
Российская Академия наук

Институт проблем информатики Российской Академии наук




«Информатика и ее применения» (Том 11, Выпуск 1, 2017)

Оглавление | Библиография | Об авторах

Аннотации и ключевые слова.

АНАЛИТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ШИРОКОПОЛОСНЫХ ПРОЦЕССОВ В СТОХАСТИЧЕСКИХ СИСТЕМАХ, НЕ РАЗРЕШЕННЫХ ОТНОСИТЕЛЬНО ПРОИЗВОДНЫХ

  • И. Н. Синицын   Институт проблем информатики Федерального исследовательского центра "Информатика и управление" Российской академии наук, sinitsin@dol.ru

Аннотация: Рассматриваются конечномерные нелинейные стационарные и нестационарные стохастические системы (СтС), не разрешенные относительно производных в условияхширокополосных гауссовских и негауссовских возмущений. Такие СтС описывают поведение многих технических систем информатики и управления. Для аналитического моделирования и оценки чувствительности к параметрам нормальных (гауссовских) нестационарных и стационарных стохастических процессов (СтП) в таких СтС разработаны два метода аналитического моделирования (МАМ) на основе метода статистической линеаризации (МСЛ) и метода нормальной аппроксимации (МНА). Приведены типовые нелинейности, неразрешенные относительно производных, а также два тестовых примера. Алгоритмы положены в основу разрабатываемого инструментального программного обеспечения для решения задач надежности и безопасности технических систем.

Ключевые слова: аналитическое моделирование; метод нормальной аппроксимации (МНА); метод статистической линеаризации (МСЛ); нормальный (гауссовский) стохастических процесс (СтП); стохастическая система, не разрешенная относительно производных; чувствительность к параметрам

КЛАССИФИКАЦИЯ ПО НЕПРЕРЫВНЫМ НАБЛЮДЕНИЯМ С МУЛЬТИПЛИКАТИВНЫМИ ШУМАМИ I: ФОРМУЛЫ БАЙЕСОВСКОЙ ОЦЕНКИ

  • А. В. Борисов   Институт проблем информатики Федерального исследовательского центра "Информатика и управление" Российской академии наук, aborisov@frccsc.ru

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

Ключевые слова: байесовская оценка; оптимальная фильтрация; стохастическая дифференциальная система; случайный скачкообразный процесс; мультипликативные шумы

ОБРАТИМОЕ СЖАТИЕ ДАННЫХ ПОСРЕДСТВОМ УНИВЕРСАЛЬНОГО АРИФМЕТИЧЕСКОГО КОДИРОВАНИЯ

  • А. И. Стефанович   Институт проблем информатики Федерального исследовательского центра "Информатика и управление" Российской академии наук, astefanovich@ipiran.ru
  • Д. В. Сушко   Институт проблем информатики Федерального исследовательского центра "Информатика и управление" Российской академии наук, dsushko@ipiran.ru

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

Ключевые слова: обратимое сжатие данных; сжатие без потерь; универсальное кодирование; арифметическое кодирование; компьютерная томограмма

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

  • С. Л. Френкель   Институт проблем информатики Федерального исследовательского центра "Информатика и управление" Российской академии наук, fsergei51@gmail.com
  • В. Н. Захаров   Федеральный исследовательский центр "Информатика и управление" Российской академии наук, VZakharov@ipiran.ru
  • Б. М. Басок   Московский технологический университет (МИРЭА), VM_E@mail.ru

Аннотация: Показана возможность использования двумерной марковской модели поведения конечного автомата при сбое на одном такте, предложенной ранее для вероятностной верификации аппаратных систем, для оценки устойчивости программ, представленных блок-схемами реализуемых алгоритмов, к кратковременным сбоям. Модель представляет собой произведение цепей Маркова (ЦМ), соответствующих конечно-автоматной модели программы, работающей в нормальных условиях, и автомата, в котором в некоторый момент времени произошел кратковременный (например, в пределах времени выполнения одной операции или одного машинного цикла) сбой. Устойчивость к сбоям оценивается вероятностью возвращения автомата после прекращения действия помехи на траекторию переходов исходного автомата. При этом считается, что изменения траектории при сбое в низкоуровневой (instruction- by-instruction) модели программы будут существенными только в том случае, если они соответствуют изменению ветвления в указанной блок-схеме. Модель подробно анализируется на примере конкретной блок-схемы программы.

Ключевые слова: самовосстановление программ; сбои; марковские модели; тестирование

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

  • А. К. Горшенин   Институт проблем информатики Федерального исследовательского центра "Информатика и управление" Российской академии наук, agorshenin@frccsc.ru

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

Ключевые слова: информационные системы; смешанные вероятностные модели; метод скользящего разделения смесей; статистический анализ данных; экстремальные наблюдения; зашумленные данные; пороговое значение; метод Peak Over Threshold; теорема Пикандса - Балкемы - Де Хаана; теорема Реньи; онлайн-комплекс; матричные вычисления

МНОГОУРОВНЕВЫЕ МОДЕЛИ РЕШЕНИЯ МНОГОКЛАССОВЫХ ЗАДАЧ РАСПОЗНАВАНИЯ

  • А. A. Докукин   Федеральный исследовательский центр "Информатика и управление" Российской академии наук, dalex@ccas.ru
  • В. В. Рязанов  Московский физико-технический институт (государственный университет), vasyarv@mail.ru
  • О. В. Шут   Белорусский государственный университет, olgashut@tut.by

Аннотация: Проблема поиска набора бинарных подзадач для многоклассовых задач распознавания рассмотрена с точки зрения алгебраического и логического подходов к распознаванию. При этом теоретически исследованы границы применимости указанных подходов. Так, рассмотрена связь корректности алгоритмов первого и второго уровня, получено достаточное условие. Кроме того, показана правомерность использования метода объектных резолюций для построения новых объектов на основе информации, заданной прецедентным способом. В качестве прикладных результатов предлагаются две модификации метода ECOC (error-correcting output codes - коды, исправляющие ошибки). Первая заключается в оптимизации набора бинарных подзадач с учетом качества решающих их алгоритмов. Вторая представляет собой развитие метода нечеткой объектной резолюции, где в качестве кодового описания класса используется мультимножество кодов обучающих объектов. Предложенные модификации позволяют в различных условиях улучшать качество исходного метода, что продемонстрировано с помощью модельных и прикладных задач.

Ключевые слова: распознавание; многоклассовая задача; ECOC; многоуровневый метод; корректность; алгебраический подход; логический подход; кодовое описание класса

АЛГОРИТМ ПРЕОБРАЗОВАНИЯ ОДНОГО ГРАФА В ДРУГОЙ С МИНИМАЛЬНОЙ ЦЕНОЙ

  • К. Ю. Горбунов  Институт проблем передачи информации им. А. А. Харкевича Российской академии наук, gorbunov@iitp.ru
  • В. А. Любецкий   Институт проблем передачи информации им. А. А. Харкевича Российской академии наук; механико-математический факультет Московского государственного университета им. М. В. Ломоносова, lyubetsk@iitp.ru

Аннотация: Рассматриваются ориентированные графы, состоящие из любого числа дизъюнктных цепей и циклов, ребрам графов приписаны без повторений их имена - натуральные числа. Фиксирован список операций, каждая из которых по-своему преобразует один граф в другой, ей приписано число - цена данной операции. Нужно найти минимальную по суммарной цене последовательность операций, которая для двух данных графов преобразует один в другой. Эта задача самым широким образом применяется в прикладных вопросах. По-видимому, она является NP-трудной и поэтому может быть эффективно решена только при том или ином условии на цены или при некотором ограничении на графы. Ее решение при достаточно широких условиях получено в виде линейных по времени и памяти алгоритмов, для которых доказана точность (неэвристичность), т. е. доказано, что они всегда находят минимальную по цене последовательность операций. Задача давно решается многими эвристическими алгоритмами, которые тестировались на разных данных, но предлагаемые авторами решения - первые среди точных.

Ключевые слова: ориентированный граф из цепей и циклов; преобразование графов с минимальной ценой; точное линейное решение; условие на графы; условие на цены; условно кратчайшее решение

ИНДИВИДУАЛИЗАЦИЯ ПРОЦЕССА ОБУЧЕНИЯ В РЕЖИМЕ ВЕБ-КОНФЕРЕНЦИИ НА ОСНОВЕ ИЕРАРХИЧЕСКОЙ НЕЧЕТКОЙ ЭКСПЕРТНОЙ СИСТЕМЫ

  • А. С. Алексейчук   Московский авиационный институт (национальный исследовательский университет), alexejchuk@gmail.com
  • А. В. Пантелеев   Московский авиационный институт (национальный исследовательский университет), avpanteleev@inbox.ru

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

Ключевые слова: дистанционное обучение; веб-конференция; экспертная система; иерархический нечеткий вывод

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

  • Анна А. Зализняк  Институт языкознания Российской академии наук; Институт проблем информатики Федерального исследовательского центра "Информатика и управление" Российской академии наук, anna.zalizniak@gmail.com
  • И. М. Зацман   Институт проблем информатики Федерального исследовательского центра "Информатика и управление" Российской академии наук, izatsman@yandex.ru
  • О. Ю. Инькова  Женевскийуниверситет, Olga.Inkova@unige.ch

Аннотация: Рассматривается задача контрастивного исследования коннекторов русского языка с помощью надкорпусной базы данных (НБД), которая представляет собой новую категорию информационных лингвистических ресурсов. Надкорпусная база данных содержит параллельные выровненные тексты, в которых одному или нескольким предложениям поставлены в соответствие одно или несколько предложений их перевода. Первая характерная черта НБД заключается в возможности аннотирования исследуемых языковых единиц (ЯЕ), в данном случае коннекторов. Вторая состоит в том, что решение задачи аннотирования привело к появлению широкого спектра новых сущностей и понятий как в информатике, так и в лингвистике. Для их описания предлагается система терминов, носящая междисциплинарный характер. С одной стороны, эти термины используются лингвистами для представления новых фундаментальных знаний, полученных ими в процессе контрастивного исследования коннекторов русского языка. С другой стороны, они применяются при разработке архитектуры и функциональных подсистем НБД, а также для разработки информационного, лингвистического и программного видов обеспечения. Кроме того, эта система терминов необходима для сопоставления полученных результатов с имеющимися отечественными и зарубежными аналогами.

Ключевые слова: надкорпусная база данных; система терминов; аннотирование коннекторов; параллельные тексты; корпусная лингвистика; хронотипическая фасетная классификация

ON UNIQUENESS OF CLEARING VECTORS REDUCING THE SYSTEMIC RISK

  • Kh. El Bitar   Laboratoire de Mathematiques, Universite de Franche-Comte, 16 Route de Gray, 25030 Besancon, CEDEX, France, khalilbitar _aw@hotmail.com
  • Yu. Kabanov  Laboratoire de Mathematiques, Universite de Franche-Comte, 16 Route de Gray, 25030 Besancon, CEDEX, France; Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation; National Research University "MPEI," 14 Krasnokazarmennaya Str., Moscow, 111250, Russian Federation, Youri.Kabanov@univ-fcomte.fr
  • R. Mokbel   Laboratoire de Mathematiques, Universite de Franche-Comte, 16 Route de Gray, 25030 Besancon, CEDEX, France, ritamokbel@hotmail.com

О ЕДИНСТВЕННОСТИ КЛИРИНГОВЫХ ВЕКТОРОВ, РЕДУЦИРУЮЩИХ СИСТЕМНЫЙ РИСК

  • Х. Эль Битар  Лаборатория математики Университета Франш-Конте, г. Безансон, Франция
  • Ю. Кабанов  Лаборатория математики Университета Франш-Конте, г. Безансон, Франция, Институт проблем информатики Федерального исследовательского центра "Информатика и управление" Российской академии наук, Российский университет дружбы народов, Национальный исследовательский университет "МЭИ"
  • Р. Мокбель  Лаборатория математики Университета Франш-Конте, г. Безансон, Франция

Аннотация: В финансовых системах, т. е. в сети взаимосвязанных банков, процедура взаимозачета, или клиринга, состоит в одновременной выплате задолженностей с целью уменьшения общей их суммы в системе. Вектор, компоненты которого есть суммарные выплаты каждого банка системы, называется клиринговым вектором. В простых моделях, предложенных Айзенбергом и Ноэ (2001) и независимо Судзуки (2002) было показано, что полный клиринг описывается вектором, который является неподвижной точкой некоторого отображения. Существование клирингового вектора может быть получено прямой ссылкой на теоремы о неподвижной точке Кнастера-Тарскoго или Брауэра. Вопрос о его единственности является более деликатным. Айзенберг и Ноэ получили достаточное условие единственности в терминах графа связей финансовой системы. В настоящей работе доказывается единственность для двух более общих моделей: модели Эльсингера с приоритетами долгов и модели типа Амини-Филиповича-Минки, в которой банки имеют неликвидные активы, продажа которых влияет на их рыночную цену

Ключевые слова: системный риск; финансовые сети; клиринг; теорема Кнастера-Тарского; модель Айзенберга-Ноэ; приоритет финансовых обязательств; влияние на ценообразование

INFORMATICS AND ITS ROLE FOR THE STUDY OF GENESIS AND PROPERTIES OF COMPLEX NATURAL SYSTEMS

  • R. B. Seyful-Mulyukov   Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation, rust@ipiran.ru

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

  • Р. Б. Сейфуль-Мулюков   Институт проблем информатики Федерального исследовательского центра "Информатика и управление" Российской академии наук, rust@ipiran.ru

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

Ключевые слова: информатика; информатизация; природные сложные системы; образование нефти; поиски нефти; статическая неопределенность; динамическая неопределенность