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

УДК 519.712 БКК 32.811.7 С82

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

Р е ц е н з е н т ы: д-р физ.-мат. наук В. Б. Мелас

(С.-Петерб. гос. ун-т)

канд. физ.-мат. наук А. В. Соколов

(Ин-т прикл. математ. исслед. КарНЦ РАН)

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

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

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

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

Стохастическая оптимизация в информатике. С82 Вып. 2: Межвуз. сб. / Под ред. О. Н. Граничина. - СПб.: Издательство С.-Петербургского университета, 2006. - 288 с. ISSN 1992-2922

Сборник (вып. 1, ненумерованный, вышел в 2005 г.) посвящен вопросам стохастической оптимизации в информатике и составлен по материалам одноименной регулярной серии семинаров для студентов, аспирантов и научных работников, проводившихся в 2005–2006 гг. на математико-механическом факультете С.-Петербургского университета под руководством профессора кафедры системного программирования О. Н. Грани-чина.

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

ББК 32.811.7

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

Рандомизированные алгоритмы оценивания при нерегулярных помехах

А. Т. Вахитов, O. Н. Граничин

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

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

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

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

Рандомизированный метод решения задач полуопределенного программирования

Б. Т. Поляк, П. С. Щербаков

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

Предлагается новый итеративный метод решения задач полуопределенного программирования. Метод относится к классу методов отсекающей гиперплоскости, проводимой через центр тяжести выпуклого множества. Для приближенного отыскания центра тяжести на каждом шаге в допустимой области генерируется равномерное распределение с помощью техники Hit-and-Run и ее модификаций. Обсуждаются робастные постановки задачи, когда в матричных коэффициентах присутствует неопределенность. Работа алгоритма иллюстрируется многочисленными примерами и сравнивается с результатами, полученными при использовании функции solvesdp из пакета Yalmip.

Оптимизация, математические модели

Оптимальное управление FIFO-очередями на бесконечном времени

Е. А. Аксенова

Ин-т прикл. математ. исслед. КарНЦ РАН, Петрозаводск

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

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

O. А. Граничина

Российский государственный педагогический университет

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

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

А. А. Лазутина

Ин-т прикл. математ. исслед. КарНЦ РАН, Петрозаводск

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

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

А. В. Тарасюк

Ин-т прикл. математ. исслед. КарНЦ РАН, Петрозаводск

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

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

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

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

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

Математические модели регуляции тестостерона

А. В. Медведев

Упсальский университет (Швеция)

А. Н. Чурилов, А. И. Шепелявый

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

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

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

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

А. Т. Вахитов

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

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

Алгоритмы классификации за минимальное число шагов

А. Т. Вахитов

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

O. А. Граничина

Российский государственный педагогический университет

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

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

А. С. Дольник

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

В статье рассмотрен эффективный метод последовательного построения классификационных гистограмм для оценки селективности строковых запросов к XML базам данных. Такие гистограммы нужны для специальной модели стоимости, на которой основана работа оптимизатора запросов.

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

Рандомизированный алгоритм для оптимизации энергопотребления в мобильных устройствах

В. Е. Краснощеков

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

Рассматривается Digital Voltage Scaling подход в задаче оптимизации энергопотребления. В основе динамического планировщика напряжения предлагается использовать рандомизированный метод оптимизации среднего риска и адаптивные алгоритмы. Демонстрируется простой пример применения рандомизированного алгоритма стохастической оптимизации.

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

Б. М. Соколов, Е. А. Крылова

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

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

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

Д. С. Шалымов

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

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

Гибридные компьютеры

Создание гибридных сверхбыстрых компьютеров

O. Н. Граничин, С. Л. Молодцов

Санкт-Петербургский государственный университет, Технический университет Дрездена, Германия

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

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

А.Ю. Дорогов, М.Ю. Щестопалов

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

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

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

С. С. Сынтульский

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

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

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

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

Выпуск 2

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

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

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

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

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

Усл. печ. л. 17,21

Заказ №

Издательство СПбГУ. 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