WWW.NEW.PDFM.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Собрание документов
 

Pages:   || 2 |

«УНИВЕРСИТЕТ им. М.В. ЛОМОНОСОВА ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ СБОРНИК ТЕЗИСОВ ЛУЧШИХ ДИПЛОМНЫХ РАБОТ 2009 ГОДА МОСКВА 2009 Данный сборник посвящен девяностолетнему юбилею УДК ...»

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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ им. М.В. ЛОМОНОСОВА

ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ

МАТЕМАТИКИ И КИБЕРНЕТИКИ

СБОРНИК ТЕЗИСОВ ЛУЧШИХ

ДИПЛОМНЫХ РАБОТ 2009 ГОДА

МОСКВА 2009

Данный сборник посвящен девяностолетнему юбилею

УДК 517.6 + 519.8

ББК 22 Александра Андреевича Самарского –

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

Сборник тезисов лучших дипломных работ 2009 года. М.:

Издательский отдел факультета ВМК МГУ (лицензия ИД № 05899 от 24.09.2001), 2009 – 205 страниц .

Редакционный совет сборника:

Е.И. МОИСЕЕВ, С.А. ЛОЖКИН, Б.И. БЕРЕЗИН, В.Н. ЛЫКОСОВ, С. М. НИКОЛЬСКИЙ, А.Н. ТОМИЛИН, А.В. ИЛЬИН, И.Г. ШЕВЦОВА В настоящий сборник вошли тезисы выпускных квалификационных работ, выполненных студентами факультета Вычислительной математики и кибернетики Московского государственного университета им. М.В .

Ломоносова в 2009 году, представленные на конкурс лучших дипломных проектов .

Шевцова И.Г., Ильин А.В .

ISBN 5–89407–268–9 составление, оформление, 2009 .



Издательский отдел факультета ВМК МГУ им. М.В. Ломоносова, 2009 .

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

им. М.В. ЛОМОНОСОВА

ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ

СБОРНИК ТЕЗИСОВ ЛУЧШИХ

ДИПЛОМНЫХ РАБОТ 2009 ГОДА МОСКВА 2009 Данный сборник посвящается девяностолетию академика РАН Александра Андреевича САМАРСКОГО– ученого с мировым именем, академика РАН, основоположника отечественной школы математического моделирования, создателя фундаментальной общей теории разностных схем, выдающегося педагога, воспитавшего не одно поколение известных ученых, активного организатора и яркого пропагандиста науки Оглавление ОГЛАВЛЕНИЕ КАФЕДРА МАТЕМАТИЧЕСКОЙ ФИЗИКИ [ГРУППЫ 501,502] Расширение частотного диапазона аудио сигнала ЛЮБИМОВ НИКОЛАЙ АНДРЕЕВИЧ

Методы построения изображений расширенной глубины резкости МАТРОСОВ МИХАИЛ АЛЕКСАНДРОВИЧ

Методы восстановления нелинейного источника в уравнении теплопроводности ПАВЕЛЬЧАК ИВАН АЛЕКСЕЕВИЧ

Алгоритм восстановления трехмерных сцен СЕМЕЙКИНА ЕКАТЕРИНА ВИКТОРОВНА

Единственность определения зависящей от решения неоднородности в уравнении теплопроводности ЧУРБАНОВ ДМИТРИЙ ВЛАДИМИРОВИЧ

Компьютерные методы обработки медицинских видеоданных ЯТЧЕНКО АРТЁМ МИХАЙЛОВИЧ

Численное моделирование двухкомпонентной оптической системы .

ДАНИЛИН ИВАН ВЛАДИМИРОВИЧ

Моделирование соударения сверхзвуковых потоков газа с использованием суперкомпьютерного комплекса БАТЧИКОВ ПЕТР СЕРГЕЕВИЧ

Решение интегрального уравнения первого рода с дельта-образным ядром КОРСАКОВ МАКСИМ ВЛАДИМИРОВИЧ

Моделирование трехмерных турбулентных течений вязкой несжимаемой жидкости с применением графических процессоров САХАРНЫХ НИКОЛАЙ АЛЕКСАНДРОВИЧ

КАФЕДРА ВЫЧИСЛИТЕЛЬНЫХ ТЕХНОЛОГИЙ И МОДЕЛИРОВАНИЯ





Вычислительные алгоритмы интерполяции и экстраполяции в проблемах численного решения задач вариационной ассимиляции геофизических данных наблюдений ЗАХАРОВА НАТАЛЬЯ БОРИСОВНА

Численная реализация метода внеснной границы для моделирования вязкой несжимаемой жидкости в областях сложной конфигурации МОРТИКОВ ЕВГЕНИЙ ВАЛЕРЬЕВИЧ

Математическое моделирование механизмов патогенеза туберкулезной инфекции легких СЫТИН ЕВГЕНИЙ АНТОНОВИЧ

КАФЕДРА ВЫЧИСЛИТЕЛЬНЫХ МЕТОДОВ

Критерий устойчивости однопараметрического семейства нелокальных разностных схем для уравнения теплопроводности БОРЗОВ АНДРЕЙ ГЕННАДЬЕВИЧ

Тезисы лучших дипломных работ ВМК МГУ 2009 года

Математическое моделирование развития социально-экологической ситуации современного крупного города на примере города Астана СПИРИН ЕВГЕНИЙ ВЛАДИМИРОВИЧ

КАФЕДРА АВТОМАТИЗАЦИИ НАУЧНЫХ ИССЛЕДОВАНИЙ

Восстановление глубины сцены по ее изображениям СЕВРЮКОВ БОГДАН ГЕННАДЬЕВИЧ

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

СУЧКОВ ЕГОР ПЕТРОВИЧ

Нахождение оптимальных траекторий объектов на основе метода динамического программирования ЧЕРТОК АНДРЕЙ ВИКТОРОВИЧ

Численное моделирование молекулярных нанопереключателей ШУМКИН ГЕОРГИЙ НИКОЛАЕВИЧ

КАФЕДРА НЕЛИНЕЙНЫХ ДИНАМИЧЕСКИХ СИСТЕМ И ПРОЦЕССОВ УПРАВЛЕНИЯ

Исследование свойств нейронной сети нового типа и ее применение для распознавания и классификации растровых изображений ГРЕБЁНКИНИЛЬЯ ОЛЕГОВИЧ

Алгоритмы построения регуляторов,одновременно стабилизирующих дискретные линейные объекты второго порядка МИНЯЕВ СЕРГЕЙ ИГОРЕВИЧ

Спиральные волны и диффузионный хаос в уравнении Курамото-Цузуки НИКИТИНА МАРИНА ЮРЬЕВНА

Стабилизация систем управления с помощью понижения их динамического порядка РОДИЧЕНКО НИКИТА СЕРГЕЕВИЧ

Структура бифуркационных диаграмм систем двумерных нелинейных неавтономных дифференциальных уравнений РЯБКОВ ОЛЕГ ИГОРЕВИЧ

КАФЕДРА ОБЩЕЙ МАТЕМАТИКИ

Методы визуализации гиперповерхностей КОЛЕСНИКОВА ОЛЬГА СЕРГЕЕВНА

О четырех смешанных задачах для уравнения колебаний струны с граничными и нелокальными условиями первого и второго родов КУЛЕШОВ АЛЕКСАНДР АНДРЕЕВИЧ

О скорости сходимости спектральных разложений для обыкновенных дифференциальных операторов второго порядка МАРКОВ АЛЕКСЕЙ СЕРГЕЕВИЧ

Исследование задачи Трикоми для уравнения Лаврентьева-Бицадзе в некоторых областях с отклонением от характеристик НАЗАРОВА ИРИНА ЭРКИНОВНА

–  –  –

КАФЕДРА ИССЛЕДОВАНИЯ ОПЕРАЦИЙ [ГРУППЫ 511,512] Математическое моделирование динамики запутанности ядер в химических реакциях АКСЁНОВ БОРИС ЕВГЕНЬЕВИЧ

Оценка эффективности систем вихревого прогноза при полетах летательных аппаратов ИЗВОЛЕНСКИЙ АНТОН СЕРГЕЕВИЧ

Дифференциальные методы оценки европейских опционов МУРАВЕЙ ДМИТРИЙ ЛЕОНИДОВИЧ

Свойства голосования по правилу большинства КОПНЫШЕВ АЛЕКСАНДР СЕРГЕЕВИЧ

Исследование задач математического моделирования стратегий управления демографическими процессами КРУГЛЯК ЛЮБОВЬ КОНСТАНТИНОВНА

Свойства голосования с правом вето МАШЕЧКИН АЛЕКСЕЙ ИГОРЕВИЧ

Оптимальная организация налоговой инспекции при непрерывном распределении дохода налогоплательщиков в условиях коррупции НИКОЛАЕВ ПАВЕЛ ВАЛЕРЬЕВИЧ

Исследование модели многоуровневой налоговой инспекции УРАЗОВ АНТОН СЕРГЕЕВИЧ

КАФЕДРА ОПТИМАЛЬНОГО УПРАВЛЕНИЯ

Вероятностная модель межрегиональных отношений в контексте поставок природного газа БОРИСОВА АНАСТАСИЯ ВИКТОРОВНА

Исследование и численный анализ некоторы нелинейных управляемых динамических систем ВИННИКОВ ЕВГЕНИЙ ВЛАДИМИРОВИЧ

Динамическая модель оптимального управления структурой общества ИВАНОВА МАРИЯ ВЛАДИСЛАВОВНА

Игровые Модели энергетического рынка ИВАНОВА АННА ЕВГЕНЬЕВНА

Решение задачи быстродействия для нелинейной управляемой системы, описывающей движение трехколесного робота с фазовыми ограничениями МАРШИНИН АЛЕКСЕЙ БОРИСОВИЧ

Исследование некоторых нелинейных задач оптимального управления ПУЧКОВА АЛЁНА ИГОРЕВНА

КАФЕДРА СИСТЕМНОГО АНАЛИЗА

Построение оптимального синтеза в одной линейной задаче с фазовыми ограничениями ЖУКОВ ДМИТРИЙ АНДРЕЕВИЧ

Стабилизация на основе прогнозирующей модели дискретной динамической системы с помехой КАЛЯКИНА НАТАЛЬЯ АЛЕКСЕЕВНА

Тезисы лучших дипломных работ ВМК МГУ 2009 года Оптимальная ликвидация портфеля с использованием информации о глубине и релаксации рынка КОСТОВ ТЕОДОР ВЕСЕЛИНОВ

Динамическое программирование в линейных системах с состояниями в виде распределений МАЗУРЕНКО СТАНИСЛАВ СЕРГЕЕВИЧ

КАФЕДРА МАТЕМАТИЧЕСКОЙ СТАТИСТИКИ

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

ГАЙНАНОВА ИРИНА ВАЛЕРЬЕВНА

Асимптотическая оценка постоянной в неравенстве Берри-Эссеена для распределений, не имеющих третьего момента .

ГАПОНОВА МАРГАРИТА ОЛЕГОВНА

Применение процессов леви для определения оптимального времени исполнения реальных опционов ЛОМАКИН НИКИТА АЛЕКСАНДРОВИЧ

Свойства статистик в модели коинтеграции ряда векторной авторегрессии РОМАНЮК ГЛЕБ ВИКТОРОВИЧ

Анализ методов выявления экстремальных значений в рядах наблюдений ЧЕСНОКОВ АЛЕКСАНДР ВАСИЛЬЕВИЧ

КАФЕДРА МАТЕМАТИЧЕСКИХ МЕТОДОВ ПРОГНОЗИРОВАНИЯ

Скелетная сегментация линейчатых изображений АРГУНОВ ДМИТРИЙ АЛЕКСАНДРОВИЧ

Разрешимость и регулярность задач нечткой разметки точечных конфигураций ДОРОФЕЕВ НИКОЛАЙ ЮРЬЕВИЧ

Анализ пространственной структуры данных магнитной энцефалографии КОРНИЛИНА ЕЛЕНА ДМИТРИЕВНА

Построение композитно-иерархических скрытых марковских

моделей для анализа поведения ТЕМЛЯНЦЕВ АЛЕКСАНДР ВАЛЕРЬЕВИЧ

Решение задачи восстановления регрессии на основе решений коллектива классификаторов ТКАЧЕВ ЮРИЙ ИГОРЕВИЧ

Сегментация формы пространственных изображений ХРОМОВ ДЕНИС ВАЛЕРЬЕВИЧ

Логические алгоритмы классификации: проблема переобучения и применение в задачах медицинской диагностики ЦУРКО ВАРВАРА ВЛАДИМИРОВНА

КАФЕДРА МАТЕМАТИЧЕСКОЙ КИБЕРНЕТИКИ [ГРУППЫ 518,519] Оценки сложности мультиплексорной функции в некоторых классах схем ВЛАСОВ НИКИТА ВАДИМОВИЧ

Исследование сложности умножения в групповых алгебрах ЧОКАЕВ БЕКХАН ВАХАЕВИЧ

Оглавление Метод предобуславливания для блочного алгоритма типа Ланцоша для решения задачи факторизации АЛЕХОВА ЕЛЕНА ЮРЬЕВНА

Свободные от сумм множества в группе Zp ПАВЛОВ АЛЕКСЕЙ ИГОРЕВИЧ

Криптоанализ российского стандарта функции хэширования РУЧКИНА АНАСТАСИЯ АЛЕКСАНДРОВНА

КАФЕДРА АВТОМАТИЗАЦИИ СИСТЕМ ВЫЧИСЛИТЕЛЬНЫХ КОМПЛЕКСОВ [ГРУППЫ 521, 522]

Механизм симметричного удаленного вызова методов, основанный на высокоуровневом языке сериализации данных КЛЕМЕНКОВ ПАВЕЛ АНДРЕЕВИЧ

Методы оценки эффективности значений параметров управления видеокодеком РАГУЛИНА КИРА ОЛЕГОВНА

Алгоритм матирования видеопоследовательности СИНДЕЕВ МИХАИЛ СЕРГЕЕВИЧ

Создание параллельного ядра анализа событий для системы обнаружения и предотвращения атак КАЗАЧКИН ДМИТРИЙ СЕРГЕЕВИЧ

Разработка и реализация средства анализа результатов имитационного моделирования на основе методов нечткого поиска ЧЕРЕЙ МАКСИМ ВИТАЛЬЕВИЧ

Обеспечение совместимости требований к информационному обмену при планировании с применением различных эвристик ШЕСТОВ ПЁТР ЕВГЕНЬЕВИЧ

КАФЕДРА АЛГОРИТМИЧЕСКИХ ЯЗЫКОВ [ГРУППЫ 524,525] Библиотечная поддержка объектно-ориентированной модели языка Рефал БРОНШТЕЙН ИГОРЬ ЕВГЕНЬЕВИЧ

Программируемый агент взаимодействия по протоколу передачи гипертекста ВЛАСЕНКО ЮЛИЯ ВЛАДИМИРОВНА

Методы и алгоритмы контроля доступа и автоматизации технической поддержки в сетях последней мили ФЕДОСЕЕВ ВАСИЛИЙ ОЛЕГОВИЧ

Программные средства поддержки компьютерного словаря буквенных и морфемных паронимов БЕЛОВА ТАТЬЯНА СЕРГЕЕВНА

Использование поисковых машин и ресурсов интернет для отбора терминов предметной области БОНДАРЕНКО ИГОРЬ ВЛАДИМИРОВИЧ

Программная поддержка языка лексико-синтаксических шаблонов LSPL НОСКОВ АЛЕКСЕЙ АНАТОЛЬЕВИЧ

Разработка и реализация модели специализированного режима использования мобильного телефона САНИН АЛЕКСЕЙ ЕВГЕНЬЕВИЧ

–  –  –

КАФЕДРА СИСТЕМНОГО ПРОГРАММИРОВАНИЯ [ГРУППЫ 527,528] Алгоритмы оптимизации программ, обеспечивающие снижение энергопотребления встраиваемых систем БАТУЗОВ КИРИЛЛ АНДРЕЕВИЧ

Разработка статического межпроцедурного алгоритма управления напряжением на процессоре ЖУЙКОВ РОМАН АЛЕКСАНДРОВИЧ

Исследование и реализация распределенного поиска на основе онтологий КУЗНЕЦОВ КОНСТАНТИН АЛЕКСАНДРОВИЧ

Исследование методов построения транзакционной памяти с аппаратной поддержкой и без не МУЗЫЧЕНКО АЛЕКСАНДР ВИКТОРОВИЧ

Система автоматизированного распараллеливания Фортран-программ: анализ многомодульных программ КАТАЕВ НИКИТА АНДРЕЕВИЧ

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

система анализа и визуализации ОСИПОВ АРТЕМ ВАЛЕРЬЕВИЧ

Динамический контроль корректности OpenMP-программСМИРНОВ АЛЕКСАНДР АНДРЕЕВИЧ

Исследование и разработка методов автоматического извлечения семантических отношений из текстов СЫСОЕВ АНДРЕЙ АНАТОЛЬЕВИЧ

ОТДЕЛЕНИЕ БАКАЛАВРОВ

Моделирование распределений приращений финансовых показателей с помощью распределений экстремальных значений ДУЧИЦКИЙ ИГОРЬ АЛЕКСАНДРОВИЧ

Математическое моделирование развития городов СИМАКОВА ОЛЬГА КОНСТАНТИНОВНА

Разработка генератора должностных инструкций МАКСИМОВ ДМИТРИЙ АЛЕКСАНДРОВИЧ

Распределенная система звукового вещания на основе датчиков присутствия ГРЕЧКА ДМИТРИЙ АНДРЕЕВИЧ

Система мониторинга движения общественного транспорта МУХАМЕТДИНОВА ЛЮДМИЛА РАФИСОВНА

Эффективное внедрение флэш-памяти в архитектуру реляционных СУБД .

ЖЕРЕБЦОВ КОНСТАНТИН АЛЕКСАНДРОВИЧ

ОТДЕЛЕНИЕ МАГИСТРАТУРЫ

Безопасная передача сообщений в сетях с использованием сетевого кодирования КОТОВ ИВАН ЕВГЕНЬЕВИЧ

Оглавление Исследование параметров булевских функций, близких к нелинейности ОМАРОВ РУСТАМ РАМАЗАНОВИЧ

Оценка свойств тиражируемых программных продуктов СТЕЛЬМАШЕНКО ДАРЬЯ ЕВГЕНЬЕВНА

Анализ возможностей языка XACML и его использование в J2EE контейнерах ЧЭНЬ ЛИИН

Предобработка биометрических данных на основе метода эмпирических мод ЧЭНЬ НИН

ТЕМЫ ДИПЛОМНЫХ РАБОТ, ЗАЩИЩЕННЫХ В 2009 ГОДУ (ОТДЕЛЕНИЕ СПЕЦИАЛИСТОВ)...... 165 ТЕМЫ ДИПЛОМНЫХ РАБОТ СТУДЕНТОВ, ОКОНЧИВШИХ ОБУЧЕНИЕ В 2006/2007 ИЛИ 2007/2008 УЧЕБНЫХ ГОДАХ

ТЕМЫ ДИПЛОМНЫХ РАБОТ, ЗАЩИЩЕННЫХ В 2009 ГОДУ (ОТДЕЛЕНИЕ БАКАЛАВРОВ)............ 200 АЛФАВИТНЫЙ УКАЗАТЕЛЬ

–  –  –

С растущей потребностью в цифровом широкоформатном теле- и радиовещании возникает необходимость в улучшении качества передаваемого звукового сигнала при малом «битрейте» - скорости передачи данных по цифровому каналу. Используемые на сегодняшний день системы сжатия аудио данных, такие как MPEG Layer 3 (mp3) и Vorbis (ogg), нуждаются в развитии новых технологий, улучшающих воспринимаемое качество сигнала после работы алгоритмов декодирования. Одной из таких технологий стала технологий Расширения Спектральной Полосы (Spectral Band Replication - SBR) [3], которая позволила увеличить эффективность аудио кодирования на 50%. На сегодняшний день данная технология широко используется во многих систем широкоформатного вещания, например, таких как XM Satellite Radio и Digital Radio Mondiale [4] .

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

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

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

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

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

Литература [1]. Eric Larsen, Ronald M. Aarts “Audio Bandwidth Extension. Application of Psychoacoustics, Signal Processing and Loudspeaker Design, November 2004 [2] Martin Jacklin et al. “MPEG-4. The Media Standart, Mpeg4 Industry Forum, November [3] Martin Dietz, Lars Liljeryd et al. “Spectral Band Replication, a novel approach in Audio Coding”, Audio Engineering Society 112-th convention, Munich, 2003 [4] Per Ekstrand “Bandwidth Extension of Audio Signals by Spectral Band Replication”, Proc 1st IEEE Benelux on MPCA Workshop, Belgium, 2002 [5] Л. Рабинер, Б. Гоулд «Теория и применение цифровой обработки сигналов», Изд .

«Мир», Москва 1978 [6] Eric Larsen, Ronald Aarts, Michael Danessis Efficient High-Frequency Bandwidth Extension of Music and Speech, Audio Engineering Society 112-th convention, Munich, 2002 [7] Neil Gershenfeld, Cluster-Weighted Modeling: Probabilistic Time Series Prediction, Characterization and Synthesis, Nature of Mathematical Modeling, MIT Press, 1998, Ch. 15, pp .

365-386 [8] Arttu Laaksonen “Bandwidth Extension in High-Quality Audio Coding, Helsinki University of Technology, 2005, PhD Thesis

–  –  –

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

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

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

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

–  –  –

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

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

Литература

1. Fisher R. A.. The Wave of Advantageous Genes. – Ann.Eugenics 7,355-369, 1937 .

2. Murray J. D.. Mathematical Biology. – Springer NY, 1993 .

3. Колмогоров А. Н., Петровский И. Г., Пискунов Н. С.. Исследование уравнения диффузии, соединнной с возрастанием количества вещества, и его применение к одной биологической проблеме. – Бюлл. МГУ, Секция А. Математика и механика, 1937, т. 1, вып. 6, с. 1-26 .

Тезисы лучших дипломных работ ВМК МГУ 2009 года

АЛГОРИТМ ВОССТАНОВЛЕНИЯ ТРЕХМЕРНЫХ СЦЕН

Семейкина Екатерина Викторовна студентка кафедры математической физики e–mail: semeikinae@gmail.com Научный руководитель – с.н.с., к.ф.-м.н. Юрин Дмитрий Владимирович Целью настоящей работы является построение трехмерной модели сцены по е двумерным проекциям (фотографиям), полученным при неизвестном положении и ориентации камер и неизвестных внутренних параметрах камеры. Восстановление трехмерных сцен применяется в различных приложениях виртуальной реальности .

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

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

1. Поиск характеристич. точек и их векторов признаков

–  –  –

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

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

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

4. Так как, даже используя признаки с хорошей отличительной способностью, нельзя установить соответствия с необходимой степенью надежности, необходимо наложить дополнительные геометрические ограничения на расположение на кадрах отвечающих друг другу точек. Фундаментальная матрица (ФМ) F задает ограничение на то, что точка x' второго кадра, соответствующая точке x первого, должна лежать на линии l Fx (координаты точек здесь и далее - однородные). В дипломной работе реализовано два варианта поиска ФМ: через гомографии и по поточечным соответствиям. Эти соответствия содержат погрешности в координатах точек, и часть соответствий установлена ошибочно и должна быть исключена из вычислений. Для этого применяется робастный статистический алгоритм RANSAC [2], внутри которого итеративно применяется DLT-алгоритм [2] решения СЛАУ, основанный на сингулярном разложении матриц .

Кафедра МФ

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

6. K diag f, f, 1 - калибровочная матрица [2], содержащая на диагонали фокусное расстояние камеры f. С е помощью от ФМ можно перейти к существенной (СМ):

E K T FK. Известно, что два из сингулярных чисел i СМ должны быть равны, а третье равно нулю. Это свойство приводит к следующей задаче минимизации для нахождения фокусного расстояния: f 1 2 .

arg min

7. Следующим этапом является проективное восстановление, то есть определение 3D координат точек с точностью до проективного преобразования трехмерного пространства .

Матрица камеры P – это матрица, с помощью которой производится проектирование из трехмерного пространства на плоскость изображения. Матрица первой камеры может быть выбрана в каноническом виде: P I | 0. Для матрицы второй P ' камеры по СМ находится 4 возможных варианта, выбор среди которых осуществляется путем проверки, что восстановленные точки лежат впереди обеих камер .

3D координаты X точек находятся [2] из системы x PX, x' P' X .

8. На этапе метрического восстановления находится преобразование ректифицирующей гомографии H. Если применить это преобразование к матрицам камер, а обратное - к найденным на предыдущем этапе трехмерным точкам x PHH 1 X, то новые координаты будут восстановлены с точностью до преобразования подобия сцены .

9. Полученная модель представляется в формате VRML (Virtual Reality Modeling Language - язык моделирования виртуальной реальности) .

Рис.1. Пример пары изображений Рис.2. Восстановленные точки, Рис.3. Текстурная модель, (две книги под прямым углом друг к другу) вид сбоку вид спереди Алгоритм был реализован на языке С++. Тестирование показало, что большая часть характеристических точек восстанавливается верно, и погрешность координат таких точек невелика. Неверно восстановленные точки составляют менее 2х процентов от общего числа восстановленных точек. Алгоритм не накладывает существенных ограничений на ракурсы съемки, с которых должны быть сделаны снимки, на масштаб, в котором снимается сцена, и умеренные изменения освещения. Кроме того, для работы алгоритма не требуется проведение каких-либо предварительных калибровочных съемок .

[1] D.G.Lowe Object recognition from local scale-invariant features//ICCV1999-P.1150-1157 .

[2] R. Hartley, A. Zisserman Multiple View Geometry in Computer Vision. Cambridge University Press 2004, 672 p., ISBN:

Тезисы лучших дипломных работ ВМК МГУ 2009 года

–  –  –

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

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

Пусть функция удовлетворяет следующей задаче, в которой определяется :

с дополнительным условием .

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

–  –  –

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

Литература

1. Музылев Н.В. Теоремы единственности для некоторых задач теплопроводности .

- ЖВМ, 1980, Т.20, №2 .

2. Дрожжина О.В. Метод численного восстановления коэффициентов в квазилинейном параболическом уравнении теплопроводности. - Вест. Моск. Ун-та, Сер. 15, 2003, №2 .

3. Щеглов А. Ю. Обратная задача для квазилинейного уравнения теплопроводности .

- Вест. Моск. Ун-та, Сер. 15, 1987,№2 .

4. Ладыженская О.А. Солонников В.А. Уральцева Н.Н. Линейные и квазилинейные уравнения параболического типа. –Москва, Наука, 1967 .

5. Фридман А. Уравнения с частными производными параболического типа. - Москва, Мир, 1967 .

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

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

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

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

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

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

–  –  –

Рисунок 1: Трехмерная визуализация: (a) – входных объемных данных, (b) – сегментированных сосудов печени, (c) – сегментированных областей омывания печени .

Методы были оптимизированы под выполнение на персональном компьютере, реализованны на платформе.NET и встроены в станцию обработки и анализа медицинских данных АРИС MultiVox 5.5. Трехмерная визуализация объемных данных была реализована с использование языка HLSL и адаптирована под выполнение на графическом адаптере персонального компьютера, поддерживающего шейдеры версии 3 [3] (см. Рисунок 1) .

Испытания работы алгоритмов проводились в Российском Научном Центре Хирургии РАМН (лаборатории нагрузочных тестов и абдоминальных методов исследования) и показали их пригодность для использования в качестве диагностических инструментов .

Полученные при использовании разработанного алгоритма сегментации сосудов печени клинические результаты были представлены совместно с сотрудниками ГУ Российский научный центр хирургии им.Б.В. Петровского РАМН, Москва в докладе на ХХ Всероссийском радиологическом съезде 26-28 мая 2009г. г. Москва. [4] Литература

1. Comaniciu, D., Zhou, X.S., Krishnan, S. Robust real-time myocardial border tracking for echocardiography: An information fusion approach. In: IEEE Trans. Medical Imaging .

(2004) V.23, n.7, p. 849-860

2. Selle D., Preim B., Schenk A., Peitgen H.-O. Analysis of vasculature for liver surgical planning. Medical Imaging, IEEE Transactions on Volume 21, Issue 11 (Nov. 2002) p .

1344 – 1357

3. Klaus Engel, Martin Kraus, Thomas Ertl. High-Quality Pre-Integrated Volume Rendering Using Hardware-Accelerated Pixel Shading. Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware. (2001) p. 9-16

4. Ховрин В., Камалов Ю.Р., Ким Е.Ф., Филин А.В., Гаврилов А.В., Архипов И.В., Ятченко А.М. Первый опыт применения отечественной рабочей станции MultiVox 2D/3D для оценки ангиоархитектоники печени у потенциальных родственных доноров фрагментов печени. Тезисы докладов ХХ Всероссийского радиологического съезда. (2009) стр. 53-56 Задача об обтекании источника равномерным потоком является классической задачей динамики несжимаемой жидкости [1] .

В случае сжимаемого газа данная задача исследована гораздо менее подробно. Первое численное решение задачи о соударении сверхзвуковых равномерного и радиального потоков газа, в рамках невязких уравнений Эйлера, было получено в работе [2] при помощи известного метода Бабенко-Русанова [3]. Однако решение [2] было получено лишь для лобовой области взаимодействия. Что касается течения в хвостовой области взаимодействия, то оно обладает гораздо более сложной структурой и для его численного моделирования неизбежно применение метода сквозного счета, что в свою очередь связано с большими вычислительными затратами .

В данной работе осесимметричная задача о взаимодействии равномерного и радиального сверхзвуковых потоков газа в хвостовой области их взаимодействия решается методом С. К. Годунова [4]. При этом численное решение, полученное в [2] для лобовой области, используется в качестве граничного условия на входной границе прямоугольной расчтной области. Граничные условия включают также условия симметрии и так называемые мягкие граничные условия на выходных границах области.

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

и на равномерной сетке (1150x750) со сторонами ячеек: deltaX = 0.013, deltaY = 0.013. В качестве базового варианта рассмотрен случай обтекания гиперзвукового источника равномерным потоком с числом Маха ; показатель адиабаты .

Реализация метода сквозного счета С.К. Годунова написана на языках С++ и С#, в ходе которой была смоделирована и разработана структура данных, полученных в результате решения задачи о соударении сверхзвуковых потоков газа в хвостовой области их взаимодействия, для удобства визуализации. Программа, написанная на языке С++ отлажена для работы на суперкомпьютерном комплексе IBM eSeries p690 («Регатта») и распараллелена с помощью технологии OpenMP. Программа, написанная на языке С#, предназначается для оптимального моделирования задачи на современных персональных компьютерах и использует другой метод для инициализации параллельных вычислений. Для удобной работы с программой, написанной на языке С#, создан многофункциональный пользовательский интерфейс для отображения визуального ряда, численных результатов в любой момент времени и всевозможной работы с данными. Также, на указанных выше языках, написаны скрипты, которые формируют данные для последующей визуализации в виде одномерных графиков значений величин в выделенной точке расчтной области в зависимости от времени. Для визуализации численных результатов в виде изолиний в чрнобелом и цветном вариантах, а также изображений линий тока были использованы: язык Python, функции Matplotlib и NCAR Command Language соответственно .

Кафедра МФ Использование многопроцессорной системы IBM eSeries p690 («Регатта») позволило провести расчты с приемлемой точностью и сократить время счета в несколько раз. В качестве средства для написания параллельных программ использовалась технология OpenMP. В результате были распараллелены все основные циклы по направлению X и по направлению Y, а также добавлен код для синхронизации нитей в конце расчта одного шага по времени. Таким образом, удалось сократить время расчта задачи на сетке 1150х750 на порядок по сравнению с однопроцессорной реализацией (с 219 404 секунд до 46 437 секунд для этой сетки и при заданном времени расчта, равном 200). Расчты проводились с использованием шестнадцати процессоров. Для сравнения вычислительной мощности и конечных результатов была распараллелена программа, написанная на языке С# для работы на современных персональных компьютерах .

Для распараллеливания последовательного кода использовалось: using System.Threading. Расчты проводились с помощью системы Intel® Core™2 Quad CPU Q6600 @ 2.40GHz с 4 процессорами. Выполняя программу при полной нагрузке всех процессоров, удалось сократить время расчта задачи на сетке 1150х750 в 3.25 по сравнению с однопроцессорной реализацией (с 219 404 секунд до 70 097 секунд для этой сетки и при заданном времени расчта, равном 200) .

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

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

Литература [1] Кочин Н.Е., Кибель И.А. Розе Н.В., Теоретическая гидромеханика Т1 .

М.: Физматгиз. 1963 .

[2] Лебедев М.Г., Сандомирская И.Д. Встречное взаимодействие сверхзвуковых невязких потоков газа // Вычислительные методы и программирование. Вып. 34. М.: Изд-во МГУ, 1981 .

[3] Бабенко К.И., Русанов В.В. Разностные методы решения пространственных задач газовой динамики // Труды II Всесоюзного съезда по механике. Обзорные доклады. Вып. 2. М.: Наука, 1965 .

[4] Годунов С.К., Забродин А.В., Иванов М.Я., Крайко А.Н., Прокопов .

«Наука», М.: 1976 .

Тезисы лучших дипломных работ ВМК МГУ 2009 года

–  –  –

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

Динамика таких сред описывается системой двух нелинейных уравнений [1] типа реакция-диффузия [2]:

–  –  –

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

Наилучшую точность по результатам тестирования показала схема 4-го порядка; схема 2-го порядка на смещенной сетке оказалась лучше схемы с искусственным условием в нуле. По времени схема показывает более высокую по сравнению с чисто явной/неявной схемой точность .

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

В зависимости от параметров и выбора стационаров выявлены следующие особенности поведения системы:

стремление к стационарам стабилизация в окрестности стационаров с сохранением формы (рис. 1)

–  –  –

Дополнительно была исследована возможность применения графических процессоров (GPU) для решения задач подобного типа. Аппроксимация дифференциальных уравнений на сетке - в частности, представленный метод решения задачи - обладает высокой степенью параллелизма на каждом из этапов (дискретизация функций по узлам сетки, преобразование Фурье, решение СЛАУ), что позволяет эффективно использовать мощности массово-параллельной архитектуры графического процессора. В качестве программно-аппаратной архитектуры использовалась модель nVidia CUDA. Тестирование проводилось на видеокарте nVidia GTX260 и процессоре Intel Core2Duo E6400. Результаты тестирования показывают, что благодаря использованию графического процессора удается получить ускорение в десятки раз (табл. 1) .

2x32 4x64 28x128 56x256 Ускорение 9 1 3 1, раз.7x 5.9x 4.3x 02.3x Табл. 1. Сравнительная производительность CPU и GPU реализаций, ускорение GPU vs. CPU Алгоритмы решения уравнения Гельмгольца общего вида с граничными условиями различных типов, встречающегося во многих задачах математической физики, были оформлены в виде динамической библиотеки. Реализованы алгоритмы для CPU и GPU .

1. Рахманов А. М., Воронцов М. А., Попова А. П., Шмальгаузен В. И .

Оптическая модель двумерной активной среды // Квантовая электроника, т.19, №7, c.643-645, 1992

2. John G. Alford, Giles Auchmuty. Rotating wave solutions of the FitzHugh-Nagumo equations // Mathematical Biology, Vol. 53: pp. 797–819, 2006 Тезисы лучших дипломных работ ВМК МГУ 2009 года

–  –  –

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

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

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

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

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

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

–  –  –

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

В работе был проведен обзор основных подходов к моделированию турбулентностей, поставлена задача и выведена система полных уравнений, описывающих движение жидкости [1]. Предложен численный метод покоординатного расщепления [2] и его эффективная реализация в программной модели NVDIA CUDA [3] для массивно-параллельной архитектуры графических процессоров. На поставленной задаче проведен сравнительный анализ производительности архитектур новых многоядерных процессоров от Intel, суперкомьютера и графического процессора Было IBM Regatta NVIDIA Tesla .

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

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

Литература

1. Флетчер К. Вычислительные методы в динамике жидкостей. – Москва, Мир, 1991, Том 2 .

2. Пасконов В. М., Березин С. Б., Корухова Е. С. Динамическая система визуализации для многопроцессорных компьютеров с общей памятью и ее применение для численного моделирования турбулентных течений вязких жидкостей. – Москва, Вестник МГУ, 2007 .

3. NVIDIA Corporation. NVIDIA CUDA Programming Guide. – June 2008, Version 2.0

–  –  –

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

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

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

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

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

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

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

Литература В.И. Агошков, С.А. Лебедев, Е.И. Прамузин, «Численное решение проблемы 1 .

вариационной ассимиляции данных спутниковых наблюдений о температуре поверхности океана». //Шестая всероссийская открытая ежегодная конференция «Современные проблемы дистанционного зондирования Земли из космоса» Москва, ИКИ РАН, 10-14 ноября 2008 г .

Сборник тезисов конференции. М. ИКИ РАН. С. 7 .

У.Г. Рис, «Основы дистанционного зондирования». /Пер. с англ. М.Б. Кауфмана и 2 .

А.А. Кузьмичевой. – М: Техносфера, 2006. – 336 с. (Rees W.G. Physical Principles of Remote Sensing. 2nd Edition. – Cambridge University Press. 2001. – 372 pp.)

3. V. Agoshkov, E. Botvinovsky, A. Gusev, S. Lebedev, E. Parmuzin and V. Shutyaev, «Variational data assimilation system INM-T1». //Geophysical Research Abstracts, Vol. 10, EGU2008-A-08220, 2008, SRef-ID: 1607-7962/gra/EGU2008-A-08220, EGU General Assembly 2008 .

С.А. Лебедев, В.И. Агошков, «Структура базы данных «Мировой океан – ИВМ РАН»

4 .

Института вычислительной математики Российской академии наук». - Отчет, 2006 .

А.А. Самарский, П.Н. Вабищевич, «Численные методы решения обратных задач 5 .

математической физики». – М.: ЛКИ, 2007 .

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

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

Первые попытки повысить точность аппроксимации краевых условий на криволинейной границе на декартовых сетках появились в конце пятидесятых годов XX века. В настоящее время широко используются такие методы как метод ступенчатого представления границы (stair-step method), метод скошенных ячеек (cut-cell method), метод внеснной границы (immersed boundary method). Из перечисленных методов все большее практическое распространение получают различные варианты метода внесенной границы .

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

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

Литература

1. R. Mittal, G. Iaccarino. Immersed boundary methods. Annual Review of Fluid Mechanics 2005 37: 239-261. 2005 .

2. J. Mohd-Yosuf. Combined immersed boundary/B-spline methods for simulation of flow in complex geometries. Annual Research Briefs, Center for Turbulence Research 317-328. 1997 .

Кафедра ВТМ

–  –  –

Дипломная работа посвящена разработке методов и алгоритмов оценки влияния генетических факторов на заболевания на примере туберкулеза. Основным участком геномной ДНК человека, контролирующим функцию системы защиты организма при заболеваниях, является главный комплекс гистосовместимости (HLA), локализованный в 6-й хромосоме. В работе предложена программа-оболочка IrGene для анализа 1.0 популяционного полиморфизма системы HLA и попарных сравнений частотных распределений генотипических признаков на основе таблиц сопряженности [1]. С ее использованием по данным ДНК-типирования низкого разрешения, предоставленным отделом иммуногенетики человека Института иммунологии ФМБА России, построены оценки величин относительного риска и описаны маркеры наследственной предрасположенности к развитию туберкулеза [2]. Численно реализована блочная модель патогенеза туберкулезной инфекции, предложенная в работе [3], и рассмотрена схема учета влияния генетических полиморфизмов на процессы иммунной защиты при туберкулезной инфекции .

Литература

1. Сытин Е.А. IrGene 1.0 – интерфейс и программа для анализа популяционногенетических данных в иммунологии // Сб. статей молодых ученых факультета ВМК МГУ им. М.В. Ломоносова. 2009. Вып. 6 (в печати) .

2. Селицкая Р.П., Болдырева М.Н., Родин А.А., Сытин Е.А. и соавт. О полиморфизме DRB1-локуса системы HLA и восприимчивости к туберкулзу // Иммунология. 2009 (представлено к публ.)

3. Wigginton J.E., Kirschner D.E. A model to predict cell-mediated immune regulatory mechanisms during human infection with Mycobacterium tuberculosis // J. Immunol. 2001 .

V. 166. P. 1951–1965 .

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

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

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

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

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

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

Литература

1. Самарский А.А. Теория разностных схем. 1977 .

2. Ионкин Н.И. Задача для уравнения теплопроводности с неклассическим (нелокальным) краевым условием. 1979 .

3. Гулин А.В., Ионкин Н.И., Морозова А.В. Устойчивость нелокальных разностных схем. 2008 .

4. Абрамов А.А., Андреев В.Б. О применении метода прогонки к нахождению периодических решений дифференциальных и разностных уравнений. ЖВМ и МФ, 3, № 2, с. 377 – 381, 1963 .

–  –  –

Дипломная работа посвящена моделированию некоторых аспектов социальноэкологического характера в развитии крупного города. В современном обществе одной из немаловажных мировых проблем является вопрос об управлении очисткой твердых бытовых отходов. Тврдые бытовые отходы (ТБО) — товары, потерявшие потребительские свойства, наибольшая часть отходов потребления. Ежегодно количество мусора возрастает примерно на 3% по объму. Количество ТБО в СНГ составляет более 100 млн. тонн/год. Проблема управления очисткой твердых бытовых отходов занимает в системе городского хозяйства второе место по затратам и инвестициям после сектора водоснабжения и канализации .

Постулаты ядра модели .

Прирост численности населения увеличивает как прирост мусора – ТБО, так и радиус городского расселения;

–  –  –

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

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

жесткость законодательства и рост цен отражены в конечном радиусе R0 .

На основе этих постулатов была разработана математическая модель, которая описывается системой из одиннадцати ОДУ и задает задачу Коши:

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

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

Литература

1. Шведовская Т.Л., Шведовский В.А. Моделирование управления санитарной очисткой твердых бытовых отходов. Сборник статей XI Международной научно-практической конференции "Промышленные и бытовые отходы: проблемы хранения, захоронения, утилизации, контроля", Пензенский Дом Знаний, 2006 г .

2. Maruyama M. The second cybernetics: deviation-amplifying mutual causal processes .

Amer. Sci. 51: 164-79, 1963, p.176

3. Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам/Пер. с англ. А.М.Раппопорта, С.И.Травкина .

Под ред. А.И.Теймана. – М.: Наука. Гл. ред. физ.-мат. лит., 1986. – 496с .

Кафедра АНИ

–  –  –

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

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

Автор некоторое время занимался исследованиями в этой области, например, задачей ускорения обучения нейросети, результаты были опубликованы в [7] и [8]. Прототип алгоритма реконструкции на видеокарте работает на 1-2 порядка (в зависимости от размера изображения) быстрее, чем на центральном процессоре .

Рис. 1. Некоторые из результатов реконструкции карты глубины по двум кадрам. На рисунках изображены две трехмерные поверхности, построенные по картам глубины .

–  –  –

2. Lucas B. Generalized Image Matching by the Method of Differences, doctoral dissertation, 1984: [http://www.ri.cmu.edu/pubs/pub_5610.html], апрель 2009

3. Lucas B. and Kanade T. An iterative image registration technique with an application to stereo vision. Proc. DARPA IU Workshop, pp. 121-130, 1981 .

4. Thomas Brox et al. High Accuracy Optical Flow Estimation Based on a Theory for Warping. - Computer Vision - ECCV 2004 .

5. Thomas Pock et al. A Duality Based Algorithm for TV-L1-Optical-Flow Image Registration. - Lecture Notes in Computer Science, vol. 4792/2007, pp. 511-518, Springer Berlin / Heidelberg, 2007 .

6. CUDA 2.0 Programming Guide:

[http://developer.download.nvidia.com/compute/cuda/2_0/docs/NVIDIA_CUDA_Progr amming_Guide_2.0.pdf], сентябрь 2008

7. Б.Г.Севрюков. Ускорение процесса обучения нейросети за счет использования графического акселератора. - Материалы докладов XV Международной конференции студентов, аспирантов и молодых ученых «Ломоносов» .

[Электронный ресурс] - М.: Издательство МГУ; СП МЫСЛЬ, 2008, с. 52-53 .

8. А.А.Лукьяница, Б.Г.Севрюков.Ускорение процесса обучения нейросети за счет использования графического акселератора. - Параллельные вычислительные технологии (ПаВТ‘2009): Труды международной научной конференции [Электронное издание] – Челябинск: Изд. ЮУрГУ, 2009, 839с, с. 579-587

9. C.Tomasi and T.Kanade. Detection and tracking of point features. Technical Report CMU-CS-91-132, CMU, 1991: [www.ces.clemson.edu/~stb/klt/tomasi-kanadetechreport-1991.pdf], - апрель 2009

10. C. Harris, M. Stephens. A combined corner and edge detector. - Proc. 4th Alvey Vision Conference, pp. 147-151, 1988 .

11. M.Han, T.Kanade. A perspective factorization method for Euclidean reconstruction with uncalibrated cameras, 2002

12. Tomasi C., Kanade T. Shape and Motion from Image Streams: a factorization method. Proceedings of the National Academy of Sciences of the United States of America, vol .

90, issue 21, pp. 9795-9802, 1993 .

13. S. Mahamud, M. Herbert, Y. Omori, J. Ponce. Probably-convergent iterative methods for projective structure from motion. - In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2001 .

14. Hartley R., Zisserman A. Multiple View Geometry in Computer Vision. - Cambridge University Press, 2nd edition, 672pp, 2004

–  –  –

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

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

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

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

–  –  –

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

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

Дипломная работа посвящена одной из самых важных проблем, которая решается при анализе видеоизображения – нахождению траекторий объектов, за которыми ведется наблюдение .

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

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

Тезисы лучших дипломных работ ВМК МГУ 2009 года Результаты, полученные автором, включены в труды следующих международных конференций по компьютерному зрению и анализу изображений: «International Conference on Computer Vision Theory and Applications» (VISAPP 2009, Лиссабон, Португалия), «The 2009 International Conference on Image Processing, Computer Vision, and Pattern Recognition» (IPCV 2009, Лас-Вегас, США), а также приняты к участию в конференции «IEEE Congress on Evolutionary Computation» (Трондхейм, Норвегия). Он стал финалистом конкурса курсовых и дипломных проектов, проводимого компанией Intel в рамках конференции Graphicon-2008 (23-27 июня 2008 г.) .

Литература

1. T. Cham, J. Rehg, A multiple hypothesis approach to figure tracking. In IEEE International Conference on Computer Vision and Pattern Recognition. 239-245, 1999 .

2. Chang, Y. L. and Aggarval, J. K. 1991. 3d structure reconstruction from an ego motion sequence using statistical estimation and detection theory. In Workshop on Visual Motion. 268– 273 .

3. D. Chetverikov and J. Verestoy, "Feature Point Tracking for Incompete Trajectories,"Computing, vol 62, pp. 321-338, 1999 .

4. I.J. Cox, A Review of Statistical Data Association Techniques for Motion Correspondence, Int‘l J. Computer Vision, vol. 10, no. 1, pp. 53-66, 1993 .

5. I.J. Cox, S. Hingorani, An efficient implementation of reid‘s multiple hypothesis tracking algorighm and its evalutaion for the purpose of visual tracking. IEEE Trans. Patt. Analy. Mach .

Intell. 18, 2, 138 - 150, 1996 .

6. M.R.W. Dawson, The How and Why of What Went Where in Apparent Motion: Modeling Solutions to the Motion Correspondence Problem, Psychological Rev., vol. 98, pp. 569-603, 1991 .

7. Johansson, Spatio-Temporal Differentiation and Integration in Visual Motion Perception, Psychological Research, vol. 38, pp. 379- 393, 1976 .

8. T.E. Fortmann, Y. Bar-Shalom, and M. Sheffe,.Sonar Tracking of Multiple Targets Using Joint Probabilistic Data Association, IEEE J. Oceanic Eng., vol. 8, no. 3, pp. 173-184, July 1983 .

9. B.K.P. Horn and B.G. Schunck, Determining Optical Flow, Artificial Intelligence, vol. 17, pp. 185-203, 1981. R.Y .

10. K. Rangarajan and M. Sha, "Establishing Motion Correspondence," CVGIP: Image Understanding, vol. 24, no. 6, pp. 56-73, July 1991 .

11. C. Rasmussen, G. Hager, 2001. Probabilistic data association methods for tracking complex visual objects. IEEE Trans. Patt. Analy. Mach. Intell. 23, 6, 560–576 .

12. D.B. Reid, An Algorithm for Tracking Multiple Targets, IEEE Trans. Automatic Control, vol. 24, no. 6, pp. 843-854, Dec. 1979 .

13. I.K. Sethi and R. Jain, Finding Trajectories of Feature Points in a Monocular Image Sequence,"IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 9, no. 1, pp. 56-73, Jan .

1987 .

14. Tsai and T.S. Huang, Uniqueness and Estimation of Three- Dimensional Motion Parameters of Rigid Objects with Curved Surface, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 6, no. 1, pp. 13-26, Jan. 1984 .

15. S. Ullman, The Interpretation of Visual Motion. Cambridge, Mass.: MIT Press, 1979 .

16. Veenman, C., Reinders, M., and Backer, E. 2001. Resolving motion correspondence for densely moving points. IEEE Trans. Patt. Analy. Mach. Intell. 23, 1, 54–72 .

17. C.J. Veenman, E.H. Hendriks, and M.J.T. Reinders, A Fast and Robust Point Tracking Algorithm, Proc. IEEE Int‘l Conf. on Image Processing, vol. 3, pp. 653-657, Oct. 1998 .

Кафедра АНИ

–  –  –

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

В дипломной работе впервые проведено численное моделирование из первых принципов (без эмпирических параметров) процесса изменения проводимости молекулы с использованием метода квантомеханической молекулярной динамики в формулировке КарПарринелло [2]. Использовался параллельный код квантовой молекулярной динамики CPMD [3-4], инсталлированный автором на супер-ЭВМ IBM BlueGene/P. Проедение расчетов стало возможным благодаря использованию супер-ЭВМ IBM BlueGene/P, так как вычисления одного варианта с помощью однопроцессорного компьютера длилось бы 3 года .

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

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

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

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

С помощью метода метадинамики получены характеристики поверхности свободной 2 .

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

Проведен анализ эволюции электронной плотности в процессе переключения, 3 .

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

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

Литература Peter Lijeroth, Jascha Repp, Gerhard Meyer, Current-Induced Hydrogen Tautomerization and 1 .

Conductance Switching of Naphthalocyanine Molecules, Science, 317, pp. 1203-1206, 31 August, 2007 R. Car and M. Parrinello, Unified approach for molecular dynamics and density- functional 2 .

theory, Physical Review Letters, 55, pp. 2471-2474, 1985 W. Andreoni and A. Curioni, New advances in chemistry and Materials Science with CPMD 3 .

and Parallel Computing, Parallel Computing, 26, pp. 819-842, 2000

4. The CPMD consortium, http://www.cpmd.org A. Laio and M. Parrinello, Escaping free-energy minima, PNAS, 99, № 20, 2002 5 .

–  –  –

изображений рукописных цифр MNIST и базы фотоизображений объектов на сложном фоне NORB, была получена оценка производительности нейронной сети LICS, а также исследованы ее свойства и особенности. Обе базы находятся в свободном доступе по веб-адресу http://yann.lecun.com .

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

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

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

Исследование нейронной сети LICS, а также результаты, полученные на базе изображений MNIST, были опубликованы в журнале Российской Академии Наук «Информационные Технологии и Вычислительные Системы» (1, 2009) .

–  –  –

лежат строго внутри единичного круга на комплексной плоскости .

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

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

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

Проверка необходимого условия одновременной стабилизации основана на исследовании совместности систем линейных неравенств Кафедра НДС иПУ

–  –  –

фазовом пространстве .

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

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

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

Литература

1. Ахомеева Т.С., Курдюмов С.П. Нестационарные структуры и диффузионный хаос. М.:

Наука, 1992

2. Ахомеева Т.С., Малинецкий Г.Г. Двухкомпонентные диссипативные системы в окрестности точки бифуркации // Математическое моделирование. Процессы в нелинейных средах. М.: Наука, 1986, С. 1-51 .

3. Kuramoto Y., Tsuzuki T. On the formation of dissipative structures in reaction-diffusion systems.// Progr. Theor. Phys., 1975, vol. 54, N 3, p. 687--699 .

4. Kuramoto Y. Diffusion-induced chaos in reaction systems.// Suppl. Progr. Theor. Phys., 1978, N 64, p. 346--367 .

Кафедра НДС иПУ

–  –  –

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

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

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

Это дает два важных результата:

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

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

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

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

Литература

1. С.В. Емельянов, С.К. Коровин Новые типы обратной связи: Управление при неопределенности – М.: Наука. Физматлит, 1997

2. С.В. Емельянов Системы автоматического управления с переменной структурой. М.:

Наука, 1967

3. Д.П. Ким Теория автоматического управления. Т.1. Линейные системы, Т.2 .

Многомерные, нелинейные, оптимальные и адаптивные системы. – М.: Физматлит, 2003

–  –  –

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

[4], [7]) являются непрерывными деформациями орбитально-устойчивых периодических решений (циклов) в диссипативном случае (их положение в фазовом пространстве непрерывно зависит от параметров системы), что говорит о связи сложной динамики в этих двух случаях. В области высокой диссипации порядок появления циклов с ростом одного из параметров в точности совпадает с порядком появления циклов в унимодальных отображениях (дискретная динамическая система, см. [1]). Затем, с уменьшением диссипации, области устойчивости циклов начинаю пересекаться, и строгий порядок нарушается, переходя в консервативном случае в тот порядок, в котором возникают ‹‹островки››. Выявить строгих закономерностей здесь уже не удается, хотя есть попытки объяснить их с помощью специальных полимодальных отображений (см. [5],[6]). Следует отметить, что исследования в данной области за рубежом проводятся и публикуются в разделе полученные нами данные нельзя считать строгим Experimental Math, математическим фактом, а лишь некой информацией к размышлению .

Литература

1. K.T. Hansen, Bifurcation structures for multimodal maps, Submitted to Experimental Math, 1997. \\ http://alf.nbi.dk/khansen/papers/multi mod.ps.gz

2. Магницкий Н.А., Сидоров С.В. Новые методы хаотической динамики. - М.:Едиториал УРСС, 2004 .

3. Шустер Г., Детерминированный хаос: введение. - М.:Мир, 1988 .

4. Трещев Д.В., Гамильтонова механика. - М.:Лекционные курсы НОЦ, выпуск 4, 2006 .

5. K.T. Hansen, P. Cvitanovich, Bifurcation structures in maps of Henon type, Nonlinearity 11 1233-1261, 1998 .

6. D.Sterling, H.R. Dullin, Homoclinic Bifurcations for the Henon Map, Physica D Vol. 134 Issue 2, 1999 .

7. Арнольд В.И., Математические методы классической механики. - М.:Наука, 1974 Кафедра ОМ

–  –  –

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

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

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

–  –  –

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

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

–  –  –

(3) (4) (5) (6) В условиях (3)-(6) удовлетворяет неравенству, – произвольная константа .

Основные результаты работы:

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

–  –  –

рода на левом конце и нелокальным условием второго рода для произвольных значений [0,l) и для произвольного T0 .

параметра, любых

3. Получен явный вид обобщенного решения смешанной задачи для уравнения колебаний струны на отрезке с нулевыми начальными условиями, граничным условием второго рода на левом конце и нелокальным условием первого рода для произвольных значений [0,l) и для произвольного T0 .

параметра, любых

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

–  –  –

Литература

1. В.А.Ильин. Граничное управление процессом колебаний на двух концах в терминах обобщенного решения волнового уравнения с конечной энергией. – Дифференциальные уравнения, 2000, Т.36, N 11. с. 1513 - 1528 .

2. В.А.Ильин. Единственность обобщенных решений смешанных задач для волнового уравнения с нелокальными граничными условиями. – Дифференциальные уравнения, 2008, Т.44, N 5. с. 672 - 680 .

3. В.А.Ильин. Аналитический вид оптимального граничного управления смещением на одном конце струны с модельным нелокальным граничным условием одного из четырех типов. – Доклады Академии наук, 2008, Т.420, N 3. с. 309 - 313 .

4. В.А.Ильин. Оптимизация граничного управления упругой силой на одном конце струны с модельным нелокальным граничным условием одного из четырех типов. – Доклады Академии наук, 2008, Т.420, N 4. с. 442 - 446 .

5. В.А.Ильин. Оптимизация граничного управления на одном конце струны при наличии модельного нелокального граничного условия. – Дифференциальные уравнения, 2008, Т.44, N 11. с. 1487 - 1498 .

6. А.А.Холомеева. Оптимизация нелокального граничного управления колебаниями струны с закрепленным концом за произвольный кратный 2l промежуток времени. – Дифференциальные уравнения, 2008, Т.44, N 5. с. 696 - 700 .

–  –  –

| 1. Установлена равносходимость вплоть до границы отрезка O( ln | |), | k k k биортогональных разложений функций по корневым функциям оператора L с разложением этой функции в обычный тригонометрический ряд Фурье. Получены точные оценки скорости равносходимости на всем интервале. Показана зависимость скорости равносходимости от расстояния от компакта до границы основного интервала. Полученные оценки скорости равносходимости могут существенно зависеть от степени суммируемости s коэффициента при первой производной .

–  –  –

Рассматривается решение из класса функций, непрерывных в замкнутой области D, непрерывно дифференцируемых в открытой области D, за вычетом отрезков характеристик C i E i, E i С i 1, выпускаемых последовательно из точки C1 ( p, p) и из точек пересечения этих характеристик с линией изменения типа, либо с границей, и дважды непрерывно дифференцируемых в открытой области D, за вычетом линии изменения типа и указанных отрезков характеристик. В работе доказывается принцип экстремума и единственность решения рассматриваемой задачи. Актуальность задач такого рода для приложения к моделям трансзвуковой газодинамики описана Ф.И. Франклем в работе [1] .

Литература

1. Франкль Ф.И. Избранные труды по газовой динамике. – Москва, Наука, 1973 .

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

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

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

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

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

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

Литература

1. Р.Фейнман. Теория фундаментальных процессов, Наука, 1978

2. Р.Фейнманб А.Хиббс. Квантовая механика и интегралы по траекториям, Мир, 1968

3. Нильсен М., Чанг И. Квантовые вычисления и квантовая информация, Мир, 2006

4. Р.Фейнман. Квантовая электродинамика, Мир, 1964

5. Ожигов Ю.И. Конструктивная физика

–  –  –

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

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

В рамках использования предложенной системы вихревого прогноза самолеты условно делятся на 3 типа по массе, посадочной скорости, размаху крыла и некоторым аэродинамическим характеристикам. Минимальные безопасные расстояния в эшелоне зависят от типов следующих друг за другом самолетов. Они определяются на основе расчета времен освобождения окон, расположенных вдоль глиссады, от вихревого следа пролетевшего первым самолета. При этом учитываются размеры окон, влияние земли, и погодные условия (боковой ветер, атмосферное давление и турбулентность). Для учета атмосферной турбулентности использовалась EDR(Energy Dissipation Rate)-модель Сарпкайя. По безопасным расстояниям между самолетами различных типов определяется максимально возможная длина эшелона, ограниченная размерами воздушного пространства аэропорта, а также числом самолетов в наиболее длинном эшелоне. Самолеты, прибывающие сверх этого числа, при неблагоприятном стечении обстоятельств не смогут пристроиться в эшелон и вынуждены будут пойти на второй круг. ВПП рассматривается как система массового обслуживания. Самолеты прибывают по пуассоновскому закону с параметром. Вероятность принадлежности самолета заданному типу определяется Тезисы лучших дипломных работ ВМК МГУ 2009 года частотой посадок самолетов этого типа в соответствии с расписанием полетов. Время обслуживания самолета предполагается случайной величиной, равной интервалам времени между посадками данного и предшествующего ему самолетов. Вероятность того, что за интервал времени между двумя последовательными посадками в эшелон добавилось ровно k самолетов, равна где - вероятность прилета самолета i-го типа. Число самолетов в эшелоне рассматривается как состояние цепи Маркова. Находится максимальное значение параметра, при котором вероятность захода самолетов на второй круг не превосходит заданную предельно допустимую величину. Это значение полагается равным пропускной способности ВПП. При расчете пропускной способности ВПП учитывались статистические данные о повторяемости ветров в районе аэропорта в виде розы ветров .

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

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

Поддержано грантом президента РФ «Поддержка ведущих научных школ», проект №НШ-693.2008.1 и грантом РФФИ, проект №08-01-00-249 .

Литература

1. В.И. Бабкин, А.С. Белоцерковский, В.В. Морозов и др. Системы обеспечения вихревой безопасности полетов летательных аппаратов. М. 2008г .

2. Green G.C. An approximate model of vortex decay in the atmosphere. J. of Aircraft, Vol.23, July 1986. P. 566-573 .

3. Белоцерковский С.М. Скобелев Б.Ю. Метод дискретных вихрей и турбулентность .

Препринт № 10-93. Новосибирск: Институт прикладной и теоретической механики, 1993 .

4. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М., 1969г .

–  –  –

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

В начале 70–х годов ХХ века появились модели рынка ценных бумаг(определение и виды ценных бумаг подробно описаны, например в [1]), в рамках которых можно исследовать динамику поведения цен ценных бумаг, в частности опционов и облигаций .

Наиболее известной из этих моделей является диффузионная модель рынка Блэка-МертонаШоуллса [2-3], используя различные модификации которой, Гербер [4], Кокс[5], Бюттлер[6] и другие авторы получили аналитические оценки для различных типов ценных бумаг .

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

ut ( x, t ) Au ( x, t ), t 0, x 0, u( x,0) ( x), x 0, Bu(0, t ) 0, t 0, (1) где B - заданный дифференциальный оператор первого порядка по x .

В работе показывается, что для рассматриваемой задачи применима известная теорема Стоуна [7], в силу которой решение задачи (1) представляется в виде:

t u ( x, t ) e (dE )( x), (2)

–  –  –

Рассматривалась игра трех лиц N={1,2,3} по выборам одного из кандидатов {a,b,c} .

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

Если функции полезности от избрания кандидата заданы следующим циклическим образом:

U1(a)=0, U1(b)=1/2, U1(c)=1;

U2(b)=0, U2(c)=1/2, U2(a)=1;

U3(c)=0, U3(a)=1/2, U3(b)=1, то согласно утверждению Э.Мулена, при информированности игроков относительно функций полезности каждого будет избран кандидат а, наихудший для первого. Такая игра получила название Парадокс Кондорсе .

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

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

Изучены аналитические свойства игры с побочными платежами. Игра сведена к иерархической игре, состоящей из одного этапа. Показано, что функция наилучшего гарантированного результата Wi(pi,p-i), где pi – вектор предложений побочных платежей i-го игрока, а p-I – векторы предложений остальных игроков, является кусочно-линейной функцией, имеющей конечное число граней разрыва, а область непрерывности представляет собой выпуклое многогранное множество .

Литература

1) Мулен Э. Теория игр с примерами из математической экономики. М: Мир, 1985 .

2) Васин А.А., Морозов В.В. Теория игр и модели математической экономики. М.: МАКС Пресс, 2005 г .

3) Gehrlein WV. Condorcet‘s Paradox and the likelihood of its occurrence: Different perspectives on balanced preferences. Theory and Decision 52: 171-199., 2001

4) Gehrlein WV.Condorcet winners on four candidates with anonymous voters. Economics Letters 71: 335-340, 2001 .

5) Fishburn PC, Gehrlein WV. Borda's rule, positional voting, and Condorcet's simple majority principle. Public Choice 28: 79-88., 1976

6) Fishburn PC, Gehrlein WV. An analysis of voting procedures with nonranked voting .

Behavorial Sciences 22: 178-185.,1977

7) Tovey CA.Probabilities of preferences and cycles with supermajority rules. Journal of Economic Theory 75: 271-279, 1997 .

8) Condorcet M de. An essay on the application of probability theory to plurality decision making: An election between three candidates.,1785. In: Sommerlad F, McLean I .

9) The political theory of Condorcet. University of Oxford Working Paper, Oxford, pp 90-108 .

(1989,eds) Тезисы лучших дипломных работ ВМК МГУ 2009 года

–  –  –

F ( K (t ), N тр (t )) - производственная функция, определяющая величину выпуска обобщенного продукта, производимого в государстве с - среднее потребление на душу населения .

Z (t ) - затраты на решение демографических проблем (повышение рождаемости, привлечение мигрантов и др.) .

r (t ) [0, rmax ] - коэффициент рождаемости,

–  –  –

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

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

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

Литература

1. Д.М.Эдиев, «Демографические потенциалы. Теория и приложения». М.:

МАКС Пресс,. 2007

2. В.И. Дмитриев, Е.С. Куркина «Математическое моделирование демографических процессов»

3. Галахов М.А., Орлов Ю.Н., Суслин В.М. Математические модели жизнеустройства. Демография. Препринт ИПМ им. М.В. Келдыша РАН, № 69, 2000 .

4. Российский статистический ежегодник. М.: Госкомстат, 2008 .

–  –  –

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

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

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

Таким образом, данная игровая модель представима в следующем виде:

U1(1) U1(a1) U1(b1) U1(c1), a1, b1, c1 {2,3,4};

U2(2) U2(a2) ? U2(b2) ? U2(c2), a2, b2, c2 {1,3,4};

U3(3) U3(a3) ? U3(b3) ? U3(c3), a3, b3, c3 {1,2,4} .

Были исследованы две модели выборов. Первая – закрытое голосование. Игроки накладывают сво вето одновременно, после чего, на каждом туре, по заранее определнному правилу исключается кандидат(ы). Для этой модели было доказано е несоответствие содержательной постановке изначальной задачи .

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

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

Выяснилось, что обе игры с последовательным голосованием распадаются на два типа игровых форм:

1. для игрока, голосующего вторым, кандидат от первого игрока более выгоден, чем кандидат от ещ не проголосовавшего выборщика;

2. для игрока, голосующего вторым, кандидат от первого игрока не выгоднее (строго хуже для однокритериальной игры) кандидата от 3-го игрока .

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

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

Указанные результаты опубликованы в сборнике "Прикладная математика и информатика" (принята к печати в № 31). Работа выполнена по программе государственной поддержки ведущих научных школ (код проекта НШ-693.2008.1) .

Литература

Васин А.А., Морозов В.В. Теория игр и модели математической экономики. М.:

1 .

МАКС Пресс, 2005 г .

Мулен Э. Теория игр с примерами из математической экономики. М: Мир, 1985 .

2 .

Гермейер Ю.Б. Игры с непротивоположными интересами. М.: Наука, 1976 .

3 .

Borda J.C. Mmoire sur les lections au scrutin. Paris : Histoire de l'Acadmie Royale 4 .

des Sciences, 1781 .

Condorcet M. Essai sur l‘application de l‘analyse la probabilit des dcisions 5 .

rendues la pluralit des voix. Paris: Imprimerie royale, 1785 .

6. Arrow K. Social choice and individual values. New York: Wiley, 1951 .

7. Farquharson R. Theory of Voting. New Haven, CT: Yale University Press, 1969 .

8. Mueller D.C. Voting by Veto// Journal of Public Economics 10, 57-75, 1978 .

9. Moulin H. The Strategy of Social Choice. Amsterdam: North-Holland Publ., 1983 .

10. Felsenthal D.S. and Machover M. Sequential Voting by Veto: Making the MuellerMoulin Algorithm More Versatile// Theory and Decision 33:3, 223–240, 1992 .

11. Yuval F. Sophisticated voting under the sequential voting by veto//Theory and Decision 53: 343-369, 2002 .

–  –  –

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

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

Рассматривается однородная группа плательщиков с распределением дохода I, заданным функцией плотности 0. Обозначим через налоговое (I ), I T ( I ) tI обязательство, соответствующие доходу I. Плательщики максимизируют свой чистый доход, декларируя доход I d в зависимости от реального дохода I и от стратегии центра. Центр организует двухуровневую систему проверки – на первом уровне помещаются рациональные риск-нейтральные инспектора, максимизирующие свой доход, на втором уровне – идеальные инспектора, всегда проверяющие честно. Идеальные инспектора получают заработную плату s, намного превосходящую заработную плату рационального инспектора s. Государство проверяет с вероятностью p ( I d ) тех, кто декларировал доход I d. Инспектор первого уровня может быть подкуплен уклоняющимся плательщиком и сообщить центру о вскрытом доходе [ I d, I ). Если инспектор первого уровня не подкуплен, то он всегда вскрывает реальный IR

–  –  –

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

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

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

Инспекция проводится в несколько этапов. Сначала рациональные инспекторы нулевого уровня с некоторой вероятностью проводят проверку налогоплательщиков, указавших в декларациях низкий доход. Затем рациональные инспекторы 1-го уровня проверяют работу своих коллег нулевого уровня с выбранной вероятностью и т.д. На последнем (k-ом уровне) доверенные лица проверяют работу рациональных инспекторов k-1го уровня .

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

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

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

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

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

3. Чистый налоговый доход существенно зависит от точности определения альтернативной зарплаты .

Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований по проекту 08-01-00249 и гранта НШ 693.2008.1

–  –  –

компонента которого отражает попарные политические взаимоотношения между двумя из трех стран в момент времени k. rijk принимает значение 0, в случае негативных отношений, или значение 1, в случае позитивных отношений. Переменная g k в бинарном смысле отражает наличие поставки газа от поставщика к потребителю в момент времени k .

(rst, rtc, rsct, g k ) – вектор расширенного состояния системы, с начальным состоянием xk k k k

–  –  –

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

Первый подход использует пространство состояний системы, описываемых вектором r k. C помощью исходно заданных условных вероятностей строится матрица переходных вероятностей A [aij ]8 j 1 и вектор-столбец вероятностей перехода в состояние коллапса i,

q [qi ]8 1. Выведены явные формулы для вероятности наступления коллапса на шаге k :

i

–  –  –

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

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

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

Проведено исследование модели диффузии информации (2) с помощью принципа максимума Понтрягина .

Кафедра ОУ

–  –  –

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

Литература

1. Гусейнов Х.Г., Моисеев А.Н., Ушаков В.Н. Об аппроксимации областей достижимости управляемых систем.// Прикладная математика и механика, 1998. Т.62, вып.2, с. 179-187 .

2. Спесивцев Л.В., Ушаков В.Н. Задача о приведении движения управляемой системы в окрестность заданной точки множества достижимости.// Вестник Удмуртского университета. Серия математика. 2006. №1. c. 111-126 .

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

1987. Т. 4. c. 31-34 .

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

5. Горнов А.Ю., Тятюшкин А.И. Вычислительные технологии поиска глобального экстремума в задаче оптимального управления. Материалы международной конференция «Вычислительные и информационные технологии в науке, технике и образовании» .

Алматы, Казахстан, 10-14 сентября 2008 года .

6. Черноусько Ф.Л. Оценивание фазового состояния динамических систем. Метод эллипсоидов. М., Наука, 1988 .

7. Измоденова К.В., Михайлов А.П. Об оптимальном управлении процессом распространения информации.// Математическое моделирование. 2005. Т. 17. № 5, с. 67Киселв Ю.Н., Аввакумов С.Н., Орлов М.В. Оптимальное управление. Линейная теория и приложения. М., МАКС Пресс, 2007 .

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

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

1997. Т. 3. Выпуск 3, с. 847-868 .

11. Самарский А.А., Гулин А.В. Численные методы. М., Наука, 1989 .

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

Екатеринбург: Ин-т матем. и механ. УрО РАН, 2005. 106с .

Тезисы лучших дипломных работ ВМК МГУ 2009 года

–  –  –

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

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

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

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

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

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

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

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

Это позволило сделать следующие экономические выводы:

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

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

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

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

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

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

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

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

Тезисы лучших дипломных работ ВМК МГУ 2009 года

–  –  –

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

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

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

3. Jonathan P. Caulkins, Gustav Feichtinger, Dieter Grass, Michael Johnsonm Gernot

Tragler, Yuri Yegorov. Placing the Poor While Keeping the Rich in Their Place:

Separating Strategies for Optimally Managing Residential Mobility and Assimilation .

29 November 2004 .

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

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

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

Кафедра ОУ

–  –  –

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

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

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

–  –  –

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

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

Литература

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

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

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

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

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

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

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

Москва. Наука. 1985

–  –  –

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

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

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

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

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

Литература

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

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

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

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

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

–  –  –

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

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

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

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

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

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

–  –  –

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

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

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

Q, представляющие наибольший интерес:

–  –  –

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

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

–  –  –

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

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

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

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

Литература

1. Морозов Р. (2003): ``Дипломная работа: Модель управления портфелем с учетом ликвидности финансового рынка'', Московский Государственный Университет им.М.В.Ломоносова, факультет ВМК, кафедра Системный Анализ

2. Науменко В.В. (2006): Магистерская диссертация: Оценка показателей потенциальных потерь портфеля с учетом ликвидности рынка, ГУ ВШЭ

3. Almgren R., Chriss N.A. (1999): Optimal Execution of Portfolio Transactions, University of Chicago, Department of Mathematics

4. Bangia A., Diebold F. X., Schuermann T., Stroughair J.D. (1998): Modeling liquidity risk with implications for traditional market risk measurement and managment, Warton Financial Institutions Center

5. Bertsimas D., Lo A.W. (1998): Optimal control of execution costs, Journal of Financial Markets 1-50

6. Kyle A. (1985): Continuous Auctions and Insider Trading, Econometrica, 53, pp. 1315Large J. (2007): Measuring the resiliency of an electronic limit order book, Journal of financial markets 1-25 Тезисы лучших дипломных работ ВМК МГУ 2009 года

–  –  –

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

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

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

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

–  –  –

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

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

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

–  –  –

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

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

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

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

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

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

–  –  –

1. J.Mai, A.Sridharan, C.-N.Chuach, T.Ye, H.Zang. Is Sampled Data Sufficient for Anomaly Detection? – Proceeding of ACM Internet Measurement Conference, 2006

2. G.J.Simmons. The prisoners problem and the subliminal channel.- Advances in Cryptology: Proceedings of Crypto, Plenum Press, 1984

–  –  –

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

Пусть X1,…,Xn,…- последовательность независимых одинаково распределенных случайных величин, удовлетворяющих соотношениям

–  –  –

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

В данной работе обобщен результат Х. Правитца на случай 0 1.

В частности, получена следующая таблица верхних оценок:

–  –  –

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

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

1. В. В. Петров. Суммы независимых случайных величин. Москва, Наука, 1972 .

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

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

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

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

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

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

Dissertation, Wuppertal, 1983 .

–  –  –

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

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

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

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

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

Литература

1. P. Barrieu, N. Bellamy Impact of Market Crises on Real Options – John Wiley and Sons, 2005

2. E. Mordecki Optimal Stopping for a Diffusion with Jumps – Finance and Stochastics,

3. S. Kou, H. Wang Option Pricing Under a Double Exponential Jump Diffusion Model

– Management Science, 2004

4. L. Trigeorgis Real Options – MIT Press, 1996 Тезисы лучших дипломных работ ВМК МГУ 2009 года

–  –  –

Дипломная работа посвящена изучению асимптотических свойств статистики для проверки гипотезы об отсутствии зависимости коинтеграционных соотношений от времени в модели Меняющейся во Времени Коинтеграции (Time Varying Cointegration) .

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

Пусть p-мерный авторегрессионный ряд, стационарный в разностях, задан с помощью уравнения Меняющейся во Времени Коинтеграции (МВК) k1 i X t i + t, t = 1, 2, … T, X t = t X t 1 i=1

–  –  –

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

–  –  –

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

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

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

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

Econometric Theory, 16: 740-778 .

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

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

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

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

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

BdB' .

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

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

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

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

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

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

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

–  –  –

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

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

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

Литература

1. V. Barnett, T. Lewis Outliers in Statistical Data, John Wiley (1994)

2. A. Loureiro, L. Torgo, C. Soares Outlier Detection Using Clustering Methods (2004)

3. Z. He, X. Xu, S. Deng Discovering Cluster Based Local Outliers (2003)

4. E. Knorr, R. Ng, V. Tucakov Distance-Based Outliers (2000)

5. V. J. Hodge, J. Austin A survey of outlier detection methodologies (2004)

6. A. Leroy, P. Rousseeuw Robust Regression and Outlier Detection (1987)

7. M. Bassewille, I. V. Nikiforov Detection of Abrupt Changes: Theory and Application (1993) Д. Уилер, Д. Чамберс Статистическое управление процессами. Оптимизация бизнеса с 8 .

использованием контрольных карт Шухарта, Москва (2009)

–  –  –

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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

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

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

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

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

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

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

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

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

–  –  –

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

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

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

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

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

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

Литература

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

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

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

176-201 .

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

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

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

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

–  –  –

В результате исследования было выделено две основные частоты: 10 и 20 Гц, на которых была произведена локализация источников в контрлатеральных и ипсилатеральных областях височных долей коры головного мозга, соответственно (рис. 3,4) .

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

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

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

Литература

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

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

3. Махортых С. А., Семечкин Р. А. Спектральные методы анализа магнитных энцефалограмм. Динамика неоднородных систем // Труды Института системного анализа РАН, 2008, Т. 33(вып. 12): 236-250

4. Устинин М. Н., Махортых С. А., Молчанов А. М. и др. Задачи анализа данных магнитной энцефалографии Компьютеры и суперкомпьютеры в биологии.М.: Институт компьютерных технологий,2002,С. 327-349

5. Whitham E. M., Pope K. J., Fitzgibbon S. P. Scalp electrical recording during paralysis:

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

–  –  –

Графические модели (graphical models [2, ch. 8]) зарекомендовали себя как надежный и эффективный инструмент статистического анализа структурированных данных. Являя собой выразительный язык для описания и конструирования сложных вероятностных моделей, они обеспечивают универсальный подход к решению основных задач машинного обучения. В данной работе означенная идеология применяется для автоматического определения эмоциональной динамики живой системы по внешним, наблюдаемым проявлениям ее активности (например, по видеозаписи или динамике биометрических показателей) На основании актуальных представлений о структуре поведенческого акта [1] и эмоционального состояния была построена композитно-иерархическая скрытая марковская модель - байесовская сеть, дополненная аналитическими ограничениями, для которой были разработаны эффективные алгоритмы обучения (на основе EM-алгоритма) и байесовского вывода (являющийся обобщением известного алгоритма Витерби для скрытых марковских моделей [3]) .

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

Литература

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

АН СССР, 1971 .

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

4. S. Fine, Y. Singer and N. Tishby. The Hierarchical Hidden Markov Model: Analysis and Applications – Machine Learning, vol. 32, p. 41–62, 1998

–  –  –

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

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

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

1 .

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

2 .

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

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

3 .

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

4 .

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

5 .

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

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

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

7 .

Наука, 1986 .

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

8 .

–  –  –

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

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

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

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

Следует особо отметить, что в работе используются именно плоские скелеты:

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

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

Задача включает в себя следующие подзадачи:

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

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

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

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

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

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

Литература

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

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

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

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

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

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

Кафедра ММП

–  –  –

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

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

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

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

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

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

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

1 .

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

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

Drost, N. Henze, O. Herden, M. Minor et al. – Humbold-Universitat Berlin, 2004. – Pp. 147Furnkranz J., Peter F. ROC n‘ rule learning – towards a better understanding of converting 3 .

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

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

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

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

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

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

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

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

2008 .

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

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

–  –  –

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

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

Сложность мультиплексорной ФАЛ изучалась в ряде работ. Известно (см. [1]), что сложность реализации ФАЛ, n 1,2,, как схемами из функциональных элементов n

–  –  –

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

–  –  –

называется длиной билинейного алгоритма. Билинейной сложностью умножения в алгебре A или рангом A называется длина кратчайшего билинейного алгоритма для A и обозначается rgA .

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

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

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

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

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

Теорема 1. Пусть F[G] – произвольная коммутативная групповая алгебра размерности n над полем характеристики нуль .

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

–  –  –

Задача эффективной факторизации больших чисел является одной из самых актуальных задач современной криптографии. Именно к ней сводятся большинство используемых на практике методов криптоанализа такой широко распространнной системы, как RSA [1]. Наиболее трудомким этапом решения задачи факторизации является решение СЛАУ Ax=0 над полем GF(2). Матрица A этой СЛАУ разреженна, неструктурированна и е размеры могут достигать. Для решения подобных СЛАУ разработан класс специализированных методов [2], наиболее широко используемым из которых является блочный метод Ланцоша. Метод Ланцоша является итерационным и скорость его сходимости может быть повышена предобуславливанием. Однако, построение эффективных предобуславливателей затруднено особенностями матрицы A. В данной работе предлагается метод построения предобуславливателей, использующий преобразование матриц в гиперграфы и построение разбиений гипергафов, минимизирующих определнную метрику .

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

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

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

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

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

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

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

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

Построение по матрице СЛАУ гиперграфа Hc, в соответствие вершинам ставятся столбцы

1. Разбиение гиперграфа Hc на k частей с минимизацией метрики cost. k выбирается таким образом, что если N — порядок матрицы СЛАУ, то задача обращения матрицы порядка N/k выполнима за разумное время

2. Построение по матрице СЛАУ гиперграфа Hr, в соответствие вершинам ставятся строки

3. Разбиение гиперграфа Hr на k частей с минимизацией метрики 1

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

–  –  –

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

Существует несколько инструментов, позволяющих строить разбиения гиперграфов: PaToH, hMETIS, Mondriaan, MLPart, Parkway, Zoltan. Однако, эмпирические тесты показывают, что для разбиения очень большой матрицы на большое количество частей, сам генератор разбиений должен работать распределнно. Из вышеперечисленных инструментов параллельную работу поддерживают лишь Zoltan и Parkway. Из результатов тестов, представленных в [3] видно, что для решения рассматриваемых в данной работе задач оптимальным является использование Zoltan .

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

Были обработаны матрицы различных размеров от 105 до 106, в частности, матрица размером 227000 227000 с ненулевых элементов, полученная в реальной задаче факторизации. Размеры получаемых блоков составляли от до. Количество одновременно запускаемых процессов составляло от 128 до 1024. Время работы параллельного этапа составляло менее 15 минут для всех случаев. Были выведены теоретические оценки вероятности обратимости надиагональных блоков, подтвердившиеся эмпирически. Таким образом было установлено, что вышеописанный метод предобуславливания на основе разбиений гиперграфов пригоден для использования в практических целях повышения эффективности блочного алгоритма Ланцоша при решении задачи факторизации больших чисел .

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

Литература [1] Н. О. Василенко. Теоретико-числовые алгоритмы в криптографии. М.:МЦНМО, 2003 .

[2] Bradford Hovinen. Blocked lanczos-style algorithms over small finite fields, 2004 .

[3] K.D. Devine, E.G. Boman, R.T. Heaphy, R.H. Bisseling, and U.V. Catalyurek. Parallel hypergraph partitioning for scientific computing. Parallel and Distributed Processing Symposium, International, 0:102, 2006 .

[4] P. Montgomery. A block lanczos algorithm for finding dependencies over gf(2). Lecture Notes in Computer Science, vol. 921, Springer-Verlag, pages 106–120, 1995 .

Кафедра МК

–  –  –

Понятие свободного от сумм множества было введено Шуром (Shur) в 1914 году .

Возникали различные задачи, связанные с этим понятием: задача оценки количества свободных от сумм множеств, которая была введена Камероном в 1988 году, оценивалось количество нерасширяемых свободных от сумм множеств (то есть максимальных по включению)[1], исследовался размер нерасширяемого свободного от сумм множества [2,3] .

Также была поставлена задача центрируемости свободных от сумм множеств [4] .

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

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

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

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

Литература

1. А.А.Сапоженко. Асимптотика числа множеств, свободных от сумм в группах простого порядка. Доклады Академии Наук, 2009, том 424, № 4, С. 1–2

2. P.H. Diananda and H.P. Yap. Maximal sum-free sets of elemets of finite groups, Proc. Japan Acad. 45

3. H.P. Yap. Maximal sum-free sets in finite abelian groups. IV., Nanta Math .

5(1972),no. 3, 70-75

4. J.-M. Deshouillers, V.F. Lev. Refined bound for sum-free sets in groups of prime order. Bulletin of the London Mathematical Society, to appear .

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

До 2008 года хэш-функция ГОСТ Р 34.11-94 являлась одной из наиболее стойких в мире: не было известно ни одной атаки, сложность которой была бы меньше, чем 2128 для нахождения коллизий и 2 256 для нахождения прообраза. Однако в 2008 году группа европейских криптологов [1] предложила атаку, которая понижала эти цифры до 2105 и 2192 соответственно. Слабым местом хэш-функции ГОСТ Р 34.11-94 оказался параллелизм на этапе вычисления функции сжатия: использование четырех параллельно работающих шифраторов. Атака основывается на нахождении неподвижных точек для одного такого шифратора, однако никаким способом не используется строение самого блочного шифра .

Проведем некоторые упрощения в шаговой функции блочного шифра ГОСТ 28147уберем циклический сдвиг и заменим сложение по модулю 232 обычным побитовым сложением. В таком случае каждый шифратор можно разбить на 8 подшифраторов, работающих по аналогичной схеме. Для каждого из них будет определен свой S-box, свой открытый текст (8 бит) и свой ключ (32 бита), которые будут получаться из открытого текста (64 бита) и ключа (256 бит) исходного шифратора.

Рассмотрим данное разбиение ключа и открытого текста:

1) Ключи .

a. Исходный ключ: K (k77 ||... || k7i ||... || k70 ||... || k07 ||... || k0i ||... || k00 )

–  –  –

b. Открытый текст для i го подшифатора: Pi ( Li || Ri ) .

Рассмотрим проведение атаки на хэш-функцию ГОСТ Р 34.11-94 при данных упрощениях структуры блочного шифра Применяя указанные упрощения к двум шифраторам при условии симметричности h0 и h1, мы можем разбить их работу на 8 эквивалентных систем вида:

–  –  –

ключей .

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

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

Таким образом, сложность нахождения коллизии для хэш-функции в такой схеме составляет 272 вызовов функции сжатия, или, применяя обобщенный парадокс о днях рождения [2] - 274 .

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

–  –  –

Задача разделения вычислительных ресурсов является одной из основных задач, которую решают инженеры и программисты уже на протяжении полувека. Именно эта задача привела к появлению первой компьютерной сети APRANET в 1958 году. С тех пор сети начали быстро развиваться, расширяться, увеличивалась пропускная способность, уменьшалось время отклика, и, конечно же, менялись технологии разработки распределенных приложений. Одной из таких технологий является RPC (Remote Procedure Call) – удаленный вызов процедур .

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

Автор языка программирования Python Guido van Rossum однажды сказал: «Основной задачей современного программирования является создание удобных и мощных инструментов для разработчика». Поэтому целью данной работы явилось проектирование и создание современного, функционального и удобного механизма удаленного вызова процедур .

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

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

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

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

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

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

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

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

Литература

1. Andrew D. Birrell, Bruce Jay Nelson. Implementing remote procedure calls // ACM Transactions on Computer Systems, Volume 2, Issue 1. 1984. P. 39-59 Современный мир сложно представить без цифрового видео. Однако видео обладает такими размерами, что не представляется возможным хранить его в исходном виде, поэтому сжатие является одной из главных задач в области работы с цифровым видео [8]. Разные настройки видеокодеков ведут к сильно различающимся результатам, поэтому актуальна задача анализа значений используемых параметров сжатия видео. Стоит отметить, что у видеокодеков, как правило, довольно много параметров, а процесс сжатия является весьма трудоемким. Поэтому перепробовать все возможные настройки и выбрать лучшие не представляется возможным. При анализе качества определенного набора настроек (значений параметров) нас в первую очередь интересует время кодирования и качество закодированного видео (характеризующее похожесть оригинала и сжатого видео [1,8]) .

Традиционно рассматривалась задача выбора оптимальных наборов значений параметров [6,9] и анализа отдельных параметров с использованием внутреннего строения частей видеокодека, настраиваемых этими параметрами (например, работы международных стандартов ISO/IEC MPEG-4, JVT). В этой дипломной работе показано, что такая постановка задачи не позволяет делать выводы касательно эффективности значений параметров и существующие методы решения этих традиционных задач не применимы для задачи анализа параметров видеокодека с точки зрения эффективности их значений. В дипломной работе предложены два метода анализа параметров видеокодека и оценки эффективности их значений: метод анализа параметров видеокодеков с точки зрения эффективности их значений в областях с фиксированным соотношением между временем кодирования и качеством закодированного видео и метод анализа параметров видеокодеков с точки зрения средней эффективности их значений по отношению к другим значениям этих параметров .

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

Кафедра АСВК Разработанные методы были апробированы на видеокодеке x264 [4] стандарта MPEG-4 AVC/H.264 [5] и получены практические рекомендации по использованию их значений [2] .

Литература

1. Ватолин Д., Паршин А. Сравнения кодеков стандарта MPEG-4 AVC/H.264 с использованием объективных метрик // Труды конференции Graphicon-2006,

2006. C.447-454 .

2. Анализ параметров видеокодека x264 стандарта MPEG-4 AVC/H.264 [pdf] (http://www.compression.ru/video/codec_comparison/x264_options_analysis_08.ht ml) .

3. Лотов А.В., Поспелова И.И. Конспект лекций по теории и методам многокритериальной оптимизации. М.: ВМиК МГУ им. М.В. Ломоносова, 2006. 132 с .

4. Видеокодек x264 стандарта MPEG-4 AVC/H.264 (http://www.videolan.org/developers/x264.html) .

5. Coding of audio-visual objects – Part 10: Advanced Video Coding - ISO/IEC 14496http://www.iso.org/iso)

6. Kwon D., Agathoklis P., Driessen P. Performance and Computational Complexity Optimization in a Configurable Video Coding System // Wireless Communications and Networking. 2003. 3. Р.2086-2089 .

7. Рагулина К.О., Попов В. Д., Паршин А.Е. Алгоритмы анализа значений параметров кодирования видеокодеков // Новые информационные технологии в автоматизированных системах: материалы двенадцатого научнопрактического семинара. № 12. М.: Моск. гос. ин-т электроники и математики .

2009. С.39-50 .

8. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных .

Устройство архиваторов, сжатие изображений и видео. М.: ДИАЛОГ-МИФИ, 2003. 384 с .

9. Vanam R., Riskin E., Hemami S., Ladner R. Distortion-Complexity Optimization of the H.264/MPEG-4 AVC Encoder using the GBFOS Algorithm // Data Compression Conference. 2007. Р.303-312 .

–  –  –

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

Широкое применение матирование нашло в кино: изначально неподвижные или подвижные (покадровые) маски («маты») объекта переднего плана рисовались на стеклянных панелях [1] и предотвращали экспонирование фона на пленку, куда затем отдельным проходом экспонировался новый фон на основе инвертированной маски .

В конце XX – начале XXI появились технологии цифровой обработки видео .

а) исходный кадр б) результат Применительно к матированию Рис. 1. Пример из х/ф «Преодоление» (Invincible, цифровое видео дает возможность более детальной 2006) .

проработки отснятой сцены и практически неограниченного увеличения числа слоев;

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

Пример матирования актера для добавления элементов фона приведен на рис. 1 .

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

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

Используется формула композиции (в каждом пикселе):

F (1 )B, где C – цвет изображения, F, B – цвета объекта и фона соответственно, – C коэффициент смешивания ( [0, 1]). Изображение коэффициентов образует маску объекта, называемую альфа-каналом .

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

Предложенный функционал соответствует энергии случайного марковского поля. Для его минимизации применяется дискретный метод КПБО (квадратичной псевдо-булевой оптимизации) с альфа-расширением1. Возможные векторы движения (т.е. значения Альфа-расширение – процедура, сводящая решение N-арного случайного марковского поля к серии решений бинарных полей (однако находит, вообще говоря, локальный минимум) Кафедра АСВК оптического потока) в пикселе дискретизируются путем регулярного разбиения квадрата с центром в данном пикселе. Обработка ведется иерархически (по размеру изображения) для сокращения времени работы. При этом пространство поиска на каждом уровне иерархии ограничивается окном 3x3 в каждом пикселе .

Алгоритм реализован в виде консольного приложения на языке C++.

Было проведено сравнение с существующими аналогами: программой «Клякса» [3] (осуществляет только бинарную сегментацию) и программой RobustMatting [4], содержащей 2 режима обработки:

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

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

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

а) исходный б) «Клякса»

известного результата (масок всех кадров или кадр некоторых кадров – контрольной выборки) .

Для 20 тестовых видеопоследовательностей были созданы ключевые кадры. По итогам тестирования выборка была разбита на 3 части: в) г) предлагаемый простые видео (искусственные), с RobustMatting алг .

которыми все алгоритмы справлялись хорошо (для контроля) Рис. 2. Сравнение алгоритма с средние по сложности, на которых хотя бы один их сравниваемых алгоритмов аналогами работает приемлемо сложные, с которыми ни один из сравниваемых алгоритмов не справляется (т.е .

выдает неадекватные маски объектов, и численное сравнение не имеет смысла) В численном сравнении были использованы средние по сложности видеопоследовательности. Для них были созданы точные маски всех кадров для численного сравнения. Типичный результат работы алгоритмов показан на рис. 2 (показан 50-й кадр видео, отслеживание маски осуществлялось с 1-го кадра) .

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

Литература

1. Hanson B. Matte Painting: Art in Film Special Effects. – [PPT] (http://wwwgraphics.stanford.edu/courses/cs99d-00/projects/BrookeHanson-specialfx.ppt)

2. Levin A., Lischinski D., Weiss Y. A Closed Form Solution to Natural Image Matting. – Proc. of IEEE CVPR, 2006, p. 61–68

3. Claxa. – [HTML] (http://patchmaker.net/Claxa/)

4. Wang J., Cohen M. Optimized Color Sampling for Robust Matting. – Proc. of IEEE CVPR, 2007, p. 1–8

–  –  –

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

Для упрощения построения анализаторов сетевого трафика в лаборатории Вычислительных комплексов кафедры АСВК разрабатывается специализированная программная среда AURA (Automata for Recognition and Analysis – автоматы для распознавания и анализа), в состав которой, в частности, входит проблемноориентированный автоматный язык программирования и среда поддержки выполнения программ на этом языке .

Основной задачей данной работы было создание параллельного аналога существующей среды поддержки выполнения программ (RTS – RunTime System) для языка программирования AURA, при обеспечении функциональной совместимости и обратной совместимости по исходному коду. Разработанная RTS позволяет организовать быструю обработку асинхронных потоков событий за счет использования возможностей современных многоядерных процессоров. RTS была реализована для операционных системам семейства Windows 2000/XP и Linux .

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

Результаты работы докладывались на конференциях SYRCoSE 2008, РусКрипто 2009 .

Литература Кафедра АСВК

1. Кеммерер Р., Виджна Д. Обнаружение вторжений: краткая история и обзор [HTML] (http://www.osp.ru/text/302/181714.html)

2. Пировских А. Snort: инструмент выявления сетевых атак [HTML] (http://www.thg.ru/network/20051020/index.html)

3. Deri L. Improving Passive Packet Capture: Beyond Device Polling [PDF] (http://luca.ntop.org/Ring.pdf)

4. Rizzo L. Device Polling Support for FreeBSD [HTML] (http://info.iet.unipi.it/~luigi/polling/)

5. Deri L. nCap: Wire-speed Packet Capture and Transmission [PDF] (http://luca.ntop.org/nCap.pdf)

6. Mikolasek V. Intrusion Detection Systems - State of the Art Report [PDF] (http://www.vmars.tuwien.ac.at/php/pserver/extern/download.php?fileid=1524)

7. Wang H.J., Guo C., Simon D.R., Zugenmaier A. Shield: Vulnerability-Driven Network Filters for Preventing Known Vulnerability Exploits. [PDF] (http://research.microsoft.com/~helenw/papers/shieldSigcomm04.pdf)

8. Schear N., Albrecht D.R., Borisov N. High-Speed Matching of Vulnerability Signatures [PDF] (http://www.cs.uiuc.edu/homes/nschear2/raid-2008.pdf)

9. Vossen J.P. Snort Intrusion Detection and Prevention Guide [HTML] (http://searchsecurity.techtarget.com/generic/0,295582,sid14_gci1083823,00.html)

10. Jacob N., Brodley C. Offloading IDS computation to the GPU [PDF] (http://www.acsac.org/2006/papers/74.pdf)

11. Vasiliadis G., Antonatos S., Polychronakis M., Markatos E.P., Ioannidis S. Gnort:

High Performance Network Intrusion Detection Using Graphics Processors [PDF] (http://www.ics.forth.gr/dcs/Activities/papers/gnort.raid08.pdf)

12. Kazachkin D., Gamayunov D. Network traffic analysis optimization at signaturebased intrusion detection systems. // In Proceedings of SYRCoSE 2008, Vol 1, p. 27REDSecure: обнаружение и предотвращение атак [HTML] (http://redsecure.ru/)

14. Гамаюнов Д. Ю. Обнаружение компьютерных атак на основе анализа поведения сетевых объектов. // Москва, 2007. Кандидатская диссертация .

15. Eckmann S.T., Giovanni V. G., Kemmerer R.A. STATL: An Attack Language for State-based Intrusion Detection [PDF] (www.cs.ucsb.edu/~vigna/publications/2000_eckmann_vigna_kemmerer_statl.pdf)

16. Lattner C., Adve V. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation [PDF] (http://llvm.org/pubs/2003-09-30LifelongOptimizationTR.pdf)

17. Гамаюнов Д.Ю., Казачкин Д.С. AURA: программная платформа высокоскоростного анализа сетевого трафика для задач информационной безопасности. // Материалы конференции РусКрипто'09, 2009 г. [PDF] (http://ruscrypto.ru/netcat_files/File/ruscrypto.2009.008.zip)

18. Blaise B. POSIX Threads Programming [HTML] (https://computing.llnl.gov/tutorials/pthreads/)

19. Giovanni V. G., Kemmerer R.A. NetSTAT: A Network-based Intrusion Detection Approach [PDF] (http://www.acsac.org/1998/presentations/wed-a-1030-vigna.pdf)

20. Eckmann S.T. Translating Snort rules to STATL scenarios [PDF] (http://www.raidsymposium.org/raid2001/papers/eckmann_raid2001.pdf) Дипломная работа посвящена одному из способов анализа результатов имитационного моделирования .

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

Целью дипломной работы является разработка и реализация программного инструмента в рамках стенда ПНМ, позволяющего сравнивать степень схожести трасс выполнения имитационных моделей стенда, а также их участков, с использованием алгоритмов нечткого поиска [3,4,5,6] .

В рамках данной работы рассматриваются возникающие задачи анализа трасс выполнения имитационных моделей [7] и выделяется ряд задач, которые не решаются существующими средствами стенда ПНМ. В работе подробно рассматриваются следующие прикладные задачи: задача анализа трасс выполнения циклограмм обменов по каналу данных МКИО [8] и задача анализа трасс выполнения циклограмм функциональных задач .

Данные задачи предлагается решать при помощи разработанного программного средства .

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

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

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

Литература

1. Грибов Д.И., Смелянский Р.Л. Комплексное моделирование бортового оборудования летательного аппарата // Методы и средства обработки информации. Труды второй Всероссийской научной конференции. - М.: Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, 2005. - С.59-74

2. Балашов В.В., Бахмуров А.Г., Волканов Д.Ю., Смелянский Р.Л., Чистолинов М.В., Ющенко Н.В. Применение стенда полунатурного моделирования для разработки вычислительных систем морского навигационного комплекса // Программные системы и инструменты. Тематический сборник № 9, М.: Изд-во ф-та ВМиК МГУ, 2008. стр. 153Gonzalo Navarro, A Guided Tour to Approximate String Matching // University of Chile, 2001

4. Graham A.S. String Search. // School of Electronic Engineering Science University College of North Wales,1992 .

5. Nakatsu, N., Y. Kambayashi, S.Yajima A longest common subsequence algorithm suitable for similar text strings. // Acta Informatika 18, 171-179, 1982 .

6. Landau, G.M., U. Vishkin Fast string matching with k differences. // Jour. Comp. and Susyem Sci. 37, 63-78,1988 .

7. Волканов Д.Ю., Черей М.В. Применение алгоритмов нечткого поиска для анализа результатов имитационного моделирования ВСРВ // Научная сессия МИФИ-2008, том 13, Москва, 2008 .

8. Государственный стандарт РФ «Интерфейс магистральный последовательный системы электронный модулей» ГОСТ Р 52070-2003 .

–  –  –

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

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

Ограничениями задачи являются:

1) диапазоны изменения требований;

2) ограничение совместимости искомого решения (откорректированных требований) .

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

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

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

Литература

1. Балашов В.В. Алгоритмы формирования рекомендаций при планировании информационного обмена по каналу с централизованным управлением. // Известия РАН .

Теория и системы управления, 2007, N.6, с. 76-84 .

2. Костенко В.А., Гурьянов Е.С. Алгоритм построения расписаний обменов по шине с централизованным управлением и исследование его эффективности. // М., Программирование, 2005, No. 6, стр. 340-346 .

3. Балашов В.В. Шестов П.Е. Формирование рекомендаций по обеспечению совместимости требований к обмену по общей шине во встроенных системах реального времени // Труды Четвертой международной конференции "Параллельные вычисления и задачи управления" (РАСО'2008). М.: ИПУ им. В.А.Трапезникова РАН. 2008. С. 1385-1404

4. Balashov V.V., Kostenko V.A., Smeliansky R.L. A Tool System for Automatic Scheduling of Data Exchange in Real-Time Distributed Avionics Systems // Proceedings of the Second European Conference For Aero-Space Science, 2007 .

5. Мину М. Математическое программирование. Теория и алгоритмы // М.: Наука. Гл .

ред. физ.-мат. лит., 1990 .

6. М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982 .

7. Blazewicz J., Ecker K., Pesch E., Schmidt G., Weglarz J. Handbook on Scheduling: From Theory to Applications. Springer, 2007 .

8. Liu C.L., Layland J.W. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment // Journal of the ACM.1973. 20. № 1. P. 46 – 61

9. A. K. Mok, Fundamental design problems of distributed systems for the hard-real-time environment, Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, 1983 .

Дипломная работа посвящена поддержке вычислительной модели языка Рефал в рамках проектов на языке Си++. В ходе работы реализованы в виде библиотеки классов Си++ рефал-вычислитель приемлемой эффективности и транслятор кода из синтаксиса языка Рефал-5 в Си++ .

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

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

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

Существует множество подходов к интеграции языков программирования. Библиотека InteLib реализует метод непосредственной интеграции разнородных языковых механизмов [1]. Смысл метода заключается в написании на основном языке программирования библиотеки, которая будет реализовывать конструкции, моделирующие конструкции языков, интегрируемых в основной язык. Под моделирующими конструкциями здесь понимаются те, которые семантически эквивалентны и в некотором смысле «синтаксически близки» к исходным. В случае InteLib основным языком выступает Си++ .

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

Новая реализация включает в себя:

Кафедра АЯ

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

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

• реализацию безымянных предложений (with-блоков) языка Рефал, ранее полностью отсутствующую в InteLib;

• поддержку всех функций стандартной библиотеки языка Рефал-5 .

Благодаря последним двум пунктам было достигнуто полное соответствие поддерживаемого диалекта описанию языка Рефал-5 .

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

Кроме того, он обладает следующими свойствами:

• возможностью принимать на вход любое число файлов на Рефале;

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

Эти требования являются стандартными для трансляторов, являющихся частью InteLib (например, им удовлетворяют соответствующие трансляторы языков Лисп и Scheme). Таким образом, в отличие от уже существовавшего прототипа транслятора Рефала, вновь созданный транслятор аналогичен всем присутствующим в InteLib. Интересным его свойством является возможность в случае наличия специального флага командной строки компилировать несколько файлов на Рефале-5 непосредственно в исполняемый файл .

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

Результаты работы были включены в библиотеку InteLib и доступны для скачивания по адресу http://www.intelib.org .

–  –  –

Работа посвящена вопросам реализации программы, способной осуществлять взаимодействия по протоколу передачи гипертекста, как в качестве клиента, так и в качестве сервера. Фактически такая программа представляет собой агента взаимодействий по протоколу HTTP [1]. Ключевой особенностью созданной программы является возможность управления поведением агента на алгоритмически полном языке. Эта возможность реализована путем встраивания в программу интерактивного интерпретатора языка Лисп, при помощи средств библиотеки InteLib [2], реализующих вычислительную модель языка Лисп в рамках программ на C++ .

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

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

Кафедра АЯ

блокировки программируемого агента при блокировке отдельного потока и наличии других потоков, готовых к выполнению .

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

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

–  –  –

Разработанная автором система автоматизации контроля доступа клиентов мультисервисной сети представляет собой альтернативу традиционной авторизации PPP-соединений и менее распространенной Port-Security функциональности управляемых коммутаторов .

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

Ключевым понятием является «привязка» - жесткое установление соответствия между клиентским оборудованием и точкой подключения к среде передачи данных провайдера. Реализовано управление коммутаторами Dlink DES3526 и другими, брандмауэром маршрутизаторов на базе серверов под управлением FreeBSD .

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

Система предусматривает интеграцию с биллингом сети, автоматизирует техническую поддержку и обнаруживает некоторые виды несанкционированного изменения топологии сети. Она также содержит некоторые дополнительные функции по конфигурации оборудования и проверке его конфигураций, например – ограничение потоков данных многоадресной рассылки(multicast streams) в «узких местах» сети .

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

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

Литература

1. Фейт С. - TCP/IP. Архитектура, протоколы, реализация. – Москва:Лори, 2000, 424с .

2. Обзор технологии DLink IP-MAC-PortBinding – март 2006 http://www.dlink.ru/up/uploads_media/FAQ_IP_MAC_Port_Binding.pdf [pdf]

3. Программа сетевой академии Cisco CCNA 1 и 2. Вспомогательное руководство, 3-е изд., с испр.: Пер. с англ. – Москва:Издательский дом «Вильямс», 2005. – 1168 с .

4. Mauro D. R., Schmidt K. J. - Essential SNMP, Second Edition. – O‘Reilly Media, 2005, 460 с .

5. Perkins D., Mcginnis E. - Understanding SNMP MIBS. - Prentice Hall, 1996, 528 с .

6. James Turnbull - Pro Nagios 2.0 – Berkeley:Apress, 2006 – 423 с .

Кафедра АЯ

–  –  –

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

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

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

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

Эти параметры включают:

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

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

–  –  –

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

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

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

Программные средства реализованы на языке Java с использованием СУБД HSQLDB и внешнего модуля морфологического анализа «Диалинг. Русская морфология». Доступ к основным функциям словаря паронимов осуществляется с помощью прикладного и пользовательского интерфейсов .

Реализованные программные средства были проверены при загрузке и пополнении разных по структуре и объему текстовых файлов со словарными данными (объемом от 16 до 90 тыс. слов) и продемонстрировали устойчивую работу. В результате автоматического пополнения число пар буквенных паронимов, по сравнению с исходным файлом, увеличилось на 30% .

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

–  –  –

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

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

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

Результаты работы методов оценивались на основе решений экспертов по включению словосочетаний в разрабатываемый терминологический ресурс – Онтологию по естественным наукам и технологиям [1] .

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

Тезисы лучших дипломных работ ВМК МГУ 2009 года

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

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

Для оценки качества сортировки получаемых списков словосочетаний использовалась мера, служащая для оценки качества результатов информационного поиска, так называемая средняя точность (Mean Average Precision - MAP) [3]. Тестирование было проведено на выборке 3000 и 5000 словосочетаний. Было достигнуто существенное улучшение точности MAP по сравнению с точностью исходного списка (+27.2 %) и точностью наилучшей из отдельно взятых характеристик (+5.6%). Все методы сохранили более высокую среднюю точность MAP по сравнению с отдельными характеристиками при увеличении тестовой выборки .

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

Литература [1] Добров Б.В., Лукашевич Н.В., Синицын М.Н., Шапкин В.Н. Разработка лингвистической онтологии по естественным наукам для решения задач информационного поиска.

// Труды 7-ой Всероссийской научной конференции «Электронные библиотеки:

перспективные методы и технологии, электронные коллекции» - RCDL‘2005 .

[2] Weka 3: Data Mining Software in Java. http://www.cs.waikato.ac.nz/~ml/weka/ [3] Агеев М.С., Кураленок И.Е. Официальные метрики РОМИП‘2004. // Российский семинар по Оценке Методов Информационного Поиска (РОМИП 2004) — Пущино, 2004 .

–  –  –

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

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



Pages:   || 2 |
Похожие работы:

«Муниципальное дошкольное образовательное учреждение "Детский сад № 23" Конспект занятия (дети старшего дошкольного возраста 6-7 лет) Зимние Олимпийские Игры Подготовила Учитель-логопед Кукушкина Е.В. г. Ростов Цель:...»

«1 ПУБЛІКАЦІЇ ШТАТНИХ НАУКОВО-ПЕДАГОГІЧНИХ ТА НАУКОВИХ ПРАЦІВНИКІВ ДВНЗ "ПРИАЗОВСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ" Азархов Азархов А. Ю. Перспективы развития направления "Биомедицинской инженерии" в Восточном рег...»

«6год Паспорт программы. Название программы Рабочая программа учителя – логопеда средней группы компенсирующей направленности Сроки реализации 2016 – 2017 учебный год Наименование учреждения ГБДОУ детский сад № 7 Автор программы Якушко Елена Борисовна Должность – учитель – логопед Об...»

«Муниципальное автономное общеобразовательное учреждение города Калининграда средняя общеобразовательная школа № 38 РАССМОТРЕНО "СОГЛАСОВАНО" "УТВЕРЖДЕНО" на заседании МО на заседании ПС приказом директора протокол №...»

«Интернет-проект №4 от 25 мая 2010 года "Учительской газеты" Коммуникативные игры. Простые и сложные. Денис Рочев, учитель немецкого языка Гатчинской гимназии "Апекс", Победитель конкурса "Учитель года Ленинградской области 2006", Победитель...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ШАДРИНСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ ТРЕБОВАНИЯ К ИСХОДНЫМ МАТЕРИАЛАМ ДЛЯ РАЗРАБОТКИ ЭЛЕКТРОННЫХ ИЗДАНИЙ УЧЕБНОГО НАЗНАЧЕНИЯ Шадринск УДК 378(075) ББК 74.58я73 T 66 Рекомендовано редакционно-издательском советом Шадринского государственного педагогического института Составители: В...»

«Семинар-практикум для педагогов ДОУ "Путешествие в страну Красивой речи" 1 слайд: Здравствуйте, уважаемые коллеги! 2 слайд: Представьте себе величественную картину мира – мира наук и знаний, который все время занимает умы и вообра...»

«МУЗИЧНА НАУКА НА ПОЧАТКУ ТРЕТЬОГО ТИСЯЧОЛІТТЯ. 2016, Випуск № 2. musikology.com.ua Иваницкая Анна "ЗЕМНОЕ" О МОЦАРТЕ "Достичь небес – это нечто прекрасное и возвышенное, но и на милой земле несравненно прекрасна жизнь! Поэтому оставьте нас быть людьми" Вольфганг Амадей Моцарт В статье рассматриваются некоторые страницы жизни и ха...»

«МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ ДОШКОЛЬНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ПОЧИНКОВСКИЙ ДЕТСКИЙ САД № 3 УТВЕРЖДЕНО. Заведующий МБ ДОУ Починковский детский сад № 3 _ И.Ю. Сбитнева Приказ от "01"августа 2017 № 81 Дополнительная общераз...»

«Памяти друзей-коллег Казимежа Годлевского, Иохима Вернера, Рышарда Волонгевича Вы ждали перемен под атрием квадратным, Вы наслаждались духом варварских начал, И каждый становился немножко скифократом, И от дерьма с конюшен тихонечко торчал. Е...»

«Муниципальное бюджетное учреждение дополнительного образования города Новосибирска "Дом детского творчества "Центральный" Принята "УТВЕРЖДАЮ" на заседании педагогического совета Директор ДДТ "Центральный" от ""_20_г. _Л.И. Мандыч Протокол № _ ""_20_ г. Дополнительная общеобра...»

«Пояснительная записка Автор разработки: Полунина Ирина Геннадьевна, учитель начальных классов, МБОУ "Мгинская средняя общеобразовательная школа". Внеклассное занятие. 4 класс. Тема: "Музей под названием русские чудеса".Цели: 1.Пробудить интерес к прошлому своего народа.2.Познакомить с национальной культурой.3. Приобщить д...»

«VILNIAUS PEDAGOGINIS UNIVERSITETAS FILOLOGIJOS FAKULTETAS RUS LITERATROS IR TARPKULTRINS KOMUNIKACIJOS KATEDRA Janina Guobyt Specialyb "Rus filologija" II kursas Animalistiniai motyvai Sidabro amiaus poezijoje Magistro darbas Darbo vadovas doc...»

«Хозяйки судьбы или Спутанные Богом карты Метлицкая Мария Хозяйки судьбы, или Спутанные Богом карты Благодарность моему мужу Жене Когану, Лене и Алику Сорока, Наташе Побединской, Анне Штерн, Алле Орловой, Маше Гуревич, Льву Щеголеву, Тане...»

«Муниципальное автономное образовательное учреждение дополнительного образования детей "Детско-юношеская спортивная школа "Центр физического развития" Комитета образования Администрации Великого Новгорода Рассмотрена на педагогическом совете УТВЕРЖДАЮ МАОУДОД "ДЮСШ "ЦФР" Директор (протокол № 1 от 06. 09. 2011 г.) ДЮСШ "ЦФР"...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ РОССИЙСКАЯ АКАДЕМИЯ ОБРАЗОВАНИЯ ФГБОУ ВО "МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ ИМЕНИ М. Е. ЕВСЕВЬЕВА"МОРДОВСКИЙ НАУЧНЫЙ ЦЕНТР РОССИЙСКОЙ АКАДЕМИИ ОБРАЗОВАНИЯ. ФАКУЛЬТЕТ ИНОСТРАННЫХ...»

«Газета Муниципального общеобразовательного учреждения 6+ "Средняя школа № 90" г. Ярославля №6 Март 2016 В номере: Медовые новости. С. 2-3. Виртуальный музей школы. С.7. Соцопрос. С. 6. Фестиваль. С. 4-5. Язык Интернета. С. 8-9. Блогсфера. С. 10-13. Общение в Сети. С 14. Как заработат...»

«РЕЗЮМЕ ПРЕПОДАВАТЕЛЯ 1. Фамилия, имя, отчество Бирюкова Елена Евгеньевна 2. Дата рождения 11.12.1966 3. Телефоны: рабочий: (4922)47-99-32 4. E-mail: bestiarys@gmail.com 5. Образование ВГПИ(Владимирский государственный педагогический инсттитут), специальность "Учитель изобразительного искусства и ч...»

«УТВЕРЖДАЮ РАБОЧАЯ ПРОГРАММА ПО КУРСУ "Клиросное пение" (внеурочная деятельность) 5-9 классы Учитель: _ уч.год _уч.год _ _ уч.год _уч.год _ 2016 год Содержание рабочей программы: 1 Пояснительная записка стр 3 2 Общая характеристика учебного предмета "Клиросное стр 4 пение" 3 Место предмета "Клиросное пение" в учебном плане стр 4...»

«Леонид Пантелеев Республика Шкид Посвящаем эту книгу товарищам по школе имени Достоевского. Авторы Первые дни На Старо-Петергофском проспекте в Ленинграде среди сотен других каменных домов затерялось облупившееся трех...»

«А.В.ФЕДОРОВ, А.А.ЛЕВИЦКАЯ, И.В.ЧЕЛЫШЕВА, Е.В. МУРЮКИНА, В.Л.КОЛЕСНИЧЕНКО, Г.В.МИХАЛЕВА, Р.В.СЕРДЮКОВ НАУЧНО-ОБРАЗОВАТЕЛЬНЫЙ ЦЕНТР "МЕДИАОБРАЗОВАНИЕ И МЕДИАКОМПЕТЕНТНОСТЬ" Москва УДК 316.77:001.8 ББК 74.580.215 Федоров А.В., Левицкая А.А., Челышева И.В., Мурюкина Е....»

«Публичный отчет за 2015-2016 учебный год. муниципального бюджетного общеобразовательного учреждения Лопатинской средней общеобразовательной школы Татарского района Прошедший учебный год, второй год работы ш...»

«УДК 373.167.1:91 ББК 26.8я72 Д86 Душина, И. В. Д86 География : Материки, океаны, народы и страны. 7 кл. : учебник / И. В. Душина, В. А . Коринская, В. А. Щенев ; под ред. В. П. Дронова. — 5-е изд., пересмотр. — М. : Дрофа, 2018. — 398, [2] с. ISBN 978-5-358-19435-9 Учебник соответствует ФГОС основн...»

«МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ – СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА № 7 г. БАЛАКОВО САРАТОВСКОЙ ОБЛАСТИ Рассмотрено на заседании Согласовано Утверждаю ШМО учителей Зам. директора по УВР Директор протокол № _ "" 20 г. "" _ 20 г. "" _ 20 г. РАБОЧАЯ ПРОГРАММА русскому язы...»

«СОДЕРЖАНИЕ СЛОВО ГЛАВНОГО РЕДАКТОРА Иванова С.В. О вечной памяти павшим и спасшим СОВЕТСКАЯ ШКОЛА В ГОДЫ ВЕЛИКОЙ ОТЕЧЕСТВЕННОЙ ВОЙНЫ Овчинников А.В. Роль государства и учительской общественности...»






 
2018 www.new.pdfm.ru - «Бесплатная электронная библиотека - собрание документов»

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