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

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

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


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В. ЛОМОНОСОВА ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ СБОРНИК ТЕЗИСОВ ЛУЧШИХ ДИПЛОМНЫХ РАБОТ 2009 ...»

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

Построение по матрице СЛАУ гиперграфа Hc, в соответствие вершинам ставятся столбцы 1. Разбиение гиперграфа Hc на k частей с минимизацией метрики cost. k выбирается таким образом, что если N — порядок матрицы СЛАУ, то задача обращения матрицы порядка N/k выполнима за разумное время 2. Построение по матрице СЛАУ гиперграфа Hr, в соответствие вершинам ставятся строки 3. Разбиение гиперграфа Hr на k частей с минимизацией метрики 4. Переупорядочивание строк и столбцов исходной матрицы в соответствии с полученными разбиениями. При этом строки и столбцы, оказавшиеся в Тезисы лучших дипломных работ ВМК МГУ 2009 года одинаковых частях разбиения ставятся рядом. После переупорядочивания получаем матрицу B, для которой далее строится предобуславливатель.

Очевидно, что система с матрицей B получается из системы с матрицей A эквивалентными преобразованиями — переупорядочиванием уравнений и переименованием переменных.

5. Получение предобуславливателя M из матрицы B следующим образом:

1. Рассматриваем надиагональные блоки в матрице B. Обозначим их Bi 2. Eсли det(Bi)0, то на то место, где в матрице B стоит блок Bi в матрице M ставится блок {Bi}- 3. Иначе, на то место, где в матрице B стоит блок Bi в матрице M ставится единичная матрица соответствующего размера.

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

Существует несколько инструментов, позволяющих строить разбиения гиперграфов: PaToH, hMETIS, Mondriaan, MLPart, Parkway, Zoltan. Однако, эмпирические тесты показывают, что для разбиения очень большой матрицы на большое количество частей, сам генератор разбиений должен работать распределнно. Из вышеперечисленных инструментов параллельную работу поддерживают лишь Zoltan и Parkway. Из результатов тестов, представленных в [3] видно, что для решения рассматриваемых в данной работе задач оптимальным является использование Zoltan.

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

Были обработаны матрицы различных размеров от 105 до 106, в частности, матрица размером 227000 227000 с ненулевых элементов, полученная в реальной задаче факторизации. Размеры получаемых блоков составляли от до. Количество одновременно запускаемых процессов составляло от 128 до 1024. Время работы параллельного этапа составляло менее 15 минут для всех случаев. Были выведены теоретические оценки вероятности обратимости надиагональных блоков, подтвердившиеся эмпирически. Таким образом было установлено, что вышеописанный метод предобуславливания на основе разбиений гиперграфов пригоден для использования в практических целях повышения эффективности блочного алгоритма Ланцоша при решении задачи факторизации больших чисел.

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

Литература [1] Н. О. Василенко. Теоретико-числовые алгоритмы в криптографии. М.:МЦНМО, 2003.

[2] Bradford Hovinen. Blocked lanczos-style algorithms over small finite fields, 2004.

[3] K.D. Devine, E.G. Boman, R.T. Heaphy, R.H. Bisseling, and U.V. Catalyurek. Parallel hypergraph partitioning for scientific computing. Parallel and Distributed Processing Symposium, International, 0:102, 2006.

[4] P. Montgomery. A block lanczos algorithm for finding dependencies over gf(2). Lecture Notes in Computer Science, vol. 921, Springer-Verlag, pages 106–120, 1995.

Кафедра МК СВОБОДНЫЕ ОТ СУММ МНОЖЕСТВА В ГРУППЕ ZP Павлов Алексей Игоревич студент кафедры математической кибернетики e–mail: pavlov.alexey.i@gmail.com Научный руководитель – профессор Сапоженко Александр Антонович Понятие свободного от сумм множества было введено Шуром (Shur) в 1914 году.

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

Также была поставлена задача центрируемости свободных от сумм множеств [4].

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

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

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

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

Литература 1. А.А.Сапоженко. Асимптотика числа множеств, свободных от сумм в группах простого порядка. Доклады Академии Наук, 2009, том 424, № 4, С. 1– 2. P.H. Diananda and H.P. Yap. Maximal sum-free sets of elemets of finite groups, Proc. Japan Acad. 3. H.P. Yap. Maximal sum-free sets in finite abelian groups. IV., Nanta Math.

5(1972),no. 3, 70- 4. J.-M. Deshouillers, V.F. Lev. Refined bound for sum-free sets in groups of prime order. Bulletin of the London Mathematical Society, to appear.

Тезисы лучших дипломных работ ВМК МГУ 2009 года КРИПТОАНАЛИЗ РОССИЙСКОГО СТАНДАРТА ФУНКЦИИ ХЭШИРОВАНИЯ Ручкина Анастасия Александровна студент кафедры математической кибернетики e-mail: minas_anor@mail.ru Научный руководитель – к.ф.-м.н Карпунин Григорий Анатольевич Дипломная работа посвящена исследованию стойкости российского стандарта функции хэширования в случае изменения некоторых преобразований в конструкции блочного шифра, на котором основана данная хэш-функция.

До 2008 года хэш-функция ГОСТ Р 34.11-94 являлась одной из наиболее стойких в мире: не было известно ни одной атаки, сложность которой была бы меньше, чем 2128 для нахождения коллизий и 2 256 для нахождения прообраза. Однако в 2008 году группа европейских криптологов [1] предложила атаку, которая понижала эти цифры до 2105 и соответственно. Слабым местом хэш-функции ГОСТ Р 34.11-94 оказался параллелизм на этапе вычисления функции сжатия: использование четырех параллельно работающих шифраторов. Атака основывается на нахождении неподвижных точек для одного такого шифратора, однако никаким способом не используется строение самого блочного шифра.

Проведем некоторые упрощения в шаговой функции блочного шифра ГОСТ 28147 89: уберем циклический сдвиг и заменим сложение по модулю 232 обычным побитовым сложением. В таком случае каждый шифратор можно разбить на 8 подшифраторов, работающих по аналогичной схеме. Для каждого из них будет определен свой S-box, свой открытый текст (8 бит) и свой ключ (32 бита), которые будут получаться из открытого текста (64 бита) и ключа (256 бит) исходного шифратора. Рассмотрим данное разбиение ключа и открытого текста:

1) Ключи.

a. Исходный ключ: K (k77 ||... || k7i ||... || k70 ||... || k07 ||... || k0i ||... || k00 ) b. Ключ для i го подшифатора: Ki ( k7i ||... || k0i ) 2) Открытые тексты.

a. Исходный открытый текст: P ( L7 ||.. || Li ||... || L0 || R7 ||... || Ri ||...R0 ) b. Открытый текст для i го подшифатора: Pi ( Li || Ri ).

Рассмотрим проведение атаки на хэш-функцию ГОСТ Р 34.11-94 при данных упрощениях структуры блочного шифра Применяя указанные упрощения к двум шифраторам при условии симметричности h и h1, мы можем разбить их работу на 8 эквивалентных систем вида:

Кафедра МК h0i E ( K0i, h0i ), | h0i | | h1i | 8,| K0i | | K1i | 32, i 0.. h1i E ( K1i, h1i ) Далее сделаем ограничение на вид одного из преобразований на этапе генерации ключей хэш-функции: A( X ) ( g63 ( x63 ) || g62 ( x62 ) ||.. || g1 ( x1 ) || g 0 ( x0 )).

При данном преобразовании A получаем зависимость между ключами ( g 2i7 (k07i ) || g 2i6 (k06i ) ||... || g 2i2 (k02i ) || g 2i1 (k01i ) || g 2i0 (k00i )) K1i f, где индексы g i j и константа f определяются преобразованиями этапа генерации ключей.

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

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

Таким образом, сложность нахождения коллизии для хэш-функции в такой схеме составляет 272 вызовов функции сжатия, или, применяя обобщенный парадокс о днях рождения [2] - 274.

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

Литература:

1. Mendel F., Pramstaller N., Rechberger C., Kontak M., and Szmidt J.: Cryptanalysis of the GOST Hash Function, Crypto 2008, LNCS 5157, pp. 162-178, Springer-Verlag, 2. Wagner D.: A generalized birthday problem, Crypto 2002. LNCS 2442, pp. 288–303. Springer Verlag, Тезисы лучших дипломных работ ВМК МГУ 2009 года МЕХАНИЗМ СИММЕТРИЧНОГО УДАЛЕННОГО ВЫЗОВА МЕТОДОВ, ОСНОВАННЫЙ НА ВЫСОКОУРОВНЕВОМ ЯЗЫКЕ СЕРИАЛИЗАЦИИ ДАННЫХ Работа удостоена диплома III-ей степени Клеменков Павел Андреевич студент кафедры автоматизации систем вычислительных комплексов e-mail: parser@cs.msu.su Научный руководитель – к.ф.-м.н., доцент Гуляев Анатолий Викторович Задача разделения вычислительных ресурсов является одной из основных задач, которую решают инженеры и программисты уже на протяжении полувека. Именно эта задача привела к появлению первой компьютерной сети APRANET в 1958 году. С тех пор сети начали быстро развиваться, расширяться, увеличивалась пропускная способность, уменьшалось время отклика, и, конечно же, менялись технологии разработки распределенных приложений. Одной из таких технологий является RPC (Remote Procedure Call) – удаленный вызов процедур.

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

Автор языка программирования Python Guido van Rossum однажды сказал: «Основной задачей современного программирования является создание удобных и мощных инструментов для разработчика». Поэтому целью данной работы явилось проектирование и создание современного, функционального и удобного механизма удаленного вызова процедур.

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

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

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

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

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

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

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

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

Литература 1. Andrew D. Birrell, Bruce Jay Nelson. Implementing remote procedure calls // ACM Transactions on Computer Systems, Volume 2, Issue 1. 1984. P. 39- Тезисы лучших дипломных работ ВМК МГУ 2009 года МЕТОДЫ ОЦЕНКИ ЭФФЕКТИВНОСТИ ЗНАЧЕНИЙ ПАРАМЕТРОВ УПРАВЛЕНИЯ ВИДЕОКОДЕКОМ Работа удостоена диплома II-ей степени Рагулина Кира Олеговна студентка кафедры Автоматизации Систем Вычислительных Комплексов e–mail: ragulina.keira@gmail.com Научный руководитель – к.ф.-м.н. Ватолин Дмитрий Сергеевич Современный мир сложно представить без цифрового видео. Однако видео обладает такими размерами, что не представляется возможным хранить его в исходном виде, поэтому сжатие является одной из главных задач в области работы с цифровым видео [8]. Разные настройки видеокодеков ведут к сильно различающимся результатам, поэтому актуальна задача анализа значений используемых параметров сжатия видео. Стоит отметить, что у видеокодеков, как правило, довольно много параметров, а процесс сжатия является весьма трудоемким. Поэтому перепробовать все возможные настройки и выбрать лучшие не представляется возможным. При анализе качества определенного набора настроек (значений параметров) нас в первую очередь интересует время кодирования и качество закодированного видео (характеризующее похожесть оригинала и сжатого видео [1,8]).

Традиционно рассматривалась задача выбора оптимальных наборов значений параметров [6,9] и анализа отдельных параметров с использованием внутреннего строения частей видеокодека, настраиваемых этими параметрами (например, работы международных стандартов ISO/IEC MPEG-4, JVT). В этой дипломной работе показано, что такая постановка задачи не позволяет делать выводы касательно эффективности значений параметров и существующие методы решения этих традиционных задач не применимы для задачи анализа параметров видеокодека с точки зрения эффективности их значений. В дипломной работе предложены два метода анализа параметров видеокодека и оценки эффективности их значений: метод анализа параметров видеокодеков с точки зрения эффективности их значений в областях с фиксированным соотношением между временем кодирования и качеством закодированного видео и метод анализа параметров видеокодеков с точки зрения средней эффективности их значений по отношению к другим значениям этих параметров.

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

Кафедра АСВК Разработанные методы были апробированы на видеокодеке x264 [4] стандарта MPEG- AVC/H.264 [5] и получены практические рекомендации по использованию их значений [2].

Литература 1. Ватолин Д., Паршин А. Сравнения кодеков стандарта MPEG-4 AVC/H.264 с использованием объективных метрик // Труды конференции Graphicon-2006, 2006. C.447-454.

2. Анализ параметров видеокодека x264 стандарта MPEG-4 AVC/H.264 [pdf] (http://www.compression.ru/video/codec_comparison/x264_options_analysis_08.ht ml).

3. Лотов А.В., Поспелова И.И. Конспект лекций по теории и методам многокритериальной оптимизации. М.: ВМиК МГУ им. М.В. Ломоносова, 2006. 132 с.

4. Видеокодек x264 стандарта MPEG-4 AVC/H. (http://www.videolan.org/developers/x264.html).

5. Coding of audio-visual objects – Part 10: Advanced Video Coding - ISO/IEC 14496 10:2005 (http://www.iso.org/iso) 6. Kwon D., Agathoklis P., Driessen P. Performance and Computational Complexity Optimization in a Configurable Video Coding System // Wireless Communications and Networking. 2003. 3. Р.2086-2089.

7. Рагулина К.О., Попов В. Д., Паршин А.Е. Алгоритмы анализа значений параметров кодирования видеокодеков // Новые информационные технологии в автоматизированных системах: материалы двенадцатого научно практического семинара. № 12. М.: Моск. гос. ин-т электроники и математики.

2009. С.39-50.

8. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных.

Устройство архиваторов, сжатие изображений и видео. М.: ДИАЛОГ-МИФИ, 2003. 384 с.

9. Vanam R., Riskin E., Hemami S., Ladner R. Distortion-Complexity Optimization of the H.264/MPEG-4 AVC Encoder using the GBFOS Algorithm // Data Compression Conference. 2007. Р.303-312.

Тезисы лучших дипломных работ ВМК МГУ 2009 года АЛГОРИТМ МАТИРОВАНИЯ ВИДЕОПОСЛЕДОВАТЕЛЬНОСТИ Синдеев Михаил Сергеевич студент кафедры АСВК e-mail: m_sindeev@mail.ru Научный руководитель – к.ф.-м.н. Конушин Антон Сергеевич Дипломная работа посвящена задаче матирования видеопоследовательности – выделения объекта переднего плана с целью наложения на новый фон, либо раздельной обработки (например, цветокоррекции) переднего плана и фона. Объект переднего плана должен выделяться с учетом полупрозрачных областей, что делает его выглядящим естественно при наложении на новый фон.

Широкое применение матирование нашло в кино: изначально неподвижные или подвижные (покадровые) маски («маты») объекта переднего плана рисовались на стеклянных панелях [1] и предотвращали экспонирование фона на пленку, куда затем отдельным проходом экспонировался новый фон на основе инвертированной маски.

В конце XX – начале XXI появились технологии цифровой обработки видео.

а) исходный кадр б) результат Применительно к матированию Рис. 1. Пример из х/ф «Преодоление» (Invincible, цифровое видео дает возможность более детальной 2006).

проработки отснятой сцены и практически неограниченного увеличения числа слоев;

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

Пример матирования актера для добавления элементов фона приведен на рис. 1.

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

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

F (1 )B, где C – цвет изображения, F, B – цвета объекта и фона соответственно, – C коэффициент смешивания ( [0, 1]). Изображение коэффициентов образует маску объекта, называемую альфа-каналом.

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

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

Алгоритм реализован в виде консольного приложения на языке C++. Было проведено сравнение с существующими аналогами: программой «Клякса» [3] (осуществляет только бинарную сегментацию) и программой RobustMatting [4], содержащей 2 режима обработки:

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

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

Важной составляющей такого набора должно являться наличие масок ключевых кадров и а) исходный б) «Клякса»

известного результата (масок всех кадров или кадр некоторых кадров – контрольной выборки).

Для 20 тестовых видеопоследовательностей были созданы ключевые кадры. По итогам тестирования выборка была разбита на 3 части: в) г) предлагаемый простые видео (искусственные), с RobustMatting алг.

которыми все алгоритмы справлялись хорошо (для контроля) Рис. 2. Сравнение алгоритма с средние по сложности, на которых хотя бы один их сравниваемых алгоритмов аналогами работает приемлемо сложные, с которыми ни один из сравниваемых алгоритмов не справляется (т.е.

выдает неадекватные маски объектов, и численное сравнение не имеет смысла) В численном сравнении были использованы средние по сложности видеопоследовательности. Для них были созданы точные маски всех кадров для численного сравнения. Типичный результат работы алгоритмов показан на рис. 2 (показан 50-й кадр видео, отслеживание маски осуществлялось с 1-го кадра).

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

Литература 1. Hanson B. Matte Painting: Art in Film Special Effects. – [PPT] (http://www graphics.stanford.edu/courses/cs99d-00/projects/BrookeHanson-specialfx.ppt) 2. Levin A., Lischinski D., Weiss Y. A Closed Form Solution to Natural Image Matting. – Proc. of IEEE CVPR, 2006, p. 61– 3. Claxa. – [HTML] (http://patchmaker.net/Claxa/) 4. Wang J., Cohen M. Optimized Color Sampling for Robust Matting. – Proc. of IEEE CVPR, 2007, p. 1– Тезисы лучших дипломных работ ВМК МГУ 2009 года СОЗДАНИЕ ПАРАЛЛЕЛЬНОГО ЯДРА АНАЛИЗА СОБЫТИЙ ДЛЯ СИСТЕМЫ ОБНАРУЖЕНИЯ И ПРЕДОТВРАЩЕНИЯ АТАК Казачкин Дмитрий Сергеевич студент кафедры автоматизации систем вычислительных комплексов e–mail: zok@lvk.cs.msu.su Научный руководитель – к.ф.-м.н., м.н.с. Гамаюнов Денис Юрьевич Дипломная работа посвящена задаче анализа сетевого трафика на высокоскоростных сетевых каналах, актуальной в области информационной безопасности. Эффективность систем защиты от компьютерных атак, поточных антивирусов, межсетевых экранов уровня приложений и тому подобных систем при функционировании на современных каналах Gigabit Ethernet во многом определяется эффективностью решения рутинных задач по сбору данных с канала, передаче их по стеку протоколов в ядре операционной системы, и собственно задач анализа данных.

Для упрощения построения анализаторов сетевого трафика в лаборатории Вычислительных комплексов кафедры АСВК разрабатывается специализированная программная среда AURA (Automata for Recognition and Analysis – автоматы для распознавания и анализа), в состав которой, в частности, входит проблемно ориентированный автоматный язык программирования и среда поддержки выполнения программ на этом языке.

Основной задачей данной работы было создание параллельного аналога существующей среды поддержки выполнения программ (RTS – RunTime System) для языка программирования AURA, при обеспечении функциональной совместимости и обратной совместимости по исходному коду. Разработанная RTS позволяет организовать быструю обработку асинхронных потоков событий за счет использования возможностей современных многоядерных процессоров. RTS была реализована для операционных системам семейства Windows 2000/XP и Linux.

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

Результаты работы докладывались на конференциях SYRCoSE 2008, РусКрипто 2009.

Литература Кафедра АСВК 1. Кеммерер Р., Виджна Д. Обнаружение вторжений: краткая история и обзор [HTML] (http://www.osp.ru/text/302/181714.html) 2. Пировских А. Snort: инструмент выявления сетевых атак [HTML] (http://www.thg.ru/network/20051020/index.html) 3. Deri L. Improving Passive Packet Capture: Beyond Device Polling [PDF] (http://luca.ntop.org/Ring.pdf) 4. Rizzo L. Device Polling Support for FreeBSD [HTML] (http://info.iet.unipi.it/~luigi/polling/) 5. Deri L. nCap: Wire-speed Packet Capture and Transmission [PDF] (http://luca.ntop.org/nCap.pdf) 6. Mikolasek V. Intrusion Detection Systems - State of the Art Report [PDF] (http://www.vmars.tuwien.ac.at/php/pserver/extern/download.php?fileid=1524) 7. Wang H.J., Guo C., Simon D.R., Zugenmaier A. Shield: Vulnerability-Driven Network Filters for Preventing Known Vulnerability Exploits. [PDF] (http://research.microsoft.com/~helenw/papers/shieldSigcomm04.pdf) 8. Schear N., Albrecht D.R., Borisov N. High-Speed Matching of Vulnerability Signatures [PDF] (http://www.cs.uiuc.edu/homes/nschear2/raid-2008.pdf) 9. Vossen J.P. Snort Intrusion Detection and Prevention Guide [HTML] (http://searchsecurity.techtarget.com/generic/0,295582,sid14_gci1083823,00.html) 10. Jacob N., Brodley C. Offloading IDS computation to the GPU [PDF] (http://www.acsac.org/2006/papers/74.pdf) 11. Vasiliadis G., Antonatos S., Polychronakis M., Markatos E.P., Ioannidis S. Gnort:

High Performance Network Intrusion Detection Using Graphics Processors [PDF] (http://www.ics.forth.gr/dcs/Activities/papers/gnort.raid08.pdf) 12. Kazachkin D., Gamayunov D. Network traffic analysis optimization at signature based intrusion detection systems. // In Proceedings of SYRCoSE 2008, Vol 1, p. 27 13. REDSecure: обнаружение и предотвращение атак [HTML] (http://redsecure.ru/) 14. Гамаюнов Д. Ю. Обнаружение компьютерных атак на основе анализа поведения сетевых объектов. // Москва, 2007. Кандидатская диссертация.

15. Eckmann S.T., Giovanni V. G., Kemmerer R.A. STATL: An Attack Language for State-based Intrusion Detection [PDF] (www.cs.ucsb.edu/~vigna/publications/2000_eckmann_vigna_kemmerer_statl.pdf) 16. Lattner C., Adve V. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation [PDF] (http://llvm.org/pubs/2003-09-30 LifelongOptimizationTR.pdf) 17. Гамаюнов Д.Ю., Казачкин Д.С. AURA: программная платформа высокоскоростного анализа сетевого трафика для задач информационной безопасности. // Материалы конференции РусКрипто'09, 2009 г. [PDF] (http://ruscrypto.ru/netcat_files/File/ruscrypto.2009.008.zip) 18. Blaise B. POSIX Threads Programming [HTML] (https://computing.llnl.gov/tutorials/pthreads/) 19. Giovanni V. G., Kemmerer R.A. NetSTAT: A Network-based Intrusion Detection Approach [PDF] (http://www.acsac.org/1998/presentations/wed-a-1030-vigna.pdf) 20. Eckmann S.T. Translating Snort rules to STATL scenarios [PDF] (http://www.raid symposium.org/raid2001/papers/eckmann_raid2001.pdf) Тезисы лучших дипломных работ ВМК МГУ 2009 года РАЗРАБОТКА И РЕАЛИЗАЦИЯ СРЕДСТВА АНАЛИЗА РЕЗУЛЬТАТОВ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ НА ОСНОВЕ МЕТОДОВ НЕЧЁТКОГО ПОИСКА Работа удостоена диплома I-ей степени Черей Максим Витальевич студент кафедры автоматизации систем вычислительных комплексов e–mail: fill_os_off@lvk.cs.msu.su Научный руководитель – ассистент Волканов Дмитрий Юрьевич Дипломная работа посвящена одному из способов анализа результатов имитационного моделирования.

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

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

В рамках данной работы рассматриваются возникающие задачи анализа трасс выполнения имитационных моделей [7] и выделяется ряд задач, которые не решаются существующими средствами стенда ПНМ. В работе подробно рассматриваются следующие прикладные задачи: задача анализа трасс выполнения циклограмм обменов по каналу данных МКИО [8] и задача анализа трасс выполнения циклограмм функциональных задач.

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

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

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

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

Литература 1. Грибов Д.И., Смелянский Р.Л. Комплексное моделирование бортового оборудования летательного аппарата // Методы и средства обработки информации. Труды второй Всероссийской научной конференции. - М.: Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, 2005. - С.59- 2. Балашов В.В., Бахмуров А.Г., Волканов Д.Ю., Смелянский Р.Л., Чистолинов М.В., Ющенко Н.В. Применение стенда полунатурного моделирования для разработки вычислительных систем морского навигационного комплекса // Программные системы и инструменты. Тематический сборник № 9, М.: Изд-во ф-та ВМиК МГУ, 2008. стр. 153 3. Gonzalo Navarro, A Guided Tour to Approximate String Matching // University of Chile, 4. Graham A.S. String Search. // School of Electronic Engineering Science University College of North Wales,1992.

5. Nakatsu, N., Y. Kambayashi, S.Yajima A longest common subsequence algorithm suitable for similar text strings. // Acta Informatika 18, 171-179, 1982.

6. Landau, G.M., U. Vishkin Fast string matching with k differences. // Jour. Comp. and Susyem Sci. 37, 63-78,1988.

7. Волканов Д.Ю., Черей М.В. Применение алгоритмов нечткого поиска для анализа результатов имитационного моделирования ВСРВ // Научная сессия МИФИ-2008, том 13, Москва, 2008.

8. Государственный стандарт РФ «Интерфейс магистральный последовательный системы электронный модулей» ГОСТ Р 52070-2003.

Тезисы лучших дипломных работ ВМК МГУ 2009 года ОБЕСПЕЧЕНИЕ СОВМЕСТИМОСТИ ТРЕБОВАНИЙ К ИНФОРМАЦИОННОМУ ОБМЕНУ ПРИ ПЛАНИРОВАНИИ С ПРИМЕНЕНИЕМ РАЗЛИЧНЫХ ЭВРИСТИК Работа удостоена диплома III-ей степени Шестов Птр Евгеньевич студент кафедры Автоматизации систем вычислительных комплексов e–mail: shestovp@mail.ru Научный руководитель – м.н.с Балашов Василий Викторович В распределнных встроенных системах реального времени (ВСРВ) для взаимодействия между подсистемами широко используются каналы с централизованным управлением. Расписания информационного обмена по этим каналам строятся статически, с учтом требований к обмену, обусловленных особенностями аппаратных и программных средств конкретной ВСРВ. Требования к обмену могут быть несовместимыми, что означает невозможность построения корректного расписания обмена по каналу. В этом случае разработчику необходимо внести коррективы в требования к обмену (например, сократить минимальный резерв свободного времени в расписании), чтобы обеспечить возможность построения корректного расписания для заданного набора периодических заданий.

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

1) диапазоны изменения требований;

2) ограничение совместимости искомого решения (откорректированных требований).

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

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

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

Литература 1. Балашов В.В. Алгоритмы формирования рекомендаций при планировании информационного обмена по каналу с централизованным управлением. // Известия РАН.

Теория и системы управления, 2007, N.6, с. 76-84.

2. Костенко В.А., Гурьянов Е.С. Алгоритм построения расписаний обменов по шине с централизованным управлением и исследование его эффективности. // М., Программирование, 2005, No. 6, стр. 340-346.

3. Балашов В.В. Шестов П.Е. Формирование рекомендаций по обеспечению совместимости требований к обмену по общей шине во встроенных системах реального времени // Труды Четвертой международной конференции "Параллельные вычисления и задачи управления" (РАСО'2008). М.: ИПУ им. В.А.Трапезникова РАН. 2008. С. 1385- 4. Balashov V.V., Kostenko V.A., Smeliansky R.L. A Tool System for Automatic Scheduling of Data Exchange in Real-Time Distributed Avionics Systems // Proceedings of the Second European Conference For Aero-Space Science, 2007.

5. Мину М. Математическое программирование. Теория и алгоритмы // М.: Наука. Гл.

ред. физ.-мат. лит., 1990.

6. М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

7. Blazewicz J., Ecker K., Pesch E., Schmidt G., Weglarz J. Handbook on Scheduling: From Theory to Applications. Springer, 2007.

8. Liu C.L., Layland J.W. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment // Journal of the ACM.1973. 20. № 1. P. 46 – 9. A. K. Mok, Fundamental design problems of distributed systems for the hard-real-time environment, Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, 1983.

Тезисы лучших дипломных работ ВМК МГУ 2009 года БИБЛИОТЕЧНАЯ ПОДДЕРЖКА ОБЪЕКТНО-ОРИЕНТИРОВАННОЙ МОДЕЛИ ЯЗЫКА РЕФАЛ Бронштейн Игорь Евгеньевич студент кафедры алгоритмических языков e–mail: igor.bronstein@gmail.com Научный руководитель — к. ф.-м. н. Столяров Андрей Викторович Дипломная работа посвящена поддержке вычислительной модели языка Рефал в рамках проектов на языке Си++. В ходе работы реализованы в виде библиотеки классов Си++ рефал-вычислитель приемлемой эффективности и транслятор кода из синтаксиса языка Рефал-5 в Си++.

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

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

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

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

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

Новая реализация включает в себя:

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

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

• реализацию безымянных предложений (with-блоков) языка Рефал, ранее полностью отсутствующую в InteLib;

• поддержку всех функций стандартной библиотеки языка Рефал-5.

Благодаря последним двум пунктам было достигнуто полное соответствие поддерживаемого диалекта описанию языка Рефал-5.

Так как создавать модуль, целиком состоящий из моделирующих конструкций библиотеки InteLib, бывает затруднительно, был также реализован транслятор из синтаксиса языка Рефал-5 в Си++. Транслятор является самоприменимым (написан на самом Рефале) и таким образом позволяет легко продемонстрировать работоспособность созданной реализации Рефала. Кроме того, он обладает следующими свойствами:

• возможностью принимать на вход любое число файлов на Рефале;

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

Эти требования являются стандартными для трансляторов, являющихся частью InteLib (например, им удовлетворяют соответствующие трансляторы языков Лисп и Scheme). Таким образом, в отличие от уже существовавшего прототипа транслятора Рефала, вновь созданный транслятор аналогичен всем присутствующим в InteLib. Интересным его свойством является возможность в случае наличия специального флага командной строки компилировать несколько файлов на Рефале-5 непосредственно в исполняемый файл.

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

Результаты работы были включены в библиотеку InteLib и доступны для скачивания по адресу http://www.intelib.org.

Литература [1] Столяров А. В. Интеграция изобразительных средств альтернативных языков программирования в проекты на C++. Рукопись депонирована в ВИНИТИ РАН 06.11.2001, 2319-В2001, Москва, 2001.

Тезисы лучших дипломных работ ВМК МГУ 2009 года ПРОГРАММИРУЕМЫЙ АГЕНТ ВЗАИМОДЕЙСТВИЯ ПО ПРОТОКОЛУ ПЕРЕДАЧИ ГИПЕРТЕКСТА Работа удостоена диплома II-ей степени Власенко Юлия Владимировна студентка кафедры алгоритмических языков e–mail: yuliavlasenko@gmail.com Научный руководитель – к. ф.-м. н. Столяров Андрей Викторович Работа посвящена вопросам реализации программы, способной осуществлять взаимодействия по протоколу передачи гипертекста, как в качестве клиента, так и в качестве сервера. Фактически такая программа представляет собой агента взаимодействий по протоколу HTTP [1]. Ключевой особенностью созданной программы является возможность управления поведением агента на алгоритмически полном языке. Эта возможность реализована путем встраивания в программу интерактивного интерпретатора языка Лисп, при помощи средств библиотеки InteLib [2], реализующих вычислительную модель языка Лисп в рамках программ на C++.

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

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

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

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

Литература 1. Hypertext Transfer Protocol – HTTP/1.1. Official Internet Protocol Standards:

Standards Track: RFC 2616.

2. The InteLib Home Page [HTML] (http://www.intelib.org) 3. W. Richard Stevens. UNIX Network Programming, Volume 1: Interprocess Communications (2nd Edition). Prentice Hall, 1999. 592 p.

Тезисы лучших дипломных работ ВМК МГУ 2009 года МЕТОДЫ И АЛГОРИТМЫ КОНТРОЛЯ ДОСТУПА И АВТОМАТИЗАЦИИ ТЕХНИЧЕСКОЙ ПОДДЕРЖКИ В СЕТЯХ ПОСЛЕДНЕЙ МИЛИ Федосеев Василий Олегович студент кафедры алгоритмических языков e–mail: vasfed@vasfed.ru Научный руководитель – профессор Мальковский Михаил Георгиевич Разработанная автором система автоматизации контроля доступа клиентов мультисервисной сети представляет собой альтернативу традиционной авторизации PPP-соединений и менее распространенной Port-Security функциональности управляемых коммутаторов.


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

Ключевым понятием является «привязка» - жесткое установление соответствия между клиентским оборудованием и точкой подключения к среде передачи данных провайдера. Реализовано управление коммутаторами Dlink DES3526 и другими, брандмауэром маршрутизаторов на базе серверов под управлением FreeBSD.

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

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

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

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

Литература 1. Фейт С. - TCP/IP. Архитектура, протоколы, реализация. – Москва:Лори, 2000, 424с.

2. Обзор технологии DLink IP-MAC-PortBinding – март http://www.dlink.ru/up/uploads_media/FAQ_IP_MAC_Port_Binding.pdf [pdf] 3. Программа сетевой академии Cisco CCNA 1 и 2. Вспомогательное руководство, 3-е изд., с испр.: Пер. с англ. – Москва:Издательский дом «Вильямс», 2005. – 1168 с.

4. Mauro D. R., Schmidt K. J. - Essential SNMP, Second Edition. – O‘Reilly Media, 2005, 460 с.

5. Perkins D., Mcginnis E. - Understanding SNMP MIBS. - Prentice Hall, 1996, 528 с.

6. James Turnbull - Pro Nagios 2.0 – Berkeley:Apress, 2006 – 423 с.

Кафедра АЯ ПРОГРАММНЫЕ СРЕДСТВА ПОДДЕРЖКИ КОМПЬЮТЕРНОГО СЛОВАРЯ БУКВЕННЫХ И МОРФЕМНЫХ ПАРОНИМОВ Работа удостоена диплома III-ей степени Белова Татьяна Сергеевна студентка кафедры алгоритмических языков e–mail: tatjana.inbox@gmail.com Научный руководитель – к.ф.-м.н., доцент Большакова Е. И.

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

Рассматриваются паронимы двух типов: буквенные (различающиеся несколькими буквами, например, время – бремя) и морфемные (различающиеся несколькими морфами, например, одеть – надеть).

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

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

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

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

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

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

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

Программные средства реализованы на языке Java с использованием СУБД HSQLDB и внешнего модуля морфологического анализа «Диалинг. Русская морфология». Доступ к основным функциям словаря паронимов осуществляется с помощью прикладного и пользовательского интерфейсов.

Реализованные программные средства были проверены при загрузке и пополнении разных по структуре и объему текстовых файлов со словарными данными (объемом от 16 до 90 тыс. слов) и продемонстрировали устойчивую работу. В результате автоматического пополнения число пар буквенных паронимов, по сравнению с исходным файлом, увеличилось на 30%.

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

Литература 1. Большакова Е. И., Большаков И. А. Автоматическое обнаружение и автоматизированное исправление русских малапропизмов. // НТИ. Сер. 2, №5, 2007, с.

27-40.

2. Гусев В. Д., Саломатина Н. В. Электронный словарь паронимов: версия 1. // НТИ, Сер.

2, № 6, 2000, с. 34-41.

Кафедра АЯ ИСПОЛЬЗОВАНИЕ ПОИСКОВЫХ МАШИН И РЕСУРСОВ ИНТЕРНЕТ ДЛЯ ОТБОРА ТЕРМИНОВ ПРЕДМЕТНОЙ ОБЛАСТИ Бондаренко Игорь Владимирович студент кафедры алгоритмических языков e–mail: Ivers_87@mail.ru Научный руководитель – к.ф.-м.н.,с.н.с. НИВЦ МГУ Лукашевич Наталья Валентиновна Задача автоматического извлечения терминов из текстов предметной области является актуальной, поскольку термины являются неотъемлемой частью языка предметной области. Отобранные термины могут использоваться для формирования тезаурусов, разработки информационно-поисковых систем и систем автоматической обработки текстов в определенной предметной области.

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

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

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

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

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

Для оценки качества сортировки получаемых списков словосочетаний использовалась мера, служащая для оценки качества результатов информационного поиска, так называемая средняя точность (Mean Average Precision - MAP) [3]. Тестирование было проведено на выборке 3000 и 5000 словосочетаний. Было достигнуто существенное улучшение точности MAP по сравнению с точностью исходного списка (+27.2 %) и точностью наилучшей из отдельно взятых характеристик (+5.6%). Все методы сохранили более высокую среднюю точность MAP по сравнению с отдельными характеристиками при увеличении тестовой выборки.


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

Литература [1] Добров Б.В., Лукашевич Н.В., Синицын М.Н., Шапкин В.Н. Разработка лингвистической онтологии по естественным наукам для решения задач информационного поиска. // Труды 7-ой Всероссийской научной конференции «Электронные библиотеки:

перспективные методы и технологии, электронные коллекции» - RCDL‘2005.

[2] Weka 3: Data Mining Software in Java. http://www.cs.waikato.ac.nz/~ml/weka/ [3] Агеев М.С., Кураленок И.Е. Официальные метрики РОМИП‘2004. // Российский семинар по Оценке Методов Информационного Поиска (РОМИП 2004) — Пущино, 2004.

Кафедра АЯ ПРОГРАММНАЯ ПОДДЕРЖКА ЯЗЫКА ЛЕКСИКО-СИНТАКСИЧЕСКИХ ШАБЛОНОВ LSPL Работа удостоена диплома I-ей степени Носков Алексей Анатольевич студент кафедры алгоритмических языков e–mail: alexey.noskov@gmail.com Научный руководитель – к.ф.-м.н., доцент Большакова Елена Игоревна Дипломная работа посвящена проблемам автоматического выявления различных конструкций в текстах на естественном языке.

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

Язык LSPL, используемый в качестве гибкого средства описания конструкций естественного языка для их автоматического выделения в тексте с учетом особенностей русского языка, позволяет записывать конструкции в виде так называемых лексико синтаксических шаблонов. Шаблон языка LSPL в общем случае состоит из нескольких альтернатив, описывающих различные варианты выделяемой конструкции и состоящих из последовательности элементов, представляющих слова с их морфологическими характеристиками и условиями грамматического согласования. Язык включает средства записи повторяющихся элементов описываемой конструкции и позволяет задавать фрагменты конструкции с помошью уже определенных шаблонов. Например, шаблон NG = {A} N1 A=N1 [NG2c=gen] описывает именную группу, состоящую из последовательности прилагательных ({A}), существительного (N1), согласованного с этими прилагательными (A=N1), и опциональной именной группы в родительном падеже ([NG2c=gen]). Такому шаблону соответствует фразы вида «белый кот», «долгая зимняя ночь» и «тоненькая струйка дыма далекого пожара».

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

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

Центральный компонент выделения конструкций по шаблонам;

1.

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

приложениями на языке Java;

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

выделение в тексте конструкций по LSPL-шаблонам;

Графический пользовательский интерфейс, позволяющий загружать текст из различных 4.

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

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

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

Литература 1. Большакова Е.И., Баева Н.В., Бордаченкова Е.А., Васильева Н.Э., Морозов С.С.

Лексико-синтаксические шаблоны в задачах автоматической обработки текстов // Компьютерная лингвистика и интеллектуальные технологии: Труды Межд. конф.

Диалог '2007 – М.: Изд. центр РГГУ, 2007, стр. 70-75.

Кафедра АЯ РАЗРАБОТКА И РЕАЛИЗАЦИЯ МОДЕЛИ СПЕЦИАЛИЗИРОВАННОГО РЕЖИМА ИСПОЛЬЗОВАНИЯ МОБИЛЬНОГО ТЕЛЕФОНА Санин Алексей Евгеньевич студент кафедры алгоритмических языков e–mail: saninalexei@gmail.com Научный руководитель – доцент Абрамов Владимир Геннадьевич В данной дипломной работе рассмотрен вопрос о применимости многопользовательского режима к такому виду устройств, как мобильные телефоны.

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

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

На основе разработанной модели реализована пробная версия программной системы, обеспечивающей раздельный доступ к выбранному набору ресурсов устройства – текстовые сообщения и звонки. В качестве ОС устройства для реализации и тестирования выбирается ОС Symbian и ее эмулятор для ОС Windows XP соответственно.

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

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

Тезисы лучших дипломных работ ВМК МГУ 2009 года АЛГОРИТМЫ ОПТИМИЗАЦИИ ПРОГРАММ, ОБЕСПЕЧИВАЮЩИЕ СНИЖЕНИЕ ЭНЕРГОПОТРЕБЛЕНИЯ ВСТРАИВАЕМЫХ СИСТЕМ Батузов Кирилл Андреевич студент кафедры системного программирования e –mail: batuzovk@ispras.ru Научный руководитель – к.ф.-м.н., доцент Гайсарян Сергей Суренович Дипломная работа посвящена алгоритмам оптимизации программ, обеспечивающим снижение энергопотребления встраиваемых систем. Встраиваемые системы, работающие от батареи или аккумулятора получили в современном мире очень широкое распространение.

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

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

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

В результате запуска статического алгоритма с допустимым замедлением порграммы 20% было получено снижение энергопотрбления от 6% до 61% при замедлении от 3.3% до 18.2% соответственно. Смешанный алогритм был запущен с допустимым замедлением программы 10%. В результате запуска было получено снижение энергопотрбления от 11.6% до 74% при замеделнии от 2.5% до 9.2% соответственно.

Литература 1. Chung-Hsing Hsu. Compiler-Directed Dynamic Voltage and Frequency Scaling for CPU Power and Energy Reduction.A dissertation submitted to the Graduate School—New Brunswick Rutgers, The State University of New Jersey in partial fulfillment of the requirements for the degree of Doctor of Philosophy Graduate Program in Computer Science.

2. Nevine AbouGazaleh, Daniel Mosse, Bruce Childers and Rami Melhem. Collaborative Operating System and Compiler Power Management for Real-Time Applications.ACM Transactions on Embedded Computing Systems, Volume 5, Issue 1, February 2006. pp. 82 115.

3. Ana Azevedo, Ilya Issenin, Radu Cornea Rajesh Gupta, Nikil Dutt, Alex Veidenbaum, Alex Nicolau. Profile-based Dynamic Voltage Scheduling using Program Checkpoints.In Proceedings of Design, Automation and Test in Europe Conference, 2002. pp. 168-176.

4. Dmitry Zhurikhin, Andrey Belevantsev, Arutyun Avetisyan, Kirill Batuzov, Semun Lee.

Evaluating power-aware optimizations within GCC compiler.In First Internation Workshop on GCC Research Oportunities (GROW09), 2009.

Кафедра СП РАЗРАБОТКА СТАТИЧЕСКОГО МЕЖПРОЦЕДУРНОГО АЛГОРИТМА УПРАВЛЕНИЯ НАПРЯЖЕНИЕМ НА ПРОЦЕССОРЕ Работа удостоена диплома III-ей степени Жуйков Роман Александрович студент кафедры системного программирования e–mail: zhroman@gmail.com Научный руководитель – профессор Гайсарян Сергей Суренович Данная работа посвящена решению актуальной проблемы управления напряжением на процессоре с целью снижения его энергопотребления. В ней описывается новый алгоритм управления напряжением на процессоре, относящийся к группе статических методов динамического изменения напряжения (ДИН). Основной идеей статического алгоритма ДИН является поиск компилятором участков кода программы, на которых не требуется высокая производительность процессора. Для нахождения таких участков кода используется статический анализ кода, а также анализ данных профилирования. В результате работы алгоритма вставляются инструкции для снижения частоты и напряжения на выбранных участках кода. В рассматриваемых алгоритмах выбираются только участки кода с одним входом, называемые регионами. Разработанный в данной работе алгоритм основан на существующем внутрипроцедурном алгоритме, но в отличие от последнего использует более крупные регионы для понижения частоты. Например, допускаются регионы, содержащие несколько процедур. Помимо этого в алгоритме используется новая, более эффективная, стратегия выбора регионов для снижения частоты.

Разработанный алгоритм был реализован для набора компиляторов GNU [4] и протестирован на тестовой плате с процессором ARM. На наборе тестов aburto [5] алгоритму при установленном ограничении в 30% на замедление программы в среднем удается сэкономить около 15% энергопотребления процессора, а на отдельных программах с большим количеством операций с памятью – до 50%.

Литература 1. Hsu C. Compiler-Directed Dynamic Voltage and Frequency Scaling for CPU Power and Energy Reduction. A dissertation submitted to the Graduate School — New Brunswick Rutgers, The State University of New Jersey in partial fulfillment of the requirements for the degree of Doctor of Philosophy Graduate Program in Computer Science. 120p.

2. Aho A.V., Lam M.S., Sethi R., Ullman J.D. Compilers: Principles, Techniques, and Tools.

Second edition. New York: Addison Wesley, 2006. 1175p.

3. Cormen T., Leiserson C., Rivest R. Introduction to Algorithms. MIT, 2001. pp 337-339.

4. GNU Compiler Collection (GCC) Internals. [HTML] http://gcc.gnu.org/onlinedocs/gccint/ 5. Alfred Aburto's system benchamrks. [HTML] ftp://gd.tuwien.ac.at/perf/benchmark/aburto Тезисы лучших дипломных работ ВМК МГУ 2009 года ИССЛЕДОВАНИЕ И РЕАЛИЗАЦИЯ РАСПРЕДЕЛЕННОГО ПОИСКА НА ОСНОВЕ ОНТОЛОГИЙ Работа удостоена диплома II-ей степени Кузнецов Константин Александрович студент кафедры системного программирования e–mail: K.Kuznetcov@gmail.com Научный руководитель – профессор Серебряков Владимир Алексеевич Интенсивное развитие информационных технологий и Интернет привело к накоплению огромных объемов данных в различных источниках, разнородных, автономно разработанных, представляющих информацию различными способами, содержащих взаимосвязанные и взаимно противоречивые сведения. Интеграция и совместное использование информации из множества таких источников данных является сложной задачей, остающейся неизменно актуальной на протяжении последних десятилетий.

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

Ключевой особенностью разрабатываемой системы является использование так называемых «семантических технологий» – для описания схем данных используется язык веб-онтологий OWL, запросы формулируются на языке SPARQL. Предлагаемая система обладает гибкой, настраиваемой архитектурой. В работе предложена объектно-ориентированная модель представления SPARQL запросов и правил отображения онтологий. Основное внимание в работе уделено алгоритмам построения логического и физического плана исполнения запроса. Описываются алгоритмы переформулировки запросов относительно онтологий и правил отображения онтологий, алгоритм распределенного исполнения запроса.

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

Литература 1. Бездушный А.А., Бездушный А.Н., Серебряков В.А., Филиппов В.И. Интеграция метаданных Единого Научного Информационного Пространства РАН. – Москва, Вычислительный Центр им. А.А. Дородницына РАН, 2006, 238 с.

2. Бездушный А.А., Бездушный А.Н., Нестеренко А.К., Серебряков В.А., Сысоев Т.М., Теймуразов К.Б., Филиппов В.И. Информационная Web-система «Научный институт»

на платформе ЕНИП. – Москва, Вычислительный Центр им. А.А. Дородницына РАН, 2007, 248 с.

3. Бездушный А.А. Математическая модель интеграции данных на основе дескриптивной логики. – Москва, Московский физико-технический институт, 2008, 100 с.

4. Levy, A.Y., Rajaraman, A., Ordille, J.J., Querying Heterogeneous Information Sources Using Source Descriptions. – In Proceedings of the International Conference on Very Large Databases (VLDB). San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1996. P. 251- 5. Abiteboul S., Hull R., Vianu V. Foundations of Databases. – Reading, MA, Addison-Wesley, 1995.

6. Pottinger R., Halevy А. MiniCon: A scalable algorithm for answering queries using views. – VLDB Journal: Very Large Data Bases, 2001, vol. 10, no. 2-3. New York, Springer-Verlag, 2001. P. 182-198.

Кафедра СП ИССЛЕДОВАНИЕ МЕТОДОВ ПОСТРОЕНИЯ ТРАНЗАКЦИОННОЙ ПАМЯТИ С АППАРАТНОЙ ПОДДЕРЖКОЙ И БЕЗ НЕЁ Музыченко Александр Викторович студент кафедры системного программирования e–mail: alexmuz@gmail.com Научный руководитель – профессор Кузнецов Сергей Дмитриевич Дипломная работа посвящена исследованию нового механизма параллельного доступа к общей памяти – транзакционной памяти.

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

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

Транзакционная память – удобное средство управления доступом к разделяемым данным, предоставляющее ряд преимуществ: более эффективное использование ядер процессора, поскольку транзакции могут выполняться параллельно в разных потоках управления;

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

более простая и понятная программная модель.

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

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

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

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

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

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



Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |
 





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

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