Лаба ОТА1 КН221Д. Метод_Лаб_OТА_2021. Методичні вказівки по виконанню лабораторних робіт за курсом Основи теорії алгоритмів

Название	Методичні вказівки по виконанню лабораторних робіт за курсом Основи теорії алгоритмів
Анкор	Лаба ОТА1 КН221Д
Дата	15.04.2022
Размер	275.2 Kb.
Формат файла
Имя файла	Метод_Лаб_OТА_2021.odt
Тип	Методичні вказівки #477386

Міністерство освіти та науки України

Національний технічний університет

«Харківський політехнічний інститут»

Кафедра «Програмна інженерія та інформаційні технології управління»

Методичні вказівки

по виконанню

лабораторних робіт

за курсом «Основи теорії алгоритмів»

для студентів, які навчаються за спеціальністю

“Інженерія програмного забезпечення ”

Харків 2021

Методичні вказівки по виконанню лабораторних робіт за курсом «Основи теорії алгоритмів» для студентів, які навчаються спеціальністю “Інженерія програмного забезпечення ”

Укладач: Стратієнко Н.К.

ЗМІСТ

Рекомендації щодо виконання робіт 5

1Лабораторна робота 1. Базові структури даних 7

1.1Методичні вказівки 7

1.2Завдання 8

1.3Варіанти завдань 8

2Лабораторна робота 2. Базові структури даних. Хеш-таблиці 9

2.1Методичні вказівки 9

2.2Завдання 10

2.3Варіанти завдань 11

3Лабораторна робота 3. Базові структури даних: червоно-чорні дерева 12

3.1Методичні вказівки 12

3.2Завдання 13

3.3Варіанти завдань 13

4Лабораторна робота 4. Алгоритми сортування 15

4.1Методичні вказівки 15

4.2Завдання 17

4.3Варіанти завдань 17

5Лабораторна робота 5. Комбінаторні алгоритми 19

5.1Методичні вказівки 19

5.2Завдання 21

5.3Варіанти завдань 21

6Лабораторна робота 6. Фундаментальні алгоритми на графах і деревах 23

6.1Методичні вказівки 23

6.2Завдання 23

6.3Варіанти завдань 23

7Лабораторна робота 7. Геометричні алгоритми 25

7.1Методичні вказівки 25

7.2Завдання 25

7.3Варіанти завдань 25

8Лабораторна робота 8. Динамічне програмування 27

8.1Методичні вказівки 27

8.2Завдання 27

8.3Варіанти завдань 27

9Лабораторна робота 9. Жадібні алгоритми 29

9.1Методичні вказівки 29

9.2Завдання 29

9.3Варіанти завдань 29

Рекомендована література 30

1Лабораторна робота 1. Базові структури даних

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

1.1Методичні вказівки

Стеки і черги - це динамічні множини, в яких елемент, що видаляється з множини операцією Delete, що не задається довільно, а визначається структурою множини. Саме, зі стеку (stack) можна видалити тільки той елемент, який був у нього доданий останнім: стек працює за принципом «останнім прийшов - першим пішов» (last-in, first-out - LIFO). З черги (queue), навпаки, можна видалити тільки той елемент, який знаходився в черзі довше всього: працює принцип «першим прийшов - першим пішов» (first-in, first-out — FIFO).

У зв'язаному списку (або просто списку; linked list) елементи лінійно впорядковані, але порядок визначається не номерами, як у масиві, а покажчиками, що входять до складу елементів списку. Списки є зручним способом реалізації динамічних множин.

Якщо кожен стоїть у черзі запам'ятає, хто за ним стоїть, після чого все безладно розсядуться на лавочці, вийде однобічно пов'язаний список; якщо він запам'ятає ще й того, хто попереду, буде двобічно зв'язаний список.

Іншими словами, елемент двобічно зв'язаного списку (doubly linked list) - це запис, що містить три поля: key (ключ) і два покажчика next (наступний) і prev (попередній). Крім цього, елементи списку можуть містити додаткові дані.

У різних ситуаціях використовуються різні види списків. В одне сторін незв'язаному (singly linked) списку відсутні поля prev. У впорядкованому (sorted) списку елементи розташовані в порядку зростання ключів, так що у голови списку ключ найменший, а у хвоста списку - найбільший, на відміну від неврегульованого (unsorted) списку. У кільцевому списку (circularlist) поле prev голови списку вказує на хвіст списку, а поле next хвоста списку вказує на голову списку.

1.2Завдання

Розробити програму, яка читає з клавіатури послідовність N цілих чисел (1 < N < 256), жодне з яких не повторюється, зберігає їх до структури даних (згідно завданню) та видає на екран наступні характеристики:

кількість елементів;
середнє арифметичне збережених елементів;
мінімальний та максимальний елемент;
четвертий елемент послідовності;
елемент, що йде перед мінімальним елементом.

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

Використовувати готові реалізації структур даних (наприклад, STL) заборонено.

1.3Варіанти завдань

Використати наступні структури даних.

Черга.
Стек.
Однобічно зв’язний список.
Двобічно зв’язний список.
Кільцевий список.
Масив із довільним доступом.

2Лабораторна робота 2. Базові структури даних. Хеш-таблиці

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

2.1Методичні вказівки

Часто бувають потрібні динамічні множини, що підтримують тільки «словникові операції» додавання, пошуку і видалення елемента. У цьому випадку часто застосовують так зване хешування; відповідна структура даних називається «хеш-таблиця». У гіршому випадку пошук в хеш-таблиці може займати стільки ж часу, скільки пошук у списку (

), але на практиці хешування вельми ефективно.

У той час як при прямій адресації елементу з ключем

відводиться позиція номер k, при хешуванні цей елемент записується в позицію номер

в хеш-таблиці (hashtable)

, де

- деяка функція, звана хеш-функцією (hash function).

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

хеш-значень повинні бути рівноймовірні.

Тривіальне хешування полягає у використанні хеш-функції, що повертає власний аргумент.

Побудова хеш-функції методом ділення із залишком (division method) полягає в тому, що ключу

ставиться у відповідність залишок від ділення

на

, де

- число можливих хеш-значень:

.

Наприклад, якщо розмір хеш-таблиці

і ключ дорівнює 100, то хеш-значення дорівнює 4.

Хороші результати зазвичай виходять, якщо вибрати в якості

просте число, далеко відстоїть від ступенів двійки.

Побудова хеш-функції методом множення (multiplication method) полягає в наступному. Нехай кількість хеш-значень дорівнює

. Зафіксуємо константу

в інтервалі

, і покладемо

, де

- дрібна частина

.

Перевага методу множення в тому, що якість хеш функції мало залежить від вибору

. Звичайно як

вибирають ступінь двійки, оскільки в більшості комп'ютерів множення на таке

реалізується як здвигання слова.

Хешування Пірсона (Pearson hashing) - алгоритм, запропонований Пітером Пірсоном для процесорів з 8-бітними регістрами, завданням якого є швидке обчислення хеш-коду для рядка довільної довжини. На вхід функція виходить слово

, що складається з

символів, кожен розміром 1 байт, і повертає значення в діапазоні від 0 до 255. Значення хеш-коду залежить від кожного символу вхідного слова.

Алгоритм можна описати таким кодом мовою Python, який отримує на вхід рядок w і використовує таблицю перестановок T:

def hash_pearson(w):

h = 0

for c in w:

index = h ^ ord(c)

h = T[index]

return h

2.2Завдання

Розробити програму, яка читає з клавіатури цілі числа N, M (1 < N, M < 256), N пар <ключ, значення> (ключ — ціле, дійсне число або рядок в залежності від варіанту завдання; значення — рядок; усі рядки до 255 символів), жодний з яких не повторюється та ще M ключів. Всі рядки розділяються пробілом або новим рядком. Програма зберігає пар рядків до хеш-таблиці та видає на екран значення, що відповідають переліченим ключам.

Приклад входу для ключів-рядків.

3 2

abc x

gh yq

io qw

gh

io

Вихід.

yq

qw

Використовувати готові реалізації структур даних (наприклад, STL) заборонено, але можна використати реалізацію рядків (наприклад, std::string у C++).

2.3Варіанти завдань

Ключ — ціле число; тривіальне хешування.
Ключ — ціле число; хешування за допомогою ділення.
Ключ — ціле число; мультиплікативне хешування.
Ключ — дійсне число; мультиплікативне хешування.
Ключ — рядок; хешування за остачею суми символів.
Ключ — рядок; хешування Пірсона.

3Лабораторна робота 3. Базові структури даних: червоно-чорні дерева

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

3.1Методичні вказівки

Дерева у якості реалізації словників ефективні, якщо їх висота мала, але мала висота не гарантується, і в гіршому випадку дерева не більш ефективні, ніж списки. Червоно-чорні дерева - один з типів збалансованих дерев пошуку, в яких передбачені операції балансування, гарантують, що висота дерева не перевищить O (lg n).

Червоно-чорне дерево (red-black tree) - це двійкове дерево пошуку, вершини якого розділені на червоні (red) і чорні (black). Таким чином, кожна вершина зберігає один додатковий біт - її колір.

При цьому повинні виконуватися певні вимоги, які гарантують, що глибини будь-яких двох листя відрізняються не більше ніж у два рази, тому дерево можна назвати збалансованим (balanced).

Кожна вершина червоно-чорного дерева має поля color (колір), key (ключ), left (лівий дитина), right (правий дитина) і p (батько). Якщо у вершини відсутня дитина або батько, відповідне поле містить nil. Для зручності ми будемо вважати, що значення nil, що зберігаються в полях left і right, є посиланнями на додаткові (фіктивні) листя дерева. У такому поповнень дереві кожна стара вершина (що містить ключ) має двох дітей.

Двійкове дерево пошуку називається червоно-чорним деревом, якщо воно має такі властивості (будемо називати їх RB-властивостями, red-black properties).

Кожна вершина - або червона, або чорна.
Кожен лист (nil) - чорний.
Якщо вершина червона, обидва її дитини чорні.
Всі шляхи, що йдуть вниз від кореня до листя, містять однакову кількість чорних вершин.

Операції Tree-Insert і Tree-Delete виконуються на червоно-чорному дереві за час O (lg n), але вони змінюють дерево, і результат може не володіти RB-властивостями. Щоб відновити ці властивості, треба перефарбувати деякі вершини і змінити структуру дерева.

Детально процес повороту та модифікації червоно-чорного дерева описано у лекційному курсі.

3.2Завдання

Розробити програму, яка читає з клавіатури числа N, M (1 < N, M < 256); послідовність N ключів (цілих, дійсних чисел або рядків (до 255 символів) в залежності від варіанту завдання); послідовність M ключів. Програма зберігає першу послідовність до червоно-чорного дерева.

Кожного разу, коли до дерева додається новий елемент, потрібно вивести статистику (згідно варіанту завдання).

Мінімальний елемент та його колір;
Максимальний елемент та його колір.

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

Чи є елемент у дереві та його колір.
Successor(x) та його колір.
Predecessor(x) та його колір.

Використовувати готові реалізації структур даних (наприклад, STL) заборонено, але можна використати реалізацію рядків (наприклад, std::string у C++).

3.3Варіанти завдань

1.1.
1.2.
1.3.
2.1.
2.2.
2.3.

4Лабораторна робота 4. Алгоритми сортування

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

4.1Методичні вказівки

Багато алгоритми використовують сортування в якості проміжного кроку. Є багато різних алгоритмів сортування; вибір в конкретній ситуації залежить від довжини сортованої послідовності, від того, якою мірою вона вже відсортована, а також від типу наявної пам'яті.

Сортування бульбашкою (bubble sort) складається з повторюваних проходів по сортованого масиву. За кожен прохід елементи послідовно порівнюються попарно і, якщо порядок у парі невірний, виконується обмін елементів. Проходи по масиву повторюються N-1 раз або до тих пір, поки на черговому проході не опиниться, що обміни більше не потрібні, що означає - масив відсортований. При кожному проході алгоритму по внутрішньому циклу, черговий найбільший елемент масиву ставиться на своє місце в кінці масиву поруч з попереднім найбільшим елементом, а найменший елемент переміщається на одну позицію до початку масиву ("спливає" до потрібної позиції, як бульбашка у воді, звідси і назва алгоритму).

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

Швидке сортування засноване на принципі «розділяй і володарюй». Сортування ділянки

відбувається так:

Елементи масиву переставляються так, щоб будь-який з елементів був не більший будь-якого з елементів , де - деяке число в інтервалі. Цю операцію ми будемо називати поділом (partition).
Процедура сортування рекурсивно викликається для масивів і .
Після цього масив відсортований.

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

Нетривіальною частиною є з'єднання двох упорядкованих масивів в один. Воно виконується за допомогою допоміжної процедури

. Параметрами цієї процедури є масив

і числа

, що вказують кордону зливаних ділянок. Процедура передбачає, що

та що ділянки

вже відсортовані, і зливає (merges) їх до однієї ділянки

.

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

Кожен лист має глибину або , або , - максимальна глибина дерева.
Значення в будь вершини не менше (інший варіант - не більше) значення її нащадків.

Зручна структура даних для сортувального дерева - такий масив

, що

- елемент в корені, а нащадки елемента

.

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

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

Алгоритм сортування підрахунком можна застосувати, якщо кожен з

елементів сортованої послідовності - ціле позитивне число у відомому діапазоні (що не перевершує заздалегідь відомого

). Якщо

, то алгоритм сортування підрахунком працює за час

.

Ідея цього алгоритму в тому, щоб для кожного елемента

заздалегідь підрахувати, скільки елементів вхідної послідовності менше

, після чого записати

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

, то в вихідному масиві

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

4.2Завдання

Розробити програму, яка читає з клавіатури числа N, M (1 < N, M < 256); послідовність N ключів (цілих або дійсних чисел в залежності від варіанту завдання); послідовність M ключів. Програма зберігає першу послідовність до масиву та виконує сортування. Потім програма виводить відсортовану послідовність на екран та виконує бінарний пошук кожного елементу другої послідовністі x: для кожного x повідомити, чи є він у першій послідовністі, а якщо є, то на якому місці.

4.3Варіанти завдань

Сортування бульбашкою.
Сортування включенням.
Швидке сортування.
Сортування злиттям.
Сортування купою.
Сортування підрахунком (для цілих чисел).

5Лабораторна робота 5. Комбінаторні алгоритми

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

5.1Методичні вказівки

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

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

, що задається наступною формулою:

, де

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

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

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

, де

- дійсні числа з діапазону [0, 1),

- цілі позитивні числа, звані лагами. При реалізації через цілі числа досить формули

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

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

Лаги a і b - «магічні» і їх не слід вибирати довільно. Рекомендуються наступні значення лагів: (a, b) = (55,24), (17,5) або (97,33).

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

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

. Таким чином, число нулів і одиниць має бути приблизно однаковим. Якщо обчислена в ході тесту значення ймовірності

, то дана двійкова послідовність не є істинно випадковою. В іншому випадку, послідовність носить випадковий характер. Варто відзначити, що всі наступні тести проводяться за умови, що пройдено даний тест.

Тест на послідовність однакових бітів полягає в підрахунку повного числа рядів у вихідній послідовності, де під словом «ряд» мається на увазі безперервна підпослідовність однакових бітів. Ряд довжиною

біт складається з

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

, то дана двійкова послідовність не є істинно випадковою. В іншому випадку, вона носить випадковий характер.

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

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

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

5.2Завдання

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

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

Лінійний конгруентний метод.
Метод Фібоначчі із затримуванням.

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

Гістограма розподілу елементів послідовності.
Розподіл на площині (елементи попарно обробляються як координати точок (x, y)).
Автокореляція (користувач задає зсув для копії послідовності).

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

Частотний побітовий тест.
Тест на послідовність однакових бітів.
Тест на найдовшу послідовність одиниць.

5.3Варіанти завдань

1.1.1.
1.1.2.
1.1.3.
1.2.1.
1.2.2.
1.2.3.
1.3.1.
1.3.2.
1.3.3.
2.1.1.
2.1.2.
2.1.3.
2.2.1.
2.2.2.
2.2.3.
2.3.1.
2.3.2.
2.3.3.

6Лабораторна робота 6. Фундаментальні алгоритми на графах і деревах

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

6.1Методичні вказівки

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

6.2Завдання

Розробити програму, яка читає з клавіатури числа N, M (1 < N, M < 256) — кількість вершин та ребер графу; послідовність M пар цілих чисел - ребра графу. Програма зберігає граф та виконує над ним алгоритм згідно варіанту.

Варіанти представлення графів.

Матриця суміжності.
Список суміжності.

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

Пошук у ширину. На екран потрібно вивести вершини у порядку обходу. Для кожної вказати час прибуття та предка у дереві обходу.
Пошук у глибину. На екран потрібно вивести вершини у порядку обходу. Для кожної вказати час початку розгляду, кінця розгляду та предка у дереві обходу.
Топологічне сортування. На екран потрібно вивести ті ж дані, що і для пошуку в глибину, а також результат сортування.
Визначити, чи є заданий граф деревом або лісом.
Побудувати остовне дерево алгоритмом Прима.
Побудувати остовне дерево алгоритмом Крускала.

6.3Варіанти завдань

1.1.
1.2.
1.3.
1.4.
1.5.
1.6.
2.1.
2.2.
2.3.
2.4.
2.5.
2.6.

7Лабораторна робота 7. Геометричні алгоритми

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

7.1Методичні вказівки

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

Нехай дано вектора

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

можна розуміти площа паралелограма (з урахуванням знаку), утвореного точками

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

.

Якщо

позитивне, то найкоротший поворот

відносно (0, 0), що поєднує його з

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

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

7.2Завдання

Розробити програму, яка читає з клавіатури число N (1 < N < 256) та N пар дійсних чисел — координати точок на площині. Програма виконує один за алгоритмів згідно варіанту.

7.3Варіанти завдань

Точки належать ламаній. Потрібно для кожної нової ланки вказати, направо чи наліво здійснено поворот.
Точки належать ламаній. Потрібно для кожної нової ланки вказати, чи перетинає вона будь-яку з попередніх.
Точки є координатами багатокутника в порядку обходу. Вивести площину багатокутника та повідомити, по чи проти годинникової стрілки здійснено обхід.
Побудувати опуклу оболонку наданих точок алгоритмом Грехема.
Побудувати опуклу оболонку наданих точок алгоритмом Джарвіса.

8Лабораторна робота 8. Динамічне програмування

Мета роботи: навчитися використовувати динамічне програмування та оцінювати його складність.

8.1Методичні вказівки

8.2Завдання

Розробити програму, яка читає з клавіатури вхідні дані та розв’язує задачу методом динамічного програмування. Визначити складність алгоритму.

8.3Варіанти завдань

Пошук маршруту на прямокутному полі так, щоб сума чисел у клітинах, через які він іде, була максимальною. Рух починається із клітинки верхнього лівого кута та завершується у правому нижньому. Кожний крок виконується на одну позицію праворуч або вниз. Вхідні дані: натуральні числа N, M (1< N, M < 256) та послідовність N * M натуральних чисел — прямокутне поле рядок за рядком. Вихідні дані: таблиця динамічного програмування ( = максимальна сума маршруту до клітинки (i, j)); прямокутне поле із маршрутом, що відмічено зірочками, та сума чисел у клітинках маршруту.
Пошук найбільшої спільної підпослідовності. Вхідні дані: натуральні числа N, M (1< N, M < 256) та дві послідовності X та Y натуральних чисел довжиною N та M відповідно. Вихідні дані: динамічна таблиця ( = довжина НСП для префіксів та ) та НСП для X та Y.
Пошук оптимального способу множення матриць. Вхідні дані: натуральне число N (1 < N < 256) — кількість матриць, натуральні числа - розмірності матриць (матриця має розмірність ). Вихідні дані: таблиця динамічного програмування ( = найменша кількість множень для обчислення добутку матриць ) та оптимальна розстановка дужок у виразі .

9Лабораторна робота 9. Жадібні алгоритми

Мета роботи: навчитися використовувати жадібні алгоритми та оцінювати їхню складність.

9.1Методичні вказівки

9.2Завдання

Розробити програму, яка читає з клавіатури вхідні дані та розв’язує задачу жадібним алгоритмом. Визначити складність алгоритму.

9.3Варіанти завдань

Розв’язати задачу про вибір найбільшої кількості заявок для аудиторії. Вхідні дані: кількість заявок N (1 < N < 256), N пар натуральних чисел - початок та кінець заявок . Вихідні дані: заявки, відсортовані за зростанням часу закінчення, та номери заявок, які потрібно обрати.
Стиснути послідовність нулів та одиниць алгоритмом Хаффмана. Вхідні дані: натуральні числа N, M (1 < N < 256, 1 < M < 9) та послідовність N груп по M нулів та одиниць. Вихідні дані: перелік кодів, які потрібно використати для кожної групи, та стиснута послідовність.
Розв’язати неперервну задачу про рюкзак. Вхідні дані: натуральні числа N, W (1 < N < 256, 1 < W < 1024) — кількість видів товару та місткість рюкзака, послідовність N пар p[i], v[i] — вартість та вага товару номер i. Вихідні дані: набір дійсних чисел, які вказують, скільки кожного товару потрібно покласти до рюкзаку, щоб сумарна вартість була максимальною.