Рандомизированные алгоритмы
Стохастическая
оптимизация и системное программирование
О. Н. Граничин, д. ф.-м. н.
Санкт-Петербургский государственный университет
Один из возможных способов дословного перевода термина "системное программирование" с английского языка — организация работы системы. Особые теоретические трудности возникают при исследовании сложных систем. Во многих практических задачах механических перенос на сложные системы естественных подходов, работоспособных для простых, приводит к неразрешимым противоречиям. В частности, возникает огромное число, так называемых, неразрешимых задач (за реальное время).
В последнее время все чаще используются новые "рандомизированные" подходы к решению задач организации работы сложных систем, которые дают удовлетворительные ответы с высокой степенью вероятности. В этой статье будет рассказано о некоторых новых результатах в этой области, полученных в последние годы студентами и аспирантами кафедры системного программирования математико-механического факультета СПбГУ.
Ключевые слова: рандомизированные алгоритмы, метод Монте-Карло, оптимизация и оценивание, распознавание образов, устойчивая кластеризация, compressive sensing, l-1-оптимизация, рандомизированные измерения.
Определение подножия континентального склона на основе батиметрических данных
О. Н. Граничин, д. ф.-м. н.
Л. С Гуревич,
Е. В. Степанов.
Санкт-Петербургский государственный университет
01eg_granichin@mail.ru, gurevich.lev@gmail.com.
В работе представлен алгоритм расчета доверительной полосы, в пределах которой с высокой долей вероятности лежит подножие континентального шельфа, в соответствии с требованиями Конвенции и Научно-технического руководства по границам континентального шельфа (Нью-Йорк, 1999). Особенностью задачи являются неполнота и неточность имеющейся информации, которые учитываются в алгоритме внесением рандомизации.
Ключевые слово,: континентальный шельф, метод Монте-Карло, рандомизированный алгоритм.
Аппаратная реализация на базе FPGA рандомизированного метода сжатия изображений
О. П. Исаев
Санкт-Петербургский государственный университет
Рассмотрены традиционные подходы к сжатию изображений. Проведена оценка сложности их реализации. На основе применения парадигмы Compressive Sensing (CS) сокращения размерности массивов данных для задач сжатия изображений представлен математический аппарат получения прямых рандомизированных измерений. Выбран метод восстановления исходного изображение по измеренным данным с помощью процедуры £\-оптимизации. Реализован аппаратный энкодер на базе CS для FPGA. Проведена сравнительная оценка занимаемой логики в реконфигурируемой логической схеме (FPGA) для стандарта JPEG и для рандомизированного метода. Показаны основные достоинства и недостатки предложенного аппаратного метода сжатия изображения.
Ключевые слова: рандомизированные измерения, l-1-оптимизация, восстановление разреженных сигналов, сжатие информации, FPGA, Compressive Sensing, DOT.
Репрезентативность случайно сгенерированных недетерминированных конечных автоматов с точки зрения соответствующих базисных автоматов
Б. Ф. Мельников, д. ф.-м. н..
С. В. Пивнева, к. п. н.,
О. А. Рогова.
Тольяттинский государственный университет
B.Melnikov@tltsu.ru, tlt.swetlana@rambler.ru, rogovaolgatlt@yandex.ru
В статье рассматриваются варианты случайной генерации недетерминированных конечных автоматов. Эти варианты являются авторскими усовершенствованиями известного алгоритма Ван Зиджл, основанного на случайных битовых потоках. Также рассмотрен авторский подход к проверке репрезентативности входных данных на основе приведенных алгоритмов генерации автоматов. Один из рассматриваемых в статье критериев проверки репрезентативности — специально выбираемые характеристики эквивалентного базисного автомата.
Результаты проведенных вычислительных экспериментов показывают. что предлагаемые в статье алгоритмы случайной генерации дают недетерминированные конечные автоматы, более подходящие для решения задач выбранной предметной области.
Ключевые слова: недетерминированный конечный автомат, базисный автомат, алгоритмы случайной генерации, репрезентативность.
Исследования метода Hit-and-Run случайного генерирования точек в выпуклых областях
Е. Г. Лабанкова.
Институт проблем управления им. В. А. Трапезникова
В работе исследуется поведение метода Hit-and-Run, позволяющего получить в областях почти равномерно распределенные точки. Этот метод находит все большее применение в задачах управления. В связи с чем возникает задача о выявлении его достоинств и недостатков. Главным требованием к Hit-and-Run (для его успешного применения) является получение точек с распределением, близким к равномерному. В работе предложено несколько способов исследования метода на равномерность. Первый основан на нахождении минимального и максимального значений линейной функции. Вводится специальная оценка, с помощью которой можно понять насколько равномерным является распределение точек. Во втором способе используется понятие функции распределения. Также для исследования используется тест Колмогорова-Смирнова. Проверяется скоррелированность последовательно брошенных точек.
Ключевые слово,: рандомизационные алгоритмы, метод Монте-Карло, метод Hit-and-Run, проверка статистических гипотез.
Мулътиагентные системы
Легкий беспилотный летательный аппарат для автономной группы
К. С. Амелин
Санкт-Петербургский государственный университет
Рассматривается архитектура беспилотного летательного аппарата, техническое оснащение которого будет удовлетворять требованиям работы в автономной группе БПЛА. Описывается прототип созданного БПЛА.
Ключевые слова: Беспилотные летательные аппараты, навигационная система, автопилот, исполнительные механизмы, групповое взаимодействие.
Достижение консенсуса автономной группой беспилотных самолетов
Н. О. Амелина
Санкт-Петербургский государственный университет
natalia amelina@mail.ru
Рассматривается задача достижения консенсуса для автономной группы беспилотных летательных аппаратов с помощью формирования стратегии управления на основе виртуальной структуры.
Ключевые слова: достижение консенсуса, виртуальная структура, мульти-агентные системы, стратегии управления, беспилотные летательные аппараты.
Некоторые простые алгоритмы управления мультиагентными системами
П. С. Щербаков, д. ф.-м. н.
Институт проблем управления РАН7 Москва
Рассматривается разработанный в [1] алгоритм эволюции совокупности точек на плоскости, приводящий ее в некоторую регулярную конфигурацию. Предлагаются обобщения алгоритма, изучаются некоторые новые свойства. обсуждается связь с методами управления формациями, намечаются новые и более простые алгоритмы такого типа.
Ключевые слова: мультиагентные системы, степенной метод, линейные алгоритмы.
Адаптивные и робастные системы
Имитационная нормализация в задаче идентификации параметров стохастической линейной системы
Ю. В. Цыганова, к. ф.-м. н.
Ульяновский государственный университет
А. В. Цыганов, к. ф.-м. н.
Ульяновский государственный педагогический
университет имени И. Н. Ульянова
TsyganovaJV@mail.ru, andrew.tsyganov@gmail.com
В работе рассматривается решение задачи идентификации параметров стохастической линейной системы с помощью вспомогательного функционала качества (ВФК). Для нахождения минимума ВФК используется метаэв-ристический алгоритм имитационной нормализации (имитации отжига), не требующий вычисления градиента ВФК. Приводятся результаты численных экспериментов.
Ключевые слова: стохастические линейные системы, адаптивная фильтрация, параметрическая идентификация, фильтр Калмана, вспомогательный функционал качества, метод имитации отжига.
Дискретные системы
Анализ некоторых методов представления двухприоритетной очереди
Д. В. Зайцева,
Петрозаводский университет,
А. В. Соколов, д. ф.-м. н.
ИПМИ КарНЦ РАН, Петрозаводск
zaiceva@cs.karelia.ru, avs@krc.karelia.ru
В работе рассматриваются методы представления очереди с двумя приоритетами в памяти одного уровня в виде двух последовательных циклических и в виде двух связанных FIFO-очередей.
Возможны операции "вставить", "удалить элемент с наибольшим приоритетом" и "найти элемент". Предложены алгоритмы нумерации состояний, построения соответствующих регулярных цепей Маркова и вычисления средней доли потерянных элементов при бесконечном времени работы для последовательного и связанного способов представления FIFO-очередей, и нахождения оптимального разбиения памяти для последовательного способа с точки зрения минимизации средней доли потерянных элементов.
Ключевые слова : очереди с приоритетами, FIFO-очереди, случайное блуждание, цепи Маркова, динамические структуры данных.
Вычисление показателя Ляпунова для одной модели стохастической системы с синхронизацией
Н. К. Кривулин, д. ф.-м. н.
Санкт-Петербургский государственный университет
Рассматривается стохастическая динамическая система с синхронизацией. Динамика системы описывается при помощи линейного векторного уравнения с матрицей второго порядка в идемпотентном полукольце с операциями максимума и сложения. Предполагается, что недиагональные элементы матрицы равны нулю, один диагональный элемент является случайной величиной с экспоненциальным распределением, а другой — неотрицательной константой. Решение задачи вычисления показателя Ляпунова для системы включает замену переменных, в результате которой вместо случайных координат вектора состояний системы вводятся новые случайные величины, анализ которых оказывается более удобным. Затем осуществляется построение и исследование сходимости соответствующих этим величинам последовательностей одномерных функций распределения. Показатель Ляпунова вычисляется как среднее значение предельного распределения.
Ключевые слово,: стохастическая динамическая система, показатель Ляпунова, синхронизация событий, сходимость распределений.
Об эквивалентном преобразовании R-нечетких автоматов в стохастические
В. Н. Трубников,
М. К. Чирков, д. ф.-м. н.2
Санкт-Петербургский государственный университет
Работа посвящена исследованию возможности эквивалентного преобразования заданного над полем вещественных чисел нечеткого конечного автомата в стохастический конечный автомат, который представляет тот же обобщенный язык. Доказаны достаточные условия такого преобразования и разработан соответствующий алгоритм. Приведен пример.
Ключевые слова: стохастические конечные автоматы, нечеткие конечные автоматы, обобщенные вероятностные языки, нечеткие языки, эквивалентные преобразования автоматов.
Анализ языков, моделируемых конечно-нестационарными недетерминированными автоматами со случайным входом
М. К. Чирков, д. ф.-м. н..
А. С. Шевченко
Санкт-Петербургский государственный университет
vakh08@mail.ru, annion@yandex.ru
Работа посвящена анализу эквивалентности стационарных стохастических автоматов и обобщенных конечно-нестационарных недетерминированных автоматов со случайным входом, и показано, что они моделируют языки. принадлежащие одному и тому же классу. Доказано, что для любого обобщенного конечно-нестационарного недетерминированного автомата со случайным входом может быть построен абстрактный стохастический автомат, эквивалентный по представляемому обобщенному вероятностному языку.
Ключевые слова: стохастические автоматы, вероятностные языки, конечно-нестационарные недетерминированные автоматы, моделирование вероятностных языков автоматными моделями со случайным входом.
Информационные системы
Интеграция информационных систем НОУ на основе персональных данных1
С. Н. Комаров
Санкт-Петербургский государственный университет
В статье рассматривается один из возможных методов интеграции информационных систем крупного научно-образовательного учреждения (НОУ). основанный на объединении и актуализации персональных данных всех физических лиц вовлеченных в основные бизнес-процессы НОУ с помощью системы управления метакаталогом ПЕРСОНАЛИИ, на примере проведенной работы в СПбГУ.
Ключевые слово,: интеграция информационных систем, интероперабель-ность.
Модель извлечения графематических дескрипторов в системе обработки вьетнамского языка
Ле Чунг Хьеу
Санкт-Петербургский государственный университет
В работе рассматривается модель извлечения графематических дескрипторов в системе обработки вьетнамского языка. Модель использует метод. основанный на сопоставлении образцов в большом текстовом массиве данных, для реализации следующих основных функций: (i) извлечение графематических дескрипторов из текстов (знаков пунктуации, цифровых комплексов, формул, собственных имен, сокращений, и т. п.); (ii) определение границ предложений, фраз. Ключевым элементом модели является набор правил извлечения. Для эксперимента данные были взяты из 283 992 онлайн статей, в которых около 15 000 000 фраз.
Ключевые слова: извлечение графематических дескрипторов, распознавание фактов на вьетнамском языке, графематический анализ, метод, основанный на сопоставлении образцов.
Модель морфологического анализа текстов вьетнамского языка
Ле Чунг Хьеу
Санкт-Петербургский государственный университет
В работе рассматривается новый подход к морфологическому анализу текстов в системе обработки вьетнамского языка. Используя вероятностные модели, набор грамматических правил, а также "ручной" с участием лингвистов процесс морфологической разметки, он позволяет провести: (i) графема-тический анализ — выделение различных нестандартных элементов текста. присваивание им соответствующих графематических дескрипторов, сегментация предложений текста на слова и фразы; (И) на его основе далее осуществляется поиск по морфологическому словарю для каждого слова в предложениях; (Ш) автоматический морфологический анализ вьетнамских текстов на основе Марковской модели и набора грамматических правил.
Основные результаты — формализованный набор грамматических правил и аннотированный корпус вьетнамских текстов — могут быть использованы в развитии средств обработки вьетнамского языка.
Ключевые слова: морфологическая разметка корпуса, морфологический анализ, обработка вьетнамского языка, Марковская модель, алгоритм Витерби. гибридный метод.
Содержание
Рандомизированные алгоритмы
Граничин О.Н. (СПбГУ) Стохастическая
оптимизация и системное
программирование........................................................................................... 3
Граничин О.Н., Гуревич Л.С, Степанов Е.В.
(СГТбГУ) Определение
подножия континентального склона на основе батиметрических дан
ных ................................................................................................................. 45
Исаев О.П. (СПбГУ) Аппаратная реализация на
базе FPGA рандо
мизированного метода сжатия изображений................................................... 52
Мельников Б.Ф., Пивнева СВ., Рогова О.А.(ТГУ) Репрезентативность случайно сгенерированных недетерминированных конечных автоматов с точки зрения соответствующих базисных автоматов . . 74
Лабанкова Е.Г. (ИПУ, Москва) Исследования
метода Hit-and-R,un
случайного генерирования точек в выпуклых областях .............................. 83
Мультиагентные системы
Амелин К.С. (СПбГУ) Легкий беспилотный
летательный аппарат
для автономной группы................................................................................... 117
Амелина Н.О. (СПбГУ) Достижение консенсуса
автономной группой
беспилотных самолетов ................................................................................ 127
Щербаков П.С. (ИПУ, Москва) Некоторые
простые алгоритмы управ
ления мультиагентными системами................................................................. 133
Адаптивные и робастные системы
Цыганова Ю.В. (УлГУ), Цыганов А.В. (УлГПУ)
Имитационная нор
мализация в задаче идентификации параметров стохастической ли
нейной системы ............................................................................................. 147
Дискретные системы
Зайцева Д.В., Соколов А.В. (Петрозаводск)
Анализ некоторых ме
тодов представления двухприоритетной очереди
....................................... 160
Кривулин Н.К. (СПбГУ) Вычисление показателя
Ляпунова для од
ной модели стохастической системы с синхронизацией................................. 171
Трубников В.Н., Чирков М.К. (СПбГУ) Об
эквивалентном преобра
зовании 1-нечетких автоматов в стохастические
........................................ 184
Чирков М.К., Шевченко А.С. (СПбГУ) Анализ
языков, моделируе
мых конечно-нестационарными недетерминированными автоматами
со случайным входом....................................................................................... 203