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

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

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

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

 

 

Розробити програму, яка читає з клавіатури число та параметри генератора випадкових чисел і виводить на екран послідовність з згенерованих чисел. Програма зберігає до файлу графічну характеристику по-слідовності згідно з завданням та виводить на екран результат одного з тестів NIST (згідно з варіантом завдання).

Варіанти генераторів випадкових чисел:

1) лінійний конгруентний метод;

2) метод Фібоначчі із затримуванням.

Варіанти графічних характеристик:

1) гістограма розподілу елементів послідовності;

2) розподіл на площині (елементи попарно обробляються як координати точок (x, y));

3) автокореляція (користувач задає зсув для копії послідовності).

Варіанти тестів NIST:

1) частотний побітовий тест;

2) тест на послідовність однакових бітів;

3) тест на найдовшу послідовність одиниць.

 

 

В таблиці 5.1 наведені варіанти завдань до даної лабораторної роботи.

 

 

 

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

 

 

Структури даних та алгоритми, які потрібно використати, розглянуто в лекційному курсі, а також в запропонованій літературі.

 

 

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

1) числа – кількість вершин та ребер графа;

2) послідовність M пар цілих чисел – ребра графа.

Програма зберігає граф та виконує над ним алгоритм згідно з варіантом.

Варіанти подання графів:

1. Матриця суміжності.

2. Список суміжності.

Варіанти алгоритмів:

1. Пошук в ширину. На екран потрібно вивести вершини в порядку об-ходу. Для кожної вказати час прибуття та предка в дереві обходу.

2. Пошук у глибину. На екран потрібно вивести вершини в порядку об-ходу. Для кожної вказати час початку розгляду, кінця розгляду та предка у де-реві обходу.

1. Топологічне сортування. На екран потрібно вивести ті ж дані, що і для пошуку в глибину, а також результат сортування.

2. Визначити, чи є заданий граф деревом або лісом.

3. Побудувати кістяк дерева алгоритмом Прима.

4. Побудувати кістяк дерева алгоритмом Крускала.

6.3 Варіанти завдань до лабораторної роботи 6

В таблиці 6.1 наведені варіанти завдань до даної лабораторної роботи.

 

 

 

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

 

 

Основний засіб багатьох геометричних алгоритмів – поняття векторного добутку.

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

Для обчислень більш зручне визначення векторного добутку як визнач-ника матриці .

Якщо позитивне, то найкоротший поворот відносно , що поєднує його з , відбувається проти годинникової стрілки, а якщо негативне, то за нею.

Алгоритми побудови опуклої оболонки розглянуте у лекційному курсі, а також у запропонованій літературі.

 

 

Розробити програму, яка читає з клавіатури число та пар дійсних чисел-координат точок на площині. Програма виконує один з алгоритмів згідно з варіантом.

 

 

Варіант 1. Точки належать ламаній. Потрібно для