«СБОРНИК ТЕЗИСОВ ЛУЧШИХ ДИПЛОМНЫХ РАБОТ 2013 года МОСКВА 2013 УДК 517.6 + 519.8 ББК 22 С23 Данный сборник посвящается 110-летию со дня рождения Андрея Николаевича Колмогорова – выдающегося математика, одного из ...»

Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года На основе значений асимптотической эффективности было произведено сравнение с другими методами построения покрытия — методом ППП (Пошагового Пополнения Покрытия), который был предложен и исследован в [3], и многомерными полярными координатами, свойства которого были изучены в [4]. В двумерном случае оптимальное (а значит, и равномерное) покрытие строится с помощью сферической системы координат.

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

В работе был проведен численный эксперимент для сравнения радиусов покрытий, порождаемых методами ППП и ПТК, при небольшом числе точек базы покрытия (k = 300), в ходе которого было показано преимущество использования адаптивного субоптимального метода ППП.

1. Л. С. Понтрягин, В. Г. Болтянский, Р. В. Гамкрелидзе, Е. Ф. Мищенко. Математическая теория оптимальных процессов. М.: Наука, 2. А. В. Лотов, В. А. Бушенков, Г. К. Каменев, О. Л. Черных. Компьютер и поиск компромисса. Метод достижимых целей. М.:Наука, 3. Г. К. Каменев, В. А. Лотов, Т. С. Майская. Итеративный метод построения покрытий многомерной единичной сферы. Журнал вычислительной математики и вычислительной физики, том 53, №2, 2013. C. 181-194.

4. Т. С. Майская. Оценка радиуса покрытия многомерной единичной сферы метрической сетью, порожденной сферической системой координат. Сборник статей молодых ученых факультета ВМК МГУ, вып. 8. М.:Изд. ВМК МГУ, 2011. С. 83-98.

Стохастические дифференциальные уравнения для случайных процессов со смешанными гауссовскими распределениями Работа удостоена диплома I степени Алекритский Дмитрий Игоревич Кафедра математической статистики Научный руководитель: д.ф.-м.н., проф. Королёв Виктор Настоящая дипломная работа посвящена разработке разумной математической модели хаотических стохастических процессов, прежде всего, процессов, описывающих эволюцию финансовых индексов, в частности, биржевых цен. Как показано во многих исследованиях (например, в [1]), адекватными макроструктурными моделями таких процессов могут быть подчинённые винеровские процессы, конечномерными распределениями которых являются смеси нормальных законов. Эти процессы имеют непрерывные траектории. С другой стороны, анализ высокочастотных данных позволяет считать, что на временных микро-масштабах траектории процессов биржевых цен кусочно постоянны.

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

Эти потоки определяют механизм ценообразования данного инструмента (см. [2]). Введён и изучен процесс дисбаланса потоков заявок, имеющий вид разности процессов Кокса с зависимыми интенсивностями. Процессу дисбаланса можно придать смысл приращения логарифма цены финансового инструмента. Получены весьма естественные достаточные условия сходимости конечномерных распределений случайного процесса дисбаланса потоков заявок к смесям нормальных законов при измельчении величины скачков и неограниченном возрастании интенсивности торгов на конечном отрезке времени.

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

Для этих уравнений приведены довольно простые достаточные условия существования и единственности сильных решений. В частности, улучшены и обобщены результаты статьи [4]. Выбор именно конечных смесей мотивирован тем обстоятельством, что в отличие от общих сдвиг/масштабных смесей гауссовских распределений конечные смеси идентифицируемы, т. е. возможно статистически оценить смешивающее Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года распределение. На основе построенных СДУ предложена адекватная модель эволюции финансовых индексов и решены традиционные математические задачи определения рациональной стоимости производных ценных бумаг.

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

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

1. Королёв В. Ю. Вероятностно-статистические методы декомпозиции волатильности хаотических процессов. М.: Изд-во Моск. ун-та, 2. Королёв В. Ю., Черток А. В., Корчагин А. Ю., Горшенин А. К.

Вероятностно-статистическое моделирование информационных потоков в сложных финансовых системах на основе высокочастотных данных. Москва, 2013.

3. Abergel F., Jedidi A. A mathematical approach to order book modeling.

New York, 2011.

4. Brigo D., Mercurio F., Sartorelli G. Lognormal-mixture dynamics under dierent means. — Working paper. Available:

';

www.fabiomercurio.it/qnternal.pdf 5. Harrison J. M., Pliska S. R. Martingales and stochastic integrals in the theory of continuous trading // Stochastic Processes and their Applications 11, 1981, 215-260.

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

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

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

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

Выборочная автокорреляционная функция, зависящая от объема корзины, показала, что логарифм мгновенной интенсивности имеет структуру, типичную для процесса авторегрессии низкого порядка, и что коэффициент автокорреляции убывает с объемом корзины. Функция логарифма хорошо моделирует уменьшение корреляции с ростом объема корзины. Следует отметить, что с ростом объема корзины увеличивается и интервал времени, на котором рассматривается ряд, так как нам требуется больше наблюдений, чтобы собрать корзину нужного объема. Эффект убывания автокоррелированности может быть связан с эффектом "унормаливания описанном в [1]: приращения процессов за интервалы времени большей длины намного ближе к нормальным, нежели распределения приращений процессов за интервалы меньшей длины.

Далее было исследовано поведение процесса интервалов времени для корзин разного объема. Предполагалось, что с ростом объема корзины должны пропадать «горбы» на гистограмме процессов приращений времени, сформированных для корзины заданного объема. Однако, оказалось, что «горбы» по прежнему сохраняются, но при этом с ростом объТезисы лучших дипломных работ факультета ВМК МГУ 2013 года ема корзины распределение меняет форму. Таким образом, на практике мы столкнулись с нарушениями условий теоремы, описанной в статье [2], о представлении данного распределения в виде смеси экспоненциальных законов. Мы показали, что распределение интервалов времени нельзя представить в виде смеси экспоненциальных законов.

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

1. Королев В.Ю. Вероятностно-статистические методы декомпозиции волатильности хаотических процессов Издательство Московского Университета, 2011.

2. Andrey Gorshenin, Alexander Doynikov, Victor Korolev, Victor Kuzmin Statistical Properties of the Dynamics of Order Books: Emperical Results, VI International Workshop "APTP + MS"(Autumn Sessions, 2012), pp.

Влияние стратегии выбора порога при обработке зашумленных изображений с помощью вейвлет-разложения Работа удостоена диплома II степени Кафедра математической статистики email: [email protected] Научный руководитель: д.ф.-м.н., доц. Шестаков Олег В работе рассматриваются алгоритмы пороговой фильтрации цифровых изображений, основанные на вейвлет-разложении. В качестве входных данных используются полутоновые изображения(фотографии),описываемые массивами разного размера, и с разным содержанием. К изображениям добавляется аддитивный гауссовский белый шум.

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

в [4]) и способы выбора величины порога, которые можно разделить на две группы. К первой относятся способы выбора порога, зависящие от размерности входного массива, описывающего сигнал, и дисперсии шума (это универсальный порог [4], применимый и с мягкой, и с жесткой пороговой обработкой, и минимаксный порог [2], приминимый только с мягкой пороговой обработкой). Ко второй группе относятся способы выбора порога, при вычислении значения которых учитывается величина каждого элемента входного массива (это SURE-порог [1] и GCV-порог [3], применяющиеся с мягкой пороговой обработкой). Обычно результат обработки оценивается с помощью среднеквадратичной ошибки, отношения сигнал/шум и визуально.

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

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

Обрабатываемые фотографии можно приблизительно разделить на три класса по размеру исходного массива, описывающего изображение: малый (400400 пикселя), средний (12001200 пикселя) и большой (30894118 пикселей). Обработка улучшает соотношение сигнал/шум при любом размере входного массива. Однако размер массива существенно влияет на визуальное восприятие результата. При малом размере мелкие детали расплываются или теряются, появляются заметные артефакты.

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

Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года 1. Donoho D., Johnstone I. Adapting to unknown smoothness via wavelet shrinkage //J. Am. Statist. Assoc. 1995. 90. P. 1200–1224.

2. Donoho D., Johnstone I. Ideal spatial adaptation via wavelet shrinkage //Biometrika. 1994. 81. P. 425–455.

3. Jansen M. Wavelet thresholding and noise reduction. ISBN 90-5682-235Захарова Т. В., Шестаков О. В. Вейвлет-анализ и его приложения.

М.: Макс Пресс, 2009.

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

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

В работе рассматриваются различные подходы к построению скрытых марковских моделей, адекватно моделирующих сигналы ЭКГ [1]. Сюда входит рассмотрение некоторых вариантов топологий, таких, как полная модель и последовательная модель Бакиса, использование смесей гауссовских распределений в качестве наблюдаемых переменных и соответствия скрытых переменных и разметки сигнала.

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

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

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

Метод был реализован в среде Matlab и протестирован на реальных данных. Он показал адекватные в рамках задачи результаты, что подтвердило возможность применения скрытых марковских моделей для данной задачи.

1. Novak. D. Electrocardiogram Signal Processing using Hidden Markov Models. PhD thesis. Czech Technical University in Prague, Faculty of Electrical Engineering, Technicka 2, 166 27 Prague 6, Czech Republic, Разделение речевых потоков с помощью Кафедра математической статистики Научный руководитель: д.ф.-м.н., доц. Шестаков Олег Дипломная работа посвящена решению задачи слепого разделения источников применительно к разделению речевых потоков в смеси. Предполагается, что сигнал, полученный на датчиках некоторой автоматической системы обработки речи, представляет собой смесь нескольких источников и, кроме того, содержит шумы. Если нет никакой априорной информации о виде смеси, то такая задача называется задачей слепого разделения источников. Целью работы является разработка метода, позволяющего выделить из смеси исходные сигналы.

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

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

В работе приведены оценки качества, схожие по природе с величиной SNR (отношение сигнал-шум), но адаптированные к задаче разделения источников [3]. Наибольшее внимание уделено величине SIR (отношение источник-помехи), являющейся отношением мощности целевого источника к мощности прочих источников в полученной оценке целевого источника.

Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года В экспериментальной части дипломной работы описанный метод реализован в среде Matlab. В экспериментах с незашумленными данными объединенный метод показал результаты несколько хуже, чем обычные алгоритмы, реализующие ICA. Однако в экспериментах с данными, зашумленными на уровне 30-33 дБ, объединенный метод показал результаты, качество которых близко и даже превышает качество результатов обычных алгоритмов, что указывает на обоснованность его использования в реальных задачах. Кроме того, методы, подобные разработанному, могут применяться во многих иных задачах слепого разделения источников (см., например, [4]).

1. Matei B. A Review of Independent Component Analysis Techniques.

Electrical and Computer Engineering Department, Rutgers University, Piscataway, NJ, 08855-0909, USA.

2. Малла С. Вэйвлеты в обработке сигналов. Второе издание. М.: Мир, 3. Vincent E., Gribonval R., Fevotte C. Performance Measurement in Blind Audio Source Separation. IEEE Transactions on Audio, Speech and Language Processing, vol. 14, no. 4, pp.1462 -1469, 2006.

4. Azzerboni B., La Foresta F., Mammone N., Morabito F.C.

A New Approach Based On Wavelet-ICA Algorithms For Fetal Electrocardiogram Extraction. University of Messina, Italy, 2005.

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

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

В данной работе рассмотрен и программно реализован новый метод построения поверхности российского индекса волатильности с помощью процесса Variance-Gamma. Впервые этот процесс был определён в статье года «The Variance Gamma process and option pricing». Это стохастический процесс с тремя параметрами, который обобщает Броуновское движение.

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

В статье 1998 года было получено две формулы: риск-нейтральный процесс цены акции европейского call опциона и цена европейского call опциона на акцию, когда риск-нейтральная динамика цены акции задана с помощью процесса Variance Gamma с риск-нейтральными параметрами.

Построение поверхности российского индекса волатильности в помощью процесса Varianсe-Gamma осуществляется в несколько этапов:

1. Получение в реальном времени значений текущих цен таких контрактов, как Фьючерсный контракт на Индекс РТС, Маржируемый Опцион колл на фьючерсный контракт на Индекс РТС и Маржируемый Опцион пут на фьючерсный контракт на Индекс РТС. Рассматривались контракты с разными датами исполнения: 15.05.2013, 17.06.2013, 16.09.2013, 16.12.2013 и 17.03.2014.

2. С помощью процесса Variance-Gamma выполняются одновременно расчёты для построения поверхности: по полученным данным для всех страйков и для всех дат исполнения вычисляется цена опциона с использованием процесса Varianсe-Gamma. (Как в случае callопционов, так и в случае put-опционов).

3. Для каждой даты исполнения c помощью поиска решений в Excel вычисляются оптимальные параметры процесса Variance-Gamma.

4. По полученным данным вычисляются значения подразумеваемой волатильности с помощью модели Блэка-Шольца.

Данный способ построения поверхности - прост и понятен, в нём нет формул с засекреченными параметрами и непонятными функциями. В методе построения поверхности волатильности Фондовой биржи присутствует шесть (!) нигде не опубликованных параметров. В методе, основываемом на процессе Variance-Gamma параметров всего три: волатильность Броуновского движения, дисперсия гамма-изменений времени и сдвиг Броуновского движения. Таким образов, существенно сокращено необходимое количество расчётов для получения конечного результата. При окончательном построении поверхности российского индекса волатильности была учтена малая ликвидность российского рынка. Данный подход позволяет избежать очевидных ошибок, которые возникают из-за нехватки данных.

Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года При сравнении двух способов построения поверхностей волатильности были получены следующие результаты: Цены опционов, вычисленные по моделям RTS и Variance-Gamma, совпадают. Для опционов со средними страйками значение волатильностей совпадает, однако у опционов с крайними страйками есть расхождение в полученных результатах. В середине наблюдается максимальное совпадение, поскольку основные торги проходят как раз по опционам со средними страйками, и, значит, по ним достаточно информации.

1. Dilip B. Madan, Peter P. Carr, Eric C. Chang The Variance Gamma process and option pricing. М.:European Finance Review 2: 79-105, 1998.

2. статьи rts.micex.ru Российский индекс волатильности: комментарии разработчиков Анализ волатильности российского фондового рынка Просто о сложном: принципы расчета Российского индекса волатильности Методика расчета Индекса волатильности.

3. Ю.Г.Баласанов, А.Н.Дойников, М.Ф.Королёва, А.Ю.Юровский Прикладной анализ временных рядом с программой Эвриста. М.:Центр СП «Диалог» МГУ, 1991.

Криволинейный скелет полигональной Кафедра математических методов прогнозирования Научный руководитель: д.т.н., проф. Местецкий Леонид В дипломной работе рассматривается задача построения криволинейного скелета (curve-skeleton) для полигональной модели пространственного объекта. Криволинейный скелет представляет собой «проволочную модель» такого объекта. Это геометрический граф в трёхмерном пространстве, структура которого отображает геометрию и топологию исходного объекта. Криволинейные скелеты используются для решения различных прикладных задач, связанных с анализом формы трехмерных объектов [3], таких как скелетная анимация, виртуальная навигация в 3Dпространстве, извлечение признаков формы для задач классификации. В последнее время таких задач ставится все больше, что обусловлено появлением дешевых инструментов для сканирования объектов реального мира.

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

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

В рамках проведенного исследования предложена принципиально новая реализация известной идеи [4] итерационного утончения объекта. В работе предлагается новый метод для утончения объекта, основанный на построении по серединным осям плоских проекций облака точек, аппроксимирующего криволинейный скелет. Метод использует множество серединных осей проекций модели с разных ракурсов. Аппроксимация скелета облаком точек основана на погружении серединных осей плоских проекций внутрь модели. Полученное облако точек после этого подвергается фильтрации и уточнению на базе алгоритма Mean-Shift. Важную роль в фильтрации занимает использование визуальной оболочки (visual hull) [5], что позволяет избежать очень ресурсозатратного анализа полигонов модели.

Был проведен численный эксперимент на известной базе трехмерных моделей [3] с использованием программной реализации предлагаемого метода. Эксперимент показал достаточно высокое качество получаемых скелетов, что позволяет рассчитывать на использование разработанного метода в прикладных задачах. Метод показал в среднем 6-кратное ускорение вычислений по сравнению с известными методами. Алгоритм практически идеально масштабируется, что делает перспективным его реализацию на графических процессорах, что в свою очередь позволит использовать его в задачах реального времени.

Полученные оригинальные прикладные результаты опубликованы в статье на конференции «ИОИ-2012» [2]. Результаты работы нашли применение в рамках проекта РФФИ 11-01-00783.

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

фигуры, скелеты, циркуляры. — М.: ФИЗМАТЛИТ, 2009.

2. Зимовнов А. В., Местецкий Л. М. Построение криволинейного скелета пространственного объекта по проекциям с окклюзиями // Доклады 9-й международной конференции «Интеллектуализация обработки информации». — 2012. — с. 422Ц-425.

Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года 3. Cornea N. D., Silver D., Min P. Curve-skeleton applications // IEEE Visualization. — IEEE Computer Society, 2005. — P. 13.

4. Skeleton extraction by mesh contraction / O. K.-C. Au, C.-L. Tai, H.-K.

Chu et al. // ACM SIGGRAPH 2008 papers. — SIGGRAPH Т08. — New York, NY, USA: ACM, 2008. — Pp. 44:1–44:10.

5. Livesu M., Guggeri F., Scateni R. Reconstructing the curve-skeletons of 3d shapes using the visual hull // IEEE Trans. Vis. Comput. Graph. — 2012. — Vol. 18, no. 11. — Pp. 1891Ц-1901.

Бинарные функции многозначных аргументов. Минимизация их представлений в классе формул, обобщающих дизъюнктивно нормальные формы булевых Кафедра математических методов прогнозирования Научный руководитель: академик РАН Журавлев Юрий Данная работа посвящена обобщению теории дизъюнктивных нормальных форм на случай многозначного аргумента и бинарного множества значений функции, а также методу построения форм достаточно короткого вида для функций с малым числом нулей.

В работе рассматривается один из способов обобщения понятия элементарной конъюнкции на случай многозначного аргумента. Ранее такие попытки были предприняты в работах [2] и [3], однако, результаты этих работ было бы трудно применить для построения теории минимизации дизъюнктивных нормальных форм булевых функций с малым числом нулей. В качестве элементарной конъюнкции предлагается функция, принимающая значение 1 на таких наборах, для которых i i для любого i {1,..., n}, где i — фиксированное подмножество множества Ek, которое либо является замкнутым отрезком, либо является комбинацией двух замкнутых отрезков, содержащих элементы 0 и k 1. Вводятся определения, аналогичные определениям для бинарного случая, таким образом, чтобы существующая теория являлась частным случаем построенной.

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

Подробно рассматриваются свойства функции, которая принимает значение 0 только на наборах, для которых i = j для любых i и j. Эта функция часто используется для построения коротких форм для других функций с малым числом нулей. Для функции построена сокращенная дизъюнктивная нормальная форма, а также два вида достаточно коротких форм, отличающихся длиной в зависимости от значений n и k.

Для обоих видов форм доказана их тупиковость. Эти нормальные формы могут в дальнейшем использоваться в качестве базовых частей для построения коротких нормальных форм функций с малым числом нулей методом, подробно описанным в [1] для случая бинарного аргумента.

1. Журавлев Ю. И., Коган А. Ю. Реализация булевых функций с малым числом нулей дизъюнктивными нормальными формами и смежные задачи —Докл. АН СССР.—1985.—Т.285. №4.—C. 795–799.

2. Абдугалиев У. Ф. К вопросу представления функций k-значной логики нормальными формами —Дискретный анализ.—1969.—Т.15.—С.3Нурлыбаев А. Н. О нормальных формах k-значной логики —Сборник работ по математической кибернетике. М.: ВЦ АН СССР.—1976.— Т.1.—С.56-58.

4. Яблонский С. В. Введение в дискретную математику —M.: Наука, Дизъюнктивные нормальные формы специального вида для функций с малым Кириллов Александр Николаевич Кафедра математических методов прогнозирования Научный руководитель: д.ф.-м.н., проф. Дьяконов Во многих задачах, таких как построение алгоритмов распознавания, основанных на переборе конъюнкций или на выделении представительных наборов, встречается задача построения как можно более коротких дизъюнктивных нормальных форм (ДНФ) для функций с малым количеством нулей. В работе [1] представлен способ сведения этой задачи к построению ДНФ для полных функций с тем же количеством нулей. Матрица, построенная из наборов, на которых достигается ноль, называется нулевой матрицей функции. Полной функцией n переменных с k нулями называется функция, нулевая матрица которой состоит из 2k1 1 различных столбцов, причем среди них нет столбца, состоящего целиком из нулей или Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года единиц, а также для любого столбца в матрице, столбец, являющийся его почленным отрицанием, не входит в матрицу.

Важным требованием является возможность эффективного построения соответствующих ДНФ. Впервые методы, позволяющие строить достаточно простые ДНФ с применением алгоритмов, трудоемкость которых относительно невысока, были получены в работах [1, 2]. Метод, предложенный в работе [2], имеет высокую сложность реализации при больших k, что ограничивает возможности применения подобной техники.

В работе [3] был предложен алгоритм построения ДНФ полной функции. Длина полученной ДНФ для функции n переменных и k нулей состаk1)/ вила n + k 3k + Ck1. Для доказательства был использован аппарат околонулевых наборов. Околонулевыми наборами называются наборы, отличающиеся от нулевых лишь одним элементом.

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

Была доказана корректность формулы, а также тупиковость данной ДНФ.

Длина полученной ДНФ D полной функции n переменных с k нулями составляет ДНФ D является рекордной с точки зрения количества элементарных конъюнкции.

1. Журавлёв Ю. И., Коган А. Ю. Алгоритм построения дизъюнктивной нормальной формы, эквивалентной произведению левых частей булевых уравнений нельсоновского типа. Ж. вычисл. матем. и матем. физ. 41:5(2001), 821Ц828.

2. Журавлёв Ю. И., Коган А. Ю. Реализация булевых функций с малым числом нулей дизъюнктивными нормальными формами и смежные задачи. Докл. АН СССР. 285:4 (1985), 795Ц799.

3. Дьяконов А. Г. Реализация одного класса булевых функций с малым числом нулей тупиковыми дизъюнктивными нормальными формами. Ж. вычисл. матем. и матем. физ. 41:5(2001), 821Ц828.

Бинарные функции многозначных аргументов. Обобщения и исследования дизъюнктивных нормальных форм для таких Работа удостоена диплома II степени Кафедра математических методов прогнозирования Научный руководитель: академик РАН Журавлев Юрий Часто задачи распознавания с бинарными признаками [1], [2] сводятся к построению дизъюнктивных нормальных форм достаточно короткого вида функций с малым числом нулей. Как правило, данные ДНФ строятся методом, предложенным Ю. И. Журавлевым и А. Ю. Коганом [3], [4].

Метод основан на формуле, предложенной С. В. Яблонским. На практике признаки могут быть не бинарными. Использование бинарных функций k-значных аргументов позволяет уйти от этого ограничения.

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

Вводятся следующие понятия:

• Класс функций:

• Элементарная конъюнкция:

• Дизъюнктивная нормальная форма:

Ui - элементарная конъюнкция, i = 1, m Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года В работе доказывается ряд фундаментальных свойств описанных выше дизъюнктивных нормальных форм.

Рассматривается аналог функции Яблонского:

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

где S(m, i) - числа Стирлинга второго рода [5].

В работе удалось полностью перенести метод Ю. И. Журавлева и А.

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

1. Платоненко И. М. О реализации алгоритмов типа «Кора» с помощью решения систем булевых уравнений специального вида М.: ВЦ АН СССР, 1983.

2. Баскакова Л. В., Журавлев Ю. И. Модель распознающих алгоритмов с представительными наборами и системами опорных множеств Ж. вычисл. матем. и матем. физ., 1981.

3. Журавлёв Ю. И., Коган А. Ю. Реализация булевых функций с малым числом нулей дизъюнктивными нормальными формами и смежные задачи Докл. АН СССР, 1985.

4. Журавлёв Ю. И., Коган А. Ю. Алгоритм построения дизъюнктивной нормальной формы, эквивалентной произведению левых частей булевых уравнений нельсоновского типа Ж. вычисл. матем. и матем.

физ., 1986.

5. Rennie B. C., Dobson A. J. On stirling numbers of the second kind Journal of Combinatorial Theory, 1969.

Комбинаторные оценки обобщающей способности и их применение для построения композиций линейных Работа удостоена диплома I степени Кафедра математических методов прогнозирования Научный руководитель: д.ф.-м.н., доц. Воронцов Решение задач машинного обучения связано с принятием решений по неполной информации: имеется случайная конечная обучающая выборка объектов, и требуется из заданного множества алгоритмов выбрать тот, который ошибался бы как можно реже не только на объектах наблюдаемой обучающей выборки, но и на объектах скрытой контрольной выборки. Если частота ошибок на контрольной выборке оказывается значительно выше, чем на обучающей, то говорят, что произошло «переобучение» алгоритма — он слишком хорошо описывает конкретные данные, но не обладает способностью к их обобщению, не восстанавливает порождающую их зависимость и не пригоден для построения прогнозов.

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

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

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

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

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

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

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

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

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

Часть полученных результатов была представлена на конференциях «Ломоносов-2012» [3] и «ИОИ-2012» [4]. По материалам работы подана статья на конференцию «NIPS-2013».

1. Vorontsov K. V., Ivahnenko A. A. Tight combinatorial generalization bounds for threshold conjunction rules. // 4-th Int’l Conf. on Pattern Recognition and Machine Intelligence (PReMI’11). Lecture Notes in Computer Science. Springer-Verlag. 2011, 66–73.

2. Jin C., Wang L. Dimensionality Dependent PAC-Bayes Margin Bound.

// Advances in Neural Information Processing Systems, 2012, 25, 1043– 3. Соколов Е. А. Оценки вероятности переобучения и комбинаторные отступы в задачах классификации. // Сборник тезисов XIX Международной научной конференции «Ломоносов-2012». М.: МАКС Пресс, 2012, с.106-107.

4. Соколов Е. А., Воронцов К. В. Минимизация вероятности переобучения для композиций линейных классификаторов малой размерности.

// Сборник докладов 9-й международной конференции «Интеллектуализация обработки информации» М.: Торус Пресс, 2012, с. 82-85.

Системы точек с вырожденными матрицами Работа удостоена диплома III степени Кафедра математических методов прогнозирования Научный руководитель: д.ф-м.н., проф. Дьяконов Работа посвящена изучению свойства k-сингулярности, введённого в работе [1]. Система q попарно различных точек пространства Rm называется k-сингулярной, если размерность пространства значений полиномов (с поэлементным умножением) степени не выше k от столбцов матрицы попарных l1 -расстояний меньше q. Ясно, что 1-сингулярность эквивалентна вырожденности матриц попарных l1 -расстояний, а k-сингулярность — более сильное свойство, чем 1-сингулярность. Свойство k-сингулярности тесно связано с теорией интерполяции: система точек не является kсингулярной тогда и только тогда, когда любая функция на этой системе точек может быть представлена в виде суммы функций от k переменных.

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

В работе [2] доказан метрический критерий k-сингулярности: kсингулярность эквивалентна линейной зависимости системы функций k (, si ), i = 1,..., q, где вместо второго аргумента подставляются точки системы, а — метрика Хэмминга или l1 -метрика.

В дипломной работе приведено авторское доказательство метрического критерия k-сингулярности. На основе этого доказательства критерий обобщён на широкий класс метрик. Показано, что в качестве можно выбрать:

Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года • обобщённую метрику Хэмминга: (, y ) = i=1 di [xi = yi ], di > • обобщённую l1 -метрику: (, y ) = m d |xi yi |, d > 0, i = 1,..., m;

• сумму двух предыдущих метрик;

• полуметрики из конуса разрезных полуметрик CU T q [3], при этом формулировка критерия незначительно усложняется.

Важным фактом теории k-сингулярности является равенство линейных замыканий столбцов характеристической матрицы HS (ij-й элемент равен числу совпадающих координат у i-й и j-й точки системы S) и матрицы PS попарных расстояний Хэмминга системы точек. В доказательстве этого равенства из работы [1] неявно требуется, чтобы существовал вектор c с неотрицательными компонентами такой, что HS c = (без ограничения на знак компонент это верно всегда). В дипломной работе приведена система точек, для которой это предположение неверно.

Работа выполнена при поддержке гранта РФФИ №12-07-00187-a.

1. Дьяконов А. Г. Критерии вырожденности матрицы попарных l расстояний и их обобщения, Докл. РАН. 425:1 (2009), 11-14.

2. Карпович П. А. Критерии k-сингулярности и разделение 1сингулярных систем, Вестник Московского университета. Секция, 15. Вычислительная математика и кибернетика 34:4 (2010), 164-171.

3. Деза М. М., Лоран М. Геометрия разрезов и метрик. // М.: МЦНМО, 2001.

Криптоанализ криптосистемы Мак-Элиса, построенной на основе двоичных кодов Работа удостоена диплома I степени Кафедра математической кибернетики Научный руководитель: к.ф.-м.н., ассистент Чижов Иван В настоящее время важным аспектом криптографических исследований являются работы, посвященные криптосистемам с открытым ключом. Наиболее распространенными являются криптосистемы RSA и ЭльГамаля, стойкость которых основывается на известных проблемах в теории чисел. За последние годы бурное развитие теории чисел и возможное построение квантового компьютера актуализировали исследования альтернативных криптосистем. Одной из таких альтернатив являются кодовые криптосистемы, то есть криптосистемы, основанные на задачах из теории кодов, исправляющих ошибки. В настоящее время широкую известность получила криптосистема Мак-Элиса, оригинальная версия которой использует коды Гоппы. В 1994 году В.М. Сидельников в своей работе [2] предложил использовать для построения криптосистемы МакЭлиса коды Рида-Маллера, которые позволяют увеличить как скорость расшифрования криптограммы, так и скорость передачи криптосистемы.

В данной работе рассматриваются два разных способа восстановления секретного ключа по открытому ключу криптосистемы Мак-Элиса, основанной на двоичных кодах Рида-Маллера. Первый способ анализа основан на сведении задачи поиска секретного ключа криптосистемы Мак-Элиса к эквивалентной задаче ВЫПОЛНИМОСТЬ КНФ. Этот способ часто применяется для криптоанализа криптосистем с секретным ключом. Хотя задача ВЫПОЛНИМОСТЬ КНФ в общем случае является NP-трудной, существует большое число готовых программных продуктов, способных её решить. Такие продукты называются SAT-решателями, и среди них проводят множество международных конкурсов. В данной работе удалось описать и программно реализовать алгоритм со сложность O(n3 ) битовых операций, который строит эквивалентную криптосистеме КНФ. Верхние оценки на параметры полученной КНФ приведены в работе, так же приводятся параметры КНФ полученные при практических запусках алгоритма. Данный алгоритм позволяет использовать для криптоанализа криптосистемы вычислительные мощности суперкомпьютера без каких-либо доработок, нужно использовать подходящий параллельный SAT-решатель.

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

Второй способ криптоанализа опирается на алгоритм Л. Миндера и А.

Шокроллахи, предложенный ими в 2007 году в работе [3]. Этот алгоритм имеет субэкспоненциальную сложность. Идея, предложенная Л. Миндером и А. Шокроллахи, заключается в сведении задачи взлома криптосистемы с параметрами кода RM (r, m) к такой же задаче, но для кода RM (1, m). В данной работе предложен другой алгоритм сведения, который имеет полиномиальную сложность для некоторого подмножества кодов Рида-Маллера.

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

Теорема. Пусть НОД(r, m 1) = d > 1. Тогда существует алгоритм со сложностью O(nd + n4 log2 n) битовых операций, который по порожТезисы лучших дипломных работ факультета ВМК МГУ 2013 года дающей матрице кода RM (r, m) находит перестановку такую, что RM · (r, m) = RM (r, m).

Это означает, что для параметров кода RM (r, m) у которых НОД(r, m 1) ограничен, предложенная атака имеет полиномиальную сложность.

Теоретические результаты подтверждаются практическими исследованиями: алгоритм был реализован программно и запускался на ноутбуке с процессором 2,1 ГГц. Результаты приведены в таблице:

Результат Л. Миндера и А. Шокроллахи (процессор 2,4 ГГц):

1. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. Теория кодов, исправляющих ошибки. М.: Связь. 1979.

2. Сидельников В. М. Открытое шифрование на основе двоичных кодов Рида – Маллера. Дискретная математика. т. 6, 1994. № 2. С. 3–20.

3. Minder L., Shokrollahi A. Cryptanalysis of the Sidelnikov cryptosystem LNCS. 2007. V. 4515. P. 347–360.

Нижние оценки функции Шеннона длины проверяющего теста при константных неисправностях на выходах элементов в некоторых схемных базисах Работа удостоена диплома II степени Кафедра математической кибернетики Научный руководитель: к.ф.-м.н., доц. Романов Дмитрий В дипломной работе рассматриваются нижние оценки функции Шеннона длины проверяющего теста при константных неисправностях на выходах элементов в некоторых схемных базисах. Пусть f (n ) — произвольx ная булева функция, формально зависящая от переменных x1, x2,..., xn, а S — схема из функциональных элементов в некотором базисе B, реализующая функцию f. Пусть на схему S действует источник неисправностей U, способный вызывать какие-то поломки функциональных элементов (под поломкой или неисправностью элемента подразумевается функционирование элемента в режиме работы, отличном от исправного; при задании источника неисправностей количество вызываемых им поломок элементов может быть ограничено). Неисправностью схемы при этом называется совокупность поломок всех ее элементов. Считается, что действие источника неисправностей является единовременным, и в процессе исследования схемы на предмет анализа ее неисправности характер поломок элементов схемы не меняется. Константной называется такая неисправность на выходе функционального элемента, при которой функция, реализуемая на его выходе, заменяется на константу. (Источник неисправностей, вызывающий произвольные константные неисправности на выходах функциональных элементов, обозначим через U c ). Тривиальной будем называть такую неисправность схемы S, при которой значение на выходе любого элемента E неисправной схемы на всяком входном наборе равно значению на выходе этого же элемента E исходной схемы S (при отсутствии в ней неисправности). Неисправности, не являющиеся тривиальными, будем называть нетривиальными. Примерами тривиальной неисправности являются а) отсутствие неисправностей в схеме, б) неисправность типа константа “ на выходе функционального элемента, на выходе которого на всех входных наборах при исправной работе схемы возникает значение. Поскольку любую тривиальную неисправность схемы S нельзя обнаружить даже введением дополнительных контрольных точек в схеме, в дальнейшем будут рассматриваться только исходная схема и схемы, полученные из исходной под действием нетривиальных неисправностей.

Множество всех схем, полученных из схемы S под действием нетривиальных неисправностей (вызванных источником U ), обозначим через V U (S).

Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года Схемной целью контроля (для схемы S и источника неисправностей U ) называется некоторое множество Z неупорядоченных пар различных схем из множества {S} V U (S). Множество T наборов значений входных переменных схемы S называется тестом для схемы S относительно источника неисправностей U и схемной цели контроля Z тогда и только тогда, когда для любой пары схем (S, S ) из Z выполняется условие: если реализуемые схемами S, S функции f и f не равны, то найдется набор из T, для которого f () = f ( Количество различных наборов в тесте T называется его длиной и обозначается через l(T ) или через |T |. Тест минимальной длины называется минимальным. Тест относительно источника неисправностей, одновременно производящего не более одной поломки элемента в схеме называется единичным. Тест относительно цели контроля Z = {(S; S ) | S V U (S)} называется полным проверяющим тестом.

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

Пусть P2 — множество всех булевых функций f (n ), существенно заx висящих от каждой своей переменной (n N{0}, при n = 0 множество P2 n состоит из двух констант). Обозначим через DU (S) длину минимального единичного проверяющего теста относительно источника неисправностей U в схеме S, через DB, U (f (n )) — минимум величины DU по всем тестопригодным реализующим f ( ) схемам S в базисе B. Через detect DB, U (n) обозначим функцию Шеннона длины единичного проверяющего теста относительно источника неисправностей U, т. е. функцию Д.С. Романовым в [2]-[3] устанавливается, что длина минимального единичного проверяющего теста относительно инверсных и произвольных константных неисправностей на выходах элементов в произвольном полном базисе для каждой неконстантной булевой функции лежит в пределах от 2 до 4.

В дипломной работе получен следующий результат:

Теорема. Для схем из функциональных элементов в любом конечном полном базисе B с не более чем 2 входами нижняя оценка функции Шеннона длины единичного проверяющего теста относительно произвольных константных неисправностей на выходах элементов не меньше 3: DB, U (n) 3 при n 3.

1. Редькин Н. П. Надежность и диагностика схем. М.: Моск. университет, 2. Романов Д. С. Об оценках функции Шеннона длины единичного проверяющего теста относительно произвольных константных неисправностей на выходах элементов // Материалы XI Международного семинара "Дискретная математика и ее приложения посвященного 80-летию со дня рождения академика О. Б. Лупанова (Москва, МГУ, 18-23 июня 2012 г.). М.: Изд-во мех.-мат. ф-та МГУ, 2012. С. 160-163.

3. Романов Д. С. Метод синтеза легкотестируемых схем в одном базисе, допускающих единичные проверяющие тесты константной длины. Вестник Моск. ун-та. Матем. Механ. 2012. № 2, С. 24-29.

4. Бородина Ю. В. О синтезе легкотестируемых схем в случае однотипных константных неисправностей на выходах элементов. Вестник Моск. ун-та. — 2008. — Серия 15. Вычислит. матем. и киберн.

5. Бородина Ю. В. О схемах, допускающих единичные тесты длины при константных неисправностях на выходах элементов. Вестник Моск. ун-та. — 2008. — Серия 1. Матем. Механика. — № 5, С. 49-52.

Выделение полупрозрачных частиц переднего плана в видео на основе анализа Акимов Дмитрий Александрович Кафедра автоматизации систем вычислительных комплексов email: [email protected] Научный руководитель: к.ф.-м.н., c.н.с. Ватолин Дмитрий Рис. 1. Пример особо сложной для обработки сцены (а) с большим количеством небольших полупрозрачных объектов переднего плана и карта глубины (б), созданная с применением предложенного метода.

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

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

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

В работе принимается предположение, что вся сцена находится после области фокусировки, на переднем плане располагаются искомые частицы. В данных рамках размытие границ объектов переднего плана возможно аппроксимировать как сглаживание фильтром Гаусса с неизвестным параметром и оценить на основе сравнения с переразмытым изображением [1].

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

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

Работа была частично поддержана грантом РФФИ 10-01-00697-a и совместным грантом компаний Intel и Cisco. По результатам были сделаны публикации [2, 3, 4] и доклады на конференциях «ГрафиКон’11», «Ломоносов-2011» и «Ломоносов-2013».

1. Zhuo S., Sim T. On the Recovery of Depth from a Single Defocused Image // Proceedings of the 13th International Conference on Computer Analysis of Images and Patterns, 2009, P. 889–897.

2. Akimov D., Vatolin D., Smirnov M. Single-Image Depth Map Estimation Using Blur Information // 21st GraphiCon International Conference on Computer Graphics and Vision, 2011, P. 12–15.

3. Акимов Д. А. Методы восстановления карты глубины сцены по одному изображению // Материалы XVIII Международной конференции студентов, аспирантов и молодых ученых «Ломоносов». 2011.

T. IV:Вычислительная математика и кибернетика. Компьютерная графика. C. 65–57.

4. Акимов Д. А. Выделение полупрозрачных частиц переднего плана в видео на основе анализа резкости кадра // Материалы XX Международной конференции студентов, аспирантов и молодых ученых «Ломоносов». 2013. T. IV:Вычислительная математика и кибернетика. Компьютерная графика. C. 91–93.

Применение метамоделей для задачи выбора механизмов обеспечения отказоустойчивости распределенных вычислительных систем реального времени Кафедра автоматизации систем вычислительных комплексов Научный руководитель: ассистент Волканов Дмитрий Одним из способов повышения надёжности распределённых вычислительных систем реального времени (РВС РВ) является использование механизмов обеспечения отказоустойчивости (МОО) [1], то есть добавление в систему избыточных ресурсов, позволяющих предотвратить отказ.

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

Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года РВС РВ состоит из нескольких взаимодействующих между собой модулей. Структура РВС РВ задаётся в виде ориентированного ациклического графа, вершины которого соответствуют программным компонентам модулей, а дуги — зависимостям по данным. Для каждого модуля заданы доступные МОО. Каждый модуль содержит не менее одной версии аппаратного и программного компонента (количество версий зависит от МОО). Известны наборы версий аппаратных и программных компонентов и МОО, которые можно использовать в модуле. Каждая версия аппаратного или программного компонента характеризуется надежностью и стоимостью. Для каждой пары (версия аппаратного компонента, версия программного компонента) известно время выполнения. Известен объем данных, передаваемых вдоль дуг графа зависимостей по данным. Работа программного компонента модуля считается завершённой, если его выходные данные полностью переданы всем зависящим от него компонентам. Программный компонент не может начать выполнение до тех пор, пока не получит данные от других компонентов, от которых он зависит.

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

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

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

Данная задача решается с помощью адаптивного гибридного эволюционного алгоритма (АГЭА) [2], в ходе работы которого приходится многократно вычислять время завершения работы программ для различных конфигураций РВС РВ. Для вычисления этого времени проводятся имитационные эксперименты, имеющие большую по сравнению с АГЭА вычислительную сложность: эксперименты показали, что 99% времени работы АГЭА приходятся на вычисление времени.

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

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

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

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

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

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

1. Wattanapongsakorn N., Coit D. W. Fault-tolerant embedded system design and optimization considering reliability estimation uncertainty.

Reliability Engineering and System Safety. 2007. 92. P.395–407.

2. Волканов Д. Ю., Глонина А. Б. Исследование модификаций адаптивного гибридного эволюционного алгоритма для задачи сбалансированного выбора модулей РВС РВ и их механизмов обеспечения отказоустойчивости. Программные системы и инструменты. Тематический сборник №12, М.: Изд-во факультета ВМК МГУ, 2011., С.150–162.

3. Knowles J., Nakayama H. Meta-modeling in multi-objective optimization.

Multi-objective Optimization — Interactive and Evolutionary Approaches. Springer LNCS 5252, 2008. P.245–284.

Разработка стабильного во времени метода анализа прозрачности границ объектов Кафедра автоматизации систем вычислительных комплексов email: [email protected] Научный руководитель: к.ф.-м.н., c. н. с. Ватолин Одной из ключевых задач, возникающих при редактировании и монтаже изображений и видеопоследовательностей, является построение карты прозрачности (матирования) объекта переднего плана для последующей замены фона или изменения положения объекта относительно фона. Необходимость построения карты прозрачности, а не бинарной маски объекта, обусловлена: конечностью разрешающей способности сенсора, несфокусированностью камеры на границе объекта, быстрым движением снимаемого объекта, действительной полупрозрачностью объекта (волосы, шерсть).

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

передний план (F ), карту прозрачности () и фон (B) — таким образом, чтобы для всех точек изображения выполнялось условие:

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

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

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

Для измерения качества решения, находимого предложенным методом, была сформирована тестовая выборка, содержащая входные данные и эталонные решения для них.

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

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

Составленная выборка была использована для проведения объективного сравнения предложенного метода с алгоритмом разделяемого сэмплирования и алгоритмом аналитического решения задачи матирования.

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

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

Стандартное отклонение ошибки 1. Gastal Eduardo S. L. Shared Sampling for Real-Time Alpha Matting // Computer Graphics Forum, 2010, pp. 575–584.

2. Levin A. Closed-Form Solution to Natural Image Matting // Pattern Analysis and Machine Intelligence, 2008, pp. 228–242.

учетом требований отказоустойчивости Кафедра автоматизации систем вычислительных комплексов Научные руководители: Пашков Василий Николаевич, чл.-корр. РАН Смелянский Руслан Леонидович Программно-конфигурируемые сети (ПКС, Software Dened Networks, SDN) [1] — подход к архитектуре компьютерных сетей, предложенный учеными университетов Стэнфорда и Беркли в качестве альтернативы традиционным сетям. ПКС предполагает разделение функций управления сетью и передачи данных. Реализация функции передачи данных остается Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года в сетевом оборудовании (коммутаторах), а управление сетью осуществляется контроллером ПКС и работающими на нем приложениями. Взаимодействие между контроллерами и сетевым оборудованием происходит по открытому протоколу, что позволяет не зависеть от внутреннего устройства сетевого оборудования.

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

Таким образом, возникает следующая задача размещения контроллеров в ПКС с учетом резервирования контроллеров.

Пусть дана сеть из S коммутаторов с зафиксированной топологией, которая представлена в виде графа, а также известны задержки для всех соединений сети. Данная сеть может управляться несколькими контроллерами, каждый из которых присоединяется к одному из коммутаторов.

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

Необходимо найти размещение C = Nmax + 1 контроллеров в сети и разбить сеть на сегменты, каждый из которых управляется одним контроллером, так, чтобы: а) в каждом сегменте было не более Nmax коммутаторов; б) средняя/максимальная задержка между коммутатором и основным контроллером была минимальной; в) между каждой парой контроллеров существовало хотя бы два пути, не имеющих общих коммутаторов и соединений.

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

б) средняя/максимальная задержка между коммутатором и резервным контроллером была минимальной.

Для решения поставленной задачи предложен следующий метод:

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

2. При помощи метода кластеризации k-средних [2] сеть разбивается на сегменты. Центры сегментов выбираются внутри одной компоненты двухсвязности и совпадают с местами размещения контроллеров.

Выбор начальных центров сегментов осуществляется при помощи алгоритма k-means++ [3].

3. Задача выбора резервного контроллера для коммутатора сводится к задаче булевского линейного программирования, для решения которой используется аддитивный алгоритм (метод Балаша) [4].

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

Разработанный метод реализован в виде программного средства. Экспериментальное исследование предложенного метода проведено на топологиях реальных магистральных сетей (от 20 до 60 коммутаторов) из библиотеки Internet Topology Zoo [6]. Эксперименты показали, что использование аддитивного алгоритма для решения задачи выбора резервного контроллера ограничивает область применения разработанного метода сетями среднего размера (до 50 коммутаторов). В качестве возможного направления дальнейших исследований можно указать исследование применимости приближенных алгоритмов для решения задачи определения резервного контроллера, что позволит расширить область применения метода на сети, состоящие из большого количества узлов.

1. Software-Dened Networking: The New Norm for Networks / ONF White Paper. 2012.

2. MacQueen James [и др.]. Some Methods for Classication and Analysis of Multivariate Observations // Proceedings of the fth Berkeley symposium on mathematical statistics and probability / California, USA.

3. Arthur David, Vassilvitskii Sergei. k-means++: The Advantages of Careful Seeding // Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms / Society for Industrial and Applied Mathematics. 2007.

4. Balas Egon, Glover Fred, Zionts Stanley. An Additive Algorithm for Solving Linear Programs with Zero-One Variables // Operations Research. 1965.

Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года 5. Internet Topology Zoo: http://www.topology-zoo.org.

Применение методов глубокого обучения для распознавания изображений Кафедра автоматизации систем вычислительных комплексов email: [email protected] Научный руководитель: к.ф.-м.н., н.с. Конушин Антон Задача распознавания изображений является одной из основных задач компьютерного зрения. Она заключается в поиске на изображении объектов, принадлежащих одному из заранее определенных классов, и определения метки класса для каждого из найденных объектов. В дипломной работе в качестве модели для задачи распознавания было решено использовать задачу распознавания знаков дорожного движения ввиду ее актуальности и достаточной сложности.

Идея методов глубокого обучения состоит в применении глубоких нейронных сетей, то есть сетей, имеющих больше двух внутренних слоев. До недавнего времени применение глубоких нейронных сетей было сильно ограничено, пока в 2006 году не были придуманы эффективные методы обучения таких нейронных сетей [1]. На многих задачах компьютерного зрения глубокие нейронные сети показали свое преимущество над другими методами.

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

На этапе обнаружения обычно используется каскад классификаторов [2]. Каскад представляет собой цепочку классификаторов, где каждый классификатор определяет, является ли текущее изображение изображением целевого объекта и, если является, то оно передается на вход следующему классификатору в каскаде; если же не является, то текущее изображение отбрасывается. Изображения, которые были приняты всеми классификаторами в каскаде, считаются изображениями целевых объектов. Для достижения высокой скорости работы желательно, чтобы на первых этапах каскада использовались простые (т.е. быстрые для подсчета) классификаторы и отбрасывалось как можно больше изображений фона.

Идея применения методов глубокого обучения на этапе обнаружения заключается в добавлении глубокой нейронной сети в качестве последнеКафедра АСВК го этапа каскада. Это позволяет, с одной стороны, не терять в скорости работы (а на практике получается даже прирост скорости на 10–15%) и, с другой стороны, повысить точность обнаружения. Каскад строится таким образом, чтобы число ложных обнаружений не превосходило 109. Это значение было выбрано из практических соображений и означает не более одного ложного срабатывания на 100 изображений размера 1280х1024.

Затем для построенных каскадов сравнивается доля найденных целевых объектов. Как показали эксперименты, по этому показателю каскад, включающий в себя глубокую нейронную сеть, превосходит каскад, построенный без использования глубокой нейронной сети, на 6–10%.

На этапе классификации также используется глубокая нейронная сеть.

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

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

В ходе работы была написана программная реализация основных методов глубокого обучения в среде Microsoft Visual Studio 2010 с использованием языков программирования C++ и CUDA C.

1. Hinton G. E., Osindero S., Teh Y. A fast learning algorithm for deep belief nets. Neural Computation. 2006. N 18. P 1527-1554.

2. Viola P., Jones M. Robust real-time face detection. International Journal of Computer Vision. 2004. N 57. P 137-154.

Методы распознавания текста на фотографиях с мобильных устройств Кафедра автоматизации систем вычислительных комплексов Научный руководитель: к.ф.-м.н., м.н.с. Баринова Ольга Большое количество изображений содержат в себе текстовую информацию, автоматизированное извлечение которой находит применение в разнообразных приложениях, таких как автоматический перевод текста на фотографиях с иностранного языка, аннотация фотографий в интернете, поиск по изображениям, фильтрация спама на изображениях в интернете и других. Причем задача распознавания текста на изображениях, Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года полученных с мобильных устройств (таких как телефоны, планшетные компьютеры, фотоаппараты), является значительно более сложной, чем задача распознавания текста на отсканированных документах, в связи с низким качеством входных данных. Данная работы посвящена методам распознавания текста на фотографиях, полученных с помощью мобильных устройств.

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

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

1. Neumann L., Matas J. Real-Time Scene Text Localization and Recognition. // Conference on Computer Vision and Pattern Recognition (CVPR) P. 150-157, 2012.

2. Wang K., Babenko B., Belongie S. End-to-end scene text recognition.

// International Conference on Computer Vision (ICCV) P. 1457-1464, Поиск возможностей распараллеливания в программах множественного выравнивания и сравнение эффективностей параллельных Научный руководитель: к.ф.-м.н., с.н.с. Сальников Алексей Алгоритмы множественного выравнивания представляют собой инструмент для установления функциональных, структурных или эволюционных взаимосвязей между биологическими последовательностями.

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

В работе произведен обзор наиболее популярных параллельных алгоритмов множественного выравнивания: СlustalW-MPI, Parallel T-Coee, MSAProbs, MSA-CUDA. Даны и экспериментально подтверждены оценки сложности алгоритмов, проведены тесты производительности и качества выравнивания. Для тестирования алгоритмов был взят известный биоинформатический бенчмарк BENCH. Качество выравнивания измерялось с помощью утилиты qscore входящей в состав бенчмарка.

После проведения обзора, для дальнейшего исследования и создания параллельной реализации был выбран алгоритм ClustalW(в его последней модификации ClustalW2), ввиду того что он: завоевал доверие биологов по всему миру; обладает простым и понятным С++ кодом, относительно конкурентов; показывает высокую скорость работы среди рассмотренных алгоритмов.

Алгоритм ClustalW2 выполняется в три этапа. На первом этапе, последовательности выравниваются попарно все-со-всеми. Для этого применяются алгоритмы Смита-Ватермана (Smith - Waterman)[2] и МайерсаМиллера (Myers & Miller)[3]. Результат записывается в матрицу расстояний. Далее, по матрице расстояний строится направляющее дерево. На третьем этапе, в порядке заданном деревом строится множественное выТезисы лучших дипломных работ факультета ВМК МГУ 2013 года равнивание.

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

Разработанная параллельная реализация использует архитектуру главный-подчинённые(master-slave) и технологию MPI. Для межпроцессорного взаимодействия на распределенной памяти были использованы коммуникационные примитивы стандарта MPI-2. Каждый процессор вычисляет свою порцию матрицы расстояний и записывает результат. Позже результат отправляется на мастер-узел.

Для распределения порций между узлами используется алгоритм динамического планирования Variable Increase, который показал хорошие результаты на тестах производительности[4]. Алгоритм использует стратегию увеличения порции, за счет чего количество шагов планирования сокращается, а так же уменьшаются накладные расходы на передачу порций. В результате применения Variable Increase удалось увеличить скорость работы параллельной реализации алгоритма ClustalW2 по сравнению с ClustalW-MPI на 20%.

Промежуточные результаты работы были отправлены на конференцию «EuroMPI-2013» секция «Bioinformatics». Возможным направлением дальнейших исследований является параллельная реализация внутренних алгоритмов первого этапа работы ClustalW2 на GPU с помощью технологии CUDA.

Исходный код параллельной реализации ClustalW2 доступен любому желающему по адресу https://github.com/sochix/parallel-clustalw 1. Lloyd G. S. Parallel Multiple Sequence Alignment: An Overview Retrieved March. Ц 2010. Ц Т. 24. Ц С. 2012.

2. Smith T. F., Waterman M. S. Comparison of biosequences Advances in Applied Mathematics. Ц 1981. Ц Т. 2. Ц №. 4. Ц С. 482-489.

3. Myers E. W., Miller W. Optimal alignments in linear space Computer applications in the biosciences: CABIOS. Ц 1988. Ц Т. 4. Ц №. 1. Ц С.

4. Philip T., Das C. R. Evaluation of loop scheduling algorithms on distributed memory systems Pennsylvania State University, Department of Computer Science and Engineering, College of Engineering, 1996.

Исследование возможности обнаружения вредоносного исполнимого кода на основе остовных последовательностей Кафедра автоматизации систем вычислительных комплексов Научный руководитель: к.ф.-м.н., с.н.с. Гамаюнов Денис Целью данной работы является разработка и реализация метода динамического анализа исполнимого кода и его бинарной классификации на вредоносный и нормальный.

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

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

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

Чтобы эвристика смогла обнаружить атаку необходимо, чтобы атака была проведена успешно. Однако многие злоумышленники применяют техники, которые препятствуют анализу и могут менять поведение Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года вредоносного кода на легитимное, если определят, что выполняются на виртуальной машине [2]. Поэтому, в реализованном методе применяются техники защиты от обнаружения выполнения на виртуальной машине.

Проведённое тестирование реализации показывает отсутствие ложных срабатываний на легитимных данных. Эксперименты на вредоносных образцах, соответствующих определяемому классу атак, выявили полноту обнаружения вредоносного кода 93%. Эксперименты на коллекции вредоносных файлов VxHeavens показали наличие 38% образцов, соответствующих описанному в дипломной работе вредоносному поведению.

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

1. Michalis Polychronakis, Kostas G. Anagnostakis, Evangelos P. Markatos.

Comprehensive Shellcode Detection using Runtime Heuristics. the 26th Annual Computer Security Applications Conference (ACSAC).

December 2010.

2. Lindorfer, M., Kolbitsch, C., Comparetti, P.M. Detecting EnvironmentSensitive Malware. the 14th international conference on Recent Advances in Intrusion Detection, 2011.

3. J. Ma, J. Dunagan, H. J. Wang, S. Savage, and G. M. Voelker. Finding diversity in remote code injection exploits. the 6th Internet Measurement Conference (IMC), 2006.

4. M. Shimamura, K. Kono. Yataglass: Network-level code emulation for analyzing memory-scanning attacks. DIMVA ’09 Proceedings of the 6th International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment, 2009.

5. Ruoxu Zhao, Dawu Gu, Juanru Li, Hui Liu. Detecting Encryption Functions via Process Emulation and IL-Based Program Analysis. the 14th international conference on Information and Communications Security, October 2012.

Обнаружение вредоносных Flash-баннеров Кафедра автоматизации систем вычислительных комплексов Научный руководитель: м.н.с Петухов Андрей Дипломная работа посвящена задаче обнаружения вредоносного программного обеспечения, актуальной в области информационной безопасности. Более конкретно, обнаружению вредоносных приложений, написанных для браузерного плагина Adobe Flash Player.

Большинство существующих методов обнаружения вредоносных Flashприложений основаны на поиске известных фрагментов вредоносного кода методом статического анализа (т.н. сигнатурный метод) и динамическом анализе трасс выполнения приложения с целью поиска известных вредоносных последовательностей вызовов (т.н. обнаружение эксплуатации уязвимостей). В некоторых случаях динамический анализ проводится в специальном окружении, например, система Wepawet анализирует Flash-приложения с помощью выполнения в специально модифицированном Flash-плагине [1]. Основным недостатком такого подхода является то, что стандартный плагин Adobe Flash Player нельзя модифицировать в силу его проприетарности, а все остальные плагины поддерживают не всю функциональность, предоставляемую стандартным плагином. Данное обстоятельство приводит к тому, что ключевым ограничением (хоть и техническим) систем, основанных на этом подходе, является то, что модифицированные среды легко обнаруживаются злоумышленниками.

С целью преодоления подобного недостатка в данной работе предлагается использовать динамический анализ с помощью модификации Flashприложения и последующего выполнения в стандартном плагине. Подобный анализ возможен в силу того, что бинарный код Flash-приложения не может быть изменен при выполнении, и того, что Flash-приложение не может получить доступ к своему коду. Следовательно, при модификации исходного кода перед выполнением покрывается весь потенциально исполняемый код Flash-приложения, которое при выполнении не сможет обнаружить изменение своего кода. Модификация Flash-приложений проводится с помощью средства RABCDasm [2]. Все обращения к необходимым для анализа системным классам модифицируются таким образом, что в ходе выполнения Flash-баннера становится возможным анализ вызовов методов этих классов и их параметров. На основе трассы из подобных вызовов и статического анализа бинарного кода Flash-баннеры классифицируются на вредоносные и легитимные.

Предложенные методы анализа реализованы в виде среды для анализа Flash-баннеров на вредоносность. В ходе тестирования полученное Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года средство было обучено на основе Flash-баннеров, находящихся в рейтиге Alexa top 500, а затем протестировано на образцах вредоносных Flashприложений, полученных от команды Безопасного Поиска Яндекса. В результате тестирования средство сумело обнаружить не только известные для него классы вредоносных Flash-приложений по прямым характеристикам вредоносности, но и другие классы вредоносных Flash-баннеров с помощью таких косвенных признаков как обфускация и определение окружения.

Результаты работы докладывались на конференции ZeroNights 2012 и опубликованы в журнале Хакер [3].

[PDF] (http://www.cs.bham.ac.uk/~covam/data/papers/acsac09_ash.pdf) 2. Пантелеев В. Robust ABC (ActionScript Bytecode) [Dis-]Assembler [HTML] (https://github.com/CyberShadow/RABCDAsm) 3. Петухов А., Самосадный К. CSRF В МАССЫ! или Фреймворк для проведения массовых атак через баннерные сети Хакер, №1 (168), Москва, 2013, с. 86–88.