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

Pages:     | 1 | 2 || 4 |

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

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

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

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

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

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

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



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

Результаты тестирования на суперкомпьютере IBM Blue Gene/P показывают, что обе схемы демонстрируют практически максимальное ускорение и высокую равномерность загрузки процессоров при числе процессоров значительном меньшем числа столбцов исходной матрицы. Оценка объёмов подзадач в S-схеме гораздо менее трудоёмка, чем в В-схеме, поэтому S-схема позволяет обрабатывать матрицы большего размера.

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

Результаты частично опубликованы в [4] и доложены на конференции «Интеллектуализация обработки информации (ИОИ-2014)» [5].

Литература

1. Дюкова Е. В., Прокофьев П. А. Построение и исследование новых асимптотически оптимальных алгоритмов дуализации. // Машинное обучение и анализ данных, т. 1, № 8, c. 1048–1067, 2014.

Отделение специалитета

2. Murakami K., Uno T. Efficient Algorithms for Dualizing Large-Scale Hypergraphs. // Discrete Applied Mathematics, т. 170, pp. 83–94, 2014.

3. Дюкова Е. В. Об асимптотически оптимальном алгоритме построения тупиковых тестов. // ДАН СССР, т. 223, № 4, c. 527–530, 1977.

4. Дюкова Е. В., Никифоров А. Г.,Прокофьев П. А. Статистически эффективная схема распараллеливания алгоритмов дуализации. // Машинное обучение и анализ данных, т. 1, № 7, с. 846–853, 2014.

5. Дюкова Е. В., Никифоров А. Г.,Прокофьев П. А. Эффективный параллельный алгоритм дуализации. // Тезисы доклада 10-й международной конфереции «Интеллектуализация обработки информации (ИОИ-2014)», 2014 г. Греция, о. Крит. С. 48–49.





–  –  –

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

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

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

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

В дипломной работе рассматривается недавно предложенное И. Оселедцом [2] разложение тензорного поезда (TT-разложение или TTформат). Алгоритмы TT-разложения хранят тензор в специальном формате, который позволяет эффективно оперировать над тензорами. Эффективность TT-разложения определяется величиной TT-рангов тензора. В работе показано, что тензор энергии (минус логарифма вероятности) марковского случайного поля обладает низкими TT-рангами, а тензор вероятности — высокими TT-рангами. Для подсчета нормировочной константы в условиях высоких TT-рангов тензора вероятности предложен метод, основанный на факторизации графической модели. Факторы графической модели переводятся в TT-формат и комбинируются таким образом, чтобы оценить нормировочную константу, не строя сам тензор вероятности. Для данного метода выведены теоритические оценки точности работы.

Так же в работе рассматривается предложенный в 2014 году метод n-окрестностей [3], придуманный для оценки нормировочной константы (или, как её называют в физической литературе, «статистической суммы») модели Изинга2. Основная идея метода n-окрестностей — разбить множество значений энергии на подмножества и приблизить эмпирическую функцию распределения энергий в каждом подмножестве с помощью нормального распределения. В дипломной работе предлагается отказаться от рассмотрения отдельных подмножеств и рассматривать множество всех энергий целиком. Полученные формулы позволяют применять такой метод к произвольному марковскому случайному полю (тогда как метод n-окрестностей предложен только для модели Изинга), а использование полного множества энергий в ряде случаев позволяет получить более точные результаты.

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

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

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

Литература

1. Wainwright M. J., Jordan M. I. Graphical models, exponential families, and variational inference. // Foundations and Trends in Machine Learning, 2008, 1(1–2):1–305.

2. Oseledets I. V. Tensor-Train decomposition. SIAM J. Scientific Computing, 2011, 33(5):2295–2317.

3. Kryzhanovsky B., Litinskii L. Approximate method of free energy calculation for spin system with arbitrary connection matrix.

arXiv:1410.6696, 2014.

4. Smolensky P. Information processing in dynamical systems: Foundations of harmony theory. 1986.

–  –  –

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

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

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

Генерация графов байесовских сетей производилась на основе моделей случайных графов Эрдеша-Реньи и Барабаши-Альберт [3]. Для генерации таблиц условных вероятностей использовалось распределение Дирихле.

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

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

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

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

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

Литература

1. Daphne Koller, Nir Friedman. Probabilistic Graphical Models: Principles and Techniques. The MIT Press, 2009.

2. Alessio Farcomeni. A review of modern multiple hypothesis testing, with particular attention to the false discovery proportion. Statistical Methods in Medical Research, 2007.

3. Кузюрин Н.Н., Берновский М.М. Случайные графы, модели и генераторы безмасштабных графов. Труды Института системного программирования РАН, 22:419–434, 2012.

–  –  –

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

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

Мультиплексорная функция порядка n - это ФАЛ от + 2 переменных, где первые переменных называются адресными, оставшиеся 2 информационными, а значение этой ФАЛ равно значению той ее информационной переменной, номер которой поступил на адресные входы.

Пусть ( ) — древовидная BDD, реализующая мультиплексорную ФАЛ порядка n и имеющая 2 (соответственно, 1) стоков с пометкой 0 и Кафедра МК 2 (соответственно, 1) стоков c пометкой 1. Рассмотрим также реализующую ее асимптотически оптимальную по сложности контактную схему, которая описана в [3].

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

Линейная функция порядка n — это ФАЛ вида = 1....

Обозначим через BDD, реализующую ее на основе схемы Кардо.

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

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

Справедливы следующие утверждения:

Теорема 4 Для любого 2 выполняется равенство ( ) = + 3.

–  –  –

Теорема 8 Для любого 2 выполняется неравенство ( ) (4 3), а при = 2 — равенство ( ) = (4 3).

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

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

–  –  –

Литература

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

Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2008. №1. С. 44-50.

2. Ложкин С. А. Лекции по основам кибернетики. М.: Изд-во МГУ.

2004.

3. Власов Н.В. О сложности мультиплексорных функций в некоторых классах схем. Диссертация на соискание ученой степени кандидата физико-математических наук. М., 2013

–  –  –

( ) =, ( (, ) )

–  –  –

где и - константы, зависящие только от базиса B.

Теорема 3. Существует неотрицательная и стремящееся к нулю последовательность действительных чисел (1), (2),.

.. такая, что для любого, = 1, 2,..., мультиплексорная ФАЛ может быть реализована некоторой СФЭ над базисом B0 = {&,, ¬}, удовлетворяющей неравенствам (1 + ()) · 2+1, ( ) (1 + ()) · 5.

( ) Отделение специалитета Теорема 3 с учетом результатов работы [4] устанавливает возможность построения такой реализующей ФАЛ СФЭ, которая является асимптотически оптимальной по сложности и имеет оптимальную по порядку роста динамическую активность.

Литература

1. Касим-Заде О. М. Об одной мере сложности схем из функциональных элементов // Проблемы кибернетики. — М.: Наука, 1981. — Вып. 38. — С. 117–179.

2. Najm F. A survey of power estimation techniques in VLSI circuits (Invited paper) // IEEE Trans VLSI Syst. — 1994. — V. 2, № 4. — P. 446– 455.

3. Ложкин С. А., Шуплецов М. С. О динамической активности схем из функциональных элементов и построении асимптотически оптимальных по сложности схем с оптимальной по порядку динамической активностью // Учён. зап. Казан. гос. ун-та. Сер. Физ.-матем.

науки 156:3 — 2014. С. 84–97.

4. Коровин В. В. О сложности реализации универсальной функции схемами из функциональных элементов // Дискретная математика 7:2 — 1995. С. 95–102.

–  –  –

+1, ( )

–  –  –

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

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

4. Маркелов Н. К. Нижняя оценка сложности функций трехзначной логики в классе поляризованных полиномов. Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. № 3. 2012. С. 40-45.

5. Селезнева С. Н. Сложность систем функций алгебры логики и систем функций трехзначной логики в классах поляризованных полиномиальных форм. Дискретная математика. Том 27. Выпуск 1. 2015.

С. 111–122.

–  –  –

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

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

Одним из результатов данной работы является классификация относительно группы Джевонса минимальных корреляционно-иммунных функций от 6-ти переменных. Для её построения с помощью реализованного комплекса программ были посчитаны все корреляционно-иммунные функции от 6-ти переменных веса 2, 4, 6, 8, 10, 12, 14, 16, среди них были выделены минимальные и проведена их классификация. Всего насчитывается 634 432 минимальные корреляционно-иммунные функции от 6-ти переменных и 44 класса эквивалентности. Данная классификация полна в предположении гипотезы о непрерывности весового спектра: если не существует минимальных корреляционно-иммунных функций веса от переменных, то не существует минимальных корреляционно-иммунных функций веса большего от переменных ( —четное).

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

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

При 5 справедливо соотношение | (, ( ) = 6)| 22 2.

Кроме того, в работе сформулирован спектральный критерий минимальности корреляционно-иммунной функции: () тогда и только тогда, когда,=0=,()=1 () = 0.

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

На основании этого метода сформулирована следующая теорема:

Отделение специалитета Если существует минимальная корреляционно-иммунная функция веса от переменных, то существует минимальная корреляционноиммунная функция веса от переменных,.

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

Для любого 5 существуют минимальные корреляционноиммунные функции веса 6 и веса 8.

Для любого 6 существуют минимальные корреляционноиммунные функции веса 10.

Литература

1. Алексеев Е. К., Карелина Е. К. Классификация корреляционноиммунных и минимальных корреляционно-иммунных булевых функций от 4 и 5 переменных. Дискретная математика. 2015. Т. 27.

2. Braeken A., Borissov Y., Nikova S., Preneel B. Classification of Boolean Functions of 6 Variables or Less with Respect to Cryptographic Properties. Cryptology ePrint Archive, Report 2004/248.

3. Harrison M. A. On the Classification of Boolean Functions by the General Linear and Affine Group. Journal of the Society for industrial and applied mathematics, Vol.12, pp.284-299, 1964.

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

2011.

Исследование границ применимости некоторых методов криптографического анализа потоковых шифров, построенных на основе регистров сдвига Работа удостоена диплома II степени Кущинская Людмила Александровна Кафедра информационной безопасности e-mail: lyudmila.kuschinskaja@yandex.ru Научный руководитель: к.ф.-м.н., Алексеев Евгений Константинович Потоковый шифр является широко распространенным на практике криптографическим примитивом. Основным преимуществом потоковых шифров над блочными является скорость обработки информации. Одним Кафедра МК из классических элементов конструкций, используемых в ряде потоковых шифров является так называемый фильтрующий генератор. Задача криптографического анализа данных конструкций является актуальной, поскольку с некоторыми модификациями они используются для построения современных потоковых шифров. Примером тому могут служить, например, шифры MICKEY [1], Grain [2], участвующие в европейском конкурсе потоковых шифров eSTREAM.

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

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

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

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

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

Следующая часть исследований посвящена исследованию границ применимости предложенного метода. Рассматривается фильтрующий генератора, у которого функция усложнения принадлежит классу МайэронаМак-Фарланда. К данному классу относятся функции вида:

(, ) =, () (),,, где : — подстановка на пространстве и — булева функция от переменных.

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

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

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

Left Subsystem Right Subsystem LILI-128 D метода 223 275 2118 D brute-force 239 289 2128 По результатам исследований была подготовлена статья для журнала «Прикладная дискретная математика», которая находится в процессе рецензирования, а также данные результаты были представлены на конференции «Дискретные модели в теории управляющих систем» в 2015 году.

Литература

1. S. Babbage and M. Dodd. The Stream Cipher MICKEY 2.0. ECRYPT Stream Cipher, 2006.

2. M. Hell, T. Johansson and W. Meier. Grain - A Stream Cipher for Constrained Environments. International Journal of Wireless and Mobile Computing, vol. 2, no. 1, pp. 86-93, 2007.

3. E. Dawson, A. Clark, J. Golic, W. Millan, L. Penna, L. Simpson. The LILI-128 Keystream Generator. Proc. of first NESSIE workshop.

4. Е. К. Алексеев. Об атаке на фильтрующий генератор с функцией усложнения, близкой к алгебраически вырожденной. Сборник статей молодых ученых факультета ВМК МГУ, 2011.

–  –  –

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

Одна из таких криптосистем - криптосистема Мак-Элиса - была предложена Р. Дж. Мак-Элисом в 1978 году [1]. В 1996 году В.М. Сидельников предожил использовать для построения такой криптосистемы коды Рида– Маллера. А в 2007 году Л. Миндер и А. Шокроллахи описали атаку на такую криптосистему [2]. В 2013 И.В. Чижовым и М.А. Бородиным была предложена новая атака, которая имеет полиномиальную сложность, в случае ограничения некоторых параметров кода Рида–Маллера [3].

Представляется интересным изучить модификацию криптосистемы Мак-Элиса, построенную на подкодах кода Рида–Маллера. В работе изучен этот вопрос для подкодов ( 2) - порядка.

Кодом Рида-Маллера (, ) называется множество векторзначений всех булевых функций (1, 2, · · ·, ), степень нелинейности которых не превосходит. Известно, что код (, ) имеет размерность =, =0

–  –  –

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

Имеется три различных случая:

Отделение специалитета

1. Удаление строк с номерами + 2 Для этого случая доказана теорема, показывающая, что можно восстановить полный код, то есть код размерности.

И построена атака.

2. Удаление строк с номерами 1, + 1 В этом случае доказана теорема, что восстанавливается только строка с номером, а строка с номером не восстанавливается.

Соотвественно, дальнейшее исследование должно проводиться для кодов размерности ( 1).

3. Удаление строк с номерами 1 Для этого случая доказано, что ни одна строка не восстановится.

Значит, остаётся код размерности ( 2).

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

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

–  –  –

1. McEliece R. J. A public-key cryptosystem based on algebraic coding theory. М.: DSN Prog. Rep., Jet Prop. Lab., California Inst. Technol.

1978. Vol. January. Pp. 114-116

2. Minder L., Shokrollahi A. Cryptanalysis of the Sidelnikov cryptosystem Advances in Cryptology M.: EUROCRYPT 2007, Lecture Notes in Computer Science. 2007. Vol. 4515. Pp. 347-360

3. И. В. Чижов, М. А. Бородин. Эффективная атака на криптосистему Мак-Элиса, построенную на основе кодов Рида-Маллера. M.:

Дискретная математика, 1(26):10-20, 2014

–  –  –

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

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

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

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

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

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

Эффект кулисности (присутствие неестественно «плоских» объектов в сцене, полностью находящихся на одном уровне глубины). Данный эффект хорошо изучен в случае стереосъемки [1,2], но доступная литература по анализу эффекта кулисности в 2D-3D конвертации крайне ограничена;

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

Первые два алгоритма (обнаружения стробящих границ и эффекта кулисности) были протестированы на 10 полнометражных конвертированных стереофильмах и позволили выявить: 155 примеров стробящих границ, способных вызывать дискомфорт у зрителя, 136 заметных примеров сцен с эффектом кулисности. Алгоритм оценки потенциальной заметности перекрестных помех был использован для анализа и сравнения 105 полнометражных стереофильмов, как непосредственно снятых в стереоформате, так и конвертированных на этапе пост-продакшна.

В ходе работы была выполнена публикация на международной конференции Stereoscopic Displays and Applications XXV [4], входящей в списки Scopus и Web of Science; сделаны доклады на конференции «Ломоносов»

в 2013 и 2015 гг. Работа была поддержана грантом У.М.Н.И.К. 2014-2016, частично поддержана грантом РФФИ №15-01-08632-a и совместным грантом компаний Intel и Cisco.

–  –  –

1. Yamanoue H., Okui M., Yuyama I. A study on the relationship between shooting conditions and cardboard effect of stereoscopic images // IEEE Transactions on Circuits and Systems for Video technology, 2000, P. 411– 416.

2. Yamanoue H., Okui M., Okano F. Geometrical analysis of puppettheater and cardboard effects in stereoscopic HDTV images // IEEE Transactions on Circuits and Systems for Video technology, 2006, P. 744– 752.

3. Xing L., You J., Ebrahimi T., Perkis A. A perceptual quality metric for stereoscopic crosstalk perception // IEEE International Conference on Image Processing (ICIP), 2010, P. 4033–4036.

–  –  –

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

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

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

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

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

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

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

Далее необходимо применить различные методы машинного обучения.

В рамках данной работы рассматривалась разновидность методов машинного обучения — методы поиска исключений. Исключениями называются объекты, которые не соответствуют или сильно отличаются от остальных объектов в хранилище или базе данных. В задаче распознавания по походке применялись такие методы поиска исключений, как KNN, Single-class Отделение специалитета SVM, а также нечеткий метод поиска исключений на основе потенциальных функций [2].

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

Для данных двух задач были проведены соответствующие эксперименты. В каждом эксперименте приняли участие 10 человек. В задаче распознавания по походке с них брались по 20 образцов походки для обучения и по 40 образцов для тестирования. В задаче распознавания по жесту также брались по 20 образцов жестов для обучения и по 40 образцов для тестирования. Для сравнения алгоритмов использовалась единая метрика сравнения — F-мера.

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

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

Литература

1. Яковлев А. Н. Введение в вейвлет-преобразования. Н.: НГТУ, 2003.

2. Петровский М. И. Применение методов интеллектуального анализа данных в задачах выявления компьютерных вторжений // Труды Второй Всероссийской научной конференции, Методы и средства обработки информации. М.: Изд-во факультета ВМиК МГУ, 2005, с. 158–168.

–  –  –

Одной из основных задач компьютерного зрения является задача распознавания объектов на изображении: для входного изображения нужно Кафедра АСВК найти объекты интересующих классов, выделить их и указать, к какому именно классу они принадлежат. Формально говоря, на выходе требуется разметка изображения = { }, где = {(, ), (, ), } — координаты ограничивающего прямоугольника и метка класса -го объекта.

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

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

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

Рассматривались два подхода синтеза изображений дорожных знаков:

генерация по иконке дорожного знака и размножение реальных данных.

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

Для экспериментальной оценки алгоритмов синтеза была собрана и размечена выборка автодорожных знаков. Данные были получены на российских дорогах. Выборка состоит из 180 тысяч кадров. На этих кадрах 15 тысяч реальных знаков (т.е. знаков, соответствующих реальным объектам) и 93 тысячи изображений знаков в 120 классах. Трудоемкость разметки выборки составила 500 человеко-часов.

Задачу распознавания объектов можно разбить на два этапа: выделение и классификация. В данной работе использовался классификатор сверточная нейронная сеть и каскадный детектор на основе деревьев решений глубины 2 и интегральных признаков на цветовых и градиентных каналах. Архитектура нейронной сети описана в [1], устройство детектора — в [2]. Качество классификатора оценивается процентом верно классифицированных объектов, качество детектора — площадью под roc-кривой (auc, area under curve). Алгоритм выделения был протестирован на трех категориях знаков: синие круги, треугольники с красной рамкой и круги с красной рамкой.

Отделение специалитета Обучающая выборка Класc., % Выделение, auc реальные данные 92.7 0.81 0.91 0.81 96.0 0.88 0.90 0.81 реал. + равномерная синт.

93.8 0.84 0.93 0.82 реал. + обученная синт.

только равномерная синт. 82.0 0.59 0.22 0.22 только обученная синт. 58.4 0.12 0.03 0.09 94.8 размножение реал. данных 0.80 0.91 0.79 Результаты экспериментальной оценки алгоритмов классификации и выделения дорожных знаков, обученных на различных выборках Экспериментальная оценка алгоритмов синтеза показала, что использование синтетических и реальных данных в обучающей выборке улучшает качество классификации и выделения по сравнению с реальными данными. Размножение реальных данных улучшает результат только в случае классификации. Использование только синтетических данных в обучающей выборке показывает неудовлетворительные результаты.

Литература

1. Cirean D., Meier U., Schmidhuber J. A Committee of Neural Networks s for Traffic Sign Classification. Neural Networks, 2011.

2. Dollar P., Appel R., Belongie S., Perona P. Fast feature pyramids for object detection. Pattern Analysis and Machine Intelligence, 2014.

–  –  –

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

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

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

В связи с этим стоит отметить две особенности предметной области.

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

В данной работе для обучения моделей построена собственная эталонная выборка записей непрерывной речи на русском языке. Фразы корпуса построены на основе фонетически репрезентативных текстов базы ISABASE, разработанной коллегами с Филологического факультета МГУ имени М. В. Ломоносова [1]. Построена также и собственная тестовая выборка.

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

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

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

В качестве базовой выбрана аудио-модель, обучаемая с помощью инструментов библиотеки HTK (Hidden Markov Model Toolkit) на большой открытой базе размеченных записей русской речи Voxforge. Также расОтделение специалитета сматривается эта модель после дообучения её на используемой обучающей эталонной выборке видео последовательнсотей описанным в работе образом, но без добавления видео-признаков.

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

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

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

Работа выполнена в рамках проекта, поддержанного грантом «Умник».

Литература

1. Богданов Д. А. и др. База речевых фрагментов русского языка «ISABASE» // Интеллектуальные технологии ввода и обработки информации, 1998, с. 74–85.

2. Ahmad B. A. Hassanat Visual Speech Recognition, Speech and Language Technologies. 2014 Исследование протокола криптографически защищенных групповых коммуникаций с функцией отказуемости Коростелева Мария Викторовна Кафедра автоматизации систем вычислительных комплексов e-mail: mariak@seclab.cs.msu.su Научный руководитель: к.ф.-м.н., с.н.с. Гамаюнов Денис Юрьевич Вопросы обеспечения безопасности интернет-общения интересуют пользователей и разработчиков уже давно, не теряют они своей актуальности и сегодня: так, в мае 2015 года прошло заседание Совета по правам человека Организации объединенных наций, по результатам которого шифрование и анонимность в сети Интернет были причислены ООН к правам человека [1]. И хотя сегодня существует много различных технологий, призванных обеспечить защиту передаваемых по сети данных, существующие технологии имеют ряд существенных ограничений.

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

1. Совершенная секретность в будущем (Perfect Forward Secrecy) – сохранение конфиденциальности переданной во время коммуникации информации при компрометации долговременных ключей.

2. Отказуемость (Deniability) — невозможность фактически подтвердить предположения о содержании разговора и даже участие в разговоре конкретного лица. Возможность отсутствует как для третьих лиц, так и для самих участников разговора.

3. Согласованность транскрипта (Transcript synchronisation) – каждый участник коммуникации видит одинаковую или примерно одинаковую последовательность сообщений в процессе коммуникации.

На сегодняшний день все вышеуказанные свойства, за исключением свойства согласованности транскрипта, поддерживает протокол OTR (Offthe-Record Messaging) [2] и его производные. Однако протокол OTR позволяет общаться только двум собеседникам, поэтому протокол, предложенный в работе, призван заполнить нишу защищенных отказуемых групповых коммуникаций.

Предложенный вариант протокола основан на статье Яна Голдберга [3] и состоит из четырех фаз:

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

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

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

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

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

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

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

–  –  –

1. Human Rights Council Report of the Special Rapporteur on the promotion and protection of the right to freedom of opinion and expression. 2015.

2. Borisov N., Goldberg I., Brewer E. Off-the-Record Communication, or, Why Not to Use PGP. Proceedings of the 2004 ACM workshop on Privacy in the electronic society, 2004, pp. 77–84.

–  –  –

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

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

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

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

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

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

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

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

Было проведено экспериментальное исследование разработанного средства на 2-х тестовых выборках: ROP-шеллкодах из доступных баз и созданных генераторами ROP-шеллкодов, а также произвольных данных.

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

–  –  –

Динамический алгоритм балансировки нагрузки на основе миграции коммутаторов для распределенной платформы управления в программно-конфигурируемых сетях Рыжов Игорь Дмитриевич Кафедра автоматизации систем вычислительных комплексов e-mail: idryzhov@lvk.cs.msu.su Научный руководитель: чл.-корр. РАН, д.ф.-м.н., проф.

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

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

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

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

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

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

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

В процессе обзора существующих подходов к решению поставленной задачи был изучен предложенный в статье [3] алгоритм миграции коммутатора между контроллерами. Данный алгоритм обладает рядом преимуществ — во-первых, он использует только сообщения протокола OpenFlow, а во-вторых, в процессе миграции не происходит потерь пакетов данных и сообщений Packet-In. Таким образом, проблема «бесшовной» передачи управления коммутатором уже решена.

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

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

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

Литература

1. Смелянский Р.Л. Программно-конфигурируемые сети Открытые системы, 2012.

2. McKeown N., Anderson T., Balakrishnan H., Parulkar G., Peterson L., Rexford J., Shenker S., Turner J. OpenFlow: Enabling Innovation in Campus Networks SIGCOMM Computer Communication Review, vol.

38, no. 2, pp. 69–74, 2008.

3. Dixit A., Hao F., Mukherjee S., Lakshman T.V., Kompella R.

Towards an Elastic Distributed SDN Controller SIGCOMM Computer Communication Review, vol. 42, no. 4, pp. 7–12, 2013.

Кафедра АСВК Алгоритмы планирования вычислений в системах на основе интегрированной модульной авионики Селецкий Станислав Валерьевич Кафедра автоматизации систем вычислительных комплексов e-mail: leostas@lvk.cs.msu.su Научный руководитель: программист Балаханов Вадим Андреевич Необходимость планирования вычислений стоит особенно остро в системах реального времени, в которых опоздание хотя бы одной вычислительной задачи может привести к катастрофическим последствиям. Соответственно, нужно уметь так выстраивать последовательность выполнения задач на вычислителях, чтобы все они укладывались в свои директивные сроки. В этом может существенно помочь теория расписаний.

Задача построения статико-динамического расписания (СДР) возникает при разработке вычислительных систем реального времени, построенных в соответствии с концепцией интегрированной модульной авионики (ИМА) — перспективного направления развития комплексов бортового оборудования воздушных судов. Система, построенная на основе ИМА, представляет из себя набор многопроцессорных модулей, связанных между собой при помощи некоторой среды обмена.

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

Статико-динамика описанной задачи СДР заключается в следующем:

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

Требуется описать конфигурацию системы, включающую:

1. привязку разделов к модулям и процессорам системы;

2. расписание окон для каждого модуля;

3. привязку разделов к окнам;

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

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

Отделение специалитета Кроме того, в работе было доказано, что полученная задача принадлежит к классу NP-трудных задач.

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

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

Данный алгоритм был реализован на языке C++ и интегрирован в инструментальное средство, разрабатываемое в лаборатории вычислительных комплексов — систему автоматизированного проектирования функциональных задач (САПР ФЗ). Были проведены серии экспериментов как на искусственно сгенерированных данных, так и на данных, повторяющих специфику реальных бортовых систем. Результаты экспериментов показали, что полученный алгоритм справляется с поставленной задачей и строит полное корректное расписание вплоть до 90%-ной загрузки ядер работами. Была выдвинута и экспериментально подтверждена гипотеза, что дальнейшее (хоть и незначительное) ухудшение результатов работы алгоритма происходит из-за возросшего влияния времени, необходимого на переключение контекста между окнами разных разделов. Таким образом, существенную роль играет не столько равномерная загрузка ядер работами, сколько равномерная загрузка ядер разделами. И этот факт необходимо учитывать на этапе построения привязки разделов к ядрам.

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

Литература

1. Easwaran A., Lee I., Sokolsky O., Vestal S. A Compositional Framework for Avionics (ARINC-653) Systems. University of Pennsylvania, 2009

2. Lee Y., Younis M., Zhou J. Partition Scheduling in APEX Runtime Environment for Embedded Avionics Software. Proc. IEEE Real-Time Кафедра АСВК Computing Systems and Applications, с. 103-109, Oct. 1998.

–  –  –

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

Современные беспроводные сети, которые рассматриваются в этой работе, работают в соответствии со стандартом IEEE 802.11 [1] в частотных диапазонах 2.4 ГГц и 5 ГГц. Стандарт определяет ограниченный набор широкополосных пересекающихся каналов в этих диапазонах. Радио ресурсы — это набор настраиваемых параметров беспроводного передатчика (или передатчиков), такие как частота передачи, мощность и/или ширина канала передачи.

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

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

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

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

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

Рассмотренный алгоритм был реализован в рамках централизованной системы управления точками доступа, использующей протокол CAPWAP [3]. Центром этой системы является контроллер беспроводных точек доступа, развиваемый в рамках проекта WiMark Sysmes [4]. Контроллер обладает событийно-ориентированной архитектурой с микроядром в основе. Вся прикладная функциональность вынесена в динамически подгружаемые модули. Одним из таких модулей и является реализация алгоритма оптимального распределения радио ресурсов беспроводной сети.

Результатами работы являются:

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

наилучшая целевая функция для некоторого конкретного экспериментального стенда;

реализация алгоритма распределения радио-ресурсов согласно предъявленному критерию.

–  –  –

2. M. Bernaschi A CAPWAP-based solution for frequency planning in large scale networks of WiFi Hot-Spots Istituto Applicazioni del Calcolo-CNR, Rome, Italy 2011 Кафедра АСВК

3. Calhoun P., Montemurro M., Stanley D. Control And Provisioning of Wireless Access Points (CAPWAP) Protocol Specification Aruba Networks, March 2009

4. Wimark Systems http://wimarksystems.com/

–  –  –

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

В результате автором установлен вид зависимостей проводимости цепочки от степени дефазировки d, коэффициента взаимодействия со стоком s и интенсивности перелёта фотонов. Полученная зависимость подтверждает эффект DAT увеличения проводимости при добавлении дефазировки в систему, что объясняется уменьшением деструктивной интерференции между всевозможными путями распространения фотонов [5].

Таким образом, эффект DAT был воспроизведён для системы содержащей как фотоны, так и экситоны.

Литература

1. A. Bermudez, M. Bruderer, M. B. Plenio. Controlling and measuring quantum transport of heat in trapped-ion crystals. Phys. Rev. Lett., Vol. 111, 2013.

2. S. F. Huelga, M. B. Plenio. Vibrations, Quanta and Biology.

Contemp. Phys., Vol. 54, Iss. 4, 2013.

3. F. Caruso, N. Spagnolo, C. Vitelli, F. Sciarrino, M. B. Plenio. Simulation of noise-assisted transport via optical cavity networks. Phys. Rev. A, Vol. 83, 2011.

4. F. Caruso, S. F. Huelga, M. B. Plenio. Noise-enhanced classical and quantum capacities in communication networks. Phys. Rev. Lett., Vol. 105, 2010.

–  –  –

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

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

1. Их решение не может быть получено аналитически.

2. Обладают большой размерностью.

–  –  –

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

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

Отделение специалитета

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

( ( ) cos( ) ( + ) sin( ) ) (,, ) = ( ) ( + ) sin( ) cos( ) Таким образом мы получили оптимизационную задачу, которая требует вычислений для 3 параметров, где -это число кубит, и оперирует векторами длины 2, подобные размерности вызывают затруднения уже для 25 кубит.

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

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

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

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

Литература

1. Чернявский А. Ю. Минимум энтропии измерений как вычислимая мера запутанности многочастичных квантовых состояний.

2. De Burgh M.D., Langford N.K., Doherty A.C., Gilchrist A. Choice of measurement sets in qubit tomography Physical Review A, Vol. 78, No.

5, 052122, 11.2008

–  –  –

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

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

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

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

= 2 — матрица протокола — вектор верояностей — эрмитовая, неотрицательна матрица с едничным следом, вытянутая в столбец.

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

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

min ( * + * ) ( ) + =, ( ) = (1 *, 2 *,..., * ) Матрица — симметричная, положительно полуопределен

–  –  –

Для матриц, операция * : * =,, *, Отделение специалитета, — неизвестные, которые принадлежат выпуклым множествам S и K соответственно. При этом происходит переход от комплексной задачи к вещественной.

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

Литература

1. Богданов Ю.И, Кокин А.А., Лукичев В.Ф. и др. Квантовая механика и развитие информационных технологий. //Информационные технологии и вычислительные системы, 2012.

2. Богданов Ю.И., Гавриченко A.K., Лукичев В.Ф. Методы оценивания качества квантовых информационных технологий на основе квантовых измерений. // Труды Физико-Технологического Института, 2013.

3. Boyd, Stephen P. Convex Optimization // Cambridge University Press,

4. CVX – библиотека для решения задач выпуклой оптимизации.

[HTTP] (http://web.cvxr.com/cvx/doc/)

5. SDPT3 – пакет для решения оптимизационных задач на множествахконусах.[HTTP] (http://www.math.cmu.edu/ reha/sdpt3.html )

–  –  –

Каждый год вместе с производительностью суперкомпьютерных комплексов по всему миру не менее быстро растет и база пользователей подобных систем. Суперкомпьютер «Ломоносов», используемый для исследований, которые проводят ученые и студенты Московского Государственного Кафедра АСВК Университета имени М. В. Ломоносова, занимает второе место в рейтинге Топ50 суперкомпьютеров, установленных на территории СНГ и показавших наибольшую производительность на тесте Linpack (по состоянию на 31 марта 2015 года), и удерживает 58 место в авторитетном международном рейтинге самых высокопроизводительных вычислительных систем Top500 (по состоянию на 18 ноября 2014 года).

В текущей конфигурации «Ломоносов» доступны 8 разделов, количество узлов в каждой колеблется от 1 до 4096. В среднем в день выполняется от 200 до 400 задач, которые ставят на запуск 30-50 разных пользователей, причем каждый год активно используется около 400 аккаунтов, и эти числа не являются пределом. Чтобы справляться с ежедневно растущими нагрузками на суперкомпьютер «Ломоносов», на нем используется система Simple Linux Utility for Resource Management (SLURM).

SLURM — один из самых перспективных менеджеров ресурсов суперкомпьютеров. Его основные преимущества — хорошая масштабируемость и портируемость. На суперкомпьютере «Ломоносов», так же как и на многих ведущих системах списка TOP500, используется встроенный плагинпланировщик Backfill, который оперирует одноименным алгоритмом планирования. Исследования показали, что алгоритм позволяет повысить плотность использования ресурсов суперкомпьютеров на примерно 20% и уменьшить среднее время ожидания постановки задач на исполнение [1].

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

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

Реализован новый планировщик, который использует полный алгоритм планирования Backfill, а так же дополнен следующими нововведениями [2]:

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

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

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

4. Возможностью добавления квот по времени: определённое число процессоро-часовв неделю/месяц/год;

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

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

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

На системах Суперкомпьютерного комплекса Московского Университета используются разные версии SLURM. Например, на суперкомпьютере «Ломоносов» - версия 2.5.6, а на суперкомпьютере «Ломоносов-2» - версия 14.11.5. В связи с этим решение должно быть легко переносимо и использовать стандартные интерфейсы SLURM. Менеджер ресурсов SLURM обладает большим сообществом разработчиков, но несмотря на это отсутствует детальная документация системы. После проведения исследования архитектуры SLURM весь описанный набор функций был включен в ядро SLURM. Но тестирование показало, что данное решение плохо переносимо. В связи с этим была выбрана архитектура, основанная на интерфейсе wiki2, который первоначально предназначается для внешнего планировщика MOAB. Данное решение легко расширяемо и переносимо благодаря реализованным программным примитивам и полноте информации, которую новый внешний планировщик получает от SLURM.

Результаты работы были доложены на конференциях [3–4], а так же готовится материал на международную конференцию «Технологии высокопроизводительных вычислений и компьютерного моделирования» (YSC 2015), Афины.

Кафедра АЯ Литература

1. D. Jackson, Q. Snell, and M. Clement Core Algorithms of the Maui Scheduler. В издании Job Scheduling Strategies for Parallel Processing М.: Springer-Verlag, 2001. – c. 87–102

2. Жуматий С. А. Программная среда поддержки эффективного выполнения задач на параллельных вычислительных системах. – Москва, 2005.

3. Леоненков С. Расширение функциональности менеджера ресурсов суперкомпьютера SLURM. Научный сервис в сети Интернет: многообразие суперкомпьютерных миров: Труды Международной суперкомпьютерной конференции (22-27 сентября 2014 г., г. Новороссийск). – М.: Изд-во МГУ, 2014. – с. 472–476

4. Леоненков С. Расширение функциональности менеджера ресурсов суперкомпьютера SLURM. Параллельные вычислительные технологии (ПаВТ’2015): труды международной научной конференции (31 марта – 2 апреля 2015 г., г. Екатеринбург). Челябинск: Издательский центр ЮУрГУ, 2015. – с. 506

–  –  –

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

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

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

Добиться повышения точности классификации можно различными способами:

1. Учет лингвистических особенностей текста (разные части речи, отрицания).

2. Грамотный подбор параметров обучения классификаторов.

Отделение специалитета

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

Источником текстов, необходимых на этапах обучения и тестирования классификаторов, в нашем случае является сеть Интернет В качестве текстов были выбраны отзывы об отелях, магазинах, электронике. Такой выбор обусловлен тем, что к каждому из таких отзывов имеется также и численная оценка объекта. Для сбора отзывов была написана клиентсерверная программа на языках HTML+JS со стороны клиента и Java для серверной части. Было собрано около 50 тысяч отзывов, которые были позже отфильтрованы и обработаны для получения достаточно репрезентативной выборки.

Рассмотрены два метода машинного обучения: метод опорных векторов и метод нейронных сетей. Были изучены имеющиеся библиотеки, реализующие данные методы, отобраны наиболее подходящие с точки зрения эффективности, простоты использования и достаточной документированности. Это библиотеки Encog(нейросети)[1] и LibSVM[2], реализованные на языке программирования Java.

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

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

Проведен анализ влияния данных параметров на качество классификатора. Выяснилось, что существует диапазон, в котором данные параметры наиболее оптимальны. Это значения от 0,05 до 0,5.

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

Наиболее важным этапом работы являлось совмещение классификаторов и получение ансамбля классификаторов. Для оптимального подбора участников коллектива был предложен алгоритм «Удаления лишних классификаторов».

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

1. Голосование по большинству. Решение здесь принимается большинством голосов.

2. Голосование по старшинству. Здесь решение принимается самым «старшим» классификатором, который достаточно уверен в своей Кафедра АЯ оценке. Достаточная уверенность здесь является параметром и может регулироваться. В нашем случае это значение 75 и выше процентов.

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

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

Заключительным этапом работы являлось написание интерфейса программной системы, которая позволяет проводить анализ эмоциональной направленности текста, введенного пользователем. Интерфейс реализован на языках на HTML+JS на клиенте, Java(JSP) на сервере. Сервером является Apache Tomcat v7.0. Подводя итог, стоит отметить, что предложенные методы позволили добиться улучшения качества классификации до 5–6%, что достаточно много в контексте решаемой задачи.

Литература

1. Encog. Официальная страница проекта [HTML] (http://www.heatonresearch.com/encog).

2. LibSVM. Официальная страница проекта [HTML] (http://www.csie.ntu.edu.tw/ cjlin/libsvm/).

–  –  –

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

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

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

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

Представленный в работе метод реализован в программной системе, которая доступна по адресу http://pure-mesa-9322.herokuapp.com. В текущей версии реализована классификация по 16 композиторам, метод показал оценку F–меры порядка 0.8. Список композиторов может быть расширен при проведении дополнительного обучения системы.

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

–  –  –

1. Yi-Wien Liu Modelling Music as Markov Chains:Composer Identification http://esf.ccarh.org/254/254_LiteraturePack1/ [PDF] ComposerID_Liu.pdf

2. Maximos A. Kaliakatsos-Papakostas, Michael G. Epitropakis, Michael N. Vrahatis Musical Composer Identification through Probabilistic and Feedforward Neural networks - Lecture Notes in Computer Science, Vol.6025, p.411-420, 2010.

–  –  –

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

Решающие эту задачу алгоритмы называются алгоритмами уменьшения звёздной высоты регулярного выражения.

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

Литература

1. Hashiguchi K. Algorithms for determining relative star height and star height // Information and Computation. 1988. Vol. 78. p. 124–169.

2. Kirsten D. Distance desert automata and the star height problem // Theoretical Informatics and Applications. 2005. Vol. 39, no. 3. P.

455–509.

3. Hopcroft J., Motwani R., Ullman J. D. Introduction to Automata Theory, Languages, and Computation (2nd ed.). Addison-Wesley, 2000.

Отделение специалитета Диалект и интерпретатор языка Лисп для анализа древовидной разметки Кулёва Анна Сергеевна Кафедра алгоритмических языков e-mail: akuleva1993@gmail.com Научный руководитель: к.ф.-м.н., доц. Столяров А. В.

В работе рассматривается расширяемый язык разметки XML, позволяющий вводить новые атрибуты, теги и создавать документы произвольной сложности. XML-документы имеют древовидную структуру, которая может быть представлена с помощью s-выражений языка Лисп. В большинстве проектов, решающих задачи связанные с XML, основным языком является C++. В работе применяется библиотека InteLib [1], позволяющая использовать семантические особенности языка Лисп в рамках C++.

Идея работы с XML-деревом как с s-выражением не является новой. Однако в большинстве проектов (например, [2-3]) XML-теги и XML-атрибуты представляются списочными структурами. Такой подход имеет ряд минусов. Например, часто употребляемая функция cons влечет накладные расходы при работе с XML-тегами. Также данный подход ничем не отличает их от обычных списков.

В данной работе предлагается представлять XML-атрибут и XML-тег в виде атомарных s-выражений. В библиотеке InteLib существует иерархия классов, позволяющая представить целые числа, символы, сторки и т. д. в виде s-выражений. Базовым классом этой иерархии является класс SExpression. Было создано два его наследника SExpressionXmlAttr и SExpressionXmlTag, позволяющие представить XML-атрибут и XML-тег в виде s-выражений соответственно. Создан набор проблемно-ориентированных функций для работы с этими s-выражениями, а также числами, строками, файлами и директориями.

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

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

Умея работать с XML-потоком, можно писать программы, работающие по модели «клиент-сервер». Для этого созданы два s-выражения SExpressionClientPart и SExpressionServerPart, инкапсулирующие данные клиентской и серверной частей соответственно. Разработан набор проблемно-ориентированных функций для работы с созданными s-выражениями. С помощью этих инструментов были созданы шаблонКафедра АЯ ные программа-сервер и программа-клиент на языке Лисп. Они обладают базовым функционалом, но пользователь может дополнить их необходимыми ему функциями. На основе шаблонной программы-клиента был создан jabber-бот, который авторизовывает своих пользователей, играет с ними в игру «Быки и Коровы», собирает статистику и ведет логи.

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

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

Среди задач связянных с XML-деревьями существуют задачи по их преобразованию. Одним из средств для преобразований является XSLT.

XSLT-шаблон — это XML-документ, поэтому для его представления в виде s-выражения не пришлось вводить новых классов. Язык XPath — это язык запросов к элементам XML-документа, который придает XSLT выразительность. В работе реализовано подмножество языков XPath и XSLT. Была создана программа на языке Лисп, которая получет на вход XML-документ и XSLT-шаблон, а на выходе получает преобразованное дерево.

К результатам работы можно отнести следующее: была предложена модель для представления XML-деревьев и объявлений DTD-описаний в виде атомарных s-выражений. Создан диалект языка Лисп, предназначенный для обработки XML-данных; основу диалекта составляют специализированные типы s-выражений для представления XML-тегов и XML-атрибутов, а также элементов DTD-описаний, и проблемноориентированные функции для обработки этих s-выражений. Работоспособность построенной модели продемонстрирована на задачах преобразования набора XML-документов в веб-сайт и создания jabber-бота.

Литература

1. Андрей Столяров. Библиотека InteLib — инструмент мультипарадигмального программирования. Тезисы докладов II конференции разработчиков свободных программ «На Протве», Обнинск, 25-27 июля 2005 года, стр. 56-62.

2. Robert Goldman. XMLS, a simple XML parser for Common Lisp.

http://common-lisp.net/project/xmls/

3. Andrey Maskvitin. CL-Libxml2. High-lever wrapped around libXML2 and Отделение специалитета libxslt libraries.

http://cl-libxml2.googlecode.com/svn/doc/index.html

–  –  –

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

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

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

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

Кафедра АЯ Литература

1. Академия Google http://scholar.google.ru/

2. Российский индекс научного цитирования http://elibrary.ru/ project_risc.asp

3. Интеллектуальная Система Тематического Исследования НАучнотехнической информации https://istina.msu.ru/

–  –  –

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

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

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

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

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

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

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

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

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

Литература

1. Haghighat M., Rastegari H., Nourafza N., A Review of Data Mining Techniques for Result Prediction in Sports. ACSIJ Advances in Computer Science: an International Journal, Vol. 2, Issue 5, No.6, 2013.

2. Govan A.Y., Ranking Theory with Application to Popular Sports. PhD dissertation, North Carolina State University, 2008.

3. Tristan J. Barnett, Mathematical Modelling in Hierarchical Games with Specific Reference to Tennis. PhD dissertation, Swinburne University of Technology, 2006.

Кафедра СП

4. James Adam Gardner. Modeling and Simulating Football Results. 2011.

5. Friedman J. Greedy Function Approximation: A Gradient Boosting Machine. IMS, Reitz Lecture, 1999.

Разработка поддержки анализа программ на языке C# в статическом анализаторе Svace Кондратьев Михаил Владимирович Кафедра системного программирования e-mail: kondratievmikhail@gmail.com Научные руководители: к.ф.-м.н., проф. Гайсарян Сергей Суренович, к.ф.-м.н. Белеванцев Андрей Андреевич В последние годы возрос интерес к проблеме статического анализа программ. Инструменты статического анализа автоматически исследуют исходный код без реального выполнения программы. Использование таких инструментов позволяет находить ошибки, которые тяжело отследить вручную или обнаружить во время работы программы. Поиск дефектов в программе очень важен, поскольку цена последствий ошибки обнаруженной после релиза продукта может на порядки превосходить стоимость её исправления на этапе разработки. Может быть потеряно время и дорогостоящее оборудование или украдены персональные данные пользователей.

В Институте системного программирования РАН разрабатывается статический анализатор под названием Svace [1]. Его основными преимуществами являются скорость работы и высокое качество анализа. Svace позволяет проверять программы на языках C, C++ иJ ava. Для каждого языка используются два типа анализа: глубокий межпроцедурный анализ на основе аннотаций и поиск дефектов на уровне абстрактного синтаксического дерева. Первый тип позволяет исследовать сложные взаимоотношения между объектами, которые могут иметь место во время исполнения программы. Второй тип позволяет быстро находить ряд семантических и синтаксических дефектов. Оба типа расширяются за счёт специальных модулей, называемых детекторами. Каждый из них отвечает за свой тип ошибок. Например, существуют детекторы для поиска переполнения буфера, утечки ресурсов или разыменования нулевого указателя.

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

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

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

Литература

1. Иванников В.П., Белеванцев А.А., Бородин А.Е., Игнатьев В.Н., Журихин Д.М., Аветисян А.И., Леонов М.И. Статический анализатор Svace для поиска дефектов в исходном коде программ М.: Труды ИСП РАН. 2014. №1.

–  –  –

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

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

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

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

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

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

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

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

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

Литература

1. Падарян В.А., Гетьман А.И., Соловьёв М.А. Программная среда для динамического анализа бинарного кода Труды Института Системного Программирования РАН. Т. 16, 2009., С. 51–72.

2. Аветисян А., Гетьман А. Восстановление структуры бинарных данных по трассам программ Труды Института системного программирования РАН. Т. 22, 2012.

–  –  –

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

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

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

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

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

Кафедра СП Предлагается интегрировать данное преобразование в систему САПФОР для её расширения и достижения большей автоматизации процесса распараллеливания.

Литература

1. Коновалов Н.А., Крюков В.А., Михайлов С.Н., Погребцов А.А.

Fortran DVM — язык разработки мобильных параллельных программ // Ж. «Программирование». 1995. №1. С. 49–54.

2. Бахтин В.А., Клинов М.С., Крюков В.А. Автоматизация распараллеливания Фортран-программ // Труды Международной научной конференции «Суперкомпьютерные системы и их применение»

(SSA‘2010): доклады конференции. Минск: ОИПИ НАН Беларуси,

2010. С. 240–244.

–  –  –

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

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

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

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

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

Реализация решения поставленной задачи представляет собой подключаемую библиотеку функций, которые решают поставленные задачи на основе модели Inspector/Executor. Были созданы функции распределения матрицы по процессам, распределения витков по процессам и обработки массивов для параллельного выполнения программы, которые в совокупности являют собой инспектора, производящего необходимую обработку данных до начала работы распараллеливаемого алгоритма. Также была создана функция обеспечения синхронизации элементов, обеспечивая правильную работу исполнителя. Данная реализация была протестирована на программе, реализующей решение краевой задачи для двумерного квазилинейного параболического уравнения, записанного в дивергентной форме на неструктурированных треугольных сетках. На системе K-100 использование библиотеки для распараллеливания задачи с матрицей из 525313 элементов позволило достичь ускорения в 45 раз на 72 процессах.

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

Литература

1. Андрианов А. Н., Ефимкин К. Н. Подход к параллельной реализации численных методов на неструктурированных сетках. Вычислительные методы и программирование. 2007. Т. 8. С 6-17.

Кафедра СП

2. Mahesh Ravishankar, John Eisenlohr, Louis-Noel Pouchet, J.

Ramanujam, Atanas Rountev, P. Sadayappan. Code Generation for Parallel Execution of a Class of Irregular Loops on Distributed Memory Systems. The Ohio State University, Louisiana State University.

–  –  –

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

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

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

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

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

( )2 +( )2 =,

–  –  –

Результатом взвешенной медианной фильтрации является значение пикселя [3].

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

–  –  –

2. D. Zhou, X. Shen, and W. Dong. Image zooming using directional cubic convolution interpolation. IET Image Processing. vol. 6, no. 6, pp. 627

–  –  –

В настоящее время широко распространено применение геофизических методов исследования Земли на базе упругих сейсмических полей для поисков полезных ископаемых. Вибрационная сейсморазведка (ВСР) основана на использовании источников длительного воздействия с постоянной или медленно меняющейся во времени частотой, и позволяет, таким образом, перейти от временного зондирования к частотному. В данной работе предлагается вместо традиционного корреляционного подхода к решению задач ВСР использовать импедансный подход, описанный в работе В. И. Дмитриева и Г. В. Аккуратова [2]. Этот подход аналогичен методу частотного зондирования слоистых сред для переменных электромагнитных полей, математически обоснованному в 50-х годах академиком А. Н. Тихоновым, и позволяет получить полное представление о поле, возбуждаемом источником колебаний.

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

В прямой задаче рассматривается изотропная идеально-упругая плоско-слоистая среда, в которой характеристики Ламе, и плотность являются кусочно-непрерывными функциями от. Требуется найти решение системы уравнений для случая установившихся колебаний в однородной среде ( + 2) · grad div · rot rot + · + 2 · = 0. Расчёты ведутся в цилиндрической системе координат в силу осевой симметрии источника колебаний с нагрузкой (,,, ) = () ·, расположенного на поверхности земли.

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

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

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

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

1. Вычисление тензора импеданса (, ) по рекуррентным соотношениям от нижнего слоя к верхнему;

2. Расчёт спектральных характеристик (, ), (, ) по рекуррентным формулам от 1-го слоя к -му;

3. Численное определение положительных действительных нулей знаменателя Рэлея 1 (), с которыми связаны полюса подынтегральных функций преобразования Ханкеля;

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

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

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

В работе проанализировано поведение знаменателя Рэлея в положительном квадранте комплексной плоскости. Описанный алгоритм реализован в среде Matlab, использованы готовые реализации необходимых для расчётов функций Бесселя и Неймана, функция Струве реализована самостоятельно. Алгоритм БПХ, взятый из статьи [1], заключается в представлении интеграла в виде свёртки с заранее известной функцией. Готовая реализация протестирована на различных моделях сред.

Литература

1. Anderson W. L. Computer program numerical integration of related Hankel transforms of orders 0 and 1 by adaptive digital filtering.

Geophysic, 1979, 44(7):1287-1305.

2. Дмитриев В. И., Аккуратов Г. В. Математическое моделирование сейсмического частотного зондирования. М.: Изд-во Московского университета, 1984.

Отделение магистратуры

3. Самарский А. А., Гулин А. В. Численные методы: Учебное пособие для вузов. М.: Наука. Гл. ред. физ-мат. лит., 1989.

–  –  –

Криптосистема Мак-Элиса является криптосистемой с открытым ключом. Эта криптосистема была предложена в 1978 году Р. Дж. Мак-Элисом.

Стойкость криптосистемы Мак-Элиса основывается на сложности задачи декодирования кода, исправляющего ошибки, который не обладает видимой алгебраической, комбинаторной и иной структурой [1]. В 1986 году Г. Нидеррайтер предложил использовать для построения криптосистемы коды Рида-Соломона. Однако уже в 1994 году В. М. Сидельников и С. О. Шестаков построили полиномиальную атаку на такую криптосистему [2]. В 1996 году В. М. Сидельников предложил использовать для построения коды Рида-Маллера. В 2007 году Л. Миндер и А. Шокроллахи описали структурную атаку на эту криптосистему [3]. В 2013 И. В. Чижовым и М. А. Бородиным была предложена полиномиальная атака на криптосистему Мак-Элиса, построенную на основе таких кодов Рида-Маллера (, ), что НОД(, 1) = 1 [4]. В настоящей работе исследуется криптосистема Мак-Элиса, построенная на основе подкодов кода РидаМаллера. Такое исследование необходимо, так как для атак, работающих на полный код, не всегда справедлива применимость таких атак на подкод.

Начало исследований стойкости криптосистемы Мак-Элиса, построенной на подкодах кода Рида-Маллера было положено в дипломной работе Е. В. Ивановой. Тогда удалось построить полиномиальную атаку на криптосистему при НОД(, 1) = 1.

В настоящей работе исследуется вопрос построения атаки на два типа криптосистем Мак-Элиса, основанных на подкодах кода Рида-Маллера (, ) при НОД(, 1) = 1. Эти два типа криптосистем отличаются способами построения подкода. Первый тип использует подкод, полученный удалением произвольной строки из стандартной порождающей матрицы кода Рида-Маллера. Во втором типе подкод получается удалением первой строки из произвольной порождающей матрицы кода РидаМаллера (, ).

Основным результатом магистерской диссертации является построение атаки на кримтосистему Мак-Элиса при любых параметрах кода РидаМаллера (, ). В общем случае не удалось построить атаку на криптосистему с полиномиальной сложностью. Предложенная атака была реКафедра СиКИ ализована на языке програмирования С++ и проведены ряд испытательных прогонов программы с разными параметрами кода Рида-Маллера (, ), в ходе которого показано, что для взлома критосистемы с размером ключа 3.7Мб (параметры = 2, = 7) достаточно 5 часов на персональном компьютере.

Литература

1. McEliece R. J. A public-key cryptosystem based on algebraic coding theory. DSN Prog. Rep., Jet Prop. Lab., California Inst. Technol. 1978, Vol. January, Pp. 114-116.

2. Сидельников В. M., Шестаков С. О. О системе шифрования, построенной на основе обобщенных кодов Рида-Соломона. Дискрет. матем., 4:3 (1992), 57-63.

3. Minder L., Shokrollahi A. Cryptanalysis of the Sidelnikov cryptosystem.

Advances in Cryptology - EUROCRYPT 2007, Lecture Notes in Computer Science. 2007. Vol. 4515. Pp. 347-360.

4. Бородин M. А., Чижов И. В. Эффективная атака на криптосистему Мак-Элиса, построенную на основе кодов Рида-Маллера. Дискрет.

матем., 26:1(2014), 10-20.

–  –  –

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

Существующие средства анализа поведения параллельных программ, основанные на сборе трасс, такие как: Intel Trace Analyzer, Vampir, R Отделение магистратуры Scalasca, позволяют решать различные актуальные задачи исследовательского и прикладного характера. В большинстве случаев, программы сбора и анализа трасс с богатым функционалом, таким как визуализация трассы, автоматическое выявление узких мест, являются коммерческими продуктами. Многие инструменты основываются на несовместимых друг с другом форматах [1].

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

В данной системе в качестве основного формата представления трасс параллельных программ используется OTF2 (Open Trace Format 2) [2].

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

Метод сбора трасс основывается на инструментальной системе ScoreP. Метод требует предварительной инструментации параллельной программы на этапе компиляции. Метод хранения трасс параллельных программ организован на базе данных MongoDB [3]. Импорт трасс в базу данных осуществляется программой, использующей библиотеку для работы с OTF2 [2] форматом и драйвер MongoDB [3]. Методы доступа к данным трасс основываются на Node.js [4] веб-сервисе.

В системе реализованы методы визуализации трасс, позволяющие проводить анализ параллельной программы в веб-браузере. Метод основан на JavaScript библиотеке интерактивной визуализации данных D3.js (DataDriven Documents) [5].

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

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

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

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

Кафедра АЯ Разработанная система была применена для анализа трасс ряда параллельных приложений для суперкомпьютера IBM Blue Gene/P.

Литература

1. Матвеев В., Попова Н. Средства сбора трасс параллельных программ для суперкомпьютеров экзафлопсной производительности // Программные системы и инструменты. — Т. 15 из Тематического сборника. — Изд-во факультета ВМиК МГУ Москва, 2014. — С. 76Dominic Eschweiler, Michael Wagner, Markus Geimer, Andreas Knupfer, Wolfgang E. Nagel, Felix Wolf. Open Trace Format 2: The Next Generation of Scalable Trace Formats and Support Libraries. PARCO 2011: 481-490.

3. K. Chodorow and M. Dirolf. MongoDB: the definitive guide. O’Reilly Media, Inc., 2010.

4. P. Teixeira. Professional Node.js: Building Javascript Based Scalable Software. Wiley.com, 2012.

5. S. Murray. Interactive Data Visualization for the Web. O’Reilly Media, 2013.

–  –  –

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

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

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

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

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

положительная, если вычисленное число больше параметра нейтральная, если это число меньше и больше отрицательная, если число меньше Параметры и экспериментально подбирались для наибольшей точности. Они получились следующими: = 7.3, а = 6.3.

Вторая проблема связана с определением информативности словосочетаний. Большинство стандартных алгоритмов учитывают частоту упоминания словосочетаний. В этой же области словосочетания дважды практически не встречаются. Для решения этой проблемы была разработана система весов, а именно каждому слову для данного выпуска комиксов присваевается число по следующей формуле: = ln #, где # – количество раз, которое данное слово встречалось в отзывах на данный выпуск, а # – количество раз, которое слово встречалось во всех отзывах. Далее для каждого словосочетания выбирался вес, равный максимальному из входящих в него слов. Этот метод позволяет, во-первых, дать больший вес словосочетаниям, состоящим из слов, наиболее часто встречающихся в отзывах данного выпуска, а во-вторых, дать меньший вес словосочетаниям, состоящим из общеупотребительных слов, использующихся во всех отзывах (например, first issue).

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

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

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

Литература

1. Bing Liu Sentiment Analysis and Opinion Mining Morgan & Claypool Publishers, May 2012.

2. Koji Yatani, Michael Novati, Andrew Trusty, and Khai N. Truong Analysis of Adjective-Noun Word Pair Extraction Methods for Online Review Summarization Department of Computer Science, University of Toronto Toronto, Canada.

Отделение второго высшего образования

–  –  –

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

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

Алгоритмы реализованы в рамках программного комплекса BNBSolver [2], разработанном в Центре распределенных вычислений ИППИ РАН, в виде набора классов на языке C++. В BNB-Solver уже был реализован некоторый алгоритм балансировки нагрузки. В нем выделены управляющий процесс и рабочие процессы. Сначала управляющий процесс генерирует некоторое количество подзадач, заведомо большее, чем количество рабочих процессов. Далее подзадачи распределяются между рабочими процессами, которые решают их до конца. Полученные в процессе решений наилучшие найденные результаты (рекорды) пересылаются управляющему процессу, который из всех выбирает оптимальный.

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

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

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

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

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

Основные результаты выпускной квалификационной работы:

Разработаны 2 варианта алгоритма адаптивной балансировки нагрузки: с фиксированными и изменяемыми параметрами;

Разработанные алгоритмы реализованы в рамках программного комплекса для решения задач глобальной оптимизации BNB-Solver;

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

–  –  –

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

// Труды ИСА РАН, 2006, Т. 25, с. 18–25.

Разработка программного обеспечения для анализа и наглядного представления выравниваний белковых последовательностей большого объема Курин Виталий Владимирович кафедра алгоритмических языков e-mail: vitaliykurin@gmail.com Научный руководитель: к.б.н. Леонов Михаил Васильевич, к.ф.-м.н. Алексеевский Андрей Владимирович В последнее время с развитием биотехнологий растут объёмы биологических данных, особенно данных о белковых последовательностях [1].

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

Программа принимает на вход файлы с белковыми выравниваниями — строками, состоящими из символов латинского алфавита. Изначально происходит разделение на три группы: последовательности без начала (первые n символов являются гэпами4 ), без конца (последние n символов являются гэпами), полноразмерные. После этого, подобное разделение проводится еще раз внутри каждой группы — то есть, всего на выходе получается 9 групп. Далее проводится анализ последовательностей каждой группы на основе похожести. Под похожестью понимается количество совпадающих при попарном сравнении символов в j-й позиции деленное на длину выравнивания. Строится граф, в вершинах которого последовательности, а между схожими проводятся рёбра. По завершении построения графа выполняется поиск связных компонент — групп вершин, внутри которых есть пути между каждыми двумя вершинами в группе. Это и есть кластеры, поиск которых является задачей программы.

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



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

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

«Материалы для студентов "Информатика и ИКТ" 1 курс Содержание занятия Информатика и ИКТ Лекция 4 Подходы к измерению информации. Единицы измерения информации. Хранение информационных объектов различных видов на различных...»

«Вестник Псковского государственного университета УДК 537.632 А. Н. Верхозин МАГНИТООПТИКА ВЧЕРА И СЕГОДНЯ (к 170-летию открытия эффекта Фарадея) Нет другого такого физического эффекта, который бы применялся в столь далёких друг от друга областях науки и техники, как эффект, открытый Фарадеем в 1845 году. Спектр его...»

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

«Региональная информатизация МЕТОДИЧЕСКИЕ МАТЕРИ АЛЫ Методический подход, используемый для создания служебной системы дистанционного обучения служащих органов государственной власти Ленинградской области (СДО ОГВ ЛО) Санкт-Петербург 2005г. От авторов В подготовке материалов принимали участие: Резников Л.Я...»

«Гильдия Управляющих Документацией Об информационном взаимодействии органов государственной власти и местного самоуправления в условиях развития информационного общества Бачило Иллария Лаврентьевна, заведующий Сектором информационного права Института государства и права РАН, д.ю.н., профессор, заслуж...»

«1 Пояснительная записка Данная рабочая программа разработана на основе следующих нормативных документов:1. Закон РФ "Об образовании";2. Федеральный базисный учебный план для образовательных учреждений РФ от 09.03.2004 № 1312;3. Государств...»

«"Имидж России: стратегия, тактика, технологии", материалы научной конференции 26 ноября 2013г. АВДЕЕВА Н. студентка факультета политологии МГУ имени М.В. Ломоносова Формирование имиджа России на примере телеканала Russia Today Одной из важнейших тенденции в мировом сообществе является процесс его информатизации и постепен...»

«ISSN 2222-0364 • Вестник ОмГАУ № 3 (23) 2016 СЕЛЬСКОХОЗЯЙСТВЕННЫЕ НАУКИ kolmakovaek.@mail.ru; Ледовский Евгений НикоLedovskiy Evgeniy Nikolaevich, Cand. Agr. Sci., Head, лаевич, кандидат с.-х. наук, завед...»

«Министерство образования Республики Беларусь Учреждение образования "БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ" УТВЕРЖДАЮ Проректор по учебной работе д.т.н., профессор _А.А.Хмыль "12" _июня_ 2013 г. ПРОГРАММА вступительного экзамена в магистратуру по специальности 1-40 80 01 "Элементы и устройства вычи...»

«И.Н. Блинов, В.С. Романчик Java. ПРОМЫШЛЕННОЕ ПРОГРАММИРОВАНИЕ Практическое пособие Минск "УниверсалПресс" УДК 004.434 ББК 32.973.26-018.2 Б69 Авторы: доцент кафедры Численных методов и программирования БГУ, кандидат физико-математических наук И.Н. Блинов, доцент, зав. кафедрой Численных методов и программирования БГУ, канди...»

«368 вычислительные методы и программирование. 2011. Т. 12 УДК 519.6; 533.72 ДЕТЕРМИНИРОВАННЫЙ МЕТОД ЧАСТИЦ-В-ЯЧЕЙКАХ ДЛЯ РЕШЕНИЯ ЗАДАЧ ДИНАМИКИ РАЗРЕЖЕННОГО ГАЗА. ЧАСТЬ I Е. А. Малков1, М. С. Иванов1 Предлагается метод численного решения уравнения Бо...»

«Леушкин Евгений Владимирович АНАЛИЗ ЭВОЛЮЦИИ ИНСЕРЦИЙ И ДЕЛЕЦИЙ В ПОСЛЕДОВАТЕЛЬНОСТИ ДНК,...»

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

«44 ЭЛЕКТРОНИКА, ИЗМЕРИТЕЛЬНАЯ ТЕХНИКА, РАДИОТЕХНИКА И СВЯЗЬ УДК 621.397.6 И.Н. Пустынский, В.Ф. Коновалов, М.И. Курячий, И.В. Гальчук Телевизионно-вычислительная система контроля c радиационно-стойкой видеокамерой Изложены результаты разработки телевизионно-вычислительной системы контроля, предназначенной для визуа...»

«42 вычислительные методы и программирование. 2010. Т. 11 УДК 004.272.2+004.75+544.18 ТЕХНОЛОГИИ ГРИД В ВЫЧИСЛИТЕЛЬНОЙ ХИМИИ В. М. Волохов1, Д. А. Варламов1,2, А. В. Пивушков1, Г. А. Покатович1, Н. Ф. Сурков1 Рассмотрены осно...»

«ВЕСТНИК ПНИПУ Электротехника, информационные технологии, системы управления № 13 УДК 681.3.067 С.А. Воронов, А.Н. Гладков, В.В. Михалев, А.Н. Павлов Пермский военный институт внутренних войск МВД России, Пермь, Россия МЕТОДИКА ОЦЕНК...»

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

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Федеральное государственное образовательное учреждение высшего профессионального образования "СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ" ИНФОРМАЦИОННО-АНАЛИТИЧЕСКИЙ ДЕПАРТАМЕНТ УТВЕРЖДАЮ проректор по информатизации СФУ _ А.В. Сарафанов "_" 2008 г. Руководство пользователя...»

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

«М.Б.Игнатьев, Т.С.Катермина КОНТРОЛЬ И КОРРЕКЦИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ В РЕАЛЬНОМ ВРЕМЕНИ НА ОСНОВЕ МЕТОДА ИЗБЫТОЧНЫХ ПЕРЕМЕННЫХ Учебное пособие Издательство Нижневартовского государстве...»

«Достижения кафедры информатики Одним из важных результатов деятельности кафедры информатики явился вклад в подготовку специалистов в Черноморском филиале Московского государственного университета в период его становления. По прось...»

«В.Ю. Зайченко ГЕОИНФОРМАТИКА КАК САМОСТОЯТЕЛЬНАЯ НАУКА И ОТДЕЛЬНАЯ НАУЧНАЯ ДИСЦИПЛИНА Введение Новое научное направление науки информатики, получившее название Геоинформатика возникло в России в середине 70-х годов ХХ столетия в связ...»

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








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

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