WWW.DOC.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Различные документы
 

Pages:   || 2 | 3 | 4 |

«СБОРНИК ТЕЗИСОВ ЛУЧШИХ ВЫПУСКНЫХ РАБОТ ФАКУЛЬТЕТА ВМК МГУ 2015 года МОСКВА МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. ...»

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

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

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

Факультет

вычислительной математики

и кибернетики

СБОРНИК ТЕЗИСОВ

ЛУЧШИХ

ВЫПУСКНЫХ РАБОТ

ФАКУЛЬТЕТА ВМК МГУ

2015 года

МОСКВА

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

имени М.В. ЛОМОНОСОВА Факультет вычислительной математики и кибернетики

СБОРНИК ТЕЗИСОВ

ЛУЧШИХ

ВЫПУСКНЫХ РАБОТ

ФАКУЛЬТЕТА ВМК МГУ

2015 года МОСКВА – 2015 УДК 517.6 + 519.8 ББК 22 С23 Печатается по решению Редакционно-издательского совета факультета вычислительной математики и кибернетики МГУ имени М.В. Ломоносова

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

Е.И. МОИСЕЕВ, С.А. ЛОЖКИН, В.Н. ЛЫКОСОВ, М.В. УЛЬЯНОВ, А.Н. ТОМИЛИН, А.Н. СОТНИКОВ, А.В. ЧЕЧКИН, Н.М. НОВИКОВА, А.К. ПЕТРЕНКО, М.В. ФЕДОТОВ, И.Г. ШЕВЦОВА Сборник тезисов лучших выпускных работ факультета

С23 ВМК МГУ 2015 года/ Сост.: Капалин И.В., Шевцова И.Г. – М.:

Издательский отдел Факультета ВМиК МГУ им. М.В. Ломоносова (лицензия ИД N 05899 от 24.09.2001 г.); МАКС Пресс, 2015. – 312 с.



ISBN 978-5-89407-536-5 ISBN В настоящий сборник вошли тезисы выпускных квалификационных работ, дипломных работ и магистерских диссертаций, выполненных студентами факультета Вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова в 2015 году, представленные на конкурс лучших выпускных работ.

УДК 517.6 + 519.8 ББК 22 Издательский отдел Факультета вычислительной математики и кибернетики МГУ имени М.В. Ломоносова Лицензия ИД N 05899 от 24.09.01 г.

119992, ГСП-2, Москва, Ленинские горы, МГУ имени М.В. Ломоносова, 2-й учебный корпус Напечатано с готового оригинал-макета Формат 60х90 1/16.

Издательство ООО “МАКС Пресс” Лицензия ИД N 00510 от 01.12.99 г.

119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к.

Тел. 939-3890, 939-3891. Тел./Факс 939-3891.

© Капалин И.В., Шевцова И.Г., ISBN 978-5-89407-536-5 составление, оформление, 2015 ISBN © Издательский отдел факультета ВМК МГУ имени М.В. Ломоносова, 2015 Оглавление Отделение бакалавриата Кафедра математической физики Степанищева Виктория Сергеевна Исследование задач теплопроводности в случае полуограниченной среды.................................... 16 Петров Константин Игоревич Метод решения обратной задачи для нелинейного дифференциального уравнения с параметром...................... 18 Довганич Андрей Артурович Метод анализа изображений образцов ткани кожи.......... 19 Кафедра вычислительных технологий и моделирования Третьякова Руфина Максимовна Моделирование фармакокинетики и фармакодинамики противовирусных препаратов для задач управления динамикой ВИЧ-инфекции 22 Кафедра вычислительной математики Костоев Руслан Саламханович Разработка алгоритма численного решения стационарных уравнений гемодинамики............................ 24 Левин Александр Дмитриевич Моделирование конвекционно-диффузионных процессов в пористой среде................................. 25

–  –  –

Сторожева Анастасия Алексеевна Реконструкция трехмерной сцены по набору проекций....... 28 Кафедра нелинейных динамических систем и процессов управления Гришина Анна Павловна Синтез оптимального регулятора упрощенной модели вертикальной стабилизации плазмы в тороидальной камере с магнитными катушками в случае широтно-импульсной модуляции........ 30 Коромыслов Александр Юрьевич Разработка базовой станции для беспилотного летательного аппарата типа конвертоплан. Создание модуля состыковки беспилотных летательных аппаратов типа конвертоплан........... 31 Кафедра общей математики Ястребов Кирилл Сергеевич Сходимость и устойчивость некоторых аппроксимационных методов в метрических пространствах................... 33 Кафедра суперкомпьютеров и квантовой информатики Даугель-Дауге Артём Александрович Разработка и реализация интерактивного графического представления модели суперкомпьютерного комплекса............ 35 Кафедра исследования операций Христолюбова Екатерина Геннадьевна Оптимальное размещение объектов социальной инфраструктуры при планировании застройки...................... 37 Макарова Алёна Игоревна Минимизация затрат при крупных закупках на дискретном финансовом рынке.............................. 39 Шакенко Наталья Александровна Сравнительный анализ бонус-малус систем.............. 41 Тезисы выпускных работ факультета ВМК МГУ 2015 года Кафедра оптимального управления

–  –  –

Кафедра системного анализа Терёшин Владимир Сергеевич Задачи управления потоками транспорта на автостраде...... 45 Вартапетов Самвел Андреевич О некоторых свойствах метрики Хаусдорфа............. 47 Заночкин Андрей Юрьевич Устойчивые методы построения зависимостей: приложение к методу Смита—Уилсона............................ 49 Кафедра математических методов прогнозирования Дойков Никита Владимирович Адаптивная регуляризация вероятностных тематических моделей 51 Колмаков Евгений Александрович Метрический подход к модификации алгоритмов классификации на основе анализа формальных понятий................ 52 Подоприхин Дмитрий Александрович Распознавание паттернов в сигналах головного мозга........ 54 Родоманов Антон Олегович Разработка метода стохастической оптимизации для задач машинного обучения с большими данными.................. 56 Сендерович Никита Леонидович Автоматизация кодирования открытых вопросов.......... 58

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

Гордеев Михаил Михайлович О длине некоторых периодических функций пятизначной логики в классе поляризованных полиномиальных форм.......... 60 Оглавление Кухтинов Александр Сергеевич О тестовой сложности некоторого класса функций, реализованных схемами контактного типа........................ 62 Сальников Владимир Александрович О тестовой сложности реализованных схемами контактного типа функций из отдельных замкнутых классов.............. 64 Зиновьев Владимир Сергеевич Синтез и сложность универсальных схем контактного типа с разделёнными полюсами........................... 65 Абраменкова Марина Анатольевна Применение графических ускорителей для поиска высоковероятностных линейных дифференциальных характеристик современных хэш-функций............................. 67 Давлетшина Александра Маратовна Вопрос стойкости криптосистемы Мак-Элиса–Сидельникова, построенной на основе кодов Рида–Маллера............... 69 Колганова Виктория Викторовна Пространство ключей криптосистемы Мак-Элиса–Сидельникова на основе кодов Рида–Маллера..................... 71

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

Багров Никита Юрьевич Распознавание человека по изображению лица на основе глубинного обучения............................... 73 Лаврушкин Сергей Валерьевич Алгоритм поиска перепутанных ракурсов в стереовидео...... 75 Орпанен Игорь Сергеевич Исследование и разработка методов динамической аутентификации пользователя на основе специфики его работы с клавиатурой 77 Зобнин Денис Станиславович Сопоставление изображений магнитно-резонансной томографии головного мозга человека на основе ключевых точек........ 78 Быковец Евгений Владимирович Разработка алгоритма отображения виртуальных ресурсов на физические в программно-конфигурируемых сетях........... 80 Кибитова Валерия Николаевна Разработка и реализация алгоритма синхронизации времени для среды имитационного моделирования DYANA.





........... 82 Тезисы выпускных работ факультета ВМК МГУ 2015 года Савков Борис Вячеславович Исследование возможности обнаружения уязвимостей внедрения выражений на языке запросов к элементам XML документов... 84 Степанов Евгений Павлович Исследование алгоритмов управления качеством транспортного соединения в Интернет с помощью многопоточных протоколов.. 86 Афанасьев Илья Викторович Массивно-параллельные вычислительные ядра для графических процессоров: семейство алгоритмов треугольного разложения блочных разреженных матриц..................... 88 Потапов Юрий Юрьевич Массивно-параллельные вычислительные ядра для графических процессоров: семейство алгоритмов для решения систем линейных уравнений с мелко-блочными разреженными матрицами...... 90 Желтков Артем Александрович Исследование особенностей разработки и функционирования программного комплекса для формирования рейтинга производительности устройств на различных мобильных платформах....... 91

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

Казаков Артем Александрович Исследование алгоритмов упаковки таблично заданных функций. 93 Мадорский Константин Максимович Построение дескрипторов научного текста на базе векторной модели........................ 95 Смирнова Александра Сергеевна Разработка базы слов-омофонов для коррекции ошибок в текстах 97 Тодуа Антон Романович Разработка интерпретатора языка Рефал............... 98

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

Белов Никита Андреевич Автоматическое обнаружение использования неинициализированных значений в рамках полносистемной эмуляции.......... 100 Богомолов Данила Андреевич Генерация тестового покрытия для транслятора гостевых инструкций полносистемного эмулятора.................... 101 Оглавление Машонский Иван Дмитриевич Исследование и разработка методов анализа предложений, содержащих сравнения............................. 103 Пархоменко Павел Андреевич Выявление тематик исследований в графе цитирования...... 105 Баранов Максим Сергеевич Преобразование последовательных Си-программ для их распараллеливания................................. 107 Малахов Дмитрий Павлович Методы автоматической рубрикации текстовых документов предметной области.............................. 109 Отделение специалитета Кафедра математической физики Гурьянов Федор Александрович Применение метода эмпирических мод для анализа медицинских изображений................................ 112 Хвостиков Александр Владимирович Текстурный анализ и подавление спеклов ультразвуковых медицинских изображений.......................... 114 Мамаев Николай Владимирович Адаптивные методы подавления шума на многомерных изображениях..................................... 116 Ильясова Ольга Хисамовна Синтез оптического покрытия с минимальным отражением в заданном наборе частот.......................... 118 Старостин Александр Сергеевич Регуляризованный по Тихонову биспектральный метод решения одной обратной задачи офтальмологии................ 120 Терешкин Денис Евгеньевич Метод контрастности в одномерной обратной задаче зондирования слоистой среды.............................. 122

Кафедра вычислительных технологий и моделирования

Азиатцева Валерия Валерьевна Обратные задачи математического моделирования динамики инфекции, вызванной вирусом иммунодефицита человека....... 124 Тезисы выпускных работ факультета ВМК МГУ 2015 года Матвеев Сергей Александрович Численное решение многомерного уравнения коагуляции Смолуховского на основе малоранговых разложений массивов...... 126 Кафедра вычислительной математики Егоров Дмитрий Сергеевич Исследование нелинейных решений в распределенных джозефсоновских переходах с помощью метода конечных элементов..... 128 Кафедра автоматизации научных исследований Балыков Глеб Александрович Моделирование распространения электромагнитных волн в метаматериалах................................. 130 Кафедра нелинейных динамических систем и процессов управления Блинов Дмитрий Михайлович Элементы систем управления мультикоптером............ 132 Роговский Александр Игоревич Роль обобщенного относительного порядка в задаче обращения векторной системы............................ 133 Кафедра общей математики Бородинова Дарья Юрьевна Спектральные свойства сильно сингулярных дифференциальных операторов второго порядка на отрезке................ 135 Кафедра исследования операций Мигачёва Ольга Александровна Методы оценки стоимости опционов на дискретных рынках.... 137

–  –  –

Парадеженко Георгий Витальевич Пространственная и временная корреляционные функции в оптимальном гауссовом приближении.................... 139 Кафедра системного анализа Розова Влада Стефановна Стратегия терапии в математической модели взаимодействия больных клеток с клетками иммунной системы........... 140 Семёнова Анастасия Владимировна Задача оптимального управления вибрационным гасителем.... 142 Зилонова Екатерина Михайловна Выбор стратегии лечения в математической модели взаимодействия популяции микробов и антибиотика............... 144

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

Алпатова Татьяна Игоревна Роботизированный трейдер на основе теории коинтеграции.... 146 Бодня Ян Викторович Стохастическая модель рынка новостей................ 148 Дорофеева Александра Владимировна Оценки скорости сходимости в центральной предельной теореме при оcлабленных моментных условиях................. 150 Перкина Юлия Руслановна Анализ пропущенных значений..................... 152 Полднев Антон Вячеславович Использование многомерных случайных процессов для моделирования торгов на связанных инструментах фьючерсного рынка... 154

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

Ломов Никита Александрович Методы вычисления морфологического спектра изображений на основе медиального представления................... 156 Львов Сергей Сергеевич Разработка оптимальных процедур вычисления оценок, основанных на системах логических закономерностей............ 158 Тезисы выпускных работ факультета ВМК МГУ 2015 года Никифоров Андрей Геннадьевич Разработка подхода к построению эффективных параллельных алгоритмов для дискретных перечислительных задач......... 159 Новиков Александр Витальевич Вычислительные методы приближенного подсчета нормировочной константы марковского случайного поля............... 161 Новиков Павел Александрович Исследование различных методов верификации моделей вероятностных распределений, основанных на байесовских сетях..... 163

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

Довгалюк Екатерина Леонидовна О реализации функций алгебры логики схемами, вложенными в единичные кубы.............................. 165 Кулешов Олег Владимирович Оценки динамической активности схем из функциональных элементов, реализующих функции мультиплексорного типа...... 167 Плаксина Анна Александровна О длине некоторых периодических функций трехзначной логики в классе поляризованных полиномиальных форм........... 169 Карелина Екатерина Константиновна Исследование свойств корреляционно-иммунных и алгебраически вырожденных булевых функций.................... 171 Кущинская Людмила Александровна Исследование границ применимости некоторых методов криптографического анализа потоковых шифров, построенных на основе регистров сдвига............................. 173 Слесарева Марина Николаевна Исследование криптосистемы Мак-Элиса на основе ( 2 ) - подкодов кода Рида–Маллера........................ 175

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

Боков Александр Александрович Методы объективной оценки качества видео, конвертированного в стереоформат............................... 178 Казачук Мария Андреевна Применение методов анализа временных рядов в задачах распознавания пользователей смартфонов по данным акселерометра.. 180 Оглавление Шахуро Владислав Игоревич Синтез обучающих выборок для классификации и выделения объектов.................................... 181 Старцев Михаил Леонидович Использование признаков изображений и видео для улучшения качества распознавания речи....................... 183 Коростелева Мария Викторовна Исследование протокола криптографически защищенных групповых коммуникаций с функцией отказуемости............. 185 Петров Иван Сергеевич Исследование методов обнаружения шеллкодов, построенных с применением техники возвратно-ориентированного программирования.................................... 188 Рыжов Игорь Дмитриевич Динамический алгоритм балансировки нагрузки на основе миграции коммутаторов для распределенной платформы управления в программно-конфигурируемых сетях.................. 190 Селецкий Станислав Валерьевич Алгоритмы планирования вычислений в системах на основе интегрированной модульной авионики................... 192 Шведов Юрий Алексеевич Исследование и разработка алгоритмов эффективного распределения радиочастотных ресурсов в беспроводных сетях......... 194 Богданенко Алексей Олегович Линдбладовская эволюция квантовой системы в модели ДжейнсаКаммингса-Хаббарда с фононами................... 196 Кропотов Денис Андреевич Разработка методов и алгоритмов оптимизации для задач квантовой информатики............................. 198 Курденкова Елена Олеговна Томография квантовых состояний и операций методами выпуклой оптимизации................................ 199 Леоненков Сергей Николаевич Изучение подходов повышения эффективности работы менеджера ресурсов суперкомпьютера Simple Linux Utility for Resource Management................................ 201

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

Астабацян Карапет Араевич Построение ансамбля классификаторов для анализа эмоциональной направленности текста....................... 204 Борисенкова Анна Сергеевна Инструментальные средства автоматического анализа нотных записей музыкальных произведений................... 206 Котов Юрий Вадимович Один алгоритм уменьшения звёздной высоты регулярного выражения.................................... 208 Кулёва Анна Сергеевна Диалект и интерпретатор языка Лисп для анализа древовидной разметки.................................. 209 Николаев Евгений Альбертович Система автоматизированного извлечения информации о научных публикациях в сети Интернет...................... 211 Желубенков Александр Евгеньевич Модели ранжирования в задаче предсказания результатов спортивных матчей............................... 212

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

Кондратьев Михаил Владимирович Разработка поддержки анализа программ на языке C# в статическом анализаторе Svace......................... 214 Щевьёва Светлана Михайловна Высокоуровневое представление алгоритма восстановленного по трассе машинных команд........................ 215 Буланов Артём Андреевич Преобразование последовательных Фортран-программ для их распараллеливания.............................. 217 Захаров Дмитрий Александрович Распараллеливание вычислений с разреженными матрицами... 218

–  –  –

Отделение магистратуры Кафедра математической физики Пирожков Вадим Дмитриевич Метод суперразрешения изображений с помощью адаптивного взвешенного медианного усреднения.................. 221 Звягина Лидия Александровна Математические модели в сейсмическом частотном зондировании 223 Кафедра оптимального управления Кабылов Ерлан Криптоанализ криптосистемы Мак-Элиса, основанной на подкодах кода Рида-Маллера............................ 225 Кафедра суперкомпьютеров и квантовой информатики Матвеев Владимир Владимирович Разработка методов и средств анализа поведения параллельных программ для высокопроизводительных вычислительных систем. 226 Кафедра алгоритмических языков Сальников Михаил Святославович Автоматическое аннотирование отзывов ключевыми словами... 228 Отделение второго высшего образования Голубева Яна Вадимовна Разработка и исследование алгоритмов балансировки нагрузки в параллельной реализации метода ветвей и границ.......... 231 Курин Виталий Владимирович Разработка программного обеспечения для анализа и наглядного представления выравниваний белковых последовательностей большого объема................................ 233 Смирнов Владимир Александрович Метод дискретных особенностей в задаче нахождения напряженнодеформированного состояния мембраны................ 235 Васильева Надежда Аркадьевна Математическое моделирование микробиологических процессов в почвенной среде.............................. 237 Тезисы выпускных работ факультета ВМК МГУ 2015 года Ярославцева Елена Валентиновна Исследование и разработка параллельных методов решения систем линейных алгебраических уравнений с разреженными матрицами на гибридных высокопроизводительных вычислительных системах 239 Темы выпускных квалификационных работ, защищенных в 2015 году (отделение бакалавриата)............... 242 Темы дипломных работ, защищенных в 2015 году (отделение специалитета)........................... 274 Темы магистерских диссертаций, защищенных в 2015 году (отделение магистратуры)...................... 307

–  –  –

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

[1], [2]). Основной интерес представляет обратная задача, требующая восстановления неизвестной функции источников в одномерном уравнении теплопроводности при помощи дополнительного финального переопределения. Точная постановка задачи имеет вид 0, (, ) = (, ) + (), 0, 0, (0, ) = 0, (, 0) = 0, 0, (, ) = 1 (), 0.

–  –  –

| 1 () 1 ()|, 0 со значением = 107. Поскольку погрешность приближения оказывается ничтожной, а скорость вычислений возрастает в 6 – 7 раз, то при численном решении обратной задачи вместо аналитической функции 1 () использовалось ее приближенное представление 1 ().

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

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

Литература

1. Тихонов А. Н., Самарский А. А. Уравнения математической физики. М.: Наука, 1972.

2. Карслоу Г., Егер Д. Теплопроводность твердых тел. М.: Наука, 1964.

3. Попов А. Ю., Тихонов И. В. Экспоненциальные классы разрешимости в задаче теплопроводности с нелокальным условием среднего по времени. // Матем. сборник 2005. Том 196. № 9. С. 71-102.

–  –  –

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

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

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

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

–  –  –

Были сформулированы и доказаны теоремы существования и единственности решения обратной задачи; теорема устойчивости решения обратной задачи при изменении функции ().

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

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

Литература

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

М.: Наука, 1979.

2. Денисов А. М. Введение в теорию обратных задач. М.: Изд-во МГУ, 1994.

3. Ebeling W., Fortov V. E., Klimontovich Yu. L. Transport Properties of Dense Plasmas. Basel; Boston; Stuttgart; Birkhauser, 1983.

4. Денисов А. М., Соловьева С. И. Задача определения коэффициента нелинейного стационарного уравнения теплопроводности. Ж. вычисл. матем. и матем. физ., 1993. Т. 33. № 9. С. 1294–1304.

5. Тихонов А. Н. Обратные задачи для нелинейного одномерного стационарного уравнения теплопроводности. Ж. вычисл. матем. и матем. физ., 2000. Т. 40. № 11. С. 1725–1738.

<

–  –  –

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

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

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

Алгоритм состоит из 5 этапов:

1. Предобработка изображения:

Выравнивание освещенности, Медианная фильтрация, Обработка фильтром Гаусса.

2. Применение алгоритма детектирования жирных линий.

3. Бинаризация изображения.

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

5. Наложение полученной карты жирных линий на исходное изображение с выровненной освещенностью.

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

1. Изображение сворачивается с двумерным фильтром Гаусса с = 20:

((2 + 2 )/(2 2 )).

(, ) = 2 2

–  –  –

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

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

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

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

Далее производилось наложение карты жирных линий на исходное изображение с выровненной освещенностью.

Алгоритм применен на существующей в ГБУЗ МО МОНИКИ им.

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

–  –  –

1. Махнева Н. В., Белецкая Л. В. Иммунофлюоресценция в клинике аутоиммунных буллезных дерматозов. М.: Академия Естествознания, 2010.

2. Eberly D., Gardner R., Morse B., Pizer S. C. Ridges for image analysis.

Journal of Mathematical Imaging and Vision, 353-373, 1994.

3. Shapiro L., Stockman G. C. Computer Vision. New Jersey: Prentice Hall,2001.

–  –  –

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

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

Модель динамики ВИЧ-инфекции представляет из себя систему нелинейных ОДУ () = ((), ()), переменными которой являются концентрации здоровых и зараженных клеток и вирионов в органах имунной системы [1 (), 2 (), 3 ()], а также эффективности лекарственных препаратов двух типов: RTI и PI [1 (), 2 ()].

Целью лекарственной терапии ВИЧ-инфицированного пациента является не полное устранение вируса из организма, но поддержание его концентрации на постоянном низком уровне, то есть стабилизация уровня инфекции. В терминах представленной модели это означает нахождение таких и, при которых (, ) = 0. В работе решается задача поддержания состояния равновесия: () = + (), () = + (), при помощи управления () оптимальным образом сводящего () к нулю [3].

Далее из формул фармакодинамики [4] восстанавливается концентрация препарата по его эффективности () = (()) () = (()) Отделение бакалавриата и решается задача приближения искомой функции концентрации. Фармакокинетические модели [1] позволяют описать кинетику препарата в организме по шаблону () = 0 (), где 0 – начальная доза препарата, а () – модельная функция (например, () = 0 1 ).

Если препарат принимается регулярно, через интервалы и =, то концентрация определяется формулой () = 0 ( 1 ). Задача приближения оптимальной концентрации () реально достижимой () является задачей ортогонального проектирования на линейную оболочку системы функций {( 1 )}. =1 Решение задачи приближения строится на основе проекционного метода Ритца [2] с разложением функций ( 1 ) на конечные элементы () и построением базиса () = (). Вектор решений находится =1 из системы 0 = с нижнетреугольной матрицей.

–  –  –

Система решается для различных значений {2, 4, 6, 8, 10, 12, 24} (и соответственно различных и ). Отлонение достижимой функции от искомой () () позволяет выбрать оптимальное значение.

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

Работа выполнена при поддержке гранта РФФИ 14-01-004779.

–  –  –

1. Варфоломеев С. Д., Гуревич К. Г. Биокинетика. Практический курс. М.: ФАИР-ПРЕСС, 1999.

2. Марчук Г. И., Агошков В. И. Введение в проекционно-сеточные методы. М.: Наука, 1981.

3. Поляк Б. Т., Хлебников М. В., Щербаков П. С. Управление линейными системами при внешних возмущениях: Техника линейных матричных неравенств. М.: ЛЕНАНД, 2013.

4. Macheras P., Iliadis A. Modeling in Biopharmaceutics, Pharmacokinetics and Pharmacodynamics Homogeneous and Heterogeneous Approaches.

Springer, 2006.

–  –  –

Для решения данной системы использован итерационный метод Ньютона.

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

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

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

Проведена серия тестовых расчетов на модельном графе [4] для отладки программы. Результаты расчетов совпадают с известными данными модельного графа.

Литература

1. Кошелев В. Б., Мухин С. И., Соснин Н. В., Фаворский А. П. Математические модели квази-одномерной гемодинамики. М.: МАКСПресс, 2010.

2. Андреев В. Б. Численные методы (учебное пособие). М.: МАКСПресс, 2013.

3. Эстербю О., Златев З. / Перевод с английского Икрамова Х. Д. Прямые методы для разреженных матриц. М.: МИР, 1987.

4. Циммерман М., Ениг В. и др. / Под ред. Шмидта Р. и Тевса Г. Физиология человека. М.: МИР, 1996.

–  –  –

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

Целью данной работы является построение модели распространения вещества в системе «сосуд-ткань» с учётом вышеупомянутых факторов, а Кафедра ВМ так же анализ влияния областей пониженной диффузии внутри ткани на распространение по ней вещества и время его пребывания внутри ткани до дальнейшего удаления через стенки сосуда. В работе предложен алгоритм решения поставленной задачи, а так же реализован программный комплекс CDP (от англ. convective-diffusive processes) на основе построенной модели.

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

Процесс распространения вещества по ткани описывается следующей системой уравнений относительно массовой концентрации вещества (,, ):

–  –  –

= + (,, ), 0 ; 0 ; 0 (,, ) = 0, 0 ; 0 (,, ) = (, ), 0 ; 0 (, 0, ) = 0, 0 ; 0 (,, ) = 0, 0 ; 0 Коэффициент диффузии, вообще говоря, не является постоянным, а задаётся функцией (, ), что отражает неоднородные диффузионные свойства ткани.

В рассматриваемой области вводится сетка, равномерная по координате и неравномерная по радиусу. Уравнение диффузии аппроксимируется разностной схемой с весами на пятиточечном шаблоне типа «крест».

После аппроксимации система сеточных уравнений сводится к системе трёхточечных векторных уравнений, которая решается методом матричной прогонки [1,§5.9]. В работе исследована устойчивость и корректность (формулировки и лемма взяты из [2,§4]) применённого алгоритма.

В приложении к работе представлена программная реализация на языке Fortran 90 модульного комплекса CDP, моделирующего распространение вещества в системе «сосуд-ткань» после подачи импульса вещества на границу кровеносного сосуда. С синтаксисом и семантикой языка можно ознакомиться в книге [3]. С помощью комплекса CDP были проведены многочисленные численные расчёты и построены графики зависимости величин, на основании которых сделан вывод о зависимости распространения вещества и времени его пребывания внутри ткани от областей пониженной диффузии. Было выявлено, что имеется зависимость как от наличия и величины таких областей, так и от их места расположения внутри ткани, причём эта зависимость является ярко выраженной.

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

Литература

1. Cамарский А. А., Гулин А. В. Численные методы математической физики. М.:Научный Мир, 2000.

2. Cамарский А. А., Николаев Е. С. Методы решения сеточных уравнений. М.:Главная редакция физико-математической литературы изд-ва «Наука», 1978.

–  –  –

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

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

–  –  –

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

Формально оно описывается следующими соотношениями:

(, ) (, ), =, = ( ), = ( 0 )2 + ( 0 )2.

Здесь (0, 0 ) — центр изображения.

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

Для построения трехмерной сцены использовались методы описанные в работах [2] и [3].

Таким образом, в процессе выполнения работы:

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

Проведено сравнение с детекторами SIFT и SURF на различных изображениях. Разработанный детектор оказался быстрее и точнее;

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

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

Литература

1. Marek Jakab Supervised by: Ing. Vanda Benesov Planar Object Recognition Using Local Descriptor Based On Histogram Of Intensity Patches. // Faculty of Informatics and Information Technologies. Slovak University of Technology Bratislava / Slovakia 2013

2. Аленин В. А. Трехмерная реконструкция объектов из последовательности изображений //«Молодой ученый». – 2011. – №3. Т.1.

– С. 33–36.

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

3. Жук Д. В., Тузиков А. В., Бородач А. В Восстановление трёхмерной модели сцены по цифровым изображениям //«Искусственный интеллект». – 2006 – №2. – С. 142–146 Синтез оптимального регулятора упрощенной модели вертикальной стабилизации плазмы в тороидальной камере с магнитными катушками в случае широтно-импульсной модуляции Работа удостоена диплома III степени Гришина Анна Павловна Кафедра нелинейных динамических систем и процессов управления e-mail: grishina.anna93@yandex.ru Научный руководитель: д.ф.-м.н., проф. Фомичев Василий Владимирович В работе рассматривается задача управления положением и формой плазмы в токамаке с учетом особенностей исполнительного устройства — тиристорного преобразователя. Задача синтеза алгоритма управления широко изучалась для различных установок, однако из-за того, что скорости течения процессов в магнитной системе сравнимы со скоростью работы исполнительного устройства, возникает вопрос о возможности улучшения управления за счет использования в алгоритме явной информации о тиристорном преобразователе.

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

Основною целью данной работы стала модификация одного из методов оптимизации (метода Гаусса–Ньютона для автономной системы с управляемыми переключениями) с учетом особенностей тиристорного преобразователя.

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

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

Литература

1. Гончаров О. И. Синтез контура магнитного управления плазмой токамака с учетом особенностей системы питания. М.: Вестник Московского Университета, 2015.

2. Egerstedt M., Wardi Y., Delmotte F. Optimal Control of Switching Times in Switched Dynamical Systems. М.: Atlanta, 2008.

Разработка базовой станции для беспилотного летательного аппарата типа конвертоплан. Создание модуля состыковки беспилотных летательных аппаратов типа конвертоплан Коромыслов Александр Юрьевич Кафедра нелинейных динамических систем и процессов управления e-mail: alexandr.koromyslov@gmail.com Научный руководитель: д.ф.-м.н., проф. Ильин Александр Владимирович В настоящее время широкое распространение получили беспилотные летательные аппараты(далее БПЛА). Они решают довольно большой спектр задач, как военных, так и гражданских. Беспилотники гражданского назначения могут использоваться в работе служб по чрезвычайным ситуациям; в полиции; на предприятиях сельского хозяйства и лесничествах; в компаниях, занимающихся геодезией ; в географических и геологических институтах; в компаниях нефтегазового сектора; на строительных объектах; в средствах массовой информации. Всё большее количество задач необходимо выполнять в автоматическом режиме. Для этого разрабатываются сложные программно-аппаратные комплексы — базовые станции. С их помощью можно не только управлять беспилотным летательным аппаратом и контролировать телеметрию, но также получать видеоданные, задавать последовательности действий, которые будут выполняться в автоматическом режиме.

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

Решение задачи было разбито на несколько этапов. На первом был выбран шаблон маркера, который будет являться местом посадки БПЛА.

На втором шаге производится поиск центра маркера на изображени. За основу алгоритма поиска места посадки была взята работа по разработке устойчивой системы поиска маркера для автономной посадки БПЛА на основе визуальных данных [2], которая была подвергнута значительному упрощению для увеличения быстродействия системы. Основная идея второго этапа — это совмещение метод поиска границ на изображении и метода градиентов, что позволяет точнее найти центр. На третьем этапе производится сравнение координат центра шаблона и центра изображения и, в зависимости от итогов сравнения, делается вывод, в какую сторону необходимо переместиться БПЛА. В зависимости от расстояния между центрами шаблона и изображения прикладывается различная сила, которая пропорционально зависит от расстояния. На четвертом этапе происходит непосредственное отправление управляющих сигналов полетному контроллеру.

В работе решена задача моделирования системы состыковки.

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

1) Выбран маркер, который является местом посадки БПЛА.

2) Разработан алгоритм, осуществляющий посадку БПЛА.

3) Написана программная часть, реализующая описанный выше алгоритм.

Литература

1. Weiwei Kong, Daibing Zhang, Xun Wang, Zhiwen Xian, Jianwei Zhang.

Autonomous landing of an UAV with a ground-based actuated infrared stereo vision system. // Intelligent Robots and Systems (IROS), 2013 IEEE/RSJ International Conference on 11/2013 Отделение бакалавриата

2. Verbandt Maarten, Theys Bart, De Schutter Joris. Robust markertracking system for vision-based autonomous landing of VTOL UAVs.

// Proceedings of the International Micro Air Vehicle Conference and Competition 2014 pages:84–91

–  –  –

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

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

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

–  –  –

Литература

1. Takahashi W. A convexity in metric space and nonexpansive mappings.

Kodai. Math. Sem. Rep. 22 (1970), 142-149.

2. Lee B.-S. Approximating Common Fixed Points of Two Sequences of Uniformly quasi-Lipschitzian Mappings in Convex Cone Metric Spaces.

Universal Journal of Applied Mathematics, 1(3), 166-171, 2013.

3. Elmas S., Ozdemir M. Convergence of a general iterative scheme for three infinite families of uniformly quasi-Lipshitzian mappings in convex Отделение бакалавриата metric spaces. Advanced in Fixed Point Theory. 2013, № 2, 406-417.

4. Фоменко Т. Н. Устойчивость каскадного поиска. Известия РАН, серия Математическая, Том 74, № 5, 2010, с. 171-190.

5. Гайнуллова С. Р., Фоменко Т. Н. Функционалы, подчинённые сходящимся рядам, и каскадный поиск особенностей отображений. Математические Заметки, том 96, № 2, 2014, с.314-317.

Разработка и реализация интерактивного графического представления модели суперкомпьютерного комплекса Лучшая практическая работа Даугель-Дауге Артём Александрович Кафедра суперкомпьютеров и квантовой информатики e-mail: daugeldauge@gmail.com Научный руководитель: к.ф.-м.н., с.н.с. НИВЦ МГУ Соболев Сергей Игоревич Одной из главных задач администрирования суперкомпьютерных комплексов является обеспечение оперативного контроля функционирования комплекса. Чтобы обеспечить непрерывную и правильную работу суперкомпьютерного комплекса, необходимо отслеживать все нештатные ситуации, возникающие в работе всех компонентов комплекса, и правильно реагировать на них. Для решения этой проблемы в НИВЦ МГУ имени М. В. Ломоносова разрабатывается [1-2] система Octotron. Система отслеживает наступление нештатных ситуаций и при их возникновении выполняет определенный набор действий.

Основу системы Octotron составляет мультиграф — модель суперкомпьютерного комплекса. Вершины в графе представляют физические или виртуальные компоненты суперкомпьютерного комплекса, работу которых необходимо контролировать (источники питания, вычислительные узлы, сетевые платы, лицензии на ПО и т.д.), а дуги моделируют связи между компонентами («охлаждает», «состоит из», «соединены сетью Ethernet» и т.д.). К каждой вершине графа прикреплены различные атрибуты — характеристики состояния компонентов (температура, объем свободной памяти и т.д.). При изменении значений атрибутов срабатывают правила, которые опираются на них, и определяют возникновение нештатной ситуации. Далее, если такая ситуация возникла, происходит реакция: выполняется определенный набор действий.

В ходе работ необходимо визуально оценивать корректность модели, построенной вручную или сгенерированной автоматически. Основная проблема визуализации модели — то, что граф получается достаточно большой, например в модели с/к «Ломоносов» содержится около 100 тысяч Кафедра СиКИ узлов и около 340 тысяч связей. Отобразить модель в таком виде, в каком она хранится, не получается — либо алгоритмы не справляются с графами такого масштаба, либо получается совершенно нечитаемый результат.

Как правило, в графе модели отсутствуют ориентированные циклы.

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

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

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

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

На основе описанных выше методов было разработано веб-приложение.

Серверная часть написана на фреймворке Sinatra, интерактивная визуализация графов производится силовым алгоритмом (force-directed layout [3]) с помощью библиотеки d3.js. Также был разработан пользовательский интерфейс для взаимодействия с системой. Система была развернута на сервере НИВЦ МГУ и доступна по адресу http://graphit.parallel.ru:4568.

Исходный код системы доступен под открытой MIT лицензией по адресу https://github.com/daugeldauge/clusterviz-new.

Литература

1. Антонов А. С., Воеводин Вад. В., Воеводин Вл. В., Жуматий С. А., Никитенко Д. А., Соболев С. И., Стефанов К. С., Швец П. А. Разработка принципов построения и реализация прототипа системы обеспечения оперативного контроля и эффективной автономной работы суперкомпьютерных комплексов. // Вестник УГАТУ. — 2014. — т. 18, №2. — с. 227–236.

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

2. Антонов А. С., Воеводин Вад. В., Даугель-Дауге А. А. Жуматий С. А., Никитенко Д. А., Соболев С. И., Стефанов К. С., Швец П. А. Обеспечение оперативного контроля и эффективной автономной работы Суперкомпьютерного комплекса МГУ. // Параллельные вычислительные технологии (ПаВТ’2015): труды международной научной конференции (31 марта – 2 апреля 2015 г., г.

Екатеринбург). — Издательский центр ЮУрГУ Челябинск, 2015. — с. 348–353.

3. Roberto Tamassia Handbook of Graph Drawing and Visualization (Discrete Mathematics and its Applications) // Chapman and Hall/CRC, 2007

–  –  –

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

Кафедра ИО Задача не решается известными методами, для её решения в работе предложен алгоритм, его основная идея состоит в том, что на каждом шаге есть множество потребителей, которым еще не поставлен в соответствие объект, и оно постепенно.

Кратко опишем предложенный алгоритм:

Шаг 0: На этом шаге идентифицируем необходимые переменные и множества: положим число объектов = 0, множество положим равным {1, 2,..., }. Вокруг каждого потребителя опишем круг радиуса, который задается нормативным документом [1], этот круг будем называть областью доступности данного потребителя (идея использовать круги для обозначения области доступности взята из задачника [3]).

Итерация K Шаг 1: Пусть группа, к которой относится -й потребитель, изолирована от остальных. Тогда в любой точке его области доступности расположим столько объектов, чтобы обеспечить всю эту группу местами. Увеличим на число этих объектов, а всех потребителей из группы уберем из множества, перейдем к шагу 4.

Если изолированных групп нет — перейдем к шагу 2.

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

Если все группы пересекаются как минимум с двумя другими — переходим к шагу 3.

Шаг 3: Найдем группу, длина границы области доступности которой, не принадлежащей другим областям доступности, максимальна. Тогда для этой области доступности находим область (), которая принадлежит наибольшему числу областей доступности других потребителей (множество их номеров — ()), в этой области располагаем столько объектов, чтобы по возможности обеспечить всех этих потребителей объектами так, чтобы не было свободных мест. Увеличим на число этих объектов, а всех потребителей, которых нашли место, уберем из множества. Через обозначим число потребителей, которым не хватило мест в этих объектах, заведем счетчик = 0 и переходим к шагу 3.1.

Если потребителей не осталось — переходим к шагу 4.

Шаг 3.1: Если в итоге всем потребителям хватило места, то есть =, то переходим к шагу 4. Если, то переходим к шагу 3.2.

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

Шаг 4: Если множество =, то переходим к итерации + 1.

Отделение бакалавриата Иначе алгоритм заканчивает работу.

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

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

Литература

1. Свод правил СП 42.13330.2011 (актуализированная редакция СНиП 2.07.01-89* ).

2. МГСН «Дошкольные образовательные учреждения» 4.07-05 от 21.11.2006 N 911-ПП

3. Морозов В. В., Сухарев А. Г., Федоров В. В. Исследование операций в задачах и упражнениях. Высшая школа, 1986.

–  –  –

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

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

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

–  –  –

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

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

Литература

1. Bertsimas D., Lo А. W. Optimal control of execution costs. // Journal of Financial Markets. 1988. №1. P.1–50.

2. Морозов В. В., Толли Н. И Минимизация риска при крупных закупках на финансовом рынке. // International Journal of Open Information Technologies 2014. V.2. №8.

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

–  –  –

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

Этот коэффициент рассчитывается с помощью бонус-малус систем.

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

определено конечное число классов;

каждому классу соответствует бонус-малус коэффициент (коэффициент за безаварийность);

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

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

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

Кафедра ОУ Цель работы - на основе введенных критериев качества систем, используя технику марковских цепей, сравнить 7 национальных бонус-малус систем (Австрия, Бразилия, Германия, Молдова, Россия, Тайвань, Япония).

Системы выбраны так, чтобы показать разнообразие систем и их характеристик.

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

–  –  –

2. Mahmoudvand R., Edalati A., Shokoohi F. Bonus-malus systems in Iran:

an empirical evaluation. Journal of Data Science No. 11, 2013, pp.29-41

3. Кемени Дж., Снелл Дж. Конечные цепи Маркова М.: Наука, 1970

–  –  –

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

Тогда смещение струны = (, ; ) от положения равновесия является решением следующей начально-краевой задачи:

–  –  –

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

Литература

1. Васин А. А.,Краснощеков П. С.,Морозов В. В. Исследование операций. М.: Издательский центр «Академия», 2008.

2. Тихонов А. Н., Самарский А. А. Уравнения математической физики. М.: Изд-во МГУ, 1999.

3. Васильев Ф. П. Методы оптимизации. М.: МЦНМО, 2011.

–  –  –

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

Изучаемый процесс. Приемник GPS получает информацию о координатах и моменте подачи сигнала от пяти спутников одновременно.

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

Математическая модель процесса Приемник GPS получает сигнал от пяти спутников. Для определения своего положения в пространстве GPS-приемнику нужно решить пять уравнений вида = | | =, здесь — расстояние от приемника до -го спутника, — неизвестное трёхмерное положение приемника GPS, — местоположение -го спутника, — псевдо-расстояние от приемника до -го спутника, — скорость света, — погрешность часов приемника.

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

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

Известными данными задачи являются: = (,, ) — положения спутников в пространстве, величины псевдо-расстояний и погрешности,. Величины погрешностей, не превосходят 2 и 10 метров, соответственно, и распределены в своих областях значений заданным образом. Необходимо отыскать множество в пространстве, в котором приемник GPS находится вероятностью 90% Подход к решению задачи. Исследование задачи опирается на работы [1–4].

Численное решение поставленной задачи содержит следующие этапы:

1. Генерацию множества псевдо-случайных точек, распределенных заданным в задаче образом.

2. Решение для каждого линейной системы (1 )0 + (1 )0 + (1 )0 (1 ) = = (2 2 + 1 + 1 1 + ), = 2, 5, 1

3. Исключение из полученных точек 0 тех, которые не удовлетворяют условию (0 1 )2 + (0 1 )2 + (0 1 )2 = (1 )2 с заданной точностью = 106.

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

4. Определение вероятностного закона, по которому распределены оставшиеся точки, и исключение 10% самых маловероятных значений.

Результаты расчетов. Полученные в результате выполнения этапов 1–3 точки 0 образуют параллелепипед со сторонами (в метрах) 26.50 18.71 29.93, и центром в точке = 4343409.76, = 124937.01, = 4653479.27.

Радиус-векторы этих точек 0 = 2 + 0 + 0 распределены на области своих значений нормально с математическим ожиданием = 6.367 · 106 м.

После отбрасывания 10% самых маловероятных значений, получаем параллелепипед со сторонами (в метрах) 21.93 18.02 22.12, и центром в той же точке (,, ).

Задача определения неопределенности местоположения приемника GPS решена для одного измерения. Написанная программа получает результат в течение 30–40 минут.

Литература

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

М.: Наука, 1979.

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

3. Карутин С. Н., Власов И. Б., Дворкин В. В. Дифференциальная коррекция и мониторинг глобальных навигационных спутниковых систем. М.: Издательство Московского университета, 2014.

4. Колесников Е. П., Райкунов Г. Г. Влияние отражения радиосигнала от поверхности Земли на ошибки измерений с использованием глобальной навигационной системы. Космонавтика и ракетостроение, 2009, №3(56).

–  –  –

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

Также возможны другие способы управления, например, через выделение полос для общественного транспорта или платных полос (описано в [5]).

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

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

1. Все автомобили обладают одинаковыми и неограниченными скоростными возможностями;

2. Ни один автомобиль в промежуток [, + ] не находится более, чем в двух клетках (соседних);

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

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

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

Для двух соседних клеток 1 и 2 анализ движения траффика происходит следующим образом:

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

2. Определим, какое максимальное количество машин 2, может въехать в клетку 2 за ;

3. Реальное количество машин, переезжающее за шаг моделирования из клетки 1 в клетку 2 равно 0 = min {1,, 2, };

4. Проанализировать выхождение 0 машин из клетки 1 ;

5. Проанализировать вхождение 0 машин для клетки 2.

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

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

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

Литература

1. Куржанский А. А., Куржанский А. Б., П. Варайя. Роль макромоделирования в активном управлении транспортной сетью. Труды Московского физико-технического университета, 2010.

2. Carlos F. Daganzo. The cell transmission model: a dynamic representation of highway traffic consistent with the hygrodynamic theory. Transportation Research Part B: Methodological, 1994. The cell transmission model, Part II: Network traffic. Transportation Research Part B: Methodological, 1995.

3. M. J. Lighthill, G. B. Whitham. On kinematic waves. II. A theory of traffic flow on long crowded roads. Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences, May 1955.

4. Дорогуш Е. Г. Математический анализ модели транспортных потоков на автостраде и управления ее состоянием. Диссертация, кафедра системного анализа факультета ВМК МГУ имени М. В. Ломоносова, защищена 23.03.2014.

–  –  –

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

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

Между любыми двумя замкнутыми непустыми множествами и определено расстояние Хаусдорфа соотношением (, ) := inf{ 0 : (, ), (, )}, где (, ) обозначает замкнутую окрестность радиуса множества, если для некоторого выполнены включения (, ) и (, ), в противном случае полагают (, ) :=.

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

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

Литература

1. Hausdorff F. Grundzuge der Mengenlehre. Von Veit, Leipzig, 1914.

–  –  –

3. Демьянов В. Ф. Условия экстремума и вариационное исчисление.

Высшая школа, Москва, 2005.

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

4. Nadler S.B. Multi-valued contraction mappings. Pac. J. of Math., 1969.

5. Arutyunov A.V. Covering mappings in metric spaces and fixed points.

Dokl. Math., 2007.

–  –  –

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

Во второй части работы предложены методы регуляризации исходной модели Смита—Уилсона применительно к двум видам финансовых инКафедра СА струментов. В обоих случаях за основу взят функционал гладкости, предложенный авторами метода, результатом минимизации которого служит функция дисконтирования ( ) () = exp{} 1 + (, )( (, ))1 ( ).

–  –  –

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

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

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

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

Литература

1. Smith A., Wilson T. Fitting Yield curves with long Term Constraints.

Research Notes, Bacon and Wodrow, 2001.

2. EIOPA. Consultation Paper on a Technical document regarding the risk free interest rate term structure. CP - 14/042, 2014.

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

3. Abildgaard A.S., Posselt A.M. An assessment of the Smith–Wilson method, in the light of Solvency II. Master’s thesis, Aarhus University, 2014.

4. Neumaier A. Solving ill-conditioned and singular linear systems: A tutorial on regularization. SIAM review, 40:636, 1998.

–  –  –

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

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

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

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

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

Литература

1. Hofmann T. Probabilistic latent semantic analysis // Proceedings of the Fifteenth conference on Uncertainty in artificial intelligence, Morgan Kaufmann Publishers Inc., 1999, p. 289–296.

2. Vorontsov K. V., Potapenko A. A. Tutorial on probabilistic topic modeling: Additive regularization for stochastic matrix factorization // Analysis of Images, Social Networks and Texts, Springer, 2014, p. 29–46.

3. Kim S.-J., Koh K., Boyd S., Gorinevsky D., 1 trend filtering // SIAM review, 2009, Vol. 51, no. 2, p. 339–360.

–  –  –

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

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

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

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

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

Литература

1. Kuznetsov S. O. Complexity of Learning in Concept Lattices from Positive and Negative Examples // Discrete Applied Mathematics, 2004, № 142 (1–3), p. 111–125.

2. Caprineto C., Romano G. GALOIS: An order-theoretic approach to conceptual clustering // In Proceedings of the 10th International Conference on Machine Learning (ICML 93), Amherst, USA, 1993, p. 33– 40.

3. Kuznetsov S. O. Scalable Knowledge Discovery in Complex Data with Pattern Structures // In Proceedings 5th International Conference Pattern Recognition and Machine Intelligence (PReMI’2013), Kolkata, India, 2013, Vol. 8251, p. 30–39 Кафедра ММП

4. Журавлёв Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики, 1978, т. 33, с. 5–68.

–  –  –

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

Широкое распространение получили BCI-системы, базирующиеся на снятии электроэнцефалограмм (ЭЭГ). Благодаря появлению таких коммерческих устройств, как, например, Emotiv Epoc, данные системы вышли за пределы медицинских учреждений и стали доступны широкому кругу пользователей. Однако данные электроэнцефалографы обладают рядом недостатков: коммерческие устройства по качеству снимаемого сигнала уступают своим профессиональным аналогам; электроды покрывают не все участки головного мозга.

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

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

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

сигналы, возникающие в ЭЭГ при моргании глазами;

SSVEP (Steady State Visually Evoked Potentials) сигналы.

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

Отделение бакалавриата SSVEP-сигналы являются естественной ответной реакцией на визуальные раздражители определенной частоты. Данные сигналы также позволяют добиться высокого качества распознавания. Методы, основанные на SSVEP, не требуют длительного обучения пользователя, вследствие чего они получили широкое распространение. Принципиальная возможность извлечения SSVEP-сигналов из ЭЭГ сигналов, полученных при помощи устройства Emotiv Epoc, была показана в работах [2], [3].

В ходе данного исследования была реализована игра, состоящая в проведении метки на экране монитора по простому лабиринту (игра «Лабиринт») при помощи морганий. При разработке игры для распознавания морганий глаз был предложен метод формирования пространства признаков. Классификация сигналов осуществлялась хорошо зарекомендовавшими себя на практике методами SVM и Random Forest. Игра реализована в системе MATLAB. Также была разработана система для распознавания SSVEP-сигналов, в которой генерация раздражителей осуществлялась при помощи светодиодов и платы Arduino. Классификация данных сигналов осуществляется при помощи канонического корреляционного анализа.

–  –  –

1. Ochoa J. B. EEG signal classification for brain computer interface applications // Ecole Polytechnique Federale De Lausanne, 2002, т. 7, с.

1–72.

2. Liu Y. et al. Implementation of SSVEP based BCI with Emotiv EPOC // Virtual Environments Human-Computer Interfaces and Measurement Systems (VECIMS), IEEE International Conference on, IEEE, 2012, с. 34–37.

–  –  –

где : R R, = 1,..., — всюду определенные выпуклые дважды непрерывно дифференцируемые функции, w R — оптимизируемые переменные, и 0 — заданный коэффициент. Типичными примерами задач указанного вида могут служить задачи настройки параметрической модели по данным, широко возникающие в машинном обучении.

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

Одним из наиболее известных инкрементальных методов оптимизации является метод стохастического градиента (stochastic gradient, SGD) [2].

К сожалению, этот метод обладает рядом недостатков, основными из которых являются требование тонкой настройки параметров пользователем и медленная сублинейная скорость сходимости [1].

Более эффективным инкрементальным методом является метод стохастического среднего градиента (stochastic average gradient, SAG) [3]. В отличие от метода SGD, метод SAG не требует никакой настройки параметров пользователем и, за счет использования дополнительной памяти, обладает уже линейной скоростью сходимости [3].

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

В данной работе предлагается новый инкрементальный метод оптимизации, называемый инкрементальным методом Ньютона (incremental Newton, IN) и обладающий принципиально более быстрой скоростью сходимости — суперлинейной.

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

Основная идея метода IN следующая. Сначала строится своя квадратичная модель для каждой отдельной функции :

(w) := (v ) + (v ) (w v ) + (w v ) 2 (v )(w v ), где v R является параметром модели. Далее построенные модели

–  –  –

Итерация метода заключается в обновлении лишь одной из компонент модели с помощью смещения центра этой компоненты в текущую точку, v := w, где {1,..., } — номер обновляемой компоненты; остальные центры при этом не меняются.

Затем выполняется шаг в направлении найденного минимума:

w+1 = w + (w w ), где — положительная длина шага и w := argmin (w).

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

Основной вклад данной работы:

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

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

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

Литература

1. D. P. Bertsekas. Incremental gradient, subgradient, and proximal methods for convex optimization: A survey. // Optimization for Machine Learning, 2010.

2. H. Robbins and S. Monro. A stochastic approximation method. // The annals of mathematical statistics.

Кафедра ММП

3. M. Schmidt, N. L. Roux, and F. Bach. Minimizing finite sums with the stochastic average gradient. // arXiv:1309.2388, 2013.

–  –  –

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

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

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

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

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

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

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

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

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

разработан метод генерации модельных коллекций коротких текстов;

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

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

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

По результатам исследования подана публикация.

Кафедра МК О длине некоторых периодических функций пятизначной логики в классе поляризованных полиномиальных форм Работа удостоена диплома III степени Гордеев Михаил Михайлович Кафедра математической кибернетики e-mail: gordmisha@gmail.com Научный руководитель: к.ф.-м.н., доц. Селезнева Светлана Николаевна Одним из стандартных способов задания функций k-значной логики являются поляризованные полиномиальные формы (ППФ). В ППФ каждая переменная имеет определенную поляризацию. Практическое применение ППФ нашли при построении программируемых логических матриц (ПЛМ) [1], сложность ПЛМ напрямую зависит от длины ППФ, по которой она построена. Поэтому в ряде работ исследуется сложность ППФ различных функций [2-4].

Пусть 2 – натуральное число, = {0, 1,..., 1}, отображение () : называется функцией -значной логики. Обозначим

–  –  –

( ) ( ) ) ( 2· ( ) 5.

Следствие. Класс функций является вырожденным.

–  –  –

2. Перязев Н. А. Сложность булевых функций в классе полиномиальных поляризованных форм. Алгебра и логика. 34. №3. 1995. С. 323– 326.

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

14. №2. 2002. С. 48–53.

–  –  –

Теория контроля управляющих систем является одним из важнейших разделов кибернетики. В рамках этого раздела изучается обнаружение неисправностей в работе управляющей системы (УС). Основным способом обнаружить неисправность является анализ показаний выходов УС при различных входных данных — тестирование. Этот подход был сформирован в работах С.В. Яблонского и И.А. Чегис (например, в [5]).

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

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

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

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

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

– количество входов схемы, а – количество наблюдаемых полюсов.

По аналогии с функцией Шеннона сложности схемы для класса ФАЛ [2] определим функции Шеннона длины единичного проверяющего теста ([]) и тестовой сложности ([]), где – это класс схем контактного типа, = {КС, ИКС, ОИКС}, а [] – это множество булевых функций из класса от переменных.

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

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

КС ([]) 10; ОИКС ([]) 14;

КС ([]) 10 + 90; ОИКС ([]) 28 + 154.

–  –  –

2. Ложкин С. А. Лекции по основам кибернетики. М.: МАКС Пресс, 2004. – C. 256.

3. Мадатян Х. А. Построение единичных тестов для контактных схем. Сборник работ по математической кибернетике. – М.: ВЦ АН СССР, 1981. – С. 77-86.

4. Романов Д. С. О синтезе контактных схем, допускающих короткие проверяющие тесты. Ученые записки Казанского университета.

Серия Физико-математические науки, 2014. – 156. №3. С. 110-115.

–  –  –

Теория контроля и надежности управляющих систем является важным разделом теории управляющих систем (УС). В рамках данного раздела предполагается, что на УС, реализованную некоторой схемой, воздействует источник неисправностей, который способен повредить некоторым образом схему. Это привело к формированию подхода контроля работы УС, который основан на тестировании поврежденной схемы. Данный подход сформировался в середине 20-го века в работах С. В. Яблонского и И. А. Чегис [2, 3].

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

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

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

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

Расширим понятие итеративной контактной схемы, введенное С. А. Ложкиным в [4], позволив навешивать отрицания на управляющие переменные. Полученную таким образом схему будем называть обобщенной итеративной контактной схемой (ОИКС).

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

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

Аналогично вводится понятие функции Шеннона для длины единичного проверяющего теста.

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

1. Функция Шеннона длины единичного проверяющего теста для КС, реализующих линейные функции, не превосходит 4;

2. Функция Шеннона тестовой сложности для КС, реализующих линейные функции, не превосоходит 4 + 8;

3. Функция Шеннона длины единичного проверяющего теста для ОИКС, реализующих самодвойственные функции, не превосходит 18;

4. Функция Шеннона тестовой сложности для ОИКС, реализующих самодвойственные функции, не превосоходит 54 + 90.

Литература

1. Романов Д. С. О синтезе контактных схем, допускающих короткие проверяющие тесты. Ученые записки Казанского университета.

Серия Физико-математические науки. 2014. 156. №3. С 110-115.

2. Чегис И. А., Яблонский С. В. Логические способы контроля работы электрических схем. Труды МИАН СССР. – 1958. – Т. 51. – С. 270Яблонский С. В., Чегис. И. А. О тестах для электрических схем.

Успехи мат. наук. – 1955. – Т. 10 –Вып. 4(66). – С. 182-184.

4. Ложкин С. А. Лекции по основам кибернетики. М.: МАКС Пресс, 2004. — С. 256.

–  –  –

В работе рассматривается задача об асимптотике сложности совместной реализации «больших» систем функций алгебры логики контактныКафедра МК ми (, )-полюсниками, то есть контактными схемами(КС) с входами и отличными от них выходами, в которых все функции данной системы реализованы как функции проводимости от входов КС к её выходам. Такие КС будем считать КС с разделёнными полюсами, чтобы выделить их из класса всех КС, допускающих, в общем случае, частичное или полное совпадение множества своих входов с множеством своих выходов. При этом в случае полного совпадения входов и выходов будем говорить о КС с неразделёнными полюсами. Заметим, что оптимизировать схему по сложности очень важно,так как это позволяет уменьшить ее стоимость,размеры или потребляемую мощность СБИС.

Частным случаем указанной задачи является задача о нахождении сложности минимального универсального контактного многополюсника(УКМ), который вычисляет все функции алгебры логики от заданного количества переменных. В данной работе вводится и исследуется функция (,, ) равная минимальной из сложностей (, )-универсальных контактных многополюсников, где 22, реализующих систему всех функций алгебры логики(ФАЛ) от переменных. Напомним, что как известно из [1], сложность (1, 22, ) асимптотически равна 2 · 22.

Эта же задача для класса контактных схем с 1 входом и отдельных систем ФАЛ рассматривалась в [2,3,4,5]. В этих работах были установлены асимптотические точные оценки сложности рассматриваемых систем функций в рамках данной модели. Оказалось, что для подавляющей части "больших"систем ФАЛ сложность их реализации в классе контактных схем с одним входом асимптотически равна удвоенному числу функций, входящих в этот класс. В частности, это верно для класса всех функций, класса всех самодвойственных функций, функций с фиксированным числом «1», а также для дизъюнктивного дешифратора. Заметим, что множество всех элементарных конъюнкций ранга от переменных требует для своей реализации всего лишь одного контакта на каждую функцию.

Для натуральных чисел, и таких, что · 22, обозначим через (,, ) минимальную сложность универсальных (, )-УКМ порядка, а затем положим

–  –  –

1. Ложкин С. А., Кошкин М А. О сложности реализации некоторых систем функции алгебры логики контактными многополюсниками.

ДАН СССР. 1988. Т. 298, № 4. С. 807-–811.

2. Лупанов О. Б. О синтезе некоторых классов управляющих систем.

Проблемы кибернетики. Вып.10. М.:Физматгиз, 1963. С. 63–97

3. Редькин Н. П. О реализации систем конъюнкций контактными схемами. Проблемы кибернетики. Вып.30. М.:Наука, 1975. С. 263–276

4. Трусилова И. В. Асимптотическая оценка сложности многополюсника, реализующего одну систему функций. Численные методы в математической физике М.:МГУ, 1986. С. 122–123

5. Ложкин С. А., Кошкин М А. О сложности реализации некоторых систем функции алгебры логики контактными и обобщёнными контактными схемами. Проблемы кибернетики. Вып.3. М.:Наука. Физматлит. 1991. С. 257–285 Применение графических ускорителей для поиска высоковероятностных линейных дифференциальных характеристик современных хэш-функций Абраменкова Марина Анатольевна Кафедра информационной безопасности e-mail: muroni666@gmail.com Научный руководитель: к.ф.-м.н., доц. Карпунин Григорий Анатольевич В современной криптографии важную роль играют хэш-функции, иcпользуемые в схемах электронной цифровой подписи, в протоколах аутенКафедра МК тификации и для проверки целостности сообщений. От криптографической стойкости хэш-функции к атакам поиска коллизий зависит криптостойкость использующей ее схемы электронной цифровой подписи.

Одной из наиболее популярных хэш-функций является SHA-1. Она была опубликована NIST как федеральный американский стандарт в 1995 году.

Современные атаки поиска коллизий SHA-1 основываются на атаке Каньере-Рекбергера [1], которая состоит из двух этапов. На первом этапе хэш-функция линеаризуется и строится линейная дифференциальная характеристика. На втором этапе строится полная дифференциальная характеристика, и с ее помощью ищутся коллизии. Итоговая сложность атаки напрямую зависит от веса Хэмминга линейной дифференциальной характеристики [2].

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

Целью выпускной квалификационной работы является построение линейной дифференциальной характеристики минимального веса для SHA-1 и обоснование минимальности ее веса.

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

В выпускной квалификационной работе с помощью реализаций алгоритмов Шабо [3], Штерна и Бернштейна-Ланг-Петерса на графических ускорителях с поддержкой технологии CUDA [4] найдена линейная дифференциальная характеристика SHA-1 веса 237. Характеристика совпадает с опубликованной в статье [2].

Используя теоретическую базу из статьи [5] и реализацию алгоритма Шабо на ГПУ, было получено, что вес 237 с вероятностью близкой к единице является минимальным весом соответствующего кода (вероятность ошибки не превышает 6.242 · 1014 ). Таким образом, поиск оптимальной линейной дифференциальной характеристики SHA-1 можно считать законченным, уменьшить сложность атаки поиска коллизий SHA-1 за счет построения лучшей линейной дифференциальной характеристики не удастся.

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

1. De Canniere C., Rechberger C. Finding SHA-1 Characteristics: General Results and Applications. Advances in Cryptology – ASIACRYPT 2006, vol. 4284 of Lecture Notes in Computer Science, pp. 1-20. Springer, 2006.

2. Pramstaller N., Rechberger C., Rijmen V. Exploiting coding theory for collision attacks on SHA-1. Cryptography and Coding 2005, vol. 3796 of Lecture Notes in Computer Science, pp. 78–95. Springer-Verlag, Berlin, 2005.

3. Chabaud F. On the Security of Some Cryptosystems Based on Errorcorrecting Codes. Proceedings of EUROCRYPT 1994, vol. 950 of Lecture Notes in Computer Science, pp. 131–139. Springer, 1995.

4. Сандерс Д., Кэндрот Э. Технология CUDA в примерах: введение в программирование графических процессоров. ДМК Пресс, 2011.

5. Leon J.S. A probabilistic algorithm for computing minimum weights of large error-correcting codes. IEEE Transactions on Information Theory, vol. 34(5), pp. 1354–1359, 1988.

–  –  –

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

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

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

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

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

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

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

Теорема. Существует алгоритм со сложностью (4 2 ) битовых операций, который по порождающей матрице кода (, )[] находит перестановку такую, что (, )[] = (, )[].

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

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

Такое возможно, когда матрица секретного ключа криптосистемы представима в следующем виде:

( ) = 0

–  –  –

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

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

Криптосистема Мак-Элиса–Сидельникова была предложена В. М. Сидельниковым в 1994 году [1] и является модификацией известной кодовой криптосистемы Мак-Элиса [2]. Данная криптосистема строится на основе

-кратного использования кодов Рида–Маллера. В работе И. В. Чижова [3] дается описание некоторых достаточно больших классов эквивалентных ключей специального вида.

В выпускной квалификационной работе изучалось пространство эквивалентных ключей для криптосистемы Мак-Элиса–Сидельникова с параметром = 2, построенной на кодах Рида–Маллера с параметрами = 2, = 6. Был предложен достаточно эффективный алгоритм построения класса эквивалентности для данного секретного ключа. Удалось значительно снизить сложность алгоритма по сравнению со сложностью полного перебора: в среднем 216 опробований перестановок, которые могут потенциально обеспечить эквивалентность ключей. В то время как алгоритм полного перебора имеет сложность 2128 опробований перестановок.

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

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

Время работы 290м 160м 120м 20м 145с 105с 99c 98c Время работы 98с 97с 95с 93с Из таблицы видно, что начиная с некоторого значения параметра, время работы программы достигает своего минимального значения и далее почти не отклоняется от него. Данные результаты могут быть использованы в будущем для аналитического описания классов эквивалентных секретных ключей криптосистемы Мак-Элиса–Сидельникова.

Литература

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

2. McEliece Robert J. A public-key cryptosystem based on algebraic coding theory. // DSN progress report, 1978. Vol. 42, no. 44. P. 114–116.

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

3. Чижов И. В. Пространство ключей криптосистемы Мак-Элиса– Сидельникова. Ph. D. thesis / И. В. Чижов; Московский государственный университет имени М. В. Ломоносова, 2010

–  –  –

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

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

Для сравнения двух нейросетевых дескрипторов применяется оценочная функция JointBayesian [2] (, ) = T + T + 2T Чем больше получаются значения этой функции на выходе, тем более вероятно то, что личности людей на двух изображениях совпадают. Оптимальные значения матриц, определяются EM алгоритмом по обучающей выборке. Поиск изображения в базе при решении задачи идентификации сводится к вычислению значений оценочной функции для всех изображений в базе и изображения из запроса с последующей сортировкой по убыванию.

Главным результатом работы является реализация алгоритма распознавания лиц и его интеграция в библиотеку алгоритмов анализа лиц FaceSDK [3]. Экспериментальная оценка на базах изображений лиц [4,5] показала, что алгоритм значительно превосходит по точности обычные методы распознавания лиц, основанные на дескрипторах. При этом сохраняется возможность работы в реальном времени на современных процессорах для видео высокого разрешения. Время вычисления дескриптора Кафедра АСВК для одного изображения менее 60ms. При обучении сверточной нейронной сети и параметров оценочной функции использовалась выборка лиц CASIA-WebFace от авторов статьи [1].

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

Экспериментально установлено, что увеличение обучающей выборки за счет локальных преобразований изображений позволяет повысить точность классификации с 95.6% до 97% на выборке [4].

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

Одной из дополнительных задач, поставленных в выпускной квалификационной работе, стала классификация пола человека по изображению лица. Реализованный классификатор показывает точность 97.5% на открытой выборке лиц [4]. В качестве классификатора используется метод опорных векторов с линейным ядром, обученный на нейросетевых дескрипторах изображений.

–  –  –

2. Cao, Xudong and Wipf, David and Wen, Fang and Duan, Genquan and Sun, Jian. A practical transfer learning algorithm for face verification // IEEE Computer Vision (ICCV). – P. 3208-3215, 2013.

3. FaceSDK – программная библиотека алгоритмов анализа лиц людей [HTTP] http://www.tevian.ru/ru/products/facesdk

4. Huang, Gary B and Ramesh, Manu and Berg, Tamara and LearnedMiller, Erik. Labeled faces in the wild: A database for studying face recognition in unconstrained environments // Technical Report 07-49, University of Massachusetts, Amherst, 2007.

5. Phillips, P Jonathon and Wechsler, Harry and Huang, Jeffery and Rauss, Patrick J The FERET database and evaluation procedure for facerecognition algorithms //Image and vision computing. – P. 295-306, 1998.

Отделение бакалавриата Алгоритм поиска перепутанных ракурсов в стереовидео Лаврушкин Сергей Валерьевич Кафедра автоматизации систем вычислительных комплексов e-mail: slavrushkin@graphics.cs.msu.ru Научный руководитель: Ватолин Дмитрий Сергеевич За последние несколько лет интерес зрителей к фильмам в 3D снизился. Вызвано это рядом проблем стереокинематографа, к которым в первую очередь относятся проблемы качества создаваемого контента. Существуют различные артефакты стереовидео, способные вызвать дискомфорт при просмотре фильмов в 3D. К таким артефактам относится и перепутанный порядок ракурсов в сценах.

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

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

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

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

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

Четвертый алгоритм базируется на том факте, что в левом ракурсе области открытия (видимые в данном ракурсе и невидимые в другом) находятся слева от объекта переднего плана, а в правом — справа. Поиск областей открытия осуществляется с помощью метода OCC (occlusion constraint) [4]. Для найденных областей открытия строится карта доверия.

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

В пятом алгоритме анализируются области открытия/закрытия по движению. Для поиска областей открытия/закрытия используется меКафедра АСВК тод OCC-Ince-Conrad [5]. Для каждой точки области открытия/закрытия алгоритм находит предположительную точку, которая перекрывает её в другом кадре, и анализирует значения глубины в соседних к найденным точкам областях.

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

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

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

Предложенный метод — 0,9869;

Метод, описанный в работе [2], — 0,8376.

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

Литература

1. Knee M. Getting machines to watch 3d for you // SMPTE Motion Imaging Journal. – 2012. – Т. 121. – №. 3. – С. 52-58.

2. Shestov A., Voronov A., Vatolin D. Detection of swapped views in stereo image // 22st GraphiCon International Conference on Computer Graphics and Vision. – 2012. – С. 23-27.

3. Simonyan K., Grishin S., Vatolin D., Popov D. Fast video superresolution via classification // Proceedings of IEEE International Conference on Image Processing. – 2008. – С. 349–352.

4. Egnal G., Wildes R. P. Detecting binocular half-occlusions: Empirical comparisons of five approaches // IEEE Transactions on Pattern Analysis and Machine Intelligence. – 2002. – Т. 24. – №. 8. – С. 1127Ince S., Konrad J. Geometry-based estimation of occlusions from video frame pairs // IEEE International Conference on Acoustics, Speech, and Signal Processing. – 2005. – Т. 2. – С. 933-936.

Отделение бакалавриата Исследование и разработка методов динамической аутентификации пользователя на основе специфики его работы с клавиатурой Орпанен Игорь Сергеевич Кафедра автоматизации систем вычислительных комплексов e-mail: igor@orpanen.ru Научный руководитель: Головин Сергей Игоревич Непрерывная аутентификация пользователя в процессе его работы с информационной системой обеспечивает надёжную защиту от несанкционированного доступа к информации. В данной работе исследуется использование особенностей клавиатурного ввода пользователя для решения задачи непрерывной аутентификации.

Решение задачи аутентификации пользователя делится на три этапа:

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

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

3. Принятие решения о легитимности тестируемого пользователя.

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

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

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

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

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

Литература

1. Traore I. et al. Combining mouse and keystroke dynamics biometrics for risk-based authentication in web environments // Digital Home (ICDH), 2012 Fourth International Conference on. – IEEE, 2012. – С. 138-145.

2. Tappert C. C., Villani M., Cha S. H. Keystroke biometric identification and authentication on long-text input // Behavioral biometrics for human identification: Intelligent applications. – 2009. – С. 342-367.

3. Teh P. S., Teoh A. B. J., Yue S. A survey of keystroke dynamics biometrics // The Scientific World Journal. – 2013. – Т. 2013.

Сопоставление изображений магнитно-резонансной томографии головного мозга человека на основе ключевых точек Зобнин Денис Станиславович Кафедра автоматизации систем вычислительных комплексов e-mail: d.zobnin.study@gmail.com Научный руководитель: к.ф.-м.н. Сенюкова Ольга Викторовна Анализ медицинских изображений — одна из наиболее актуальных и трудоемких задач компьютерного зрения. Задача сопоставления (регистрации) двух изображений заключается в нахождении такого преобразования первого изображения, что результат максимально похож на второе изображение. В медицине особую важность имеет точность сопоставления анатомических структур, так как регистрация является подзадачей в процессе автоматической сегментации изображения на анатомические структуры или выявления патологии.

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

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

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

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

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

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

Третий этап — вычисление нелинейного преобразования (сплайнповерхности, или -сплайна [2]). Координаты ключевых точек на изображениях и определяют систему уравнений, из которых находятся параметры преобразования.

Экспериментальная оценка предложенного метода проводилась на реальных медицинских данных, метод сравнивался с алгоритмом Symmetric normalization [3] — одним из лучших нелинейных алгоритмов регистрации на данный момент ([4]). Экспериментальная оценка показала Кафедра АСВК улучшение времени работы (с 5.09 сек до 1.097 сек на одной паре срезов), улучшение качества сопоставления основных анатомических структур мозга.

Литература

1. Guerrero R., Pizarro L., Wolz R., Rueckert D. Landmark localization in brain MR images using feature point descriptors based on 3D local selfsimilarities // IEEE International Symposium on Biomedical Imaging.

Barcelona, Spain, 2012. P. 1535–1538.

2. Davis M. H., Khotanzad A., Flamig D. P., Harms S. E. A physics-based coordinate transformation for 3-D image matching // IEEE Transactions on Medical Imaging. 1997. 16. N 3. P. 317–328.

3. Avants B., Epstein C., Grossman M., Gee J. Symmetric diffeomorphic image registration with cross-correlation: evaluating automated labeling of elderly and neurodegenerative brain // Medical image analysis, 2008.

12. N 1. P. 26–41.

4. Klein A., Andersson J., Ardekani B. A. et al. Evaluation of 14 nonlinear deformation algorithms applied to human brain MRI registration // Neuroimage. 2009. 46. N 3. P. 786–802.

Разработка алгоритма отображения виртуальных ресурсов на физические в программно-конфигурируемых сетях Быковец Евгений Владимирович Кафедра автоматизации систем вычислительных комплексов e-mail: bykovetsevgeniy@lvk.cs.msu.su Научный руководитель: к.ф.-м.н., м.н.с. Шалимов Александр Владиславович Термин «виртуализация» в самом широком смысле означает создание некоторого виртуального ресурса посредством разделения ресурсов его физического аналога. В современных системах примеров виртуализации ресурсов достаточно много: аппарат виртуальной памяти, виртуализация на уровне операционной системы, а также виртуализация целой платформы и т. д. В настоящей работе рассмотрен другой тип вирутализации – виртуализация компьютерных сетей.

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

существуют подходы основанные на изучении заголовков пакета (VLAN), Отделение бакалавриата на технологии туннелирования (VXLAN, NVGRE), а также на основе тегирования сетевого трафика (MPLS-VPN). Однако эти подходы имеют ряд недостатков: необходимость каждый раз перенастраивать оборудование, накладные расходы на инкапсуляцию пакета, влияние трафика одной виртуальной сети на другую, так как разделяется общее физическое оборудование. Однако в программно-конфигурируемых сетях (ПКС) большая часть этих недостатков нивелируется.

Концепция ПКС заключается в разделении уровня управления сетью и уровня передачи данных. Уровень управления характеризуется ПКСконтроллером, в котором сосредоточена вся логика работы сети (управление потоками трафика, политиками маршрутизации и т. д.). Уровень передачи данных характеризуется программно-конфигурируемыми коммутаторами, задача которых заключается в передаче сетевого трафика в соответствии с правилами, установленными контроллером.

Технология ПКС нашла широкое применение в центрах обработки данных (ЦОД) [1], работающих по принципу IaaS (Infrastructure-as-a-Service), суть которого заключается в предоставлении конфигурируемых вычислительных и сетевых ресурсов, а также хранилищ данных корпоративным клиентам для решения их бизнес-задач. Поэтому ключевым понятием становится SLA (Service Level Agreement), который выступает, в первую очередь, своего рода метрикой, позволяющей описывать требования клиентов к ожидаемой услуге, а ЦОДу возможность предоставлять услугу в соответствии с этими требованиями.

На данный момент существует два многофункциональных средства вирутализации ПКС – FlowVisor и OpenVirteX [2]. Однако возможности данных средств не позволяют построить отображение логической сети с произвольной топологией на произвольную физическую инфраструктуру, предоставляя возможность задавать логические топологии лишь в виде большого коммутатора ("big switch"), либо проводить более сложные отображения вручную. В рамках данной работы предложен эвристический алгоритм, решающий данную задачу, позволяя задавать сложные виртуальные топологии, состоящие из большого числа коммутаторов и конечных узлов, а также учитывать SLA на пропускную способность виртуальных каналов.

Алгоритм опирается на аппарат минимальных деревьев Штейнера [3].

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

Разработанный алгоритм состоит из четырех логических шагов:

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

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

3. Построение отображения для неграничных виртуальных коммутаторов (по принципу «один-к-одному»).

4. Построение отображения для оставшихся виртуальных каналов.

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

Литература

1. Jain R., Paul S. Network virtualization and software defined networking for cloud computing: a survey. IEEE, Communications Magazine, 2013

2. Al-Shabibi A., De Leenheer M. OpenVirteX: Make Your Virtual SDNs Programmable. New York, NY, USA, 2014

3. Bang Y. W., Kun-Mao C. Steiner Minimal Trees. Chapman & Hall/CRC Press, USA, 2004 Разработка и реализация алгоритма синхронизации времени для среды имитационного моделирования DYANA Кибитова Валерия Николаевна Кафедра автоматизации систем вычислительных комплексов e-mail: kibitovavaleria@gmail.com Научный руководитель: ассистент Волканов Дмитрий Юрьевич В системах распределенного дискретно-событийного моделирования существенное влияние на скорость выполнения оказывает алгоритм синхронизации времени [1], использующийся в системе. Выбрав наиболее подходящий для соответствующей модели алгоритм синхронизации, можно существенно сократить время проведения экспериментов с ней. В лаборатории Вычислительных Комплексов была разработана распределенная Отделение бакалавриата система дискретно-событийного моделирования DYANA, в которой изначально был реализован консервативный алгоритм синхронизации времени. При использовании данного алгоритма, велика вероятность того, что на некоторых моделях время простоя вычислительных ресурсов будет существенным.

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

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

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



Pages:   || 2 | 3 | 4 |
Похожие работы:

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

«413 вычислительные методы и программирование. 2012. Т. 13 УДК 536.75, 538.9 ПРОГРАММА MEL АТОМИСТИЧЕСКОГО МОДЕЛИРОВАНИЯ ФУНКЦИОНАЛЬНЫХ СЛОЕВ СОЛНЕЧНЫХ ЭЛЕМЕНТОВ Ф. В. Григорьев1, А. Н. Романов1, И. В. Офркин2, А. В. Сулимов2, В. Б. Сулимов1,2 e Предложен и реализован новый метод ато...»

«8326 УДК 519.6 ОБОБЩЕНИЕ МАРЬЯЖНОЙ ТЕОРЕМЫ ХОЛЛА ДЛЯ ЗАДАЧИ УПРАВЛЕНИЯ ПОРЯДКОМ ВЕТО-ГОЛОСОВАНИЯ Н.М. Новикова Вычислительный центр им. А.А. Дородницына РАН Россия, 119333, Москва, Вав...»

«Вычислительные технологии Том 18, № 4, 2013 Численное моделирование течений вязкого теплопроводного газа в канале В. В. Шайдуров1,2, Г. И. Щепановская1, М. В. Якубович1 Институт вычислительного моделирования СО РАН, Красноярск, Россия Университет Бейхан, Пекин, Китай e-mail: shaidurov04@gmail.co...»

«37 вычислительные методы и программирование. 2012. Т. 13 УДК 539.1+537.31 AB INITIO МОЛЕКУЛЯРНАЯ ДИНАМИКА: ПЕРСПЕКТИВЫ ИСПОЛЬЗОВАНИЯ МНОГОПРОЦЕССОРНЫХ И ГИБРИДНЫХ СУПЕРЭВМ П. А. Жиляев1, В. В. Стегайлов1 Представлен обзор р...»

«А.В. Гвоздев, И.С. Лебедев, И.А. Зикратов Для дальнейшей работы над представленным методом целесообразно описать и оценить: выбор параметров модели (алгоритм принятия решения, задачи классификации образов); информативность признаков...»

«111 вычислительные методы и программирование. 2010. Т. 11 УДК 519.6 ПРИМЕНЕНИЕ СУПЕРКОМПЬЮТЕРОВ ДЛЯ МОЛЕКУЛЯРНО-ДИНАМИЧЕСКОГО МОДЕЛИРОВАНИЯ ПРОЦЕССОВ В КОНДЕНСИРОВАННЫХ СРЕДАХ А. В. Янилкин1, П. А. Жиляев1, А. Ю. Куксин1, Г. Э. Норман1, В. В. Писарев1, В...»

«Вычислительные технологии Том 12, № 5, 2007 ИССЛЕДОВАНИЕ (m, 2)-МЕТОДОВ РЕШЕНИЯ ЖЕСТКИХ СИСТЕМ E. A. Новиков Институт вычислительного моделирования СО РАН, Красноярск, Россия e-mail: novikov@icm.krasn.ru The (m, 2)-methods are investigated. It has been shown that the maximum order of accuracy for the...»

«Министерство образования Республики Беларусь Учреждение образования "Белорусский государственный университет информатики и радиоэлектроники" Кафедра вычислительных методов и программирования А.И. Волковец, А.Б. Гуринович ТЕОРИЯ ВЕРОЯТНОСТЕЙ И МАТЕМАТИЧЕСКАЯ СТАТИСТИКА К...»

«ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ Корнилов И. И., Марыкова Л. А. Основы построения инфоко...»

«КАБАРДИНО-БАЛКАРСКИЙ НАУЧНЫЙ ЦЕНТР ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ ИНФОРМАТИКИ И ПРОБЛЕМ РЕГИОНАЛЬНОГО УПРАВЛЕНИЯ (ИИПРУ КБНЦ РАН) 360000, г.Нальчик, ул. И. Арманд 37А. тел. (866-2) 426562 fax: (866-2) 426562 E-m ail: iipru@rambler.ru ОКПО 00900927 ОГРН 1030...»

«Автоматика. Информатика. Управление. Приборы УДК 621.396.23 DOI: 10.17277/vestnik.2015.01.pp.007-015 СИНТЕЗ ЭНЕРГОСБЕРЕГАЮЩЕГО УПРАВЛЕНИЯ Н. Г. Чернышов1, С. И. Дворецкий2 Кафедры: "Электроснабжение, электротехника и информационное...»

«Вычислительные технологии Том 12, № 1, 2007 ЯЗЫК РАЗМЕТКИ КОМПЬЮТЕРНЫХ ПИКТОГРАММ IcoML КАК ИНСТРУМЕНТ ОПИСАНИЯ ИНФОРМАЦИИ В СЕМАНТИЧЕСКОЙ СЕТИ М. Н. Гранин, И. В. Бычков Институт динамики систем и теории управления СО РАН, Иркутск, Россия e-mail: graninico@granin.com,...»

«ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ТЕЛЕКОММУНИКАЦИЯМ “УТВЕРЖДАЮ” Председатель Государственного комитета Российской Федерации по телекоммуникациям Л.Д. Рейман 19 октября 1999 года МЕТОДИКА ПРОВЕДЕНИЯ РАБОТ ПО КОМПЛЕКСНОЙ УТИЛИ...»

«Министерство сельского хозяйства и продовольствия Республики Татарстан ГУП РТ "Республиканский информационно-вычислительный центр" Минсельхозпрода Республики Татарстан Служба информационно-консультационного обслуживания АПК РТ Новая технология выращивания картофеля...»

«АКАДЕМИЯ НАУК СССР ИНСТИТУТ ЯЗЫКОЗНАНИЯ ВОПРОСЫ ЯЗЫКОЗНАНИЯ ЖУРНАЛ ОСНОВАН В 1952 ГОДУ ВЫХОДИТ 6 РАЗ В ГОД МАЙ ИЮНЬ ИЗДАТЕЛЬСТВО "НАУКА" МОСКВА — 1 9 8 6 СОДЕРЖАНИЕ Б у д а г о в Р. А. (Москва;. АА. Потебня как языковед-мыслитель (К 15...»

«ТОРШИН В.В. Спиральные образования в природе и электродинамике МОСКВА 2008 ТОРШИН В.В. Спиральные образования в природе и электродинамике ИЗДАТЕЛЬСТВО "ЦП ВАСИЗДАСТ" МОСКВА 2008 -2НО 2 М3/02 УДК 621. 362.533.4/531.3 Рецензенты:...»

«План занятий в 5-х классах. Троицкий лицей. 2008-11-15 1 Календарно-тематическое планирование кружка Информатика для 5-х классов Преподаватель Л.Г.Куркина (Троицкий лицей), консультант Ф.В.Ткачев (Институт ядерных исследований РАН) Троицкий лицей 15 ноября 2008 г. Программа зан...»

«Геология и геофизика, 2012, т. 53, № 6, с. 797—812 УДК 550.837.22 РЕШЕНИЕ ПРЯМОЙ И ОБРАТНОЙ ЗАДАЧ МЕТОДА ЕЭП НА ОСНОВЕ УТОЧНЕННОЙ МОДЕЛИ ПРИРОДЫ ЕСТЕСТВЕННОГО ЭЛЕКТРИЧЕСКОГО ПОЛЯ* А.Н. Дмитриев Институт геологии и гео...»

«ИНФОРМАТИКА 2004 июль-сентябрь №3 ОБРАБОТКА СИГНАЛОВ И ИЗОБРАЖЕНИЙ УДК 681.3 Д.О. Чехлов, С.В. Абламейко НОРМАЛИЗАЦИЯ ИЗОБРАЖЕНИЙ ОТНОСИТЕЛЬНО ПЕРСПЕКТИВНОГО ПРЕОБРАЗОВАНИЯ НА ОСНОВЕ ГЕОМЕТРИЧЕСК...»

«Соколова Анна Викторовна МИКРОСКОПИЧЕСКАЯ ДИАГНОСТИКА НЕКОТОРЫХ ВИДОВ РОДА RANUNCULUS L. АМУРСКОЙ ОБЛАСТИ ПО СТРОЕНИЮ СТЕБЛЯ И ЭПИДЕРМЫ ЛИСТА В статье приведен сравнительный анализ строения стебля и эпидермы листа 4-х видов рода Ranunculus L., произрастающих в Благовещенском районе Амурской области. Впервые определены в...»

«Задания открытой олимпиады для школьников по информатике города Липецка "СуперБит" 6 классы. Апрель 2015. Вариант 1. Время выполнения: 40 минут. Количество задач: 10. Вариант 1. № Текст задания ВарианПравильБаллов ты ный ответ за задаответов ние Задача. Давайте познакомимся ТАБАКОВ До...»

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

«Главные управления (национальные банки) Центрального банка Российской Федерации Департамент полевых учреждений № 51-Т от 27.03.2013 Межрегиональный центр О форме договора об обмене информатизации Банка России электронными сообщениями при переводе денежных средств в рамках Первое операционное платежной си...»

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

«1 ПОЯСНИТЕЛЬНАЯ ЗАПИСКА к завершенной предметной линии учебников "Информатика" для 7 – 9 классов общеобразовательных организаций Авторы: Угринович Н.Д. ООО "БИНОМ. Лаборатория знаний" Завершенная предметная линия учебников "Информатика" для 7 9 классов включает в се...»

«Программа курса "Компьютерная графика". 1. Организационно-методический раздел 1.1 Название курса Компьютерная графика Направление – 552800 Информатика и вычислительная техника. Раздел – общепрофессиональные дисциплины. Компонент – федеральный.1.2 Цели и задачи курса Основная цель курса: ознакомить студентов с основными задачами м...»

«Московский Государственный Университет имени М.В. Ломоносова Факультет вычислительной математики и кибернетики Кафедра системного программирования Курсовая работа на тему: "Норма...»








 
2017 www.doc.knigi-x.ru - «Бесплатная электронная библиотека - различные документы»

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