авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

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


Pages:   || 2 | 3 | 4 | 5 |
-- [ Страница 1 ] --

Министерство образования и науки Российской Федерации

Московский государственный университет им. М.В. Ломоносова

Факультет Вычислительной математики и кибернетики

СОВЕТ МОЛОДЫХ УЧЁНЫХ

ВМК МГУ

Сборник тезисов

XX Международной научной конференции студентов,

аспирантов и молодых учёных

«ЛОМОНОСОВ-2013»,

секция

«ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА И КИБЕРНЕТИКА»

Москва МГУ имени М. В. Ломоносова 9–12 апреля 2013 г.

УДК 517.6+519.8 ББК 22 Л75 Организационный комитет Международной молодежной научной олимпиады «Ломоносов-2013»

Сопредседатель Сопредседатель Организационного комитета Организационного комитета Ректор МГУ им. М.В. Ломоносова, Министр образования и науки академик В. А. Садовничий Российской Федерации Д. В. Ливанов Организационный комитет XX Международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов-2013»

секции «Вычислительная математика и кибернетика»:

Е.И. Моисеев (председатель), Шевцова И.Г. (ответственный секретарь), Нефедова Ю.С. (зам. отв.

секретаря), Гончаров О.И., Дарьин А.Н., Дмитриев Л.В., Дьяконов А.Г., Капалин И.В., Конушин А.С., Корухова Ю.С., Майсурадзе А.И., Месяц А.И., Мокин А.Ю., Ровенская Е.А., Сальников А.Н., Федорова В.С., Холомеева А.А..

Ломоносов-2013: Материалы XX Международной научной конференции студентов, Л аспирантов и молодых ученых: секция «Вычислительная математика и кибернетика»;

9-12 апреля;

Москва, МГУ имени М.В. Ломоносова, факультет ВМК: Сборник тезисов/Сост. Месяц А.И., Шевцова И.Г. – М.: Издательский отдел факультета ВМК МГУ (лицензия ИД 05899 от 24.09.2001)), 2013. – 156с.

ISBN: 978-5-89407-507- В настоящий сборник вошли тезисы докладов участников Международной научной конференции «Ломоносов-2013» по секции «Вычислительная математика и кибернетика». Тематика тезисов очень разнообразна и охватывает многие актуальные проблемы современной фундаментальной науки. Все представленные в сборнике материалы были рекомендованы к публикации Экспертным советом секции. Тезисы публикуются в том виде, в котором были представлены авторами, они не редактировались, а были лишь приведены к единому формату.

УДК 517.6+519. ББК Издательский отдел факультета вычислительной математики и кибернетики МГУ имени М.В. Ломоносова, ISBN 978-5-89407-507- Месяц А.И., Шевцова И.Г., составление, оформление, Содержание Программирование Абдрахманова Алёна Маратовна Использование двумерных штрихкодов для создания системы по зиционирования в помещении........................................ Гайворонская Светлана Александровна, Гамаюнов Денис Юрьевич Иерархическая топология декомпозированных алгоритмов для об наружения вредоносного исполнимого кода.......................... Азимов Александр Евгеньевич Метод автоматического исправления ошибок сочетаемости слов в текстах............................................................... Бурцев Александр Павлович Моделирование волновых процессов в задачах сейсморазведки на суперкомпьютерах “Ломоносов” и BlueGene/P....................... Глонина Алевтина Борисовна Применение метамоделей для задачи выбора механизмов обеспече ния отказоустойчивости распределенных вычислительных систем реального времени (МОО РВС РВ).................................. Дашкевич Антон Дмитриевич Решение систем уравнений гиперболического типа на графических процессорах с использованием технологии CUDA................... Ефимов Александр Юрьевич Интерфейс на основе шаблонных классов С++ для работы с боль шими типизированными файлами................................... Захаров Илья Сергеевич Моделирование окружения драйверов операционной системы Linux для поддержки процесса статической верификации................. Зорин Даниил Александрович Преобразования расписаний в итерационных алгоритмах структур ного синтеза вычислительных систем................................ Климов Георгий Петрович Эффективное использование графических процессоров в задачах глобальной оптимизации............................................ Левоневский Дмитрий Константинович Применение метода временных рядов для определения влияния DDoS-атак на системный и сетевой трафик сервера................. Манжосов Андрей Николаевич Генерация входных описаний для планировщика по моделям на языке UML........................................................... Москвин Вадим Викторович Разработка новых методов повышения надежности устройств управления.......................................................... Москвин Максим Викторович Цифровая модель искусственного нейрона на элементах автомат ной памяти.......................................................... Конференция Ломоносов – Новиков Константин Викторович Исследование и программная реализация алгоритма кластеризации в терминологической сети............................................ Седов Никита Викторович Подходы к компьютерному моделированию нейрона: история и пер спективы............................................................. Пашков Василий Николаевич О подходе к обеспечению отказоустойчивости контроллера в программно-конфигурируемых сетях................................ Смагин Сергей Владимирович Комплекс программ для индуктивного формирования баз медицин ских знаний в форме, принятой в медицинской литературе........ Дискретная математика и анализ данных Абдиримов Кудрат Рахимберганович Поиск логических закономерностей в форме полуплоскостей....... Александров Ярослав Алексеевич Оптимизация размещения инфраструктуры нефтяного месторож дения................................................................. Артюхин Станислав Геннадьевич Автоматическое распознавание статичных жестов с помощью Kinect на примере дактильной азбуки............................... Будников Егор Алексеевич Адаптивный одноклассовый классификатор при представлении объектов бинарными признаками................................... Горелов Алексей Анатольевич Восстановление зерновых вершин графа, полученного поиском в ширину............................................................... Дерябин Максим Анатольевич, Зайцев Александр Александрович Моделирование и исследование пороговой схемы разделения секре та на основе системы остаточных классов........................... Бухман Антон Владимирович О сложности распознавания периодичности булевых функций, за данных полиномами.................................................. Зимовнов Андрей Вадимович, Фигурнов Михаил Викторович Метод поиска аксессуаров к товарам интернет-магазина на основе рекомендательной системы........................................... Калистратова Ольга Евгеньевна Методы информационного поиска для определения настроения му зыки.................................................................. Кушнир Олеся Александровна Вычисление меры парного различия скелетных графов посред ством выравнивания цепочек примитивов........................... Кондрашкин Дмитрий Андреевич Критерии представления функции многих переменных в виде сум мы функций меньшего числа переменных........................... Кириллов Александр Николаевич Настройка линейной модели рекомендательной системы............ Секция Вычислительная математика и кибернетика Осипян Артур Аркадьевич О некоторых каналах связи.......................................... Мартьянов Евгений Александрович Методика оценки защищенности информационного объекта......... Прокашева Ольга Владимировна Классификация на основе анализа формальных понятий........... Сабурова Мария Ивановна О теоретических свойствах новой схемы кодирования неструктури рованной информации................................................ Твердохлеб Юлия Владимировна Вейвлет-преобразование в задаче разделения профиля поверхно сти................................................................... Четвёркин Илья Игоревич Кластеризация оценочных слов по тональности на основе марков ских случайных полей............................................... Численные методы и математическое моделирование Аникеев Фёдор Александрович Суперкомпьютерное моделирование кинетики тороидальной плаз мы методом Монте–Карло........................................... Гришанин Алексанр Андреевич Разработка и исследование численных моделей квантовых точек... Бикулов Дмитрий Александрович Математическая модель пульсового течения крови.





................. Дайлова Екатерина Александорвна Модель оптимального поведения агентов на двухэтапном рынке.... Матвеев Сергей Александрович Вычисление тензорного ранга за конечное число операций.......... Никольский Илья Михайлович Об эффективности некоторых параллельных предобуславливате лей.................................................................... Муратов Максим Викторович, Санников Александр Владимирович, Фаворская Алена Владимировна Моделирование волновых процессов в трещиноватых геологиче ских средах........................................................... Новикова Алина Олеговна Численные методы построения множеств достижимости нелиней ных управляемых систем на основе параллельных вычислений..... Устинов Владислав Дмитриевич Параметрическая зависимость между распределением частиц по размерам и экстремумами дифракционной картины в лазерной ди фрактометрии эритроцитов......................................... Юрова Александра Сергеевна Технология построения расчетных сеток в задачах биомедицины... Никишин Николай Глебович Моделирование электронной структуры молекулярной системы при фазовом переходе второго рода в аморфном углероде............... Конференция Ломоносов – Романенко Алексей Александрович Оптимизация числа базовых алгоритмов в агрегирующем алгорит ме В. Вовка........................................................... Сучков Егор Петрович Применение метода эпсилон сетей для решения обратных задач на суперкомпьютерах.................................................... Чижов Иван Владимирович, Бородин Михаил Алексеевич Атака на криптосистему Мак-Элиса, построенную на основе кодов Рида–Маллера........................................................ Стохастический анализ Андреев Николай Анатольевич Численное исследование книги лимитированных заявок для рынка акций, движимого заявками......................................... Иванов Сергей Валерьевич О решении двухуровневой задачи стохастического программирова ния с квантильным критерием и дискретным случайном парамет ром.................................................................. Щербинин Виктор Владимирович Сравнение различных подходов к построению системы аксиом при аксиоматическом подходе к распознаванию нештатного поведения динамических систем................................................. Черток Андрей Викторович Моделирование потоков заявок на финансовых рынках............. Наумов Алексей Александрович Полукруговой закон для случайных матриц с зависимыми элемен тами.................................................................. Компьютерная графика Акимов Дмитрий Александрович Выделение полупрозрачных частиц переднего плана в видео на ос нове анализа резкости кадра......................................... Белоус Александр Константинович Обнаружение различий резкости в стереовидео...................... Боков Александр Александрович Оценка несоответствия резкости границ в конвертированном 3D видео................................................................ Буланова Юлия Анатольевна Алгоритм выделения области кисты на маммограмме............... Гитман Юрий Александрович Автоматическое построение карты распределения внимания зрите ля по площади кадра................................................. Гурьянов Антон Константинович Построение сеток излучательности на графических процессорах.... Кононов Владимир Андреевич Быстрая реидентификация людей в видеоархиве.................... Ерофеев Михаил Викторович Разработка стабильного во времени метода матирования объектов переднего плана в видео............................................ Секция Вычислительная математика и кибернетика Гусев Владимир Юрьевич Геометрическая коррекция спутниковых изображений............. Меркулов Кирилл Дмитриевич Разработка стереоинструментов в расширенной реальности........ Лахтионова Инна Сергеевна Оценка формирования когнитивных карт пространства при помо щи технологии виртуальной реальности CAVE..................... Людвиченко Виталий Андреевич Улучшение качества цветокоррекции в стереовидео................ Новикова Татьяна Владимировна Распознавание текста на фотографиях с учетом высокоуровневой информации......................................................... Новоторцев Леонид Владимирович Использование особенностей бинокулярного зрения человека в за даче разработки алгоритма тональной компрессии................ Самсонов Павел Андревич Эффективные способы моделирования многослойных покрытий на основе аппроксимации двулучевой функции отражения............ Савичева Светлана Владимировна Автоматизированная система распознавания наложенных деталей на конвейере........................................................ Харенко Максим Викторович Автоматический выбор метода построения карт салиентности для видеопоследовательностей.......................................... Свистунов Сергей Сергеевич Интерактивный рендеринг при помощи сферических дизайнов.... Сумин Денис Александрович Метод быстрого построения оптического потока в применении к задаче сопоставления ракурсов стереоизображения................ Федоров Алексей Александрович Полуавтоматическое определение характеристик 3D-устройств.... Дифференциальные уравнения и оптимальное управление Абдукаримов Махмадсалим Файзуллоевич Граничное управление вынужденными колебаниями на одном кон це струны и его приложения........................................ Аванесян Сергей Вагинакович О свойствах решений одной линейной однородной системы диффе ренциальных уравнений............................................. Аристов Анатолий Игоревич Об одном нелинейном соболевском уравнении...................... Вещинская Виктория Валерьевна Уравнение переноса с разрывными коэффициентами и метод ха рактеристик........................................................ Атамась Евгений Иванович Построение передаточной функции инвертора динамической систе мы произвольного относительного порядка......................... Конференция Ломоносов – Галанина Анна Михайловна Развитие двумерных локальных возмущений в потоке слабопрово дящего газа в магнитном поле...................................... Гайнуллова Светлана Ришатовна Каскадный поиск особенностей отображений для функционалов, подчиненных сходящимся рядам................................... Исаков Виктор Александрович Квазиакустическая схема для уравнений Эйлера газовой динамики Лихоманенко Татьяна Николаевна О базисности одной тригонометрической системы, возникающей в задаче Франкля..................................................... Комарова Елена Станиславовна Моделирование течения жидкости в каналах и влияние ширины канала на получаемое решение...................................... Мальцева Анна Всеволодовна Некоторые вычислительные аспекты одновременной стабилизации Нефедов Павел Владимирович Об одной неклассической задаче для уравнения Лапласа в круге с граничным условием специального вида............................ Нестеренко Юрий Русланович Матричные канонические формы относительно преобразований унитарного подобия................................................. Рогожников Алексей Михайлович Оптимизация граничных управлений колебаниями в составном стержне............................................................. Орлов Сергей Михайлович Управляемая модель распространения вируса гриппа A(H1N1).... Самыловский Иван Александрович Об особых режимах в простейшей задаче о движении материаль ной точки с нелинейным сопротивлением и ограниченным расходом топлива.............................................................. Стефонишин Даниил Александрович Аналитический вид обобщенных решений смешанных задач для волнового уравнения в случае неоднородных нелокальных условий, заданных на конечном подмножестве точек струны................ Стрелковский Никита Витальевич К одному методу решения задач гарантирующего управления с неполной информацией для линейных динамических систем...... Сушникова Дарья Алексеевна Методы решения больших плотных систем линейных уравнений, возникающих при дискретизации интегральных уравнений........ Торебек Берикбол Тиллабаевич Об одном аналоге формулы Эйлера для обобщенных тригономет рических функций.................................................. Расписание заседаний.......................... Именной указатель........................... Программирование Использование двумерных штрихкодов для создания системы позиционирования в помещении Абдрахманова Алёна Маратовна Аспирант Факультет ВМК МГУ им. М.В.Ломоносова, Москва, Россия E-mail: web2alyona@mail.ru Изобретение технологии спутниковой связи позволило создать си стему GPS – глобальную систему позиционирования, с помощью ко торой можно определить своё местоположение почти в любой точке планеты. Система GPS хорошо работает на открытом пространстве, но становится практически бесполезной внутри помещения, посколь ку сигнал от спутника сильно ослабляется, проходя через стены. С развитием телекоммуникационных технологий стало возможным со здание сервисов, помогающих определить нахождение пользователя внутри помещения. Потребность в такой технологии может возник нуть у посетителей торговых центров, развлекательных комплексов, аэропортов. Навигация внутри зданий становится одним из наибо лее востребованных мобильных сервисов, который позволит строить карты помещений, прокладывать маршруты между точками в поме щении, находить нужный товар.

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

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

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

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

Литература 1. Google Indoor Maps & Indoor Location: http://www.indoorlbs.

com/2012/04/google-indoor-maps-indoor-location.html 2. Enterprise-Wide Location Tracking Explained: How Does Ekahau RTLS Work? http://www.ekahau.com/ products/real-time-location-system/overview/ how-ekahau-rtls-works.html 3. 2012 Will be the Year of the Chips for Indoor Location: http:

//www.indoorlbs.com/search/label/Broadcom 4. Nokia приспосабливает Bluetooth для навигации внутри поме щений: http://www.ixbt.com/news/hard/index.shtml?15/30/ 5. Системы позиционирования объектов в реальном времени (RTLS): http://www.grog.lv/products_8.php Иерархическая топология декомпозированных алгоритмов для обнаружения вредоносного исполнимого кода Гайворонская Светлана Александровна, Гамаюнов Денис Юрьевич Аспирант, Старший научный сотрудник Факультет ВМК МГУ имени М. В. Ломоносова, Москва, Россия E-mail: sadie@lvk.cs.su.su, gamajun@cmc.msu.su Темой работы является обнаружение вредоносного исполнимого кода в высокоскоростных каналах передачи данных. В рамках рабо ты рассматривается механизм распространения ботнетов с помощь сетевых червей путем эксплуатации уязвимости переполнения буфе ра. Вредоносный код, эксплуатирующий подобную уязвимость, на зывается шеллкодом. Как любой массовый феномен, распростране ние червя проще заметить в крупных масштабах (на высокоскорост ных каналах), чем на оконечных узлах. Таким образом, критичными становятся скорость работы и количество ложных срабатываний ал горитов.

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

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

ii) вычислительная слож ность алгоритма минимальна по сравнению с простой комбинацией алгоритмов;

iii) обеспечивается полное покрытие классов шеллкодов.

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

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

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

Используя набор элементарных классификаторов, можно сфор мулировать задачу автоматической генерации гибридного классифи катора как cоставление ориентированного графа GpV, Eq с опреде ленной топологией, где tV u - множество узлов- классификаторов, а дуги tEu представляют из себя пути следования потока данных.

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

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

• на каждом уровне обеспечивается покрытие всех доступных классов шеллкодов;

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

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

Сравнение скорости работы гибридного классификатора с линейной комбинацией. Тестовые наборы: а) шеллкоды б) легитимные бинарные файлы в) рандомные данные г) мультимедия Литература 1. Y. I. Zhuravlev, Algebraic approach to the solution of recognition or classication problems. Pattern recognition and image analysis, 1998, vol. 8;

no.1, 59- 2. Brett Stone-Gross, Marco Cova, Lorenzo Cavallaro, Bob Gilbert, Martin Szydlowski, Richard Kemmerer, Christopher Kruegel, Giovanni Vigna Your Botnet is My Botnet: Analysis of a Botnet Takeover. Technical report, University of California, May 3. E. Filiol Metamorphism, formal grammars and undecidable code mutation. International Journal of Computer Science,2, Секция Вычислительная математика и кибернетика 4. Cormen T., Leiserson C., Rivest R., Stein S. Introduction to algorithms, 3rd edition // The MIT Press, Cambridge, Massachu setts. 2009.

Метод автоматического исправления ошибок сочетаемости слов в текстах Азимов Александр Евгеньевич Аспирант Факультет ВМК МГУ имени М. В. Ломоносова, Москва, Россия E-mail: mitradir@gmail.com Современные системы редактирования текстов на естественном языке, использующие компьютерные словари и методы синтаксиче ского анализа, выявляют орфографические и частично синтакси ческие ошибки, однако пока не обнаруживают и не корректируют ошибки сочетаемости слов. Подобные лексические ошибки (дать вни мание вместо уделить внимание;

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

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

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

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

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

Описываемый метод был реализован для исправления ошибок со четаемости в английских текстах, написанных русскоязычными ав торами. Для создания базы данных вероятностей синтаксических связей слов был проведен автоматический синтаксический разбор большой коллекции текстов с использованием синтаксического ана лизатора Stanford Parser [2]. Проведенное тестирование продемон стрировало перспективность предложенного метода: в тестовом на боре было обнаружено 80% ошибок сочетаемости, причем 87% по строенных вариантов коррекции предложения включали в себя линг вистически верный вариант исправления.

Литература 1. Brockett C. Dolan W. Gamon M. Correcting ESL Errors Using Phrasal SMT Techniques // In Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics ACL, Sydney, Australia, 2. Stanford Parser :

http://nlp.stanford.edu/software/lex-parser.shtml Моделирование волновых процессов в задачах сейсморазведки на суперкомпьютерах “Ломоносов” и BlueGene/P Бурцев Александр Павлович Магистрант Факультет ВМК МГУ имени М. В. Ломоносова, Москва, Россия E-mail: apburtsev@gmail.com В настоящее время поиск полезных ископаемых, таких как нефть и газ, является очень важной задачей. Промышленность и транс порт потребляют всё больше и больше углеводородов, а развитие альтернативных источников энергии, пока не позволяет отказаться от использования традиционных природных ресурсов.

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

Цель данной работы исследование эффективности различных параллельных алгоритмов моделирования распространения акусти ческих волн в однородной и неоднородной среде на регулярных сетках. Для численного решения дифференциального уравнения, описывающего распространение волн, используется явная конечно разностная схема 2-ого порядка по времени и 4-ого по простран ственным координатам [3]. На границе среды реализованы поглоща ющие граничные условия. За основу взят последовательный вариант предложенный в open-source пакете Madagascar [5]. Рассматриваются три основных комплекса программно-аппаратных средств для раз работки параллельных решений: OpenMP для SMP архитектуры, MPI для кластеров и CUDA для графических ускорителей компа нии NVIDIA [1], а также комбинированные версии этих подходов.

При организации параллельных вычислений был использован прин цип геометрического параллелизма: исходные данные разбиваются на набор одинаковых подобластей, в каждой из которых можно ве сти вычисления независимо при этом на каждом шаге по времени требуется проводить обмен граничными элементами между соседни ми подобластями. Основные тесты проводились на базе кластеров Ломоносов и Blue Gene/P. Все предложенные варианты показали достойную эффективность и масштабируемость, основным недостат ком GPU версии является сравнительно небольшой размер данных которые можно вычислять на одной видеокарте и достаточно долгое время необходимое на копирование данных между памятью видео карты и оперативной памятью CPU. Одновременно с вычислениями можно выполнять копирование данных из оперативной памяти на жёсткий диск, что дает значительный прирост производительности.

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

Литература 1. Боресков А. В., Харламов А. А. Основы работы с технологией CUDA. М.: ДМК 2010. 230 с.

2. Бурцев А. П., Курин Е. А. Исследование различных подходов к разработке параллельных алгоритмов моделирования рас Конференция Ломоносов – пространения акустических волн для задач сейсморазведки // Программные системы и инструменты. Тематический сборник.

2012. No 13. С. 56–61.

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

4. Хмелевской В. К., Горбачёв А. В., Калинин А. В., Попов М. Г., Селиверстов И. Н., Шевнин В. А. Геофизические методы иссле дований. Петропавловск-Камчатский: КГПУ 2004. 232 с.

5. Страница проекта Guide to programming with madagascar :

http://reproducibility.org/wiki/Guide_to_programming_ with_madagascar Применение метамоделей для задачи выбора механизмов обеспечения отказоустойчивости распределенных вычислительных систем реального времени (МОО РВС РВ) Глонина Алевтина Борисовна Студент Факультет ВМК МГУ имени М. В. Ломоносова, Москва, Россия E-mail: alevtina@lvk.cs.msu.su Одним из способов повышения надежности РВС РВ является ис пользование МОО. МОО механизмы предоставления системе из быточных функциональных возможностей и ресурсов, позволяющие предотвратить отказ. В работе в качестве МОО рассматривается N версионное программирование и восстановление блоками [3].

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

В [1] был предложен адаптивный гибридный эволюционный алго ритм (АГЭА) решения задачи. В ходе работы АГЭА необходимо мно Секция Вычислительная математика и кибернетика гократно оценивать время выполнения программных компонентов.

Для этого применяется имитационное моделирование: по конфигу рации РВС РВ строится и запускается ее имитационная модель. Экс перименты со средой моделирования ДИАНА показали, что прове дение имитационных экспериментов вычислительно дорогая про цедура.

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

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

Литература 1. Bakhmurov A. G., Balashov V. V., Pashkov V. N., Smeliansky R. L., Volkanov D. Yu. Method For Choosing An Eective Set Of Fault Tolerance Mechanisms For Real-Time Embedded Systems, Based On Simulation Modeling // Problems of dependability and modelling /eds. Jacek Mazurkiewicz [i in.]. Wroclaw : Ocyna Wydawnicza Politechniki Wroclawskiej, 2011. P. 13–26.

2. Knowles J., Nakayama H. Meta-modeling in multi-objective optimization // Multi-objective Optimization Interactive and Evolutionary Approaches. Springer LNCS 5252, 2008. P. 245–284.

3. Wattanapongsakorn N., Coit D. W. Fault-tolerant embedded system design and optimization considering reliability estimation uncertainly // Reliability Engineering and System Safety. 2007.

№ 92. P. 395–407.

Решение систем уравнений гиперболического типа на графических процессорах с использованием технологии CUDA Дашкевич Антон Дмитриевич Студент Факультет ФУПМ МФТИ, Долгопрудный, Россия E-mail: anton.dashkevich.1@gmail.com Системы уравнений гиперболического типа имеют большое зна чение при математическом описании моделей для численного реше Конференция Ломоносов – ния прикладных физических задач. В том числе, они используют ся для моделирования некоторых задач распространения динамиче ских волновых возмущений в гетерогенных средах. К таким задачам относятся задачи сейсмостойкости зданий, задачи разведки углево дородов и другие задачи сейсмики [1]. Они имеют важное практи ческое значение на этапе проектирования и выбора площадок для постройки зданий, мостов, плотин, атомных электростанций, других стратегических объектов и сложных наземных сооружений, а также при разведке и оценке запасов месторождений углеводородов.

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

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

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

В результате удалось получить ускорение около 60 раз при ис пользовании одного графического устройства (nVidia Tesla s2050) по сравнению со скоростью работы на центральных процессорах.

Литература 1. Хохлов Н. И., Петров И. Б. Моделирование сейсмических явле ний сеточно-характеристическим методом // Труды МФТИ.

2011. Т. 3, № 3. С. 159–167.

2. Голубев В. И., Квасов И. Е., Хохлов Н. И., Петров И. Б. Числен ное моделирование сейсмостойкости жилых и промышленных наземных сооружений // Технологии обеспечения комплексной безопасности, защиты населения и территорий от чрезвычай ных ситуаций - проблемы, перспективы, инновации XVI меж дународная научно-практическая конференция, Москва, Рос сия, 2011, С. 215–218.

Секция Вычислительная математика и кибернетика 3. CUDA C Best Practices Guide:

http://docs.nvidia.com/cuda/cuda-c-best-practices-guide/ index.html Интерфейс на основе шаблонных классов С++ для работы с большими типизированными файлами Ефимов Александр Юрьевич Студент Факультет ВМК МГУ имени М. В. Ломоносова, Москва, Россия E-mail: efimov.alexander@gmail.com При обработке больших объёмов данных часто встаёт задача хра нения и быстрого доступа к последовательностям одинаковых эле ментов. Такие данные удобно хранить в типизированных файлах бинарных файлах, состоящих из последовательностей элементов од ного типа. Структура такого файла похожа на обычный массив, но в отличие от него, объём данных, хранящихся в файле, может быть больше объёма доступной программе оперативной памяти.

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

К описанному вектору предъявляется несколько требований:

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

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

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

Литература 1. Страуструп Б. Язык Программирования С++. Специальное издание. Бином, 2011. C. 417–420.

2. Алгоритм LRU: http://en.wikipedia.org/wiki/Cache_ algorithms#Least_Recently_Used Моделирование окружения драйверов операционной системы Linux для поддержки процесса статической верификации Захаров Илья Сергеевич Студент Факультет управления и прикладной математики Московского физико-технического института, Москва, Россия E-mail: ilja.zakharov@ispras.ru В настоящее время ядро операционной системы Linux динамично развивается. Новые версии ядра появляются каждые 2-3 месяца и могут включать в себя более 10 тысяч патчей, а в их подготовке обычно участвует порядка тысячи разработчиков [6]. Большую часть ядра составляют драйверы. В большинстве случаев падение системы происходят именно из-за них [3]. Поэтому именно драйверы нужда ются в верификации в первую очередь, так как при текущих темпах развития осуществлять их поддержку вручную слишком трудоемкая задача. Одним из способов решения этой проблемы является приме нение инструментов статической верификации.

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

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

Системы статической верификации драйверов, такие как Microsoft SDV [1] (входит в набор Windows Development Kit для разработчиков драйверов Windows), Avinux [2] (разработана в уни верситете города Тюбинген в Германии), DDVerify [5] (разработка Оксфордского университета), а также LDV [4] (разработана в инсти туте системного программирования РАН), имеют ряд существенных недостатков в построения модели окружения. Данная работа посвя щена новому подходу к генерации модели окружения для драйверов Linux, который был реализован в системе LDV.

Литература 1. Ball T., Bounimova E., Levin V., Kumar R., Lichtenberg J. The Static Driver Verier Research Platform // CAV 2010. 2010.

2. Hendrik P., Wolfgang K. Integrated Static Analysis for Linux Device Driver Verication. // IFM’07 Proceedings of the 6th international conference on Integrated formal methods. 2007, p.

518-537.

3. Swift M., Bershad B., Levy H. Improving the reliability of commodity operating systems. // SOSP ’03. 2003.

4. Khoroshilov A., Mutilin V., Shcherbina V. et al. How to cook an automated system for Linux verication // 2nd Spring Young Researchers’ Colloquium on Software Engineering. 2008, Vol. 2. p.

11–14.

5. Witkowski T., Blanc N., Kroening D., Weissenbacher G. Model Checking Concurrent Linux Device Drivers ASE ’07: Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering // ACM. 2007. p. 501–504.

6. Corbet J., Kroah-Hartman G., McPherson A. Linux kernel development. How Fast it is Going, Who is Doing It, What They are Doing, and Who is Sponsoring It: http://go.

linuxfoundation.org/who-writes-linux- Преобразования расписаний в итерационных алгоритмах структурного синтеза вычислительных систем Зорин Даниил Александрович Аспирант Факультет ВМК МГУ имени М. В. Ломоносова, Москва, Россия E-mail: juan@lvk.cs.msu.ru В данной работе рассматривается задача структурного синтеза и построения расписания для многопроцессорной системы. Множе Конференция Ломоносов – ство заданий или программа, для которых строится расписание, за дано графом потока данных. Из-за зависимостей некоторые зада ния должны выполняться в строго определенном порядке, поэтому не любое расписание будет выполнимым (корректным). Требуется построить расписание, выполняющееся на наименьшем возможном числе процессоров. При этом также заданы ограничения на время выполнения расписания и требования к надежности системы [1].


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

Одним из классов алгоритмов решения оптимизационных задач являются итерационные алгоритмы [2]. Итерационные алгоритмы не гарантируют нахождения точного решения задачи, но являются вы числительно эффективными, поэтому часто применяются для реше ния сложных задач из класса NP.

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

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

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

Литература 1. Wattanapongsakorn N., Levitan S. P. Reliability optimization models for embedded systems with multiple applications // Reliability, IEEE Transactions on. 2004. № 53. P. 406–416.

2. Калашников А. В., Костенко В. А. Параллельный алгоритм имитации отжига для построения многопроцессорных распи саний // Известия РАН. Теория и системы управления. 2008.

№ 3, С. 101–110.

Секция Вычислительная математика и кибернетика Эффективное использование графических процессоров в задачах глобальной оптимизации Климов Георгий Петрович Аспирант Факультет инноваций и высоких технологий Московского Физико–Технического института, Москва, Россия E-mail: tolkachev@physics.msu.ru Данная работа посвящена исследованию двух методов глобальной оптимизации, являющихся параллельными модификациями метода Monotonic Basin Hopping (MBH) [1] применяемого для решения задач поиска структуры молекулярных систем в физике. Практическая часть заключается в эффективной реализации исследуемых мето дов на современных высокопроизводительных графических процес сорах, установлении связи входных параметров алгоритмов с харак теристиками аппаратного обеспечения (АО) и данными конкретной задачи. Для выделенного круга задач проведен сравнительный ана лиз эффективности использования двух методов.

Метод MBH успешно используется для решения задач поиска конфигурации молекулярного кластера [2, 3, 4]. Его суть кратко можно изложить так [5]:

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

2) совершается случайное смещение из исходной точки в окрест ности заданных пределов;

3) к полученной таким образом точке применяется алгоритм ло кальной минимизации;

4) если удалось улучшить начальное приближение, то оно заменя ется найденным значением и алгоритм продолжается из найденной точки;

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

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

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

Конференция Ломоносов – Программно исследуемые алгоритмы реализованы с помощью технологии CUDA [7, 8], дающей возможность эффективного про граммирования на высокопроизводительных графических процес сорах Nvidia. Проведены тесты производительности в зависимости от входных параметров алгоритмов (радиус смещения, число ша гов цикла), характеристик АО (число процессоров) и условий за дачи (размер исследуемой области). Были выявлены взаимосвязи и сформулированы рекомендации, которые позволяют оптимизиро вать входные параметры алгоритма под конкретное АО.

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

Результаты тестирования позволили сформулировать выводы:

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

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

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

Литература 1. Northby J. A. Structure and binding of Lennard-Jones clusters: ¤ n ¤147 // J. Chem. Phys. 1987. 87. 6166–6178.

2. Xue G. L. Improvements on the Northby algorithm for molecular conformation: better solutions // Journal of Global Optimization.

1994. 4(4). 425–440.

3. Doye J. P. K., Wales D. J., Berry R. S. The eect of the range of the potential on the structure of clusters // J. Chem. Phys. 1995.

103. 4234–4249.

4. Leary R. H. Global optimization on funneling landscapes // J.

Global Optim. 2000.18. 367–383.

5. Посыпкин М.А. Методы решения задач конечномерной опти мизации в распределенной вычислительной среде. // Третья Международная конференция Системный анализ и информа ционные технологии САИТ – 2009: Труды конференции. М., 2009, С. 729- 6. Andrea Grosso, Marco Locatelli, Fabio Schoen, Apopulation based approach for hard global optimization problems based on dissimilarity measures, Math. Program. 110(2), 2007, pp. 373- Секция Вычислительная математика и кибернетика 7. Боресков А. В., Харламов А. А. Основы работы с технологией CUDA. М.: ДМК Пресс, 2010.

8. Дж. Сандерс, Э. Кэндрот. Технология CUDA в примерах. ДМК Пресс, 9. Test functions for unconstrained global optimization [HTML] (htttp://www-optima.amp.i.kyoto-u.ac.jp/member/ student/hedar/Hedar\_files/TestGO\_files/Page364.htm) Применение метода временных рядов для определения влияния DDoS-атак на системный и сетевой трафик сервера Левоневский Дмитрий Константинович Младший научный сотрудник Санкт-Петербургский Институт Информатики и Автоматизации РАН, Санкт-Петербург, Россия E-mail: DLewonewski.8781@gmail.com В настоящее время в Интернете распространены атаки типа Distributed Denial of Service (DDoS), ставящие своей целью выве сти объект (вычислительную систему) из рабочего состояния. Мас штабные DDoS-атаки в большинстве случаев приводят к финансо вым потерям со стороны жертвы, а также отличаются простотой ор ганизации и высокой эффективностью. Эти особенности обусловли вают актуальность исследования DDoS-атак. В частности, представ ляет интерес статистическое исследование временных рядов систем ного и сетевого трафика как в различных режимах работы сервера, что позволяет в дальнейшем выявлять факт вторжения на основе поведенческих сигнатур.

Для исследования временных рядов был разработан стенд, моде лирующий клиент-серверное взаимодействие между компьютерами как в регулярном режиме, так и при наличии наиболее распростра нённых атак (HTTP-ood, SYN-ood, UDP-ood). Стенд включает в себя средства генерации трафика на клиентской стороне и средства мониторинга – на сервере. Для генерации атак использована про грамма Longcat Flooder, для генерации регулярного трафика раз работана программа Client. Для сбора данных разработана утилита Monitor, протоколирующая объём входящего и исходящего сетево го трафика и загрузку памяти и процессора. В качестве атакуемого хоста выбран Web-сервер на базе Apache/PHP/MySQL.

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

Например, для атаки класса HTTP-ood результаты говорят:

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

об изменении закона распределения времени простоя процес сора;

о снижении дисперсии входящего и исходящего сетевого тра фика.

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


Данная работа выполнена при поддержке компании ИнфоТеКС Академия.

Литература 1. Бриллинджер Д. Временные ряды. Обработка данных и тео рия. – М.: Мир, 1980. – 536 с.

2. Петров В. В. Статистический анализ сетевого трафика. – М.:

МЭИ, 2003. – 47 с.

3. Олифер В. Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. – СПб.: Питер, 2006. – 958 с.

Генерация входных описаний для планировщика по моделям на языке UML Манжосов Андрей Николаевич Аспирант Факультет ВМК МГУ имени М. В. Ломоносова, Москва, Россия E-mail: amanzhosov@gmail.com Входные описания планировщика представляют собой тексты на специальных языках, определяющие типы объектов и связей меж ду объектами предметной области, а также начальные состояния и цели задач, которые предстоит решить планировщику. В большин стве современных планировщиков входные описания составляются на языке PDDL (Planning Domain Denition Language) [1].

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

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

Работы по созданию инженерии знаний в области планирования, базирующейся на использовании UML, ведутся в университете Сан Паулу в рамках проекта itSIMPLE [3]. Особенностью моделей, со зданных в среде itSIMPLE, является то, что они могут быть исполь зованы только в её рамках. В отличие от этого предлагается под ход, базирующийся на стандартных UML-моделях, к которым при менимы универсальные CASE-средства, а не только инструменты itSIMPLE.

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

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

В отличие от проекта itSIMPLE, где преобразователь написан на Java, реализация моего генератора осуществлена с помощью средств генерации текстов по моделям, соответствующих стандарту OMG MOF2Text [4]. Первая часть генератора создана в виде набора шаб лонов Acceleo. Шаблоны Acceleo являются удобным высокоуровне вым средством описания преобразований моделей в тексты. Всего в состав генератора входят две группы шаблонов, в каждой из кото рых 8–10 элементов. Первая группа отвечает за создание описания предметной области, вторая за создание описания задач планиро вания.

Конференция Ломоносов – Вторая часть генератора выполняет анализ OCL-выражений, входящих в состав UML-моделей, и перевод их в PDDL. Она до полняет PDDL-описания, сгенерированные по шаблонам, пред- и по стусловиями действий, формулировками целей задач. В настоящее время реализация второй части генератора не окончена. Она осу ществляется на языке Java при помощи Eclipse OCL API.

Иллюстрации Фрагменты UML-модели и входного описания планировщика Литература 1. Gerevini, A., Long, D.: Plan constraints and preferences in PDDL3.

Technical Report, Univ. Brescia, Italy, 2005. 12p.

2. Арлоу Д., Нейштадт И. UML 2 и унифицированный процесс.

Практический объектно-ориентированный анализ и проектиро вание, 2-е издание. СПб.: Символ-Плюс, 2007. 624 с.

3. Vaquero T. S., Silva J. R From Requirements and Analysis to PDDL in itSIMPLE3.0 // Proceedings of the 3rd International Competition on Knowledge Engineering for Planning and Scheduling (ICAPS-09). Thessaloniki, Greece. 2009.

4. Object Management Group MOF Model to Text Transformation Language, v 1.0 2008 (http://www.omg.org/spec/MOFM2T/1.0/ PDF) Разработка новых методов повышения надежности устройств управления Москвин Вадим Викторович Соискатель Факультет инфраструктуры и подвижного состава железнодорожного транспорта Государственного Экономико-технологического Университета Транспорта, Киев, Украина E-mail: v_moskvin@ukr.net Обеспечение надежности изделий сложнейшая комплексная зада ча, затрагивающая практически все сферы деятельности человека и включающая множество обязательных условий организационного, административного, инженерного и научного планов.

Секция Вычислительная математика и кибернетика Подсчитано, что при доле дефектности партий компонентов, ис пользуемых при производстве электроники, в пределах 0,01%, то есть 100 дефектных на один миллион поставленных, процент отка зов печатных плат, на которых смонтированы эти 100 компонентов, составит 9,5%. При дефектности партий компонентов в пределах 1% выход годных печатных плат составит 63,4%, то есть брак составит 36,6% [4].

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

Целью работы является разработка новых методов повышения надежности устройств управления при использовании элементарных схем автоматной памяти, предложенных Мараховским Л.Ф. [2,3].

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

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

Принцип структурной организации многофункциональных схем памяти (МФСП) заключается в том, что используются n логиче ских элементов ИЛИ-НЕ (И-НЕ), которые разбиваются на m (m n) групп.

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

Литература 1. Хетагуров Я.А. Обеспечение национальной безопасности си стем реального времени. – М.: BC/NW 2009;

№2 (15): 2. Мараховський Л.Ф. Комп’ютерна схемотехнiка: Навч. Посiб. – К.: КНЕУ, 2008.

3. Мараховский Л.Ф. Основы новой информационной технологии:

монография. Saarbrcken, Germany, i.melnic@lap-publishing.ru / www.lap-publishing.ru, 2013.

Конференция Ломоносов – 4. http://www.chipinfo.ru/literature/chipnews/200105/5.

html Цифровая модель искусственного нейрона на элементах автоматной памяти Москвин Максим Викторович Соискатель Факультет инфраструктуры и подвижного состава железнодорожного транспорта Государственного Экономико-технологического Университета Транспорта, Киев, Украина E-mail: m.mosqvin@gmail.com В настоящее время вся вычислительная техника использует дво ичную схему памяти, обладающую нулевой информационной из быточностью, неспособную перестраивать структуру запоминаемых состояний и, обладает недостаточной надежностью при создании устройств управления сложных систем.

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

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

2].

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

Многофункциональные схемы автоматной памяти могут быть со единены в ансамбли до 8-ми уровней, в которых внутренние сохра няющие сигналы поступают с общего (i -1)-уровня на более частный i -уровень ансамбля. Эти внутренние сохраняющие сигналы настра ивают частные уровни многоуровневой схемы памяти (МУСП) на определенный режим работы и соответственно отражают определен ные выходные сигналы, принадлежащие определенным подмноже ствам на каждом уровне, кроме нулевого [3–4].

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

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

Литература 1. Мараховский Л.Ф. Многофункциональные схемы памяти. – Киев: УСиМ – № 6.-1996.– С. 59- 2. Мараховский Л.Ф. Многоуровневые устройства автоматной па мяти. I ч. – Киев: УСиМ. – №1.– 1998.– С. 66- 3. Мараховский Л.Ф. Многоуровневые устройства автоматной па мяти. II ч. – Киев: УсиМ. – №2. – 1998. – С. 63- 4. Мараховский Л.Ф. Основы новой информационной технологии:

монография Saarbrcken, Germany: i.melnic@lap-publishing.ru / www.lap-publishing.ru, 2013. – 369 с.

5. Мараховский Л.Ф., Михно Н.Л., Москвин М.В. Автоматы тре тьего рода – новый шаг к моделированию работы человеческого мозга. / Мараховский Л.Ф., Чечик А.Л. и др. Пути познания закономерностей процессов эволюции сложных систем: коллек тивная монография – Одесса: ООО ИКТ, 2012. – С. 247 – 256.

Исследование и программная реализация алгоритма кластеризации в терминологической сети Новиков Константин Викторович Студент Факультет ВМК МГУ имени М. В. Ломоносова, Москва, Россия E-mail: novkostya@gmail.com За всю историю существования человечество, начиная с самых ранних времен, накапливало свои знания. Для умелого обраще ния с накопленной информацией необходимо разумно представлять, структурировать, хранить полученные знания, поэтому важно сопо ставлять различные методы представления знаний и по заданным критериям определять наиболее полезные. Правильно выбранный метод представления знаний позволяет значительно упростить слож ные задачи, практически не поддающиеся решению при иных под ходах. Решение таких задач и включает в себя проблема наиболее корректной организации и хранения знаний.

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

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

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

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

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

Литература 1. Мальковский М Г., Соловьев С Ю. Универсальное терминоло гическое пространство. Труды международного семинара:

Компьютерная лингвистика и интеллектуальные технологии, М: Наука, 2002. Т.1, 266–270.

2. Мальковский М Г., Соловьев С Ю. Технология формирования универсального терминологического пространства. Сб. Инфор мационные компьютерные технологии и Интернет в образова нии и науке. Москва: изд-во МИИ для инвалидов с нарушением ОДС, 2002, 54–55.

3. Глоссарий.ру: http://glossary.ru Подходы к компьютерному моделированию нейрона: история и перспективы Седов Никита Викторович Аспирант Южный федеральный университет, НИИ механики и прикладной математики имени И. И. Воровича, Ростов-на-Дону, Россия E-mail: sed-nik@yandex.ru С учетом назначения и степени приближения к объекту могут быть выделены два класса моделей нейронов: модели обработки сиг налов в нейроне и портретные модели нервных клеток. В классе моделей обработки сигналов в нейроне можно различать простые формальные модели нейрона и биологически правдоподобные моде ли обработки сигналов в нейроне.

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

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

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

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

Построение портретных моделей требует слишком много вы числительных ресурсов, т.к. химические процессы виртуально вос производятся при помощи компьютера. Так, для обеспечения рабо ты проекта Blue Brain Project использовался суперкомпьютер Blue Gene производства корпорации IBM с 8192 процессорами.

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

Литература 1. Кохонен Т. Самоорганизующиеся карты. М.: БИНОМ. Лабора тория знаний, 2008. 655 с.

2. Мак–Каллок У., Питтс В. Логическое исчисление идей, относя щихся к нервной активности // Нейронные сети: история раз вития теории / Под общ. ред. Галушкина А. И., Цыпкина Я. З.

М: ИПРЖР, 2001.

3. Markram H. The blue brain project. // Nat Rev Neurosci. Vol. 7, pp. 153–160 (2006).



Pages:   || 2 | 3 | 4 | 5 |
 



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





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

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