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

Pages:     | 1 || 3 |

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

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

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

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

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

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

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



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

–  –  –

1. Осокин А. А., Ветров Д. П., Кропотов Д. А. Построение трехмерной модели мозга мыши по набору двумерных изображений из Алленовского Атласа. Труды 14-ой Всероссийской конференции Математические методы распознавания образов. Москва: Макс Пресс, 2009. С. 582 585 .

2. Allen Institute for Brain Science. Allen Brain Atlas. Seattle (WA), http://www.brain-map.org, 2008 .

3. Osokin A., Belotserkovky A., Vetrov D., Kropotov D., Zhuravlev Y. Mouse Brain Slice Segmentation for Analysis of Physiological Activity. Proc. of 10th International Conference on Pattern Recognition and Image Processing

2009. Publ. center of BSU. Minsk: 2009. Pp. 348 353 .

4. Rahman Z., Jobson D. J., and Woodell G. A. Multi-scale retinex for color image enhancement. Proceedings of International Conference on Image Processing. Vol. 3. 1996. Pp. 1003 1006 .

5. Ju T. et al. 3D volume reconstruction of a mouse brain from histological sections using warp ltering. Journal of Neuroscience Methods. 2006. Vol .

156, Pp. 84 100 .

6. Kybic J., Unser M. Fast parametric elastic image registration. IEEE Transactions on Image Processing. 2003. Vol. 12, no. 11. Pp. 1427 1442 .

Кафедра МК О сложности распознавания некоторых свойств функций многозначных логик, заданных полиномами Работа удостоена диплома III степени Бухман Антон Владимирович студент кафедры математической кибернетики email: antfb@rambler.ru научный руководитель доцент Селезнева Светлана Николаевна Пусть Ek = {0, 1,..., k 1}. Функцией k-значной логики от n переменных n будем называть любое отображение f : Ek Ek .





Определение. Мономом над переменными x1,..., xn называется любое jl выражение вида xji... xil, где l 1, 1 i1,..., il n, 1 j1,..., jl k1, все i переменные различны; либо просто 1. Полиномом называется сумма по модулю k конечного числа различных мономов с ненулевыми коэффициентами из Ek или 0 (можно понимать как сумму нулевого числа мономов). Длиной полинома называется число его слагаемых. Длину нулевого полинома будем считать равной 0 .

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

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

В качестве исполнителя алгоритмов рассматривается машина с произвольным доступом в память (RAM). В работе рассматривается задание функций k-значной логики полиномами. Если длина полинома функции равна l, и эта функция зависит от n переменных, то на вход алгоритма подаётся запись длины nl. При таком способе задания функций вопрос о существовании полиномиального алгоритма распознавания сохранения функциями предикатов не является тривиальным. В работе [1] были построены полиномиальные алгоритмы для распознавания сохранения функциями, заданными полиномами, всех предикатов из пяти семейств, которые описывают предполные классы .

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

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

В работе доказаны следующие теоремы .

Теорема. Пусть k – простое число. Можно построить полиномиальТезисы лучших дипломных работ факультета ВМК МГУ 2010 года ный алгоритм, который по полиному функции из Pk может определить, сохраняет ли эта функция двуместный центральный предикат, задаваемый матрицей „ « 0... k 1 0... 1... k 1 0... k 1 1... k 1 0... 0 Теорема. Пусть функция трёхзначной логики задаётся полиномом, в который все переменные входят в степени не выше 1, тогда существует полиномиальный алгоритм распознавания сохранения этой функцией двуместного центрального предиката с центром {1} .

Обозначим E(g(x)) множество значений функции g(x) .

Теорема. Пусть k – простое число. Для любого l Ek \ {0}, для любого i 1, k 1 можно построить полиномиальный алгоритм, который будет распознавать, сохраняет ли функция, заданная полиномом, одноместный центральный предикат с центром E(lxi ) .

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

Теорема. Пусть k – простое число. Для любого l Ek \ {0}, для любого i 1, k 1 можно построить полиномиальный алгоритм, который будет распознавать, сохраняет ли функция, заданная полиномом, одноместный центральный предикат с центром E(lxi ) \ {0} .

Литература

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

2. С.В. Яблонский, Г.П. Гаврилов, А.А. Набебин. Предполные классы в многозначных логиках. М.: Изд-во МЭИ, 1997 .

3. С.В. Яблонский. Введение в дискретную математику. М.: Наука, 1986 .

Порождение двоичных последовательностей с помощью регистров сдвига малой степени Лысиков Владимир Владимирович студент кафедры математической кибернетики email: lysikov-vv@yandex.ru научный руководитель д.ф.-м.н., проф. Алексеев Валерий Борисович В дипломной работе рассматривается сложность порождения двоичных последовательностей де Брёйна с помощью регистров сдвига с обратной связью при ограничении на степень функции обратной связи. Регистры сдвига Кафедра МК с обратной связью являются одним из широко распространенных элементов различных криптографических схем, в частности, генераторов псевдослучайных чисел и потоковых шифров.(см. напр. [1] и [2])

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

–  –  –

В [5] получено точное значение средней линейной сложности случайной последовательности заданной длины. В [6] выдвинута гипотеза о том, что средняя квадратичная сложность случайной последовательности длины l равна 2l. Получена нижняя оценка средней сложности, которая согласуется с этой гипотезой при k = 2 .

Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Теорема 4. При k 2 средняя рекуррентная сложность степени k случайной последовательности длины l больше k k!l(1 o(1)) при l .

Литература

1. S. W. Golomb, Shift Register Sequences, Aegean Park Press, 1981 .

2. Логачев О. А., Сальников А. А., Ященко В. В., Булевы функции в теории кодирования и криптологии, МЦНМО, 2004 .

3. A. H. Chan, R. A. Games, E. L. Key, On the Complexity of de Bruijn Sequences, J. Comb. Theory (A), 33-3, pp.233-246, Elsevier, 1982 .

4. A. H. Chan, R. A. Games, On the Quadratic Spans of Periodic Sequences, Advances in Cryptology CRYPTO’89, pp.82-89, Springer, 1990

5. R. A. Rueppel, Linear complexity and random sequences, Advances in Cryptology EUROCRYPT’85, pp. 167–188, Springer, 1986 .

6. A. M. Youssef, G. Gong, On the Quadratic Span of Binary Sequences, Technical report, 2000 .

О некоторых свойствах функций многозначных логик, связанных с линейными преобразованиями Мазуров Анатолий Алексеевич студент кафедры математической кибернетики email: anat-mazurov@mail.ru научный руководитель доцент, к.ф.-м.н. Селезнева Светлана Николаевна В данной работе рассматриваются классы функций 3-значной логики, являющихся собственными функциями преобразования Мёбиуса то есть таких, для которых вектор коэффициентов полинома можно вычислить как вектор значений функции f .

C · f, где C {1, 2}, а f Для задания функции k-значной логики часто используются её представления в виде вектора значений или в виде вектора коэффициентов полинома .

Преобразование из первого представления во второе называется преобразованием Мёбиуса и обозначается µ(f ). Это преобразование является линейным оператором на множестве векторов длины kn из Pk .

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

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

Обозначим Qk (n) = {f E3 (n) | µk (f ) i · f } это класс функций, i являющихся собственными векторами преобразования µk с собственным значением i .

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

1. 8-я степень µ тождественное преобразование:

µ8 (f ) f

–  –  –

Реализация булевых функций схемами с подведением переменных, вложенными в единичный куб Садовников Олег Александрович студент кафедры математической кибернетики email: oleg.a.sadovnikov@gmail.com научный руководитель д.ф.-м.н. Ложкин Сергей Андреевич В настоящее время в теории синтеза управляющих систем большое внимание уделяется задачам структурной реализации дискретных функций и, в частности, задачам их геометрической реализации. В общем случае под геометрической реализацией схемы понимается совместное размещение ее управляющих (функциональных) и соединительных (коммутационных) элементов в некоторой геометрической структуре, позволяющей моделировать фактическое взаимное расположение элементов в реальной схеме .

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

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

Упомянутая выше модификация заключается в следующем. Пусть некоторая (обычная) BDD управляется входными булевскими переменными (БП) Кафедра МК x1, x2,..., xn. Для каждой БП xi, i = 1, 2,..., n, строится так называемый граф подводки Ti, то есть граф, связывающий все вершины xi исходной BDD и не имеющий с ней других пересечений (по вершинам и рёбрам). Графом подводки для BDD называется объединение графов подводки для всех ее входных БП. Объединение BDD и ее графа подводки называется BDD с подведением переменных, соответствующей BDD. Таким образом, последующая геометрическая реализация схем из модифицированного класса автоматически будет учитывать размещение как управляющих, так и всех необходимых коммутационных элементов .

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

Под сложностью D() BDD с подведением переменных понимается минимальная размерность единичного куба, допускающего гомеоморфное вложение. Обычным образом для рассматриваемого класса схем вводится функционал D(f ) сложности реализации функции алгебры логики (ФАЛ) f : D(f ) = min D(), а также функция Шеннона D(n) = max D(f ) .

реал. f f P2 (n) Также рассматривается класс обобщенных BDD с подведением переменных, позволяющий реализовывать системы ФАЛ, и соответствующий функционал D(F ) сложности реализации системы ФАЛ F (вводится аналогичным образом) .

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

• сложности дешифратора порядка n (то есть системы ФАЛ Qn, состоящей из всех элементарных конъюнкций от n БП ранга n):

–  –  –

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

Литература

1. С. А. Кравцов. О реализации функций алгебры логики в одном из классов схем из функциональных и коммутационных элементов. Проблемы кибернетики, 1967, Вып. 19. М.: Наука, 1967. С.285-292 .

2. С. А. Ложкин. Лекции по основам кибернетики (учебное пособие для студентов). М.: Издательский отдел ф-та ВМК МГУ, 2004 .

3. О. Б. Седелев. О реализации функций алгебры логики BDD, вложенными в единичный куб. Вестник Московского университета, сер. 15. Вычислительная математика и кибернетика, 2006, №4, с. 29-35 .

4. C. Y. Lee. Representation of Switching Curcits by Binary-Decision Programs .

Bell Systems Technical Journal, 1959, July, Vol. 38, Pp 985-999 .

Сложность реализации булевых функций в некоторых моделях клеточных схем Работа удостоена диплома II степени Улесова Александра Юрьевна студентка кафедры математической кибернетики email: ulesova@gmail.com научный руководитель д.ф.-м.н. Ложкин Сергей Андреевич В дипломной работе исследуются две математические модели клеточных схем (КС) КС вида схем из функциональных элементов(СФЭ) и КС типа via-congurable (VC). При этом рассматриваются сопутствующие схемы, отличающиеся от классических тем, что входные переменные могут подаваться только на верхнюю границу схемы, но каждая переменная может подаваться многократно. В работе оцениваются функции Шеннона для площади схем в таких моделях, реализующих функции алгебры логики (ФАЛ) .

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

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

Вводится понятие функции Шеннона для площади КС ограниченной высоты. Для любой ФАЛ f и любого h 2 (см. [3]) определена функция Ah (f ), B равная наименьшей из площадей A(), где минимум берется по всем КС Кафедра МК над базисом B высоты h, реализующим f. Функция Шеннона Ah (n) опредеB ляется как максимум из величин Ah (f ) по всем ФАЛ f от n переменных. Для B введенной функции Шеннона доказываются следующие теоремы .

Теорема 1. При h 4 в произвольном базисе B справедлива следующая асимптотическая оценка функции Шеннона Ah (n) :B h2n Ah (n) .

B log2 n

–  –  –

Замечание. В стандартном базисе {&,, ¬} указанная асимптотика функции Шеннона имеет место при h 3, а верхняя оценка из теоремы 2 при h 4. Асимптотика функции Шеннона в классе КС, где входные 2n переменные могут подаваться по всей границе схемы, имеет вид h log n и справедлива при h 7 .

Во второй части работы рассматриваются двухслойные КС типа VC (см. [4]). В первом слое располагаются две параллельные зоны n- и pпроводимости, состоящие из транзисторов соответствующего типа. Размеры транзисторов и расстояния между ними равны 1. В первом же слое параллельно зонам проводимости располагаются каналы, в которых можно проложить проводники, соединяющие транзисторы между собой. Во втором слое каналы располагаются перпендикулярно зонам проводимости. Для связи слоев схемы в некоторых местах пересечения проводников ”пробиваются дырки”, по которым возможна передача сигнала .

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

Длиной КС типа VC называется число транзисторов в одном ее ряду, а шириной число параллельных каналов в ней, без учета шин ”нуля” и ”единицы”. Высота схем фиксирована и равна некоторой константе h. Сложностью схемы называется ее площадь Avia (). Для произвольной ФАЛ f функция Ah (f ) определяется как наименьшая из площадей Avia (), где миниvia мум берется по всем схемам высоты h, реализующим f. Функция Шеннона Ah (n) определяется как максимум из Ah (f ) по всем ФАЛ f от n переvia via менных. В дипломной работе устанавливается следующая оценка для этой функции Шеннона .

Теорема 3.

При h 5 для функции Шеннона Ah (n) справедлива следуvia ющая асимптотическая оценка:

h2n Ah (n) .

via log2 n Для построения КС типа VC была написана программа в среде Microsoft Visual Studio 2008 на языках C++ и C#. Программа, получив на вход чисТезисы лучших дипломных работ факультета ВМК МГУ 2010 года ло n [5, 10] и ФАЛ f, зависящую от n переменных, рисует КС типа VC, реализующую заданную функцию f .

Литература

1. Кравцов С. С. О реализации функций алгебры логики в одном из классов схем из функциональных и коммутационных элементов // Проблемы кибернетики, вып. 19. М.: Наука, 1967. С. 285-292 .

2. Альбрехт А. О схемах из клеточных элементов // Проблемы кибернетики, вып. 33. М.: Наука, 1975. С. 209-214 .

3. Тиунчик А. А. О реализации функций алгебры логики клеточными схемами ограниченной ширины // Методы дискретного анализа в решении экстремальных задач, вып. 50. Новосибирск: Институт математики СО АН СССР, 1990. С. 73-83 .

4. Yajun Ran and Malgorzata Marek-Sadowska Designing Via-Congurable Logic Blocks for Regular Fabric // IEEE transactions on very large scale integration (VLSI) systems, vol. 14(1), 2006. С. 1-14 .

Тестирование бесповторных функций в различных базисах Работа удостоена диплома I степени Чистиков Дмитрий Викторович студент кафедры математической кибернетики email: dd1email@gmail.com научный руководитель д. ф.-м. н., проф. Вороненко Андрей Анатольевич Пусть B некоторый функциональный базис в алгебре логики. Функция f называется бесповторной в базисе B, если она представима формулой над B без повторений символов переменных. В задачах тестирования бесповторных функций базисы обыкновенно полагают наследственными, то есть содержащими вместе с каждой функцией все ее подфункции, получаемые подстановками констант на места переменных .

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

Минимальная длина теста (количество наборов в нем) функции f в базисе B обозначается символом TB (f ) .

Первой в дипломной работе рассматривается задача тестирования относительно бесповторной альтернативы в базисе {&, } [1].

Доказывается следующая индивидуальная нижняя оценка длины теста для функций, выразимых Кафедра МК бесповторными монотонными КНФ и ДНФ (результат сформулирован для случая КНФ):

Теорема 1. Для минимальной длины теста функции

–  –  –

Данная оценка, в частности, устанавливает минимальность построенных А. А. Вороненко тестов длины длины 3 n 1 для функций специальной подпоследовательности, а также позволяет усилить для случая КНФ и ДНФ универсальную нижнюю оценку 2 n, полученную С. Е.

Бубновым:

Теорема 2. Для функции f (x1, .

.., xn ), выразимой бесповторной монотонной КНФ или ДНФ, минимальная длина теста удовлетворяет неравенству pp T{&,} (f ) 2 2 n 1 .

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

Теорема 3. Если конечный наследственный базис B содержит двухместную дизъюнкцию, а n-местная дизъюнкция как бесповторная функция не допускает теста линейной длины, то в B не выполняется гипотеза подфункции: существуют бесповторные функции f и f такие, что f подфункция f, но TB (f ) TB (f ) .

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

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

T{&,,¬} (n) n2 n + 1. В дипломной работе доказан следующий факт:

Теорема 4. Для произвольного наследственного базиса B, допускающего бесповторное выражение конъюнкции, дизъюнкции и отрицания и содержащего хотя бы одну не являющуюся бесповторной в элементарном базисе функцию, TB (n) = 2(n) .

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

Литература

1. Бубнов С. Е., Вороненко А. А., Чистиков Д. В. Некоторые оценки длин тестов для бесповторных функций в базисе {&, } // Прикладная математика и информатика. 2009. 33. С. 90–100 .

2. Вороненко А. А., Чистиков Д. В. Расшифровка бесповторных функций оракулом счетчиком четности // Прикладная математика и информатика. 2010. 34 .

Построение модели влияния трафика вредоносного программного обеспечения на трафик в глобальной сети Абрамов Николай Александрович студент кафедры автоматизации систем вычислительных комплексов email: cunick@lvk.cs.msu.su научный руководитель Качалин Алексей Игоревич Сетевой трафик это данные, передаваемые по сети. Он описывается объемом передаваемых данных в единицу времени (в каждой точке сети), а также характеристиками передачи задержкой и процентом потерь при передаче из одной точки сети в другую. Указанные характеристики определяют уровень качества обслуживания в сети [2]. Примером, позволяющим оценить качество обслуживания с точки зрения пользователя, является средняя скорость загрузки Интернет-страницы .

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

Кафедра АСВК В Лаборатории Вычислительных Комплексов ведется проект по разработке системы Гибридного Моделирования Глобальной Сети (ГМГС). Данная система создается с целью исследования трафика глобальной сети и, в частности, трафика ВПО. Данная система основывается на потоковых моделях трафика и сетевых примитивах масштаба домена и/или автономной системы. Система ГМГС разбита на два сегмента, в совокупности описывающих глобальную сеть: наблюдаемый (применяется топология уровня доменов) и внешний (вся глобальная сеть, без наблюдаемого сегмента; применяется топология уровня магистральных каналов) .

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

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

В частности выполнено следующее:

• проведены обзоры аналитических моделей трафика и ВПО, которые позволили выбрать наиболее подходящие модели для различных приложений и эпидемий ВПО[1];

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

• предложенная модель реализована в составе системы Гибридного Моделирования Глобальной Сети;

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

• предложены дальнейшие направления работы над разработанной моделью .

Литература

1. Н. А. Абрамов, А. И. Качалин Выбор моделей распространения ВПО при разработке модели глобальной сети. Методы и средства обработки информации. Труды третьей Всероссийской научной конференции, 2003 .

2. D.P. Heyman, D. Lucantoni Modeling multiple ip trac streams with rate limits. IEEE/ACM Trans. Network, 2003 .

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

3. M. Liljenstam, D. M. Nicol, V. H. Berk, R. S. Gray. Simulating realistic network worm trac for worm warning system design and testing. In proceedings of the 2003 ACM workshop on Rapid Malcode, ACM Press, 2003 .

4. S. Wei Distributed worm simulation with a realistic internet model .

Washington, DC, USA: IEEE Computer Society, 2005 .

Исследование сходимости протокола BGP в глобальной сети Работа удостоена диплома III степени Азимов Александр Евгеньевич студент кафедры автоматизации систем вычислительных комплексов email: mitradir@lvk.cs.msu.su научный руководитель м.н.с. Качалин А.И .

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

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

1. Время сходимости протокола BGP вследствие объявления нового маршрута BGP маршрутизатором пропорционально диаметру графа сети относительно рассматриваемого маршрутизатора;

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

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

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

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

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

Литература

1. RFC 4271, A Border Gateway Protocol 4 (BGP-4), [HTML] (http://www.faqs.org/rfcs/rfc4271.html)

–  –  –

3. Parallel Real-time Immersive network Modeling Environment (PRIME), [HTML] (https://www.primessf.net/bin/view/Public/PRIMEProject)

4. СBGP, [HTML] (http://cbgp.info.ucl.ac.be/) Разработка инструментальных средств для анализа характеристик коммуникационной среды многопроцессорных вычислительных систем Андреев Дмитрий Юрьевич студент кафедры автоматизации систем вычислительных комплексов email: andreev@angel.cs.msu.su научный руководитель к.ф.-м.н. Сальников Алексей Николаевич На данный момент существует множество многопроцессорных систем с числом вычислительных узлов больше 1000. К таким системам можно отнести: МВС 100К (МСЦ РАН), СКИФ МГУ Чебышев (НИВЦ МГУ), IBM Blue Gene/P (ВМК МГУ). Наиболее популярной технологией для обеспечения обмена данными между процессами в программе на таких многопроцессорных системах на данный момент является Message Passing Interface (MPI, интерфейс передачи сообщений). Коммуникационная среда многопроцессорной системы неоднородна, обмен данными между разными парами процессоров может происходить с разной скоростью передачи. На производительность Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года параллельной программы могут влиять физические характеристики коммуникационной среды. Из-за особенностей архитектуры время передачи сообщения нелинейно зависит от длины сообщения. Сложно делать оценки на время доставки сообщения, основываясь на информации о времени передачи сообщения другой длины .

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

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

В состав разработанного инструментария входят:

• Система синтетических тестов коммуникационной среды .

• Средство визуализации результатов тестирования .

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

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

Результаты тестов хранятся в бинарном формате на основе NetCDF .

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

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

С помощью созданного инструментария были получены данные для вычислительных систем МВС-100К и СКИФ-МГУ. Среднее полученное количество кластеров для одной длины сообщения:

• 128 процессоров 20 .

Кафедра АСВК • 256 процессоров 27 .

• 512 процессоров 34 .

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

Литература

1. Н. М. Булочникова, В. Ю. Горицкая, А.Н. Сальников. Методы тестирования производительности сети с точки зрения организации вычислений // Научный сервис в сети Интернет 2004: Труды Всероссийской научной конференции, Изд-во МГУ имени М. В. Ломоносова, 2004, С. 219 .

2. Д. Ю. Андреев, А. Н. Сальников. Средство автоматической кластеризации результатов тестирования коммуникаций многопроцессорных систем // Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность: Труды Всероссийской научной конференции, Изд-во МГУ имени М.В. Ломоносова, 2009, С. 293-297 Исследование эффективности применения параллельных эвристических алгоритмов к решению задачи мэппинга для массивно-параллельной системы Blue Gene/P Анциферова Дарья Александровна студентка кафедры автоматизации систем вычислительных комплексов email: antsiferova.d@gmail.com научный руководитель к.ф.-м.н., доцент Попова Н.Н., д.ф.-м.н., профессор, член-корр. РАН Королев Л.Н .

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

В дипломной работе исследовано решение задачи распределения процессов параллельной программы по вычислительным узлам массивно-параллельной системы Blue Gene/P (задача мэппинга), при котором минимизируется время работы программы, затраченное на коммуникации между процессами [1] .

Решением поставленной задачи является файл с координатами отображения MPI-процессов параллельной программы на вычислительные узлы системы Blue Gene/P, который может быть использован в качестве входного параметра при запуске программы на системе [2] .

Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Для решения поставленной задачи мэппинга в дипломной работе впервые использовались параллельные эвристические алгоритмы: Генетический алгоритм [3] и алгоритм Пчелиной колонии [4]. С учетом специфики трехмерного тора в системе Blue Gene/P, из существующих моделей параллельных алгоритмов выбрана Клеточная модель, как легко масштабируемая и подходящая к архитектуре данной системы [5]. В работе исследовано влияние параметров алгоритмов на их сходимость. Среди параметров Генетического алгоритма рассмотрены варианты операторов скрещивания, мутации и отбора; для алгоритма Пчелиной Колонии рассмотрены варианты осуществления локального поиска агентов. В работе проведено исследование влияния параметров миграции на сходимость параллельных алгоритмов. Предложен метод ускорения работы алгоритмов, основанный на выборе начальной популяции .

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

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

–  –  –

1. Bhanot G., Gara A., Heidelberger P., Lawless E., Sexton J. C., Walkup R. Optimizing task layout on the Blue Gene/L supercomputer. [PDF] (http://portal.acm.org/citation.cfm?id=1665980) .

2. IBM System Blue Gene Solution: Blue Gene/P Application Development .

Third Edition. [PDF] (http://www.redbooks.ibm.com/) .

–  –  –

4. Pham D.T., Ghanbarzadeh A, Koc E, Otri S, Rahim S, Zaidi M. The Bees Algorithm. Technical Note, Manufacturing Engineering Centre, Cardi University, UK, 2005 .

–  –  –

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

В дипломной работе рассматриваются наиболее распространенные в настоящий момент средства организации удаленного рабочего места (RDP, VNC [1], NX, X Window System и Sun Ray). В результате проведенных исследований показано, что ни одно из вышеупомянутых средств не обеспечивает прозрачной работы пользователя на удаленной машине. Работа приложений на сервере приложений считается прозрачной, если она неотличима от работы на локальном рабочем месте. Прежде всего, проблема возникает из-за нагрузки на канал передачи данных и, как следствие, больших задержек в обновлении элементов интерфейса (отзывчивости) .

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

Область, встретившаяся 1 раз, передается по сети в виде растрового изображения; для области, встретившейся 2 раза, формируются протокольные данные с пометкой клиенту закэшировать ее; для области, встретившейся 3 и более раз, формируются протокольные данные с пометкой клиенту взять ее из кэша .

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

Проведенные эксперименты показали, что использование разработанного расширения совместно на исходной последовательности обновленных областей сокращает нагрузку на канал передачи данных на 24-35% в зависимости от типа запущенных пользователем приложений и типа кодирования графической информации. Использование расширения на сеточном разбиении исходной последовательности сокращает нагрузку на канал передачи данных на 34-54%, на охватывающем разбиении на 51-83% .

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

1. Разработано расширение прокола RFB, повышающего отзывчивость тонких клиентов. Расширение реализовано на базе пакета TigerVNC;

2. Проведено сравнение различных стратегий кэширования графических данных, выявлено наиболее эффективное .

–  –  –

2. Richardson T. The RFB Protocol, [PDF] (http://www.realvnc.com/docs/rfbproto.pdf) Кафедра АСВК Исследование эффективности решения разностных задач на высокопроизводительных вычислительных системах Работа удостоена диплома II степени Глазкова Екатерина Алексеевна студентка кафедры автоматизации систем вычислительных комплексов email: katrin-elinor@yandex.ru научный руководитель к.ф.-м.н. Попова Нина Николаевна Дипломная работа посвящена исследованию эффективности выполнения параллельных программ на высокопроизводительных вычислительных системах (ВПВС). Актуальность этой тематики обуславливается низкой эффективностью использования ВПВС при решении прикладных задач .

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

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

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

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

Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Проведено исследование эффективности модельной задачи и тестового пакета NAS Parallel Benchmarks для вычислительной системы Blue Gene/P .

Выполнен сравнительный анализ эффективности технологий параллельного программирования: MPI и гибридного (MPI + OpenMP) подхода для модельной и тестовых задач. Исследовано влияние различных параметров, задаваемых при запуске задач на системе Blue Gene/P, на время выполнения параллельных программ .

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

1. Для параллельных приложений, решающих разностные задачи с подобластями одинакового размера, использование гибридного подхода оправдано в случае большого объема коммуникаций в программе. Для модельной задачи исследуемые параметры: способ распределения процессов по процессорам, виртуальная топология и режим выполнения программы (VN, DUAL, SMP), значительно влияют на время выполнения программы. Худшее и лучшее время выполнения различаются в 2 раза .

2. Для параллельных приложений, решающих разностные задачи, где размеры подобластей, на которые разбивается исходная область, существенно различаются, использование гибридного (MPI+OpenMP) подхода является целесообразным за счет уменьшения накладных расходов на балансировку нагрузки. Для таких задач выбор одного из стандартных способов назначения процессов на процессоры практически не влияет на время выполнения программы, а соотношение числа MPIпроцессов и OpenMP-нитей значительно влияет на время .

–  –  –

1. Makris I. Mixed Mode Programming on Clustered SMP Systems .

Dissertation. The University of Edinburgh, 2005 .

2. Hager G., Jost G., Rabenseifne R. Communication Characteristics and Hybrid MPI/OpenMP Parallel Programming on Clusters of Multi-core SMP Nodes. Cray User Group Proceedings. Atlanta: National Center for Computational Sciences, 2009 .

3. IBM System Blue Gene Solution: Blue Gene/P Application Development .

[PDF] (http://www.redbooks.ibm.com/redbooks/pdfs/sg247287.pdf) .

Кафедра АСВК Инcтрументальное средство автоматизации построения моделей нормального поведения приложений Горнак Татьяна Александровна студентка кафедры автоматизации систем вычислительных комплексов email: tehhi@lvk.cs.msu.su научный руководитель м. н. с., к.ф.-м.н. Гамаюнов Денис Юрьевич Дипломная работа посвящена актуальной задаче контроля поведения приложений на узлах .

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

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

Метод реализован в инструментальном средстве и протестирован на простом сервере FTP для ОС Linux, для которого существует готовый профиль SELinux. Получено разбиение на пять блоков, которое позволяет изолировать выполняемые сервером системные вызовы внутри блоков .

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

–  –  –

1. M. Jones Anatomy of Security-Enhanced Linux [HTML] (http://www.ibm.com/developerworks/linux/library/l-selinux/) .

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

2. Bauer An Introduction to Novell AppArmor [HTML]

(http://www.linuxjournal.com/article/9036) .

3. Беззубцев С.О. Гамаюнов Д.Ю. Горнак Т.А. Сапожников А.В. Сахаров Ф.В. Контроль безопасного поведения приложений с помощью поведенческих моделей // Методы и средства обработки информации, 439-444,

4. MiniFTPD - Summary [HTML] (http://gna.org/projects/miniftpd/) .

5. David Wheeler, Secure programmer: Minimizing privileges [HTML] (http:

//www.ibm.com/developerworks/linux/library/l-sppriv.html) .

Система визуализации комплексных атак и состояния защищаемой сети Елизаров Анатолий Валерьевич студент кафедры автоматизации систем вычислительных комплексов email: tolya@lvk.cs.msu.su научный руководитель м.н.с., к.ф.-м.н. Гамаюнов Денис Юрьевич Дипломная работа посвящена проблеме создания системы визуализации распределенных и многошаговых атак на компьютерные сети в режиме реального времени .

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

Комплексные атаки обладают следующими свойствами:

• распределенности: одна атака может иметь как несколько источников, так и различные цели;

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

• протяженности по времени: для атаки определено время первого и последнего на данный момент обнаруженного события .

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

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

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

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

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

Результаты работы докладывались на конференции 6th International Workshop on Visualization for Cyber Security, IEEE VisWeek’09, Atlantic City, New Jersey, USA, опубликована статья в сборнике конференции [5] .

–  –  –

1. Shneiderman B. The Eyes Have It: A Task by Data Type Taxonomy for Information Visualizations. In Proceedings of IEEE Symposium on Visual Languages, 1996. P. 336-343 .

2. Cleveland W.S. Graphical Perception: Theory, Experimentation, and Application to the Development of Graphical Methods. In Journal of the American Statistical Association, 1984. №387. P. 531-554 .

3. Kasemsri R.R. A Survey, Taxonomy, and Analysis of Network Security Visualization Techniques. Geordia State University, US, 2005 .

4. Keim D.A. Challenges in Visual Data Analysis. In International Conference on Information Visualization, 2006. №10. P. 9-16 .

5. Yelizarov A., Gamayunov D. Visualization of Complex Attacks and State of Attacked Network. In Proceedings of 6th International Workshop on Visualization for Cyber Security, IEEE VizWeek’09, Atlantic City, New Jersey, USA, October 11, 2009. P. 1-9 .

Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Физически аккуратное моделирование отражательной способности материалов поверхностей плоских объектов Лебедев Андрей Сергеевич студент кафедры автоматизации систем вычислительных комплексов email: alebedev@graphics.cs.msu.ru научный руководитель к.ф.-м.н. Игнатенко Алексей Викторович Данная работа посвящена получению физически аккуратных моделей материалов [1] реального мира, которые необходимы для предварительного расчета освещения при проектировании различных зданий, помещений, автомобилей и т.п. и визуальной оценки эстетичности внешнего вида объектов [2] .

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

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

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

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

Визуализация материала происходит со скоростью более 100 кадров в секунду на средней по производительности видеокарте NVIDIA GeForce 6600 (количество треугольников не более 15000). Проведенный анализ необходимого числа фотографий для реалистичного восстановления моделей освещения показывает, что достаточно 5–6 фотографий для алгоритма реконструкции .

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

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

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

1. Проведен обзор существующих моделей освещения. Были выявлены достоинства и недостатки существующих моделей освещения .

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

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

4. Проведен анализ необходимых входных данных для системы, верификация модели освещения и алгоритмов ее построения .

–  –  –

2. Волобой А.Г., Галактионов В.А. Машинная графика в задачах автоматизированного проектирования // Информационные технологии в проектировании и производстве. 2006. № 1. С. 64-73 .

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

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

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

При сравнении c фильтром из коллекции Deen и другими методами [1,2,3,4], предложенный алгоритм показал высокое визуальное и объективное качество работы. При использовании метрики Y-PSNR прирост качества составил до +0,75 дБ .

Литература

1. Kaup A., Reduction of ringing noise in transform image coding using simple adaptive lter // Electronics Letters, 1998, vol. 34, pp. 2110–2112 .

2. H. S. Kong, Y. Nie, A. Vetro, H. Sun, K. E. Barner, Coding artifact reduction using edge map guided adaptive and fuzzy lter // IEEE International Conference on Multimedia and Expo, 2004, pp. II-1135–1138 .

3. Tomasi C., Manduchi R., Bilateral Filtering for Gray and Color Images // Proceedings of the Sixth International Conference on Computer Vision, 1998, p. 839 .

4. Guangyu Wang, Tien-Tsin Wong, Pheng-Ann Heng, Deringing Cartoons by Image Analogies // ACM Transactions on Graphics, 2006, vol. 25, no. 4, pp. 1360–1379 .

Исследование эффективности модификаций генетического алгоритма для задачи выбора сбалансированного набора механизмов отказоустойчивости в вычислительных системах Пашков Василий Николаевич студент кафедры автоматизации систем вычислительных комплексов email: vasyapashkov@gmail.com научный руководитель Волканов Дмитрий Юрьевич В развитии современных вычислительных систем прослеживаются тенденции к повышению их функциональности за счёт увеличения числа используемых аппаратных модулей и компонентов, повышения сложности и размеров программного обеспечения, а также за счёт значительного роста данных, с которыми этим системам приходится работать. Проблема обеспечения стабильного безотказного функционирования вычислительных систем приобретает особую актуальность .

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

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

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

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

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

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

2. Отклонение от оптимального решения в среднем составило около 7 процентов .

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

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

Кафедра АСВК

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

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

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

4. Предложенные алгоритмы реализованы в виде программного средства .

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

–  –  –

2. Wattanapongsakorn N. and Coit D.W., Fault-tolerant embedded system design and optimization considering reliability estimation uncertainly,Reliability Engineering and System Safety, 92, pp. 395-407, 2007 .

Контроль нормального поведения приложений в подсистеме безопасности ядра Linux Торощин Эдуард Сергеевич студент кафедры автоматизации систем вычислительных комплексов email: hades@lvk.cs.msu.su научный руководитель к.ф.-м.н. Гамаюнов Денис Юрьевич В дипломной работе рассматривается задача контроля поведения приложений на узлах .

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

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

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

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

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

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

–  –  –

1. David Wheeler Secure programmer: Minimizing privileges [HTML] http://www.ibm.com/developerworks/linux/library/l-sppriv.html

2. Michael Wikberg Secure computing: SELinux 2007 [PDF] http://www.tml.tkk./Publications/C/25/papers/Wikberg_nal.pdf Разработка модели пользовательского трафика в глобальной сети на основе аналитических моделей трафика доменов Усков Евгений Иванович студент кафедры автоматизации систем вычислительных комплексов email: un1verse@lvk.cs.msu.su научный руководитель Качалин Алексей Игоревич Основная задача глобальной сети заключается в предоставлении сервиса пользователям. Например, глобальная сеть предоставляет доступ к таким сервисам, как электронная почта, информационные ресурсы, видео трансляции и т. д. Описанные возможности реализуются посредством передачи сетевого трафика, который представляет собой данные, передаваемые по сети .

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

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

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

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

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

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

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

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

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

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

1. T. Neame. Characterisation and Modelling of Internet Trac Streams .

Ph. D. thesis / The University of Melbourne. 2003 .

2. J. H. Cowie, D. M. Nicol, A. T. Ogielski. Modelling the Global Internet // Computing in Science and Engg. 1999 .

3. D.P. Heyman, D. Lucantoni. Modeling Multiple IP Trac Streams with Rate Limits // IEEE/ACM Trans. Network. 2003 .

4. Y. Liu, F. L. Presti, V. Misra. Scalable Fluid Models and Simulations for Large-Scale IP Networks // ACM Trans. Model. Comput. Simul. 2004 .

5. L. Muscariello, M. Mellia, M. Meo. Markov Models of Internet Trac and a New Hierarchical MMPP Model // Comput. Commun. 2005 .

Алгоритмы фотореалистичной визуализации на графических процессорах Фролов Владимир Александрович студент кафедры автоматизации систем вычислительных комплексов email: vfrolov@graphics.cs.msu.su научный руководитель к.ф.-м.н. Игнатенко Алексей Викторович Графические процессоры (GPU - Graphics Processing Unit) это массивнопараллельные вычислительые устройства, изначально ориентированные на ускорение метода растеризации в компьютерной графике. На настоящее время графические процессоры активно развиваются и совершенствуются, что позволяет решать на них все более сложные задачи. В последнее время значительно увеличилось число работ, посвященных ускорению фотореалистичной визуализации на GPU, например это работы [1], [2] .

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

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

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

Когда активных блоков становится мало, увеличивается количество одновременно трассируемых лучей на пиксел. Такая модель не только позволяет сделать трассировку путей адаптивной, но также выполнить все требования и Кафедра АСВК ограничения GPU, вызванные ее SIMD природой. Например, вследствие того, что все данные для лучей внутри блока хранятся последовательно, соблюдается правило объединения запросов к памяти (coalescing), характерное для архитектур G80/90, GT200 и GF100 .

Литература

1. Wang, R., Zhou, K., Pan, M., and Bao, H. 2009. An ecient GPU-based approach for interactive global illumination. ACM Trans. Graph. 28, 3 (Jul .

2009), 1-8 .

2. McGuire, M. and Luebke, D. 2009. Hardware-accelerated global illumination by image space photon mapping. In Proceedings of the Conference on High Performance Graphics 2009. ACM, New York, NY, 77-89 .

Автоматическое выделение объектов в данных лазерного сканирования Работа удостоена диплома III степени Шаповалов Роман Викторович студент лаборатории компьютерной графики и мультимедиа email: shapovalov@graphics.cs.msu.su научный руководитель к.ф.-м.н., н.с. Конушин Антон Сергеевич Работа посвящена классификации трёхмерных облаков точек, полученных при лазерной съёмке естественных сцен. В настоящее время эта задача успешнее всего решается с помощью разновидностей ассоциативных Марковских сетей. [1] В рамках такой модели невозможно выразить натуральные взаимодействия между объектами, такие как “крыша дома обычно находится выше земли”. В данной работе используются Марковские сети общего вида, что позволяет повысить точность классификации. Показано, как эффективно осуществлять вывод и настраивать параметры модели. Пересегментация используется для сокращения размерности данных, что приводит к ускорению работы алгоритма и упрощению структуры облака .

Реализована следующая схема. Сначала строится пространственный индекс над обучающим/тестовым облаком, который также служит сегментацией1. Для сегментов находятся медоиды, и над ними строится граф основа для Марковской сети. Затем вычисляются унарные и парные потенциалы вершин и рёбер. Для настройки унарных потенциалов используется алгоритм обучения Random Forest. В случае обучения ему на вход подаётся сокращённая выборка из векторов признаков точек обучающей выборки, в случае классификации признаки медоидов сегментов. Для настройки парных потенциалов используется статистика признаков рёбер по обучающему

Сегментация осуществляется с помощью библиотеки GML LidarK:

http://graphics.cs.msu.ru/en/science/research/3dpoint/lidark Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года скану. В работе описаны способы настройки парных потенциалов в рамках порождающей и разделяющей моделей. Когда унарные и парные потенциалы вычислены, запускается алгоритм TRW-S (sequential tree-reweighted messagepassing; передача сообщений на основе последовательного перевзвешивания деревьев) [2] для вывода в Марковской сети. Он возвращает финальное назначение меток классов медоидам сегментов, которые затем распространяются на сегменты целиком .

Результаты экспериментов показали превосходство разработанного метода над ассоциативными Марковскими сетями. Более подробно метод и его результаты описаны в [3] .

–  –  –

1. D. Anguelov, B. Taskar, V. Chatalbashev, D. Koller, D. Gupta, G. Heitz, A. Ng. Discriminative Learning of Markov Random Fields for Segmentation of 3D Scan Data. In IEEE Conference on Computer Vision and Pattern Recognition, San Diego, CA, 2005, pp. 169-176 .

2. V. Kolmogorov. Convergent Tree-Reweighted Message Passing for Energy Minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, 2006, pp. 1568-1583 .

3. R. Shapovalov, A. Velizhev, O. Barinova. Non-Associative Markov Networks for Point Cloud Classication. In Photogrammetric Computer Vision and Image Analysis, Paris, 2010. To appear .

Бустинг решающих деревьев с использованием методов эволюционной оптимизации Работа удостоена диплома I степени Янгель Борис Константинович студент кафедры автоматизации систем вычислительных комплексов email: hr0nix@acm.org научный руководитель к.ф.-м.н. Попова Нина Николаевна Бустинг [1] один из широко используемых алгоритмов обучения по прецедентам. Основная идея бустинга состоит в том, что неизвестная зависимость y(x) может быть приближена суммой базовых решающих правил

–  –  –

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

Оно затем добавляется к комбинации:

–  –  –

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

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

Реализация предлагаемого метода свободно доступна по адресу http://code.google.com/p/evoboost. Сравнение этой реализации с рядом современных методов решения задачи обучения классификаторов изображений по таким критериям, как скорость обучения и качество резульТезисы лучших дипломных работ факультета ВМК МГУ 2010 года тирующего классификатора, показывает перспективность предлагаемого метода .

Литература

1. R. E. Schapire. The Boosting Approach to Machine Learning: An Overview .

MSRI Workshop on Nonlinear Estimation and Classication, 2002 .

2. P. Viola, M. Jones. Robust Real-time Object Detection. International Journal of Computer Vision, 2001 .

3. B. Yangel. Fast Weak Learner Based on Genetic Algorithm. Труды конференции GraphiCon’09, 2009 .

4. A. Treptow, A. Zell. Combining Adaboost Learning and Evolutionary Search to Select Features for Real-Time Object Detection. Proceedings of the 2004 Congress on Evolutionary Computation, 2004 .

5. J. Wu, C. Brubaker, M. Mullin, J. Rehg. Fast Asymmetric Learning for Cascade Face Detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008 .

Автоматическое обновление аннотации новостного кластера Работа удостоена диплома III степени Алексеев Алексей Александрович студент кафедры алгоритмических языков email: bmw-motors@mail.ru научный руководитель к.ф.-м.н., с.н.с. НИВЦ МГУ Лукашевич Наталья Валентиновна На сегодняшний день в связи с развитием Интернета и в целом информационных технологий задача автоматического реферирования (аннотирования) приобретает все большую актуальность. Системы автоматического реферирования широко используются в новостных сервисах в сети Интернет, а также в других системах, работающих с большими объемами данных .

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

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

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

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

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

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

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

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

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

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

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

1. Лукашевич Н. В., Добров Б. В. Автоматическое аннотирование новостного кластера на основе тематического представления. Труды Международной конференции Диалог’2009. - Москва, РГГУ, 2009, стр .

299-305 .

2. Schiman B., McKeown K. Columbia University in the Novelty Track at TREC 2004. Proceedings of the Thirteenth Text Retrieval Conference (TREC’2004). - Gaithersburg, USA, 2004 .

3. Boudin F., El-Beze M., Torres-Moreno J.-M. The LIA Update Summarization Systems at TAC-2008. Proceedings of the Text Analyze Conference’2008. - Gaithersburg, Maryland USA, 2008 .

Автоматизированное формирование базы знаний для задачи анализа мнений Работа удостоена диплома III степени Четверкин Илья Игоревич студент кафедры алгоритмических языков email: ilia2010@yandex.ru научный руководитель к.ф.-м.н. Лукашевич Наталья Валентиновна В настоящее время в Интернете можно найти огромное количество отзывов о продуктах и услугах. В этих данных содержится много полезной информации, полученной людьми в результате их профессиональной и бытовой деятельности [1]. Приведем пример отзыва о фильме: Неожиданная развязка и новые герои делают этот фильм непохожим на предшественника .

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

Для решения задачи извлечения оценочных слов была выбрана предметная область о фильмах и сформированы 4 корпуса данных. Первые два корпуса состоят из данных, собранных с рекомендательного портала www.imhonet.ru, это корпус мнений, в который вошли 30 тысяч отзывов о фильмах с пользовательскими оценками от 1 до 10, и корпус описаний, в который входят 20 тысяч описаний фильмов. Кроме этих двух корпусов есть еще новостной корпус, который состоит из 1 млн. документов, и малый корпус, составленный из частей корпуса мнений. Таким образом, мы имеем два корпуса с высоким содержанием оценочных слов и два с низким. Все данные прошли предварительную морфологическую обработку и были разделены на прилагательные и неприлагательные ввиду того, что оценочные слова в основном являются прилагательными .

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

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

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

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

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

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

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

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

Для ее решения проводились эксперименты с наиболее распространенными алгоритмами машинного обучения. Оценка качества работы алгоритмов производилась по двум параметрам: F-мере и количеству оценочных слов, попавших в первую 1000 слов в выдаче классификатора, упорядоченных по оценке вероятности (чем ближе значение к 1, тем вероятнее слово является оценочным). Наилучшие показатели получились с использованием алгоритма логистической регрессии для прилагательных 69.1% и нейронных сетей для неприлагательных 50.9%. Рост качества для прилагательных составил 8.28%, для неприлагательных 20.6% по точности на первой тысяче слов (по сравнению со списками по характеристикам) .

После разработки набора характеристик и выбора алгоритмов классификации была реализована программная система извлечения оценочных слов .

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

1. А. Е. Ермаков. Извлечение знаний из текста и их обработка: состояние и перспективы. Информационные технологии, 2009 .

2. М. С. Агеев, Б. В. Добров, Н. В. Лукашевич, А. В. Сидоров. Экспериментальные алгоритмы поиска/классификации и cравнение с basic line .

РОМИП, 2004 .

Извлечение информации из новостных кластеров на основе автоматически сформированных шаблонов Работа удостоена диплома I степени Котельников Дмитрий Сергеевич студент кафедры алгоритмических языков email: info@dmitriu.com научный руководитель к.ф.-м.н. Лукашевич Наталья Валентиновна Задача извлечения информации состоит в выделении совокупности упоминаемых в тексте сущностей, отношений между ними и ситуаций, в которых они принимали участие .

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

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

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

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

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

1. Киселев С. Ермаков А. Плешко В. Поиск фактов в тексте естественного языка на основе сетевых описаний М.: Изд-во РГГУ, 2004 .

2. Хорошевский В. OntosMiner: семейство систем извлечения информации из мультиязычных коллекций документов М.: Физматлит, 2004 .

Моделирование поведения взаимодействующих агентов в среде с ограничениями Работа удостоена диплома II степени Юданов Анатолий Александрович студент кафедры алгоритмических языков email: XAPKOHHEH@gmail.com научный руководитель к.ф.-м.н. Бордаченкова Елена Анатольевна Подход к анализу систем с помощью их моделирования, в связи с ростом вычислительных мощностей и разработкой новых моделей, начинает применяться все более активно при решении множества практических задач, таких как анализ работы программных комплексов, анализ видео, звука. [1,2] В данной работе рассматриваются системы, состоящие из взаимодействующих компонент, причем функционирование системы в целом нельзя представить как сумму работы отдельных компонент .

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

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

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

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

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

Для предложенной модели выведены расширенные алгоритмы Баума-Уэлша и Витерби [3,4] .

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

Реализованная программная система моделирования была применена и испытана на игре Quake 3 с участием двух игроков, соревновавшихся от 5 до 10 мин. Результаты работы ССММ сравнивались с экспертной оценкой игры и с работой нескольких независимых СММ, процент ошибочной разметки ССММ составил 13-21% против 28-30% у независимых СММ .

–  –  –

1. Jun Yin and Yan Meng Meng Abnormal Behavior Recognition Using SelfAdaptive Hidden Markov Models Volume 5627/2009, pp. 337-346, 2009 .

2. Bobick, A. F., Davis, J. W. The Recognition of Human Movement Using Temporal Templates PAMI(23), No. 3, March 2001, pp. 257-267 .

3. Baum L. E., Petrie T., Soules G., Weiss N. A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains Ann. Math. Statist., vol. 41, no. 1, pp. 164–171, 1970 .

4. Viterbi A. J. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm IEEE Transactions on Information Theory 13 (2) April 1967 : 260–269 .

Кафедра СП Исследование новых подходов к организации аналитической обработки данных большого объема Работа удостоена диплома III степени Аро Диас Филипп Луисович студент кафедры системного программирования email: aro.dias@gmail.com научный руководитель д.т.н., профессор Кузнецов Сергей Дмитриевич Дипломная работа посвящена вопросам организации аналитической обработки крупномасштабных данных внутри систем хранилищ данных. В частности, уделяется внимание разработке распараллеливаемых статистических алгоритмов, выполняемых в аналитических хранилищах данных. В настоящее время распространенным подходом к организации статистического анализа является использование статистических пакетов, установленных на отдельных аналитических серверах. Данному подходу присущи высокие издержки на пересылку данных по сети, что становится существенным недостатком при работе с данными большого объема. В качестве альтернативы рассматривается выполнение статистических методов внутри хранилища данных .

Среди систем аналитических хранилищ данных, были рассмотрены те из них, которые основаны на СУБД с массивно-параллельной архитектурой, поскольку они являются наиболее масштабируемыми. Однако при использовании таких систем встает вопрос об организации параллельного выполнения аналитических функций, создаваемых пользователями. В отличие от SQLзапросов, пользовательский код не может быть автоматически распараллелен средствами СУБД. Одним из новых подходов, направленных на решение этой проблемы, является интеграция технологии MapReduce в массивнопараллельные СУБД. На текущий момент существуют две системы хранилищ данных, реализующих этот подход: Greenplum Database и Aster nCluster .

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

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

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

–  –  –

1. Cohen J., Dolan B., Dunlap M., Hellerstein J.M., Welton C. MAD Skills:

New Analysis Practices for Big Data. Proceedings of the VLDB Endowment .

Lyon, France: VLDB Endowment, 2009. P. 1481-1492 .

2. Friedman E., Pawlowski P., Cieslewicz J. SQL/MapReduce: A practical approach to self-describing, polymorphic, and parallelizable userdened functions. Proceedings of the VLDB Endowment. Lyon, France: VLDB Endowment, 2009. P. 1402-1413 .

3. Chu C., Kim S.K., Lin Y.A., Yu Y., Bradski G.R., Ng A., Olukotun K. Mapreduce for machine learning on multicore. NIPS. Vancouver, B.C., Canada:

MIT Press, 2006. P. 281–288 .

Кафедра СП Средства разработки расчётных моделей для моделирования ядерных реакторов Работа удостоена диплома III степени Плотникова Анастасия Константиновна студентка кафедры системного программирования email: askil@list.ru Научные руководители – профессор Крюков Виктор Алексеевич, старший научный сотрудник Головков Сергей Леонардович В дипломной работе изучаются и анализируются возможные пути решения проблемы создания расчетных моделей на основе предварительного построения и дальнейшего использования твердотельного представления расчетной области .

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

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

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

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

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

1. Афанасьев П. Б., Воронков А. В., Головков С. Л. Средства формирования расчетной модели комплекса программ РЕАКТОР-ГП. Ж. Вопросы атомной науки и техники. 2009. №24. С.56-64 .

2. Воронков А. В., Головков С. Л., Афанасьев П. Б. Средства генерации расчетных моделей для моделирования ядерных реакторов. Научный сервис в сети Интернет. Труды Всероссийской суперкомпьютерной конференции. М.: Изд-во МГУ, 2009. С. 71-75 .

3. Воронков А. В., Головков С. Л., Смирнов В. К. Распределенный архив пакета прикладных программ REACTOR-P. Научный сервис в сети Интернет. Труды Всероссийской научной конференции. М.: Изд-во МГУ, 2004. С. 64-65 .

4. Воронков А. В., Головков С. Л., Смирнов В. К. Распределенный Монитор пакета прикладных программ REACTOR. Научный сервис в сети Интернет. Труды Всероссийской научной конференции. М.: Изд-во МГУ, 2005. С. 50-53 .

5. Головков С. Л., Воронков А. В. Средства генерации расчётных сеток для моделирования ядерных реакторов. Научный сервис в сети Интернет. Труды Всероссийской научной конференции. М.: Изд-во МГУ, 2006 .

С. 14-16 .

6. Пьянов В. AutoCad-2010. САПР и графика. 2009. №4. С.74-79 .

(http://www.sapr.ru/Article.aspx?id=20637) .

7. Российский федеральный ядерный центр. Направления деятельности .

Исследования. Теоретические исследования, математическое моделирование. (http://www.vniief.ru/directions/reseach/teorz/dalee3.html)

8. Attila system website. (http://www.transpireinc.com/uence.htm) .

–  –  –

10. OpenCascade technology website (http://www.opencascade.org/occ/) .

11. Qt - a cross platform application and UI platform. (http://qt.nokia.com/) .

Кафедра СП Распараллеливание многоблочных задач для SMP-кластера Работа удостоена диплома I степени Притула Михаил Николаевич студент кафедры системного программирования email: pritmick@yandex.ru научный руководитель д.ф.-м.н. Крюков Виктор Алексеевич Одним из достоинств DVM-системы является то, что получаемые параллельные программы могут настраиваться при запуске на количество выделенных для них процессоров. Такое свойство программ позволяет запускать их на произвольном числе процессоров, компоновать сложные программы из имеющихся простых программ, повысить эффективность использования параллельных систем коллективного пользования за счет более гибкого распределения процессоров между отдельными программами. К сожалению, этим свойством не обладают DVM-программы, использующие механизм подзадач, поскольку он требует от программиста самому распределить процессоры между подзадачами. Распределение вручную зачастую затруднено вследствие большого количества подзадач, заметного разброса их сложности, необходимости осуществлять распределение на различное количество процессоров .

Постановка исследуемой задачи: Есть M процессоров, N подзадач, для каждой подзадачи известно:

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

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

3. функция зависимости времени исполнения от количества процессоров time(k) 0 такая, что для всех k из диапазона [Kmin, Kmax - 1] выполнено: time(k) * k time(k + 1) * (k + 1) Требуется составить оптимальное - с минимальным финишным временем

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

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

Алгоритм полностью описан и имеет алгоритмическую сложность асимптотически равную O(N * (N + M)), затраты по памяти асимптотически равны O(N + M). Предлагаемый алгоритм был реализован и включен в систему поддержки времени выполнения DVM-системы LibDVM в виде статической библиотеки функций. Результаты автоматического распределения сравнены с двумя вариантами ручного распределения, использовавшимися при расчете многоблочной задачи по обсчету аэродинамики самолета в ИПМ им. Келдыша РАН и показали заметное ускорение работы на больших количествах процессоров. Время работы текущей реализации алгоритма на синтетическом случайном тесте с 10000 подзадачами, 2048 процессорами на среднепроизводительном домашнем компьютере с процессором Intel Core 2 Duo с тактовой частотой 2,33 ГГц составило 100 секунд .

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

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

Литература

1. Н.А.Коновалов, В.А.Крюков, А.А.Погребцов, Н.В.Поддерюгина, Ю.Л .

Сазанов. Параллельное программирование в системе DVM. Языки Fortran-DVM и C-DVM. Труды Международной конференции Параллельные вычисления и задачи управления (PACO’2001) Москва, 2–4 октября 2001 г., 140–154 с .

2. Oliver Sinnen. Task Scheduling for Parallel Systems // John Wiley And Sons, Inc. 2007 .

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

Исследование методов разработки приложений баз данных в сервис-ориентированных кластерных архитектурах Работа удостоена диплома II степени Ручкин Дмитрий Андреевич студент кафедры системного програмирования email: dmitry.ruchkin@gmail.com научный руководитель д.т.н, проф., гл.н.с ИСП РАН Кузнецов Сергей Дмитриевич Долгое время технологии распределённых систем и технологии систем управления базами данных шли отдельно друг от друга, формируя свои подходы к работе с данными. В настоящее время имеется ряд предпосылок к Кафедра СП тому, чтобы частично интегрировать достижения этих областей. Одним из главных доводов к этому является то, что данные, с которыми должна работать СУБД, могут быть сильно распределены физически и должны быть доступны многим пользователям одновременно. Такая проблема актуальна в большом числе областей это масштабные современные научные проекты, сервера поисковых систем, веб-сервисы (например, Интернет-магазины) и т.д .

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

В данной работе проводится исследование того, как именно новые требования влияют на структуру СУБД и модель данных в целом (в частности, в работе развивается идея работы с данными в условиях ослабленной согласованности, описанной в работе [2]). В соответствии с этим предлагается обновлённая трёхуровневая схема архитектуры средств управления данными в данных условиях. Во-первых, внимание уделяется построению и деталям реализации самой распределённой среды для работы с новой моделью данных .

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

–  –  –

1. Florescu, D., and Kossmann, D. Rethinking cost and performance of database systems // ACM SIGMOD Record. 2009. 38. № 1. P. 43-48 [PDF] (http://doi.acm.org/10.1145/1558334.1558339) .

2. Vogels, W. Eventually Consistent // ACM Queue. 2008. 6. №6. P. 14-19 [HTML, PDF] (http://doi.acm.org/10.1145/1466443.1466448) .

Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Идентификация параметров и валидизация популяционных моделей фармакокинетики противосудорожных препаратов по данным терапевтического лекарственного мониторинга Работа удостоена диплома II степени Бондарева Кристина Игоревна студентка кафедры математической статистики email: kristuha@gmail.com научные руководители: профессор, д.ф.-м.н. Бенинг Владимир Евгеньевич; д.б.н., в.н.с. лаборатории фармакокинетики ГУ НИИ им. В.В. Закусова РАМН Литвин Александр Алексеевич Эпилепсия – одно из наиболее часто встречающихся неврологических заболеваний, распространенность которого оценивается приблизительно как 1% всего населения Земли. При лечении эпилепсии часто требуется длительная терапия противосудорожными препаратами (ПП). Индивидуализация такой терапии на основе популяционного фармакокинетического (ФК) моделирования по данным терапевтического лекарственного мониторинга (ТЛМ) может повысить эффективность лечения, позволяет избежать побочных эффектов. Для моделирования фармакокинетики препаратов обычно используются динамические камерные модели, описываемые системой дифференциальных уравнений. Все расчеты в работе были проведены с помощью лицензионной версии пакета программ USC*PACK (лаборатория Прикладной фармакокинетики Университета Южной Калифорнии, США) [2]. Этот пакет программ для изучения ФК поведения лекарств в определенной популяции пациентов позволяет реализовывать основные подходы: параметрический и непараметрический, в рамках каждого для идентификации параметров применяются методы максимального правдоподобия и Байесовский подход [1] .

В работе на основе имеющихся данных ТЛМ впервые были идентифицированы параметры популяционных моделей для основных вариантов противосудорожной политерапии. Затем эти модели использовались в работе в качестве априорной информации в Байесовских процедурах адаптивного управления для оценки индивидуальных значений ФК параметров пациентов по измеренным у них уровням ПП в крови. Целью работы также была внешняя валидизация процедуры индивидуализации противосудорожной терапии по данным ТЛМ, не вошедшим в расчет этих моделей, в реальных клинических условиях. Важность такого анализа обсуждается, например, в [3]. Во время получаемой пациентом хронической терапии концентрации ПП в крови могут варьироваться из-за флуктуаций и изменений фармакокинетики с течением времени, а также из-за ошибок измерения и необходимости использования упрощенной динамической модели для описания сложных ФК процессов .

На основе ретроспективного статистического анализа по данным пациентов с многократными процедурами ТЛМ (от 4 до 26 измерений концентрации) за период наблюдения от 1 до 6 лет в работе впервые была получена оценка Отделение бакалавров внутрииндивидуальной вариабельности, вызванной перечисленными причинами (16–28%), а также продемонстрировано приемлемое с клинической точки зрения качество прогноза концентрации для монотерапии вальпроатом (n = 662), карбамазепином (n = 556) и дуотерапии этими ПП (n = 830) (71–85% случаев). Оцененные статистические характеристики остатков между наблюдаемыми и предсказанными значениями концентрации, отсутствие систематической ошибки позволили сделать вывод, что информация, содержащаяся в измерениях уровня препарата в крови во время проведения одной процедуры ТЛМ, может считаться полезной для индивидуализации терапии и прогноза изменений этих уровней при изменении режима дозирования. Наблюдаемое некоторое снижение точности таких прогнозов для вальпроата в присутствии карбамазепина, возможно, связано с известным ФК взаимовлиянием этих препаратов. Уникальным свойством процесса связывания вальпроата белками крови является его зависимость от концентрации, что может приводить к появлению побочных эффектов. В данной работе не наблюдалось снижение точности прогноза в связи с ростом значений измеренной концентрации или в связи со значительным изменением суточной дозы ПП, то есть не наблюдалось статистически значимое влияние нелинейного процесса связывания на точность прогноза общей концентрации вальпроата в крови. Для всех ПП качество прогноза несколько снижалось с ростом значений глубины прогноза (статистически значимый временной тренд), но было показано, что даже для глубины прогноза более 2 лет его точность была допустима в 65–72% случаев без каких-либо проявлений систематической ошибки .

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

–  –  –

1. Bauer RJ., Guzy S., Ng Ch. A Survey of Population Analysis Methods and Software for Complex Pharmacokinetics and Pharmacodynamics Models with Examples. // The AAPS Journal, 2007. 9(1): 25–36 .

2. Jellie RW., Schumitzky A., Van Guilder M., Liu M., Hu L. Maire P. et al .

Individualizing drug dosage regimens: roles of population pharmacokinetic and dynamic models, Bayesian tting, and adaptive control. // Ther Drug Monit. 1993. 15(5): 380–393 .

3. Karlsson M.O., Sheiner L.B. The Importance of Modeling Interoccasion Variability in Population Pharmacokinetic Analysis. // Journal of Pharmacokinetics and Biopharmaceutics. 1993. 21(6): 735–750 .

Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Визуализация трехмерных неструктурированных массивов данных большого объема Работа удостоена диплома III степени Грызунов Дмитрий Аркадьевич студент отделения бакалавров информационных технологий email: DmitryGry@gmail.com научный руководитель к.ф.-м.н. Березин Сергей Борисович Целью данной работы была разработка программного обеспечения для визуализации трехмерных массивов дискретных данных больших объемов .

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

Для объединения множества объектов в кластеры используется Метод

Главных Компонент [5]. Далее краткое описание предметной области. Имеются точки с координатами x,y,z и диаметром s. Кластеры объекты, объединяющие множества точек. Кластер характеризуется двумя параметрами:

1)Центроид точка, олицетворяющая кластер (центр кластера);

2)Отклонение сумма отклонений всех точек кластера от центроида;

Центроид Xj и Отклонение j кластера Ij вычисляются по формулам:

P iI si xi Pj iIj si X 2 = 2 xi Xj j 2 iIj

–  –  –

Останавливаем процесс разбиения при достижении установленного порога .

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

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

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

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

–  –  –

1. Laur D. And Hanrahan Hierarchical Splatting: A Progressive Renement Algorithm for Volume Rendering In Proc. Siggraph 1991, ACM, 285–288 .

2. Mueller K. Moeller T. Splatting without the Blur Proc. Visualization 1999, IEEE, 363–370 .

3. Thomas Ertl Matthias Hopf Michael Luttenberger Hierarchical Splatting of Scattered 4D Data April 5, 2004 .

4. Zwicker M. Pfeister H. Van Baar J. And Gross Surface Splatting In Proc .

Siggraph 2001, ACM, 371–378 .

5. Jollie IT Principal Component Analysis 2002 New York: Springer Verlag .

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

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

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

Литература

1. NUI Group NUI Group MultiTouch Technologies Book, 2009 .

2. NUI Group Software and Hardware forum http://nuigroup.com/forums

3. NUI Group Community Wiki http://wiki.nuigroup.com

4. Microsoft Surface www.microsoft.com/surface Распознавание цитат в текстовых фрагментах Куренной Алексей Святославович студент кафедры математических методов прогнозирования email: alex-kurennoy@yandex.ru научный руководитель д.ф.-м.н. Воронцов Константин Вячеславович В работе решается задача распознавания правомерных заимствований в текстовых фрагментах. Эта задача возникла в связи с необходимостью повысить качество Интернет-сервиса Антиплагиат.ru. Проблема заключается в том, что правомерные цитаты не должны считаться плагиатом и снижать оценку оригинальности проверяемого документа. Формальных критериев, по которым можно было бы отличить правомерную цитату от плагиата, не существует. В то же время, человек различает эти ситуации относительно легко .

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

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

Для применения методов машинного обучения каждый фрагмент необходимо преобразовать в числовой вектор признаковое описание, в связи с этим была разработана система признаков текстового фрагмента. Её можно разделить на 3 группы. В группу синтаксических признаков входят признаки, показывающие наличие в участке текста тех или иных цепочек символов, например, внутритекстовых ссылок и отсылок. Для программного обнаружения отсылок была разработана специальная грамматика, учитывающая ГОСТ и то, как обычно оформлялись отсылки в окружении фрагментов обучающей выборки. Число признаков, направленных на обнаружение внутритекстовых ссылок и отсылок, равно 126. Помимо них в группу синтаксических признаков входит 20 признаков, показывающих присутствие в Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года окружении фрагмента фамилий и инициалов, а также 3960 признаков, которые отслеживают одновременное наличие фамилий и ссылок на небольшом расстоянии друг от друга. Признаковое описание включает и другие синтаксические признаки: заключён ли фрагмент в скобки, имеются ли в нём сочетания знаков, применяемых при прямой речи, и прочие. Группа лексических признаков проверяет присутствие в окружении фрагмента слов и словосочетаний цитирования. К ним относятся, например, отметил, с точки зрения и другие. Программа для нахождения значений признаков использует словарь, составленный в процессе разметки обучающей выборки. Третью группу образуют признаки длины фрагмента. Чрезмерно малая или слишком большая длина фрагмента говорит в пользу того, что он не является правомерным заимствованием. Для получения бинарных признаков, учитывающих длину фрагмента, был использован метод минимизации энтропии .

Число признаков первоначального признакового описания составило более пяти тысяч. Из него были удалены неинформативные признаки, принимающие одно и то же значение более чем на 99% фрагментов, в результате чего оно сократилось до 230 признаков. Для дальнейшего отбора признаков были применены стандартные методы, реализованные в пакетах RapidMiner и WEKA: генетический алгоритм и алгоритм best rst. Качество набора признаков измерялось с помощью двух функционалов, один из которых учитывает корреляцию признаков между собой и с целевой зависимостью .

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

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

Итоговое качество классификации составляет 2% ошибок первого рода (плагиат классифицирован как правомерное заимствование) и 12% ошибок второго рода (правомерная цитата классифицирована как плагиат). Указанное качество является приемлемым для практического применения .

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

Литература

1. D. W. Aha, L. A. Breslow. Simplifying decision trees: a survey. Navy center for applied research in articial intelligence, 1996, 47 c .

2. M. A. Hall. Correlation-based feature selection for machine learning: Ph.D .

thesis. The University of Waikato, 1999, 198 c .

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

3. К. В. Воронцов. Лекции по методу опорных векторов, 2007, 18 с .

Разработка программного средства-инструментария для исследования криптографических свойств булевых функций Работа удостоена диплома II степени Минеев Дмитрий Борисович студент кафедры математической кибернетики email: comrade_gandalf@mail.ru научный руководитель к.ф.-м.н. Буряков Михаил Леонидович Важным направлением исследований в области криптографии является изучение криптографических свойств булевых функций и связей между этими свойствами. Достаточное число математически содержательных соотношений между параметрами, описывающими различные криптографические свойства, облегчает решение сложной оптимизационной задачи выбора булевых функций при синтезе стойких криптосистем .

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

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

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

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

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

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

–  –  –

Разработанная архитектура программного средства позволяет легко добавлять новые модули и расширять функциональные возможности. Основной особенностью разработанного программного средства-инструментария является запуск алгоритмов вычисления криптографических свойств в фоновом (асинхронном) режиме в зависимости от сложности булевой функции или при большом наборе булевых функций отобранных для исследования. Выбранная технология развёртывания (Microsoft.NET Framework) делает разработанное средство кроссплатформенным и легкодоступным для пользователей любой категории. Для наглядного представления информации о булевых функциях был создан современный и многофункциональный графический пользовательский интерфейс .

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

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

Литература

1. О. А. Логачёв, А. А. Сальников, В. В. Ященко, Булевы функции в теории кодирования и криптологии. M.: МЦНМО, 2004

2. В. Б. Алексеев. Введение в теорию сложности алгоритмов (учебное пособие для студентов). М.: Издательский отдел факультета ВМК МГУ, 2002 .

3. В. В. Баев. Эффективные алгоритмы получения оценок алгебраической иммунности булевых функций. Диссертация на соискание ученой степени кандидата физико-математических наук, специальность 01.01.09, Москва, 2007 .

4. Мак-Дональд М. Windows Presentation Foundation в.NET 3.5 с примерами на C# 2008. Изд-во М.:Вильямс, 2008 .

5. Доктрина информационной безопасности Российской Федерации. В сб .

Научные и методологические проблемы информационной безопасности Под ред. В. П. Шерстюка, сс. 149–197 М.: МЦНМО, 2004 .

Отделение бакалавров Реализация операций обработки многомерных массивов на языке программирования F# Работа удостоена диплома I степени Рубанов Максим Сергеевич студент лаборатории технологий Microsoft email: rubanov.m@gmail.com научный руководитель к.ф.-м.н. Березин Сергей Борисович Массивы одна из наиболее часто используемых структур данных. В связи с этим, логично возникает вопрос о создании эффективных методов работы с массивами, а также приёмов, позволяющих оптимизировать выполнение операций над ними. При значительных размерах обрабатываемых объектов вопрос об оптимизации встаёт особенно остро .

Для того чтобы оптимизации могли быть реализованы, нужен язык, на котором можно было бы записать операции над массивами в виде выражений (запросов). Что касается свойств такого языка, то исследователи сходятся во мнении, что язык должен содержать небольшое количество операторов, а также обладать возможностями для нетривиальных преобразований структур данных [1]. Этим критериям удовлетворяет язык AML (Array Manipulation Language) [2] .

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

Операция Merge производит слияние двух массивов в общую структуру данных. Наконец, Apply служит для применения пользовательских функций к элементам массива. Также помимо описанных операций, в AML определён ряд правил для оптимизации выражений, сформулированных в виде теорем .

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

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

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

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

Литература

1. D. Maier, B. Vance. A Call to Order. In Proс. of the ACM SIGACTSIGMOD-SIGART Symposium on Principles of Database Systems. 1993 .

P. 1-16 .

2. Arunprasad P. Marathe, Kenneth Salem. A Language for Manipulating Arrays. Proceedings of the 23rd International Conference on Very Large Data Bases. 1997. P.46-55 .

Система автоматизированной защиты программного обеспечения от несанкционированного доступа Работа удостоена диплома I степени Третьяков Ярослав Игоревич студент кафедры алгоритмических языков email: yarhotty@gmail.com научный руководитель к.ф.-м.н. Абрамов Владимир Геннадьевич Данная выпускная квалификационная работа исследует проблемы несанкционированного доступа к программному обеспечению (далее ПО) и средства защиты от него. Проблема нелицензионного копирования ПО является основным фактором, замедляющим развитие современных информационных технологий. Кроме того, оно несёт в себе значительный вред для экономики, как внутригосударственной, так и международной. В ходе работы были проанализированы основные методики защиты ПО от несанкционированного доступа и их эффективность.

В результате исследования были сделаны два важных вывода о защите ПО:

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

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

также она известна как SaaS (Software as a Service) и SoD (Software on Demand). Основной особенностью подобного ПО является способ его монетизации - оплата за использование принимается от пользователей не разово, при покупке, а по мере использования ПО .

В данной работе реализован комплекс программных средств, позволяющий при малой затрате человеческих ресурсов обеспечить преобразование стандартной программы (исполняющейся на одной машине) к SaaSархитектуре. После данного преобразования для полноценной работы программа должна установить соединение с сервером и авторизоваться с помощью лицензионного ключа. Подобная архитектура делает программу практически неуязвимой для большинства атак. Единственной относительно простой атакой в данном случае является вызов удалённого метода неавторизованным пользователем через авторизованного. Для противостояния данной атаке была реализована модель удалённого хранения данных: каждый объект, который должен размещаться в динамической памяти, размещается на сервере. Это организованного следующим образом: при вызове конструктора объекта на сервер посылается запрос на создание удалённого объекта. В ответ возвращается уникальный идентификатор этого объекта, который в последствие используется как указатель this при вызове удалённых методов. Защита от вышеописанной атаки осуществляется путём ограничения количества управляющих объектов на сервере .

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

При реализации решения преследовались две главные цели:

1) преобразованию могут быть подвержены любые программные продукты (в т.ч. уже готовые)

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

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

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

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

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

Разработка методики сравнения банковских веб-сайтов Работа удостоена диплома III степени Фам Ху Куанг студент кафедры алгоритмических языков email: pimply_p00m@yahoo.com научный руководитель д.ф.-м.н. Соловьев Сергей Юрьевич Данная работа специализируется в области веб-дизайна. Объектом для исследования был банковский сектор российского Интернет, который в настоящий момент стремительно развивается. Работа рассматривает задачу сравнения банковских веб-сайтов, результатом которой является выяснение степени близости данного сайта к совершенству .

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

• Визуальное представление. Он должен, как и визитная карта компании, запомниться посетителю и дать понять, чем компания занимается .

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

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

• Веб-сервисы. Сайты кредитных организаций должны содержать главные банковские веб-услуги: интернет-банк и нахождение филиалов/банкоматов .

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

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

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

Критерии проверки автоматического анализатора включают:

• Плохие заголовки страниц

• Ссылки, ведущие на ту же страницу, которая содержит эти ссылки

• Неподчеркнутые ссылки

• Посещенные ссылки без отдельной окраски

• Слишком длинные текстовые абзацы

• Тексты прописными буквами

–  –  –

1. Якоб Нильсен Веб-дизайн, книга Якоба Нильсена Издательство СимволПлюс, 2007 .

2. Стив Круг Веб-дизайн, или Не заставляйте меня думать Издательство Символ-Плюс, 2008 .

3. Артемий Лебедев Ководство .

Тезисы лучших дипломных работ факультета ВМК МГУ 2010 года Разработка средств создания мобильных биобиблиографических энциклопедий Работа удостоена диплома III степени Яковлев Игорь Юрьевич бакалавр IV курса по направлению Информационные технологии email: hellqx@mail.ru научный руководитель к.б.н. Леонов Михаил Васильевич Целью квалификационной работы была разработка программного средства (пакета) для создания и сопровождения специализированной информационной системы с биографическими и библиографическими данными. В ходе работы в качестве примера была создана энциклопедия по первому директору ботанического сада Георгу-Францу Гофману .

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

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

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

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

1. Мак-Дональд М. Windows Presentation Foundation в.NET 3.5 с примерами на C# 2008. Изд-во М.:Вильямс, 2008 .

2. Прохоренок Н.А. Jquery.Новый стиль программирования на JavaScript .

Изд-во М.:Вильямс, 2010 .



Pages:     | 1 || 3 |



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

«444 МАТЕМАТИЧНІ МЕТОДИ, МОДЕЛІ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ В ЕКОНОМІЦІ Баглан Т. Аймурзина, Куралай Ж. Садвакасова РЫНОК ТРУДА КАК ОБЪЕКТ ПРОГНОЗИРОВАНИЯ: ЗАРУБЕЖНЫЙ ОПЫТ И ВОЗМОЖНОСТИ ЕГО ПРИМЕНЕНИЯ В КАЗАХСТАНЕ В статье рассмотрен рынок труда как объ...»

«ГОУ ВПО РОССИЙСКО-АРМЯНСК ИЙ (СЛАВЯНСКИЙ) УНИВЕРСИТЕТ Составлена в соответствии с У Т В Е Р Ж ДАЮ : государственными требованиями к ми н и м у м у с о д е р ж а ни я и у ро вн ю Ректор А.Р. Дарбинян подготовки выпускников по указанным направлениям и Положением РАУ " О порядке разработки и утверж дения учебных программ". математической кибернети...»

«ГУСЕВА Ирина Николаевна ФЛОРА ЛЕСОВ ЦЕНТРАЛЬНОГО ПРЕДКАВКАЗЬЯ И ЕЁ АНАЛИЗ 25.00.23 – Физическая география и биогеография, география почв и геохимия ландшафтов АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата географических наук Ставрополь 2015 Работа выполнена в Федеральном государственном автономном образовательном учрежден...»

«ИТФ-93-26? Ь, И-Р(,).4ано'\ Г.Ф.Филиппе. ПОДЯРИЗЛЦШ ДЕЙТРОНОВ 1 1рсцаса5 м 5 -z СГОДКНОВЕНШ Академия наук Украины •'нститут теоретической физики лм,Н.Н.Боголюб ова Препринт В.Н.Романов, Г.Ф.Филиппов ПОЛЯРИЗАЦИЯ ДЕЙТРОНОВ В ПРОЦЕССЕ ИХ СТОЛКНОВЕНИЯ 2 Киев 199Э [л УДК 529.T...»

«Российская академия наук "Утверждаю" Президент Российской академии наук Академик В.Е. Фортов "_" 2016 г. ПРОГРАММА ФУНДАМЕНТАЛЬНЫХ ИССЛЕДОВАНИЙ ПРЕЗИДИУМА РАН Программа № I.7 "Экспериментальные и теоретические исследования объектов Солнечной системы и планетных систем звезд. Переходные и взрывные процессы в астрофизике" Аннот...»

«PI 3-96-297 А.К.Попов АНАЛИЗ УСТОЙЧИВОСТИ ИМПУЛЬСНОГО РЕАКТОРА ИБР-2 ПРИ ДЕВЯТИПАРАМЕТРИЧЕСКОИ МОДЕЛИ МОЩНОСТНОЙ ОБРАТНОЙ СВЯЗИ © Объединенный институт ядерных исследований,...»

«. Москва БИНОМ. Лаборатория знаний УДК 544+547+678 ББК 24.58я73 Л42 Лейкин Ю. А.Л42 Физико-химические основы синтеза полимерных сорбентов : учебное пособие / Ю. А. Лейкин. — М. : БИНОМ. Лаборатория знаний, 2011. — 413 с. : ил. — (Уч...»

«ж ФИЗИКА И ТЕХНИКА СПЕКТРАЛЬНОГО АНАЛИЗА (БИБЛИОТЕКА ИНЖЕНЕРА) Серия выпускается под общим руководством Комиссии по спектроскопии АН СССР ГОСУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВО ФИЗИКО-МАТЕМАТИЧЕСК...»

«Химия и Химики № 1 (2010)    Химия галогенов В. П. Зломанов Введение Несмотря на то, что свойства галогенов и их соединений описаны лучше, чем других элементов [1], остается много новых неожиданных фактов, которые требуют своего объяснения. К ним относится, например, фундаментальная...»

«А. Г. Терещенко, Н. П. Пикула, Т. В. Толстихина ВНУТРИЛАБОРАТОРНЫЙ КОНТРОЛЬ КАЧЕСТВА РЕЗУЛЬТАТОВ АНАЛИЗА С ИСПОЛЬЗОВАНИЕМ ЛАБОРАТОРНОЙ ИНФОРМАЦИОННОЙ СИСТЕМЫ...»

«СТРУКТУРА ЦФ РАН ЦФ РАН был организован 8 октября 1996 г. Постановлением Президиума РАН на базе Отдела фотохимии ИХФ АН СССР, созданного в 1987 году приказомраспоряжением Минхимпрома СССР и АН СССР. ЦФ РАН работает в области структуры, динамики и фотоники супрамолекулярных систем и наноструктурированных материалов. Деятельность Центра направлена н...»

«Лейкин Алексей Юрьевич АРОМАТИЧЕСКИЕ ПОЛИБЕНЗИМИДАЗОЛЫ ДЛЯ ВЫСОКОТЕМПЕРАТУРНЫХ ПРОТОНПРОВОДЯЩИХ МЕМБРАН 02.00.06 – Высокомолекулярные соединения АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата химических наук Москва – 2009 Работа выполнена в Инжиниринговом центре водородных технологий и альтернативной энергет...»

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

«Московский государственный университет имени М. В. Ломоносова физический факультет Ю. И. Кузнецов, В. М. Шахпаронов RC-ГЕНЕРАТОР Методическая разработка для Практикума по радиофизике Москва 2016 УДК 537.862:621.373.121.15 Юрий Иванович Кузнецов, Владимир Михайлович Шахпаронов. RС -...»

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Направление — Астрономия (011501) Профиль — звездная астрономия Асипович Ася Дмитриевна БЛИЗКИЕ К ПЕРИОДИЧЕСКИМ ОРБИТЫ В РАВНОБЕДРЕННОЙ ЗАДАЧЕ ТРЕХ ТЕЛ Дипломная работа Научный руковод...»

«ФЗИ-1781 ФИЗИКО-ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ П. В. ВЫРОДОВ, А. С. КРУГЛОВ, В. Л. ФАЗКУЛЛИН Автоматизированная система для исследования радиационной ползучести материалов в ядерном реакторе БР-10 Многоканальный измеритель температуры Обнинск — 1986 УДК 621.039....»

«ФХФ-2011 Лекция 6. Окислительно-восстановительные реакции Те химические реакции, в которых изменяются степени окисления взаимодействующих веществ, называют окислительно-восстановительными. Отметим, что понятие степень окисления является условным и обозначает состояние частицы, которая пот...»

«С616Ц8ЙИ1 обидшшп института 1Д1РИЫХ иселднаш! ДУМ 13-87-773 В.Д.Аксиненко, Н.С.Глаголева, |Е.А.Дементьев], Н.И.Каминский, А.Т.Матюшин, В.Т.Матюшин, Н.Н.Нургожин*, С.А.Рожнятовская, В.Н.Ряховский, Е.К.Хусаинов* СИСТЕМА ВЫСОКОВОЛЬТНОГО ИМПУЛЬСНОГО ПИТАНИЯ СТРИМЕРНОЙ КАМЕРЫ СПЕКТРОМЕТРА ГИБС Институт физики высоких энергий АН КазССР,...»

«НАНОСИСТЕМЫ: ФИЗИКА, ХИМИЯ, МАТЕМАТИКА, 2013, 4 (1), С. 48–53 УДК 546.41:546.185:617:666.3:666.1:666.9 ПОЛИМОРФИЗМ Ca3(PO4)2 П. В. Евдокимов1, В. И . Путляев1,2, Д. А. Мерзлов2, Т. Б. Шаталова2,...»

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

«УДК 66.0451.091.001.57 : 681.3.06 ХИМИЧЕСКАЯ ТЕХНОЛОГИЯ Академик В.В. КАФАРОВ, В.П. МЕШАЛКИН, Г.И. МАНКО ИНФОРМАЦИОННЫЙ КРИТЕРИЙ ПРОВЕРКИ ГИПОТЕЗ О ЗАКОНАХ РАСПРЕДЕЛЕНИЯ ХАРАКТЕРИСТИК НАДЕЖНОСТИ ХИМИКО-ТЕХНОЛОГИЧЕСКИХ СИСТЕМ Одним из этапов системного анализа надежн...»

«Одеська національна академія харчових технологій РОЗДІЛ 2 ХІМІЧНІ, ФІЗИЧНІ ТА МАТЕМАТИЧНІ МЕТОДИ ДОСЛІДЖЕННЯ ПРОЦЕСІВ ТА АПАРАТІВ 58 Збірник наукових праць молодих учених, аспірантів та студентів, 2014 Одеська національна академія харч...»

«оценка справедливой доходности основные параметры выпуска Группа компаний "Полипласт" — лидер российского рынка Выпуск химических добавок для бетона. Производственные мощноНоминал, валюта 1 000 руб. сти Группы расположены в разных регионах с...»

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

«№ 2 (2), 2013 Естественные науки. Химия ХИМИЯ УДК 544.2:[546.273:543.4] С. В. Костюков ИССЛЕДОВАНИЕ ВЛИЯНИЯ ПРИМЕСЕЙ ПРАЗЕОДИМА, ТУЛИЯ И ГОЛЬМИЯ НА ЛЮМИНЕСЦЕНЦИЮ ТВЕРДЫХ РАСТВОРОВ Y1-xYBxAL3(BO3)4 Аннотация. Актуальность и...»

«Дата последней редакции APRIL 2013 Редакция 5 ПАСПОРТА БЕЗОПАСНОСТИ ВЕЩЕСТВ И МАТЕРИАЛОВ Смывка для флюса 1 ИДЕНТИФИКАЦИЯ ХИМИЧЕСКОЙ ПРОДУКЦИИ И СВЕДЕНИЯ О ПРОИЗВОДИТЕЛЕ ИЛИ ПОСТАВЩИКЕ 1.1. Идентифика...»

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

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ _ Казанский государственный энергетический университет А.Г. ЛАПТЕВ, И.А. ВЕДЬГАЕВА УСТРОЙСТВО И РАСЧЕТ ПРОМЫШЛЕННЫХ ГРАДИРЕН Казань 2004...»

«СОРБЦИОННЫЕ СВОЙСТВА И БИОТЕХНОЛОГИЧЕСКИЕ АСПЕКТЫ МОДИФИЦИРОВАННЫХ ПРИРОДНЫХ АЛЮМОСИЛИКАТОВ Шапкин Николай Павлович доктор химических наук, профессор Дальневосточного федерального университета, РФ, г. Владивосток E-mail: npshapkin@gmail.com Хальченко Ирина Григорьевна старший преподаватель Дальневосточного...»








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

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