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

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




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

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

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

АНАЛИЗ И МОДЕЛИРОВАНИЕ РАСПРЕДЕЛЕНИЙ В ЭРЕДИТАРНЫХ СТОХАСТИЧЕСКИХ СИСТЕМАХ.

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

Аннотация: Рассматриваются методы и алгоритмы анализа и моделирования (аналитического, статистического) одно- и многомерных распределений в эредитарных стохастических системах (ЭСтС) с винеровскими и пуассоновскими шумами. Приводятся нелинейные стохастические интегродифференциальные уравнения. Для затухающих физически возможных эредитарных ядер рассматриваются два способа их аппроксимации (на основе линейных операторных уравнений и вырожденных ядер). Устанавливаются алгоритмы приведения ЭСтС к дифференциальным стохастическим системам (ДСтС). Приводится подробный анализ подходов к аналитическому и статистическому моделированию распределений в ЭСтС, приводимых кДСтС.Воснову подходов положеныкакметодыпрямого численного интегрирования уравнений ДСтС, так и численного интегрирования для параметров ортогонального разложения плотностей (моментов, коэффициентов ортогонального разложения и др.). Подробно рассматриваются алгоритмы аналитического и статистического моделирования, основанные на методе статистической линеаризации (МСЛ) и методе нормальной аппроксимации (МНА). Получены условия устойчивости алгоритмов на основеМСЛ иМНА. Для задачМСЛ рассматриваются прямые одношаговые сильные методы и алгоритмы численного интегрирования (различной точности) для гладких и разрывных правых частей уравнений ЭСтС. Разработан комплекс тестовых примеров для разрабатываемого в ИПИ РАН инструментального программного обеспечения “IDStS” в среде MATLAB. Подробно рассмотрены задачи анализа и моделирования колебаний осциллятора Дуффинга и релейного осциллятора в эредитарной стохастической среде.

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

АНАЛИЗ ЗАДЕРЖЕК ПРИ ДИСПЕТЧЕРИЗАЦИИ ОДНОРОДНЫХ ЗАДАНИЙ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ.

  • Ю.Е. Малашенко  Вычислительный центр им. А.А. Дородницына Российской академии наук, malash09@ccas.ru
  • И.А. Назарова  Вычислительный центр им. А.А. Дородницына Российской академии наук, irina-nazar@yandex.ru

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

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

ОЦЕНКА НАДЕЖНОСТИ СЛОЖНЫХ СИСТЕМ С ВОССТАНОВЛЕНИЕМ ПО РЕЗУЛЬТАТАМ ИСПЫТАНИЙ ЭЛЕМЕНТОВ.

  • И.В. Павлов  Московский государственный технический университет им. Н.Э. Баумана, ipavlov@bmstu.ru

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

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

ИСПОЛЬЗОВАНИЕ ПРИНЦИПА РАВНОВЕСИЯ ДЛЯ УПРАВЛЕНИЯ МАРШРУТИЗАЦИЕЙ В ТРАНСПОРТНЫХ СЕТЯХ.

  • Н.С. Васильев  Московский государственный технический университет им. Н.Э. Баумана, nik8519@yandex.ru

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

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

АСИМПТОТИЧЕСКИЕ СВОЙСТВА ОЦЕНКИ РИСКА ПРИ ПОРОГОВОЙ ОБРАБОТКЕ ВЕЙВЛЕТ-КОЭФФИЦИЕНТОВ В МОДЕЛИ С КОРРЕЛИРОВАННЫМ ШУМОМ.

  • А.А. Ерошенко  Московский государственный университет им. М.В. Ломоносова, кафедра математической статистики факультета вычисли- тельной математики и кибернетики, aeroshik@gmail.com
  • О.В. Шестаков  Московский государственный университет им. М.В. Ломоносова, кафедра математической статистики факультета вычисли- тельной математики и кибернетики; Институт проблем информатики Российской академии наук, oshestakov@cs.msu.su

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

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

БАЗИС РЕАЛИЗАЦИИ СУПЕР-ЭВМ ЭКСАФЛОПСНОГО КЛАССА.

  • И.А. Соколов  Институт проблем информатики Российской академии наук, ISokolov@ipiran.ru
  • Ю.А. Степченков  Институт проблем информатики Российской академии наук, YStepchenkov@ipiran.ru
  • С.Г. Бобков  Научно-исследовательский институт системных исследований Российской академии наук, bobkov@cs.niisi.ras.ru
  • В.Н. Захаров  Институт проблем информатики Российской академии наук, VZakharov@ipiran.ru
  • Ю.Г. Дьяченко  Институт проблем информатики Российской академии наук, diaura@mail.ru
  • Ю.В. Рождественский  Институт проблем информатики Российской академии наук, YRogdest@ipiran.ru
  • А.В. Сурков   Научно-исследовательский институт системных исследований Российской академии наук, surkov@cs.niisi.ras.ru

Аннотация: Статья посвящена выбору схемотехнического базиса реализации микропроцессоров и коммуникационных сред супер-ЭВМэксафлопсного класса. Проведен сравнительный анализ характеристик цифровых устройств различной сложности, реализованных в синхронном (С) и самосинхронном (СС, self-timed) базисе. Подтверждены основные преимущества СС-схем по сравнениюс синхронными аналогами: отсутствие гонок, максимально возможный диапазон работоспособности, высокое быстродействие, относительно низкая мощность потребления. В результате перехода от синхронной к квазисамосинхронной и самосинхронной реализации зона работоспособности устройства расширяется независимо от его сложности. В наибольшей степени эти преимущества проявляются при использовании СС-схем для проектирования надежной цифровой аппаратуры. Рассмотрены различныеметодологии проектирования СС-схем. Проведен сравнительный анализ реализации СС-схем в обобщенном базисе схем, нечувствительных к задержкам, развиваемом авторами, и в базисе NCL (NULL Convention Logic) схем. Показано, что предлагаемый базис обеспечивает получение схем с лучшими параметрами по быстродействию, аппаратнымзатратами энергопотреблениюпри проектировании типовых цифровых устройств, составляющих основу для построения современных вычислительных систем и комплексов.

Ключевые слова:  синхронные схемы; самосинхронные схемы; нечувствительность к задержкам; NULL Convention Logic; быстродействие; энергопотребление; отказоустойчивость

ИНФОРМАЦИОННАЯ МОДЕЛЬ ТЕХНОЛОГИИ ПРЕДСТАВЛЕНИЯ НАТУРНОГО ОБЪЕКТА И ИЗМЕНЕНИЯ ЕГО ПРОСТРАНСТВЕННОГО ПОЛОЖЕНИЯ.

  • О.П. Архипов  Орловский филиал Института проблем информатики Российской академии наук, arkhipov12@yandex.ru
  • Ю.А. Маньяков  Орловский филиал Института проблем информатики Российской академии наук, maniakov_yuri@mail.ru
  • Д.О. Сиротинин  Орловский филиал Института проблем информатики Российской академии наук, vespert@mail.ru

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

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

ДИНАМИЧЕСКИЕ КОНТЕКСТЫ БАЗЫ ДАННЫХ РЕЛЯЦИОННОГО ТИПА.

  • С.В. Зыкин  Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, szykin@mail.ru

Аннотация: Предложена технология динамического формирования представления данных. Эта технология является развитием методов аналитической обработки данных (OLAP — online analytical processing). Источником данных служит реляционная база данных (БД) с произвольной схемой (не обязательно иерархической). Целевое представление данных — композиционная таблица, которая позволяет представлять многомерные данные на плоскости. Эта таблица предполагает раздельное формирование размерностей с последующим сопоставлением мер размерностям в таблице. Основой промежуточных представлений данных является таблица связанных соединений, удовлетворяющая контекстными логическим ограничениям. Предложены алгоритмы формирования таких таблиц и исследованыих свойства. Особое внимание уделено рассмотрению контекстов, используемых при формировании таблиц связанных соединений. Для создания контекстов предложен алгоритм направленного перебора и на примере выполнен сравнительный анализ работы алгоритмов формирования контекстов. Исследованные свойства контекстов и предложенные алгоритмы предназначены для автоматизации работы пользователя при формировании новых представлений данных.

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

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

  • Е.Б. Козеренко  Институт проблем информатики Российской академии наук, kozerenko@mail.ru

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

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

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

  • В.А. Маренко  Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, marenko@ofim.oscsbras.ru
  • О.Н. Лучко  Омский государственный институт сервиса, o luchko@rambler.ru
  • О.С. Лупенцов   Омский государственный институт сервиса, lupentsov@mail.ru

Аннотация: Приведена когнитивная карта «Процесс обучения» в виде ориентированного графа. На дуги ориентированного графа нанесены согласованные экспертные оценки. Объекты на когнитивной карте делятся на целевой фактор и управляющие факторы. Целевым фактором является качество обучения. Управляющие факторы используются для корректировки образовательного процесса. Приведена информация, которая используется при построении модели управляющего фактора «когнитивная готовность студента». Формализация экспериментальных данных осуществлена с применением метода семантического дифференциала и аппарата нечетких множеств. Приведена когнитивная модель образовательного процесса в виде функционального ориентированного графа. Показаны результаты имитационного эксперимента «управление образовательным процессом». Показано, что при увеличении управляющего фактора «уровень стабильности внешней среды» увеличивается и целевой фактор «качество обучения».

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

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

  • А.И. Зейфман  Вологодский государственный университет; Институт проблем информатики Российской академии наук, Институт социально-экономического развития территорий Российской академии наук, a_zeifman@mail.ru
  • В.Ю. Королев  Факультет вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова; Институт проблем информатики Российской академии наук, vkorolev@cs.msu.su
  • А.В. Коротышева  Вологодский государственный университет, a_korotysheva@mail.ru
  • С.Я. Шоргин  Институт проблем информатики Российской академии наук, SShorgin@ipiran.ru

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

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

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

  • В.И. Киреев  Московский государственный горный университет, Vladimir-Kireyev@mail.ru
  • М.М. Гершкович  Институт проблем информатики Российской академии наук, makmg@mail.ru
  • Т.К. Бирюкова   Институт проблем информатики Российской академии наук, yukonta@mail.ru

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

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

STABILITY ANALYSIS OF AN OPTICAL SYSTEM WITH RANDOM DELAY LINES LENGTHS.

  • E. Morozov  Institute of Applied Mathematical Research, Karelian Research Center, Russian Academy of Sciences, 11 Pushkinskaya Str., Petrozavodsk 185910, Russian Federation
  • L. Potakhina  Petrozavodsk State University, 33 Lenin Str., Petrozavodsk 185910, Russian Federation
  • K. De Turck   Ghent University, TELIN Department, 41 Sint-Pietersnieuwstraat,Gent B-9000, Belgium
АНАЛИЗ УСТОЙЧИВОСТИ СИСТЕМЫ ПЕРЕДАЧИ ДАННЫХ С ОПТИЧЕСКИМИ ЛИНИЯМИ ЗАДЕРЖКИ СЛУЧАЙНОЙ ДЛИНЫ.
  • Е.В.Морозов  Институт прикладных математических исследований КарНЦ РАН, Россия, Республика Карелия, г. Петрозаводск 185910, ул. Пушкинская 11; Петрозаводский государственный университет, Россия, Республика Карелия, г. Петрозаводск 185910, пр. Ленина 33; emorozov@karelia.ru
  • Л.В. Потахина  Институт прикладных математических исследований КарНЦ РАН, Россия, Республика Карелия, г. Петрозаводск 185910, ул. Пушкинская 11; Петрозаводский государственный университет, Россия, Республика Карелия, г. Петрозаводск 185910, пр. Ленина 33; lpotahina@gmail.com
  • К. Де Турк  Университет Гента, Sint-Pietersnieuwstraat 41, Гент B-9000, Бельгия; kdeturck@telin.ugent.be

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

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