Учебная работа. Реферат: Научные проблемы Интернета

Учебная работа. Реферат: Научные проблемы Интернета

УО «БГУИР»

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

РЕФЕРАТ

на тему:

«Научные трудности Веба»

МИНСК, 2008

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

· защита инфы

· Сжатие инфы

· Поиск инфы

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

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

· Систематизация документов

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

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

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

1
защита инфы

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

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

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

метод
RSA. Пусть нужно передать по полосы связи числа
(разглядим тут лишь целые положительные числа). Заместо числа
передают число
, вычисляемое по формуле

,
(1.1)

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

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

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

Операция

(1.2)

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

2 = 17 mod 5

либо

1 = 41 mod 8.

Но пусть требуется отыскать

630 mod 18 = ?

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

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

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

.

По правде, пусть

,

,

.

Тогда

.

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

.

сейчас несложно это правило применить, скажем, к

713
mod 8 = ?

Запишем

.

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

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

Пусть , , .

Найдем

.

Итак, . Это x
.

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

,
(1.3)

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

.
(1.4)

Если
обычное число и
– целое, то

.
(1.5)

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

.

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

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

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

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

.
(1.6)

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

.
(1.7)

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

,

,

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

,

.

(1.8)

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

, .

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

(a) ,

(b) ,

(c) .

(1.9)

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

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

,

.

(1.10)

Обратим внимание на последующее принципное событие. В сопоставлении с (1.8) процесс должен окончиться рано либо поздно одним из 2-ух результатов:

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

,

,

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

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

.
(1.11)

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

.
(1.12)

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

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

.
(1.13)

Итак, .

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

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

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

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

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

.
(1.14)

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

Пример
.

, :

.

,:.

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

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

Для этого употребляется число
– открытый ключ подписавшего документ. Сейчас весьма просто проверить соотношение:

.

Подобрать скрытый ключ
к открытому ключу
фактически нереально.

способ Диффи-Хеллмана
.

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

,

где
– огромное обычное число (взаимно обычное с ); .

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

.

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

метод
DES. Метод DES (descriptionencryptionsystem) состоит в последовательности чередующихся операций подстановки и перемешивания. метод DES употребляет скрытый ключ
. Пусть, к примеру, блок данных есть , а ключ .

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

10010011

11001011

01011000

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

01011000

11001011

10010011

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

.
(1.15)

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

,
(1.16)

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

,

,

,

,

и т.д.

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

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

2. Сжатие инфы

Сжатие по способу Д. Хаффмана

Способ сжатия Хаффмана является одним из наилучших методов сжатия инфы. Данный способ мы изложим на последующем примере. Пусть дана подлежащая сжатию последовательность из «0» и «1»:

010000101000101111001011.
(1.17)

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

010’000’101’000’101’111’001’011

010 – 1

000 – 2

101 – 2

111 – 1

001 – 1

011 – 1

a)

000 – 2

101 – 2

010 – 1

111 – 1

001 – 1

011 – 1

b)

Рис. 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)

‘000-101’ – 2

‘010-111’ – 2

‘001-011’ – 2

Рис. 3.16.

‘010-111-001-011’ – 4

‘000-101’ – 4

Рис. 3.17.

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

Рис. 1.18.

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

000 – 11

101 – 10

010 – 001

111 – 010

001 – 001

011 – 000

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

01111101110010001000.
(1.18)

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

,
(1.19)

где – число битов в
-ой композиции,

– относительная частота встречаемости
-ой композиции.

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

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

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

.
(1.20)

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

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

Пусть имеется последовательность .
(1.21)

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

, , .

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

[0; 0,25], (0,25; 0,75], (0,75; 1].
(1.22)

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

[0; 0,0625), [0,0625; 0,1875), [0,1875; 0,25].
(1.23)

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

[0,0625; 0,09375), [0,09375; 0,15625), [0,15625; 0,1875].
(1.24)

Последующий знак – . Избираем 2-ой подинтервал (0,09375; 0,15625]. Делим его на три подинтервала соответственно частотам знаков:

[0,09375; 0,109375), [0,109375; 0,140625), [0,140625; 0,15625].
(1.25)

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

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

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

Сжатие графических файлов

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

.

Возьмем матрицу преобразования:

.
(1.26)

Поначалу найдем по правилам матричной алгебры произведение

,

Потом

.
(1.27)

Получим

.

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

.

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

.
(1.28)

и, аналогично,

.
(1.29)

При помощи (3.28), (3.29) получим восстановленную приближенную матрицу начальных данных:

.

Опосля квантования получим

.

Эта крайняя матрица весьма близка к начальной матрице
(!).

До этого всего, заметим, что матрица преобразования
обязана строится особым образом. Во-1-х, она обязана быть ортогональной, что значит, что векторное произведение всех ее 2-ух строк либо столбцов равно 0 (а это значит, что строчки и столбцы матрицы не зависимы и, как следует, определитель матрицы отличен от 0). Во-2-х, матрица
подбирается так, что сумма частей лишь в первой строке и в первом столбце максимальны; в других строчках и столбцах суммы частей равны либо близки к 0.

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

.
(1.30)

В (3.30) – x
и столбце
квадратной матрицы пикселей размеров ;

Матрица одномерного DCT-преобразования употребляет расчетную формулу

.
(1.31)

Заметим, что величины

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

1
1
1
1
1
1
1
1

0,981
0,831
0,556
0,195
-0,195
-0,556
-0,831
-0,981

0,924
0,383
-0,383
-0,924
-0,924
-0,383
0,383
0,924

0,831
-0,195
-0,981
-0,556
0,556
0,981
0,195
-0,831

0,707
-0,707
-0,707
0,707
0,707
-0,707
-0,707
0,707

0,556
-0,981
0,195
0,831
-0,831
-0,195
0,981
-0,556

0,383
-0,924
0,924
-0,383
-0,383
0,924
-0,924
0,383

0,195
-0,556
0,831
-0,981
0,981
-0,831
0,556
-0,195

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

В jpeg употребляется цветовая модель YCrCb, где Y передает светимость пикселя. Преобразование DCT производится раздельно к светимости Y, и раздельно к матрице, кодирующей хроматические числа Cr и Cb. К светимости Y применяется одномерное DCT преобразование. Для составляющие <Cr, Cb> производится разбиение изображения на матрицы пикселей . К каждой из таковых матриц применяется двумерное DCT-преобразование. Таковым образом, производится сжатие с потерей инфы.

Сокращение jpeg происходит от слов JointPhotographicExpertGroup – совместная группа по фото. Проект jpeg стал эталоном в 1991г. – принят интернациональной организацией эталонов ISO.

3.
систематизация документов

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

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

задачка систематизации и идентификации документов

Пусть в базе данных имеются спецификации текстов документов I1
, I2
,…,In


, на входе системы имеется спецификация документа Х = (х1
, х2
, …,хm
)

. Требуется установить, к какому классу документов I1
, I2
,…,In


относится

.

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

· характеристики х1
, х2
, …,хm


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

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

В итоге будут вычислены некие оценки

1






2






n


, определяющие систему предпочтений в установлении документа-шаблона, к которому принадлежит текст

, при всем этом



i




и если

p






s


, то беспристрастно принадлежность

Ip


оцениваетсявыше, чем к Is


.

Описание трудности и шагов ее решения

Допустим, что в силу общности либо пересечения тем документов может появиться

кластеров (доменов, зон) с различной степенью (оценки) принадлежности к ним рассматриваемого документа

; Пусть





i






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

относится к домену

i


. В силу аксиомы Байеса получим:

, (1.32)

где — возможность фактического наблюдения вектора

с данными значениями частот встречаемости главных слов (термов);

— априорная возможность того, что документ относится к домену

i


,

— возможность того, что домен

i


мог привести к возникновению вектора

i


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

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

0


– ни один из шаблонов-документов не является обладателем

;

1


–

-й источник является обладателем

, другие – нет;

m


–

-й источник является обладателем

, другие – нет;

m


+1


– 1-й и 2-й источники в совокупы могут быть обладателями

, другие нет;

n


– все

могут быть в совокупы обладателями

.

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

, (1.33)

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


заместо фактического Ij


.

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

сейчас, приняв Lkk




и Lij




Lji


=1 (для всех













), получим совсем

(1.34)

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

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

, (1.35)

можно утверждать, что меньшему значению

i


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

.

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

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


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

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

m


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





i




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

i


, а аспектами являются причины, обусловливающие априорные значения





i




. Для оценки значений



x



i




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

i


.

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

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

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

значения dij


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


поближе к единице, тем, по воззрению профессионала, вероятнее соответствие факта принадлежности

-го главного слова

— му домену.

Для выявления вероятного домена — обладателя выбраны последующие аспекты:

Т1

— степень соответствия входной спецификации теме

-го шаблона-документа,

Т2

– распространенность темы;

Т3

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

Т4

– степень общности темы (широта темы).

Для получения обобщенной, всеохватывающей оценки вероятности по

аспектам сразу нужно найти коэффициенты

j


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

Т1

Т2

Т3

Т4

Т1

1
d12

d13

d14

Т2

d21

1
d22

d24

Т3

d31

d32

1
d34

Т4

d41

d42

d43

1

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

( 1.36 )

Откуда

( 1.37 )

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

( 1.38 )

где

Размер матрицы
1
2
3
4
5
6
7
8
9
10

x
0
0
0,58
0,90
1,12
1,24
1,32
1,41
1,45
1,49

Обобщенную оценку вероятности обладателя документа Ii


можно вычислить по формуле:

( 1.39 )

где

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

ij


— личные функции полезности

-го объекта по

-му аспекту;

j


— статистический вес (значимость)

-го аспекта





j






.

Величины

(…) употребляются последующим образом. Находим, к примеру,





я




— оценку априорной вероятности того, что обладателями являются домены 1, 2 , а другие три источника – 3,4,5,6 – нет:

R




=

(1)*

(2)*(1-

(3))*(1-

(4))*(1-

(5)) *(1-

(6)).

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

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

.

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

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

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

— ( **) число уровней варьирования всякого фактора обозначается

и именуется модулем;

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

—

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

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

N = Sn
,

( 1.40)

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

n








( 1.41 )

где

— число уровней варьирования;

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

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

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

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

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

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

раз попорядку;

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





повторений и т.д.

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

в согласовании с координатами вершин связок плоскостей на бесконечности (генераторов информационной сети).

Определение векторов
|
mi

|
оценок достоверности обладателя шаблона
Ii

Для получения оценок векторов средних значений mi


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

i


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

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

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

( 1.42 )

где: mi


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


,

— размерность вектора

ci


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

ci


-1


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

— определитель матрицы

i

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

( 1.43 )

Определение классифицирующего огромного количества документов-шаблонов

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

Расстоянием меж 2-мя документами назовем величину

(


a


,


b


) (


x


,


c


):

(1.44)

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

На основании этих данных строится

— матрица

bjj




таковая, что bij


= 1


в том и лишь в том случае, когда расстояние dij


меж документами

и

не превосходит

, и bij




в неприятном случае. Любому документу присвоим вес Сi


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

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

Во-1-х, можно отыскать малое взвешенное покрытие

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с.

]]>