СОДЕРЖАНИЕ

Стохастические системы

Поляк Б.Т., Щербаков П.С. (ИПУ РАН, Москва) Mножества достижимости и притяжения линейных систем с ограниченным управлением: описание с помощью инвариантных эллипсоидов

Понятский В.М. (ГУП «КБП», Тула) Исследование динамического объекта с ограничениями по выходным координатам c использованием метода инвариантного погружения

Рандомизированные алгоритмы

Вахитов А.Т.,Гуревич Л.C. (СПбГУ) Псевдоградиентный метод с возмущением на входе для нестационарной задачи безусловной оптимизации

Мисриханов~М.~Ш., Рябченко~В.~Н. (МЭСЦ, Mосква) Рандомизированные алгоритмы вычисления инвариантных нулей больших динамических систем

Системы массового обслуживания

Аксенова Е.А., Соколов А.В. (ИПМИ КарНЦ РАН, Петрозаводск) Анализ некоторых методов реализации приоритетной очереди

Драц А.В., Соколов А.В. (ИПМИ КарНЦ РАН, Петрозаводск) Оптимальное размещение в памяти одного уровня n стеков и/или очередей

Кривулин Н.К. (СПбГУ)  Вычисление показателя Ляпунова в стохастических динамических моделях систем с очередями

Мосягина Е.Н., Чирков М.К. (СПбГУ)  Оптимальное управление системой взаимосвязанных периодически нестационарных стохастических автоматов в нечетко заданных условиях

Обучение и адаптация

Вахитов А.Т.(СПбГУ)  Адаптивное оценивание параметров в параллельных многопользовательских вычислительных системах

Вахитов А.Т.,Гуревич Л.C., Павленко Д.В.  (СПбГУ)  Обзор алгоритмов стереозрения

Ле Ч.Х. (СПбГУ), Ле А.В. (ELTEU, Венгрия), Ле Ч.К. (ГуэУ, Вьетнам) Автоматическое выделение слов и словосочетаний из вьетнамских печатных текстов

Паньшенсков М.А.. (СПбГУ) Адаптивный метод управления потоком решения изолированных заданий в параллельной вычислительной среде

Понятский В.М. (ГУП «КБП», Тула) Исследование способов реализации адаптивной системы управления с фильтром Калмана

Халидов В., Forbes F., Hansard M., Arnaud E., Horaud R. (Inria, Grenoble, France) Обнаружение и локализация объектов в пространстве посредством самообучающейся модели кластеризации

Шалымов Д.C.(СПбГУ)  Алгоритмы устойчивой кластеризации на основе индексных функций и функций устойчивости

Информационные системы

Граничин О.Н. (СПбГУ), Граничина О.А.(РГПУ) Создание информационной системы контроля качества образовательного процесса в вузе

 

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

НИИ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

СТОХАСТИЧЕСКАЯ ОПТИМИЗАЦИЯ В ИНФОРМАТИКЕ

Издается с 2005 года

ВЫПУСК 4

Издательство С.-Петербургского  университета

2008


УДК 519.712 БКК 32.811.7 С82

Ответственный редактор д. ф.-м. н., проф. О.Н. Граничин

Редакционная коллегия: Н. К. Кривулин (С.-Петерб. гос. ун-т),

Г. А. Леонов (С.-Петерб. гос. ун-т),

Б. Т. Поляк (ИПУ РАН),

А. В. Соколов  (ИПМИ КарНЦ РАН),

А. Н. Терехов (С.-Петерб. гос. ун-т),

M. К. Чирков (С.-Петерб. гос. ун-т),

П. С. Щербаков (ИПУ РАН)

Печатается по постановлению

Редакционно-издательского совета

математико-механического факультета

С.-Петербургского государственного университета

С82                Стохастическая     оптимизация     в     информатике.

Вып. 4 /    Под ред. О. Н. Граничина   -    СПб.:    Издательство С.-Петербургского  университета 2008. - 299с. ISSN 1992-2922

Издание выпускается ежегодно (вып. 1, ненумерованный, вышел в 2005 г., вып. 2, 3 — в 2006-07 гг.) и содержит научные работы по сто­хастической оптимизации, особо выделяя приложения в информатике. 4-й выпуск составлен в основном по материалам одноименной регулярной серии семинаров для студентов, аспирантов и научных работников, про­водившихся в 2008 г. на математико-механическом факультете С.-Петер­бургского университета под руководством профессора кафедры систем­ного программирования О. Н. Граничина и организованных совместно с Лабораторией системного программирования и информационных техноло­гий (СПРИНТ) СПбГУ, которая была создана при поддержке корпорации Intel.

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

ББК 32.811.7

©   Авторы статей, 2008


Стохастические системы

Множества достижимости и притяжения линейных систем с ограниченным управлением: описание с помощью инвариантных эллипсоидов

Б. Т. Поляк, д. т. н., П. С. Щербаков, д. ф.-м. н.

Институт проблем управления РАН, Москва

boris@ipu.ru sherba@ipu.ru

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

Ключевые слова: множество притяжения, инвариантный эллипсоид, линей­ные матричные неравенства, абсолютная устойчивость.

 

 

Исследование динамического объекта с ограничениями по выходным координатам c использованием метода инвариантного погружения

В. М. Понятский, к. т. н.

ГУП “Конструкторское бюро приборостроения”, Тула

kbkedr@tula.net, pwmru@rambler.ru

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

Ключевые слова: идентификация, динамический объект, оценка, параметры, ограничения.

 

 

Рандомизированные алгоритмы

 

Псевдоградиентный метод с возмущением на входе для нестационарной задачи безусловной оптимизации

А. Т. Вахитов, Л. С. Гуревич

Санкт-Петербургский государственный университет

av38@yandex.ru, gurevich.lev@gmail.com

Рассматривается применение метода стохастической оптимизации с проб­ным одновременным возмущением с двумя измерениями в задаче оптими­зации нестационарного функционала без ограничений связи на вход. Уста­новлена верхняя среднеквадратическая граница невязки при условиях один дифференцируемости функционала и почти произвольных помех.

Ключевые слова: стохастическая оптимизация, рандомизация, нестационар­ность, оптимизация, псевдоградиентный метод.

 

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

М. Ш. Мисриханов, д. т. н., В. Н. Рябченко, д. т. н.

Магистральные Электрические Сети Центра, Mосква

mms@mes-centra.ru  rvn@mes-centra.ru

Описывается алгоритм решения задачи определения инвариантных ну­лей большой динамической системы с многими входами и многими выходами (MIMO). Задача определения инвариантных нулей путем рандомизированно­го квадрирования исходной MIMO-системы сводится к стандартной задаче на собственные значения числовых матриц. Практические приложения лежат в области больших электроэнергетических систем.

Ключевые слова: MIMO-система, инвариантные нули, квадрирование систе­мы, задача на собственные значения, большая электроэнергетическая систе­ма.

 

 

Системы массового обслуживания

Анализ некоторых методов реализации приоритетной очереди

Е. А. Аксенова, канд. ф.-м. н., А. В. Соколов, д. ф.-м. н.

ИПМИ КарНЦ РАН, Петрозаводск

aksenova@krc.karelia.ru  avs@krc.karelia.ru

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

Ключевые слова: приоритетная очередь, случайные блуждания, цепи Мар­кова.

 

Оптимальное размещение в памяти одного уровня n стеков и/или очередей

А. В. Драц, А. В. Соколов, д. ф.-м. н.

Петрозаводский универ-т, ИПМИ КарНЦ РАН, Петрозаводск

adeon88@mail.ru, avs@krc.karelia.ru

В работе рассмотрена проблема размещения n стеков и/или очередей в памяти одного уровня размера m для последовательного и связного спосо­бов представления. Предложены алгоритмы нумерации состояний и алгорит­мы построения соответствующих поглощающих цепей Маркова и вычисления среднего времени до переполнения памяти для связного представления и на­хождения оптимального (с точки зрения максимизации среднего времени до переполнения памяти) разбиения памяти для последовательных представле­ний. Приводятся результаты численных экспериментов.

Ключевые слова: LIFO-cтеки, FIFO-очереди, связанные списки, цепи Марко­ва, динамические структуры данных.

 

Вычисление показателя Ляпунова в стохастических динамических моделях систем с очередями

Н. К. Кривулин, к. ф.-м. н.

Санкт-Петербургский государственный университет

Nikolai@NK1200.spb.edu

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

Ключевые слова: стохастические динамические системы, показатель Ляпу­нова, идемпотентная алгебра, системы с очередями, среднее время цикла об­служивания.

 

Оптимальное управление системой взаимосвязанных периодически нестационарных стохастических автоматов в нечетко заданных условиях

Е. Н. Мосягина, М. К. Чирков, д. ф.-м. н.

Санкт-Петербургский государственный университет

vakh@star.math.spbu.ru

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

Ключевые слова: периодически нестационарный стохастический автомат, си­стема автоматов, «нечеткая» среда, нечеткие условия, оптимальная страте­гия.

 

 

Обучение и адаптация

Адаптивное оценивание параметров в параллельных многопользовательских параллельных вычислительных системах

А. Т. Вахитов

Санкт-Петербургский государственный университет

av38@yandex.ru

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

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

 

Обзор алгоритмов стереозрения

А. Т. Вахитов, Л. С. Гуревич, Д. В. Павленко

Санкт-Петербургский государственный университет

av38@yandex.ru, gurevich.lev@gmail.com, dmit10@gmail.com

Задача стереозрения состоит в использовании двух или нескольких камер для получения данных о дальности до объекта. При этом входные данные мо­гут представлять собой как просто отдельные изображения, так и видеоряд. Мы приводим обзор алгоритмов, связанных с частным случаем — сопостав­лением двух изображений.

Ключевые слова: стереозрение.

 

Автоматическое выделение слов и словосочетаний из вьетнамских печатных текстов

Ле Чунг Хьеу Санкт-Петербургский гос. университет

Ле Ань Ву Университет ELTE, Бyдaпeшт, Венгрия

Ле Чунг Кьен Гуэ Университет, Вьетнам

 vkhhieukien@yahoo.com, leanhvu@inf.elte.hu, hieukien@hotmail.com

В работе рассматриваются способы применения методов статистической обработки для построения списка вьетнамских слов и словосочетаний. На основе полученных результатов могут быть подготовлены входные данные для автоматической обработки текстов (Natural Language Processing) на есте­ственном вьетнамском языке.

Ключевые слова: распознавание слов и словосочетаний на вьетнамском язы­ке, методы статистической обработки, адаптация.

 

Адаптивный метод управления потоком решения изолированных заданий в параллельной вычислительной среде

М. А. Паньшенсков

Санкт-Петербургский государственный университет

mpansh@gmail.com

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

 

Ключевые слова: распределенные вычисления, распределение заданий, адап­тивные методы, коммуникация.

 

Исследование способов реализации адаптивной системы управления с фильтром Калмана

В. М. Понятский, к. т. н.

ГУП “Конструкторское бюро приборостроения”, Тула

kbkedr@tula.net, pwmru@rambler.ru

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

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

 

Обнаружение и локализация объектов в пространстве посредством самообучающейся модели кластеризации

В. Халидов, F. Forbes, M. Hansard, E. Arnaud, R. Horaud

Inria, Grenoble, France

vkhalidov@yahoo.com

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

Ключевые слова: обнаружение и локализация объектов, аудио и видео сен­соры, самообучение, кластеризация.

 

Алгоритмы устойчивой кластеризации на основе индексных функций и функций устойчивости

Д. С. Шалымов

Санкт-Петербургский государственный университет

shalydim@mail.ru

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

Ключевые слова: кластеризация, устойчивость кластеризации.

 

 

Информационные системы

 

Создание информационной системы контроля качества образовательного процесса в вузе

О. Н. Граничин, д. ф.-м. н., О. А. Граничина, к. ф.-м. н.

Санкт-Петербургский государственный университет

Российский гос. педагогический университет им. А. И. Герцена

Oleg_granichin@mail.ru  Olga_granichina@mail.ru

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

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

 

 

 


Подписано в печать 20.11.08. Формат 60 × 84/16.

Бумага офсетная. Печать офсетная

Усл. печ. л. 18,68. Тираж 100 экз.

Заказ №

Издательство СПбГУ. 199004, С.-Петербург, В.О., 6-я линия, 11/21

Тел. (812) 328–96–17; факс (812) 328–44–22

E-mail: editor@unipress.ru

www.unipress.ru

По вопросам реализации обращаться по адресу:

С.-Петербург, В.О., 6-я линия, д. 11/21, к. 21

Телефоны: 328–77–63, 325–31–76

E-mail: post@unipress.ru

Типография Издательства СПбГУ 199061, С.-Петербург, Средний пр., 41