авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

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


Pages:     | 1 | 2 || 4 | 5 |   ...   | 6 |

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В. ЛОМОНОСОВА ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ СБОРНИК ТЕЗИСОВ ЛУЧШИХ ДИПЛОМНЫХ РАБОТ 2009 ...»

-- [ Страница 3 ] --

Тезисы лучших дипломных работ ВМК МГУ 2009 года ДИНАМИЧЕСКАЯ МОДЕЛЬ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ СТРУКТУРОЙ ОБЩЕСТВА Работа удостоена диплома II-ей степени Иванова Мария Владиславовна студент кафедры оптимального управления e–mail: masha.v.ivanova@gmail.com Научный руководитель – член-корр. РАН Асеев Сергей Миронович Дипломная работа посвящена задаче оптимального управления структурой общества.

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

Целью дипломной работы являлось подробное изучение политики переселения, которую применяет государство в первую очередь для того, чтобы увеличить свой доход за счет поступления налоговых сборов, большую долю которых приносит средний класс. Таким образом, необходимо было применить социальную политику переселения, ассимилируя семьи низкого социального уровня и сделать так, чтобы отток семей среднего класса, уже проживающих в некотором рассматриваемом районе (городе или штате) был наименьшим. В качестве рассматриваемого района принимался один из штатов США.

Задача, впервые рассмотренная Jonathan P. Caulkins, формулируется следующим образом.

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

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

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

В отличие от метода рассмотрения задачи, представленного Jonathan P. Caulkins и соавторами в 2004 году, в данной работе для получения результатов был использован принцип максимума Понтрягина для задач на бесконечном горизонте времени с условием стационарности гамильтониана, который позволил наиболее подробно изучить рассматриваемую модель, которая представляет большой интерес при решении проблем, Кафедра ОУ связанных с трудностями увеличения среднего класса в структуре общества США. Это позволило сделать следующие экономические выводы:

В отсутствии миграции количество семей среднего класса (x) стремится к некоторому состоянию насыщения (x=1), и увеличение среднего класса происходит за счет естественного прироста населения, не зависящего от миграции.

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

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

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

Если на начальный момент времени количество семей среднего класса x меньше уровня, то оптимальной является политика по сдерживанию миграции u = 0, до тех пор, пока за счет естественного прироста количество семей не достигнет того уровня, когда миграция не будет приводить к уменьшению среднего класса. С этого момента можно начинать постепенное переселение u =. Это хоть и замедлит рост среднего класса, но не остановит его. Зато вопрос по переводу семей низкого социального уровня в средний класс поднимется как можно раньше. Со временем количество переселяемых семей на одну семью среднего класса можно постоянно увеличивать (соблюдая скорость заселения это делается оптимально для нашей задачи). Ограничения на скорость переселения возникают, как только затраты на него начинают преобладать над выгодой от переселения.

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

В качестве примера города (штата), в котором наиболее ярко отражается рассмотренная ситуация с миграцией, является штат Нью-Йорк.

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

Тезисы лучших дипломных работ ВМК МГУ 2009 года Литература 1. Л.С. Потрягин, В.Г. Болтянский, Р.В. Гамкрелидзе, Е.Ф. Мищенко.

Математическая теория оптимальных процессов. - 4е изд. - М.: "Наука", Главная редакция физико-математической литературы, 1983.-392 с.

2. С.М. Асеев, А.В. Кряжимский. Принцип максимума Понтрягина и задачи оптимального экономического роста. - М.: Издательство "Наука" - МАИК "Наука/Интерпериодика", 2007. - 272 с. - (Тр. МИАН;

Т. 257).

3. Jonathan P. Caulkins, Gustav Feichtinger, Dieter Grass, Michael Johnsonm Gernot Tragler, Yuri Yegorov. Placing the Poor While Keeping the Rich in Their Place:

Separating Strategies for Optimally Managing Residential Mobility and Assimilation.

29 November 2004.

4. Л.С. Потрягин. Обыкновенные дифференциальные уравнения. - 4е изд. - М.:

"Наука", Главная редакция физико-математической литературы, 1974.

5. В.В. Немыцкий, В.В. Степанов. Качественная теория дифференциальных уравнений. ОГИЗ. Гос. изд. технико-теоретической литературы. Москва, 1947.

Кафедра ОУ ИГРОВЫЕ МОДЕЛИ ЭНЕРГЕТИЧЕСКОГО РЫНКА Иванова Анна Евгеньевна студентка кафедры оптимального управления e–mail: anetta86@list.ru Научный руководитель – академик, профессор Кряжимский Аркадий Викторович, ассистент Пивоварчук Денис Геннадьевич Дипломная работа посвящена поиску и исследованию равновесных состояний одной модели энергетического рынка. Добыча и поставка природных ресурсов происходят в условиях конкуренции и ограниченного спроса, что создает предпосылки для существования рынка, который объединяет поставщиков и потребителей ресурсов. При выходе на рынок его участники сталкиваются с необходимостью решать различные задачи оптимизации, связанные с максимизацией прибыли и уменьшением издержек. С другой стороны, так как интересы участников могут не совпадать, а рынок накладывает общие правила и ограничения на участников, то для того чтобы сбалансировать интересы, под решением понимаются равновесные состояния.

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

Поставщик S i характеризуется положительным параметром c i, изображающим размер его денежных затрат на добычу и транспортировку потребителю единицы объема газа в единицу времени, y i - объем газа, добываемого поставщиком S i и поставляемого им потребителю в единицу времени, 0 - цена на газ, формирующаяся рыночным p механизмом как функция от размера g 0 годового спроса и размера y y 2 поставок:

y g, где 0,1 - параметр эластичности.

p y Считаем, что объем годовых поставок газа y на рынок не может превосходить заданного объема годового спроса g, то есть y g. Тогда возникает задача y1 y максимизации годовой прибыли поставщиков при наличии верхнего суммарного ограничения на поставки Тезисы лучших дипломных работ ВМК МГУ 2009 года g J 1 y1, y 2 y1 c1 y1 max, y1 y2 y1 y 2 g g J 2 y1, y 2 y2 c2 y 2 max.

y1 y2 y1 y 2 g Необходимо найти все точки равновесия по Нэшу. Решение задачи основано на функциях наилучших ответов игроков. В ходе решения задачи вводятся и исследуются функции наилучших ответов игроков в более простой задаче, когда отсутствует верхнее суммарное ограничение на поставки. Затем, используя решение упрощенной задачи, определяются и исследуются функции наилучших ответов игроков при наличии верхнего суммарного ограничения на поставки и, на их основе, описывается множество всех точек равновесия по Нэшу в поставленной задаче.

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

Литература 1. G.Klaassen, A.Kryazhimskii, A.Tarasyev. Competition of gas pipeline projects: game of timing. International Institute for Applied Systems Analysis, Interim Report IR-01-037, 2001.

2. G.Klaassen, A.Kryazhimskii, A.Tarasyev. Multiequilibrium game of timing and competition of gas pipeline projects. J. Optim. Theory Appl. 120 (2004), 147-179.

3. O.Golovina, G.Klaassen, A.Roehrl. An economic model of international gas pipeline routings to the Turkish market: numerical results for an uncertain future. International Institute for Applied Systems Analysis, Interim Report IR-02-33, 2002.

4. Н.Н. Воробьев. Теория игр. Лекции для экономистов. Издательство ЛГУ.

Ленинград. 1974.

5. Г. Оуэн. Теория игр. Мир. Москва. 1977.

6. А.Ф. Филиппов. Дифференциальные уравнения с разрывной правой частью.

Москва. Наука. Кафедра ОУ РЕШЕНИЕ ЗАДАЧИ БЫСТРОДЕЙСТВИЯ ДЛЯ НЕЛИНЕЙНОЙ УПРАВЛЯЕМОЙ СИСТЕМЫ, ОПИСЫВАЮЩЕЙ ДВИЖЕНИЕ ТРЕХКОЛЕСНОГО РОБОТА С ФАЗОВЫМИ ОГРАНИЧЕНИЯМИ Маршинин Алексей Борисович студент кафедры оптимального управления e–mail: almarsh.home@gmail.com Научный руководитель – к.ф.-м.н. Камзолкин Дмитрий Владимирович Работа посвящена важной математической проблеме – оптимальному управлению роботами. Цель ее – найти эффективный метод построения управления, переводящего трехколесный робот из одной точки плоскости в другую за минимальное время при наличии фазовых ограничений.

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

В работе подробно на основе обзора научной литературы (44 наименования) исследованы методы, применявшиеся ранее для решения подобных задач. Отдельно рассмотрены методы, аналогичные примененному в данной работе.

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

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

Литература 1. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., МищенкоЕ.Ф.

Математическая теория оптимальных процессов, М.: Наука, 1983.

2. Белотелов В.Н., Голован А.А., Гришин А.А., Жихарев, Д.Н.Ленский А.В., Пахомов В.Б. Задача оптимального по быстродействию выезда мобильного робота в заданную точку.

3. Голубев Ю.Ф. Основы теоретической механики. с.131-133.

4. Евтушенко Ю.Г. Численные методы решения задач нелинейного программирования. Журнал вычислительной математики и математической физики, Том 16, 1976, №2, стр.307-324.

Тезисы лучших дипломных работ ВМК МГУ 2009 года ИССЛЕДОВАНИЕ НЕКОТОРЫХ НЕЛИНЕЙНЫХ ЗАДАЧ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ Пучкова Ална Игоревна студентка кафедры оптимального управления e–mail: apuchkova@gmail.com Научный руководитель – доцент Орлов Михаил Владимирович В первой части дипломной работы рассматривается линейно-квадратичная задача оптимального управления с закрепленными концами траектории Здесь и – одномерные фазовая переменная и управление соответственно. Константы,, заданы, причем. Ограничение на управление отсутствует.

,,,,, Оптимальное решение этой задачи найдено двумя способами.

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

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

Литература Кафедра ОУ 1. Асеев С.М., Кряжимский А.В. Принцип максимума Понтрягина и задачи оптимального экономического роста. – Тр. МИАН, 2007, т. 257.

2. Асеев С.М., Кряжимский А.В., Тарасьев А.М. Принцип максимума Понтрягина и условия трансверсальности для одной задачи оптимального управления на бесконечном интервале. – Тр. МИАН, 2001, т. 233, с. 71 - 88.

3. Ашманов С.А. Математические модели и методы в экономике. – М.: Изд-во Моск. ун та, 1980.

4. Киселв Ю.Н. Достаточные условия оптимальности в терминах конструкций принципа максимума Понтрягина. – Материалы научного семинара "Математические модели в экономике и биологии". М. МАКСПресс. 2003, с. 57 - 67.

5. Киселв Ю.Н., Орлов М.В. Исследование одномерных задач распределения ресурсов на бесконечном промежутке времени. – Вестник Моск. ун-та. Сер. 15. Вычисл. матем. и киберн., 2007, N 2, с. 5 - 11.

6. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. – М. 1961.

Тезисы лучших дипломных работ ВМК МГУ 2009 года ПОСТРОЕНИЕ ОПТИМАЛЬНОГО СИНТЕЗА В ОДНОЙ ЛИНЕЙНОЙ ЗАДАЧЕ С ФАЗОВЫМИ ОГРАНИЧЕНИЯМИ Жуков Дмитрий Андреевич студент кафедры системного анализа e–mail: baetle@mail.ru Научный руководитель – д.ф.-м.н. профессор Арутюнов Арам Владимирович В дипломной работе рассматривается одна двумерная задача оптимального управления с фазовыми ограничениями на фиксированном отрезке времени:

x2 (t )dt min, t 0,1, x u, x1 x2 0, x1 x2 0, (1) x (0) x0, ( x1, x2 )T 2, x0 ( x10, x20 )T, x 2 u1 u (u1, u2 )T 2, u 1.

a2 b В качестве метода исследования задачи (1) используется принцип максимума Понтрягина для задач с фазовыми ограничениями [1,3]. Впервые необходимые условия минимума в форме принципа максимума Понтрягина для задач оптимального управления с фазовыми ограничениями были получены Гамкрелидзе [4] более сорока лет назад. В более общей форме принцип максимума для задач с фазовыми ограничениями был сформулирован и доказан Дубовицким и Милютиным [2]. Впоследствии различными авторами было получено много других, по всей видимости, эквивалентных условий экстремума для этой задачи. Несмотря на это, исследование конкретных задач с фазовыми ограничениями и в наше время вызывает определенные трудности и требует индивидуального подхода. Это прежде всего обусловлено тем, что среди множителей Лагранжа, участвующих в формулировке принципе максимума, присутствуют регулярные меры, устройство которых в каждом конкретном случае является уникальным. В дипломной работе при помощи принципа максимума удалось не только исследовать поведение траекторий вблизи фазовых ограничений, но и построить оптимальный синтез, что является редкостью для задач подобного типа.

Задача (1) рассматривается сначала с упрощенными фазовыми ограничениями x ( x1, x2 )T 2 | x1 x2 0 и затем обобщается на более сложный случай ограничений H 0. При этом в работе доказывается, что решение x ( x1, x2 )T 2 | x1 x G 0, x1 x основной и упрощенной задачи совпадает на множестве G \ Q, где Q - некоторая окрестность нуля, границы которой находятся аналитически и приведены ниже:

Кафедра СА ap a 2 b a a 2 p a2 b a b x10 p10 ln, b b a 2 p102 b2 ( p10 1) bp10 b a 2 p102 b2 ( p10 1)2, x b p10,0.

a 2 b Наиболее интересным является случай x20 x10 b, когда оптимальная траектория выходит на границу фазовых ограничений. При помощи принципа максимума доказывается, что это происходит гладким образом и вся траектория – гладкая кривая, причем в случае G \ Q области задания начальных точек траектория по времени разбивается на два участка 0,t1 и t1,1 ( 0 t1 1 ), а в случае Q - на три 0,t1, t1, t2 и t2,1 ( 0 t1 t2 1 ), где t1 - время выхода траектории на границу x1 x2 0, а t2 - время попадания траектории в точку 0.

Проведенные исследования позволили существенно сократить количество неизвестных и получить уравнения для оптимальной траектории в явном виде. На их основе в среде MatLab было написано приложение, позволяющее получить оптимальную траекторию в задаче (1) при произвольных параметрах и начальных данных.

Основным результатом работы является построение оптимального синтеза в задаче (1). Ниже приводятся уравнения оптимальной траектории для начальных точек из множества Q, представляющие наибольший интерес:

a 2 p102 b2 ( p20 t ) a 2 p10 b( p20 t ) a x10 ln,t 0, p10 p20, b b a 2 p102 b2 p bp a2 a a ab x1 (t ) x1 p10 p20 (t p10 p20 ), t p10 p20, p10 p20, b2 b2 b a 2 b 0, t p10 p20,1.

a a 2 p102 b2 ( p20 t )2 a 2 p102 b2 p202, t x20 0, p10 p20, b a2 a2 a ab x2 (t ) x2 p10 p20 (t p10 p20 ), t p10 p20, p10 p20, b2 b2 b a 2 b 0, t p10 p20,1.

Литература 1. Арутюнов А.В., Магарил-Ильяев Г.Г., Тихомиров В.М. Принцип максимума Понтрягина. – М.: Факториал Пресс, 2006.

2. Дубовицкий А.Я., Милютин А.А. Задачи на экстремум при наличии ограничений. ЖВМ и МФ, т.5, 1965, с. 395-453.

3. Иоффе А.Д., Тихомиров В.М. Теория экстремальных задач. – М.: Наука, 1974.

4. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф.

Математическая теория оптимальных процессов. – М.: Физматлит, 1961.

Тезисы лучших дипломных работ ВМК МГУ 2009 года СТАБИЛИЗАЦИЯ НА ОСНОВЕ ПРОГНОЗИРУЮЩЕЙ МОДЕЛИ ДИСКРЕТНОЙ ДИНАМИЧЕСКОЙ СИСТЕМЫ С ПОМЕХОЙ Калякина Наталья Алексеевна студентка кафедры системного анализа e–mail: neochka@gmail.com Научный руководитель – академик РАН Александр Борисович Куржанский Дипломная работа посвящена задаче стабилизации информационного множества для линейной дискретной многошаговой системы с неполной информацией и неопределенными возмущениями. В рамках подхода model predictive control([1]) временная ось, роль которой играет множество натуральных чисел, разбивается на подмножества, на каждом из которых ищутся условия на параметры системы, позволяющие выбрать управление, сужающее информационное множество. Задача решается в рамках эллипсоидального подхода теории гарантированного оценивания([2]). Заранее ясно, что выбрать управление, обеспечивающее сужение информационного множества, не всегда возможно. А потому выделение класса систем, где сужение происходит, представляет собой весьма важную и актуальную задачу.

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

Литература 1. M. Morary, J.H.Lee Model predictive control: Past, present and future. – Computers and Chemical Engineering, 23, 1999, 667-682с.

2. A.B. Kurzhanski, I.Valyi Ellipsoidal Calculus for Estimation and Control. – Birkhauser, 3. Х. Квакернаак, Р. Сиван Линейные оптимальные системы управления. – Москва, Мир, Кафедра СА ОПТИМАЛЬНАЯ ЛИКВИДАЦИЯ ПОРТФЕЛЯ С ИСПОЛЬЗОВАНИЕМ ИНФОРМАЦИИ О ГЛУБИНЕ И РЕЛАКСАЦИИ РЫНКА Работа удостоена диплома III-ей степени Костов Теодор Веселинов студент кафедры системного анализа e-mail: kostov.teodor@gmail.com Научный руководитель – Смирнов Сергей Николаевич Как правило, современные финансовые модели строятся на основании предположения о совершенном рынке, на котором имеющийся в управлении портфель при желании может быть немедленно ликвидирован по рыночным ценам соответствующих активов. На практике ликвидационная стоимость портфеля будет отличаться от его рыночной стоимости вследствие наличия транзакционных издержек, являющихся неизбежной составляющей любой сделки. Величина данного расхождения будет напрямую зависеть от ликвидности рынка входящих в портфель активов. К сожалению, ликвидность рынка не является четкой концепцией, так как охватывает ряд различных свойств рынка, связанных с процессом самой торговли. Согласно подходу Kyle [6] ликвидность можно рассматривать как совокупность отдельных характеристик рынка (сжатость, глубина, релаксация), которые описывают с разных углов зрения данное явление.

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

Все расчеты были сделаны с использованием реальных данных о ходе торгов акциями на Московской межбанковской валютной бирже (ММВБ).

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

Литература 1. Морозов Р. (2003): ``Дипломная работа: Модель управления портфелем с учетом ликвидности финансового рынка'', Московский Государственный Университет им.М.В.Ломоносова, факультет ВМК, кафедра Системный Анализ 2. Науменко В.В. (2006): Магистерская диссертация: Оценка показателей потенциальных потерь портфеля с учетом ликвидности рынка, ГУ ВШЭ 3. Almgren R., Chriss N.A. (1999): Optimal Execution of Portfolio Transactions, University of Chicago, Department of Mathematics 4. Bangia A., Diebold F. X., Schuermann T., Stroughair J.D. (1998): Modeling liquidity risk with implications for traditional market risk measurement and managment, Warton Financial Institutions Center 5. Bertsimas D., Lo A.W. (1998): Optimal control of execution costs, Journal of Financial Markets 1- 6. Kyle A. (1985): Continuous Auctions and Insider Trading, Econometrica, 53, pp. 1315 7. Large J. (2007): Measuring the resiliency of an electronic limit order book, Journal of financial markets 1- Тезисы лучших дипломных работ ВМК МГУ 2009 года ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ В ЛИНЕЙНЫХ СИСТЕМАХ С СОСТОЯНИЯМИ В ВИДЕ РАСПРЕДЕЛЕНИЙ.

Работа удостоена диплома I-ей степени Мазуренко Станислав Сергеевич студент кафедры системного анализа e–mail: stasmazurenko@mail.ru Научный руководитель – академик Александр Борисович Куржанский Дипломная работа посвящена анализу задач оптимального управления с заданным распределением начальных состояний при помощи методов динамического программирования.

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

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

В данной работе применяется метод динамического программирования для анализа детерминированных задач с состояниями в виде распределений, формулируется принцип оптимальности, и выводятся аналоги уравнений Гамильтона-Якоби-Беллмана в общем случае. Далее рассматривается случай линейной управляемой системы с линейно квадратичным функционалом;

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

Литература 1. А.Б. Куржанский Курс лекций Динамическое программирование и процессы управления – МГУ, ф-т ВМК, кафедра системного анализа, 2007-2008.

2. R.W. Brockett Optimal control of the Liouville equation – Engineering and applied science, Harvard University, 2008.

3. В. С. Владимиров Уравнения математической физики – Наука, Главная редакция физико-математической литературы, Москва 1981.

4. И.М. Гельфанд, Г.Е. Шилов Обобщенные функции и действия над ними – Государственное издательство физико-математической литературы, Москва Кафедра МС Вероятностно-статистические задачи, возникающие при применении выборочных методов к анализу интернет-трафика.

Гайнанова Ирина Валерьевна студентка кафедры математической статистики e–mail: irina.gain@gmail.com Научный руководитель – д.ф.-м.н, профессор Грушо Александр Александрович Дипломная работа посвящена решению актуальных вероятностных задач, возникающих при анализе интернет-трафика. Основное внимание в работе уделяется решению двух проблем в компьютерной безопасности: проблеме выявления аномалий в интернет-трафике и проблеме предотвращения скрытой передачи информации. В работе сделан акцент на изучение влияния погрешности выборочных методов оценки параметров трафика на последующий анализ состояния сети.

Для решения задачи выявления аномалий в сети были рассмотрены три модели трафика: пуассоновская модель, модель с распределением Парето и смешанная модель.

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

В следующей модели время между приходами пакетов рассматривается как случайная величина, соответствующая распределению Парето В, xm 0, 0.

f ( x) xm x качестве параметра, отвечающего за появление аномалии в сети, анализируется параметр формы.

В случае смешанной модели предполагается, что время между приходами пакетов является случайной величиной с функцией распределения F ( x) (1 F2 ( x). Здесь ) F1 ( x) 0 сколь угодно малая величина, F1 ( x) - экспоненциальная функция распределения, - функция распределения произвольной непрерывной случайной величины, F2 ( x) принимающей значения в области x 0. В качестве аномалии рассматривается отклонение от нормального значения параметра в экспоненциальной части распределения.

Для случая пуассоновской модели и модели с распределением Парето доказано существование состоятельных наиболее мощных критериев для выявления изучаемых аномалий, а также получен явный вид критических множеств. В случае пуассоновской Тезисы лучших дипломных работ ВМК МГУ 2009 года модели показано, что построенный критерий устойчив при замене изначальных данных их случайной выборкой. В случае модели Парето показано, что это не так.

В случае смеси экспоненциального и произвольного другого распределения удалось установить ограничения на существование состоятельного наиболее мощного критерия.

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

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

Установлены ограничения на пропускную способность скрытого канала в заданных условиях.

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

Литература 1. J.Mai, A.Sridharan, C.-N.Chuach, T.Ye, H.Zang. Is Sampled Data Sufficient for Anomaly Detection? – Proceeding of ACM Internet Measurement Conference, 2. G.J.Simmons. The prisoners problem and the subliminal channel.- Advances in Cryptology: Proceedings of Crypto, Plenum Press, Кафедра МС АСИМПТОТИЧЕСКАЯ ОЦЕНКА ПОСТОЯННОЙ В НЕРАВЕНСТВЕ БЕРРИ ЭССЕЕНА ДЛЯ РАСПРЕДЕЛЕНИЙ, НЕ ИМЕЮЩИХ ТРЕТЬЕГО МОМЕНТА Гапонова Маргарита Олеговна студентка кафедры математической статистики e–mail: margarita.gaponova@gmail.com Научный руководитель – профессор д.ф.-м.н. Королев Виктор Юрьевич Одним из основных подходов при построении математических моделей, направленных на выявление вероятностных закономерностей поведения характеристик стохастических ситуаций, является замена распределения вероятностей его асимптотической аппроксимацией. Повсеместное распространение получило использование нормальной аппроксимации, основанное на центральной предельной теореме. В этом случае возникает вопрос о скорости сходимости изучаемого распределения к нормальному, ответ на который дает неравенство Берри-Эссеена.

Пусть X1,…,Xn,…- последовательность независимых одинаково распределенных случайных величин, удовлетворяющих соотношениям E|X|2+ EX1=0, DX1=1,, 2+ для некоторого 0 1. Обозначим Sn= Fn(x)=P(Snx), (x)= В этом случае справедливо неравенство Берри-Эссеена (см. [3, 4] для =1 и [1] для 0 1) supx| Fn(x) (Fn, n) (x)| C( ), n- /2– дробь Ляпунова, С( ) зависит только от.

где = 2+ Известно, что С(1) 0.7005 [2]. Для 0 1 В. Тысиаком [6] получена следующая таблица значений верхних оценок константы C( ):

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0. С( ) 1.102 1.076 1.008 0.950 0.902 0.863 0.833 0.812 0. На практике мало, поэтому интересен вопрос об асимптотических оценках С( ), которые впервые были найдены Х. Правитцем [5] для =1:

С(1) Данный результат справедлив и для разнораспределенных случайных величин.

В данной работе обобщен результат Х. Правитца на случай 0 1. В частности, получена следующая таблица верхних оценок:

Тезисы лучших дипломных работ ВМК МГУ 2009 года С( ) 0.4 0.3 0.2 0.1 0.05 0. 0.01 0.1707 0.1707 0.1707 0.1707 0.1707 0. 0.05 0.7268 0.1601 0.1601 0.1601 0.1601 0. 0.10 0.6996 0.1520 0.1481 0.1480 0.1480 0. 0.20 0.9230 0.3241 0.1378 0.1283 0.1277 0. 0.30 0.8527 0.3453 0.2151 0.1206 0.1131 0. 0.40 0.7722 0.3795 0.2462 0.1338 0.1107 0. 0.50 0.7050 0.4157 0.2880 0.1674 0.1274 0. 0.60 0.6675 0.4498 0.3332 0.2295 0.1652 0. 0.70 0.6519 0.4823 0.3797 0.2864 0.2218 0. 0.80 0.6508 0.5144 0.4265 0.3495 0.2985 0. 0.90 0.6611 0.5477 0.4737 0.4166 0.3818 0. 1.00 0.6861 0.5875 0.5249 0.4894 0.4767 0. Из таблицы видно, что оценки В. Тысиака могут быть существенно уточнены уже при 0.4.

Кроме того, получено уточнение результата Х. Правитца для одинаково распределенных слагаемых: С(1) Литература 1. В. В. Петров. Суммы независимых случайных величин. Москва, Наука, 1972.

2. И. Г. Шевцова. Уточнение абсолютной константы в классическом неравенстве Берри-Эссеена.- Статистические методы оценивания и проверки гипотез, изд во Пермского государственного университета, Пермь, 2008.

3. A. C. Berry. The accuracy of the Gaussian approximation to the sum of independent variates.- Trans. Amer. Math. Soc., 1941,vol.49, p.122--139.

4. C. G. Esseen. On the Liapunoff limit of error in the theory of probability.- Ark. Mat.

Astron. Fys., 1942, vol.A28, No.9, p.1-19.

5. H. Prawitz. On the remainder in the central limit theorem.- Scand. Actuarial J., 1975, No.3, pp.145-156.

6. W. Tysiak. Gleichma ige und nicht-gleichma ige Berry – Esseen – Abschatzungen.

Dissertation, Wuppertal, 1983.

Кафедра МС ПРИМЕНЕНИЕ ПРОЦЕССОВ ЛЕВИ ДЛЯ ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОГО ВРЕМЕНИ ИСПОЛНЕНИЯ РЕАЛЬНЫХ ОПЦИОНОВ Ломакин Никита Александрович студент кафедры математической статистики e–mail: nikita.lomakin@gmail.com Научный руководитель – профессор Ульянов Владимир Васильевич Дипломная работа посвящена решению задачи определения оптимального времени исполнения реальных опционов. Задачи такого рода встречаются в самых разных областях финансовой математики, где в качестве базового актива опциона выступают не торгуемые на бирже активы (компания, месторождение, инвестиционный проект и т.д.). Низкий уровень ликвидности таких активов приводит к значительным разрывам в траекториях процессов, моделирующих их поведение. В рамках теории реальных опционов страйком опциона выступают первоначальные затраты инвестора.

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

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

, где – процесс Леви, моделирующий поведение базового актива, – процесс Броуновского движения, определяющий страйк опциона. Для данной модели доказано существование и вид оптимального времени исполнения реального опциона.

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

Литература 1. P. Barrieu, N. Bellamy Impact of Market Crises on Real Options – John Wiley and Sons, 2. E. Mordecki Optimal Stopping for a Diffusion with Jumps – Finance and Stochastics, 3. S. Kou, H. Wang Option Pricing Under a Double Exponential Jump Diffusion Model – Management Science, 4. L. Trigeorgis Real Options – MIT Press, Тезисы лучших дипломных работ ВМК МГУ 2009 года СВОЙСТВА СТАТИСТИК В МОДЕЛИ КОИНТЕГРАЦИИ РЯДА ВЕКТОРНОЙ АВТОРЕГРЕССИИ Работа удостоена диплома II-ей степени Романюк Глеб Викторович студент кафедры математической статистики e–mail:gleb.roma@gmail.com Научный руководитель – профессор Ульянов Владимир Васильевич Дипломная работа посвящена изучению асимптотических свойств статистики для проверки гипотезы об отсутствии зависимости коинтеграционных соотношений от времени в модели Меняющейся во Времени Коинтеграции (Time Varying Cointegration).

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

Пусть p-мерный авторегрессионный ряд, стационарный в разностях, задан с помощью уравнения Меняющейся во Времени Коинтеграции (МВК) k i X t i + t, t = 1, 2, … T, X t = t X t i= где t - матрица коинтегрирующих векторов ранга r - плавно меняется во времени: t имеет малое число членов m в разложении по полиномов Чебышва {1, 2cos i t 0,5 / T,i = 1,2,...}.

Проверяется гипотеза H 0 : t = const против H a : t const. Для этого составляем статистику отношения правдоподобия LR. В пределе при длине ряда T статистика S= 2ln(LR) имеет распределение хи-квадрат.

В настоящей работе получено разложение матожидания статистики S в ряд при верной нулевой гипотезе:

E S = f 1+ B 0 T 1 +o T Для улучшения асимптотики S предлагается использовать поправку Бартлетта.

S М=M S = Составляется модифицированная статистика ОП. Для М 1 + B 0 T Кафедра МС выполняется E M = f + o T. Таким образом, улучшается асимптотика математического ожидания, также как и моментов более высокого порядка, а, следовательно, и функции распределения. Для нахождения значения модифицированной статистики М на конкретной выборке необходимо оценить параметры модели 0, найти S и вычислить корректирующий множитель в точке 0, используя:

1 B 0 p r + pm 1 v + 2c, r + pm + 2 r v, с - функции только от ;

r, p, m — параметры модели МВК.

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

Литература [1] Bierens, H.J. and Martins, L.F. (2009). Time Varying Cointegration.

[2] Johansen, S. (1988). Statistical analysis of cointegration vectors. Journal of Economic Dynamics and Control, 12: 231-254.

[3] Johansen, S. (1999). A small sample correction for test of hypotheses on the cointegrating vectors. Journal of Econometrics.

[4] Johansen, S. (2000). A Bartlett Correction Factor for Tests on the Cointegrating Relations.

Econometric Theory, 16: 740-778.

[5] Johansen, S. (2002). A small sample correction for the test of cointegrating rank in the vector autoregressive model. Econometrica, 70: 1929-1961.

[6] Ulyanov, V.V. and Fujikoshi, Y. (2001) On accuracy of improved 2-approximations.

Georgian Mathematical Journal, 8, No2: 401-414.

[7] Anderson, T.W. (1951). Estimating linear restrictions on regression coefficients for multivariate normal distributions. Annals of Mathematical Statistics, 22: 327-51.

[8] Lawley, D.N. (1956). A general method for approximating to the distribution of likelihood ratio criteria. Biometrica, 43: 296-303.

BdB'.

[9] Phillips, P.C.B. (1988). Weak Convergence to the Matrix Stochastic Integral Journal of Multivariate Time Series Analysis, 24: 252-264.

Тезисы лучших дипломных работ ВМК МГУ 2009 года АНАЛИЗ МЕТОДОВ ВЫЯВЛЕНИЯ ЭКСТРЕМАЛЬНЫХ ЗНАЧЕНИЙ В РЯДАХ НАБЛЮДЕНИЙ Чесноков Александр Васильевич студент кафедры математической статистики e–mail: Al.Chesnokov@gmail.com Научный руководители – доцент Матвеев Виктор Федорович, Матвеев Федор Викторович Дипломная работа посвящена сравнительному анализу методов выявления выбросов в рядах наблюдений. Данная задача является одним из этапов статистического исследования и актуальна для различных прикладных областей от задачи безопасности (мониторинг операций с кредитными картами, отражение вирусных атак) до контроля качества на производстве. Существуют многочисленные публикации с описанием различных методов.

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

Статистическая интерпретация выброса – появление в выборке наблюдения с распределением отличным от распределения генеральной совокупности F ( 0 ) (случай смеси распределений рассматривался для многомерных данных). Для одномерных данных гипотезы для проверки выборки на предмет выбросов:

H 0 : { X n } ~ F ( 0 ) (вся выборка принадлежит одной генеральной совокупности) A, X j ~ F j ( j ) и F j ( j ) H1 : A {1...n} : j F( 0 ) Для сопоставления методов на одномерных данных были отобраны – тесты Граббса и Диксона[1] (для нормального распределения) и широко используемый практиками метод, известный как контрольные карты Шухарта[8]. Для работы с многомерными данными были взяты: метод, использующий иерархический кластерный анализ для обнаружения выбросов[2], метрический метод[4] и плотностный метод[3]. Данные методы были адаптированы и реализованы с использованием статистического пакета R и применены к модельным данным. Модельные данные - выборки различных распределений с искусственно добавленными выбросами – для одномерных данных, для многомерных данных была добавлены различные функциональные зависимости элементов.

Проведенное исследование показало, что результаты работы многомерных методов достаточно сильно варьируются от параметров – применение метода с неизменными параметрами к различным видам данных не показало положительных результатов на всех данных. Это делает применение этих методов возможным только после предварительного изучения данных и тщательной настройки параметров. Для одномерных методов отличную Кафедра МС устойчивость к виду распределения показали карты Шухарта, что сделало возможным их применение разработки подхода к построению кусочно-регрессионной модели.

Предположим, что мы ищем зависимость вида Yt [t 0, T ], параметр Z t f (Z t, X t ) t меняется со временем, но на промежутках вида [t i 1, t i ) остается постоянным. Полученный подход описывается следующим образом - разбиваем [t0, T ] на небольшие промежутки и на каждом оцениваем параметры модели. По нескольким первым полученным значениям параметра строится карта Шухарта. Далее на нее наносятся остальные значения параметров, до появления сигнала о разладке (значение параметра выходит за определенные контрольные пределы) – означает изменение параметра Z t. Теперь, склеив предыдущие промежутки и оценив по ним параметры модели, получим уточненное значение параметров. Далее опять по значениям параметров модели на следующих нескольких промежутках строятся новая карта Шухарта (с новыми контрольными пределами), и все повторяется до следующей разладки и т.д.

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

Применение данной модели к реальным данным (улавливание линейных трендов в динамике фондового индекса РТС) показало неплохие результаты, чем подтвердило работоспособность данного подхода.

Литература 1. V. Barnett, T. Lewis Outliers in Statistical Data, John Wiley (1994) 2. A. Loureiro, L. Torgo, C. Soares Outlier Detection Using Clustering Methods (2004) 3. Z. He, X. Xu, S. Deng Discovering Cluster Based Local Outliers (2003) 4. E. Knorr, R. Ng, V. Tucakov Distance-Based Outliers (2000) 5. V. J. Hodge, J. Austin A survey of outlier detection methodologies (2004) 6. A. Leroy, P. Rousseeuw Robust Regression and Outlier Detection (1987) 7. M. Bassewille, I. V. Nikiforov Detection of Abrupt Changes: Theory and Application (1993) Д. Уилер, Д. Чамберс Статистическое управление процессами. Оптимизация бизнеса с 8.

использованием контрольных карт Шухарта, Москва (2009) Тезисы лучших дипломных работ ВМК МГУ 2009 года СКЕЛЕТНАЯ СЕГМЕНТАЦИЯ ЛИНЕЙЧАТЫХ ИЗОБРАЖЕНИЙ Аргунов Дмитрий Александрович студент кафедры математических методов прогнозирования e–mail: dmiarg@gmail.com Научный руководитель – д.т.н., проф. Местецкий Леонид Моисеевич Дипломная работа посвящена задаче сегментации специального класса изображений – линейчатых изображений. К линейчатым изображениям среди прочих относятся изображения отпечатков пальцев и изображения текста. Линейчатые изображения характеризуются наличием двух семейств локально параллельных линий. Так, изображения отпечатков пальцев состоят из линий папиллярного узора и промежутков между ними.

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

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

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

использование двух порогов вместо одного (тринаризация изображения);

одновременная обработка внутреннего и внешнего скелетов тринаризованного изображения.

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

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

Вводится понятие внешнего и внутреннего скелетов тринарного изображения: они получены из двух бинаризаций исходного линейчатого изображения по принципу «ниже верхнего порога» и «выше нижнего порога». Внутренний и внешний скелеты – это первое приближение описания двух семейств линий исходного изображения.

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

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

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

Литература 1. Местецкий Л.М. Непрерывная морфология бинарных изоражений: фигуры, скелеты, циркуляры. - М., Физматлит, 2009.

2. Гонзалес Р., Вудс Р. Цифровая обработка изображений. - М., Техносфера, 2006.

3. Масалович А.А., Местецкий Л.М. Использование патча Безье для аппроксимации искажения изображений текстовых документов // Труды 17 международной конф.

ГРАФИКОН-2007, Москва, ВМК МГУ, 2007. с. 239-243.

4. Svetlana N. Yanushkevich, Patrick S. P. Wang Image pattern recognition: synthesis and analysis in biometrics. - World Scientific, 2007.

5. Яне Б. Цифровая обработка изображений. - М., Техносфера, 2006.

6. http://www.neurotechnology.com.

7. http://www.sonda-tech.com/ru.

8. http://audio.rightmark.org/lukin/graphics/resampling.htm.

Тезисы лучших дипломных работ ВМК МГУ 2009 года РАЗРЕШИМОСТЬ И РЕГУЛЯРНОСТЬ ЗАДАЧ НЕЧЁТКОЙ РАЗМЕТКИ ТОЧЕЧНЫХ КОНФИГУРАЦИЙ Работа удостоена диплома II-ей степени Дорофеев Николай Юрьевич студент кафедры математических методов прогнозирования E–mail: cmc.nick@gmail.com Научный руководитель – к. ф.-м. н. Чехович Юрий Викторович В дипломной работе была рассмотрена задача построения обучаемых алгоритмов классификации точек в плоских конфигурациях. Постановка задачи дана в [1]. Требуется каждой точке конфигурации сопоставить элемент из некоторого множества, называемого словарм разметки. В работе [2] были рассмотрены вопросы разрешимости и регулярности задач выделения трендов. Указанные задачи были сведены к задаче классификации точек в плоских точечных конфигурациях. Там же были даны определения и получены критерии локальной разрешимости и локальной регулярности этих задач.


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

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

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

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

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

Литература 1. Чехович Ю.В. Об обучаемых алгоритмах выделения трендов // Искусственный интеллект (научно-теоретический журнал НАН Украины). № 2, 2002, с. 298-305.

2. Рудаков К.В., Чехович Ю.В. Алгебраический подход к проблеме синтеза обучаемых алгоритмов выделения трендов // Доклады Академии наук. Том 388, № 1, 2003, с. 33-36.

3. Рудаков К. В. Об алгебраической теории универсальных и локальных ограничений для задач классификации // Распознавание, классификация, прогноз. Москва, Наука, 1989, С.

176-201.

4. Журавлв Ю. И. Избранные научные труды. – Москва, Магистр, 1998, С. 91-135.

Тезисы лучших дипломных работ ВМК МГУ 2009 года АНАЛИЗ ПРОСТРАНСТВЕННОЙ СТРУКТУРЫ ДАННЫХ МАГНИТНОЙ ЭНЦЕФАЛОГРАФИИ Работа удостоена диплома II-ей степени Корнилина Елена Дмитриевна студентка кафедры математических методов прогнозирования e–mail: ekornilina@gmail.com Научный руководитель – к.ф.-м.н. Махортых Сергей Александрович В дипломной работе предложен метод анализа данных магнитной энцефалографии (МЭГ), направленный на повышение точности локализации источников биомагнитной активности. Метод может использоваться в задачах комплексной диагностики различного рода нейрофизиологических заболеваний, в частности, был рассмотрен случай слуховых галлюцинаций, которые могут возникать как самостоятельное заболевание (Tinnitus), так и сопровождать течение некоторых болезней (паркинсонизм).

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

Реализован ранее не используемый в задачах локализации источников биомагнитного поля метод, основанный на выделении значимых составляющих временного ряда МЭГ с помощью анализа Фурье и вейвлет-анализа (рис. 1,2).

Рис. 1. Спектральная плотность данных МЭГ Рис. 2. Коэффициенты вейвлет-разложения (метод Уэлча) в базисе Хаара Кафедра ММП В результате исследования было выделено две основные частоты: 10 и 20 Гц, на которых была произведена локализация источников в контрлатеральных и ипсилатеральных областях височных долей коры головного мозга, соответственно (рис. 3,4).

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

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

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

Литература 1. Астафьева Н. М. Вейвлет-анализ: основы теории и примеры применения // Успехи физических наук.том 166., _ 11. - 1996.

2. Джеффрис Г., Свирлс Б. Методы математической физики. М.: Мир, вып. 3, т. 3345с.

3. Махортых С. А., Семечкин Р. А. Спектральные методы анализа магнитных энцефалограмм. Динамика неоднородных систем // Труды Института системного анализа РАН, 2008, Т. 33(вып. 12): 236- 4. Устинин М. Н., Махортых С. А., Молчанов А. М. и др. Задачи анализа данных магнитной энцефалографии Компьютеры и суперкомпьютеры в биологии.М.: Институт компьютерных технологий,2002,С. 327- 5. Whitham E. M., Pope K. J., Fitzgibbon S. P. Scalp electrical recording during paralysis:

quantitative evidence that EEG frequencies above 20 Hz are contaminated by EMG // Clin Neurophysiol 118 (8): 1877-88. DOI:10.1016/j.clinph.2007.04.027. PMID 17574912.

Тезисы лучших дипломных работ ВМК МГУ 2009 года ПОСТРОЕНИЕ КОМПОЗИТНО-ИЕРАРХИЧЕСКИХ СКРЫТЫХ МАРКОВСКИХ МОДЕЛЕЙ ДЛЯ АНАЛИЗА ПОВЕДЕНИЯ Темлянцев Александр Валерьевич студент кафедры математических методов прогнозирования e–mail: alexander.temlyantsev@gmail.com Научные руководители – к.ф.-м.н., Ветров Дмитрий Петрович, м.н.с. ВЦ РАН Кропотов Дмитрий Александович Графические модели (graphical models [2, ch. 8]) зарекомендовали себя как надежный и эффективный инструмент статистического анализа структурированных данных. Являя собой выразительный язык для описания и конструирования сложных вероятностных моделей, они обеспечивают универсальный подход к решению основных задач машинного обучения. В данной работе означенная идеология применяется для автоматического определения эмоциональной динамики живой системы по внешним, наблюдаемым проявлениям ее активности (например, по видеозаписи или динамике биометрических показателей) На основании актуальных представлений о структуре поведенческого акта [1] и эмоционального состояния была построена композитно-иерархическая скрытая марковская модель - байесовская сеть, дополненная аналитическими ограничениями, для которой были разработаны эффективные алгоритмы обучения (на основе EM-алгоритма) и байесовского вывода (являющийся обобщением известного алгоритма Витерби для скрытых марковских моделей [3]).

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

Литература 1. Анохин П.К. Принципиальные вопросы общей теории функциональных систем. – М.:

АН СССР, 1971.

2. Bishop C.M. Pattern Recognition and Machine Learning. – Springer. 2006. ISBN-13: 978-0 387-31073- 3. Robert J. Elliott, Lakhdar Aggoun, John B. Moore. Hidden Markov Models: Estimation and Control – Berlin: Springer-Verlag, 1995.

4. S. Fine, Y. Singer and N. Tishby. The Hierarchical Hidden Markov Model: Analysis and Applications – Machine Learning, vol. 32, p. 41–62, Кафедра ММП РЕШЕНИЕ ЗАДАЧИ ВОССТАНОВЛЕНИЯ РЕГРЕССИИ НА ОСНОВЕ РЕШЕНИЙ КОЛЛЕКТИВА КЛАССИФИКАТОРОВ Ткачев Юрий Игоревич студент кафедры математических методов прогонзирования e–mail: tkachevy@gmail.com Научный руководитель – профессор Рязанов Владимир Васильевич В дипломной работе рассматривается задача установления зависимости между вектором независимых переменных и зависимой скалярной величиной по данным обучающей выборки. Априорные ограничения на вид функции не накладываются.

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


Литература Васильев Ф. П. Численные методы решения экстремальных задач. М.: Наука, 1988.

1.

Вучков И., Бояджиева. Л., Солаков Е. Прикладной линейный регрессионный анализ.

2.

М.: Финансы и статистика, 1987.

Гнеденко Б.В. Курс теории вероятности. М.: Наука, 1988.

3.

Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976.

4.

Журавлев Ю.И. Избранный научные труды. М.: Издательство Магистр, 1998.

5.

Журавлев Ю. И., Рязанов В. В., Сенько О. В. РАСПОЗНАВАНИЕ. Математические 6.

методы. Программная система. Практические применения. М.: Фазис, 2005.

Лоусон Ч., Хенсон Р. Численное решение задач метода наименьших квадратов. М.:

7.

Наука, 1986.

Хардле В. Прикладная непараметрическая регрессия. М.: Мир, 1993.

8.

Тезисы лучших дипломных работ ВМК МГУ 2009 года СЕГМЕНТАЦИЯ ФОРМЫ ПРОСТРАНСТВЕННЫХ ИЗОБРАЖЕНИЙ Хромов Денис Валерьевич студент кафедры математических методов прогнозирования e–mail: khromovd@mail.ru Научный руководитель – профессор Местецкий Леонид Моисеевич Дипломная работа посвящена задаче сегментации пространственных изображений.

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

Поэтому для их анализа нужны специальные алгоритмы.

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

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

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

построение набора плоскостей, позволяющих по соответствующим сечениям провести сегментацию пространственного объекта;

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

поиск на линии зубов критических точек, соответствующих промежуткам между зубами;

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

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

По материалам исследований подготовлен доклад на предстоящую конференцию «Графикон-2009».

Литература 1. Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы: построение и анализ. – М.:МЦНМО, 2001.

2. Местецкий Л.М. Непрерывная морфология бинарных изображений: фигуры, скелеты, циркуляры. – М.: ФИЗМАТЛИТ, 2009.

3. D. D. Hoffman and M. Singh. Salience of visual parts. – Cognition, 63(1):29-78, April 1997.

4. Dennie Reniers, Alexandru Telea. Skeleton-based Hierarchical Shape Segmentation. – Shape Modeling International, pages 179-188, 2007.

5. Sebastien Valette, Ioannis Kompatsiaris, Michael G. Strintzis. A polygonal mesh partitioning algorithm based on protrusion conquest for perceptual 3D shape description. – Workshop towards Semantic Virtual Environment SVE 2005.

6. V.A. Knyaz, S. Yu. Zheltov. Photogrammetric techniques for dentistry analysis, planning and visualisation. – ISPRS Congress Beijing 2008, Volume XXXVII, Part B5, Commission V.

Кафедра ММП ЛОГИЧЕСКИЕ АЛГОРИТМЫ КЛАССИФИКАЦИИ:

ПРОБЛЕМА ПЕРЕОБУЧЕНИЯ И ПРИМЕНЕНИЕ В ЗАДАЧАХ МЕДИЦИНСКОЙ ДИАГНОСТИКИ Цурко Варвара Владимировна студентка кафедры математических методов прогнозирования e-mail: v.tsurko@gmail.com Научный руководитель – к.ф.-м.н. Воронцов Константин Вячеславович В работе рассматривается задача предсказания отдаленного результата хирургического лечения атеросклероза. В структуре смертности атеросклероз и его проявления занимают основное место, являясь причиной 80% летальных исходов. Сужение и тромбоз артерий в большинстве случаев не удается вылечить без операции. Хирургическое вмешательство заключается в установке шунта в артерию, но это не всегда приносит положительный результат, т.к. иногда происходит повторное сужение сосуда на том же или другом уровне.

Исходные данные задачи представляют собой матрицу объекты-признаки. Объектами являются больные, которым была произведена операция, признаками — показатели, измеренные у больных до и после операции, целевым признаком является отдаленный результат операции: положительный исход (успешная операция), отрицательный исход (рецидив заболевания). Для задачи характерны следующие особенности: большая размерность (число признаков превышает число прецедентов), пропуски данных (более 16%), неточность измерения признаков, несбалансированность классов (число объектов с отрицательным исходом менее 18%), неравноценные классы (объекты с отрицательным исходом имеют большую цену ошибки, чем объекты с положительным).

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

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

Выявлено, что признаки, измеренные непосредственно после операции, информативнее признаков, измеренных до операции, иммунологическая группа признаков информативнее гемодинамической. Анализ объектов задачи выявил нетипичные объекты, исключение которых из обучающей выборки позволило улучшить качество классификации. Задача предсказания отдаленного результата операций решалась с помощью логических алгоритмов Тезисы лучших дипломных работ ВМК МГУ 2009 года классификации, т. к. эти алгоритмы легко интерпретируемы и могут быть проанализированы самими экспертами-врачами. В работе был разработан метод генерации логических правил, предложен оригинальный функционал информативности, позволивший уменьшить негативный эффект несбалансированности данных, реализован метод отбора закономерностей по двум критериям с использованием Парето-оптимального фронта.

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

Литература Воронцов К.В. Комбинаторные оценки качества обучения по прецедентам // Докл. РАН.

1.

– 2004. – Т. 394, № 2. – С. 175-178.

2. Furnkranz J. Modeling rule precision // LWA / Ed. by A. Abecker, S. Bickel, U. Brefeld, I.

Drost, N. Henze, O. Herden, M. Minor et al. – Humbold-Universitat Berlin, 2004. – Pp. 147 154.

Furnkranz J., Peter F. ROC n‘ rule learning – towards a better understanding of converting 3.

algorithms // Machine Learning. – 2005. – Vol. 58, no. 1. – Pp. 39-77.

Janssen F., Furnkranz J. On meta-learning rule heuristics // LWA / Ed. by A. Hinneburg. – 4.

Martin-Luther-University Halle-Wittenberg, 2007. – Pp. 167-174.

Ивахненко А.А. Методы улучшения обобщающей способности логических алгоритмов 5.

классификации. – Магистерская диссертация, ФУПМ МФТИ. – 2007.

Загоруйко Н.Г., Елкина В.Н., Лбов Г.С. Алгоритмы обнаружения эмпирических 6.

закономерностей. – Новосибирск, Наука, 1985.

Васин А.А., Краснощеков П.С., Морозов В.В., Исследование операций. – М., Академия, 7.

2008.

Кузнецов М.Р., Туркин П.Ю., Воронцов К.В., Дьяконов А.Г., Ивахненко А.А., Сиваченко 8.

Е.А. Прогнозирование результатов хирургического лечения атеросклероза на основе анализа клинических и иммунологических данных. – М., МАКС Пресс, 2007.

Кафедра МК ОЦЕНКИ СЛОЖНОСТИ МУЛЬТИПЛЕКСОРНОЙ ФУНКЦИИ В НЕКОТОРЫХ КЛАССАХ СХЕМ.

Работа удостоена диплома III-ей степени Власов Никита Вадимович студент кафедры математической кибернетики.

e–mail: nikv@post.ru Научный руководитель – профессор Ложкин Сергей Андреевич.

В дипломной работе решается задача синтеза для мультиплексорной функции алгебры логики (ФАЛ) порядка n (мультиплексора порядка n ), то есть ФАЛ от n 2 n n булевых переменных (БП), где первые n переменных называются «адресными», оставшиеся 2 n — «информационными», а значение функции равно значению той е информационной БП, номер которой поступил на адресные БП.

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

Сложность мультиплексорной ФАЛ изучалась в ряде работ. Известно (см. [1]), что сложность реализации ФАЛ, n 1,2,, как схемами из функциональных элементов n (СФЭ), так и формулами в стандартном базисе Б 0 y, x}, асимптотически равна {x & y, x n n. В [2] получена нижняя оценка вида 2 и верхняя оценка вида n n1 2 c1 2 O n n в классе СФЭ над базисом Б 0.

для сложности реализации ФАЛ 2n c2 2 2 O 24 n Кроме того, в [1] была установлена асимптотика сложности ФАЛ в классе СФЭ в базисе n y, x}. В [3] были доказаны верхние оценки вида (n 4) для глубины {x & y, x мультиплексорной ФАЛ порядка n в классе формул в стандартном базисе, где все функциональные элементы (ФЭ) имеют единичную глубину, и оценки вида (n 3), если ФЭ « & » и « » имеют единичную глубину, а ФЭ « » — нулевую.

В дипломной работе доказывается, что сложность реализации мультиплексорной 2n 2n ФАЛ в классе -схем равна 2 n и, тем самым, для указанной сложности O n n log n Тезисы лучших дипломных работ ВМК МГУ 2009 года впервые устанавливаются (см. [3]) асимптотические оценки высокой степени точности 2n 2n (АОВСТ). Доказываются также близкие к АОВСТ оценки вида 2 n c ( n) O n n log n для сложности реализации ФАЛ в классе формул, где c(n) — некоторая функция, n принимающая значения из отрезка [1,2].

Кроме того, в работе находится точное значение глубины ФАЛ в классе формул в n стандартном базисе, где ФЭ « & » и « » имеют единичную глубину, а ФЭ « » — нулевую, равное 2, если n 1, и равное (n 2) для всех остальных значений n, отличных от 6,,24.

Литература 1. Коровин В. В. О сложности реализации универсальной функции схемами из функциональных элементов. // Дискретная математика. — 1995. — Т. 7, вып. 2.

— С. 95-102.

2. Румянцев П. В. О сложности реализации мультиплексорной функции схемами из функциональных элементов. // Проблемы теоретической кибернетики.

Тезисы докладов XIV международной конференции (Пенза, 23-28 мая 2005 г.).

— М.: Изд-во мех.-мат. факультета МГУ, 2005. — С. 133.

3. Ложкин С.А. О синтезе формул, сложность и глубина которых не превосходят асимптотически наилучших оценок высокой степени точности. // Вестн. Моск.

ун-та сер. 1, математика. механика. 2007. №3. — С. 20-26.

Кафедра МК ИССЛЕДОВАНИЕ СЛОЖНОСТИ УМНОЖЕНИЯ В ГРУППОВЫХ АЛГЕБРАХ Работа удостоена диплома I-ей степени Чокаев Бекхан Вахаевич студент кафедры математической кибернетики e–mail: chokaev@cs.msu.su Научный руководитель – профессор Алексеев Валерий Борисович Одной из центральных областей алгебраической теории сложности является сложность умножения в алгебрах. Алгеброй называется линейное пространство, наделенное операцией умножения: отображением, которое двум произвольным элементам пространства ставит в соответствие определенный элемент этого пространства, причем это отображение является линейным по обоим аргументам. При этом размерность линейного пространства называется размерностью алгебры, базис пространства – базисом алгебры.

Задача сложности умножения в алгебре заключается в том, чтобы построить алгоритм, принадлежащий заранее зафиксированному классу алгоритмов, который для любых двух элементов этой алгебры вычислял бы их произведение и имел бы наименьшую сложность среди всех алгоритмов данного класса. Общепринятым в алгебраической теории сложности является класс билинейных алгоритмов (см. [3]).

Определение. Билинейным алгоритмом умножения для алгебры A называется такая последовательность ( f1, g1, w1,..., f r, g r, wr ), где f i, g i r, что для любых A*, wi A, 1 i r векторов a, b A их произведение вычисляется по формуле: ab f i (a) g i (b) wi. Число r i называется длиной билинейного алгоритма. Билинейной сложностью умножения в алгебре A или рангом A называется длина кратчайшего билинейного алгоритма для A и обозначается rgA.

Теорема (Алдер, Штрассен, [1]). Для произвольной ассоциативной алгебры A выполняется rgA 2 dim A t ( A), где t (A) – число максимальных идеалов алгебры A. Алгебра, для которой это неравенство выполняется как равенство, называется алгеброй минимального ранга.

Определение. Алгебра A называется групповой алгеброй, если существует такой базис a1, a 2,..., a n этой алгебры, что множество {a1, a 2,..., a n } образует некоторую группу G относительно умножения в A. В этом случае алгебра A обозначается F[G], где F – поле над которым она определена.

Сложность умножения в групповых алгебрах оказалась тесно связанной со сложностью умножения в алгебре матриц. В 2003 году Генри Коэн и Кристофер Уманс Тезисы лучших дипломных работ ВМК МГУ 2009 года доказали, что, если сложность умножения в групповых алгебрах – почти линейна относительно размерности алгебры, то сложность умножения матриц порядка n – почти квадратична относительно n (см.[4]).

Дипломная работа посвящена исследованию билинейной сложности умножения в коммутативных групповых алгебрах над произвольными полями. Для решения этой задачи предложен метод нахождения структуры групповых алгебр, который позволяет использовать теорему Алдера-Штрассена для доказательства нижних оценок и теорему Блезера (см. [2]), описывающую все алгебры минимального ранга, для доказательства верхних оценок.

Основные результаты дипломной работы.

Теорема 1. Пусть F[G] – произвольная коммутативная групповая алгебра размерности n над полем характеристики нуль. Тогда алгебра F[G] является алгеброй минимального ранга и rgF[G] 2n s. Для вычисления числа s найдены несложные формулы, зависящие от структуры группы G, а также от разложения над полем F двучлена x n 1 на неприводимые сомножители.

Теорема 2. Пусть F [G ] – групповая алгебра абелевой группы порядка n над конечным q полем из q элементов, и НОД (n, q) 1. Тогда алгебра F [G ] является алгеброй q минимального ранга тогда и только тогда, когда q 2m 2, где m – минимальное натуральное число, удовлетворяющее условию: q m 1(mod n).

Теорема 3. Пусть F[G] – групповая алгебра абелевой группы порядка n над произвольным полем характеристики p, и p не делит n. Тогда существует константа С такая, что rgF[G] Сn.

Теорема 4. Пусть F[G ] – групповая алгебра группы G над Z Z... Z n n p p p n раз произвольным полем характеристики p, где Z p - циклическая группа порядка p. Тогда rgF [Gn ] (3 o(1)) dim F [Gn ] при n.

Литература 1. A. Alder, V. Strassen. On the algorithmic complexity of associative algebras. 1981.

2. M. Blaser. Algebras of Minimal Rank over Arbitrary Fields. SIIM Technical Report, 2002.

3. P. Burgisser, M. Clausen, M. Shokrollahi. Algebraic Complexity Theory. Springer, 1997.

4. H. Cohn, C. Umans. A Group-Theoretic Approach to Fast Matrix Multiplication.

2003.

Кафедра МК МЕТОД ПРЕДОБУСЛАВЛИВАНИЯ ДЛЯ БЛОЧНОГО АЛГОРИТМА ТИПА ЛАНЦОША ДЛЯ РЕШЕНИЯ ЗАДАЧИ ФАКТОРИЗАЦИИ Алехова Елена Юрьевна студентка кафедры математической кибернетики e-mail: 0allena0@gmail.com научный руководитель— доцент Применко Эдуард Андреевич Задача эффективной факторизации больших чисел является одной из самых актуальных задач современной криптографии. Именно к ней сводятся большинство используемых на практике методов криптоанализа такой широко распространнной системы, как RSA [1]. Наиболее трудомким этапом решения задачи факторизации является решение СЛАУ Ax=0 над полем GF(2). Матрица A этой СЛАУ разреженна, неструктурированна и е размеры могут достигать. Для решения подобных СЛАУ разработан класс специализированных методов [2], наиболее широко используемым из которых является блочный метод Ланцоша. Метод Ланцоша является итерационным и скорость его сходимости может быть повышена предобуславливанием. Однако, построение эффективных предобуславливателей затруднено особенностями матрицы A. В данной работе предлагается метод построения предобуславливателей, использующий преобразование матриц в гиперграфы и построение разбиений гипергафов, минимизирующих определнную метрику.

Гиперграфом H называется пара множеств H=(V,E), где V — множество вершин, E — множество гиперрбер, каждое гиперребро является подмножеством множества вершин.

Разбиением гиперграфа P на k частей называются k подмножеств P={V0,...,Vk-1}, где Vi, i=0..k-1, {Vi}=V являются непересекающимися подмножествами множества вершин.

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

cuts(H,P)=i=0|E|-1(i(H,P)-1), (1) где i(H,P)k количество частей разбиения, в которые попали вершины из i-того гиперребра.

Построить поматрице гиперграф можно двумя основными способами. В первом способе столбцы матрицы рассматриваются как вершины гиперграфа, а строки как гиперребра, во втором наоборот. Рассмотрим первый вариант. Каждому столбцу ci исходной матрицы A с элементами aij сопоставим вершину гиперграфа, каждой строке rj — гиперребро. Вершина ci принадлежит гиперребру rj тогда и только тогда, когда aij0.

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

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



Pages:     | 1 | 2 || 4 | 5 |   ...   | 6 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.