СОДЕРЖАНИЕ

Compressive Sensing

Граничин О.Н. (СПбГУ) Рандомизация измерений и l_1-оптимизация

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

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

Гачков А..(СПбГУ) Рандомизированный алгоритм R/S-анализа финансовых рядов  

Тихомиров А.С.(НовГУ, Великий Новгород) О быстрых вариантах алгоритма отжига (simulated annealing)  

Щербаков П.С. (ИПУ РАН, Москва) Генерирование устойчивых полиномов 

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

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

Пономарева А.Ю., Строилов Р.М., Чирков М.К. (СПбГУ)  Специальные процедуры оптимизации периодически нестационарных стохастических автоматов

Тимонина А.В. (МФТИ (ГУ), Москва)  Модель задачи ранжирования и ее исследование

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

Амелин К.С., Антал Е.И., Васильев В.И, Граничина Н.О. (СПбГУ)  Адаптивное управление автономной группой беспилотных летательных аппаратов

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

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

Электроэнергетика

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

 

 

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

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

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

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

ВЫПУСК 5

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

2009


УДК 519.712 БКК 32.811.7 С82

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ББК 32.811.7

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


Compressive Sensing

Рандомизация измерений и l1-оптимизация

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

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

Oleg_granichin@mail.ru

В последнее время активно развивается новая парадигма кодиро­вания/декодирования многоразрядных сигналов, имеющих “разреженное” (sparse) представление в некотором базисе. В ее основе лежат идея рандо­мизации измерений и ^-оптимизация. В работе описан новый метод “захва­тывания” и представления сжимаемых сигналов значительно меньшим коли­чеством разрядов, чем в традиционном представлении сигналов по Найквисту. В англоязычной литературе этот метод называется “Compressive Sensing” (сжимающим ощущение).

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

 

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

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

А. Т. Вахитов

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

alexander.vakhitov@gmail.com

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

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

 

Рандомизированный алгоритм R/S-анализа финансовых рядов

А. А. Гачков

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

agachkov@mail.ru

В последнее время активно развивается фрактальный подход к оценке рисков на финансовых рынках. В качестве меры риска того или иного финан­сового актива предлагается использовать фрактальную размерность динамики курса актива за определенный период времени. Для того чтобы бо­лее точно оценивать риски присущие этому активу, необходимо использовать более точные и адекватные алгоритмы вычисления фрактальной размерно­сти. На сегодняшний момент для этой цели чаще всего используют алгоритм R/S-анализа, впервые разработанный английским гидрологом Г. Херстом. Этот алгоритм достаточно хорошо работает на входных данных, очищенных от помех. Однако при добавлении в систему помех и отклонений, которые могут появляться, например, в результате воздействия крупных рыночных игроков во время спекулятивной торговли, алгоритм выдает большую по­грешность. В статье предложен алгоритм рандомизированного R/S-анализа, который позволяет более точно оценивать фрактальную размерность в слу­чае систематических помех.

Ключевые слова: R/S-анализ, рандомизация, анализ финансовых данных.

 


О быстрых вариантах алгоритма отжига (simulated annealing)

Тихомиров А. С., к. ф.-м. н.

Новгородский государственный университет, Великий Новгород

Tikhomirov.AS@mail.ru, TikhomirovAlesha@gmail.com

Получены быстрые варианты алгоритма simulated annealing. Показано, что число вычислений невырожденной целевой функции, необходимое для достижения требуемой точности ε решения задачи при аппроксимации “по аргументу”, может медленно (логарифмически) стремиться к бесконечности при стремлении ε к нулю.

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

 


Генерирование устойчивых полиномов

П. С. Щербаков, д. ф.-м. н.

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

sherba@ipu.ru

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

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

 

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

Анализ некоторых методов размещения в памяти очереди с n приоритетами

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

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

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

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

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

 

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

А. Ю. Пономарева, к. ф.-м. н., Р. М. Строилов, М. К. Чирков, д. ф.-м. н.2

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

vakh@star.math.spbu.ru

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

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

 

Модель задачи ранжирования и ее исследование

А. В. Тимонина

МФТИ (ГУ), Москва

timonina.ann@gmail.com

Изучаются системы большой размерности на примере сети Интернет. Ис­следование проводится с целью разработки алгоритма, который позволит наиболее точно находить PageRank web-страницы. В работе построена те­стовая задача, на примере которой демонстрируется наличие существенного расхождения между точным значением “веса” страницы и значением, полу­ченным из алгоритма PageRank.

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

 

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

Адаптивное управление автономной группой беспилотных летательных аппаратов

К. С. Амелин, Е. И. Антал, В. И. Васильев, Н. О. Граничина

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

konstantinamelin@mail.ru, cathrineantal@gmail.com, gnome@bk.ru, ngranichina@mail.ru

В статье рассматривается возможность применения мультиагентной адап­тивной системы для управления группой “Беспилотных летательных аппа-ратов”(БПЛА, Unmanned Aerial Vehicles, UAV). Система основана на авто­номном общении агентов через радиосигнал. Адаптивность позволит группе оперативно принимать эффективные решения по изменению сценария выпол­нения поставленной задачи.

Ключевые слова: мультиагентные системы, адаптивность, беспилот­ные летательные аппараты, автономная группа БПЛА.

 

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

Н. О. Граничина, Д. С. Шалымов

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

(ngranichina, shalydim)@mail.ru

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

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

 

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

Ле Чунг Хьеу

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

vkhhieukien@yahoo.com

В работе рассматриваются две основные проблемы: (i) применение ве­роятностных моделей для распознавания и сегментации вьетнамских слов и фраз; (ii) итеративное построение оптимальной вероятностной модели с по­мощью обучения. На каждой итерации распознаются новые слова и их слоги соединяются друг с другом. Процесс соединения слогов повышает точность статистических функций, которые улучшают способность распознавания но­вых слов. Это обеспечивает сходимость вероятностной модели к оптимальной. Для эксперимента данные были взяты из 250 034 онлайн статей, в которых около 15 000 000 фраз. Точность алгоритма сегментации составляет более 90%. Получившийся вьетнамский словарь содержит более 100 000 слов и сло­восочетаний.

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

 

Электроэнергетика

Итерационный критерий статической устойчивости электроэнергетической системы, заданной в алгебро-дифференциальной форме

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

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

(mms, rvn)@mes-centra.ru

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

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

 


Научное   издание

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

Выпуск 5

Печатается без издательского редактирования

Обложка художника Е. А. Соловьевой

Оригинал–макет О. Н. Граничина

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

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

Усл. печ. л. 15,0. Тираж 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