Наукові проблеми Інтернету

УО «БДУІР»
кафедра інформаційних технологій автоматизованих систем
РЕФЕРАТ
на тему:
«Наукові проблеми Інтернету»
МІНСЬК, 2008

Наукові проблеми Інтернету групуються навколо наступних завдань:
· Захист інформації
· Стиснення інформації
· Пошук інформації
· Розпізнавання інформаційних об'єктів (тексту та образів)
· Прогнозування часових рядів
· Класифікація документів
· Вибір і оцінка багатокритеріальних альтернатив
· Прийняття рішень і логічний висновок і ін
Розгляд всіх цих завдань виходить за рамки цієї праці. Розглянемо лише деякі завдання.
1 Захист інформації
Сучасні способи захисту інформації використовують в першу чергу різні методи шифрування. Ми розглянемо тут два криптографічних методу: RSA і DES. Основні принципи криптографії можна сформулювати наступним чином.
1. У шифруванні основну роль грає не алгоритм, а ключ.
2. Алгоритм шифрування повинен бути таким, щоб шифрування виконувалося легко і ефективно з обчислювальної точки зору, навпаки, дешифрування має представляти собою складну математичну задачу (наприклад, переборного типу).
Алгоритм RSA. Нехай необхідно передати по лінії зв'язку числа x (розглянемо тут тільки цілі позитивні числа). Замість числа x передають число y, яке обчислюється за формулою

,

(1.1)

де e та m є відкритими числами (відомі всім абонентам мережі).
Вимагаємо, щоб e і m були взаємно простими числами (тобто не числами спільних дільників, крім 1, причому ).
Виявляється, що знаючи y, e і m, знайти x - складна математична задача. Поки ж продемонструємо, як знайти y по x, e, m.
Операція

(1.2)

знаходить цілочисельний залишок 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, рівний . Але , . Тому
.
Тепер неважко це правило застосувати, скажімо, до
^{13 липня} mod 8 =?
Запишемо
.
Маємо . Тому .
Звернемося тепер до формули (6.16).
Нехай , , .
Знайдемо
.
Отже, . Це значення і буде передано по мережі замість x.
Тепер розглянемо, як відновити x по y, m, e. Для цієї мети потрібно знайти число d, що задовольняє умові

,

(1.3)

де - Значення функції Ейлера від числа m. Функція Ейлера обчислюється порівняно просто. Так,

.

(1.4)

Якщо p просте число і r - ціле, то

.

(1.5)

Формул (1.4) і (1.5) достатньо для того, щоб знайти функцію Ейлера для будь-якого цілого позитивного числа. У нашому випадку одержуємо:
.
Для допитливих читачів відзначимо, що значення дорівнює числу цілих чисел на відрізку 1 .. m, взаємно простих з m. Відшукування значення функції Ейлера для великих цілих чисел є обчислювальної завданням дуже великої складності.
Приклад. . Всі чотири числа: 1, 2, 3, 4 взаємно прості з m.
Тепер звернемося до рівняння (3.3). У цьому рівнянні d грає роль секретного ключа. Розв'язати рівняння (3.3) шляхом перебору значень d можна, але якщо в числі m, наприклад, 100 цифр, то на обчислення d піде досить багато часу. Для невеликих значень, таких як у нашому прикладі, можна скористатися алгоритмом рішення рівнянь у цілих числах, який ми і наведемо.
Отже, в нашому прикладі рівняння таке:

.

(1.6)

Рівняння (1.6) можна переписати таким відомим чином:

.

(1.7)

У (1.7) r і d невідомі цілі числа. Уявімо (1.7) у вигляді системи двох лінійних нерівностей.
,
,
або, що еквівалентно:

, .

(1.8)

У нерівності з позитивною правою частиною виділимо член з мінімальним по модулю коефіцієнтом і дозволимо нерівність щодо цього члена:
, .
Звідси легко отримати відтинає нерівність:

(A) , (B) , (C) .

(1.9)

Тут z - нова цілочисельна змінна. Зауважимо, що перехід від (a) до (b) в (1.9) правомірний, оскільки r, d, z - цілочисельних.
Виконаємо підстановку (3.9) в систему (1.8). Отримаємо нову систему:

, .

(1.10)

Звернемо увагу на наступне принципову обставину. У порівнянні з (1.8) значення мінімального коефіцієнта знизилося. Цей факт можна строго обгрунтувати. Отже, весь процес повинен закінчитися рано чи пізно одним з двох результатів:
1) мінімальний коефіцієнт за модулем стане рівним 1 (як в (1.10)); буде отримано систему виду
,
,
де a і b - взаємно прості (у цьому випадку немає рішення в цілих числах).
У першому випадку процес вирішення завершений. Отримуємо з (1.10) підстановку для d:

.

(1.11)

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

.

(1.12)

Отже, формули (1.11) і (1.12) і дають нам підсумкові підстановки для d і r з (1.7). Наприклад, нехай . Тоді , . Візьмемо саме це значення для мінімального d.
Отже, ми підійшли до вирішального моменту: наш секретний ключ . Отримали число , , . Відновлюємо x за формулою:

.

(1.13)

Отже, .
Все зійшлося. Візьмемо, наприклад, . Тоді , :
(Відповідь той же).
Таким чином, не має значення, яке z брати для отримання d.
Метод RSA ми завершимо наступним зауваженням.
Метод RSA взагалі кажучи вимагає, щоб m було великим простим числом. Для встановлення факту, що m - просте, можна використовувати малу теорему Ферма:

.

(1.14)

У (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:
Таким чином, операція підстановки непередбачуваним чином спотворює вихідні дані. Для відновлення вихідних даних достатньо виконати підстановку вдруге:
Операція перемішування полягає в обміні місцями двох блоків відповідно до заздалегідь складеними таблицями. Довжина обмінюваних блоків однакова, але варіює від одного проходу до іншого. Операція підстановки виконується не над цілим ключем, а над випадково вибирається його частиною. Ця випадково обрана частина сама визначається значенням ключа. Одним із способів отримання псевдовипадкових чисел є наступний:

.

(1.15)

Тут - Псевдовипадкове число, породжене на кроці i. спочатку думають, наприклад, . В якості константи C приймемо

,

(1.16)

де K - секретний ключ. Величина M як правило дорівнює ; Величина n дорівнює числу розрядів генерується псевдовипадкового числа. Наприклад, нехай , , , , :
,
,
,
,
і т.д.
Породжені псевдовипадкові числа можуть визначати номери розрядів, обираних з ключа в формовану частина для виконання операції підстановки.
Для дешифрування прийнятої комбінації потрібно знати ключ K і виконувати операції підстановки і перемішування в зворотному порядку
2. Стиснення інформації

Стиснення за методом Д. Хаффмана

Метод стиснення Хаффмана є одним з кращих способів стискування інформації. Даний метод ми викладемо на наступному прикладі. Нехай дана підлягає стисненню послідовність з «0» і «1»:

010000101000101111001011.

(1.17)

Розіб'ємо цю послідовність на трійки розрядів і для кожної трійки підрахуємо, скільки разів вона зустрічається в послідовності (рис. 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)

'000-101 '- 2 '010-111 '- 2 '001-011 '- 2 Рис. 3.16.

'010-111-001-011 '- 4 '000-101 '- 4 Рис. 3.17.

Тепер намалюємо дерево, схематично передавальне реалізований нами спосіб об'єднання комбінацій (рис. 1.18)
SHAPE \ * MERGEFORMAT

1

1

1

1

1

0

0

0

0

0

000

101

010

111

001

011

корінь

Рис. 1.18.
Для отриманого дерева виконаємо рух з кореневої вершини до вихідних трійкам. При виході з будь-якого вузла позначаємо одне з двох ребер «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)

де - Число бітів в i-ої комбінації,
- Відносна частота зустрічальності i-ої комбінації.
Було відмічено, хоча це і не обов'язково вірно у всіх випадках, що довжина коду Хаффмана комбінації , Як правило, не перевершує величину (- ). Так, у нашому прикладі відносна частота комбінації 000 складає . Її код Хаффмана є 11 (довжина цього коду дорівнює 2). Маємо
(Що справедливо).
Таким чином, при кодуванні Хаффмана результуючу довжину коду можна орієнтовано записати у вигляді

.

(1.20)

Кодування Хаффмана модно застосовувати повторно.

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

Нехай є послідовність .

(1.21)

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

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

(1.22)

Зауважимо, що довжина кожного подинтервала відповідає відносній частоті відповідного символу. Неважко зміркувати, що перший подинтервала [0; 0,25] відповідає ; Подинтервала (0,25; 0,75] - символу і (0,75; 1] - символу . У послідовності (3.22) перший символ . Йому відповідає інтервал [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)

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

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

(1.25)

Нарешті, останній символ - . Йому відповідає третій інтервал. Тому в якості остаточного коду для послідовності (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) вибираємо символ .
Арифметичне стиснення може давати великі послідовності цифр і тому його застосування обмежується невеликими послідовностями символів.

Стиснення графічних файлів

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

.

(1.26)

Спочатку знайдемо за правилами матричної алгебри твір
,
Потім

.

(1.27)

Отримаємо
.
У цій матриці домінує лише невелике число елементів. Можна виконати квантування, наприклад, наступним чином:
.
Саме ця операція (квантування) і приводить до втрати даних, хоча ця втрата мало відбивається на вихідних даних. Справді, легко відновити з (3.27) матрицю С:

.

(1.28)

і, аналогічно,

.

(1.29)

За допомогою (3.28), (3.29) отримаємо відновлену наближену матрицю вихідних даних:
.
Після квантування отримаємо
.
Ця остання матриця дуже близька до вихідної матриці D (!).
Перш за все, зауважимо, що матриця перетворення W повинна будується спеціальним чином. По-перше, вона повинна бути ортогональною, що означає, що векторний добуток будь-яких її двох рядків або стовпців дорівнює 0 (а це означає, що рядки і стовпці матриці незалежні і, отже, визначник матриці відмінний від 0). По-друге, матриця W підбирається так, що сума елементів тільки в першому рядку і в першому стовпці максимальні; в інших рядках і стовпцях суми елементів рівні або близькі до 0.
З міркувань, близьких до розглянутих, будується матриця дискретного косинусного перетворення (DCT-матриця), що використовується в алгоритмі JPEG. Матриця двовимірного DCT-перетворення визначається з наступної формули

.

(1.30)

У (3.30) - Значення пікселя в рядку x і стовпці y квадратної матриці пікселів розмірів ;

Матриця одновимірного DCT-перетворення використовує розрахункову формулу

.

(1.31)

Зауважимо, що величини

змінюються для і так що в результаті з них можна побудувати наступну матрицю перетворення (для )
Ця матриця є ортогональною і побудована за тими ж принципами, що й матриця W, яку ми розглянули вище. Нам залишається коротко охарактеризувати алгоритм стиснення JPEG, основу якого складає DCT-перетворення.
У JPEG використовується колірна модель YCrCb, де Y передає світність пікселя. Перетворення DCT виконується окремо до світності Y, і окремо до матриці, що кодує хроматичні числа Cr і Cb. До світності Y застосовується одномірне DCT перетворення. Для компоненти <Cr, Cb> виконується розбиття зображення на матриці пікселів . До кожної з таких матриць застосовується двовимірне DCT-перетворення. Таким чином, виконується стиснення з втратою інформації.
Скорочення JPEG походить від слів Joint Photographic Expert Group - спільна група по фотографії. Проект JPEG став стандартом у 1991р. - Прийнятий міжнародною організацією стандартів ISO.
3. Класифікація документів
Методи специфікації та обробки документів в Internet отримують широке застосування у зв'язку зі створенням нових технологій і розширенням можливостей подання семантики текстів, в першу чергу в документах XML.
У цьому розділі розглядаються програмно-математичні аспекти обробки текстів і створення інтелектуальних пошукових систем в Internet.____________________________________

      Завдання класифікації та ідентифікації документів

Нехай у базі даних є специфікації текстів документів I _1, I ₂ ,..., I _n, на вході системи є специфікація документа Х = (х _1, х _2, ..., х _m). Установити, до якого класу документів I _1, I ₂ ,..., I _n відноситься Х.
Задачу будемо вирішувати при наступних умовах:
· Параметри х _1, х _2, ..., х _m задають частоти зустрічальності термів в тексті. Аналогічним чином, специфікації представлені векторами частот зустрічальності термів в текстах-шаблонах. Під термо розуміється ключове слово тексту.
· Відомі вагові оцінки значущості термів для відповідних документів.
У результаті будуть обчислені деякі оцінки b _1, b _2, ..., b _n, що визначають систему переваг у встановленні документа-шаблону, до якого належить текст Х, при цьому å b _i = 1 і якщо b _p> b _s, то об'єктивно приналежність Х до I _p оцінюється вище, ніж до I _s.
Опис проблеми та етапів її рішення
Припустимо, що в силу спільності або перетину тим документів може виникнути n кластерів (доменів, зон) з різним ступенем (оцінки) приналежності до них розглядають документ Х; Нехай P (w _i ï х) - умовна ймовірність того, що спостережуваний вектор х відноситься до домену w _i. У силу теореми Байєса отримаємо:
, (1.32)
де - Ймовірність фактичного спостереження вектора х з даними значеннями частот зустрічальності ключових слів (термів);
- Апріорна ймовірність того, що документ належить до домену w _i,
- Імовірність того, що домен w _i міг призвести до появи вектора х;
w _i - ідентифікатор домену.
Розглядаються такі домени:
w ₀ - жоден з шаблонів-документів не є власником Х;
w ₁ - 1-й джерело є власником Х, інші - ні;
w _m - m-й джерело є власником Х, інші - ні;
w _{m +1} - 1-й і 2-й джерела в сукупності можуть бути власниками Х, інші ні;
w _n - Все n можуть бути в сукупності власниками Х.
Введемо штрафну оцінку
, (1.33)
де - Штраф, який слід заплатити за помилкову класифікацію власника _{I i} замість фактичного I _j.
З урахуванням (1.32) перепишемо (1.33) у вигляді

Тепер, прийнявши L _kk = 0 і L _ij = L _ji = 1 (для всіх i, j, i ¹ j), отримаємо остаточно
(1.34)
Формула (1.34) є основою для прийняття рішень.
Ввівши співвідношення
, (1.35)
можна стверджувати, що найменшим значенням b _i буде відповідати документ з найменшою оцінкою можливості бути власником Х.
Застосування формули (1.34) зажадає спрощує допущення, а саме - граничні розподілу значень частот зустрічальності термів в тексті повинні підкорятися багатовимірному нормальному закону.
Апріорну ймовірність того, що власником документа є шаблон _{I i,} можна визначити на основі теорії вибору багатокритеріальних рішень з використанням функції корисності.
Для оцінки ймовірності необхідно визначити , Ймовірність фактичного спостереження вектора х, значимо не відрізняється від результатів розрахунку частот зустрічальності термів, породжуваних доменом w _m, що спричинить за собою необхідність спланувати спеціальний обчислювальний експеримент з побудовою інформаційної мережі через проективні геометрії і поля Галуа.
Таким чином, методика розрахунків зводиться до визначення членів формули (1.34). Для визначення множників P (w _i) використовується техніка багатокритеріальної оцінки на основі процедури Сааті, де в якості альтернатив розглядаються домени w _i , А критеріями є фактори, що обумовлюють апріорні значення P (w _i). Для оцінки значень P (x | w _i) проводиться серія обчислювальних експериментів, метою яких є отримання математичного очікування і середньоквадратичного відхилення частот зустрічальності термів в домені w _i.
Подальший виклад розкриває істота зазначеної методики та її теоретико-практичне наповнення.
Оцінка - Апріорної ймовірності того, що власником документа є домен w _i
Значення шуканої ймовірності можна отримати шляхом математичної обробки експертних оцінок фахівців із залученням теорії багатокритеріальних рішень і функції корисності.
Значення d _ij приватних функцій корисності, що привласнюються експертами кожному домену, можуть розташовуватися в діапазоні [0, 1]. Чим d _ij ближче до одиниці, тим, на думку експерта, найімовірніше відповідність факту приналежності j-го ключового слова i - му домену.
Для виявлення можливого домену - власника обрано такі критерії:
Т ₁ - ступінь відповідності вхідний специфікації тематиці i-го шаблону-документа,
Т ₂ - поширеність тематики;
Т ₃ - цитованість документів за тематикою за останній місяць;
Т ₄ - ступінь спільності тематики (широта тематики).
Для отримання узагальненої, комплексної оцінки ймовірності по p критеріям одночасно необхідно визначити коефіцієнти d _j, що характеризують значимість, пріоритети (статистичні ваги) кожного критерію. Для цієї мети використовується алгоритм Сааті, за яким будується матриця пріоритетів D:
Для кожного рядка знаходимо
(1.36)
Звідки
(1.37)
Знайдені значення статистичних ваг вважаються узгодженими, якщо виконується умова Сааті:
(1.38)
де
Узагальнену оцінку ймовірності власника документа _{I i} можна обчислити за формулою:
(1.39)
де p - кількості узагальнюючих ознак;
d _ij - приватні функції корисності i-го об'єкта по j-му критерію;
m _j - статистична вага (важливість) j-го критерію (0 £ m _j £ 1).
Величини q (...) використовуються таким чином. Знаходимо, наприклад, P (w _я) - оцінку апріорної ймовірності того, що власниками є домени 1, 2, а інші три джерела - 3,4,5,6 - ні:
P (w _R) = q (1) * q (2) * (1 - q (3)) * (1 - q (4)) * (1 - q (5)) * (1 - q (6)).
Відзначимо, що ця та подібні формули виходять із загальної формули Бернуллі для ймовірності складної події.
Визначення - Ймовірності фактичного спостереження вектора | х |, значимо не відрізняється від результатів розрахунку частот зустрічальності термів в документах, породжуваних від джерела _{I i.}
Перед тим як приступити до побудови інформаційної мережі, потрібно обгрунтувати вибір необхідного числа чинників і рівнів варіювання кожного фактора. Етапами формування інформаційної мережі є складання груп координат вершин зв'язок площин на нескінченності, чисельно рівних кількості факторів і виступають у якості генераторів планів експерименту, а також вирішення проблеми упаковки ортогональних таблиць шляхом заповнення їх елементами поля Галуа відповідно до генераторами планів.
При складанні груп координат вершин зв'язок площин на нескінченності, діють наступні правила:
- (*) В групу входить стільки координат, скільки вершин у фундаментальному симплекс;
- (**) Число рівнів варіювання кожного фактора позначається S і називається модулем;
- (***) Кожна наступна група координат виходить додатком одиниці до молодшого розряду по модулю;
- (****) Перший ненульова координата не може бути більше одиниці.
Необхідна кількість дослідів у вузлах інформаційної мережі визначається за формулою
N = S ^n, (1.40 )
a кількість факторів, яке можна описати цією кількістю дослідів, знаходиться з виразу
F = (S ⁿ -1) / (S -1) (1.41)
де S - число рівнів варіювання;
n - число вершин фундаментального симплекса.
Наступною операцією формування інформаційної мережі є заповнення елементами поля Галуа стовпців ортогональної таблиці під координатами вершин фундаментального симплекса (складання лінійно незалежних векторів).
Правила складання лінійно незалежних векторів:
- Групи координат вершин фундаментального симплекса повинні розташовуватися в перших шпальтах ортогональної таблиці;
- У першому стовпці елементи поля Галуа, чисельно рівні рівнями варіювання факторів, перераховуються по порядку стільки разів, скільки рівнів варіювання, тобто число елементів повинно бути (0,1, .., S) 'S;
- У другому стовпці кожен елемент, чисельно рівний рівню варіювання, повторюється S разів поспіль;
- У третьому стовпці зміна рівнів варіювання відбувається через S 'S повторень і т.д.
Рішення проблеми упаковки ортогональної таблиці проводиться шляхом множення і складання елементів поля Галуа в кільці класів лишків за модулем S відповідно з координатами вершин зв'язок площин на нескінченності (генераторів інформаційної мережі).
Визначення векторів | m _i | оцінок достовірності власника шаблону _{I i}
Для отримання оцінок векторів середніх значень m _i і стандартних відхилень (коефіцієнтів кореляції) частот зустрічальності термів необхідно розглянути ряд документів, що відносяться до однієї тематики, представленої шаблоном w _i. Цей етап повинен бути проведений заздалегідь при створенні системи ідентифікації.
Оцінка , Ймовірності того, що власником вхідного документа є шаблон _{I i}
Граничні розподілу значень частот термів від кожного джерела повинні підкорятися багатовимірному нормальному закону:
(1.42)
де: m _i - вектор математичних сподівань частот зустрічальності термів у документа, породжуваних від джерела _{I i,}
m - розмірність вектора х
c _i - коваріаційна матриця векторів частот термів,
c _i ^-1 - обернена матриця c _i,
- Визначник матриці з _i
Для визначення елементів ковариационной матриці використовується співвідношення:
(1.43)

  Визначення класифікуючого безлічі документів-шаблонів

З метою формалізації процедури прийняття рішення про необхідній кількості документів-шаблонів запропоновано розглядати деяку метрику, що встановлює міру близькості двох різних документів-шаблонів.
Відстанню між двома документами назвемо величину d _{(a, b) (x, c):}
(1.44)
Значення евклідова відстані можна використовувати для розбиття множини документів на кластери (зони), що представляють деякі типові сюжети.
На підставі цих даних будується 0,1 - матриця В = [b _jj], така, що b _{ij = 1} в тому і тільки в тому випадку, коли відстань d _ij між документами i і j не перевершує d, і b _ij = 0 у противному випадку. Кожному документу привласнимо вага З _i, що відображає його типовість для розкривається в ньому теми.
Підготовлені таким чином вихідні дані дозволяють сформулювати і вирішити наступну важливу прикладну задачу.
По-перше, можна знайти мінімальне зважене покриття p ^min, тобто така безліч рядків з ½ В ½, які мають мінімальну вартість і, принаймні, будь-яка одна рядок з p ^min містить на перетині з кожним із стовпців одиницю. Ця задача дозволяє визначити необхідну кількість шаблонів документів у классифицирующей множині.
Таким чином, процедура визначення необхідного числа документів в классифицирующей зводиться до вирішення добре відомої NP-повної задачі про мінімальний зваженому покритті 0,1-матриці безліччю рядків (ЗМВП).

Література
1. Успенський І. Інтернет як інструмент маркетингу. BHV, С-т Петербург, 256с., 2002. .
2. Меградж З. Розробка додатків для електронної комерції на ORACLE і JAVA. Вільямс, 2000, 328с.
3. Пирогов В.П. MS SQL Server 2000. Управління та програмування. - СПб. БХВ.-2005,-600С.
4. Хол М., Браун Л. Програмування для WEB. Вільямс, 2002, - 1280с.