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

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

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

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

В мире научных открытий, 2010, №1 (07), Часть 4

Материалы Общероссийской электронной научной конференции

"Актуальные вопросы современной науки и образования"

г. Красноярск, декабрь 2009 г.

ГРНТИ 27 МАТЕМАТИКА

УДК 519.67

ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА TAYLOR V. 3.0

М.А. Милкова, младший научный сотрудник

Центральный экономико-математический институт РАН г. Москва, Россия TAYLOR v. 3.0 – программная система, позволяющая с помощью оригинальных рекуррентных алгоритмов получать разложение функций, заданных различными способами, в ряд Тейлора на основе формул дифференциального исчисления, решать некоторые типичные, одномерные и многомерные, а также специальные задачи. Система функционирует в Windows в интерактивном режиме.

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

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

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

TAYLOR разработан в Центральном экономико-математическом институте РАН. В основе системы лежит компьютерная «Алгебра дифференцирования» (АД) - совокупность специальных рекуррентных алгоритмов, автором которых является д.ф-м.н., проф. В.З.

Беленький. Алгоритмы предназначены для вычисления по формулам дифференциального исчисления точного значения производных (произвольных порядков) от функций, заданных формулами любой сложности, начиная от суперпозиции элементарных функций и заканчивая функциями, заданными неявно. Периодически расширяющийся комплекс алгоритмов АД публиковался в форме препринтов [3], [1], а также в журнале «Кибернетика» [4], [5]. В настоящее время система TAYLOR функционирует в Windows.





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

в этом отношении TAYLOR является уникальной системой, не имеющей аналогов.

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

В мире научных открытий, 2010, №1 (07), Часть Каталог процедур системы TAYLOR v. 3. TAYLOR 3 включает процедуры четырех уровней. Процедуры базового уровня являются фундаментом системы;

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

Базовый уровень: получение полиномов Тейлора Процедуры получают коэффициенты c полинома Тейлора функции y = y(x) :

k n 1 (k ) p ( x) := c ( x x ) k, c = C ( y, x ) := y ( x ) n k 0 k k 0 k!

k = Задаются формула функции y(x), точка x0, а также порядок разложения n.

В системе допускается 10 способов задания функции y(x) :

Явная функция. Задается явная формула функции y = f (x ).

1) Обратная функция. Разложение строится для функции y(x), обратной к заданной 2) функции x = g ( y ).

y(x) Параметрическая функция. Функция определяется соотношениями 3) x = f1 (t ), y = f 2 (t )..

y(x) Блочная явная функция. Функция задается соотношением 4) u1 ( x),..., u m ( x) y = F [ x, u1 ( x),..., u m ( x)}], m 3;

– промежуточные функции (блоки).

Обратная к блочной функции. Разложение строится для функции y(x), обратной к 5) m 3;

u1 ( y ),..., u m ( y) заданной функции x = G[ y, u1 ( y ),..., u m ( y )}], – промежуточные функции (блоки).

F ( x, y ) = F ( x 0, y 0 ) Неявная функция. Функция y(x) определяется тождеством 6).

y(x) Сложная неявная функция. Функция определяется тождеством 7) Ф( x, y ) = Ф( x 0, y 0 ), Ф( x, y ) = F [ x, y, u1 ( x, y),..., u m ( x, y )}], m 3;

где u1 ( x, y ),..., u m ( x, y ) – промежуточные функции.

8) ОДУ первого порядка. Функция y(x) определяется как интегральная кривая обыкновенного дифференциального уравнения y' = G ( x, y ), y( x0 ) = y. (1) 9) ОДУ m-го порядка. Функция y(x) определяется дифференциальным уравнением высокого порядка y ( m) = G ( x, y, y ',..., y ( m1) ) y ( x0 ) = y y ' ( x0 ) = y 02 m5. (2)...

y ( m1) ( x0 ) = y 0 m 10) Сингулярное ОДУ. Функция y(x) определяется дифференциальным уравнением с нулевым коэффициентом при старшей производной В мире научных открытий, 2010, №1 (07), Часть x y ( m ) ( x) = G[ x, y, y ',..., y ( m 1) ] x0 = y ( x 0 ) = y m y ' ( x 0 ) = y...

( m 1) y ( x 0 ) = y 0m. (3) 11) Система ОДУ. Векторная функция Y (x ) определяется как интегральная кривая системы дифференциальных уравнений в m-мерном пространстве.

Y ' ( x) = G ( x, Y ) (Y, G R m ), m, Y ( x 0 ) = Y0. (4) Процедуры первого уровня Данные процедуры решают некоторые типичные одномерные задачи.

Корень явной функции. Процедура находит корень уравнения f ( x ) = 1) x в окрестности заданного начального значения 0.

2) Корень блочной функции. Процедура находит корень уравнения заданного в виде F[ x, u1 ( x),..., u m ( x)] = 0, m явной блочной функции в окрестности заданного x начального значения.

f (x ) процедура находит корень Корень производной. Для заданной функции 3) уравнения f ' ( x ) = 0, находящийся в окрестности заданного приближения 0.

x 4) Определенный интеграл. Для заданной функции f (x ) и пределов интегрирования b Int = f ( x)dx a, b вычисляется значение интеграла a.

Решение задачи Коши для ОДУ 1-го порядка. Для дифференциального уравнения (1) 5) вычисляется значение функции y(x) на правом конце: y(x 1 ).

Процедуры второго уровня Данные процедуры решают некоторые типичные многомерные задачи.

Решение системы двух уравнений. Для заданных функций F1 ( x), F2 ( x) 1) ( x0, y 0 ) в окрестности начального приближения находится решение системы уравнений F1 ( x, y ) = F2 ( x, y ) = Решение задачи Коши для ОДУ m-го порядка. Для дифференциального уравнения 2) (2) вычисляется значение функции y(x) на правом конце: y(x 1 ).

3) Решение задачи Коши для системы ОДУ. Для системы дифференциальных Y = ( y1 ( x), y 2 ( x),..., y m ( x)) уравнений (4) вычисляется значение вектор-функции на правом ( y ( x ), y ( x ),..., y ( x )), m конце: 1 1 2 1 m 1.

Специальные задачи Данные процедуры решают некоторые специальные задачи. В версию 3.0 программного продукта TAYLOR включены 2 специальные задачи.

1) Разложение в ряд Тейлора решения уравнения Беллмана В мире научных открытий, 2010, №1 (07), Часть Рассматривается уравнение Беллмана для одномерной стационарной модели экономической динамики в дискретном времени (см. [6]):

V ( x) = max[U (c) + V ( y )] | y = F ( x c ), x0.

0 c x Здесь x – капитал системы;

c – потребление, U (c ) – функция полезности;

z = x c – инвестиции в производство, F (z ) – производственная функция, y = F (z ) – капитал системы через единицу времени;

(0,1) - коэффициент дисконтирования;

V (x) – функция выигрыша.

В регулярной модели переходная функция x y = Y (x ) имеет неподвижную точку (единственную и устойчивую) x * = F ( z * ), где z * - корень уравнения F ' ( z ) = 1 /.

Исходной информацией является информационный паспорт модели {U (c ), F ( z ), }.

Процедура находит неподвижную точку x * и коэффициенты разложения функции выигрыша V, переходной функции Y и стратегии потребления - функции C.

Более подробно об алгоритме получения разложения решения уравнения Беллмана можно прочесть в [2].

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

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

Int = w f ( x) sin( wx )dx, (5) x где f (x ) – достаточно гладкая функция, экспоненциально убывающая на бесконечности, w 1 - частота осцилляций (колебаний);

такие интегралы встречаются во многих задачах математической физики.

Процедура вычисляет значение интеграла (5). Для вычисления используются формулы асимптотических разложений по параметру w (см. [7]).

Работа в системе Система функционирует в интерактивном режиме;

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

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

Стартовое окно системы приведено ниже:

В мире научных открытий, 2010, №1 (07), Часть Рис. 1. Стартовое окно системы После выбора интересующей процедуры пользователь переходит в соответствующее окно, где и приступает к непосредственной работе.

Примеры некоторых процедур приведены ниже:

Рис. 2. Окно для получения коэффициентов разложения в ряд Тейлора неявной функции В мире научных открытий, 2010, №1 (07), Часть Рис. 3. Окно для получения разложения решения уравнения Беллмана Принцип работы в системе построен на использовании специально разработанных DLL библиотек, что позволяет говорить не только об интерактивной версии TAYLOR, но и о, так называемой, рабочей версии, более широкой по своим возможностям, где пользователь может обращаться к представленным процедурам непосредственно из своей среды путем подключения библиотек.

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

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ 1. Беленький В.З. Базовые алгоритмы алгебры дифференцирования для ЭВМ. М.: ЦЭМИ РАН, 2003. – 46 с.

2. Борисова М.А. Применение Алгебры дифференцирования к исследованию решения уравнения Беллмана. // Сборник «Анализ и моделирование экономических процессов», вып. 5. – М.: ЦЭМИ РАН, 2008.

3. Беленький В.З. Базовые алгоритмы алгебры дифференцирования для ЭВМ. М.: ЦЭМИ АН СССР, 1983 г. (препринт) В мире научных открытий, 2010, №1 (07), Часть 4. Беленький В.З. Сообщение о программной системе «Алгебра дифференцирования TAYLOR» // Кибернетика, 1989, N 3.

5. Беленький В.З., Васильева О.А., Кукаркин А.Б. Программный модуль «Алгебра дифференцирования TAYLOR»: результаты численных экспериментов, сообщение о версии 2.1 // Кибернетика и системный анализ, 1997, N3.

6. Беленький В.З. «Оптимизационные модели экономической динамики», М.: Наука, 7. Эрдейи А. “Асимптотические разложения”, М.: ГИФМЛ, 1962.

УДК 519.2:51. АНАЛИЗ И ТИПОЛОГИЗАЦИЯ АРТЕФАКТОВ АРХЕОЛОГИЧЕСКИХ ПАМЯТНИКОВ Т.В. Пак, кандидат физико-математических наук Я.И. Еремеева, магистрант Дальневосточный государственный университет г. Владивосток, Россия Согласно утвердившейся в археологии точке зрения наиболее информативным источником, несущим сведения о самых различных сторонах материальной и духовной жизни общества, является керамика. Результаты анализа керамики позволяют решить многие проблемы, в том числе этногенеза и хронологии, реконструировать древние представления.

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

• Памятник "Ветка-2" (обозначение сосудов - В_С1, В_С2, …) находится в Ольгинском районе, деревня Ветка.

• Памятник "Бойсмана-2" (Б_С1, Б_С2, …) находится в Хасанском районе.

• Памятник "Лузанова Сопка-2" (ЛС_С1, ЛС_С2, …) находится в Хорольском районе.

• Памятник "Моряк-Рыболов" (МР_С1, МР_С2, …) находится в Ольгинском районе.

Возраст этих поселений 6200-5800 лет до н.э. [1]. Найденные фрагменты сосудов были изучены, распределены к разным сосудам, в зависимости от толщины стенок и материала, из которого изготовлены сосуды, и зарисованы. Имея данные по керамике с четырех археологических памятников необходимо:

• Выстроить иерархию признаков.

• Выделить локальные варианты керамики, характерные для каждого памятника.

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

Сосуды (22 фрагмента) памятника «Лузанова Сопка-2» были подвергнуты статистической обработке. Сосуды имеют характерные признаки, которые можно разделить на четыре группы:

• Форма венчика, • Наличие валика, • Форма среза венчика, • Техника орнаментации.

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

В мире научных открытий, 2010, №1 (07), Часть Таблица Описание керамики № Приз Название № Признак Название № Признак Название нак Прямой Заостренная Диагональные 1 8 венчик кромка гребенки Загнутый Орнамент Лопатки по 2 9 венчик по срезу горизонтали венчика Валик на Ромбы в Лопатки в 3 10 сосуде шахматном треугольнике порядке Горизонтальн Ромбы в ряд Отступающая 4 11 ая кромка лопатка Округлая Треугольни Овалы в линию 5 12 кромка ки по диагонали Скошенная Ромбы в Прочерченная 6 13 внутрь треугольник линия кромка е Скошенная Вертикальн Прочерченная 7 14 наружу ые гребенки полукруглая кромка линия Признаки из групп «форма венчика» и «форма среза венчика» присутствуют на сосуде лишь один раз в отличие от признаков групп «наличие валика» и «техника орнаментации».

Все признаки сосудов были закодированы: 1 - если признак присутствует на сосуде, и 0 если отсутствует.

Каждому признаку присвоен свой цифровой индекс, что упрощает дальнейшую обработку [2].

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

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

d rs = p d ps + q d qs + d pq + d ps d qs.

Если кластеры p и q объединяются в кластер r и требуется рассчитать расстояние от нового кластера до кластера s, применение того или иного метода зависит от способа определения расстояния между кластерами, эти методы различаются значениями коэффициентов p, q, и.

В табл. 2 приведены коэффициенты пересчета расстояний между кластерами p, q, и.

В мире научных открытий, 2010, №1 (07), Часть Таблица Методы, используемые в SPSS, и их коэффициенты p q Название метода Ближайший сосед 12 12 ~1 Дальний сосед 12 12 Кластеринг медианы 12 12 ~1 4 Связь между группами 12 12 0 kp kp Связь внутри групп 0 k p + kq k p + kq k p kq kp kp Кластеринг центройда k p + kq k p + kq k p + kq kr + k p kr + k p kr Метод Уорда kr + k p + kq kr + k p + kq kr + k p + kq где k p, k q, k r - количество объектов в кластерах p, q и r, соответственно.

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

В результате анализа данных выяснилось, что от выбора метода зависит построение дендрограммы и разделение объектов на кластеры. Таким образом, в большинстве случаев, методы «Связь внутри групп» и «Дальний сосед» делят сосуды на одинаковые по количеству объектов кластеры;

методы «Ближайший сосед», «Кластеринг центройда» и «Кластеринг медианы» выделяют одиночные кластеры;

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

Результаты кластеризации по методу «Связь внутри групп», когда получилось 2-3 и 19- кластеров, считаются неверными, потому что это означает, что либо все сосуды принадлежат одному кластеру, либо каждый сосуд - это отдельный кластер. Анализ оставшихся мер показывает, что сосуды делятся на 6 кластеров.

Сравнение результатов иерархических методов было проведено с результатом метода «К средних».

До применения метода «К-средних» был проведен факторный анализ, для объединения зависимых признаков к меньшему количеству независимых между собой факторов. Таким образом, 21 признак был объединен в 7 факторов методом «Варимакс»[5].

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

В мире научных открытий, 2010, №1 (07), Часть Таблица Объединение признаков исходя из факторного анализа № фактора Признаки округлая кромка (№5), орнамент на кромке (№9), диагональные гребенки (№15), лопатки по горизонтали (№16) ромбы в треугольнике (№13), прочерченная полукруглая линия (№21) прямой венчик (№1), загнутый венчик (№2), горизонтальная кромка (№4) скошенная внутрь кромка (№6), лопатки в треугольнике (№17), отступающая лопатка (№18) валик на сосуде (№3), скошенная наружу кромка (№7), заостренная кромка (№8), гребенка вертикальная (№14) ромбы в шахматном порядке (№10), треугольники по диагонали (№12) ромбы в ряд (№11), овалы в линию (№19), прочерченная линия (№20) На рисунке 1 изображен граф связей признаков, построенный по матрице корреляций с вычисленными коэффициентами Пирсона.

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

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

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

Таблица Распределение сосудов по группам методом «К-средних»

№ группы Сосуды по группам ЛС_С7, ЛС_С14, ЛС_С15, ЛС_С18, ЛС_С19, ЛС_С20, ЛС_С21, ЛС_С25, ЛС_С8, ЛС_С9, ЛС_С22, ЛС_С23, ЛС_С26, ЛС_С ЛС_С6, ЛС_С12, ЛС_С ЛС_С4, ЛС_С ЛС_С ЛС_С ЛС_С В мире научных открытий, 2010, №1 (07), Часть Результат кластеризации иерархическим методом помещен в таблицу 5.

Таблица Распределение сосудов по группам методом «Связь между группами»

№ группы Сосуды по группам ЛС_С7, ЛС_С14, ЛС_С15, ЛС_С18, ЛС_С19, ЛС_С20, ЛС_С21, ЛС_С25, ЛС_С ЛС_С2, ЛС_С8, ЛС_С9, ЛС_С22, ЛС_С ЛС_С4, ЛС_С17, ЛС_С26, ЛС_С ЛС_С6, ЛС_С ЛС_С ЛС_С Окончательным решение задачи кластеризации считаем распределение в таблице 4.

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

Наибольшей по количеству сосудов группе соответствуют признаки, присущие памятнику "Лузанова Сопка-2". В последних трех группах присутствуют признаки, которых нет на остальных сосудах, но на них много признаков из основной (многочисленной) группы, что означает, что не сосуд пришел из другой "культуры", а лишь орнаментальный признак.

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

Проанализируем следующий памятник «Ветка-2». Для этого памятника имеются данные по 133 сосудам с 38 признаками.

Анализ по определению количества кластеров для памятника «Ветка-2» проводился с помощью пакета SPSS 15.0 (табл. 2) по 5 методам с использованием 27 мер для анализа дихотомических данных.

При анализе результатов кластеризации выяснилось, что от количества сосудов не зависит работа методов в построении дендрограммы и разделении объектов на кластеры. Таким образом, также как и для памятника «Лузанова Сопка-2» оптимальным методом определения количества кластеров является метод «Связь между группами», по которому все сосуды делятся на 13 кластеров.

Сравнение результатов иерархического метода было проведено с результатом метода «К средних».

Окончательным решением задачи кластеризации является разбиение, полученное методом «К-средних» с предварительным корреляционным анализом признаков.

Наибольшей по количеству сосудов группе соответствуют признаки, присущие памятнику "Ветка-2". В группах 7-12 присутствуют признаки, которых нет на остальных сосудах, но на них много признаков из основной (многочисленной) группы. Чтобы проследить, существовал ли контакт и обмен между разными типами керамики памятников «Ветка-2», «Лузанова Сопка-2», «Бойсмана-2» и «Моряк-Рыболов», был проведен общий анализ артефактов этих памятников.

Анализ по определению количества кластеров для памятника «Ветка-2» (104 сосуда) и «Лузанова Сопка-2» (22 сосуда) проводился по 5 методам с использованием 27 мер для сосудов.

Наибольшим по количеству сосудов группам (1 и 2 группы) соответствуют признаки, присущие памятникам "Ветка-2" и «Лузанова Сопка-2». Из-за того, что большинство сосудов из памятника «Ветка-2», то признаки сосудов этого памятника подавляют признак «прочерченная линия», характерный для памятника «Лузанова Сопка-2». В группах 7- присутствуют признаки, которых нет на остальных сосудах, но на них много признаков из основной (многочисленной) группы.

Из-за малого количества данных для памятников «Моряк-Рыболов» (9 сосудов) и «Бойсмана-2» (7 сосудов) - большие расхождения в результатах иерархических и метода «К средних». Поэтому дальнейший анализ был проведен для объединения памятников.

В мире научных открытий, 2010, №1 (07), Часть Анализ проводился по 5 методам с использованием 27 мер иерархического анализа для памятников «Ветка-2» (104 сосуда), «Лузанова Сопка-2» (22 сосуда), «Бойсмана-2» (7 сосудов) и «Моряк-Рыболов» (9 сосудов) на данных 142 сосудов.

Оптимальным методом определения количества кластеров является метод «Связь между группами».

Сравнение результатов иерархических методов было проведено с результатом метода «К средних». Так как иерархический метод показал, что должно быть 8-9 кластеров, то неиерархическим анализом была произведена кластеризация для такого количества кластеров.

Качество разбиения лучше при 8 кластерах (табл. 6, табл. 7). %и составляет 92\% (табл. 39).

Анализируя результаты метода «К-средних», можно выделить признаки, присущие каждой группе сосудов.

Наибольшим по количеству сосудов группам (1 и 2) соответствуют признаки, присущие памятникам "Ветка-2", «Лузанова Сопка-2», «Бойсмана-2» и «Моряк-Рыболов». В группах 1-6 в табл. 7 для метода «К-средних» прослеживается связь между четырьмя памятниками по свойственным для них признакам.

Керамика памятников «Ветка-2» и «Лузанова Сопка-2» отличаются орнаментальными признаками. При добавлении новых признаков кластеризация меняется. Поэтому следует рассматривать устойчивость разбиения для одного числа признаков.

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

На основании такого допущения, качество разбиения для памятника «Ветка-2» при объединении памятников составляет 86% и 90% соответственно.

Качество разбиения для памятника «Лузанова Сопка-2» при объединении памятников составляет 91% и 82% соответственно.

Таблица Распределение сосудов по группам для всех четырех памятников методом «Связь между группами»

Сосуды по группам В_С5, В_С15, В_С22, В_С45, В_С47, В_С51, В_С61, В_С75, В_С79, В_С80, В_С90, В_С102, В_С116, В_С120, В_С133, В_С141, МР_С2, МР_С8, В_С2, В_С13, В_С18, В_С21, В_С23, В_С24, В_С27, В_С28, В_С38, В_С41, В_С49, В_С82, В_С100, В_С119, В_С145, В_С55, МР_С1, МР_С6, МР_С7, В_С10, В_С112, МР_С3, В_С17, В_С32, В_С26, В_С В_С1, В_С3, В_С4, В_С8, В_С11, В_С14, В_С19, В_С20, В_С29, В_С30, В_С33, В_С35, В_С37, В_С46, В_С48, В_С50, В_С56, В_С58, В_С59, В_С62, В_С63, В_С65, В_С69, В_С72, В_С73, В_С76, В_С84, В_С92, В_С98, В_С99, В_С110, В_С114, В_С115, В_С121, В_С122, МР_С4, МР_С5, В_С25, В_С66, ЛС_С6, В_С34, В_С67, В_С В_С12, В_С54, В_С142, ЛС_С1, ЛС_С8, ЛС_С13, ЛС_С14, ЛС_С15, ЛС_С18, ЛС_С19, ЛС_С20, ЛС_С21, ЛС_С22, ЛС_С23, ЛС_С25, Б_С3, Б_С4, Б_С5, Б_С6, Б_С7, МР_С9, В_С144, ЛС_С3, БС_С1, ЛС_С В_С42, В_С52, В_С64, В_С77, В_С85, В_С86, В_С87, В_С118, В_С139, В_С146, В_С147, ЛС_С26, ЛС_С28, Б_С2, ЛС_С4, ЛС_С9, ЛС_17, В_С В_С60, В_С95, В_С136, В_С151, ЛС_С В_С31, В_С81, ЛС_С В_С6, В_С В_С53, В_С В мире научных открытий, 2010, №1 (07), Часть Таблица Распределение сосудов по группам для всех четырех памятников методом «Связь между группами»

Сосуды по группам В_С1, В_С3, В_С4, В_С5, В_С8, В_С11, В_С14, В_С15, В_С19, В_С20, В_С22, В_С29, В_С30, В_С33, В_С35, В_С37, В_С42, В_С45, В_С46, В_С47, В_С48, В_С50, В_С51, В_С52, В_С53, В_С56, В_С58, В_С59, В_С61, В_С62, В_С63, В_С64, В_С65, В_С69, В_С72, В_С73, В_С75, В_С76, В_С77, В_С79, В_С80, В_С84, В_С85, В_С86, В_С87, В_С89, В_С90, В_С92, В_С98, В_С99, В_С102, В_С110, В_С114, В_С115, В_С116, В_С118, В_С120, В_С121, В_С122, В_С133, В_С136, В_С139, В_С141, В_С144, В_С146, В_С147, В_С151, ЛС_С7, ЛС_С26, ЛС_С28, Б_С2, МР_С2, МР_С4, МР_С5, МР_С8, В_С2, В_С12, В_С13, В_С18, В_С21, В_С23, В_С24, В_С27, В_С28, В_С38, В_С41, В_С49, В_С54, В_С67, В_С82, В_С100, В_С119, В_С142, В_С145, ЛС_С1, ЛС_С4, ЛС_С8, ЛС_С9, ЛС_С13, ЛС_С14, ЛС_С15, ЛС_17, ЛС_С18, ЛС_С19, ЛС_С20, ЛС_С21, ЛС_С22, ЛС_С23, ЛС_С25, Б_С3, Б_С4, Б_С5, Б_С6, Б_С7, МР_С В_С6, В_С10, В_С25, В_С31, В_С36, В_С66, В_С81, В_С112, ЛС_С6, ЛС_С12, МР_С В_С34, В_С55, В_С57, ЛС_С2, МР_С1, МР_С6, МР_С В_С17, В_С32, В_С60, В_С95, БС_С В_С83, ЛС_С В_С В_С Наиболее сложной процедурой для археолога является сопоставление (статистическое или интуитивное) двух или нескольких археологических комплексов. При интуитивном сравнении несколько расплывчато формулируется проблема значимости признаков, на основе которых осуществляется сопоставление. При статистическом сравнении учет сходства (или различия) идет, как правило, по всем признакам.

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ 1. Морева О.Л. Керамика бойсманской культуры (по материалам памятника Бойсмана-2) :

Автореф. дис.... канд. ист. наук. – Владивосток, 2005.

2. Молодин В.И. Самусьская культура в Верхнем Приобье. - Новосибирск: Наука. Сиб.

отд-ние,1989. - 168 с.

3. Наследов А. SPSS 15 профессиональный статистический анализ данных. - С-П., 2008.

4. Барсегян А.А., Куприянов М.С., Степаненко В.В. Технологии анализа данных: Data Mining, Visual Mining, Text Mining, OLAP. - 2-е изд., перераб. и доп. - С-П., 2008.

5. Ким Дж.-О. Факторный, дискриминантный и кластерный анализ. - М.: Финансы и статистика, 1989. - 215 с.: ил.

В мире научных открытий, 2010, №1 (07), Часть УДК 517.956. НЕКОТОРЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЭЛЛИПТИЧЕСКОГО ТИПА СО СМЕШАННЫМИ ГРАНИЧНЫМИ УСЛОВИЯМИ М.И. Сугаков, аспирант С.Р. Амироков, кандидат физико-математических наук Северо-Кавказский государственный технический университет Ставрополь, Россия На примере краевой задачи гидродинамики со смешанными условиями вдоль одной из границ показано применение приближённого метода средневзвешенного потенциала, проведено сравнение решения с аналитическим и численным.

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

Рис. 1. Геометрия задачи Требуется определить величину потока жидкости Q в пласте шириной l ( 0 x l ), высотой H (0 y H ). Жидкость на высоте H поступает через отверстие шириной l (0 x l1 ), а выходит через другое отверстие ширины l2 (l l2 x l ). Стенки пласта считаются непроницаемыми, поток образуется за счёт разности давлений между отверстиями, которые будем полагать постоянными и заранее известными.

Для решения задачи введём потенциал, который связан со скоростью потока соотношениями v = grad, divv = 0, так что = 0. (1) Таким образом, для отыскания в области G получается следующая краевая задача:

найти решение уравнения Лапласа (1) с граничными условиями = 0, (2) y OE В мире научных открытий, 2010, №1 (07), Часть = 0, (3) y BC = 1 = const, CD = 2 = const, (4) AB = = 0. (5) y y AO ED Вдоль стороны AD действуют смешанные граничные условия (3) и (4). Один из способов решения данной задачи, основанный на методе средневзвешенного потенциала (иначе известного как метод Хоу, см. [1, 3]), заключается в следующем.

Проведём разделение переменных по методу Фурье и учтём условия (2) и (5). В результате получим общий вид решения ( x, y ) = C 0 + C n cos n x ch n y, (6) n = n где n = ;

C0, C1,K – произвольные постоянные.

l Введём обозначение Cn = Q An, где Q – величина искомого потока, после чего (6) преобразуется к виду ( x, y ) = C0 + Q An cos n x ch n y. (7) n = Поток определяется как криволинейный интеграл (например, вдоль какого-либо из отверстий) от нормальной составляющей производной потенциала. В формулу для производной потенциала не войдёт постоянная C0, поэтому мы имеем право разделить все коэффициенты C n ряда в правой части выражения (6) на Q.

Примем значения потенциала при y = H на отрезках AB и CD в среднем равным 1 и 2, которые будем теперь обозначать 1* и 2 соответственно * заданным величинам l l = ( x, H )dx = 1*, (8) AB l ( x, H )dx = = * 2. (9) CD l2 l l Подставляя (7) в (8) и (9), получим алгебраическую систему относительно C0 и Q Q C0 + l S1 = 1, * (10) Q C + S = *, 0 l2 2 где S1 и S 2 обозначают следующие суммы S1 = An ch n H sin nl1, (11) n n = (1) n S 2 = An ch n H sin n l2. (12) n n= Чтобы отыскать неизвестные коэффициенты An, применим упрощающее предположение о том, что значения нормальных скоростей фильтрации вдоль отрезков AB и CD постоянны.

Из этого получаем следующее распределение нормальной скорости на границе AD В мире научных открытий, 2010, №1 (07), Часть Q l, при 0 x l1 ;

F ( x) = = 0, при l1 x l l2 ;

y y = H Q, при l l2 x l.

l nx Разложим F (x) в ряд Фурье по системе функций cos на отрезке [0, l ] l a = 0 + a n cos n x, F ( x) = (13) y y = H 2 n = 1 (1) n 2Q a0 = 0, a n = sin n l1 + sin n l2.

l n l1 l Дифференцирование (7) при y = H даёт формулу = Q An n cos n x sh n H. (14) y n = y=H cos n x, найдём Сравнивая (13) и (14), и пользуясь линейной независимостью функций 2 1 (1) l1 sin n l 2 l2 sin n l n An =.

l n2 l1l 2 sh n H Таким образом, числовые ряды S1 и S 2 принимают вид 2 1 cth n H ((1) n l1 sin n l2 l2 sin nl1 )sin nl1, S1 = 3 (15) l n =1 n l1l 2 1 cth n H ( ) 3 l l l1 sin nl2 (1) n l2 sin nl1 sin nl2.

S2 = (16) l n=1 n Нетрудно доказать абсолютную сходимость рядов (15) и (16). Если суммы известны, то величина потока находится по следующей формуле ( 1* )l1l * Q=. (17) S 2 l1 S1l Для расчёта потока требуется иметь оценку остаточных членов рядов S1 и S 2. Получить оценку можно воспользовавшись, например, признаком Дирихле сходимости рядов Абелева типа [2]. Оценка остаточных членов обоих рядов оказывается равной 4l 2 (l1 + l2 ) H rN cth.

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

1. Отобразим прямоугольную область G (рис. 1) на верхнюю полуплоскость (рис. 2).

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

В мире научных открытий, 2010, №1 (07), Часть Рис. 2. Преобразованная область Рис. 3. Область G, подготовленная для конформного отображения Найдем модуль эллиптического интеграла k 0 через отношение высоты прямоугольника к половине его ширины = 2 H l (см. [4]).

+ q k 0 = 4 =0, где q = e. (18) 1 + 2 q = 2. Пересчитаем координаты образов точек A, B, C и D по формуле 2z = sn K 0, k0, (19) l в которой z и – комплексные координаты точек до и после конформного преобразования, функция sn – эллиптический синус Якоби, K 0 = K( k0 ) – полный эллиптический интеграл Лежандра первого рода.

В случае, приведённом на рис. 3, координаты образов точек будут равны 2l l x1 = sn( K 0, k0 ) = 1, x2 = sn K 0 1, k0, l l 2l x3 = sn K 0, k0, x4 = sn(K 0, k 0 ) = 1.

l 3. Найдём приток по следующей формуле (её вывод можно найти в [3, стр. 47-49]).

K (k ) Q= 1 2, (20) K( k ) ( x3 x2 )( x4 x1 ) k=.

( x4 x2 )( x3 x1 ) Вычисление новых координат по формуле (19) осложняется при = 2 H l 1 6, что связано с особенностью эллиптического интеграла limK( x) =. В этом случае следует x В мире научных открытий, 2010, №1 (07), Часть развернуть прямоугольник AO* ED (рис. 3) так, чтобы сторона AO* лежала на оси Ox, а ось Oy делила сторону AO* пополам. При этом ход решения не изменится.

Во время расчётов следует иметь в виду, что функции эллиптических интегралов K(k ), работа которых основана на методе арифметико-геометрического среднего, могут давать неправильный результат вычислений в определённом диапазоне параметра. В частности, функции ellipke пакета MATLAB и EllipticK инструмента WolframAlpha основаны на этом алгоритме. Для проверки можно вычислять эллиптический интеграл как сумму ряда (см. [5]).

Сравнение вышеизложенных решений, т.е. решения методом средневзвешенного потенциала (СВП) и аналитического, а также решения, получаемого при помощи метода конечных элементов (МКЭ), показало приемлемую точность решения методом СВП при l1 + l2 l 2. Величины потока, находимые методом СВП, оказываются ниже вычисленных аналитически, что характерно для данного метода. Величины, получаемые МКЭ, также оказываются ниже точных значений при размерах сетки 3002600 элементов (в зависимости от размеров области).

Рис. 4. Зависимость потока от высоты прямоугольного пласта 1 = 4, 2 = 1, l = 10, l1 = 2, l2 = Рис. 5. Зависимость потока от суммарной длины отверстий 1 = 4, 2 = 1, l = 10, H = 4, l1 = l 2.

В мире научных открытий, 2010, №1 (07), Часть Все решения показывают линейную зависимость потока от разности потенциалов 1 2, о чём говорят также формулы (17) и (20). Наблюдается замедление роста потока при увеличении высоты H (рис. 4), при переходе H l, высота перестаёт оказывать существенное влияние на величину потока. Погрешность метода СВП растёт при увеличении l1 + l2 (рис. 5).

Рис. 6. Погрешность решения по методу СВП в процентах.

1 = 4, 2 = 1, l = 10, l1 = l 2.

Рис. 7. Точность решения МКЭ от числа конечных элементов N В целом, погрешность метода СВП уменьшается при увеличении H и растёт с увеличением l1 + l2. На рис. 6 показан график зависимости погрешности метода в процентах от высоты прямоугольного пласта и от длины отверстий l1 = l2. Отклонение результатов СВП от точных не превосходит 10–15% в случае l1 + l2 l 2.

Метод конечных элементов даёт заниженные значения потока в рассмотренной задаче.

Наблюдается рост точности решения с увеличением числа конечных элементов (рис. 7).

Решения методом конечных элементов получены с помощью COMSOL 3.4, тип уравнения – Laplace`s, настройки стандартные.

В мире научных открытий, 2010, №1 (07), Часть СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ 1. Фихманас Р.Ф., Фридберг П.Ш. Метод Хоу расчёта ёмкости тел и его связь с вариационными принципами // ЖТФ. – 1970. – Т.40. – вып.6. – С.1327–1328.

2. Признак Дирихле [Электронный ресурс] : Википедия – Свободная энциклопедия : [сайт].

URL: http://ru.wikipedia.org/wiki/Признак_Дирихле (дата обращения: 24.12.2009).

3. Иоссель Ю. Я., Кочанов Э. С., Струнский М. Г. Расчет электрической емкости. 2-е изд., перераб. и доп. СПб. : Энергоиздат. Ленингр. отд-ние, 1981. 288 с.

4. Лаврентьев М. А., Шабат Б. В. Методы теории функции комплексного переменного. – 4 е изд., перераб. и доп. М. : Наука, 1973. 749 с.

5. Двайт Г. Б. Таблицы интегралов и другие математические формулы / Г. Б. Двайт;

перевод с англ. Н. В. Леви;

под ред. К. А. Семендяева. 5-е изд. М. : Наука : Главная редакция физико-математической литературы, 1978. 224 с.

УДК 003.26.09:512. СИСТЕМЫ ШИФРОВАНИЯ ОСНОВАННЫЕ НА ЗАДАЧАХ ТЕОРИИ РЕШЕТОК В.С. Усатюк, аспирант О.В. Кузьмин, доктор физико-математических наук Братский государственный университет г. Братск, Россия В работе представлен обзор достижений динамично развивающейся отрасли криптографии, а именно шифрования, основанного на задачах теории решеток. Работа содержит необходимые базовые определения, описание основных задач теории решеток, а так же представлены основные преимущества этого класса криптографии - свойство криптостойкости по отношению к квантовым и молекулярным вычислителям и возможность реализации гомоморфного шифрования на основе идеальных решеток.

Ключевые слова: решетка, шифрование, хеш-функция, квантовая и молекулярная криптостойкость.

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

В свою очередь алгебры, основанные на молекулярных [1, с. 63] и квантовых вычислителях [2, с. 200] позволили реализовать алгоритмы расшифровки сообщений и поиск коллизии за полиномиальное время, для задач NP coNP(= P) класса. В результате возникла I необходимость в теоретических исследованиях и практической реализации нового поколения криптографических протоколов и примитивов - основанных на NP-полных задачах, не позволяющих реализовывать обращение таковых задач быстрее, чем с субэкспоненциальной сложностью [3].

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

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

Решетка – дискретная аддитивная подгруппа, заданная на множестве R n, т. е. решетку L можно представить как множество целочисленных линейно независимых базисных векторов n B = {b1,..., bn } R n, L = bi Z = {Bx : x Z n }, (рис. 1). У решетки может быть множество i = n a Z, (рис. 2).

базисов, L = i i = В мире научных открытий, 2010, №1 (07), Часть Рис. 1. Решетка с базисом {b1, b2 } B Рис. 2. Решетка с базисом {a1, a 2 } B На рисунках 3, 4 показаны фундаментальные параллелепипеды образованные базисами.

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

Рис. 3, 4. Фундаментальные параллелепипеды, образованные базисами Под кратчайшим вектором решетки будем понимать вектор с координатами 1 ( L) = min x y = min x (рис. 5). Тогда многомерным обобщением этого понятия x, yL, x y xL, x будет i (L) - ограниченное минимальным r, для которого размерность решетки внутри шара радиуса r больше либо равна k (рис. 6).

Рис. 6. Кратчайший базис решетки L в R Рис. 5. Кратчайший вектор В мире научных открытий, 2010, №1 (07), Часть Таким образом, познакомившись с основными определениями теории решеток, перечислим некоторые из задач этой теории активно применяемых в криптографии:

1. По базису решетки, найти кратчайший ненулевой вектор (shortest vector problem, SVP), (рис. 7);

2. По базису решетки, найти ненулевой вектор не превосходящий i (L) (shortest vector problem, SVP ), (рис. 8);

2 Рис. 7. Пример SVP-задачи в R Рис. 8. Пример SVP -задачи в R 3. По базису решетки, заданному вектору j, найти ближайший вектор b к вектору j (Closes Vector Problem, CVP), (рис. 9);

4. По базису решетки, заданному вектору j, найти вектор, находящийся на расстоянии l (Closes Vector Problem, CVP );

5. Найти линейно независимых векторов Bm в решетки, для которых m max Bxi n (Shortest Independent Vector Problem, SIVP), (рис. 10) i Рис. 9. Пример CVP -задачи в R 2 Рис. 10. Пример SIVP -задачи в R 6. Найти m линейно независимых векторов в базисе решетки Bxm, для которых max Bxi n (Shortest Independent Vector Problem, SIVP );

i 7. Поиск кратчайшего расстояния между векторами в базисе решетки;

по заданному базису ответить на вопрос, не превосходит ли кратчайший вектор норму N (Decisional SVP, GapSVP);

8. По базису решетки, заданному вектору j и 0 ответить на вопрос о существовании вектора v в решетке, близкого к вектору j с точностью до (Decisional CVP, GAPCVP);

В мире научных открытий, 2010, №1 (07), Часть 9. По базису решетки, в котором кратчайший вектор в k-раз меньше другого кратчайшего линейно независимого вектора, найти кратчайший вектор (Unique Shortest Vector Problem, uSVP), (рис. 11);

10. Дана решетка с минимальным расстоянием l (необязательно известным), по базису B и вектору j такому, что ( B, j ) l найти вектор в решетке (Bounded Distance Decoding, BDD), (рис. 12).

Рис. 11. Пример uSVP-задачи Рис. 12. Пример BDD-задачи Теория решеток считалась завершенной, будучи исследованной Лагранжем, Гауссом, Дирихле и другими выдающимися математиками. Не смотря на тот факт, что до 1996 г. оценки сложности отсутствовали и единственное, что было известно - CVP является NP-полной [4].

В 1996 г. венгерский математик-исследователь IBM Миклос Айтаи в своей работе [5] показал, что [6]:

­ возможно построить одностороннюю функцию на основе SVP-задачи;

более поздние исследователи улучшили результат до «односторонней функции с секретом» (trapdoor function, [7]) – вариантом односторонней функции, быстро обращаемой (по сравнению со скоростью получения образа функции) при наличии дополнительных сведений;

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

­ среди всего класса NP-задач, SVP-задача является самой сложной, т.е. является NP полной задачей.

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

На основе задач GapSVP и SIVP Айтаем в 1996 г. [5] были предложены методы реализации свободных от коллизий хеш-функций. Опишем эту хеш-функцию Айтая подробнее, так как остальные алгоритмы шифрования построены по аналогии.

Функция Айтая - это функция вида f a ( x ) = Ax mod q, где A Z q m и x {0,1}m.

n Например, при q = 10, n = 4, m = 7 :

В мире научных открытий, 2010, №1 (07), Часть 1 0 1 mod10 = (1 7 7 5).

f a ( x) = Ax mod q = 1 4 Параметры криптографии задаются из следующих соображений:

n - основной параметр, определяющий защищенность q = n (1), m = O (n log n ) n log 2 q, последнее обусловлено тем, что при nm задача обращения легко разрешима. Для n = 1024, q = 2 32, m = 65536. Т.е. функция Айтая f a (x ) - сжимает m-исходных бит в n log 2 q m, в данном случае 65536 в 32768 бит.

Покажем связь с теорией решеток: ядром множества A Z q m является решетка n L( A) = {z Z m : Az = 0(mod q)}. Тогда коллизия хеш-функции ( f a ( x ) = f a ( y ), x y ) станет вектором вида z = x y {1,0,1} : Az = Ax Ay = 0 mod q или же, zi L( A) с нормой = max zi = 1. Т.е. поиск коллизий хеш-функции Айтая f a (x ) соответствует решению z i SVP-задачи в решетке L.

Коллектив ученых Голдштейн-Голдвассер-Халеви (GGH) в 1997 [8] предложил вариант хеш-функции на основе псевдокуба, построенного на векторах некоторой решетки L.

Мисиансио и Рэджев [9], [10, сл. 56-60] предложили общий подход к шифрованию, основанный на добавлении шумов в решетку, что позволяет получить решетку, неотличимую от равномерного распределения. Затем, путем разбиения решетки на ячейки, построить отображение, позволяющее реализовать свободную от коллизий хеш-функцию и протокол ассиметричного шифрования. Эта концепция определила современное направление развития криптографии на основе теории решеток.

Циклическая решетка – решетка вида A = [ A(1) |... | A( m / n ) ], A( i ) Z q n, т.е. решетка, n характеризующаяся некоторой постоянной структурой, получаемой в результате перестановки элементов по некоторому правилу, например:

a1 i ) K a 2i ) ( ani ) ( ( 71 4 30 2 3 49 3 5 (i ) (i) a1 i ) ( K a3 1 2 3 3 7 1 44 0 2 35 9 3 a A = 2,A |A |A = i.

M O M M 43 7 13 4 0 21 5 9 (i ) (i) a ni) ( K a an 14 3 72 3 4 03 1 5 Крис Пеинкерт и Алон Розен в 2006 г. [11] предложили свой вариант хеш-функции, основанной на круговой общей SIVP-задаче на циклических решетках: заданный вектор определен целочисленным полиномом P ( a ) 0 mod(a n 1), необходимо найти множество или подмножество линейно независимых векторов с нормой пропорциональной величине нормы общих векторов полинома и решетки. Хеш-функция Пеинкерта-Розена обладает важными свойствами, которые выделяют ее среди всех остальных функций: линейной зависимостью длины образа хеш-функции от ее прообраза и линейным ростом сложности вычислений по времени.

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

­ система Ajtai-Dwork основанная на uSVP-задаче, с публичным ключом длины n 4 ;

­ система Goldreich-Goldwasser-Halevi (GGH) основанная на приближенной CVP- задаче, с публичным ключом длины n 2 ;

В мире научных открытий, 2010, №1 (07), Часть ­ система NTRU (Draft standard IEEE 1363.1, [12]) основанная на задаче свертки модулярных решеток (Convolution modular lattice, CML), с публичным ключом длины nlog n, ставшая стандартом шифрования.

Опишем алгоритм ассиметричного шифрования, реализующего цифровую подпись со ~ сложностью O ( n 2 ), размерами закрытого, открытого ключа и сертификата O ( n ) = m log q, основанный на циклических решетках.

Пусть имеется дайджест хэш-функции A = [ A(1) |... | A( m / n ) ] со сложностью O (n ) ;

X = ha ( x ) = A( i ) x,Y = ha ( y ) = A( i ) y ;

(i ) (i ) публичный ключ- закрытый ключ x = [ x,..., x ], x = [ y,..., y 1 (m / n) 1 (m / n) ].

Генерация подписи для n-битов данных m {0,1}n реализуется при помощи вычисления:

= ( 1,..., m / n ), где i = x ( i ) M + y ( i ), m1 L m m m1 L m3 m где M =.

M M M O m mn 1 L m1 n Проверка подписи будет заключаться в вычислении h A ( ) = XM + Y.

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

На конференции Еврокрипт 2006 [14] была экспериментально продемонстрирована уязвимость шифрования с установленными стандартом параметрами для систем шифрования GGН и NTRU. Была продемонстрирована атака на банковские смарт-карты и системы идентификации личности, защищенные криптографической системой NTRU.

Сложность решения задач теории решеток определяется выбором размерности и базиса решетки. Выбор большой размерности решетки увеличивает мощность ключевого пространства, но рост этого параметра затрудняется быстрым ростом объема данных, необходимых для хранения ключей и увеличением времени шифрования/дешифрования. Для каждой из систем о росте времени нужно говорить отдельно, в силу специфических свойств шифрования. Например, публичный ключ 1000-мерной решетки в системе Ajtai-Dwork’а займет 84 Гб, в GGH 290 Мб и 50 Мб для NTRU, при этом размер закрытого ключа значительно больше. Выбор базиса обоснован типом задачи, лежащей в основе шифрования.

Сравним системы ассиметричного шифрования NTRU, RSA, ECC (таб. 1). Размер ключа шифрования NTRU и рост сложности шифрования/дешифрования с ростом криптостойкости растет медленнее, чем у RSA. Рост сложности шифрования/дешифрования системы NTRU, растет медленнее, чем у криптографии на основе эллиптических кривых ECC.

Таблица I Сравнение ассиметричных систем шифрования класса NP coNP (RSA и ECC) и системы шифрования на основе модулярных решеток NTRU Размер открытого ключа в битах Мощность ключевого Время атаки в пространства в битах МИПС в год NTRU ECC RSA 80 2008 160 5 10 112 3033 224 3 10 128 3501 256 В мире научных открытий, 2010, №1 (07), Часть 22 160 4383 320 1,8 256 7690 521 МИПС - миллион целочисленных инструкций в год;

таблица составлена на основе сведений сообщества NTRU, стандарт IEEE 1363.1.

В июне 2009 года исследователь IBM Крейг Гентри [15] продемонстрировал реализацию гомоморфного шифрования на идеальных решетках для операций сложения и умножения.

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

Идеальная решетка – это решетка со свойствами идеала на некотором кольце чисел, т.е.

результат сложения и умножения векторов в такой решетке, так же принадлежит ей самой. Это позволяет использовать свойства кольца, вместо свойств аддитивной подгруппы. В работе [15] предлагается на основе полиномиального кольца R = Z ( x ) / f ( x ) и унитарных (приведенных) f ( x) x, deg( f ) = n J = a (x ) :

многочленов степени с идеалом {a ( x )b( x ) mod f ( x ) : b( x ) R} использовать в качестве базисов решетки элементы схемы Горнера, представленные в таблице 2.

Таблица Базисы идеальных решеток гомоморфного шифрования a (x ) a0 an a1 a2 … x a ( x ) mod f ( x ) a n1 f 0 a0 a n1 f1 a1 a n1 f 2 an 2 an 1 f n … … x n a a ( x ) mod f ( x ) Тогда аддитивная операция примет следующий вид: m + 2 v + j, где m = {0,1}k - k битное сообщение, v -случайный кратчайший вектор решетки, j J - случайный вектор из публичного ключа.

Мультипликативная операция примет вид:

( ( m1 + 2 v1 + j1 )( m2 + 2 v2 + j2 ) = m1 m2 + 2( m1v2 + m2 v1 + 2v1v2 ) + j, j J.

Параметрами шифрования будут: кольцо R;

базис BI «небольшой» идеальной решетки I ;

радиусы шифрования – окружность (сфера) радиуса в фундаментальном renc параллелепипеде, образованном базисом открытого ключа;

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

Открытым ключом будет базис B pk с векторами, многократно превышающими кратчайшие, закрытым ключом будет Bsk с векторами равными или близкими к базису «большой» идеальной решетки J : I + J R.

Операция шифрования: m = ( m + I ) I B( renc ), c = m mod B pk..

Операция расшифровки: m = ( c mod Bsk ) mod BI.

В мире научных открытий, 2010, №1 (07), Часть Сложение: c = c1 + c2 mod B pk, ( m1 + m2 ) Bsk.

Умножение: c = c1 c2 mod B pk, m1 m2 Bsk, где фундаментальный Bsk параллелепипед, построенный на базисных векторах скрытого ключа. Условия: ( m1 + m2 ) Bsk и ( m1 m2 ) Bsk - условия корректности расшифровки.

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ 1. Паун Г., Розенберг Г., Саломаа А. ДНК-компьютер. Новая парадигма вычислений: Пер. с англ. – М.:Мир, 2003. – 528 с.

2. Квантовый компьютер & квантовые вычисления. – Ижевск: Ижевская республиканская типография, 1999., 288 стр.

3. Shor P. Progress in quantum algorithms. Quantum Information Processing Vol. 3, Springer Netherlands, October 2004, pp. 5- 4. Boas. P. Another NP­complete problem and the complexity of computing short vectors in a lattice'', Tech. Report 81­04, Math Inst. Univ. Amsterdam, 1981.

5. Ajtai M. Generating Hard Instances of Lattice Problem. Proceeding of 28th ACM Symposium on Theory of Computing. Philadelphia: ACM Press, 1996, pp. 99- 6. Шокуров А.В., Кузюрин Н.Н., Фомин С.А. Курс лекций «Решетки, алгоритмы и современная криптография» [Электронный ресурс] - 2008. -127 стр. - Режим доступа:

http://discopal.ispras.ru/ru.lectures-lattice-based-cryptography.htm 7. Impagliazzo R., A personal view of average-case complexity. Proceeding of 10th IEEE Annual Conference on Structure in Complexity Theory, 1995, pp. 134- 8. Goldreich O., Goldwasser S., and Halevi S. Public-key cryptosystems from lattice reduction problems. In Proc. of Crypto ’97, volume 1294 of LNCS, IACR, Springer-Verlag, 1997, pp. 112– 9. Micciancio, Regev O., Worst-case to average-case reductions based on Gaussian measures.

Foundations of Computer Science, Proceedings. 45th Annual IEEE Symposium on Volume Issue, 17 19 Oct. 2004, pp. 372 – 10. Николенко С. Презентация к курсу лекций по криптографии. «5. Криптография и решетки» ресурс] сл. Режим доступа:

[Электронный – 2008. - 63 http://logic.pdmi.ras.ru/~sergey/index.php?page=cscryp 11. Peikert C., Rosen A. Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices. [Электронный ресурс] - 2006. – 20 стр. - Режим доступа:

http://www.cc.gatech.edu/~cpeikert/pubs/cyclic-crh.pdf 12. Hoffstein J., Pipher J., Silverman J.H. NTRU: a ring based public key cryptosystem. In Proc. of ANTS III, volume 1423 of LNCS, Springer-Verlag, 1998, pp. 267– 13. Wang Y. Abuses of Ajtai-Dwork Cryptosystem. [Электронный ресурс] - 2007. – 10 стр. Режим доступа: http://cs.uwm.edu/~wang/papers/ abusecryp.ps.gz 14. Queng P., Regev O. Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures.

Advances in Cryptology - Proceedings of EUROCRYPT 2006, Volume 4004, Springer, 2006, pp. 215 15. Gentry C. Fully homomorphic encryption using ideal lattices. Annual ACM Symposium on Theory of Computing. Proceedings of the 41st annual ACM symposium on Theory of computing. 2009, pp. 169- В мире научных открытий, 2010, №1 (07), Часть ГРНТИ 28 КИБЕРНЕТИКА УДК 004. УСКОРЕНИЕ РАЗРАБОТКИ ЭКСПЕРТНЫХ СИСТЕМ С ПОМОЩЬЮ ОБОЛОЧЕК А.Б. Зудов, студент Пензенский Государственный Университет г. Пенза, Россия В данной работе рассматривается процесс разработки экспертных систем на Прологе и способы его ускорения.

Ключевые слова: экспертная система, язык Пролог, оболочка, эксперт, эвристика, коэффициент определённости.

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

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

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

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

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

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

В некоторых случаях оба этапа можно ускорить.

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

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

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

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

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

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

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

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

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

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

Так как данная система разрабатывалась для примера, а не для коммерческого использования, на неё были наложены некоторые ограничения, воплотившиеся в её архитектуре. Каждый рецепт имеет номер, текст рецепта и список названий, в рецепт входят несколько ингредиентов, каждый из которых тоже имеет номер и несколько названий, и некоторые рецепты и ингредиенты сгруппированы, то есть входят в список, связанный с какой либо группой (для рецептов это могут быть «Боулы», «Фиксы», а для ингредиентов – «Сладкое», «Алкоголь»).

У системы четыре основных функции:

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

2) найти все напитки, которые можно приготовить из заданных компонентов;

3) найти все напитки, в состав которых входит указанное;

4) тест на выбор напитка.

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

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

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

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

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

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

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

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

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

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

В мире научных открытий, 2010, №1 (07), Часть СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ 1. Марселлус, Д. Программирование экспертных систем на Турбо Прологе: Пер. с англ. / Предисл. С. В. Трубицына. – М.: Финансы и статистика, 1994. 256 с.

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

(Московский инженерно- физический институт) Институт Актуального Образования «ЮрИнфоР-МГУ»

г. Москва, Россия В работе рассматриваются вопросы моделирования предметных областей обучающих систем на примере правовых деловых игр. Выделяются особенности предметной области, требующие настройки семантики средств моделирования. Предлагается концепция предметно-ориентированных механизмов наследования и подходы к их погружению в аппликативные вычислительные системы (АВС). В качестве общей основы описания семантики предметно-ориентированных механизмов наследования предлагается подход на основе теории категорий. Описан подход и компоненты реализации инструментальных средств с настраиваемой семантикой. Работа поддержана грантами РФФИ 07-07-00298, 09 07-00259а.

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

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

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

(2) пресыщенных и (3) динамически меняющихся оценок.

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

Особенности управления семантикой деловых игр проявляются на всех уровнях проектирования, начиная с лингвистического [4]. Необходимость использования средств настройки семантики на этом уровне предопределяется принципиальной открытостью языка системы, а также требованиями её последующего сопровождения. В юридических приложениях выбранная ПО, как правило, оказывается описанной в рамках различных «систем терминов» различными уполномоченными субъектами правоприменительной деятельности, споры между гражданами и госорганами, споры между юридическими лицами и т.д. Зачастую в основе этих споров лежат различные подходы к описанию юридически значимых обстоятельств и оценка юридических фактов, в том числе возникающие из-за различия в терминологических базисах. Так, известны споры между экономистами и юристами, налоговыми органами, гражданами и прочими субъектами, применяющими налоговое право и различным образом трактующими налоговозначимые элементы описания ПО. В силу специфики ПО большинство таких споров выходит за рамки доктринальных и имеет существенное практическое значение.

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

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

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

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

Пример 1. Рассмотрим аппликацию концептуальных единиц x (функции) и y (аргумента), которую будем обозначать как xy. Предположим, что предметно-ориентированная специфика учёта контекста для выбранной ПО проявляется в том, что функция x оказывается независимой от контекста z, который должен учитываться только при вычислении аргумента y. Тогда семантическое уравнение, отражающее эту особенность ПО, будет выглядеть как В мире научных открытий, 2010, №1 (07), Часть [xy] z = x (yz), и семантическое отображение может быть выражено в виде комбинатора композиции B xyz = x (yz).

Пример 2. Пусть теперь в условиях предыдущего примера контекст перед продолжением вычисления должен быть модифицирован с использованием некоторой функции. Тогда соответствующее семантическое отображение уже не может быть выражено в виде комбинатора B и требует некоторого другого комбинатора B, имеющего комбинаторную характеристику B xyz = x (y ( z)).

Используя общие принципы аппликативных вычислительных систем (принцип бесконечного свёртывания [2, 7]), представим B, в свою очередь, в виде аппликации B = F для некоторого F. Тогда имеем F xyz = x (y ( z)) и F xyz = x (y ( z)) = x (Byz) = Bx (By) z = Bx (CBy)z = B (Bx) (CB) yz = = CB (CB) (Bx) yz = B (CB (CB)) B xyz = CBB (CB (CB)) xyz = = B (CBB) (CB) (CB) xyz = B (B (CBB) (CB)) (CB) xyz, где C xyz = xzy. Таким образом, F = B (B (CBB) (CB)) (CB).

Полученное выражение как раз и определяет предметно-ориентированный способ манипулирования контекстом. Отметим, что комбинатор C xyz = xzy = = (xz)y определяет зависимость функции от контекста и в этом смысле может рассматриваться как механизм специализации функции в заданной вычислительной среде.

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

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

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

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

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

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

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

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

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



Pages:   || 2 | 3 | 4 | 5 |   ...   | 9 |
 










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

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