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

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

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

Целью дипломной работы стало создание двух систем: системы преобразования видеопотока из стереоформата в формат 2D+Z, который используется в некоторых автостереоскопических телевизорах, и системы оценки качества стереоскопического видео. Обе системы существенно используют решение задачи сопоставления ракурсов стереоизображения; использование алгоритма сопоставления ракурсов в этих системах наложило ограничение на скорость работы: обработка кадра стандартного разрешения (640360 пикселей) должна происходить в реальном времени.

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

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

Предложенные улучшения базового алгоритма были направлены на дальнейшее ускорение вычисления оптического потока без потери качества сопоставления. Было предложено строить набор векторовкандидатов для последующего вычисления оптического потока не для всего изображения, а для макроблоков изображения. Кроме того, были предложены фильтрация векторов-кандидатов по метрике доверия и использование дополнительной пространственно-временной информации. Ускорение алгоритма составило в среднем 2–3 раза по сравнению с базовым на предложенном тестовом наборе из 21 видеопоследовательности.

Создание алгоритма сопоставления ракурсов стереопары, обрабатывающего видеопоток в стереоформате в реальном времени, сделало возможным построение системы преобразования видеопотока из стереоформата в формат 2D+Z. Система была продемонстрирована на стенде ВМиК на Фестивале Науки 2012. Демонстрационная установка состояла из двух видеокамер (которые образовывали стереокамеру), компьютера и многоракурсного монитора; на мониторе демонстрировалось объёмное изображение, полученное с помощью стереокамеры.

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

В результате этой работы было измерено качество 15 стереофильмов, выпущенных в последнее время на Blu-ray 3D дисках. Также было произведено измерение качества фильмов-участников конкурсной программы III Московского Международного Стереофестиваля. Эти результаты подТезисы лучших дипломных работ факультета ВМК МГУ 2013 года твердили практичность предложенной системы.

Создание двух систем, использующих предложенный алгоритм сопоставления ракурсов стереоизображения, показало его практичность. По результатам работы были сделаны публикации [2, 3, 4] и доклад на конференции «Запись и воспроизведение объемных изображений в кинематографе и других отраслях». Работа была частично поддержана грантом РФФИ 10-01-00697-а и совместным грантом компаний Intel и Cisco.

1. Ogale A., Aloimonos Y. A roadmap to the integration of early visual modules. International Journal of Computer Vision: Special Issue on Early Cognitive Vision. 2007. Vol. 72, №1, P. 9-25.

2. Voronov A., Vatolin D., Sumin D., Napadovsky V., Borisov A. Towards Automatic Stereo-video Quality Assessment and Detection of Color and Sharpness Mismatch. International Conference on 3D Imaging (IC3D), 3. Voronov A., Vatolin D., Sumin D., Napadovsky V., Borisov A.

Methodology for stereoscopic motion-picture quality assessment. Proc.

SPIE 8648, IS&T/SPIE Electronic Imaging, Stereoscopic Displays and Applications XXIV, 864810.

4. Сумин Д. А. Метод быстрого построения оптического потока в применении к задаче сопоставления ракурсов стереоизображения.

«Ломоносов-2013», Москва, 2013.

Распознавание объектов городских сцен в облаках трёхмерных точек Работа удостоена диплома III степени Кафедра автоматизации систем вычислительных комплексов email: [email protected] Научный руководитель: к.ф.-м.н., н.с. Конушин Антон Бесконтактное лазерное сканирование является на сегодняшний день новейшей технологией, и несмотря на относительно небольшой срок своего существования, уже нашло своё применение во многих отраслях человеческой деятельности, таких как индустрия производства, игровая и кино индустрия. 3D-сканер это устройство, анализирующее объекты реального мира или окружающую среду с целью сбора информации об их геометрических свойствах и возможно некоторых других характеристик, таких как цвет. Результатом сканирования являются облака трёхмерных точек - набор вершин в трёхмерной системе координат. Эти вершины определяются координатами x, y, z и предназначены для представления внешней поверхности объекта.

';

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

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

• распознавание объектов находящихся в отсканированной сцене, (является важной задачей для навигации мобильных роботов и развития робототехники в целом);

• анализ состояния объекта, например, для обнаружения повреждений;

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

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

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

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

Проведено исследование вопроса по улучшению обобщающей способности данной системы. В ходе работы была создана программная реализация Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года метода называемого неявная модель формы [4] (подсистема, отвечающая за детектирование объектов), которая была встроена в библиотеку с открытым кодом Point Cloud Library. Была произведена разметка реальных данных, на которых впоследствии тестировалась система. В дипломной работе приводятся результаты работы системы распознавания, а также сравнение выявленных факторов влияющих на обобщающую способность системы. Экспериментальные результаты показали превосходство разработанной системы над существующими аналогами. Данная работа получила поддержку со стороны компании Honda и будет продолжена в ходе спринта кода Honda Research Institute Code Sprint организованном совместно с библиотекой Point Cloud Library.

1. Golovinskiy A., Kim V. G., Funkhouser T. Shape-based recognition of 3d point clouds in urban environments. // IEEE 12th International Conference on Computer Vision. 2009. P. 2154-2161.

2. Velizhev A., Shapovalov R., Schindler K. Implicit shape models for object detection in 3D point clouds. // International Society of Photogrammetry and Remote Sensing Congress. 2012.

3. Golovinskiy A., Funkhouser T. Min-cut based segmentation of point clouds. // IEEE 12th International Conference on Computer Vision Workshops (ICCV Workshops). 2009. P. 39-46.

4. Knopp J., Prasad M., Willems G., Timofte R., Van Gool L. Hough transform and 3D SURF for robust three dimensional classication. // 11th European Conference on Computer Vision. 2010. Part VI. P. 589Сопровождение людей в Работа удостоена диплома III степени Кафедра автоматизации систем вычислительных комплесков email: [email protected] Научный руководитель: к.ф.-м.н., н.с. Конушин Антон В работе рассматривается задача автоматического сопровождения людей в видеопоследовательности, снятой статичной камерой. Формально описываемая задача имеет следующую постановку:

• на вход алгоритму подается видеопоследовательность {It }N, снятая статичной камерой с матрицей калибровки C;

• выходом алгорима является множество прямоугольников t=0,k=0, каждый из которых ограничивает изображение человека Pk на кадре It входной видеопоследовательности.

В работе предлагается развитие алгоритма сопровождения через обнаружение Benfold и др. [1]. Предлагаются следующие мофицикации базового алгоритма:

1. Фильтрация обнаружений по их размерам в мировых координатах;

2. Использование более надежного алгоритма визуального сопровождения для построения треклетов;

3. Модификация способа оценки положения следующего треклета в траектории по информации о положении предыдущего.

Предлагаемый алгоритм состоит из четырех шагов: 1) поиск людей на ключевых кадрах видеопоследовательностиж 2) построение треклетов 3) построение траекторий сопровождаемых людей 4) восстановление положения людей на кадрах, где они не были обнаружены.

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

Информация о движении очень важна для построения надежных траекторий сопровождаемых людей. Поэтому для каждого обнаруженного на первом шаге человека строится треклет, объединяющий информацию о его положении и скорости движения на соседних кадрах. Для построения оценок скорости используются алгоритмы визуального сопровождения. Мои эксперименты показали, что алгоритм KLT, используемый для построения треклетов в работе Benfold и др. [1], является недостаточно надежным для получения качественных оценок скорости. Поэтому предлагается использовать алгоритмы «Стая точек» [3] или алгоритм на основе нормализованной кросс-корреляции шаблонов [4].

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

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

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

1. Benfold B., Reid I. Stable Multi-Target Tracking in Real-Time Surveillance Video // Computer Vision and Pattern Recognition. 2011.

C. 3457–3464.

(http://www.robots.ox.ac.uk/ prisacariu_reid_tr2310_09.pdf).

3. Klsch M., Turk M. Fast 2D hand Tracking with Flocks of Features and Multi-Cue Integration // Computer Vision and Pattern Recognition Workshop. 2004. C. 158.

4. Freeman W., Anderson D., Beardsley P., Dodge C., Roth M., Weissman C., Yerazunus W., Kage H., Kyuma K., Miyake Y., Tanaka K.

Computer Vision for Interactive Computer Graphics // IEEE Computer Graphics and Applications. 1998. 18. №3. С. 42-53.

5. Oh S., Russell S., Sastry S. Markov chain monte carlo data association for general multiple-target tracking problems // Decision and Control.

2004. 1. №43. С. 735-742.

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

Правило для каждого типа связи представляет собой логическую функцию, зависящую от пары слов предложения. Её результат означает, соединены ли данные слова связью соответствующего типа. Генерируемые правила должны быть достаточно эффективными и с точки зрения точности, и с точки зрения полноты. Чтобы добиться необходимой полноты правил, логические функции составляются из объединения через знак дизъюнкции множества так называемых конъюнктивных форм (КФ). Чтобы достичь достаточной точности правил, их элементы — КФ — строятся как объединение через знак конъюнкции множества так называемых дизъюнктивных форм (ДФ). Было решено, что логическая функция должна состоять из элементарных единиц (литералов), представляющих условия, накладываемые на значения морфологических признаков. В литерале могут задаваться условия нескольких видов: (а) возможное значение одного из морфологических признаков у слова, входящего в связь, (б) равенство или неравенство некоторого признака у соединённых связью слов или (в) возможное расстояние между связанными словами. Дизъюнктивная форма представляет собой формулу из двух частей: положительной и отрицательной, соединённых знаком логического вычитания. Каждая часть является объединением литералов через знак дизъюнкции. Положительные литералы показывают, какими свойствами могут обладать слова, вступающие в связь, в отрицательных указаны свойства, которых у таких слов быть не может.

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

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

1. М. Г. Мальковский, А. С. Старостин Модель синтаксиса в системе морфосинтаксического анализа «Treeton» // Ж. Компьютерная лингвистика и интеллектуальные технологии, 2006. С. 481–492.

[HTM] (http://www.dialog-21.ru/digests/dialog2006/materials/ html/Starostin.htm).

2. Синтаксически размеченный корпус русского языка: инструкция пользователя — [HTML] (http://www.ruscorpora.ru/ instruction-syntax.html).

Признаки регулярности бесконтекстных языков, заданных графами Работа удостоена диплома II степени Кафедра алгоритмических языков email: [email protected] Научный руководитель: к.ф.-м.н., ст. преп. Вылиток Проблема регулярности для контекстно-свободных языков состоит в том, чтобы по данной контекстно-свободной грамматике или магазинному автомату определить, существует ли эквивалентный конечный автомат.

Известно, что проблема регулярности алгоритмически разрешима для детерминированных контекстно-свободных грамматик и магазинных автоКафедра АЯ матов. Известные на сегодняшний день алгоритмы проверки регулярности [1] имеют двойную экспоненциальную временную сложность от размера магазинного автомата. Проверка регулярности заключается в построенни по данному ДМА M детерминированного конечного автомата A и проверке равенства языков, заданных этими автоматами: L(M ) = L(A).

Высокая временная сложность этого алгоритма обусловлена тем фактом, что существуют примеры ДМА с количеством состояний n, для которых минимальный эквивалентный ДКА имеет более 22 состояний [3].

В связи с этим возникает вопрос: можно ли выполнить проверку регулярности для данного ДМА M, не выполняя построения эквивалентного ДКА? В работе [2] был предложен подкласс графов магазинных автоматов, для которых проверку регулярности можно выполнить за экспоненциальное время от размера графа ДМА. Однако при преобразовании произвольного ДМА к этому подклассу количество состояний может возрастать экспоненциально. Поэтому проблема проверки регулярности ДМА быстрее, чем за двойное экспоненциальное время, остаётся открытой.

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

1. Valiant L. G. Regularity and related problems for deterministic pushdown automata // Journal of the ACM. 1975. Т. 22.

2. Shankar P., Adiga B. S. A Graph-Based Regularity Test for Deterministic Context-free Languages // Theor. Comput. Sci. 1991, Т. 88, с. 117–125.

3. Meyer A. R., Fischer M. J. Economy of description by automata, grammars, and formal systems // Proceedings of the 12th Annual Symposium on Switching and Automata Theory. IEEE Computer Society, 1971, с. 188–191.

4. Л. И. Станевичене. К теории бесконтекстных языков МГУ им. М. В. Ломоносова. Москва. 2000. 165 с. Рукопись деп. в ВИНИТИ РАН 29.05.2000. № 1546 B00.

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

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

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

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

В алгоритме работы анализатора учитываются основные использующиеся форматы текстовых документов:.docx,.pdf,.txt,.html и графический формат.jpeg. Все типы документов приводятся к стандартному виду при помощи внешней части системы и далее автоматически анализируются и трансформируются для последующей записи в хранилище данных.

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

Загружаемая в хранилище информация проходит несколько автоматических стадий проверки.

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

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

1. Цивьян Т. В. Исследования по структуре текста. М.: МЦНМО, 2. Steven S. Skiena The Algorithm Design Manual. NY, 2008.

Библиотечная поддержка стековых вычислительных моделей Работа удостоена диплома III степени Кафедра алгоритмических языков email: [email protected] Научный руководитель: к.ф.-м.н., доц. Столяров Андрей Метод непосредственной интеграции является способом объединения возможностей различных языков программирования в рамках одного проекта. Основной идеей этого подхода является моделирование средствами некоторого базового языка конструкций альтернативных языков.

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

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

Основным средством, использованным в работе, является библиотека InteLib, предоставляющая средства для реализации и применения метода непосредственной интеграции. На сегодняшний день в состав библиотеки входят модули, позволяющие использовать в проектах на C++ такие языки, как Lisp, Scheme [3], Refal [4], Prolog [5].

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

Для реализации были использованы система типов библиотеки InteLib на основе S-выражений и вычислительная модель на основе продолжений [3], представляющая собой двухстековую виртуальную машину.

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

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

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

Ниже представлено определение функции быстрой сортировки на языке Joy и фрагмент соответствующего кода на языке C++:

// Joy code

DEFINE

qsort == [small] [] END // C++ code JoyQProgramConstructor J;

JToken DEFINE("DEFINE");

JToken EQUALS("EQUALS");

JToken END("END");

JLabel qsort("qsort");

(J| qsort, EQUALS, (J| SMALL), ~J, ).Evaluate();

1. Leo Brodie. Thinking FORTH. A Language and Philosophy for Solving Problems. Englewood Clis, N.J., Prentice-Hall, Inc., 1984.

2. Manfred von Thun. Joy: Forth’s Functional Cousin. Proceedings of the 17th EuroForth Conference, 9 October 2001.

3. А. В. Столяров. Импорт вычислительной модели языка Scheme в объектно–ориенторованное окружение. Сборник статей молодых учёных факультета ВМиК МГУ, № 5. М.: Издательский отдел факультета ВМиК МГУ, 2008, стр. 119–130.

4. И. Е. Бронштейн, А. В. Столяров. Библиотечная поддержка вычислительной модели языка Рефал. Сборник статей молодых учёных факультета ВМиК МГУ, № 6. М.: Издательский отдел факультета ВМиК МГУ, 2009, стр. 36–46.

5. И. В. Струков. Библиотечная реализация Пролог–решателя. Сборник статей молодых ученых факультета ВМК МГУ, № 9, 2012. М.: Издательский отдел факультета ВМиК МГУ, 2012, стр. 235–250.

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

Рассматриваются уравнения, имеющие вид где • x = (x1,..., xm ) — вектор независимых переменных, • y(x) = y(x1,..., xm ) — неизвестная функция от m переменных, • s = (s1,..., sm ) — мультипоказатель, • S — конечное подмножество Zm0, Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года • as (x) — полиномы над некоторым фиксированным полем характеристики 0, • s = s1... sm, а i — частная разность по xi :

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

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

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

Как известно (см., например, [5]), существуют алгоритмы поиска всех решений в виде рациональных функций и формальных лорановых рядов линейных дифференциальных и разностных уравнений с полиномиальными коэффициентами в случае одной переменной (m = 1), они реализованы в различных системах компьютерной алгебры. Доказанные в работе теоремы означают, что не имеет смысла рассчитывать на появление такого рода алгоритмов для произвольных m > 1.

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

1. Матиясевич Ю. В. Десятая проблема Гильберта. М: Hаука, физматлит, 1993.

2. Abramov S., Petkovsek M. On polynomial solutions of linear partial dierential and (q-)dierence equations. Computer Algebra in Scientic Computing, 14th International Workshop, CASC 2012, Maribor, Slovenia, September 2012, Proceedings, LNCS 7442, 2012. P. 1–11.

3. Kauers M., Schneider C. Partial denominator bounds for partial linear dierence equations. Proceedings ISSAC’2010, 2010. P. 211–218.

4. Aroca F., Cano J. M., Jung F. R. Power series solutions for non-linear PDE’s. In Proceedings of ISSAC’03, p. 15–22. ACM Press, 2003.

5. Абрамов С. А. Элементы компьютерной алгебры линейных обыкновенных дифференциальных, разностных и q-разностных операторов. М: МЦНМО, 2012.

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

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

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

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

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

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

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

1. Behrmann G., David A., Larsen K. A tutorial on Uppaal // Lecture Notes in Computer Science, 2004, v. 3185, p. 200–236.

2. Alur R., Dill D. Automata for modeling real-time systems // Proc. of Int. Colloquium on Algorithms, Languages, and Programming, LNCS, 1990, v. 443, p. 322–335.

3. Casado M., Garnkel T., Akella A., Freedman M., Boneh D., McKeown N., Shenker S. SANE: A Protection Architecture for Enterprise Networks // 15-th Usenix Security Symposium, Vancouver, Canada, August 2006.

4. McKeown N., Anderson T., Balakrishnan H., Parulkar G., Peterson L., Rexford J., Shenker S., Turner J. Openow: Enabling innovation in campus networks // SIGCOMM Computer Communication Review, 2008, v. 38, n. 2, p. 69–74.

Алгоритмы преобразования графовых описаний формальных языков Ростовский Артем Владимирович Кафедра алгоритмических языков Научный руководитель: к.ф.-м.н., ст. преп. Вылиток В дипломной работе вводится новый способ описания формальных языков – Ln -графы и рассматриваются алгоритмы преобразования Ln графов в классические представления языков (конечные и магазинные автоматы, машины Тьюринга) и обратные алгоритмы.

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

Ln -граф является обобщением графического представления конечного автомата – диаграммы состояний. Вводится n дополнительных скобочных пометок на дугах. Допускаются цепочки из основных пометок путей, у которых цепочки из дополнительных пометок принадлежат языку Дика над алфавитом скобок. Такое обобщение позволяет задавать контекстносвободные языки при n = 1 и рекурсивно-перечислимые при n > 1. Приводятся алгоритмы (и доказывается их корректность) для построения L1 графа, задающего тот же язык, что и магазинный автомат, построения магазинного автомата, эквивалентного L1 -графу, и L2 -графа, эквивалентного машине Тьюринга.

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

1. Л. И. Станевичене. К теории бесконтекстных языков. МГУ им. М.

В. Ломоносова. Москва. 2000. 165 с. Рукопись деп. в ВИНИТИ РАН 29.05.2000. № 1546 B00.

2. М. Минский. Вычисления и автоматы. М.: Мир, 1971.

3. Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений. М.: ИД Вильямс, 2002.

4. А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978.

5. А. Е. Пентус, М. Р. Пентус. Теория формальных языков. Изд-во ЦПИ при механико-математическом ф-те МГУ, 2004.

Методы определения кластеров публикаций Кафедра алгоритмических языков Научный руководитель: к.ф.-м.н. Добров Борис В дипломной работе проведено исследование методов выделения крупных кластеров публикаций в социальной сети, связанных с определенным событием. Данная задача является особенно актуальной в связи с широким распространением социальных сетей, и тем, что они часто дополняют более традиционные формы СМИ, а нередко и заменяют их. Для исследования были использованы 110 тысяч сообщений из архивов LiveJournal за декабрь 2011 года, предоставленных компанией Яндекс Публикации в социальных сетях в подавляющем большинстве являются короткими текстами, и поэтому могут не иметь лексического пересечения с поисковым запросом, относящимся к событию [2]. Сложности добавляет также и возможность представления описания одного и того же события совершенно разными поисковыми запросами, описывающими некоторые подтемы основного события [3]. Таким образом задачей работы являлось получение метода, максимально полно и точно аппроксимирующего эталонное множество документов(кластер публикаций о событии) начиная с некоторого произвольного(но релевантного событию) поискового запроса и множества документов, найденных по нему. Результаты поиска по исходному запросу брались в качестве baseline и средняя F-мера на выбранных запросах составила 34%. Если T opic - выбранное событие, Detalon - кластер публикаций(аппроксимируемое множество) о T opic, Q0 исходный запрос, D0 = µ(Q0 ) - результаты поиска по Q0, тогда решением задачи является алгоритм MDD или MQQ :

Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года В дипломной работе были разработаны процедуры, реализующие обработку рассмотренных выше шаблонов извлечения и шаблонов генерации языка LSPL [1]. Эти процедуры реализованы в виде дополнительных компонентов библиотеки LSPL [2] и могут быть интегрированы в различные приложения по обработке текста. Библиотека доступна для свободного использования, исходный код находится по адресу http://gitorious.org/lspl. Шаблоны извлечения и шаблоны генерации опробованы при создании нескольких приложений, в частности, системы автоматизированного построения глоссариев.

1. Большакова Е. И., Баева Н. В., Бордаченкова Е. А., Васильева Н. Э., Морозов С. С. Лексико-синтаксические шаблоны в задачах автоматической обработки текстов // Компьютерная лингвистика и интеллектуальные технологии: Труды Международной конференции Диалог ’2007, М.: Издательский центр РГГУ, 2007, с. 70–75.

2. Большакова Е. И., Носков А. А. Программные средства анализа текста на основе лексико-синтаксических шаблонов языка LSPL // Программные системы и инструменты: Тематический сборник, № / Под ред. Королева Л. Н., М.: Изд. отдел факультета ВМиК МГУ имени М.В.Ломоносова; МАКС Пресс, 2010, с. 61–73.

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

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

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

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

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

В рамках данной дипломной работы была разработана такая система.

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

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

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

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

1. JSON. JavaScript Object Notation.

[HTML] (http://tools.ietf.org/html/rfc4627).

2. Neumeyer L., Robbins B., Nair A, Kesari A. S4: Distributed Stream Computing Platform // Data Mining Workshops ICDMW 2010 P. 170– 3. Narthan Marz Storm. Distributed and fault-tolerant realtime computation. [HTML] (http://storm-project.net).

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

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

высокоуровневое в виде графа потока управления и текстовое в виде листинга машинных инструкций [1].

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

На основе композиции трасс производится построение межпроцедурного графа потока управления [2].

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

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

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

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

1. Анализ производимых над значением операций. Если над значением производились операцие не свойственные адресной арифметике, например, умножение и деление, оно классифицируется как данные.

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

В работе приводится анализ перемещаемого листинга, построенного на основе трасс, снятых во время выполнения утилиты nslookup в рамках ОС Windows 2k. Сравение перемещаемого листинга экземпляра модуля ntdll.dll с результатами дизассемблирования соответсвуюшего бинарного файла средсвами IDA Pro, показывает высокую точность предложенного метода.

1. Avgerinos T., Schwartz E., Brumley D. BAP: A binary analysis platform. Proceedings of the Conference on Computer Aided Verifcation, 2. Тихонов А., Аветисян А., Падарян В. Методика извлечения алгоритма из бинарного кода на основе динамического анализа. Проблемы информационной безопасности. Компьютерные системы. № 2008. стр. 66-71.

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

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

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

В работе рассматриваются существующие тематические модели: Скрытое размещение Дирихле (LDA), Иерархическое скрытое размещение Дирихле (HLDA), Иерархической процесс Дирихле (HDP). Описываются основные методы оценки качества тематических моделей: ручная оценка, оценка качества приложений, использующих тематические модели, перплексия, интерпретируемость. Обзор данных, а также других методов тематического моделирования, представлен в статье [1].

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

• Из распределения. Для каждой темы выбирается k по следующему правилу:

Здесь T – параметр.

• Из совокупности распределений. Сначала оценивается порог T :

Затем для каждой темы вычисляется k из распределения (первый метод). Здесь H – параметр метода.

Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года Оценка интерпретируемости темы по ключевым словам производится с использованием Wkipedia и Google. При оценке с помощью Wikipedia используется поточечная взаимная информация (PMI) – вещественная функция, определенная для двух слов. Она показывает насколько часто два слова вместе встречаются в одной статье Wikipedia. Интерпретируемость оценивается как среднее значение PMI по всем парам различных ключевых слов. При использовании Google интерпретируемость оценивается как логарифм количества результатов выдачи по запросу, составленному из ключевых слов.

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

Дополнительно проводится анализ моделей Скрытое размещение Дирихле (LDA) и Иерархический процесс Дирихле (HDP) с использованием разработанных методов: выводится зависимость интерпретируемости от различных значений параметров данных моделей. Получены следующие выводы:

1. При увеличении количества тем в LDA интерпретируемость тем ухудшается 2. Интерпретируемость получаемых с помощью LDA / HDP тем несущественно зависит от параметра концентрации тем в документе / параметра концентрации первого уровня соответственно 3. При правильном выборе количества тем в LDA, данная модель выдает более интерпретируемые темы, чем HDP 1. Коршунов А., Гомзин А. Тематическое моделирование текстов на естественном языке //Труды Института системного программирования РАН. – 2012.

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

• требуется привлечение экспертов в данной предметной области;

• процесс построения методов может занять длительное время;

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

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

Задача дипломной работы состоит в следующем:

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

2. Требуется построить программное средство автоматического вывода методов на основе разработанного алгоритма.

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

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

Проведено сравнение методов, выведенных разработанным алгоритмом, с методами, полученными в результате работы алгоритма Янга-Пана.

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

На основе разработанного алгоритма построено программное средство автоматического вывода методов. Методы, полученные в результате работы программного средства, могут быть использованы в планировщиках SHOP и SHOP2 [3,4].

1. Рассел С., Норвиг П. Искусственный интеллект: современный подход, 2-е изд. М.: Вильямс, 2006. 1408 с.

2. Yang Q., Pan R., Pan S. J. Learning recursive HTN-method structures for planning // Proceedings of the ICAPS-07 Workshop on Planning and Learning. 2007.

3. Nau D., Au T.-C., Ilghami O., Kuter U., Murdock J.W., Wu D., Yaman F. SHOP2: An HTN Planning System // Journal of Articial Intelligence Research. 2003. 20. P. 379–404.

4. Nau D., Au T.-C., Ilghami O., Kuter U., Murdock J.W., Wu D., Yaman F. Applications of SHOP and SHOP2 // IEEE Intelligent Systems. 2005. 20. №2. P. 34–41.

Разработка информационной системы для прокладывания маршрутов в сети междугородного автобусного транспорта Работа удостоена диплома III степени Кафедра системного программирования Научный руководитель: н.с. Гурьев Дмитрий Евгеньевич Транспорт — неотъемлемая часть жизни людей. В крупнейших городах количество как внутренних, так и междугородных маршрутов может достигать нескольких сотен. Обширные объёмы информации о расписаниях и маршрутах, безусловно, нуждаются как в организации широкого доступа, так и в интеллектуальной обработке.

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

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

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

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

Задача поиска k кратчайших путей между двумя фиксированными вершинами является обобщением задачи нахождения одного кратчайшего пути. Она была достаточно хорошо изучена [4-5], и для её решения было предложено несколько алгоритмов. За основу был взят алгоритм Йена [6], который при реализации был оптимизирован с целью увеличения производительности работы. Сервис разработан на основе шаблона проектирования Model-View-Controller, на языке PHP, с использованием библиотек CodeIgniter, jQuery и СУБД MySQL.

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

1. Программный комплекс «Автовокзал» [HTML] (http://bus.com.ua/).

2. Транспортная информационная система «AVM Travel Network»

[HTML] (http://avm-travel.com/).

(http://avtobus.at.ua/).

4. D. R. Shier. On algorithms for nding the K shortest paths in a network.

Networks, 1979, pp. 195–214.

5. A. Perko. Implementation of algorithms for K shortest loopless paths.

Networks, 1986, pp. 149–160.

6. J. Y. Yen. Finding the K shortest loopless paths in a network.

Management Science, 1971, pp. 712–716.

Исследование и разработка методов разрешения лексической многозначности на основе неполной базы знаний Работа удостоена диплома I степени Кафедра системного программирования Научные руководители: академик РАН Иванников Виктор Астраханцев Никита Александрович Разрешение лексической многозначности — одна из центральных проблем обработки естественного языка. Данная проблема заключается в автоматическом определении значений слов на основе их контекстов.

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

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

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

В качестве метода извлечения терминологии был использован алгоритм голосования, поскольку данный метод является одним из наиболее эффективных [1]. При этом было реализовано большинство основных признаков терминов [2], такие как частота, TF*IDF, релевантность домену, согласованность, сплоченность, t-критерий и другие.

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

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

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

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

Для тестирования разработанного метода был собран корпус тематики «Настольные игры». Тестирование показало, что разработанный метод превосходит существующий алгоритм решения поставленной задачи [3], а также улучшает точность алгоритма разрешения многозначности системы Texterra на данном корпусе с 52% до 78%, что показывает практическую значимость разработанного метода.

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

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

1. Zhang Z., Iria J. A comparative evaluation of term recognition algorithms.

2. Pazienza M. T., Pennacchiotti M., Zanzotto F. M. Terminology extraction: an analysis of linguistic and statistical approaches. // Knowledge Mining. Springer, 2005, p. 255–279.

3. Erk K., Pado S. ShalmaneserЦa toolchain for shallow semantic parsing.

// Proceedings of LREC. 6, 2006.

Синтез архитектурных моделей систем управления реального времени на основе применения генетических алгоритмов Кафедра системного программирования Научный руководитель: д.ф.-м.н., проф. Петренко В данной работе рассматриваются системы реального времени, используемые на бортах самолетов, так называемые системы авионики. Наиболее передовыми системами являются системы, соответствующие стандарту AFDX - Avionics Full Duplex Switched Ethernet. Стандарт AFDX включает в себя следующие понятия :

1. оконечная система — представляет собой вычислительный модуль и набор программ, работающих на нем, такими программами могут (a) автопилот (b) подсистема, опрашивающая значения датчика высоты, gps и т.д.

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

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

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

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

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

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

1. ARINC Specication 664 Part 7. AEEC, 2. AFDX / ARINC 664 Tutorial. TechSAT GmbH, 2008.

3. Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. Физматлит, 2003.

4. Henri Bauer, Jean-Luc Scharbarg, Christian Fraboul. Worst-case endto-end delay analysis of an avionics AFDX network. Proceedings of the Conference on Design, Automation and Test in Europe, 2010.

Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года Темы дипломных работ, защищенных в 2013 году (отделение специалистов) АБАКУМОВ КОНСТАНТИН ВИКТОРОВИЧ – группа Обработка потоковых слабоструктурированных данных в реальном времени Научный руководитель: Кузнецов Сергей Дмитриевич АБРАМЧУК СЕРГЕЙ ВЛАДИМИРОВИЧ – группа О максимальных по включению множествах свободных от решений линейных уравнений Научный руководитель: Сапоженко Александр Антонович АВЕРИНА ВЕРОНИКА ВАДИМОВНА – группа Математическая модель назначения транспортных средств АГАЕВ НУРЛАН ЗАКИРОВИЧ – группа Исследование и разработка современных методов построения вопросно-ответных системы Научный руководитель: Турдаков Денис Юрьевич АГАЛЬЦОВ АЛЕКСЕЙ ДМИТРИЕВИЧ – группа Исследование обобщённого преобразования Радона и его экономические приложения Научный руководитель: Шананин Александр Алексеевич АКИМОВ ДМИТРИЙ АЛЕКСАНДРОВИЧ – группа Метод выделения полупрозрачных частиц в видео на основе анализа резкости кадра Научный руководитель: Ватолин Дмитрий Сергеевич АКЦИПЕТРОВ АЛЕКСАНДР ОЛЕГОВИЧ – группа Семантическая интеграция библиотечных данных Научный руководитель: Серебряков Владимир Алексеевич АЛЕЙНИКОВ ПАВЕЛ ВЯЧЕСЛАВОВИЧ – группа Анализ русскоязычных текстов для генерации системы синтаксических правил Научный руководитель: Грацианова Татьяна Юрьевна АЛЕКРИТСКИЙ ДМИТРИЙ ИГОРЕВИЧ – группа Стохастические дифференциальные уравнения для случайных процессов со смешанными гауссовскими распределениями Научный руководитель: Королев Виктор Юрьевич АЛЕКСАНДРОВ ЯРОСЛАВ АЛЕКСЕЕВИЧ – группа Оптимизация размещения инфраструктуры нефтяного месторождения Научный руководитель: Гуров Сергей Исаевич АЛЕХИН НИКИТА СЕРГЕЕВИЧ – группа Моделирование памяти на фазовых переходах АНИКЕЕВ ФЁДОР АЛЕКСАНДРОВИЧ – группа Параллельные методы решения кинетических уравнений Научный руководитель: Зайцев Федор Сергеевич АНИКИНА ВЕРА ВЛАДИМИРОВНА – группа Моделирование алгоритмов стабилизации линейных нестационарных динамических объектов Научный руководитель: Фурсов Андрей Серафимович АНИСИМОВ АЛЕКСАНДР ВЛАДИМИРОВИЧ – группа Некоторые классы динамических управляемых моделей Темы дипломных работ (отделение специалистов) Научный руководитель: Григоренко Николай Леонтьевич АНТОНОВ ДМИТРИЙ АНДРЕЕВИЧ – группа Исследование методов оптимизации задач обеспечения безопасности АРЕФЬЕВ АРСЕНИЙ ВИКТОРОВИЧ – группа Распознавание выражений лиц Научный руководитель: Фомичев Василий Владимирович АРТЕМОВ АНТОН ПАВЛОВИЧ – группа Метод последовательных уточнений при разрешении синтаксической омонимии АРТЮХИН СТАНИСЛАВ ГЕННАДЬЕВИЧ – группа Классификация трехмерных объектов по двухмерным проекциям Научный руководитель: Местецкий Леонид Моисеевич АРХАНГЕЛЬСКАЯ АННА СЕРГЕЕВНА – группа Исследование задачи дифракции плоской волны на локальной неоднородности границы раздела сред Научный руководитель: Ильинский Анатолий Серафимович АСТАШКИН ГЛЕБ ВЛАДИМИРОВИЧ – группа Статическое представление бинарного кода, полученное из набора связанных трасс Научный руководитель: Падарян Вартан Андроникович АТАМАСЬ ЕВГЕНИЙ ИВАНОВИЧ – группа Алгоритм обращения некоторого класса динамических систем с запаздыванием Научный руководитель: Ильин Александр Владимирович АУШКАП НИКОЛАЙ СЕРГЕЕВИЧ – группа Задача достижимости для модели межвидового взаимодействия АФАНАСЬЕВА ОЛЬГА ИГОРЕВНА – группа Оптимизация назначения резервов в страховании БАБАК АНДРЕЙ АЛЕКСЕЕВИЧ – группа Статический межпроцедурный анализ в программах на языке Питон Научный руководитель: Козлов Д.Д.

БАДРЕТДИНОВ РАМИЛЬ РИНАТОВИЧ – группа Автоматическое обнаружение ошибок в программах на языке Python при помощи статического анализа БАЗДАРЕВ СЕМЕН БОРИСОВИЧ – группа Исследование двойственных задач управления и наблюдения в оптически неоднородной среде БАКЕЕВ РУСЛАН НАДИРОВИЧ – группа Исследование симметрично-симплектических методов на точных решениях задачи Кеплера Научный руководитель: Еленин Георгий Георгиевич БАЛАНДЮК-ОПАЛИНСКАЯ ЯНИНА ЭДВАРДОВНА – группа Использование морфологии для выявления семантических характеристик слова БАННИКОВ ПАВЕЛ СЕРГЕЕВИЧ – группа Выявление истинной топологии коммуникационной среды вычислительного кластера по набору тестов Научный руководитель: Сальников Алексей Николаевич Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года БАТАНОВ ПАВЕЛ ГЕОРГИЕВИЧ – группа Сопровождение людей в системах многокамерного видеонаблюдения для спортивных игр БЕДОВ АНДРЕЙ ИГОРЕВИЧ – группа Численный анализ дифракции акустических волн на прямоугольном экране Научный руководитель: Захаров Евгений Владимирович БЕСКОВА ЕКАТЕРИНА АЛЕКСАНДРОВНА – группа Задача о бесповторном представлении функции, заданной на шести точках Научный руководитель: Вороненко Андрей Анатольевич БЕСПАМЯТНОВ ДМИТРИЙ АЛЕКСАНДРОВИЧ – группа Сравнение детерминированного и стохастического метода частиц для уравнения диффузии Научный руководитель: Богомолов Сергей Владимирович БЕСФАМИЛЬНАЯ МАРИЯ ВИКТОРОВНА – группа Многомасштабный метод оценки ширины контуров изображений Научный руководитель: Лукин А.С.

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

ВИНОГРАДОВ АНДРЕЙ ЕВГЕНЬЕВИЧ – группа Метод частиц для уравнения Кортевега-де Фриса Научный руководитель: Богомолов Сергей Владимирович ВОЛКОВ ПЕТР ВЛАДИМИРОВИЧ – группа Математическое моделирование задачи на собственные функции и собственные значения для уравнения Шредингера с нелинейным коэффициентом поглощения Научный руководитель: Федотов Михаил Валентинович ВОРОТНИКОВ АНДРЕЙ ВАЛЕРЬЕВИЧ – группа Вариационный морфологический метод анализа изображений Научный руководитель: Крылов Андрей Серджевич ВТОРОВ АЛЕКСАНДР АЛЕКСАНДРОВИЧ – группа Использование облачных вычислений в информационных системах предприятия Научный руководитель: Леонтьев Виктор Владимирович ГАВРИЛЮК КИРИЛЛ АРТУРОВИЧ – группа Методы построения иерархических тематических моделей коллекции текстовых документов Научный руководитель: Воронцов Константин Вячеславович Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года ГАЙДУКОВА АННА ВАЛЕРЬЕВНА – группа Математическое моделирование спиральных волн в краевой задаче с наклонной производной для уравнения диффузии ГАЛОЧКИНА ТАТЬЯНА ВЛАДИМИРОВНА – группа Отыскание почти периодических режимов терапии в модели динамики клеток Научный руководитель: Братусь Александр Сергеевич ГЕРМАН ЕКАТЕРИНА СЕРГЕЕВНА – группа Алгоритмы управления нелинейных динамических систем в условиях неопределенности Научный руководитель: Бобылева О.Н.

ГИНЖУЛ ВАРВАРА АЛЕКСАНДРОВНА – группа Модель оптимального экономического роста в условиях ограниченности ресурсов ГЛАДКОВА ОЛЬГА АНДРЕЕВНА – группа Визуализация и валидация планов при помощи объектных моделей Научный руководитель: Малышко Виктор Васильевич ГЛОНИНА АЛЕВТИНА БОРИСОВНА – группа Исследование применения метамоделей для задачи выбора механизмов отказоустойчивости распределенных вычислительных систем реального времени Научный руководитель: Волканов Дмитрий Юрьевич ГОЛИЦЫН ДМИТРИЙ ЛЕОНИДОВИЧ – группа Алгоритм численного доказательства существования периодических траекторий в нелинейных системах обыкновенных дифференциальных уравнений Научный руководитель: Магницкий Николай Александрович ГОЛОД АЛЕКСАНДРА ИГОРЕВНА – группа Метод Хошино для решения задач равновесного программирования Научный руководитель: Будак Борис Александрович ГОЛУШКО ПАВЕЛ АЛЕКСАНДРОВИЧ – группа Автоматическая разметка трасс машинных команд событиями уровня операционной системы Научный руководитель: Гайсарян Сергей Суренович ГОМЗИН АНДРЕЙ ГЕННАДЬЕВИЧ – группа Определение тематической направленности текстового содержимого микроблогов Научный руководитель: Коршунов Антон Викторович ГОРБУНОВ АЛЕКСАНДР ВАЛЕРЬЕВИЧ – группа Математические методы, алгоритмы и программное обеспечение для медицинской генетики Научный руководитель: Руднев Сергей Геннадьевич ГОРЯКОВА ДАРЬЯ ИГОРЕВНА – группа Решение задач оптимального управления для математической модели ВИЧ-инфекции Научный руководитель: Хайлов Евгений Николаевич ГРИГОРЯН КАРЭН РОБИКОВИЧ – группа Алгоритмы вычисления интеграла освещенности на основе двунаправленной трассировки лучей Научный руководитель: Игнатенко Алексей Викторович Темы дипломных работ (отделение специалистов) ГРИШАНИН АЛЕКСАНДР АНДРЕЕВИЧ – группа Разработка и исследование численных моделей квантовых точек Научный руководитель: Попов Александр Михайлович ГУЛЕЙКОВА АННА ДМИТРИЕВНА – группа Нижние и верхние оценки стоимости американского опциона Научный руководитель: Морозов Владимир Викторович ГУЛИЕВ РУСТАМ РАФИГОВИЧ – группа Поиск гарантирующих стратегий в математической модели динамики клеток Научный руководитель: Братусь Александр Сергеевич ГУРЬЯНОВ АНТОН КОНСТАНТИНОВИЧ – группа Воксельные модели в задачах фотореалистичной визуализации Научный руководитель: Игнатенко Алексей Викторович ДЁМИН АЛЕКСЕЙ БОРИСОВИЧ – группа Сравнительный анализ эффективности генетических алгоритмов и традиционных методов оценивания параметров в регрессионых моделях Научный руководитель: Ульянов Владимир Васильевич ДЕМИН МИХАИЛ НИКОЛАЕВИЧ – группа Моделирование эволюции аэрозолей с помощью стохастических методов Научный руководитель: Смирнов Александр Павлович ДМИТРИЕВ ЕВГЕНИЙ ДМИТРИЕВИЧ – группа Программирование Web-приложений с использованием систем NoSQL ДОЛОТКАЗИН ЮРИЙ ВЛАДИМИРОВИЧ – группа Генерация описаний задач планирования по объектной модели предметной области Научный руководитель: Малышко Виктор Васильевич ДРЯЖЕНКОВ АНДРЕЙ АЛЕКСАНДРОВИЧ – группа Неравенства наблюдаемости с оптимальным пороговым моментом для одномерного уравнения колебаний Научный руководитель: Потапов Михаил Михайлович ЕГОРЕНКОВ ВЛАДИМИР АЛЕКСАНДРОВИЧ – группа Компьютерное моделирование динамики полупроводниковой плазмы в двумерном случае Научный руководитель: Логинова Мария Михайловна ЕЛШИН ДЕНИС АЛЕКСАНДРОВИЧ – группа Разработка и реализация алгоритмов для рекомендательных систем мобильных устройств Научный руководитель: Ветров Дмитрий Петрович ЕПИХИНА ОЛЬГА БОРИСОВНА – группа Оптимизация формирования портфеля с учетом операционных издержек Научный руководитель: Морозов Владимир Викторович ЕРМИШКИН НИКОЛАЙ ЮРЬЕВИЧ – группа Поиск нестандартных компонентов систем управления содержимым при анализе web-сайтов методом черного ящика ЕРМОШИНА АНАСТАСИЯ МИХАЙЛОВНА – группа Математическая модель оптимизации кредитования Научный руководитель: Денисов Дмитрий Витальевич Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года ЕРМУШЕВА АЛЕКСАНДРА АЛЕКСАНДРОВНА – группа Задачи анализа данных с нестандартным функционалом качества Научный руководитель: Дьяконов Александр Геннадьевич ЕРОФЕЕВ МИХАИЛ ВИКТОРОВИЧ – группа Разработка стабильного во времени метода анализа прозрачности границ объектов в видео Научный руководитель: Ватолин Дмитрий Сергеевич ЕФИМОВ АЛЕКСАНДР ЮРЬЕВИЧ – группа Разработка и реализация прозрачного перехвата процесса сборки Научный руководитель: Гайсарян Сергей Суренович ЕФРЕМОВ АЛЕКСЕЙ МИХАЙЛОВИЧ – группа Метод частиц для двумерного уравнения конвекции-диффузии Научный руководитель: Богомолов Сергей Владимирович ЕФРЕМОВ АНДРЕЙ СЕРГЕЕВИЧ – группа Моделирование отражения радиоволн от сложных полигональных моделей Научный руководитель: Березин Сергей Борисович ЖАВОРОНКОВА ЮЛИЯ ВАДИМОВНА – группа Решение проблемы эквивалентности рекурсивных схем при помощи машин со сцепленными состояниями Научный руководитель: Захаров Владимир Анатольевич ЖЕБЕЛЬ ВЛАДИМИР ВИКТОРОВИЧ – группа Разработка модернизированного кода TOKAMEQ QT с расширенным набором опций Научный руководитель: Сычугов Дмитрий Юрьевич ЖИВОТИКОВ СЕРГЕЙ АЛЕКСАНДРОВИЧ – группа Разработка алгоритма численного решения квазилинейных уравнений Научный руководитель: Фаворский Антон Павлович ЖИЕНБАЙ ОЛЖАС ЕРСАЙЫНУЛЫ – группа Специальный метод штрафов для задач оптимального управления с фазовыми ограничениями ЖУРАВЛЕВ АЛЕКСЕЙ ЮРЬЕВИЧ – группа Обнаружение сайтов, реализующих маскирования от автоматических средств обхода Научный руководитель: Петухов Андрей Александрович ЖУРАХОВСКИЙ ОЛЕГ АНДРЕЕВИЧ – группа Алгоритмы обеспечения совместимости требований к обмену по каналу с централизованным управлением ЗАХАРОВА ДАРЬЯ ПАВЛОВНА – группа Исследование повторяющейся игры импа «Дилемма заключенного» со случайными ошибками Научный руководитель: Васин А.А.

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

КАЛЫГИН МИХАИЛ МИХАЙЛОВИЧ – группа Методы пространственной интерполяции климатических данных Научный руководитель: Березин Сергей Борисович КАРМОКОВ КАНТЕМИР АНДЗОРОВИЧ – группа Разработка программной системы для поиска фотографий лиц, наиболее соответствующих заданному изображению Научный руководитель: Шишкин Алексей Геннадиевич КАРНАУХОВ ДЕНИС ЮРЬЕВИЧ – группа Теоретико-игровой анализ правил государственных закупок Научный руководитель: Поспелова Ирина Игоревна Тезисы лучших дипломных работ факультета ВМК МГУ 2013 года КАРПУХИН ИВАН АЛЕКСАНДРОВИЧ – группа Корректировка положения трехмерного объекта по набору фотоизображений Научный руководитель: Игнатенко Алексей Викторович КАСИМОВА АННА АРТУРОВНА – группа Признаки регулярности бесконтекстных языков, заданных графами Научный руководитель: Вылиток Алексей Александрович КАТРАЕВ ВАСИЛИЙ ДМИТРИЕВИЧ – группа О гибкой, эффективной и стойкой реализации схем выработки общего ключа типа MTI/A Научный руководитель: Матюхин Дмитрий Викторович КАУШАНСКИЙ ВАДИМ ЯКОВЛЕВИЧ – группа Оценка параметров в моделях срочной структуры процентных ставок Научный руководитель: Лапшин В.А.