Научные проблемы Интернета

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Научные проблемы Интернета

Научные проблемы Интернета

УО «БГУИР»

кафедра информационных технологий автоматизированных систем

РЕФЕРАТ

на тему:

«Научные проблемы Интернета»

МИНСК, 2008

Научные проблемы Интернета группируются вокруг следующих задач:

· Защита информации

· Сжатие информации

· Поиск информации

· Распознавание информационных объектов (текста и образов)

· Прогнозирование временных рядов

· Классификация документов

· Выбор и оценка многокритериальных альтернатив

· Принятие решений и логический вывод и др.

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

1 Защита информации

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

1. В шифровании основную роль играет не алгоритм, а ключ.

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

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

где e и m являются открытыми числами (известны всем абонентам сети).

Требуем, чтобы e и m были взаимно простыми числами (т.е. не числами общих делителей, кроме 1, причем ).

Оказывается, что зная y, e и m, найти x - сложнейшая математическая задача. Пока же продемонстрируем, как найти y по x, e, m.

Операция

находит целочисленный остаток a от деления b на m. Например,

2 = 17 mod 5

или

1 = 41 mod 8.

Но пусть требуется найти

630 mod 18 = ?

Это сделать посложнее. Мно записать

630 = 2*315 = 2*5*63 = 2*5*7*9 = 63*10.

Теперь можно использовать правило разложения на множители

.

В самом деле, пусть

,

,

.

Тогда

.

Последняя сумма дает остаток от деления на m, равный . Но , . Поэтому

.

Теперь нетрудно это правило применить, скажем, к

713 mod 8 = ?

Запишем

.

Имеем . Поэтому .

Обратимся теперь к формуле (6.16).

Пусть , , .

Найдем

.

Итак, . Это значение и будет передано по сети вместо x.

Теперь рассмотрим, как восстановить x по y, m, e. Для этой цели нужно найти число d, удовлетворяющее условию

где - значение функции Эйлера от числа m. Функция Эйлера вычисляется сравнительно просто. Так,

Если p простое число и r - целое, то

Формул (1.4) и (1.5) достаточно для того, чтобы найти функцию Эйлера для любого целого положительного числа. В нашем случае получаем:

.

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

Пример. . Все четыре числа: 1, 2, 3, 4 взаимно просты с m.

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

Итак, в нашем примере уравнение такое:

Уравнение (1.6) можно переписать следующим известным образом:

В (1.7) r и d неизвестные целые числа. Представим (1.7) в виде системы двух линейных неравенств.

,

,

или, что эквивалентно:

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

, .

Отсюда легко получить отсекающее неравенство:

Здесь z - новая целочисленная переменная. Заметим, что переход от (a) к (b) в (1.9) правомерен, так как r , d, z - целочисленны.

Выполним подстановку (3.9) в систему (1.8). Получим новую систему:

Обратим внимание на следующее принципиальное обстоятельство. В сравнении с (1.8) значение минимального коэффициента понизилось. Этот факт можно строго обосновать. Следовательно, весь процесс должен закончиться рано или поздно одним из двух результатов:

1) минимальный коэффициент по модулю станет равным 1 (как в (1.10)); будет получена система вида

,

,

где a и b - взаимно просты (в этом случае нет решения в целых числах).

В первом случае процесс решения завершен. Получаем из (1.10) подстановку для d:

Тогда из (1.9) найдем:

Итак, формулы (1.11) и (1.12) и дают нам итоговые подстановки для d и r из (1.7). Например, пусть . Тогда , . Возьмем именно это значение для минимального d.

Итак, мы подошли к решающему моменту: наш секретный ключ . Получили число , , .Восстанавливаем x по формуле:

Итак, .

Все сошлось. Возьмем, например, . Тогда , :

(ответ тот же).

Таким образом, не имеет значения, какое z брать для получения d.

Метод RSA мы завершим следующим замечанием.

Метод RSA вообще говоря требует, чтобы m было большим простым числом. Для установления факта, что m - простое, можно использовать малую теорему Ферма:

В (1.14) a и p должны быть взаимно просты, а p - простое число.

Пример.

, :

.

,: .

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

Электронная подпись. Принцип электронной подписи легко выводится из алгоритма RSA. Пусть нужно подписать текст T. Этот текст нудно «свернуть» в некое число y. Для свертки используют алгоритм хэширования. Теперь из уравнения (1.13) на основании секретного ключа получают подпись X. Число X и возвращается вместе с T и y в качестве подписи в документу Т. Не зная секретного ключа d (заменяющего фамилию), нельзя найти X. Проверяющий легко проверит (1.1), чтобы удостовериться, что X и y соответствуют друг другу. Заметим, что кто-либо может перехватить документ и подписать его своей подписью, если ему известно преобразование (1.13). Поэтому принятый «подделанный» документ должен быть «застрахован».

Для этого используется число e - открытый ключ подписавшего документ. Теперь очень легко проверить соотношение:

.

Подобрать секретный ключ d к открытому ключу e практически невозможно.

Метод Диффи-Хеллмана.

Метод Диффи и Хеллмана является двухключевым. Каждый абонент в сети имеет два ключа: один секретный - , второй открытый, вычисляемый по формуле

,

где p - большое простое число (взаимно простое с ); .

Число выбирается так, чтобы числа , , …, по модулю p давали некоторую перестановку чисел {1, 2, …, p-1}. Число называется первообразным корнем p. Все абоненты публикуют свои открытые ключи . Допустим, абоненты A и B хотят передать друг другу информацию. Тогда первый из них, например A, берет открытый ключ абонента B и вычисляет

.

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

Алгоритм DES. Алгоритм DES (description encryption system) состоит в последовательности чередующихся операций подстановки и перемешивания. Алгоритм DES использует секретный ключ K. Пусть, например, блок данных есть , а ключ .

Подстановка есть сложение по модулю 2:

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

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

Здесь - псевдослучайное число, порожденное на шаге i. первоначально полагают, например, . В качестве константы C примем

где K - секретный ключ. Величина M как правило равна ; величина n равна числу разрядов генерируемого псевдослучайного числа. Например, пусть , , , , :

,

,

,

,

и т.д.

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

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

2. Сжатие информации

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

010'000'101'000'101'111'001'011

Рис. 1.13.

Упорядочим комбинации по частоте встречаемости (рис. 1.13b). Теперь «объединим» две последние комбинации на рис. 1.13b в одну и все комбинации снова переупорядочим по убыванию частоты встречаемости (рис. 1.14)

`001-011' - 2

000 - 2

101 - 2

010 - 1

111 - 1

Рис. 3.14.

Теперь снова объединим две последние комбинации в одну и проведем очередное упорядочение (рис. 1.15)

`010-111' - 2

`001-011' - 2

000 - 2

101 - 2

Рис. 1.15.

Дальнейший процесс объединения комбинаций выполним по аналогии (рис. 1.16, 1.17)

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

Рис. 1.18.

Для полученного дерева выполним движение с корневой вершины к исходным тройкам. При выходе из любого узла помечаем одно из двух ребер «1», а другое - «0» (рис. 1.18). Итак, запомним, что разметка выполняется при движении справа на лево по построенному дереву. Теперь новый код для любой из исходных троек получаем как комбинацию, сопоставляемую пути из корня в данную вершину. Получаем следующее соответствие исходных троек и новых комбинаций:

000 - 11

101 - 10

010 - 001

111 - 010

001 - 001

011 - 000

С учетом нового способа кодировки исходная последовательность (1.17) может быть переписана таким образом:

Длина последовательности (3.18) сократилась в сравнении с длиной (1.17) с 24 бит до 20 бит. Основной принцип кодирования Хаффмана состоит в том, что часто встречаемые комбинации кодируются более короткими последовательностями. Таким образом, общая длина последовательности оценивается как

где - число битов в i-ой комбинации,

- относительная частота встречаемости i-ой комбинации.

Было замечено, хотя это и не обязательно верно во всех случаях, что длина кода Хаффмана комбинации , как правило, не превосходит величину (- ). Так, в нашем примере относительная частота комбинации 000 составляет . Ее код Хаффмана есть 11 (длина этого кода равна 2). Имеем

(что справедливо).

Таким образом, при кодировании Хаффмана результирующую длину кода можно ориентированно записать в виде

Кодирование Хаффмана модно применять повторно.

Арифметическое кодирование

Относительная частота символов:

, , .

При арифметическом кодировании последовательность (1.21) заменяется одним единственным числом. Для получения этого числа разобьем интервал [0,1] на подинтервалы:

Заметим, что длина каждого подинтервала соответствует относительной частоте соответствующего символа. Нетрудно сообразить, что первый подинтервал [0; 0,25] соответствует ; подинтервал (0,25; 0,75] - символу и (0,75; 1] - символу . В последовательности (3.22) первый символ . Ему соответствует интервал [0; 0,25]. Поэтому выбираем этот подинтервал и делим его опять согласно относительным частотам символов:

Следующий символ - . Ему соответствует интервал (0,0625; 0,1875]. Делим его на подинтервалы:

Следующий символ - . Выбираем второй подинтервал (0,09375; 0,15625]. Делим его на три подинтервала соответственно частотам символов:

Наконец, последний символ - . Ему соответствует третий интервал. Поэтому в качестве окончательного кода для последовательности (1.21) можно указать любое число из интервала [0,140625; 0,15625]. Например, возьмем 0,15. Итак, последовательность (1.21) кодируется числом 0.15.

Чтобы восстановить исходную последовательность, нужно действовать таким образом. Согласно частотам символов составляем исходное разбиение (1.22). Видим, что наш код 0,15 попадает в первый подинтервал [0; 0,25]. Значит первый символ - . Далее разбиваем интервал [0; 0,25] на три подинтервала (1.23) и смотрим, к какому из них принадлежит наш код 0,15. Теперь этот второй подинтервал, поэтому следующий символ . Далее из представления (1.24) снова выбираем второй подинтервал и символ . Наконец, из (1.25) выбираем символ .

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

Пусть в базе данных имеются спецификации текстов документов I1, I2,...,In, на входе системы имеется спецификация документа Х = (х1, х2, ...,хm). Требуется установить, к какому классу документов I1, I2,...,In относится Х.

Задачу будем решать при следующих условиях:

Параметры х1, х2, ...,хm задают частоты встречаемости термов в тексте. Аналогичным образом, спецификации представлены векторами частот встречаемости термов в текстах-шаблонах. Под термом понимается ключевое слово текста.

Известны весовые оценки значимости термов для соответствующих документов.

В результате будут вычислены некоторые оценки 1, 2, ...,n, определяющие систему предпочтений в установлении документа-шаблона, к которому принадлежит текст Х, при этом i =1 и если ps, то объективно принадлежность Х к Ip оценивается выше, чем к Is.

Описание проблемы и этапов ее решения

Допустим, что в силу общности или пересечения тем документов может возникнуть n кластеров (доменов, зон) с различной степенью (оценки) принадлежности к ним рассматриваемого документа Х; Пусть P(i х) - условная вероятность того, что наблюдаемый вектор х относится к домену i. В силу теоремы Байеса получим:

, (1.32)

где - вероятность фактического наблюдения вектора х с данными значениями частот встречаемости ключевых слов (термов);

- априорная вероятность того, что документ относится к домену i,

- вероятность того, что домен i мог привести к появлению вектора х;

i - идентификатор домена.

Рассматриваются следующие домены:

0 - ни один из шаблонов-документов не является владельцем Х;

1 - 1-й источник является владельцем Х, остальные - нет;

m - m-й источник является владельцем Х, остальные - нет;

m+1 - 1-й и 2-й источники в совокупности могут быть владельцами Х, остальные нет;

n - все n могут быть в совокупности владельцами Х.

Введем штрафную оценку

, (1.33)

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

С учетом (1.32) перепишем (1.33) в виде

Теперь, приняв Lkk =0 и Lij = Lji =1 (для всех i, j, i j), получим окончательно

(1.34)

Формула (1.34) служит основой для принятия решений.

Введя соотношение

, (1.35)

можно утверждать, что наименьшему значению i будет соответствовать документ с наименьшей оценкой возможности быть владельцем Х.

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

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

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

Таким образом, методика расчетов сводится к определению членов формулы (1.34). Для определения множителей P(i ) используется техника многокритериальной оценки на основе процедуры Саати, где в качестве альтернатив рассматриваются домены i , а критериями являются факторы, обусловливающие априорные значения P(i ). Для оценки значений P(x|i ) проводится серия вычислительных экспериментов, целью которых является получение математического ожидания и среднеквадратического отклонения частот встречаемости термов в домене i.

Последующее изложение раскрывает существо указанной методики и ее теоретико-практическое наполнение.

Оценка - априорной вероятности того, что владельцем документа является домен i

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

Значения dij частных функций полезности, присваиваемые экспертами каждому домену, могут располагаться в диапазоне [0, 1]. Чем dij ближе к единице, тем, по мнению эксперта, вероятнее соответствие факта принадлежности j -го ключевого слова i- му домену.

Для выявления возможного домена - владельца выбраны следующие критерии:

Т1 - степень соответствия входной спецификации тематике i -го шаблона-документа,

Т2 - распространенность тематики;

Т3 - цитируемость документов по тематике за последний месяц;

Т4 - степень общности тематики (широта тематики).

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

Для каждой строки находим

( 1.36 )

Откуда

( 1.37 )

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

( 1.38 )

где

Обобщенную оценку вероятности владельца документа Ii можно вычислить по формуле:

( 1.39 )

где p- количество обобщаемых признаков;

dij- частные функции полезности i-го объекта по j-му критерию;

j - статистический вес (важность) j-го критерия ( 0 j 1).

Величины q(...) используются следующим образом. Находим, например,P(я ) - оценку априорной вероятности того, что владельцами являются домены 1, 2 , а остальные три источника - 3,4,5,6 - нет:

P(R ) = q(1)* q(2)*(1- q(3))*(1- q(4))*(1- q(5)) *(1- q(6)).

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

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

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

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

- ( *) в группу входит столько координат, сколько вершин в фундаментальном симплексе;

- ( **) число уровней варьирования каждого фактора обозначается S и называется модулем;

- (***) каждая последующая группа координат получается прибавлением единицы к младшему разряду по модулю;

- (****) первая ненулевая координата не может быть больше единицы.

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

N = Sn , ( 1.40 )

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

F =(S n -1)/(S-1) ( 1.41 )

где S - число уровней варьирования;

n - число вершин фундаментального симплекса.

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

Правила составления линейно независимых векторов:

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

- в первом столбце элементы поля Галуа, численно равные уровням варьирования факторов, перечисляются по порядку столько раз, сколько уровней варьирования, т.е. число элементов должно быть (0,1,..,S)S;

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

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

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

Определение векторов mi оценок достоверности владельца шаблона Ii

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

Оценка , вероятности того, что владельцем входного документа является шаблон Ii

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

( 1.42 )

где: mi - вектор математических ожиданий частот встречаемости термов в документа, порождаемых от источника Ii,

m - размерность вектора х

ci - ковариационная матрица векторов частот термов,

ci-1 - обратная матрица ci,

- определитель матрицы сi

Для определения элементов ковариационной матрицы используется соотношение:

( 1.43 )

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

Расстоянием между двумя документами назовем величину d(,) (,):

(1.44)

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

На основании этих данных строится 0,1 - матрица В = [bjj], такая, что bij = 1 в том и только в том случае, когда расстояние dij между документами i и j не превосходит d, и bij = 0 в противном случае. Каждому документу присвоим вес Сi , отражающий его типичность для раскрываемой в нем темы.

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

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

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

Литература

1. Успенский И. Интернет как инструмент маркетинга. BHV, С-т Петербург, 256с., 2002. .

2. Меградж З. Разработка приложений для электронной коммерции на ORACLE и JAVA. Вильямс, 2000, 328с.

3. Пирогов В.П. MS SQL Server 2000. Управление и программирование. - СПб. БХВ.-2005,-600с.

4. Холл М., Браун Л. Программирование для WEB. Вильямс, 2002, - 1280с.