1. Сортування вставками
Нехай треба впорядкувати N елементів R1, R2 ... Rn.
Назвемо їх записами, а всю сукупність N назвемо файлом. Кожна запис Rj має свій ключ Kj, який і керує процесом сортування. Крім ключа, запис може містити додаткову «супутню інформацію», яка не впливає на сортування, але завжди залишається в цьому записі.
Відношення порядку «<» на безлічі ключів таким чином, щоб для всіх 3-х значень ключів а, в, с виконувалися наступні умови:
1) справедливо одне і тільки одне із співвідношень: а <b, a = b, b <a (закон Трихотомія);
2) якщо а <b і b <с, то а <с (закон Транзит-ти).
Ці 2 властивості визначають математичне поняття лінійного впорядкування, яку називають ще досконалим впорядкуванням. Будь-яке безліч з відношенням «<», задовольняються властивостям 1) і 2), піддається сортуванню більшістю методом сортування, який ми будемо розглядати, хоча деякі з них годяться тільки для числових і буквених ключів зі звичайним відношенням порядку.
Завдання сортування - знайти таку перестановку записів p (1), p (2), p (n) після К ключі розташувалися б у неспадними порядку:
Kp (1) <Kp (2 )<...< Kp (n)
Сортування називається стійкою, якщо вона задовольняє додатковому умові, що записи з однаковими ключами залишаються в колишнього порядку, тобто:
Р (i) <Р (j), якщо Kp (i) = Kp (j) і i <j
Зазвичай сортування поділяють на 2 класи:
• внутрішню, якщо записи, які сортуються, знаходяться в операційній пам'яті;
• зовнішню, якщо деякі з записів, які сортуються, знаходяться в допоміжній пам'яті.
Обмежимо наш розгляд лише внутрішніми сортування. Алгоритми сортування можна підрозділити на кілька груп:
A. Сортування вставками. Елементи проглядаються по одному, і кожен новий
елемент вставляється у відповідне місце серед раніше упорядкованих елементів.
B. Обмінна сортування. Якщо два елементи розташовані не по порядку, то вони
міняються місцями. Цей процес повторюється до тих пір, поки елементи не будуть упорядковані.
C. Сортування за допомогою вибору. Спочатку виділяється найменший (або, може бути,
найбільший) елемент і яким-небудь-образом відокремлюється від інших, потім вибирається
найменший (найбільший) з решти і так далі.
Д. Сортування підрахунком. Кожен елемент порівнюється з усіма іншими, остаточне положення елемента визначається підрахунком числа найменших ключів.
Є. Спеціальна сортування, яка хороша для кількох елементів, але не піддається простому узагальнення на випадок більшого числа елементів.
Сортування виконується або над самими записами, або над покажчиками деякої допоміжної таблиці, наприклад, розглядаємо рис.1, на якому представлений файл з 5 записами. Якщо цей файл відсортувати у зростаючому порядку за вказаною числовому ключу, то результуючий файл буде таким, як показано на рис.2. У цьому випадку були відсортовані і самі записи.
Якщо записи і / або ключі займають кілька слів пам'яті, то часто краще скласти нову таблицю адрес (посилань), які вказують на записі і працюють з цими адресами, не переміщаючи громіздкі запису. Такий метод називається сортуванням таблиці адрес.
Якщо ключі короткі, а супутня інформація в записах велика, то для підвищення швидкості ключі можна винести в таблицю адрес; це називається сортуванням ключів. Інші схеми сортування використовують допоміжне полі зв'язку, що включається в кожну запис. Зв'язки обробляються таким чином, що в результаті всі записи виявляються пов'язаними в лінійний список, в якому кожна зв'язок вказує на наступну по порядку запис. Це називається сортуванням списку.
Досить хороший алгоритм витрачає на сортування N записів час порядку NlogN; при цьому потрібно близько log N «проходів» за даними.
При N - »oo час працює на N (log) 2, якщо всі ключі різні, так як і розміри ключів збільшуються зі зростанням N, але практично N завжди залишається обмеженим.
Сортування вставками.
Прості вставки. Нехай 1 <j <N і записи R1 ,..., Rj-1 вже розміщені так, що К1 <К 2 <... Kj1
Будемо порівнювати по черзі Kj з Kj-1 Kj-2> ... до тих пір, поки не виявимо, що запис Rj слід вставити в R1 і R1 + i; тоді посунемо запису Ri +1, ..., Rj-1 на одне місце вгору і помістимо новий запис у позицію i +1. Зручно поєднувати операції порівняння і переміщення, перемішуючи їх один з одним. Оскільки запис Rj як би «проникає на покладений їй рівень», цей спосіб часто називають просіюванням або зануренням.
Алгоритм (Сортування простими вставками). Записи R 1 ..., R N перерозміщують на тому ж місці; після завершення сортування їх ключі будуть упорядковані: К1 <... <K N.
Крок 1 [Цикл по j]. Виконати кроки 2-5 при j = 2,3 ,..., N і після цього завершити алгоритм.
Крок 2 [Встановити i, К, R]. Встановити i = jl, K = Kj, R = Rj. (У наступних кроках ми спробуємо вставити запис R в потрібне місце, порівнюючи К з Кi при відбувають значеннях i).
Крок 3 Порівняти К, K1. Якщо К> Ki, то перейти до кроку 5 (Ми знайшли шукане місце для запису R).
Сортування простими вставками.
98 12 13 7 3 21 99 128
j = 2 K 2 =
i = l K = 12 R = R 2
R 2 = R1 i = 0
12 98 13 7 3 21 99 128
j = 3
i = 2 K = K 3 = 13 R = R 3 R 3 = R 2 i = 2
12 13 98 7 3 2199 128
j = 4
i = 3 K = K4 = 7 R = R4 R4 = R 3 i = 3
12 13 7 98
j = 2
i = l K = K 2 = 13 R = R 2
12 13 7 98
j = 3
i = 2 K = K 3 = 7 R = R 3 R 3 = R 2 i = 2
12 7 13 98
j = 4
i = 3 K = K4 = 98 R = R4
12 7 13 98
j = 2
i = l K = K 2 = 7 R = R 2 R 2 = R1 i = 0
7 12 13 98
j = 3
i = 2 K = K 3 = 13 R = R 3
7 12 13 98
j = 4
i = 3 K = K4 = 98 R = R4
7 12 13 98
10 переглядів.
Крок 4 [Перемістити Ri, зменшити i]. Встановити Ri +1 = Ri, i = il. Якщо i> 0, то повернутися до кроку 3. (Якщо i = 0, то К - найменший з розглянутих досі ключів, а значить, R повинна зайняти першу позицію).
Крок 5 [R на місце Ri +1]. Встановити Rj +1 = R
2. Сортування Бетчера
Паралельна сортування Бетчера. Якщо ми хочемо отримати, алгоритм Обмін. С, час роботи якого має порядок, менший N 2, то потрібно підбирати для порівнянь деякі пари несоседніх ключів (Кi, Kj).
Схема сортування Бетчера дещо нагадує сортування Шелла, але порівняння виконуються за новим, так що поширення обмінів не обязятельно. Метод Бетчера називають ще «Обмін. С зі злиттям », тому що в ньому відбувається злиття пар відсортованих послідовностей.
Алгоритм (Бетчера). Записи R1 ..., Rn перерозміщують на тому ж місці; після завершення сортування їх ключі будуть впорядковані K1 <... <K N. Передбачається, що N> 2.
Крок 1 [Початкова установка р]. Встановити р = 2 t -1 де t = [log2N] - найменше ціле число таке, що 2 t> N. Кроки 2-5 будуть виконуватися з р = 2 t -1, 2 t -1, ... 1.
Крок 2 [Початкова установка q, г, d]. Встановити q = 2 t -1, r = 0, d = p.
Крок 3 [Цикл за i]. Для всіх i, таких, що o <i <Nd і i A p = r виконати крок 4. Потім перейти до кроку 5. (Тут через i A p позначена операція "логічні і" над двійковими уявленнями чисел i і р; всі біти результату рівні 0, крім тих, для яких у відповідних позиціях i і р знаходяться поодинокі біти.
Так, 13 A 21 = (1101) 2 A (10101) 2 = (00101) 2 = 5. До цього моменту d - непарне кратне р (тобто частка від ділення d на р. непарній), а р-ступінь двійки, так що i ^ p ^ = (i + d) ^ p; (звідси випливає, що дії кроку 4 можна виконувати при всіх потрібних значеннях i в будь-якому порядку або навіть одночасно).
Крок 4 [Порівняння / обмін R i +1 та R i + d +1]. Якщо Ki +1> Ki + d +1, то поміняти місцями Ri +1 і Ri + d + l
Крок 5 [Цикл по q]. Якщо q = p, то встановити d = qp, q = q / 2, r = p і повернутися до кроку 3.
Крок 6 [Цикл по р.]. (До цього моменту перестановка К1 К2, ... K N буде р-впорядкована). Встановити p = [p / 2]. Якщо р> 0, то повернутися до кроку 2.
Швидке сортування Бетчера. У методі Бетчера послідовність порівнянь приречення щоразу порівнюється одні й ті ж пари ключів незалежно від того, що ми могли дізнатися про фото з попередніх порівнянь. Це твердження в більшій мірі справедливо і стосовно до методу бульбашки хоч алгоритм Бетчера і використовує в обмеженою ступеня отримання відомості, з тим, скоротити кількість роботи у правому кінці файлу.
3. Структура, завдання та формалізація предметної області
В основі логічного моделювання лежить формальна система, що задається четвіркою виду М = <Т, Р, А, В>. Безліч Т - безліч базових елементів різної природи. Для цього безлічі існує деякий спосіб визначення належності або не належності будь-якого елемента до цього безлічі. Процедура перевірки може бути будь-який, але за кінцеве число кроків вона повинна дати позитивний чи негативний результат на питання, чи є х елементом множини Т. Позначимо цю процедуру П (Т).
Безліч Р - безліч синтаксичних правил. З їх допомогою з елементів Т утворюються синтаксично правильні сукупності. Існує процедура П (Р), за допомогою якої за кінцеве число кроків можна отримати відповідь на питання, чи є сукупність X синтаксично правильною.
У безлічі синтаксично правильних сукупностей виділяється деяка підмножина О. Елементи А називаються аксіомами. Процедура П (А) дає відповідь ка питання, чи належить дана синтаксично правильна сукупність до безлічі А.
Безліч В - множина правил виведення. Застосовуючи їх до елементів А, можна отримати нові сінтакагческі правильні сукупності, до яких можна застосовувати правила з В. Якщо є процедура П (У), з допомогою якої можна визначити для будь-якої синтаксично правильної сукупності, чи є вона виводиться, то відповідна формальна система називається розв'язною.
Усі предмети і події, які складають основу спільного розуміння необхідної для розв'язання задачі інформації, називаються предметною областю. Предметна область представляється з реальних або абстрактних об'єктів, званих сутностями.
Сутності предметної області знаходяться певних відносинах один до одного (асоціаціях), які також можна розглядати як сутності і включати в предметну область. Між сутностями спостерігаються різні відносини подібності. Сукупність подібних сутностей складає клас сутностей, що є новою сутністю предметної області.
Відносини між сутностями виражаються за допомогою суджень. Судження - це подумки можлива ситуація, яка може мати місце для експонованих сутностей або не мати місця.
У мові судження відповідають пропозиції. Судження та пропозиції також можна розглядати як сутність і включати в предметну область.
Мови, призначені для опису предметних областей, називаються мовами представлення знань. Універсальним мовою подання знань є природна мова. Проте використання природної мови в системах машинного представлення знань наштовхується на великі труднощі, пов'язані із двозначністю, нерегулярністю і т.д. Але головна перешкода полягає у відсутності формальної семантики природної мови, яка мала б достатньо ефективну операційну підтримку.
Для подання математичного знання в математичній логіці давно користуються обчисленням предикатів, яке має ясну формальну семантику та операційну підтримку (розроблені механізми виведення).
Описи предметних областей, виконані в логічних мовах, називаються (формальними) логічними моделями.
Нехай треба впорядкувати N елементів R1, R2 ... Rn.
Назвемо їх записами, а всю сукупність N назвемо файлом. Кожна запис Rj має свій ключ Kj, який і керує процесом сортування. Крім ключа, запис може містити додаткову «супутню інформацію», яка не впливає на сортування, але завжди залишається в цьому записі.
Відношення порядку «<» на безлічі ключів таким чином, щоб для всіх 3-х значень ключів а, в, с виконувалися наступні умови:
1) справедливо одне і тільки одне із співвідношень: а <b, a = b, b <a (закон Трихотомія);
2) якщо а <b і b <с, то а <с (закон Транзит-ти).
Ці 2 властивості визначають математичне поняття лінійного впорядкування, яку називають ще досконалим впорядкуванням. Будь-яке безліч з відношенням «<», задовольняються властивостям 1) і 2), піддається сортуванню більшістю методом сортування, який ми будемо розглядати, хоча деякі з них годяться тільки для числових і буквених ключів зі звичайним відношенням порядку.
Завдання сортування - знайти таку перестановку записів p (1), p (2), p (n) після К ключі розташувалися б у неспадними порядку:
Kp (1) <Kp (2 )<...< Kp (n)
Сортування називається стійкою, якщо вона задовольняє додатковому умові, що записи з однаковими ключами залишаються в колишнього порядку, тобто:
Р (i) <Р (j), якщо Kp (i) = Kp (j) і i <j
Зазвичай сортування поділяють на 2 класи:
• внутрішню, якщо записи, які сортуються, знаходяться в операційній пам'яті;
• зовнішню, якщо деякі з записів, які сортуються, знаходяться в допоміжній пам'яті.
Обмежимо наш розгляд лише внутрішніми сортування. Алгоритми сортування можна підрозділити на кілька груп:
A. Сортування вставками. Елементи проглядаються по одному, і кожен новий
елемент вставляється у відповідне місце серед раніше упорядкованих елементів.
B. Обмінна сортування. Якщо два елементи розташовані не по порядку, то вони
міняються місцями. Цей процес повторюється до тих пір, поки елементи не будуть упорядковані.
C. Сортування за допомогою вибору. Спочатку виділяється найменший (або, може бути,
найбільший) елемент і яким-небудь-образом відокремлюється від інших, потім вибирається
найменший (найбільший) з решти і так далі.
Д. Сортування підрахунком. Кожен елемент порівнюється з усіма іншими, остаточне положення елемента визначається підрахунком числа найменших ключів.
Є. Спеціальна сортування, яка хороша для кількох елементів, але не піддається простому узагальнення на випадок більшого числа елементів.
Сортування виконується або над самими записами, або над покажчиками деякої допоміжної таблиці, наприклад, розглядаємо рис.1, на якому представлений файл з 5 записами. Якщо цей файл відсортувати у зростаючому порядку за вказаною числовому ключу, то результуючий файл буде таким, як показано на рис.2. У цьому випадку були відсортовані і самі записи.
Якщо записи і / або ключі займають кілька слів пам'яті, то часто краще скласти нову таблицю адрес (посилань), які вказують на записі і працюють з цими адресами, не переміщаючи громіздкі запису. Такий метод називається сортуванням таблиці адрес.
Якщо ключі короткі, а супутня інформація в записах велика, то для підвищення швидкості ключі можна винести в таблицю адрес; це називається сортуванням ключів. Інші схеми сортування використовують допоміжне полі зв'язку, що включається в кожну запис. Зв'язки обробляються таким чином, що в результаті всі записи виявляються пов'язаними в лінійний список, в якому кожна зв'язок вказує на наступну по порядку запис. Це називається сортуванням списку.
Досить хороший алгоритм витрачає на сортування N записів час порядку NlogN; при цьому потрібно близько log N «проходів» за даними.
При N - »oo час працює на N (log) 2, якщо всі ключі різні, так як і розміри ключів збільшуються зі зростанням N, але практично N завжди залишається обмеженим.
Сортування вставками.
Прості вставки. Нехай 1 <j <N і записи R1 ,..., Rj-1 вже розміщені так, що К1 <К 2 <... Kj1
Будемо порівнювати по черзі Kj з Kj-1 Kj-2> ... до тих пір, поки не виявимо, що запис Rj слід вставити в R1 і R1 + i; тоді посунемо запису Ri +1, ..., Rj-1 на одне місце вгору і помістимо новий запис у позицію i +1. Зручно поєднувати операції порівняння і переміщення, перемішуючи їх один з одним. Оскільки запис Rj як би «проникає на покладений їй рівень», цей спосіб часто називають просіюванням або зануренням.
Алгоритм (Сортування простими вставками). Записи R 1 ..., R N перерозміщують на тому ж місці; після завершення сортування їх ключі будуть упорядковані: К1 <... <K N.
Крок 1 [Цикл по j]. Виконати кроки 2-5 при j = 2,3 ,..., N і після цього завершити алгоритм.
Крок 2 [Встановити i, К, R]. Встановити i = jl, K = Kj, R = Rj. (У наступних кроках ми спробуємо вставити запис R в потрібне місце, порівнюючи К з Кi при відбувають значеннях i).
Крок 3 Порівняти К, K1. Якщо К> Ki, то перейти до кроку 5 (Ми знайшли шукане місце для запису R).
Сортування простими вставками.
98 12 13 7 3 21 99 128
j = 2 K 2 =
i = l K = 12 R = R 2
R 2 = R1 i = 0
12 98 13 7 3 21 99 128
j = 3
i = 2 K = K 3 = 13 R = R 3 R 3 = R 2 i = 2
12 13 98 7 3 2199 128
j = 4
i = 3 K = K4 = 7 R = R4 R4 = R 3 i = 3
12 13 7 98
j = 2
i = l K = K 2 = 13 R = R 2
12 13 7 98
j = 3
i = 2 K = K 3 = 7 R = R 3 R 3 = R 2 i = 2
12 7 13 98
j = 4
i = 3 K = K4 = 98 R = R4
12 7 13 98
j = 2
i = l K = K 2 = 7 R = R 2 R 2 = R1 i = 0
7 12 13 98
j = 3
i = 2 K = K 3 = 13 R = R 3
7 12 13 98
j = 4
i = 3 K = K4 = 98 R = R4
7 12 13 98
10 переглядів.
Крок 4 [Перемістити Ri, зменшити i]. Встановити Ri +1 = Ri, i = il. Якщо i> 0, то повернутися до кроку 3. (Якщо i = 0, то К - найменший з розглянутих досі ключів, а значить, R повинна зайняти першу позицію).
Крок 5 [R на місце Ri +1]. Встановити Rj +1 = R
2. Сортування Бетчера
Паралельна сортування Бетчера. Якщо ми хочемо отримати, алгоритм Обмін. С, час роботи якого має порядок, менший N 2, то потрібно підбирати для порівнянь деякі пари несоседніх ключів (Кi, Kj).
Схема сортування Бетчера дещо нагадує сортування Шелла, але порівняння виконуються за новим, так що поширення обмінів не обязятельно. Метод Бетчера називають ще «Обмін. С зі злиттям », тому що в ньому відбувається злиття пар відсортованих послідовностей.
Алгоритм (Бетчера). Записи R1 ..., Rn перерозміщують на тому ж місці; після завершення сортування їх ключі будуть впорядковані K1 <... <K N. Передбачається, що N> 2.
Крок 1 [Початкова установка р]. Встановити р = 2 t -1 де t = [log2N] - найменше ціле число таке, що 2 t> N. Кроки 2-5 будуть виконуватися з р = 2 t -1, 2 t -1, ... 1.
Крок 2 [Початкова установка q, г, d]. Встановити q = 2 t -1, r = 0, d = p.
Крок 3 [Цикл за i]. Для всіх i, таких, що o <i <Nd і i A p = r виконати крок 4. Потім перейти до кроку 5. (Тут через i A p позначена операція "логічні і" над двійковими уявленнями чисел i і р; всі біти результату рівні 0, крім тих, для яких у відповідних позиціях i і р знаходяться поодинокі біти.
Так, 13 A 21 = (1101) 2 A (10101) 2 = (00101) 2 = 5. До цього моменту d - непарне кратне р (тобто частка від ділення d на р. непарній), а р-ступінь двійки, так що i ^ p ^ = (i + d) ^ p; (звідси випливає, що дії кроку 4 можна виконувати при всіх потрібних значеннях i в будь-якому порядку або навіть одночасно).
Крок 4 [Порівняння / обмін R i +1 та R i + d +1]. Якщо Ki +1> Ki + d +1, то поміняти місцями Ri +1 і Ri + d + l
Крок 5 [Цикл по q]. Якщо q = p, то встановити d = qp, q = q / 2, r = p і повернутися до кроку 3.
Крок 6 [Цикл по р.]. (До цього моменту перестановка К1 К2, ... K N буде р-впорядкована). Встановити p = [p / 2]. Якщо р> 0, то повернутися до кроку 2.
Швидке сортування Бетчера. У методі Бетчера послідовність порівнянь приречення щоразу порівнюється одні й ті ж пари ключів незалежно від того, що ми могли дізнатися про фото з попередніх порівнянь. Це твердження в більшій мірі справедливо і стосовно до методу бульбашки хоч алгоритм Бетчера і використовує в обмеженою ступеня отримання відомості, з тим, скоротити кількість роботи у правому кінці файлу.
3. Структура, завдання та формалізація предметної області
В основі логічного моделювання лежить формальна система, що задається четвіркою виду М = <Т, Р, А, В>. Безліч Т - безліч базових елементів різної природи. Для цього безлічі існує деякий спосіб визначення належності або не належності будь-якого елемента до цього безлічі. Процедура перевірки може бути будь-який, але за кінцеве число кроків вона повинна дати позитивний чи негативний результат на питання, чи є х елементом множини Т. Позначимо цю процедуру П (Т).
Безліч Р - безліч синтаксичних правил. З їх допомогою з елементів Т утворюються синтаксично правильні сукупності. Існує процедура П (Р), за допомогою якої за кінцеве число кроків можна отримати відповідь на питання, чи є сукупність X синтаксично правильною.
У безлічі синтаксично правильних сукупностей виділяється деяка підмножина О. Елементи А називаються аксіомами. Процедура П (А) дає відповідь ка питання, чи належить дана синтаксично правильна сукупність до безлічі А.
Безліч В - множина правил виведення. Застосовуючи їх до елементів А, можна отримати нові сінтакагческі правильні сукупності, до яких можна застосовувати правила з В. Якщо є процедура П (У), з допомогою якої можна визначити для будь-якої синтаксично правильної сукупності, чи є вона виводиться, то відповідна формальна система називається розв'язною.
Усі предмети і події, які складають основу спільного розуміння необхідної для розв'язання задачі інформації, називаються предметною областю. Предметна область представляється з реальних або абстрактних об'єктів, званих сутностями.
Сутності предметної області знаходяться певних відносинах один до одного (асоціаціях), які також можна розглядати як сутності і включати в предметну область. Між сутностями спостерігаються різні відносини подібності. Сукупність подібних сутностей складає клас сутностей, що є новою сутністю предметної області.
Відносини між сутностями виражаються за допомогою суджень. Судження - це подумки можлива ситуація, яка може мати місце для експонованих сутностей або не мати місця.
У мові судження відповідають пропозиції. Судження та пропозиції також можна розглядати як сутність і включати в предметну область.
Мови, призначені для опису предметних областей, називаються мовами представлення знань. Універсальним мовою подання знань є природна мова. Проте використання природної мови в системах машинного представлення знань наштовхується на великі труднощі, пов'язані із двозначністю, нерегулярністю і т.д. Але головна перешкода полягає у відсутності формальної семантики природної мови, яка мала б достатньо ефективну операційну підтримку.
Для подання математичного знання в математичній логіці давно користуються обчисленням предикатів, яке має ясну формальну семантику та операційну підтримку (розроблені механізми виведення).
Описи предметних областей, виконані в логічних мовах, називаються (формальними) логічними моделями.