WWW.NEW.Z-PDF.RU
БИБЛИОТЕКА  БЕСПЛАТНЫХ  МАТЕРИАЛОВ - Онлайн ресурсы
 

Pages:   || 2 | 3 |

«Гаврилов Сергей Вадимович Метод определения неизвестного контура в задаче Дирихле...... 11 Кривов Максим Андреевич Разработка системы ...»

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

Оглавление

Кафедра математической физики

Гаврилов Сергей Вадимович

Метод определения неизвестного контура в задаче Дирихле...... 11

Кривов Максим Андреевич

Разработка системы моделирование полёта микросамолётов на параллельных архитектурах............................ 12

Медведева Виктория Юрьевна

Диффузионные методы выделения контуров на изображениях.... 14

Романенко Татьяна Евгеньевна

Исследование периодических решений параболического функционально-дифференциального уравнения диффузии с запаздыванием.................................. 16 Семашко Александр Сергеевич Вариационный метод поиска границы диска зрительного нерва на изображениях глазного дна......................... 17 Сисакян Анастасия Алексеевна Метод нахождения и параметризации области глаз на изображениях лиц....................................... 19 Ткаченко Максим Сергеевич Многомасштабный метод подавления шумов в аудиосигналах..... 20 Кафедра вычислительных технологий и моделирования Заячковский Антон Олегович Математическое моделирование экологических рисков загрязнения вод океанов и морей............................. 22 Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Иванов Юрий Александрович Модель эластичного кровеносного сосуда и ее приложение в задачах рентгенохирургии .



.............................. 24 Калмыков Владимир Владимирович Разработка параллельной версии модели гидродинамики Мирового океана...................................... 25 Михалев Александр Юрьевич Нерекурсивный мультипольный метод в двумерном и трехмерном пространствах................................... 28 Терехов Кирилл Михайлович Параллельная реализация модели общей циркуляции океана..... 30 Кафедра вычислительной математики Александров Петр Александрович Симплектические вычислительные методы молекулярной динамики. 31 Галанина Анна Михайловна Численное решение уравнений газовой динамики в лагранжевых переменных.................................... 32 Исаков Виктор Александрович Решение уравнений газовой динамики в эйлеровых переменных с использованием сплайн функций....................... 34 Кафедра автоматизации научных исследований Кульков Дмитрий Сергеевич Корпускулярное моделирование процесса взаимодействия лазерного импульса с плазмой.............................. 36 Семёнов Алексей Николаевич Математическое моделирования рас

–  –  –

Кафедра квантовой информатики Лашков Дмитрий Геннадьевич Элементы структур простых молекул в программном комплексе для квантового моделирования.......................... 44 Кафедра исследования операций Вартанов Сергей Александрович Исследование равновесий в модели эндогенного формирования коалиций....................................... 46 Курочкин Сергей Владиславович Метод декомпозиции в задаче выбора состава оборудования...... 48 Лесков Андрей Андреевич Задача оптимизации расписания работы складских помещений.... 50 Малинина Елена Александровна Численное исследование некоторых математических моделей производства лазерных мишеней......................... 51 Молчанов Александр Александрович Математическая модель рынка с вертикальной дифференциацией продуктов................................... 52 Потапова Ольга Сергеевна Оценка стоимости опциона при переменной процентной ставке.... 54 Тропников Александр Вячеславович Принятие решений в условиях субъективной неопределенности.... 56





Кафедра оптимального управления

Артемьева Людмила Анатольевна Экстраградиентный метод решения многокритериальной задачи равновесного программирования........................ 58 Жуковская Ирина Станиславовна Численные методы построения множеств достижимости для нелинейных управляемых систем.......................... 60 Кальченко Артем Олегович Об одном классе игровых задач управления............... 62 Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Харитонова Елена Игоревна Задача оптимального управления взаимодействия предприятия и государства в экологической и экономической сферах........... 63 Костычев Евгений Алексеевич Динамическая модель оптимального развития транспортной инфраструктуры................................... 64 Овсянникова Екатерина Владимировна Решение одномерного уравнения Шредингера методом функций Грина 66

Кафедра системного анализа

Андреев Николай Анатольевич Модели ценообразования для производных финансовых инструментов на процентные ставки............................ 68 Дорогуш Елена Геннадьевна Математическое моделирование потоков автотранспорта........ 70 Запольский Кирилл Максимович Моделирование роста сосудистой раковой опухоли методом гибридных клеточных автоматов.......................... 71 Казейкина Анна Васильевна Исследование асимптотического поведения решения задачи коши для уравнения Кортевега–де Фриза–Бюргерса................. 72 Куликов Олег Вячеславович Исследование модели нефтяного месторождения с учётом возрастающих предельных издержек.......................... 74 Майская Татьяна Сергеевна Разработка и анализ методов аппроксимации оболочки Эджворта– Парето для выпуклых задач многокритериальной оптимизации.... 75 Ширяев Владимир Дмитриевич Развитие эллипсоидального метода оценивания множеств достижимости линейных систем с неопределённостью................ 76 Юрьев Александр Юрьевич Анализ задачи о квазивидах Эйгена.................... 77 Кафедра математической статистики

–  –  –

Кафедра математических методов прогнозирования Гордеев Дмитрий Вячеславович Методы восстановления пространственного изображения и оценка их точности.................................... 86 Задонский Дмитрий Алексеевич Склейка скелетов смежных многоугольных фигур............ 87 Мягков Артём Александрович Автоматизация анализа изображений срезов мозга экспериментальных животных для наполнения модели болезни Паркинсона...... 89 Осокин Антон Александрович Разработка методов построения трехмерной модели мозга мыши и вписывания в нее экспериментальных данных.............. 91

Кафедра математической кибернетики

Бухман Антон Владимирович О сложности распознавания некоторых свойств функций многозначных логик, заданных полиномами..................... 93 Лысиков Владимир Владимирович Порождение двоичных последовательностей с помощью регистров сдвига малой степени............................. 94 Мазуров Анатолий Алексеевич О некоторых свойствах функций многозначных логик, связанных с линейными преобразованиями........................ 96 Садовников Олег Александрович Реализация булевых функций схемами с подведением переменных, вложенными в единичный куб....................... 98 Улесова Александра Юрьевна Сложность реализации булевых функций в некоторых моделях клеточных схем.................................. 100 Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Чистиков Дмитрий Викторович Тестирование бесповторных функций в различных базисах...... 102

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

Абрамов Николай Александрович Построение модели влияния трафика вредоносного программного обеспечения на трафик в глобальной сети................. 104 Азимов Александр Евгеньевич Исследование сходимости протокола BGP в глобальной сети...... 106 Андреев Дмитрий Юрьевич Разработка инструментальных средств для анализа характеристик коммуникационной среды многопроцессорных вычислительных систем 107 Анциферова Дарья Александровна Исследование эффективности применения параллельных эвристических алгоритмов к решению задачи мэппинга для массивнопараллельной системы Blue Gene/P.................... 109 Гайворонская Светлана Александровна Разработка расширения протокола RFB для улучшения отзывчивости тонких клиентов................................ 111 Глазкова Екатерина Алексеевна Исследование эффективности решения разностных задач на высокопроизводительных вычислительных системах.............. 113 Горнак Татьяна Александровна Инcтрументальное средство автоматизации построения моделей нормального поведения приложений...................... 115 Елизаров Анатолий Валерьевич Система визуализации комплексных атак и состояния защищаемой сети116 Лебедев Андрей Сергеевич Физически аккуратное моделирование отражательной способности материалов поверхностей плоских объектов................ 118 Моисейцев Алексей Борисович Устранение эффекта Гиббса при восстановлении сжатого мультипликационного видео............................... 120 Пашков Василий Николаевич Исследование эффективности модификаций генетического алгоритма для задачи выбора сбалансированного набора механизмов отказоустойчивости в вычислительных системах............... 121 Оглавление Торощин Эдуард Сергеевич Контроль нормального поведения приложений в подсистеме безопасности ядра Linux............................... 123 Усков Евгений Иванович Разработка модели пользовательского трафика в глобальной сети на основе аналитических моделей трафика доменов............. 124 Фролов Владимир Александрович Алгоритмы фотореалистичной визуализации на графических процессорах...................................... 126 Шаповалов Роман Викторович Автоматическое выделение объектов в данных лазерного сканирования127 Янгель Борис Константинович Бустинг решающих деревьев с использованием методов эволюционной оптимизации.................................. 128

Кафедра алгоритмических языков

Алексеев Алексей Александрович Автоматическое обновление аннотации новостного кластера...... 130 Четверкин Илья Игоревич Автоматизированное формирование базы знаний для задачи анализа мнений..................................... 132 Котельников Дмитрий Сергеевич Извлечение информации из новостных кластеров на основе автоматически сформированных шаблонов..................... 134 Юданов Анатолий Александрович Моделирование поведения взаимодействующих агентов в среде с ограничениями................................... 135

Кафедра системного программирования

Аро Диас Филипп Луисович Исследование новых подходов к организации аналитической обработки данных большого объема......................... 137 Плотникова Анастасия Константиновна Средства разработки расчётных моделей для моделирования ядерных реакторов................................... 139 Притула Михаил Николаевич Распараллеливание многоблочных задач для SMP-кластера...... 141 Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Ручкин Дмитрий Андреевич Исследование методов разработки приложений баз данных в сервисориентированных кластерных архитектурах............... 142

Отделение бакалавров

Бондарева Кристина Игоревна Идентификация параметров и валидизация популяционных моделей фармакокинетики противосудорожных препаратов по данным терапевтического лекарственного мониторинга................ 144 Грызунов Дмитрий Аркадьевич Визуализация трехмерных неструктурированных массивов данных большого объема..................... .

......... 146 Дмитриевский Михаил Дмитриевич Сенсорные системы ввода и интуитивно понятные интерфейсы.... 148 Куренной Алексей Святославович Распознавание цитат в текстовых фрагментах.............. 149 Минеев Дмитрий Борисович Разработка программного средства-инструментария для исследования криптографических свойств булевых функций........... 151 Рубанов Максим Сергеевич Реализация операций обработки многомерных массивов на языке программирования F#.............................. 153 Третьяков Ярослав Игоревич Система автоматизированной защиты программного обеспечения от несанкционированного доступа....................... 154 Фам Ху Куанг Разработка методики сравнения банковских веб-сайтов......... 156 Яковлев Игорь Юрьевич Разработка средств создания мобильных биобиблиографических энциклопедий.................................. 158

–  –  –

Кафедра МФ Метод определения неизвестного контура в задаче Дирихле Работа удостоена диплома I степени Гаврилов Сергей Вадимович студент кафедры математической физики email: gvrlsrg@gmail.com научный руководитель д.ф.-м.н. Денисов Александр Михайлович Рассматриваемая в дипломной работе обратная задача относится к классу обратных задач для эллиптических уравнений, в которых неизвестной является часть границы области. Отличительной особенностью рассматриваемой обратной задачи является то, что в ней ищется граница неоднородности кусочно-однородной среды, в которой решается задача Дирихле. В работе [1] исследовалась обратная задача для эллиптического уравнения в случае неизвестной границы неоднородности среды, предложен численный метод решения обратной задачи в случае трехмерного пространства. Для ее численного решения использовалось специальное представление неизвестной границы. В дипломной работе разработан итерационный метод решения обратной задачи в случае двумерного пространства без предположения о специальном виде границы неоднородности .

Приведем математическую постановку задачи. Рассмотрим на плоскости односвязную ограниченную область с границей 0. Пусть 1 односвязная область с границей 1, такая, что 1. Границы 0 и 1 достаточно гладкие. Обозначим через 0 область 0 = \ 1 .

Рассмотрим следующую краевую задачу. Требуется найти функцию u(x, y) такую, что u C(), u(x, y) = ui (x, y), (x, y) i (i = 0, 1), где u0 C 2 (0 ) C 1 (0 1 ), u1 C 2 (1 ) C 1 (1 ), ui (x, y) = 0, (x, y) i, i = 0, 1;

–  –  –

u0 (x, y) u1 (x, y), (x, y) 1 .

k0 = k1 n n Здесь k0, k1 заданные положительные постоянные, а f (x, y) известная функция, непрерывная и не постоянная на 0 .

Сформулируем обратную задачу. Пусть в краевой задаче граница 0, постоянные k0, k1 и функция f (x, y) на 0 заданы, а граница 1 не известна .

Требуется определить 1, если задана дополнительная информация о решении задачи:

u(x, y) = g(x, y), (x, y) 2, Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года где 2 замкнутая кривая принадлежащая 0 и содержащая внутри себя 1, а g(x, y) заданная непрерывная на 2 функция .

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

–  –  –

1. Денисов А.М.,Захаров Е.В.,Калинин А.В.,Калинин В.В. Численные методы решения некоторых обратных задач электрофизиологии сердца//Дифференц. ур-ния. 2009. т.45. N.7. с.1014-1022 .

2. Захаров Е.В.,Калинин А.В. Численное решение трехмерной задачи Дирихле в кусочно-однородной среде методом граничных интегральных уравнений//Ж. вычисл. матем. и матем. физ. 2009. т.49. N.7. с.1197Разработка системы моделирование полёта микросамолётов на параллельных архитектурах Работа удостоена диплома III степени Кривов Максим Андреевич студент кафедры математической физики email: m_krivov@cs.msu.su научный руководитель к.ф.-м.н. Березин Сергей Борисович В данной работе проводится анализ существующих параллельных архитектур с целью разработки системы для проведения моделирования полёта микросамолётов в режиме реального времени с высокой точностью. Для достижения поставленной цели были решены такие задачи, как разработка механизма эффективного отображения вычислений на используемые вычислители, адаптация существующих алгоритмов моделирования полёта микросамолётов под используемые параллельные архитектуры и непосредственная разработка среды для моделирования полёта микросамолётов .

Под микросамолётом понимается некоторый летательный аппарат, размах крыльев которого не превышает одного метра и имеющий массу до одного килограмма. Максимальная скорость полёта микросамолётов обычно составляет от 10 до 20 метров в секунду, а числа Рейнольдса лежат в диапазоне от 10 000 до 500 000. Подобные микросамолёты обычно оснащаются одним Кафедра МФ или несколькими электрическими двигателями и батареей, емкости которых хватает всего на 1 - 2 часа автономного полёта .

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

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

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

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

1. Katz J., Plotkin A. Low-speed aerodynamics, McGraw-Hill Inc., 1991 .

2. Кривов М.А., Притула Н.М. Конвейерная модель представления параллельных программ // Материалы конференции "Высокопроизводительные Вычисления на Кластерных Системах 2009, Владимир, 2009 .

–  –  –

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

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

–  –  –

1. A. Nomura, M. Ichikawa, R.H. Sianipar, H. Miike, Reaction-Diusion Algorithm for Vision Systems, Vision Systems: Segmentation and Pattern Recognition, ed. G. Obinata and A. Dutta, i-Tech, Vienna, p. 61-80, 2007 .

2. A. Nomura, M. Ichikawa, R.H. Sianipar, H. Miike, Edge Detection with Reaction-Diusion Equations Having a Local Average Threshold, Pattern Recognition and Image Analysis, Vol. 18, No 2, pp. 289-299, 2008 .

3. P. Perona, J. Malik, Scale-space and Edge Detection Using Anisotropic Diusion, IEEE Trans. Pattern Anal. Mach. Intell., pp. 629-639, 1990 .

4. J.F.Canny, A computational approach to edge detection, IEEE Trans .

Pattern Analysis and Machine Intelligence, 8, pp.679-698, 1986 .

Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Исследование периодических решений параболического функционально-дифференциального уравнения диффузии с запаздыванием Романенко Татьяна Евгеньевна студентка кафедры математической физики email: tatjana.romanenko@gmail.com научный руководитель д.ф.-м.н. Разгулин Александр Витальевич Дипломная работа посвящена аналитическому и численному исследованию периодических решений в пространственно-однородной модели и модели с диффузией в кольце, которые описывают взаимодействие световых лучей в нелинейной оптической системе с запаздыванием в контуре обратной связи [1] .

В ходе аналитического исследования к пространственно-однородной модели, описываемой обыкновенным дифференциальным уравнением с запаздыванием du (r, t) = u(r, t) + K(1 + cos u(r, t T )), dt применялась теория, разработанная в [2], была сформулирована и доказана теорема существования и единственности периодических решений данной задачи. В ходе численного исследования при параметрах, удовлетворяющих условиям доказанной теоремы, были получены периодические решения .

В рамках исследования пространственно-неоднородной модели, описываемой параболическим функционально-дифференциальным уравнением диффузии с запаздыванием 2u du (, t) = D 2 (, t) u(, t) + K(1 + cos u( +, t T )), dt периодические решения задачи искались в виде бегущей волны. Использование движущейся системы координат позволило перейти к анализу бифуркации в стационарной задаче на основе теоремы о неявном операторе. Отметим, что переход в движущуюся систему координат применялся ранее, например в [3, 4], для параболических уравнений без запаздывания. Для уравнений с запаздыванием такой прием при исследовании бифуркации Хопфа впервые предложен в данной работе .

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

Кафедра МФ Работа выполнена при поддержке ФЦП Научные и научнопедагогические кадры инновационной России на 2009–2013 гг .

Литература

1. A. V. Razgulin Finite-Dimensional Dynamics of Distributed Optical System with Delayed FeedBack.// Computers & Mathematics with applications, 2000, Vol. 40, №12, pp. 1405–1418 .

2. Хейл Дж. Теория функционально-дифференциальных уравнений. М.:

Мир, 1984 .

3. Хенри Д. Геометрическая теория полулинейных параболических уравнений. М.: Мир, 1985 .

4. Денисов Г. А. О математическом описании спиральных волн в распределенных химических системах.// Прикладная математика и механика, 1984, т. 48, вып. 2, с. 293–301 .

Вариационный метод поиска границы диска зрительного нерва на изображениях глазного дна Работа удостоена диплома II степени Семашко Александр Сергеевич студент кафедры математической физики email: alex.semashko@gmail.com научный руководитель д.ф.-м.н. Крылов Андрей Серджевич Диабетическая ретинопатия и глаукома наиболее распространенные причины слепоты. Эти заболевания поддаются лечению на ранних стадиях, когда ухудшение зрения еще не заметно. Поэтому для их своевременного диагностирования требуется проводить регулярное обследование глазного дна .

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

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

В настоящее время существует несколько методов поиска границы ДЗН, и в системах анализа обычно используются вариации какого-либо из них. Один из лучших на сегодня методов описан в статье [1]. Он состоит в подавлении Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года сосудов с помощью морфологического закрытия и последующем применении вариационного метода активных контуров [2] для поиска границы .

Этот метод имеет следующие недостатки:

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

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

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

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

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

Работа выполнена при поддержке ФЦП Научные и научнопедагогические кадры инновационной России на 2009-2013 годы и гранта РФФИ 09-07-92000-HHC .

Литература

1. A. Osareh, M. Mirmehdi, B. Thomas and R. Markham. Colour Morphology and Snakes for Optic Disc Localisation. The 6th Medical Image Understanding and Analysis Conference. 2002. pp. 21-24 .

2. M. Kass, A. Witkin and D. Terzopoulos Snakes: Active Contour Models .

International Journal of Computer Vision. 1987. Vol. 1. pp. 321-331 .

3. С. Судаков, А. Семашко, О. Баринова, А. Конушин, В. Киншаков, А. Крылов Алгоритмы детектирования разметки и дефектов дорожного покрытия. Proceedings of GraphiCon’2008, Moscow, Russia, June 2008, pp. 206-212 .

Кафедра МФ

4. А. С. Семашко, А. С. Крылов Обработка и анализ границ объектов на основе метода активных контуров. Труды 12-й международной конференции и выставки Цифровая обработка сигналов и её применение (DSPA’2010), т. 2, стр. 90-93 .

Метод нахождения и параметризации области глаз на изображениях лиц Сисакян Анастасия Алексеевна студент кафедры математической физики email: n_sisakian@mail.ru научный руководитель – к.ф.-м.н., Крылов А.С .

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

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

В дипломной работе был проведен анализ существующих методов и предложен алгоритм поиска глаз на изображениях лиц. Предложенный алгоритм состоит из двух последовательных этапов: выделение кожных областей на изображениях лиц и поиск зрачков глаз. В алгоритме выделения кожных областей использовался перевод изображения из цветового пространства RGB в пространство ST (Saturation-Tint) [5]. Это позволило бороться с проблемой плохой освещенности на снимках. При классификации кожных областей вычислялось расстояние Махаланобиса от усредненного изображения, составленного по 16 входным изображениям из базы IMM [4], [5]. Из информации, полученной после первого этапа, были сделаны оценки на радиус глаза в зависимости от площадей кожных пикселей на изображениях, что значительно упростило работу с преобразованием Хафа для поиска круглых объектов [6] .

Алгоритм был программно реализован на языке С#.

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

• метод хорошо работает на изображениях, полученных в схожих условиях, Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года

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

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

Дальнейшая работа по повышению эффективности алгоритма будет основана на более детальном рассмотрении всех областей локальных максимумов, полученных после преобразования Хафа. Работа выполнена при поддержке ФЦП Научные и научно-педагогические кадры инновационной России на 2009 – 2013 годы .

Литература

1. Глазунов А.К. Безопасность. Компьютерное распознавание человеческих лиц. 2000. http://www.osp.ru/

2. Ke Sung, Hong Wang. A Composite Method to Extract Eye Contour, 7 p., Aective Computing and Intelligent Interaction, First International Conference, ACII 2005 .

3. T. Rajpathak, R. Kumar, E. Schwartz. Eye Detection Using Morphological and Color Image Processing, 5 p., Florida Conference on Recent Advances in Robotics, FCRAR, 2009 .

4. M.M. Nordstrom, M. Larsen, J. Sierakowski, M.B. Stegmann. The IMM Face Database. An Annotated Dataset of 240 Face Images. pp. 1–4, 2004 .

5. F. Tomaz, T. Candeias, H. Shahbazkia. Improved Automatic Skin Detection in Color Images. In: DICTA, pp. 419–428. CSIRO Publishing, 2003 .

6. К. Мариничев, В. Вежневец. Алгоритмы выделения параметрических кривых на основе преобразование Хафа. Компьютерная графика и мультимедиа. Выпуск №4(1)/2006 .

http://cgm.computergraphics.ru/content/view/107, 2006 .

Многомасштабный метод подавления шумов в аудиосигналах Ткаченко Максим Сергеевич студент кафедры математической физики email: makseq@makseq.com научный руководитель к.ф.-м.н. Лукин Алексей Сергеевич Основная цель работы построение, исследование и реализация алгоритмов очистки звукового сигнала от шума .

Шум это нежелательный сигнал, который возникает при передаче или измерении другого, чистого сигнала. Аддитивным называют шум, который можно представить так: x(t) = s(t) + w(t), где x(t) зашумлённый сигнал, Кафедра МФ s(t) чистый сигнал, w(t) сигнал шума, не зависящий от чистого сигнала .

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

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

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

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

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

–  –  –

1. S.F. Boll. Suppression of acoustic noise in speech using spectral subtraction .

IEEE Trans. Acoust., Speech, Signal Process., vol.27, Apr. 1979, pp. 113Arthur Szlam. Non-Local Means for Audio Denoising. Recent UCLA Computational and Applied Mathematics Reports, 2008, 5 p .

3. Alexey Lukin, Jeremy Todd. Adaptive Time-Frequency Resolution for Analysis and Processing of Audio. Proceeding of the Audio Engineering Society (AES) Convention, Paris, May 2006, 10 p .

4. М.С. Ткаченко, А.С. Лукин. Многомасштабный метод спектрального вычитания для подавления шумов в аудиосигналах. В сб. тезисов ”DSPA-2010”. Москва, 2010 .

5. Демонстрационная версия онлайн-денойзера: http://makseq.com/makseq Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Математическое моделирование экологических рисков загрязнения вод океанов и морей Работа удостоена диплома I степени Заячковский Антон Олегович студент кафедры вычислительных технологий и моделирования email: azayachkovskiy@gmail.com научный руководитель д. ф.-м. н., профессор Агошков Валерий Иванович В данной работе изучается проблема загрязнения поверхностных вод и разработан алгоритм для количественного подсчета экологического риска такого загрязнения с применением методов теории сопряженных уравнений .

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

В достаточно общем случае риск R может быть определен как произведение матрицы вероятностей опасности одного или нескольких рассматриваемых событий или процессов P на вектор величин ожидаемых последствий (ущерба) Q:

R = P · Q .

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

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

Определим ее в виде функционала:

Z C · dDdt .

(C) = DT Функция C описывает концентрацию пассивной примеси в регионе, DT (0, T ) D область изменения пространственно-временных координат и характеристическая функция охраняемой области водоема. Функционал представляет суммарное количество загрязнений, которое может поступить в водоем от действующих и потенциально возможных источников. Он показывает до какой степени водоем подвержен воздействию антропогенных источников и дает возможность оценить степень экологической опасности для наблюдаемого региона .

В настоящей работе доказано следующее утверждение: Пусть распространение концентрации C загрязняющего вещества при выбросе пассивной примеси массой M от мгновенного точечного источника в начальный момент времени задается решением уравнения конвекции-диффузиираспада, записанного в дифференциально-операторной форме LC C + t Кафедра ВТМ u C + v C · µ C + (C) = 0 на части поверхности сферы Rзем Rзем sin D в сферических координатах (,, Rзем ), где Rзем средний радиус земли и DT D (0, T ) область изменения пространственно-временных коорS динат. Пусть также D разбита на подобласти Di = D (меры mes(Di )) i таким образом, что можно задать вероятность аварии на конкретной части акватории как Pi ((, ) Di )).

Тогда величина экологической опасности может быть вычислена по формуле:

–  –  –

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

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

–  –  –

1. Вишняков Я. Д., Радаев Н. Н. Общая теория рисков М.: Издательский центр Академия, 2008 .

2. Пененко В. В., Цветова Е. А. Математические модели для изучения рисков загрязнения природной среды // ПМТФ. 2004 Т. 45, № 2. с. 136Марчук Г. И. Математическое моделирование в проблеме окружающей среды М.: Наука, 1982 .

4. Агошков В. И. Методы оптимального управления и сопряженных уравнений в задачах математической физики М.: ИВМ РАН, 2003 .

Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Модель эластичного кровеносного сосуда и ее приложение в задачах рентгенохирургии Иванов Юрий Александрович студент кафедры вычислительных технологий и моделирования email: yura-vtm@yandex.ru научный руководитель д.ф.-м.н. Василевский Юрий Викторович Сердечно-сосудистые заболевания по-прежнему являются основной причиной смертности во всем мире. В связи с этим потребность в создании численных моделей для решения задач, связанных с динамикой кровообращения и изменением упругих свойств стенки сосуда, во всем мире очень велика. Данная работа посвящена конкретному экономичному с вычислительной точки зрения подходу для изучения некоторых проблем, связанных с кровеносной системой человека .

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

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

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

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

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

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

Литература

1. M. Rosar, C. Peskin. Fluid ow in collapsible elastic tubes: a threedimensional numerical model. New York J. Math., 7 (2001), 281–302 .

2. С. С. Симаков. Магистерская диссертация. Разработка и численная реализация динамической модели кровеносной системы человека. 2003 .

3. S. S. Simakov, A. S. Kholodov. Computational study of oxygen concentration in human blood under low frequency disturbances. Mat. Mod. Comp. Sim., 1 (2009), 283–295 .

4. Y. Mori, C. Peskin. A universal programmable ber architecture for the representation of a general incompressible linearly elastic material as a berreinforced uid. Advances in Applied Mathematics, 1 (2009), No. 43, 75–100 .

5. К. Каро, Т. Педли, Р. Шротер, У. Сид; Под ред. С. А. Регирер, В. М. Хаютин. Механика кровообращения. М.: Мир, 1981 .

Разработка параллельной версии модели гидродинамики Мирового океана Работа удостоена диплома II степени Калмыков Владимир Владимирович студент кафедры вычислительных технологий и моделирования email: vvk88@mail.ru научный руководитель д.ф.-м.н. Ибраев Рашит Ахметзиевич Одним из актуальных направлений в исследованиях климата Мирового океана является создание моделей термогидродинамических процессов океТезисы лучших дипломных работ факультета ВМК МГУ 2010 года ана высокого пространственного разрешения. Исследования, в частности по моделированию Атлантического океана [3], показывают, что начиная лишь с разрешения 1/10 (порядка 104 104 102 точек на каждый массив функций) возможно корректное описание таких важных явлений как динамика вихрей, крупномасштабные пограничные течения и др. Очевидно, для решения задач такого масштаба требуется применение суперкомпьютерных систем. Следует отметить, что отечественных моделей с разрешением порядка 1/10 и менее не существует. Последняя версия модели Мирового океана, разработанная в России, имеет разрешение 1 1/2 по широте и долготе [1] .

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

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

Для двумерных подобластей, в которых нет расчетных точек, процессоры не выделяются, что позволяет экономить до 20-25% вычислительных ресурсов .

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

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

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

Совместное решение уравнений для бароклинной и баротропных компонент движений предполагает, что интегрирование на один шаг трехмерной бароклинной системы уравнений синхронизировано с интегрированием на 150-200 шагов двумерной системы уравнений мелкой воды для баротропных движений. Решение баротропной системы является узким местом с точки зрения масштабируемости программного кода модели из-за высокой нагрузки на коммуникации при росте числа процессоров. Это теоретическое предположение подтвердилось экспериментально. Был предложен и реализован новый алгоритм решения системы, где схема работы 1 шаг/межпроцессорный обмен заманен на схему n шагов/межпроцессорный обмен. Таким образом, решаются те же уравнения, но на расширенной на n ячеек области, и с каждым шагом эта область сужается на 1 ячейку по всем направлениям .

Модель тестировалась на суперкомпьютерном комплексе МВС-100К. Расчеты проводились на 480 шагов по времени, размер сеток 144274614 и 2882144214, 180 баротропных шагов. На всех размерах процессорных решеток получено ускорение, близкое к линейному. На 1/4 сетке на 768 процессорах получен прирост в ускорении в сравнении с исходным вариантом в 3.6 раз, на 1/8 на 2592 процессорах в 3.4 раза. Но главное, за счет разрешения узкого места программы и организации асинхронных обменов с внешней памятью, появилась возможность измельчать сетку и, соответственно, увеличивать число процессоров без серьезных коммуникационных потерь желаемая масштабируемость достигнута .

–  –  –

1. Володин Е.М. Воспроизведение современного климата с помощью совместной модели INMCM 4.0. Физика Атмосферы Океана, 2010 .

2. Ибраев Р.А. Математическое моделирование термодинамических процессов в Каспийском море. Изд-во ГЕОС, Москва, 2008 .

–  –  –

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

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

Описанный в дипломной работе алгоритм является аналогом мультипольного метода, но разбиение суммы идет не по качеству далеко - близко, а по качеству до - после [4] .

Он состоит из разложения матрицы взаимодействия новым способом и умножения матрицы в полученном виде на векторсвойство (заряд, масса,...). Само по себе разложение имеет сложность O(N 2 ), но производится всего-лишь один раз, далее работают операции по вычислению произведения матрицы на вектор (линейная сложность). Отличительной чертой алгоритма является то, что он состоит из совершенно независимых Кафедра ВТМ конвейеров вычислений, так что при его импелементации можно использовать все вычислительные ресурсы (OpenMP, MPI, CUDA) .

Алгоритм был реализован с использованием OpenMP, ускорение счета на 8 потоках составило порядка 8 раз. Результаты численных экспериментов приведены в следующих таблицах(N - количество частиц, F actor - время построения разложения, M V M ul - время умножения разложенной матрицы на вектор, naiveM V mul - время умножения не разложенной матрицы на вектор, rndL2err - относительная ошибка вычислений по норме L2, mem - необходимая память для хранения разложения) .

N F actor M V mul naiveM V mul rndL2err mem 10000 1.13 0.0212 0.446 2.1e-5 21M 20000 3.13 0.0223 1.75 2.7e-5 44M 30000 6.13 0.032 3.93 2.86e-5 68M 40000 9.62 0.04 6.95 2.86e-5 93M 50000 14.75 0.05 10.98 3.05e-5 118M 60000 20.35 0.062 15.9 3.36e-5 144M 70000 26.65 0.067 21.43 3.41e-5 170M 80000 35.67 0.074 27.84 3.58e-5 197M 90000 46.03 0.085 35.31 3.8e-5 223M 100000 59.38 0.1 43.74 3.76e-5 250M Таблица 1. Зависимость времени счета разложения, быстрого матвека, стандартного матвека, полученных максимальных рангов от количества частиц при заданной точности = 1e 5, f (x, y) = log r(x, y) в 2-мерном пространстве, частицы расположены случайным образом внутри куба [0; 1]2 N F actor M V mul naiveM V mul rndL2err mem 10000 3.66 0.0665 0.358 1.38e-5 103M 20000 16.08 0.0686 1.36 2.23e-5 236M 30000 37.3 0.105 3.06 2.54e-5 377M 40000 73.3 0.142 5.47 2.96e-5 522M 50000 125.5 0.176 8.5 3.44e-5 676M 60000 181.3 0.172 12.25 3.62e-5 828M 70000 260 0.22 16.6 4.06e-5 989M 80000 366.8 0.27 21.85 4.47e-5 1.2G 90000 455.7 0.285 27.75 4.56e-5 1.3G 100000 598 0.341 34.3 4.96e-5 1.5G Таблица 2. Зависимость времени счета разложения, быстрого матвека, стандартного матвека, полученных максимальных рангов от количества частиц при заданной точности = 1e5, f (x, y) = r(x, y)1 в 3-мерном пространстве, частицы расположены случайным образом внутри куба [0; 1]3

Литература

1. J. Barnes and P. Hut. A hierarchical O(N log N ) force-calculation algorithm .

Nature, 324:4, 1986 .

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

2. L. Greengard and V. Rokhlin. A fast algorithm for particle simulations .

Journal of Computational Physics, 73(2):325–348, 1987 .

3. E. Tyrtyshnikov. Mosaic-skeleton approximations. Calcolo, 33(1):47–57, 1996 .

4. Alan Edelman Charles E. Leiserson Erik D. Demaine, Martin L. Demaine and Per-Olof Persson. Building Blocks and Excluded Sums. From SIAM News, Volume 38, Number 1, January/February 2005, 2005 .

Параллельная реализация модели общей циркуляции океана Терехов Кирилл Михайлович студент кафедры вычислительных технологий и моделирования email: kirill.terehov@gmail.com научный руководитель д. ф.-м. н. Володин Евгений Михайлович В данной дипломной работе осуществлена параллельная реализация разработанной ранее -модели общей циркуляции океана. Параллелизация реализована с помощью технологий MPI и OpenMP .

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

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

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

Кафедра ВМ Тестирование модели производилось на сетке с разрешением 1 0, 5 на кластере SGI Altix и Bluegene/p. При сравнении времени работы параллельной программы в гибридном режиме с временем работы исходной программы получена эффективность до 50%. Получено, что на данном разрешении при использовании большого числа процессоров обмен данными занимает подавляющее время. Узкими местами программы является переинтерполяция на географическую сетку и модель морского льда, требующая меньшего шага по времени .

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

Литература

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

2. Дианский В. Б., Володин Е. М. Воспроизведение современного климата с помощью совместной модели общей циркуляции атмосферы и океана Изв, РАН. Физика атмосферы и океана, Т. 38, № 6, с. 421-442 .

3. Марчук Г. И. Методы вычислительной математики М.:Наука, 1980 .

4. Balay S., Buschelman K., Eijkhout V., Gropp W. D., Kaushik D., Knepley M. G., Curfman L., Smith B. F., Zhang H. PETSc Users Manual ANL-95/11

-Revision 3.0.0, Argonne National Laboratory, 2008 .

Симплектические вычислительные методы молекулярной динамики Работа удостоена диплома III степени Александров Петр Александрович студент кафедры вычислительных методов email: petr_aleksandrov@mail.ru научный руководитель д.ф.-м.н., проф. Еленин Георгий Георгиевич Атомно-молекулярное движение в приближении молекулярной динамики описывается решениями задач Коши для гамильтоновых систем обыкновенных дифференциальных уравнений. Для решения этих задач используются численные методы. Естественно потребовать от этих численных методов сохранения глобальных свойств исходной системы (консервативность, обратимость, симлектичность [1]). Целью работы являлось исследование возможности построения метода, сохраняющего все перечисленные свойства .

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

Исследовано поведение приращения энергии при различных значениях шага и параметра семейства .

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

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

Работа выполнена в рамках научного проекта РФФИ 09-01-12089 офи-м .

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

Литература

1. E. Hairer, S. P. Norsett, G. Wanner. Solving Ordinary Dierential Equations I. Nonsti Problems. Second Revised Edition. Springer, 1993 .

2. Г. Г. Еленин, П. И. Шляхов. О консервативности двухстадийных симметрично-симплектических методов Рунге-Кутты и метода Штермера-Верле // Дифференциальные уравнения, 2010, том 46, №7 .

Численное решение уравнений газовой динамики в лагранжевых переменных Работа удостоена диплома I степени Галанина Анна Михайловна cтудентка кафедры вычислительных методов email: GalaninaAnna@gmail.com научный руководитель д.ф.-м.н Фаворский Антон Павлович Во многих областях современной науки возникают задачи, включающие в качестве существенного элемента уравнения газовой динамики. Уравнений Кафедра ВМ газовой динамики нелинейны, поэтому одним из наиболее эффективных и универсальных способов их решения в настоящее время являются численные методы .

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

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

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

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

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

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

Схема обладает следующими свойствами:

• Схема является явной, однородной и консервативной;

• Она позволяет рассчитывать задачи с разрывными решениями (такие, как задача о распространении ударной волны, задача о распаде произвольного разрыва и т. д.) без введения регуляризаторов (искусственная Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года вязкость и т. д.);

• Как показали расчёты, численное решение слабо зависит от числа Куранта: при изменении числа Куранта на порядок получаемое численное решение практически не меняется на своём характерном масштабе;

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

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

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

–  –  –

2. А.А. Самарский, Ю.П. Попов. Разностные методы решения задач газовой динамики. М.: Наука. Гл. ред. физ.-мат. лит., 1992 .

3. Рождественский Б.Л., Яненко Н.Н. Системы квазилинейных уравнений и их приложения к газовой динамике. М.: Наука. Гл. ред. физ.-мат. лит., 1978 .

Решение уравнений газовой динамики в эйлеровых переменных с использованием сплайн функций Работа удостоена диплома II степени Исаков Виктор Александрович студент кафедры вычислительных методов email: aD-One@yandex.ru научный руководитель д.ф.-м.н Фаворский Антон Павлович Дипломная работа посвящена решению уравнений газовой динамики в эйлеровых переменных с использованием специальных сплайновых функций .

Численное решение системы уравнений газовой динамики строится в классе сеточных функций uj, отнесенным к узлам равномерной сетки по проk странственной и временной переменным. Границы расчетных ячеек проходят Кафедра ВМ через полуцелые точки пространства. Построение схемы проводится интегроинтерполяционным методом [3]. Точные интегральные потоки массы, импульса и энергии через границы ячеек представляются в виде суммы постоянного (фонового) значения потока и квазилинейной суперпозиции поправок к нему от малых возмущений, являющимися решениями линеаризованной системы уравнений газовой динамики.

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

y (x, xk, tj ) = uj + Dk (x xk ) j k j

Величина Dk характеризует угол наклона сплайна и вычисляется по формуле:

|ux | ux + |ux | ux j Dk = |ux | + |ux | Сплайновые функции разбиваются послойно на систему малых возмущений, условно называемых кирпичами .

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

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

Разработанный метод обладает следующими достоинствами:

• Схема не содержит каких-либо искусственных регуляризаторов;

• Метод обеспечивает квазимонотонное приближенное решение при расчете разрывных течений и воспроизводит структуру ударной волны на небольшом количестве расчетных ячеек (2-3 ячейки);

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

• Следует отметить слабую зависимость от числа Куранта и количества кирпичей даже при достаточно больших шагах расчетной сетки;

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

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

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

Литература

1. А.Г. Куликовский, Н.В. Погорелов, А.Ю. Семенов. Математические вопросы численного решения гиперболических систем уравнений. - М.:

Физматлит, 2001 .

2. Г. Курант, К.Ф. Фридрихс. Сверхзвуковое течение и ударные волны .

-М.: Издательство Иностранной Литературы, 1950 .

3. А.А. Самарский, Ю.П. Попов. Разностные методы решения задач газовой динамики. - М.: Едиториал УРСС, 2004 .

Корпускулярное моделирование процесса взаимодействия лазерного импульса с плазмой Работа удостоена диплома III степени Кульков Дмитрий Сергеевич студент кафедры автоматизации научных исследований email: integral.rimana@gmail.com научный руководитель к.ф.-м.н. Ечкина Евгения Юрьевна Последние годы отмечены большим прогрессом лазерной физики. Мощность лазерного импульса непрерывно возрастает и достигла значения порядка 1022 Вт·см2, что делает перспективным применение лазеров для радиационного ускорения заряженных частиц. Это обстоятельство привело к активным теоретическим и экспериментальным исследованиям ускорения ионов, предполагающего использование лазеров большой мощности [1–2] .

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

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

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

Кафедра АНИ В процессе моделирования используется два типа частиц: электроны и легкие ионы(протоны). Отношение массы иона к массе электрона выбиралось равным 1836 .

Расчетная область представляет собой прямоугольную область с характерными размерами 400 100, где длина волны = 10. На данную область накладывалась расчетная сетка 1500 1500. В расчетах участвовало 107 частиц .

Лазерный импульс гауссовского профиля с пространственными параметрами 5 25 инициируется на левой границе расчетной области при x = 0 .

Он имеет линейную поляризацию по z-компоненте и направлен вдоль оси y. Безразмерное значение его амплитуды равно a = eE0 /me c = 316. Конфигурация слоя плазмы была направлена на получение ускорения электронов и ионов. Она представляет собой сложную плазменную мишень, состоящую из двух элементов разных плотностей и расположенную в области 45 x 57. Ширина первого элемента мишени 10 с плотностью /pl = 0.2, ширина второго – 2 с плотностью /pl = 0.4 .

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

Рис.1 Распределение плотности ионов в момент времени t=180 На рис. 1 продемонстрирована плотность ионов в момент времени t =

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

На рис. 2 изображена фазовая плоскость (px, x) ионов в момент времени t = 650. На фазовой плоскости мы отчетливо видим сгусток частиц, возникающий в области локализации лазерного импульса. Максимальное значение равно 80 .

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

–  –  –

1. Mourou G. Tajima T. Bulanov S. Optics in the relativistic regime Rev. Mod .

Phys. 2006. P. 309–372 .

2. Borghesi M. Fuchs J. Bulanov S. et al. Fast ignition generation by highintensity laser irradiation of solid targets and applications Fus. Sci .

Technology. 2006. P. 412–415 .

Математическое моделирования рассеивания электромагнитных волн на метаматериалах Семёнов Алексей Николаевич студент кафедры автоматизации научных исследований email: lensflare@mail.ru научный руководитель к.ф.-м.н. Смирнов Александр Павлович Дипломная работа посвящена численным методам решения системы уравнений Максвеллла в открытой области. Эта численная задача актуальна для исследования математических моделей в физике, химии и других науках. Разработаны и реализованы две вариации численного метода решения уравнений Максвелла для двух и трёх мерного случая. Первый метод основан на стандартной модели материалов для диэлектрической проводимости и магнитной проницаемости больше единицы, второй метод базируется на дисперсной модели Друде, позволяющей использовать параметры материала меньше единицы и отрицательные. При численном решении в открытой области использовались поглощающие граничные условия .

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

Литература

1. A.Taove and S.C.Hagness, Computational Electrodynamics: The FiniteDierence Time-Domain Method.Norwood, MA:Artech, 2000 .

2. S.D. Gedney (1996). An anisotropic perfectly matched layer absorbing media for the truncation of FDTD latices .

3. Cui, Tie Jun; Smith, David; Liu, Ruopeng - Metamaterials: Theory, Design, and Applications (Eds.), (2010) .

4. Yang Hao, Raj Mittra - FDTD Modeling of Metamaterials Theory and Applications Artech House Publishers (2009) .

5. В. Г. Веселаго Электродинамика веществ с одновременно отрицательными значениями и µ // УФН. - (1967). - Т.92 - N7 - С.517 Граничное управление смещением и упругой силой на одном конце неоднородного стержня при соответственно закрепленном и свободном втором его конце Работа удостоена диплома II степени Беликов Антон Валентинович студент кафедры общей математики email: belikov.anton@gmail.com научный руководитель д.ф.-м.н., академик Ильин Владимир Александрович В данной работе рассматривается процесс продольных колебаний неоднородного стержня, состоящего из двух участков разной плотности и разной упругости при условии, что длины этих участков выбраны так, что время прохождения волны по каждому из этих участков является одинаковым .

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

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

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

Литература

1. Ильин В. А. О продольных колебаниях стержня, состоящего из двух участков разной плотности и упругости, в случае совпадения времени прохождения волны по каждому из этих участков. Докл. РАН. 2009 .

Т.429. №6. С.742-745 .

2. Ильин В. А., Луференко П. В. Смешанные задачи, описывающие продольные колебания стержня, состоящего из двуз участков, имеющих разные плотности и разные упругости, но одинаковые импедансы. Докл. РАН. 2009. Т.428. №1. С.12-15 .

3. Ильин В. А., Луференко П. В. Обобщенные решения смешанных задач для разрывного волнового уравнения при условии равенства импедансов .

Докл. РАН. 2009. Т.429. №3. С.317-321 .

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

1999. Т.35. №11. С.1517-1534 .

5. Ильин В. А. Волновое уравнение с граничным управлением на одном конце при закрепленном втором конце. Дифференц. уравнения. 1999. Т.35 .

№12. С.1640-1659 .

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

7. Ильин В. А. Граничное управление процессом колебаний на одном конце при закрепленном втором конце в терминах обобщенного решения волнового уравнения с конечной энергией. Дифференц. уравнения. 2000 .

Т.36. №12. С.1670-1686 .

Кафедра ОМ Анализ и визуализация слабых предкризисных сигналов Бурлаков Егор Андреевич студент кафедры общей математики email: egordavk@yandex.ru научный руководитель профессор Шикин Евгений Викторович Цель дипломной работы состояла в создании действенного подхода к обработке и анализу слабых предкризисных сигналов, а также надёжного способа доведения важной информации, извлеченной из этих сигналов, до руководителей организаций .

Впервые понятие слабого сигнала в управлении было введено И. Ансоффом в работе [1], где под слабым сигналом понимается ранний сигнал, возможно несущий в себе признаки наступления важных событий, а возможно, и нет. Это подразумевает, что работа со слабыми сигналами это работа с неопределённостями .

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

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

Удалось сделать следующее:

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

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

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

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

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

–  –  –

Было показано, что относительно поставленной задачи существенно различаются три случая: 1) 0 T 2l, 2) T = 2l, 3) T 2l .

При 0 T 2l граничное управление v(0, t) = µ(t) существует не для любых описанных начальных и финальных состояний. Для данного случая в работе была доказана единственность решения .

В случае T = 2l граничное управление всегда существует и единственно .

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

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

–  –  –

Этот интеграл можно интерпретировать как граничную энергию, затрачиваемую на управление .

Для промежутков времени T = 2ln, n = 2, 3,..., решение задачи оптимального граничного управления было найдено в явном аналитическом виде .

–  –  –

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

2. В. А. Ильин. Граничное управление процессом колебаний на одном конце при закрепленном втором конце в терминах обобщенного решения волнового уравнения с конечной энергией. Дифференциальные уравнения, 2000, Т. 36, № 12. с.1670-1686 .

3. В. А. Ильин. О разрешимости смешанных задач для гиперболиского и параболического уравнений. Успехи математических наук. 1960. Т. 15, вып.2(92), с.97-154 .

4. А. Зоммерфельд. Электродинамика. М. Издательство иностранной литературы, 1958 .

5. Л.А. Вайнштейн. Электромагнитные волны. М. Издательство Радио и связь, 1990 .

Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Элементы структур простых молекул в программном комплексе для квантового моделирования Лашков Дмитрий Геннадьевич студент кафедры квантовой информатики email: dm.lashkov@gmail.com научный руководитель д.ф.-м.н. Ожигов Юрий Игоревич Работа основана на описанном в книге [2] методе коллективного поведения. Сутью данного метода является представление каждой квантовой частицы несколькими экземплярами. Этот же подход применяется и в диффузионном методе Монте Карло, но в отличие от него метод коллективного поведения позволяет моделировать эволюцию волновой функции, а не только стационарные состояния. Метод коллективного поведения не сводится к дифференциальным уравнениям и применяется на основе подходов конструктивной физики. В конструктивной физике физические законы формулируются на языке алгоритмов так же, как в классической физике они формулируются на языке математического анализа [1]. Считается, что если метод верно моделирует известные случаи, то его можно применять и для предсказаний в неизвестных случаях. В методе коллективного поведения делается предположение, что недостаток вычислительных ресурсов моделирует декогеренцию распад во времени сложных квантовых состояний .

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

Разделение эволюции системы на однократный подсчёт структуры молекулы ab initio с помощью моделирования электронных облаков и поддержку рассчитанной структуры во время эволюции с помощью классической механики выгодно с точки зрения экономии вычислительных ресурсов, не смотря на то, что модель эксперимента становится менее точной. Структуру многих сложных молекул получить с помощью ab-initio расчётов современные методы квантовой химии и вычислительные ресурсы в принципе не позволяют, для таких молекул существуют только полученные эмпирическим путём данные. В качестве источника данных о структуре молекул используется Protein Data Bank [4] .

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

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

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

Проведено моделирование следующих экспериментов:

1. Бомбардировка радикала гидроксила (OH), метила (СН3 ), метоксила (CH3 O) изотопом водород-1 с нарастающей скоростью. Получение соответственно молекулы воды, метана, метанола .

2. Столкновение молекул этилена и воды .

Все эксперименты проведены с двумя экземплярами для каждого атома .

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

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

–  –  –

1. Y. I. Ozhigov. Algorithmic approach to quantum physics arXiv:quant-ph/0412196vl, 2004 .

2. Ю. И. Ожигов. Конструктивная физика http://allscience.ru, статья 080916001, 2008 .

3. К. С. Аракелов, Моделирование квантовой динамики трехчастичных систем в квазиклассическом приближении методом коллективного поведения Матем. моделирование, № 21:5, c. 83–91, 2009

4. Protein Data Bank, http://www.wwpdb.org

–  –  –

В данной работе рассматривается модель эндогенного формирования коалиций. Исследование проводится с помощью математического аппарата теории игр, в первую очередь, понятий равновесия Нэша и коалиционных равновесий. В отличие от более ранней литературы ( [1] и [2]) по данной тематике, рассматривается модель без побочных платежей, описываемая некооперативной игрой. Множество участников игры предполагается достаточно большим, что позволяет рассматривать непрерывное распределение их по идеальным точкам. Фактически, исследуемая модель является обобщением модели с равномерным распределением, рассмотренной в [3] и [4], на случай произвольного непрерывного распределения. В рассмотренной модели игроки характеризуются распределением с функцией плотности f (x) по идеальным точкам в одномерном пространстве политических программ. В качестве стратегии каждый игрок a A выбирает sa {0, 1, 2,..., N }. Функция выигрыша U (x, r, p) игрока возрастает по размеру r коалиции, к которой он присоединяется, и убывает с ростом расстояния от ее итоговой политики p до его идеальной точки x. В работе рассматриваются такие ситуации, в которых для каждой коалиции функция fi (p) плотности распределения игроков, присоединившихся к ней, интегрируема. Итоговая политика каждой коалиции определяется как медиана соответствующего распределения. Равновесием Нэша в данной модели является такой набор стратегий, в котором каждый игрок присоединяется к той коалиции, в которой он имеет максимальный выигрыш. Регулярным равновесием называется такое равновесие, в котором для любых различных коалиций соответствующие значения итоговых политик различны .

В работе исследована модель эндогенного формирования коалиций в предположении непрерывной функции выигрыша агентов вида U (x, r, p) = R(r) L(|x p|). Доказана теорема о структуре регулярного равновесия. Из неё следует, что в случае выпуклости функции L(y), характеризующей степень нонконформизма агентов, любому регулярному равновесию будет соответствовать разбиение пространства политических программ на непересекающиеся интервалы, каждый из которых соответствует либо коалиции, либо множеству агентов, воздержавшихся от вступления куда-либо. Кроме того, сформулирован принцип безразличия граничных агентов .

Другим результатом, полученным в данной работе, являются условия единственности определения размера последующих коалиций по размеру предыдущих, связывающие функции L(y) и R(r) с функцией плотности расКафедра ИО пределения f (x), и условия, при выполнении которых каждому размеру iй коалиции в равновесии соответствует не более двух возможных размеров (i+1)-й (не более двух решений уравнений безразличия). В частности, если функция R(r), соответствующая влиятельности коалиции в зависимости от размера, является выпуклой, то существует единственное решение уравнения безразличия, а если она является вогнутой - то не более двух. Также показано, что в тех случаях, когда существует ровно два решения, равновесия, составленные из коалиций размеров, соответствующих большему из корней, и равновесия, размеры коалиций в которых представляют собой чередование первых и вторых корней уравнений безразличия являются устойчивыми к локальному объединению .

Наконец, в работе найдены достаточные условия равновесности и локальной устойчивости структур, соответствующих одной большой коалиции, включающей в себя всех агентов. Так, если L(1 M ) R(1), где M - медиана распределения агентов по идеальным точкам, то эта структура является равновесием, а если L(1 M ) R(1) R( 3 ), то, кроме того, она будет локально устойчивой. Для линейно-квадратичных функций ( L(y) = a · y + b · y 2, a 0, b 0, R(r) = r) найдены условия, выполнение которых гарантирует устойчивость или неустойчивость регулярных равновесий. Доказано, что в случае вогнутой функции плотности распределения всякое регулярное равновесие является устойчивым к локальному расколу. Также было показано, что при достаточно больших значениях параметров по отношению к значениям функции распределения всякое регулярное равновесие, в котором существуют смежные коалиции, будет устойчиво к локальному объединению, а в том случае, если параметры малы, то никакое равновесие не будет устойчиво к локальному объединению .

Работа выполнена при поддержке гранта РФФИ №08-01-00249

–  –  –

1. Alberto Alesina, Enrico Spolaore. On the number and size of nations .

National Bureau Of Economic Research, Working paper №5050, March 1995

2. I. Ortuno-Ortin, J.E. Roemer. Endogenous party formation and the eect of income distribution on policy University of Alicante. IVIE working paper, 2000 .

3. Vasin A., Stepanov D. Endogenous formation of political parties Mathematical and Computer Modelling 48 (2008) 1519–1526

4. Сосина Ю.В. Эндогенное формирование политических структур и исследование их устойчивости Препринт WP7/2004/04, Серия WP7 "Теория и практика общественного выбора Москва, ГУ ВШЭ, 2004 Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Метод декомпозиции в задаче выбора состава оборудования Курочкин Сергей Владиславович студент кафедры исследования операций email: svkurochkin@gmail.com научный руководитель к.ф.-м.н. Давидсон Михаил Рувимович Задача выбора состава оборудования есть задача построения графика включения/отключения энергоблоков, работающих в рамках единой энергосистемы и определения их оптимальной почасовой нагрузки, с учетом набора ограничений, по критерию минимизации расходов на производство электроэнергии. Суммарная выработка э/энергии энергоблоков должна покрывать прогноз потребления, что является ограничением, связывающим разные энергоблоки. Другими ограничениями являются ограничения на работу отдельных энергоблоков .

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

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

Рассмотрим траекторию на горизонте планирования отдельновзятого электрогенератора, как последовательность состояний блока yt S, t = 1,..., H. Введем семейство отображений It : S {0, 1}, It (s) = 1 s = yt .

Допустимость перехода из состояния si только в состояния sj1,...

sjm, задается следующими ограничениями:

m X It (si ) It+1 (sjk ) .

k=1

–  –  –

где X[k] = x|D[k] x d[k], а ck, dk, xk, Ak разбиения соответствующие блокам матрицы. В рамках задачи выбора состава оборудования, D описывает ограничения на работу электрогенераторов, A – связывающие ограничения на суммарную выработку электроэнергии. В дипломной работе построен алгоритм решения двойственной задачи, основанный на методах выпуклого анализа [3] .

<

–  –  –

1. C.-P. Cheng, C.-W. Liu, C.-C. Liu. Unit commitment by lagrangian relaxation and genetic algorithms. IEEE Trans. on Power System, vol. 15, 2000 .

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

Наука, 1990 .

3. C. Lemarechal, A. Nemirovskii, Y. Nesterov. New variants of bundle methods. Mathematical Programming 69, 1994 .

Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Задача оптимизации расписания работы складских помещений Лесков Андрей Андреевич студент кафедры исследования операций email: andrey.leskov@gmail.com научный руководитель к.ф.-м.н. Денисов Дмитрий Витальевич В дипломной работе рассматриваются вопросы, связанные с составлением расписанием работы складов. Под складом подразумевается организация, имеющая места для хранения объектов и занимающаяся приёмом, хранении и отпуске объектов (например деталей или товаров) по определённым правилам. Вся деятельность склада влечёт определённые материальные затраты .

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

При построении математической модели были сделаны следующие предположения:

1. На склад объекты хранения прибывают детерминировано

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

3. Отпуск объектов со склада происходит с постоянной скоростью

4. Размещение заказа на складе и хранение имеет известную стоимость

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

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

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

Кафедра ИО Литература

1. Moncer Hariga. 1989. Technical report ’The warehouse scheduling problem’ .

2. Michael L.Pinedo. 2008. Scheduling. Theory,Algorithms, and Systems. Third Edition .

3. Doll And Whybark D.C. 1973. An Iterative Procedure for the SingleMachine,Multi-Product Lot Sheduling Problem .

Численное исследование некоторых математических моделей производства лазерных мишеней Работа удостоена диплома III степени Малинина Елена Александровна студентка кафедры исследования операций email: malininaea@gmail.com научный руководитель д.ф.-м.н., проф. Белолипецкий Александр Алексеевич Для решения задачи использования в практических целях энергии термоядерного синтеза существует два основных подхода: магнитный термоядерный синтез и инерциальный термоядерный синтез (ИТС). В данной дипломной работе был проведен численный анализ двух задач, возникающих в процессе производства и эксплуатации лазерных мишеней, используемых в инерциальном термоядерном синтезе: заполнения мишени и деградации её топливного слоя .

Математической моделью первой задачи является нелинейная краевая задача Коши для системы нелинейных параболических уравнений [4]. Указанная задача была численно проанализирована, получен следующий результат:

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

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

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

1. А. А. Белолипецкий, Е. А. Малинина, К. О. Семёнов. Математическая модель деградации топливного слоя при нагревании лазерной мишени тепловым излучением в рабочей камере реактора. Прикл. матем. и информ.: Труды ф-та ВМК МГУ им. М.В.Ломоносова, раздел I .

2. А. А. Белолипецкий. Об одной сингулярно возмущенной задаче Стефана, описывающей разрушение топливного слоя в лазерной мишени.Вестник Моск. ун-та. Сер. 15. вычисл. матем. и киберн.2008.№1 .

3. И. В. Александрова, А. А. Белолипецкий, Е. Р. Корешева Состояние проблемы криогенных топливных мишеней в современной программе инерциального термоядерного синтеза.Вестник РАЕН, 2007, т.7, № 2 .

4. А. А. Белолипецкий Математическое моделирование и оптимизация процессов заполнения лазерных мишеней газом. Вестник Моск. ун-та .

Сер. 15. вычисл. матем. и киберн.,1997, № 4 .

Математическая модель рынка с вертикальной дифференциацией продуктов Молчанов Александр Александрович студент кафедры исследования операций email: aleks.molchanov@gmail.com научный руководитель профессор, д.ф.-м.н. Васин Александр Алексеевич Рынкам с вертикальной дифференциацей продуктов посвящено большое количество литературы. В работе произведен анализ этой литературы и выявлены общие априорные предпосылки, на которых строятся большинство моделей. На основании этого анализа предложена новая модель .

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

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

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

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

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

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

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

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

Литература

1. Shaked A., Sutton J. Relaxing Price Competition Through Product Dierentiation The Rev. of Econ. Stud. Vol. 49. № 1, 1982 .

2. Adner R., Zemsky P. B. Disruptive Technologies and the Emergence of Competition INSEAD Working Paper No. 2001/103/SM, 2003 .

3. Moorthy K. S. Product and price competition in a duopoly Marketing Sci., v7, pp. 141-168, 1988 .

4. Gabszewicz J., Thisse J.-F. Price Competition, Quality and Income Disparities J. of Econ. Theory. Vol. 20, 1979 .

5. Шерер Ф., Росс Д. Структура отраслевых рынков: перевод с английского М: Инфра-М, 1997 .

6. Рудник П.Б. Ценовая конкуренция в высокотехнологичных отраслях Экономический журнал ВШЭ. Т. 11. № 4, 2007 .

–  –  –

для стоимости опциона V (t, x,, r, v) в рамках модели Хестона-Халла-Уайта возможно только численное, так как не все множители при вторых производных являются линейными. Поэтому использовался другой подход к нахождению стоимости опциона .

Кафедра ИО Выписана приближенная модель, где множители при вторых производных в уравнении для стоимости линейны. Для этого, используя уравнение Фокера-Планка [4], была найдена функция плотности (t) и показано, что (t) имеет нецентральное хи-квадрат распределение, что позволило ввести p новый процесс u(t), который аппроксимирует (t) по первым двум моментам .

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

–  –  –

1. F. Black, M. Scholes. The Pricing of Options and Corporate Liabilities. J .

Political Economy, 81: 637-654, 1973 .

2. S.L. Heston. A Closed-Form Solution for Options with Stochastic Volatility

with Applications to Bond and Currency Options. Rev.Finan. Stud., 2(6):

327-343, 1993 .

3. J. Hull. Options, Futures, and Other Derivatives, Seventh Edition. Prentice Hall, 2008 .

4. К.В. Гардинер. Стохастические методы в естественных науках. 1986 .

5. L.A. Grzelak, C.W. Oosterlee, S. Weeren Ecient Option Pricing with Multi-Factor Equity-Interest Rate Hybrid Models. 2009 .

Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Принятие решений в условиях субъективной неопределенности Тропников Александр Вячеславович студент кафедры исследования операций email: alex.tropnikov@gmail.com научный руководитель профессор Новикова Наталья Михайловна Применение математических методов для принятия решений предполагает построение подходящей математической модели для формализации процедуры выбора решения. Необходимыми элементами такой модели является множество X всех альтернатив и описание структуры предпочтений лица, принимающего решения (ЛПР). Структура предпочтений ЛПР необходима для сравнения стратегий по предпочтительности. При этом сравнение стратегий происходит не непосредственно, а с помощью некоторого критерия эффективности. Таким образом, стремление ЛПР к достижению определенных целей математически означает стремление к увеличению (или уменьшению) величины критерия эффективности. В классической теории исследования операций предполагается наличие одной функции, характеризующей эффективность стратегий [1]. Однако не всегда ЛПР может заранее однозначно задать эту функцию, ему проще сначала указать несколько функций .

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

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

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

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

–  –  –

1. Ю. Б. Гермейер. Введение в теорию исследования операций. М.: Наука, 1971 .

2. В. В. Подиновский, Д. В. Ногин. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982 .

3. Н. М. Новикова, И. И. Поспелова. Многокритериальные задачи принятия решения в условиях неопределенности. М.: Вычислительный центр РАН, 2000 .

4. F. Ben Abdelaziz, P. Lang, R. Nadeau. Dominance and Eciency in Multicriteria Decision under Uncertainty. Rutcor Research Report, 1997 .

5. А. В. Лотов, И. И. Поспелова. Многокритериальные задачи принятия решений. М.: МАКС Пресс, 2008 .

Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Экстраградиентный метод решения многокритериальной задачи равновесного программирования Работа удостоена диплома II степени Артемьева Людмила Анатольевна студентка кафедры оптимального управления email: artemieva.Luda@gmail.com научные руководители д.ф.-м.н. Васильев Федор Павлович, д.ф.-м.н. Антипин Анатолий Сергеевич Дипломная работа посвящена разработке и исследованию методов решения многокритериальной задачи равновесного программирования [1–3]. В рассматриваемой задаче требуется найти точку u = (w,, p ) = m m

W0 E+ 2 E+ 3, удовлетворяющую следующим условиям:

–  –  –

1. А. С. Антипин. Многокритериальное равновесное программирование:

экстрапроксимальные методы // ЖВМиМФ, 2007, 47, №12, с. 1998– 2013 .

2. А. С. Антипин. Многокритериальное равновесное программирование .

Труды XIV байкальской школы-семинара Методы оптимизации и их приложения, 2008, т.

1 Математическое программирование, Иркутск:

ИСЭМ СО РАН, с. 22–47 .

3. Anatoly Antipin. Multicriteria equilibrium programming problems and methods for their solutions // Optimization, 2009, 58:7, 729–753 .

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

5. В. В. Подиновский, В. Д. Ногин. Парето–оптимальные решения многокритериальных задач. М.: Физматлит, 2007 .

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

М.: Издательский центр Академия, 2008 .

7. П. С. Краснощеков, В. В. Морозов, Н. М. Попов. Оптимизация в автоматизированном проектировании. М.: МАКС Пресс, 2008 .

8. Ф. П. Васильев. Методы оптимизации. М.: Факториал Пресс, 2002 .

9. А. Н. Тихонов, В. Я. Арсенин. Методы решения некорректных задач .

М.: Наука, 1979 .

10. А. Н. Тихонов, А. С. Леонов, А. Г. Ягола. Нелинейные некорректные задачи. М.: Наука, 1995 .

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

11. А. Б. Бакушинский, А. В. Гончарский. Итеративные методы решения некорректных задач. М.: Наука, 1989 .

Численные методы построения множеств достижимости для нелинейных управляемых систем Жуковская Ирина Станиславовна студент кафедры оптимального управления email: irina.msu@mail.ru научный руководитель доцент Киселёв Юрий Николаевич В дипломной работе рассматривается задача построения множеств достижимости нелинейных двумерных управляемых систем численными методами на основе пиксельного подхода. Наряду с традиционным способом выбора пикселей в форме квадратов изучена версия пиксельного метода, в которой в роли элементарных ячеек используются правильные шестиугольники. На основе разработанных алгоритмов написана программа в среде Maple (Maple 11) для приближённого построения множеств достижимости X(T ) в заданный момент времени T 0 для двумерных нелинейных управляемых систем x R2, u U, x(0) X0, t [0, T ], x = f (x, u, t), где t время, x фазовая переменная, u управление, U область управления, X0 начальное множество, f двумерная нелинейная векторная функция. Множества U, X0 предполагаются компактами и задаются неравенствами. Для решения предусмотренных алгоритмом задач Коши пользователь может выбрать численный метод решения .

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

Отметим некоторые характеристики программы: программа имеет дружественный интерфейс, в программе присутствует справочник (Help), имеется библиотека примеров, кроме того, программа позволяет решать задачу построения множеств достижимости с учётом фазовых ограничений x F, в которых множество F R2 описывается системой неравенств .

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

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

–  –  –

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

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

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

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

Серия Вычисл. матем. и кибернетика. 1987. Т. 4. c. 31-34 .

4. Спесивцев Л. В., Ушаков В. Н. Задача о приведении движения управляемой системы в окрестность заданной точки множества достижимости. // Вестник Удмуртского университета. Cерия математика .

2006. №1. c. 111- 126 .

5. Ю. Н. Киселёв, С. Н. Аввакумов, М. В. Орлов. Построение в аналитической форме оптимального решения и множеств достижимости в одной задаче распределения ресурсов. // Прикладная математика и информатика. №27, M., МАКС Пресс 2007. с. 80-99

6. Ю. Н. Киселёв. Оптимальное управление. Москва: Издательство Московского университета, 1988 .

7. Ю. Н. Киселёв, С. Н. Аввакумов, М. В. Орлов. Оптимальное управление. Линейная теория и приложения. Москва: Издательство Московского университета, 2007 .

8. Винников Е. В. Численное построение множества достижимости нелинейных управляемых систем. // Обозрение прикладной и промышленной математики, т. 5, 2009, c. 824

–  –  –

Задача оптимального управления взаимодействия предприятия и государства в экологической и экономической сферах Харитонова Елена Игоревна студентка кафедры оптимального управления email: kharitonovalena@gmail.com научный руководитель к.ф.-м.н., доц. Хайлов Евгений Николаевич .

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

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

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

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

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

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

Литература

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

2. Cabo F., Escudero E., Martin-Herran G. A time-consistent agreement in an interregional dierential game on pollution and trade. World Scientic Publishing Company, 2006 .

3. Chimeli A., Braden J. Economic Growth and the Dynamics of Environmental Quality. Journal of Environmental Economics and Management, 2004 .

4. Ашманов С.А., Математические модели и методы в экономике. Издательство Московского Университета, 1980 .

–  –  –

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

Функционал полезности может быть преобразован к следующему виду:

n Z X et [i ( + i )xi (t) + Ei (x(t))]dt min, J(x) = i=1 где – параметр дисконтирования ( равно предполагаемому сроку жизни инфраструктуры) .

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

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

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

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

Литература

1. С.Н. Аввакумов Гладкая аппроксимация выпуклых компактов. Труды ИММ. 1995 Т.4 .

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

3. Р. Беллман Динамическое программирование. М.: Изд-во иностранной литературы, 1960 .

4. Ю.Б. Гермейер Введение в теорию исследования операций. М.: Наука, 1971 .

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

6. Ramsey F.P. A mathematical theory of saving Economic Journal, vol. 38, no. 152, December 1928

7. Lensink S.M. Modication of road networks to reduce the energy use of the transport sector. IIASA Interim Rept.IR-07-020, Laxenburg(Austria), 2007 .

Решение одномерного уравнения Шредингера методом функций Грина Овсянникова Екатерина Владимировна студентка кафедры оптимального управления email: katovs88@mail.ru научный руководитель к.ф.-м.н. Мельников Николай Борисович Цель работы применить метод функций Грина для решения уравнения Шредингера с периодическим потенциалом, описанный в статье [5] для трехмерного случая, к одномерному случаю .

Решается одномерное операторное уравнение Шредингера вида:

–  –  –

2. А. И. Ансельм. Введение в теорию полупроводников. М:Наука, 1978 .

3. Bruuns, Flensberg. Introduction to many-body quantum theory in condensed matter physics. Oxford Univ.Press, Oxford, 2004 .

4. Economou. Green’s functions in quantum physics. Springer-Verlag, Berlin, 2006 .

5. W. Kohn, N. Rostoker. Solutions of the Schrodinger Equation in Periodic Lattices with an Application to Metallic Lithium. Carnegie Institute of Technology, Pittsburgh, Pennsylvania, 1953 .

6. Н. Ашкрофт, Н. Мермин. Физика твердого тела. М.1979 .

Модели ценообразования для производных финансовых инструментов на процентные ставки Андреев Николай Анатольевич студент кафедры системного анализа email: nick.my.mail@gmail.com научный руководитель к.ф.-м.н. Смирнов Сергей Николаевич Срочная структура процентных ставок (временная стоимость денег) является одним из главных макроэкономических показателей финансового рынка Кафедра СА и находит широкое применение при оценке долговых инструментов. Дипломная работа посвящена исследованию одной из методик расчета срочной структуры для инструментов на плавающие процентные ставки с целью получить статическую характеристику состояния рынка .

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

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

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

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

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

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

–  –  –

1. Шарп У. Ф., Александер Г. Дж., Бэйли Дж. В. Инвестиции. М.:

ИНФРА-М, 2001 .

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

2. Adams K. J., Van Deventer D. Fitting Yield Curves and Forward Rate Curves with Maximum Smoothness. Bank of England, 1994 .

3. Borgy J. -F. The Ibor Battle exacerbates. Natixis, 29 May 2008 .

4. Smirnov S., Zakharov A. A Liquidity-Based Robust Spline Fitting of Spot Yield Curve Providing Positive Forward Rates. EFFAS -EBC working paper, 2003 (www.eas-ebc.com) .

Математическое моделирование потоков автотранспорта Работа удостоена диплома III степени Дорогуш Елена Геннадьевна студентка кафедры системного анализа email: dorogush@gmail.com научный руководитель академик А. Б. Куржанский Рассматривается задача моделирования и управления транспортным потоком на кольцевой автостраде .

Исследуется модель изменения состояния автомагистрали CTM (the cell transmission model, клеточная передаточная модель) дискретизация по Годунову гидродинамической модели, предложенной в статье [1]. Дорога представляет собою взаимодействующие ячейки-клетки .

Основные вопросы следующие. Отыскание множества положений равновесия системы при постоянном входящем потоке. Выяснение условий устойчивости положений равновесия. Характеристика поведения траекторий системы .

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

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

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

Литература

1. M. J. Lighthill, G. B. Whitham. On Kinematic Waves. I: Flood Movement in Long Rivers. II: A Theory of Trac Flow on Long Crowded Roads. Proceedings of the Royal Society of London, 1955, Series A., Vol. 229, № 1178, pp. 281–345 .

Кафедра СА

2. C. F. Daganzo. The cell transmission model: A dynamic representation of highway trac consistent with the hydrodynamic theory. Transpn. Res.-B, 1994, Vol. 28B, № 4, pp. 269–287 .

3. C. F. Daganzo. The cell transmission model, part II: Network trac .

Transpn. Res.-B., 1995, Vol. 29B, № 2, pp. 79–93 .

4. Alex A. Kurzhanskiy. Modeling and Software Tools for Freeway Operational Planning. EECS Department, University of California, Berkeley, 2007 .

http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-148.html

5. Gabriel Gomes, Roberto Horowitz, Alex A. Kurzhanskiy, Pravin Varaiya, Jaimyoung Kwon. Behavior of the cell transmission model and eectiveness of ramp metering. Transpn. Res.-C, 2007, Vol. 16, pp. 485–513 .

6. Gabriel Gomes, Roberto Horowitz. Optimal freeway ramp metering using the asymmetric cell transmission model. Transpn. Res.-C, 2006, Vol. 14, pp. 244–262 .

Моделирование роста сосудистой раковой опухоли методом гибридных клеточных автоматов Запольский Кирилл Максимович студент кафедры системного анализа email: kzapolski@gmail.com научный руководитель д.ф.-м.н. проф. Братусь Александр Сергеевич Работа посвящена построению и описанию детальной модели развития раковых популяций в тканях живого организма. Введение, первая и вторая глава диплома детально овещают проблемы и недостатки существующих подходов, отмечаются наиболее важные моменты рассматриваемых процессов, а также в сжатом виде вводят необходимые биологические основы работы .

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

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

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

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

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

Литература

1. P. Gerlee, A. R. A. Anderson. A hybrid cellular automaton model of clonal evolution in cancer: The emergence of the glycolytic phenotype. Journal of Theoretical Biology, 205 (2008) .

2. A. R. A. Anderson, M. A. J. Chaplain. Continuous and discrete mathematical models of tumor-induced angiogenesis. Bulletin of Mathematical Biology, Springer, New York, 1998 .

–  –  –

где f (u) выпуклая или удовлетворяющая энтропийным условиям функция и u+ u. Для решения u(x, t) задачи (1) изучается асимптотика вида бегущей волны u = (x t), lim (s) = u± .

s± Кафедра СА Данная задача для f (u) = u исследована в работах П.И. Наумкина, И.А .

Шишмарева ([1], [2]). При выполнении условия

–  –  –

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

В некоторых моделях транспортных потоков, а также экономических моделях, например, модели Полтеровича–Хенкина распространения новых технологий, возникает потребность в исследовании решения задачи (1) с функцией f (u), отличной от u2. В данной работе проведено обобщение условия (2) на случай произвольной выпуклой f (u). Именно, при помощи метода интегральных оценок, предложенного в [1], показано, что при выполнении условия

–  –  –

бегущая волна для уравнения КдФБ существует, является монотонной и локально устойчивой. Кроме того, в работе продемонстрировано, что результат о локальной устойчивости немонотонной бегущей волны, известный для квадратичной функции потока ([2]), также обобщается на случай произвольной выпуклой f (u) .

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

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

Литература

1. Наумкин П. И., Шишмарев И. А. Задача о распаде ступеньки для уравнения Кортевега–де Фриза–Бюргерса // Функц. анализ и его прил. 1991 .

25. № 1. С. 21–32 .

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

2. Наумкин П. И., Шишмарев И. А. О распаде ступеньки для уравнения Кортевега де Фриза Бюргерса // Функц. анализ и его прил. 1991. 26 .

№ 2. С. 88–93 .

–  –  –

p2 p4 C = W 1, C1 = p0 u0, K1 = p2 .

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

Литература

1. Петров В. В.,Поляков Г. А., Полякова Т. В., Сергеев В. М. Долгосрочные перспективы российской нефти (анализ, тренды, сценарии). М.:

ФАЗИС, 2003 .

2. Вяхирев Р. И., Коротаев Ю. П. Теория и опыт разработки месторождений природных газов. М.: ФАЗИС, 2003 .

3. Форест Грей. Добыча нефти. Олимп-Бизнес, 2007 .

4. Э. Б. Ли, Л. Маркус Основы теориии оптимального управления. М.:

Наука, 1972 .

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

Разработка и анализ методов аппроксимации оболочки Эджворта–Парето для выпуклых задач многокритериальной оптимизации Майская Татьяна Сергеевна студентка кафедры системного анализа email: prividenize@mail.ru научный руководитель д.ф.-м.н., проф. Лотов Александр Владимирович Дипломная работа посвящена изучению новых неадаптивных методов аппроксимации оболочки Эджворта–Парето (ОЭП), перенесенных из теории полиэдральной аппроксимации выпуклых компактных тел (ВКТ) на основе измерения опорной функции. Хотя долгое время для решения задачи аппроксимации ВКТ (и их ОЭП) успешно применялся адаптивный метод Уточнения Оценок (УО), показавший свою высокую эффективность по сравнению с неадаптивными алгоритмами, в последнее время появился новый интерес к неадаптивным методам. Это связано с развитием сети Internet и активным использованием параллельных алгоритмов, что поставило под вопрос преимущество адаптивного подхода перед неадаптивным. Поэтому большое значение приобретает разработка неадаптивных методов аппроксимации ОЭП .

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

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

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

Литература

1. А. В. Лотов, И. И. Поспелова. Многокритериальные задачи принятия решений. М.: МАКС Пресс, 2008 .

2. Г. К. Каменев. Оптимальные адаптивные методы полиэдральной аппроксимации выпуклых тел. М.: ВЦ РАН, 2007 .

–  –  –

Здесь коэффициенты-матрицы A(t), B(t) и C(t) непрерывны, x(t) Rn фазовый вектор системы, u Rp управление, v(t) Rq неизвестное но ограниченное возмущение (помеха), v(t) Q(t), t0 t t1, где Q(t) непрерывное по Хаусдорфу, выпуклое и компактнозначное многозначное отображение .

На управление имеется ограничение, аналогичное предыдущему u(t) P(t), t0 t t1, где P(t) непрерывное по Хаусдорфу, выпуклое и компактнозначное многозначное отображение. В задачах с помехой целесообразно рассматривать синтезированные управления, зависящие не только от времени t, но и от фазового вектора x .

Для задачи синтеза целевого управления u(t, x) P(t), x, t0 t t1, направленного на достижение терминального множества M при неопределённых возмущениях, полезно следующее понятие .

Множеством разрешимости задачи целевого управления в момент t0, в классе синтезирующих управлений u(t, x), называют совокупность таких векторов, x0, для которых существует управление u(t, x), переводящее систему из Кафедра СА позиции {t0, x }, в позицию {, x}, x M, каким бы ни было неопределённое возмущение v(t) .

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

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

В работе в данном направлении получены некоторые результаты .

Литература

1. A. B. Kurzhanski and I. Valyi. Ellipsoidal Calculus for Estimation and Control, Birkhauser, Boston, 1997 .

2. A. B. Kurzhanski, P. Varaiya. Reachability Analysis for Uncertain Systems the Ellipsoidal Technique, Journal of Dynamics of Continuous, Discrete and Impulsive Systems, Ser. B., v. 9, № 3, 2002, pp. 347–367 .

3. A. A. Kurzhanskiy and P. Varaiya. Ellipsoidal Toolbox manual, 2006-2008 .

4. Половинкин Е. С., Балашов М. В. Элементы выпуклого и сильно выпуклого анализа. М.: ФИЗМАТЛИТ, 2004 .

5. Rolf Schneider. Convex bodies: the Brunn-Minkowski theory, Cambridge University Press, Cambridge, 1993 .

Анализ задачи о квазивидах Эйгена Юрьев Александр Юрьевич студент кафедры системного анализа email: alexander.yuriev@gmail.com научные руководители д.ф.-м.н. проф. Братусь Александр Сергеевич, к.ф.-м.н. Новожилов Артём Сергеевич Работа посвящена построению эффективных алгоритмов моделирования динамики системы квазивидов. Введение и первая глава содержат краткую Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года историческую справку, а также в сжатой форме показывают основные идеи и построения, приводящие к соответствующей системе дифференциальных уравнений .

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

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

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

Литература

1. E. Baake, G. Wilfried. Biological evolution through mutation, selection, and drift: An introductory review. Annu. Rev. Comput. Phys. VII, 203– 264 (2000) .

2. D. B. Saakian, O. Rozanova, A. Akmetzhanov. Dynamics of the Eigen and the Crow-Kimura models for molecular evolution. Phys. Rev. E 78, 041908 (2008) .

–  –  –

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

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

1. Г. Вейль, “О равномерном распределении чисел по модулю 1”, в кн.:

Г. Вейль, Избранные труды, Наука, Москва, 1984 .

2. А. Пуанкаре, Теория вероятностей, Регулярная и хаотическая динамика, Ижевск, 1999 .

3. В. Феллер, Введение в теорию вероятностей и ее приложения, т. II, Мир, Москва, 1984 .

4. Н. И. Ахиезер, Лекции по теории аппроксимации, ГИТТЛ, Москва, 1947 .

5. Г. М. Фихтенгольц, Курс дифференциального и интегрального исчисления, т. II, Наука, Москва, 1969 .

6. S. Bochner, Harmonic Analysis and the Theory of Probability, Univ. of Calif .

Press, Berkeley, 1955 .

7. И. М. Виноградов, Метод тригонометрических сумм в теории чисел, Наука, Москва, 1971 .

8. A. Dvoretzky, J. Wolfowitz, “Sums of rundom integers reduced modulo m”, Duke Math. J., 18, (1951), 501–507 .

9. А. Н. Ширяев, Вероятность, Наука, Москва, 1989 .

Исследование систем массового обслуживания с параметрами авторегрессионного типа Работа удостоена диплома II степени Леонтьев Николай Дмитриевич студент кафедры математической статистики email: nicholas@newmail.ru научный руководитель д.ф.-м.н., проф. Ушаков Владимир Георгиевич Дипломная работа посвящена исследованию систем обслуживания, параметры которых задаются при помощи авторегрессионных моделей временных рядов. Авторегрессионные модели позволяют достаточно точно передавать корреляционную структуру данных, сохряняя при этом относительную простоту, что делает их удобным инструментом описания реальных процессов, возникающих в телекоммуникационных сетях .

В качестве основного средства передачи корреляционной связи использована модель дискретной авторегрессии первого порядка. Мы говорим, что Кафедра МС последовательность случайных величин {An }n0 подчинена модели дискретной авторегрессии первого порядка, если выполняется уравнение регрессии

A0 = B0, An+1 = (1 n )An + n Bn+1, n 0 .

Здесь {Bn }n0 последовательность независимых одинаково распределённых случайных величин, {n }n0 последовательность независимых бернуллиевских случайных величин с параметром p .

Основная часть работы состоит из двух разделов .

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

распределения длины очереди, времени пребывания и времени ожидания требования в системе. Также рассмотрена задача нахождения нестационарных характеристик .

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

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

Литература

1. А. А. Боровков. Курс теории вероятностей. М.: Наука, 1972, 288 с .

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

3. В. Г. Ушаков, И. Г. Харитонцева. О системе с зависимыми временами обслуживания.- Математическое моделирование и цифровая обработка информации. 1990, 154-163

4. B. D. Choi, B. Kim, G. U. Hwang and J. Kim. The analysis of a multiserver queue fed by a discrete autoregressive process of order 1.- Operations Research Letters. vol. 32, 2004, 85-93

5. G. U. Hwang, K. Sohraby. On the exact analysis of a discrete-time queueing system with autoregressive inputs.- Queueing Systems. vol. 43, 2003, 29-41

6. F. Kamoun. The discrete-time queue with autoregressive inputs revisited.Queueing systems. vol. 54, 2006, 185-192 Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года

7. J. Kim, B. Kim. Regularly varying tails in a queue with discrete autoregressive arrivals of order p.- Queueing systems. vol. 56, 2007, 93-102

8. V. G. Kulkarni. Modeling and analysis of stochastic systems. Chapman & Hall, 1995

9. M. F. Neuts Structured stochastic matrices of the M|G|1 type and their applications. Dekker, New York, 1989

10. D. W. Stroock. An introduction to Markov processes. Springer, 2005

11. L. Takacs. A single-server queue with feedback.- Bell system Technical Journal. vol. 42, 1963, 509-519 Усиленный закон больших чисел для случайных процессов Работа удостоена диплома I степени Наумов Алексей Александрович студент кафедры математической статистики email: naumovne@gmail.com научный руководитель д.ф.-м.н. Ульянов Владимир Васильевич Целью дипломной работы является доказательство аналогов усиленных законов больших чисел Колмогорова и Брунка–Прохорова для мартингалов с непрерывным параметром. Естественно предположить, что известные усиленные законы больших чисел для сумм независимых случайных величин могут быть обобщены на случай однородных случайных процессов с независимыми приращениями. В работе доказан аналог усиленного закона больших чисел Марцинкевича–Зигмунда. Точные формулировки классических утверждений можно найти в [1] .

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

В частности, оно выполняется в условиях оригинальной теоремы Брунка– Прохорова .

Теорема 1. Пусть даны измеримый сепарабельный мартингал {Mt, t R+ } относительно некоторой фильтрации {Ft, t R+ } и неограниченно возрастающая положительная функция f (t), t 0 .

Если dE|Mt | Z f (t) Кафедра МС

1. Y. Chow, H. Teicher. Probability Theory. Independence, Interchangeability, Martingales. Spinger–Verlag, 1988 .

2. I. Fazekas, O. Klesov. A general approach to the strong law of large numbers .

Теория вероятн. и ее примен. 2000. 45. № 3. C.568–583 .

3. В. М. Круглов. Обобщение усиленного закона больших чисел Брунка– Прохорова. Теория вероятн. и ее примен. 2002. 47. № 2. C.347–349 .

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

Есеналина Акмарал Ускеменовна студентка кафедры математической статистики email: ako1988@mail.ru научный руководитель д.ф.-м.н. Ульянов Владимир Васильевич Рассматривается теоретическая погрешность для асимптотического разложения распределения статистики

T = n log,

где = |Se |/|Se + P |, и Se и Sh независимы и имеют распределения Уишарта Sh P Wp (q, ) и Wp (n, ), соответственно. Таким образом, имеет распределение Уилкса p,q,n .

Основой работы послужила статья [1], в которой распределение статистики Т при n приближается 2 распределением с r = pq степенями свободы.

В ней представлены в явном виде оценки погрешностей для двух асимптотических аппроксимаций P (T x):

r (q p 1){Gr (x) Gr+2 (x)} Gr (x) и Gr (x) + 4n где Gr (x) функция распределения 2 распределения с r степенями свободы .

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

Теорема 1. Пусть T статистика, определенная выше при p = 1, т .

е .

–  –  –

3 50 0.2014 0.3298 0.2140 0.3131 75 0.1251 0.2082 0.0888 0.1146 120 0.0750 0.1253 0.0333 0.0394

–  –  –

3 120 0.1762 0.2768 0.0666 0.1044 200 0.1038 0.1626 0.0227 0.0352 4 120 0.2230 0.3923 0.0976 0.2165 200 0.1298 0.2269 0.0316 0.0709

–  –  –

1. Y. Fujikoshi, V. V. Ulyanov. Error bounds for asymptotic expansions of Wilks’ lambda distribution. J. Multivariate Anal.97(2006)1941–1957 .

Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Методы восстановления пространственного изображения и оценка их точности Работа удостоена диплома II степени Гордеев Дмитрий Вячеславович студент кафедры математических методов прогнозирования email: dott1718@gmail.com научный руководитель д.т.н., проф. Местецкий Леонид Моисеевич В работе рассматривается задача восстановления пространственного изображения объекта - трехмерной поверхности, описывающей его форму. Современные системы машинного зрения решают эту задачу, однако различные решения сильно отличаются как качеством получаемых поверхностей, так и стоимостью их получения. Для обоснования выбора системы получения трехмерного изображения применительно к конкретной прикладной задаче необходимо иметь объективную оценку точности пространственных изображений, получаемых каждым из способов. Получение таких оценок аналитическим путем, как правило, представляет собой весьма затруднительную задачу в силу сложности используемой аппаратуры и применяемых алгоритмов. Поэтому большое значение имеют экспериментальные оценки точности методов .

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

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

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

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

Все разработанные методы и алгоритмы реализованы в виде макета программной системы, обеспечивающей ввод данных, обработку и визуализацию результатов, проведение вычислительных экспериментов. Результаты исследования представлены в двух докладах на всероссийской конференции ММРО-14 [3] и международной конференции Графикон-2009 [2]. Статьи по Кафедра ММП этим исследованиям опубликованы в сборниках трудов конференций. Также результаты дипломной работы нашли применение в исследовательском проекте, выполняемом в рамках совместной программы РФФИ и Министерства науки Индии Пространственное моделирование человеческих лиц для анализа и классификации в реальном времени. Тема работы непосредственно связана с этим исследованием .

Литература

1. Дышкант Н.Ф. Метод сравнения формы пространственных изображений дипломная работа, ВМК МГУ. Москва, 2008 .

2. Гордеев Д.В., Дышкант Н.Ф. Построение модели динамики движения челюсти человека в процессе жевания по серии трехмерных изображений Доклады международной конференции ГрафиКон’09 по компьютерной графике. Москва, 2009 .

3. Гордеев Д.В., Дышкант Н.Ф. Сегментация модели лица на статические и динамические области по трехмерной видеопоследовательности Доклады конференции ММРО-14. Москва, 2009 .

4. Форсайт Д., Понс Ж. Компьютерное зрение. Современный подход Вильямс. Москва, 2004 .

Склейка скелетов смежных многоугольных фигур Задонский Дмитрий Алексеевич студент кафедры математических методов прогнозирования email: zadonskyd@yandex.ru научный руководитель д.т.н. Местецкий Леонид Моисеевич Дипломная работа посвящена задаче скелетизации сложных многоугольных фигур. Источником такой задачи служит геоинформационная система (ГИС). ГИС работает с базой данных пространственных площадных объектов. Площадные объекты на карте представляют собой многоугольные фигуры (возможно, многосвязные). В данной работе рассматривается уличнодорожная сеть города Москвы. Для некоторых задач, которые требуется решать с помощью ГИС, таких как маршрутизация по дорожной сети или анализ для моделирования строительства новых дорог, такого представления недостаточно. Поэтому требуется построить новое представление - графовую модель улично-дорожной сети. Такая модель может быть построена на основе серединных линий объектов - их скелетов. В работе показан подход, позволяющий построить серединные линии всей сети .

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

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

1. Поиск линии склейки многоугольных фигур

2. Очистка диаграмм Вороного

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

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

–  –  –

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

2. Ivan Mekhedov Leonid Mestetskiy Skeleton of a Multi-ribbon Surface .

International Conference on Computational Science and Its Applications,

3. Михедов И.С. Козлов А.В Модель улично-дорожной сети на основе скелета. Труды 19-й международной конференции Графикон 2009 .

4. Местецкий Л.М Рейер И.А Непрерывное скелетное представление изображение с контролируемой точностью. Труды 13-й международной конференции Графикон 2003 .

Кафедра ММП

5. Михедов И.С Поиск шаблонов перекрестков на векторной карте городской улично-дорожной сети. Труды международной конференции ММРО-2009 .

6. www.mappl.ru

7. www.egko.ru Автоматизация анализа изображений срезов мозга экспериментальных животных для наполнения модели болезни Паркинсона Мягков Артём Александрович студент кафедры математических методов прогнозирования email: artem.myagkov@gmail.com научный руководитель к.ф.-м.н. Гуревич Игорь Борисович Данная работа посвящена постановке и решению математимческих задач, возникающих в связи с автоматизацией анализа изображений. Основным результатом работы является метод, обеспечивающий автоматизацию анализа изображений, содержащих малые объекты неправильной формы, расположенные на неоднородном фоне. Разработанный метод был интерпретирован на примере анализа изображений серийных срезов мозга экспериментальных животных [2], используемых для построения и исследования имитационных преклинических моделей болезни Паркинсона (БП) .

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

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

Такие схемы включают основные этапы извлечения информации из изображений: (1) предварительную обработку; (2) анализ изображений; (3) построение описания объектов, представленных на анализируемых изображениях;

(4) классификацию изображений и объектов на них представленных; (5) распознавание .

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

(г) вычислять характеристики выделенных объектов .

Разработанный метод основан на операциях математической морфологии [4] и включает 7 этапов: 1. открытие изображения с помощью реконструкции; 2. преобразование “дно шляпы” с помощью двойственной реконструкции;

3. закрытие изображения с помощью двойственной реконструкции; 4. преобразование, устраняющее h-максимумы изображения; 5. выделение внутренних и внешних маркеров объектов; 6. преобразование морфологического градиента по найденным маркерам, с помощью двойственной реконструкции; 7 .

выделение объектов с помощью алгоритма сегментации по водоразделам .

Разработанный метод программно реализован и используются при выполнении НИР в Учреждении Российской Академии Наук “Институт биологии развития им. Н. К. Кольцова РАН” .

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

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

Литература

1. Ю. И. Журавлев, И. Б. Гуревич. Распознавание образов и распознавание изображений // Распознавание, классификация, прогноз. Математические методы и их применение: Ежегодник. 1989. Т. 2. Стр. 5–72 .

Под ред. Ю. И. Журавлева .

2. I. Gurevich, E. Kozina, A. Myagkov, M. Ugrumov, and V. Yashina .

Automatic Mining and Analysis of Dopaminergic Neuron Terminals on Striatum Frontal Section Images // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. - Pleiades Publishing, Ltd. 2010. Vol.20. No.3 .

3. I. B. Gurevich, V. V. Yashina, I. V. Koryabkina, H. Niemann, O. Salvetti .

Descriptive approach to medical image mining: An algorithmic scheme for analysis of cytological specimens // Pattern Recognition and Image Кафедра ММП Analysis: Advances in Mathematical Theory and Applications. 2008 .

Vol. 18, no. 4. Pp. 542–562 .

4. P. Soille Morphological Image Analysis: Principles and Applications .

Berlin: Springer, 2004 .

Разработка методов построения трехмерной модели мозга мыши и вписывания в нее экспериментальных данных Работа удостоена диплома I степени Осокин Антон Александрович студент кафедры математических методов прогнозирования email: anton.osokin@gmail.com научный руководитель к.ф.-м.н. Ветров Дмитрий Петрович По современным научным представлениям когнитивные процессы в мозге определяются экспрессией генов. Анализ экспрессии генов является перспективным направлением, позволяющим приоткрыть тайны работы мозга .

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



Pages:   || 2 | 3 |



Похожие работы:

«Fen Bilimleri Dergisi Say: 9 2008 КОНВЕРСИЯ ОКСИДА УГЛЕРОДА ВОДОЙ И РАСЧЕТ РАВНОВЕСНОГО СОСТАВА ГАЗОВОЙ И КОНДЕНСИРОВАННЫХ ФАЗ Маймеков З.К. Кыргызско-Турецкий университет "Манас", Инженер...»

«Вопросы к зачету по курсу: "Биотический круговорот"1. Понятие биотического и биогеохимического круговоротов. Функциональные элементы экосистемы: первичные продуценты, консументы и редуценты.2....»

«МИНИСТЕРСТ В О ПРИ РОДНЫХ РЕ СУРСОВ РОССИ ЙСКО Й ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ АГЕНТСТВ О ПО НЕДРОПОЛЬЗО В АНИЮ СИБИРСКИЙ НАУЧН О-ИССЛЕДОВ АТЕЛЬСКИЙ ИНСТИТУТ ГЕОЛОГИИ, ГЕОФИЗИКИ И МИНЕРАЛЬНОГО СЫР ЬЯ 50-летuю СНИИГГuМСа посвящается А. э. Канторович ГЕОlIОГИЯ НЕФТИ И ГАЗА Избранные...»

«Нохрин Алексей Владимирович ЭКСПЕРИМЕНТАЛЬНЫЕ И ТЕОРЕТИЧЕСКИЕ ИССЛЕДОВАНИЯ ЭВОЛЮЦИИ СТРУКТУРЫ СУБМИКРОКРИСТАЛЛИЧЕСКИХ МЕТАЛЛОВ, ПОЛУЧЕННЫХ МЕТОДОМ ИНТЕНСИВНОГО ПЛАСТИЧЕСКОГ...»

«39 УДК 1 (091) "980/1037" : 161/162 М. Джаббехдари, Е. Н. Лисанюк Роль математических примеров в логическом учении Ибн-Сины В статье обосновывается положение о том, что математические примеры в логике Ибн-Сины не только служат иллюстрацие...»

«Известия высших учебных заведений. Поволжский регион ХИМИЯ УДК 544.7 : 54.058 DOI: 10.21685/2307-9150-2016-2-4 Н. Г. Вилкова ВЛИЯНИЕ СВОЙСТВ ПЕН И ПЕННЫХ ПЛЕНОК НА ФЛОТАЦИОННОЕ ВЫДЕЛЕНИЕ ОРГАНИЧЕСКОЙ ЖИДКОСТИ Аннотация. Актуальность и цели. Флотация представляет собой про...»

«Воронаев И.Г. Л/I. 6 часов + 3 часа практика Тема: Качественный химический анализ катионов и анионов План лекции: 1. Введение. Основные понятия 2. Схемы деления катионов на группы 3. Кислотно-основная схема разделения катион...»

«Биоорганическая химия, №1, 2014 УДК 577.112.6.017 АНТИОКСИДАНТНАЯ И ДЕТОКСИЦИРУЮЩАЯ АКТИВНОСТЬ АНАЛОГОВ ПЕПТИДА ДЕЛЬТА-СНА © 2013 г. И. И. Михалева* #, В. Т. Иванов*, Л . В. Оноприенко*, И. А. Прудченко*, Л...»

«МЕЖДУНАРОДНЫЙ НАУЧНЫЙ ЖУРНАЛ "СИМВОЛ НАУКИ" №6/2016 ISSN 2410-700Х Для освоения логического приема сравнения детям необходимо на занятиях по языку выделять свойства предметов, находить предметы схожие и различные по внеш...»

«1986 г. Октябрь Том 150, вып. 2 УСПЕХИ ФИЗИЧЕСКИХ ИAYК 524.354.6 ФИЗИКА МАГНИТОСФЕРЫ ПУЛЬСАРА В. С. Веский, А. В. Гуревич, Я. И . Истомин СОДЕРЖАНИЕ 1. Пульсары. Основные наблюдательные характеристики 257 1.1. Периоды пульсаров 258 1.2. Средний профиль 259 1.3. Поляризация 259 1.4. Энергетика пульсаров 260...»

«УДК 544.015.4+538.958 СТРУКТУРНЫЕ И ОПТИЧЕСКИЕ ХАРАКТЕРИСТИКИ КОМПОЗИТОВ ПИРОГЕННЫЙ КРЕМНЕЗЕМ /, -Zn2SiO4:Mn Е.И. Оранская, В.М. Богатырев, А.В. Бричка, С.Я . Бричка, Ю.И. Горников Институт химии поверх...»

«Вестник ВГУИТ, №1, 2014 УДК 66-936.42 Профессор С.Ю. Панов, аспирант М. Химвинга, соискатель А.В. Зинковский (Воронеж. гос. ун-т. инж. технол.) кафедра машин и аппаратов химических производств. тел. (473) 249-91-13 E-mail: sergey.panov@mail.ru, kafedra-mahp@mail.ru Professor S.Iu. Panov, graduate M. Himwiinga, applicant A.V. Zinkovskii (Voron...»

«ЖУРНАЛ СТРУКТУРНОЙ ХИМИИ 2003, Том 44, № 1 Январь – февраль С. 155 – 161 УДК 541.123.22+541.12.034 ВЛИЯНИЕ ДАВЛЕНИЯ НА КЛАТРАТООБРАЗОВАНИЕ В СИСТЕМЕ ВОДА—ЭТАНОЛ © 2003 Ю.М. Зеленин* Институт неорганической химии им. А.В. Николаева СО РАН, Новосибирск Статья поступила 5 июня 2002 г. Си...»

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

«СТРУКТУРА ВЕЩЕСТВА И ТЕОРИЯ ХИМИЧЕСКИХ ПРОЦЕССОВ УДК 544.77.022.532:534-1:543.632.9 Р. Ф. Бакеева, О. Е. Вахитова, Л. М. Юсупова, В. Ф. Сопин КИНЕТИКА РЕАКЦИИ 5,7–ДИХЛОР–4,6–ДИНИТРОБЕНЗОФУРОКСАНА С НОВОКАИНОМ В СРЕДЕ СМЕША...»

«ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ БИОФИЗИКИ СИБИРСКОГО ОТДЕЛЕНИЯ РОССИЙСКОЙ АКАДЕМИИ НАУК ТЕЗИСЫ КОНКУРСА-КОНФЕРЕНЦИИ МОЛОДЫХ УЧЁНЫХ И АСПИРАНТОВ 28 марта 2013 г. Красноярск ПРОГРАММА НАУЧНОЙ СЕССИИ МОЛОДЫХ УЧ...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего образования "МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ...»

«Министерство образования Российской Федерации ГОУ ВПО УГТУ-УПИ Кафедра физики ИНДИВИДУАЛЬНОЕ ДОМАШНЕЕ ЗАДАНИЕ ПО ФИЗИКЕ Тема: ЭЛЕКТРОСТАТИКА. ПОСТОЯННЫЙ ТОК МЕТОДИЧЕСКИЕ УКАЗАНИЯ И ЗАДАНИЯ АВТОРЫ: ПЛЕТНЕВА Е.Д. ВАТОЛИНА Н.Д. ЕКАТЕРИНБУРГ УДК 373.53 Рецензенты: к.ф.-м.н., доцент Волко...»

«89.АКТИНИЙ 89.0. Общие замечания Есть лишь одна причина, по которой элемент №89 – актиний – интересует сегодня многих. Этот элемент, подобно лантану, оказался родоначальником большого семейства элементов, в которое вход...»

«13. Фракталы Постановка задачи Фракталы Фракталами называют математические множества, обладающие свойством самоподобия: любая часть фрактала подобна всему фракталу целиком. Термин "фрактал" был введён Бенуа Ма...»

«Екимова Ирина Анатольевна ФИЗИКО-ХИМИЧЕСКИЕ СВОЙСТВА ПОВЕРХНОСТИ ОКСИДОВ И ФТОРИДОВ ЩЕЛОЧНОЗЕМЕЛЬНЫХ МЕТАЛЛОВ И СИСТЕМ НА ИХ ОСНОВЕ 02.00.04 – физическая химия АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата химических наук Томск – 2011 Работа выполнена на кафедре физической и коллоидной химии Томского государственного университет...»

«25 27-ДНЕВНЫЕ ВАРИАЦИИ ГЛОБАЛЬНОГО ЭЛЕКТРОННОГО СОДЕРЖАНИЯ ВО ВРЕМЯ 23-ГО ЦИКЛА СОЛНЕЧНОЙ АКТИВНОСТИ 27-DAY VARIATIONS OF GLOBAL ELECTRON CONTENT DURING 23rd CYCLE OF SOLAR ACTIVITY Э.Л. Афраймович1, Э.И. Астафьева1, И.В. Живетьев2, Ю.В. Ясюке...»

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

«Вестник ДВО РАН. 2011. № 2 УДК 582.734 О.Л.БЕРЕЗОВСКАЯ, Т.П.ОРЕХОВА Использование гистохимических методов для определения зимостойкости и сроков черенкования садовых роз и шиповников Гистохимическими методами определены зимостойкость и сроки черенкования 7 видов шиповник...»

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

«ХАЙРУЛЛИН Андрей Ранифович ДИЭЛЕКТРИЧЕСКИЕ СВОЙСТВА И СТРУКТУРА БАКТЕРИАЛЬНОЙ ЦЕЛЛЮЛОЗЫ GLUCONACETOBACTER XYLINUS И ЕЕ КОМПОЗИТОВ С УГЛЕРОДНЫМИ НАНОЧАСТИЦАМИ И ФОСФАТАМИ КАЛЬЦИЯ АВТОРЕФЕРАТ диссертации на соискани...»








 
2018 www.new.z-pdf.ru - «Библиотека бесплатных материалов - онлайн ресурсы»

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