Алгоритми і структури даних

Сортування злиттям основане на принципі «розділяй і володарюй». Спочатку ми розбиваємо масив на дві половини меншого розміру. Потім ми сортуємо кожну з половин окремо. Після цього нам залишається з’єднати два впорядкованих масиви половинного розміру в один. Рекурсивне розбиття за-дачі на менші відбувається доти, поки розмір масиву не дійде до одиниці (будь-який масив довжини можна вважати впорядкованим).

Нетривіальною частиною є з’єднання двох упорядкованих масивів в один. Воно виконується за допомогою допоміжної процедури . Параметрами цієї процедури є масив і числа , що вказують на межі об’єднуваних ділянок. Процедура передбачає, що та що ділянки і вже відсортовані, і зливає (merges) їх до однієї ділянки 

Сортування купою (пірамідальне сортування) базується на ви-користанні сортувального дерева (бінарної купи). Сортувальне дерево – це та-ке двійкове дерево, у якого виконані такі умови.

1. Кожен листок має глибину або , або , де – максимальна гли-бина дерева.

2. Значення в будь вершини не менше (інший варіант – не більше) від значення її нащадків.

Зручна структура даних для сортувального дерева – такий масив , що – елемент в корені, а нащадки елемента є і .

Алгоритм сортування буде складатися з двох основних кроків:

1. Побудова сортувального дерева, такого, щоб кожний нащадок був меншим за предка. Цей крок вимагає операцій.

2. Видалення елементів з кореня по одному за раз і перебудова дерева. Тобто на першому кроці обмінюємо і , перетворюємо в сортувальне дерево. Потім переставляємо і , перетворюємо в сортувальне дерево. Процес продовжується доти, поки в сортувальному дереві не залишиться один еле-мент. Тоді – упорядкована послідовність. Цей крок ви-магає операцій.

Алгоритм сортування підрахунком можна застосувати, якщо ко-жен з елементів сортованої послідовності – ціле позитивне число у відомому діапазоні (що не перевершує заздалегідь відомого ). Якщо , то алго-ритм сортування підрахунком працює за час .

Ідея цього алгоритму полягає в тому, щоб для кожного елемента зазда-легідь підрахувати, скільки елементів вхідної послідовності менше , після чо-го записати безпосередньо у вихідний масив відповідно за цим числом (як-що, скажімо, 17 елементів вхідного масиву менше , то у вихідному масиві повинен бути записаний за номером 18). Якщо в послідовності, яку необхідно відсортувати, є однакові числа, то цю схему необхідно модифікувати, щоб не записати кілька чисел на одне місце.

 

 

Розробити програму, яка читає з клавіатури:

1) числа

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

3) послідовність ключів.

Програма зберігає першу послідовність до масиву та виконує сортуван-ня. Потім програма виводить відсортовану послідовність на екран та виконує бінарний пошук кожного елемента другої послідовності : для кожного по-відомити, чи є він у першій послідовності, а якщо є, то на якому місці.

 

 

Варіант 1: сортування бульбашкою.

Варіант 2: сортування включенням.

Варіант 3: швидке сортування.

Варіант 4: сортування злиттям.

Варіант 5: сортування купою.

Варіант 6: сортування підрахунком (для цілих чисел).

 

 

Мета роботи: познайомитися з генераторами випадкових чисел та ме-тодами перевірки випадковості.

 

 

Лінійний конгруентний метод застосовується в простих випадках і не має криптографічної стійкості.

Лінійний конгруентний метод полягає в обчисленні членів лінійної ре-курентної послідовності за модулем деякого натурального числа , що задається такою формулою:

де і – деякі коефіцієнти, цілі числа.

Отримана послідовність залежить від вибору стартового числа, і при різ-них його значеннях виходять різні послідовності випадкових чисел. Разом з тим багато властивостей цієї послідовності визначаються вибором коефіцієн-тів у формулі і не залежать від вибору стартового числа.

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

Один з найбільш поширених датчиків Фібоначчі оснований на наступній формулі:

де – дійсні числа з діапазону ;

– цілі позитивні числа, які називаються лагами.

При реалізації через цілі числа досить формули (при цьому будуть відбуватися арифметичні переповнення). Для роботи датчика Фібоначчі потрібно знати попередніх згенерованих випадкових чи-сел, які можуть бути згенеровані простим конгруентним датчиком.

Лаги і – «магічні» і їх не слід вибирати довільно. Рекомендуються наступні значення лагів:

Статистичні тести видають числову характеристику послідовності і дозволяють однозначно сказати, чи пройдено тест. Розглянемо кілька тестів пакета NIST.

Частотний побітовий тест полягає у визначенні співвідношення між нулями і одиницями у всій двійковій послідовності. Мета – з’ясувати, чи дійсно число нулів і одиниць у послідовності приблизно однакові, як це можна було б припустити у випадку істинно випадкової бінарної послідовності. Тест оцінює, наскільки близька частка одиниць до . Таким чином, число нулів і одиниць має бути приблизно однаковим. Якщо обчислене в ході тесту значен-ня ймовірності , то дана двійкова послідовність не є істинно випадко-вою. В іншому випадку послідовність має випадковий характер.