Завдання до лабораторної роботи

МЕТОДИЧНІ ВКАЗІВКИ

до виконання лабораторних робіт студентів з дисципліни

“ТЕОРІЯ АЛГОРИТМІВ”

для студентів I курсу денної форми навчання

Напрям підготовки – комп’ютерні науки

Одеса 2014

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ОДЕСЬКИЙ ДЕРЖАВНИЙ ЕКОЛОГІЧНИЙ УНІВЕРСИТЕТ

Затверджено

Проректор з методичної роботи

______________Хохлов В.М.

МЕТОДИЧНІ ВКАЗІВКИ

до виконання лабораторних робіт студентів з дисципліни

“Теорія алгоритмів”

для студентів I курсу денної форми навчання

Напрям підготовки – комп’ютерні науки

Затверджено на засіданні кафедри

інформаційних технологій

протокол №________

від "___"____________ 2014 р.

Завідувач кафедри

______________ Препелиця Г.П.

Затверджено на засіданні

Мета роботи

Метою лабораторної роботи є отримання практичних навичок визначати часову складність алгоритму. Познайомитися з алгоритмами на НСД, НСК, алгоритм Євклида, алгоритм "Решето Ератосфена". Навчитися будувати алгоритми з мінімальною часовою складністю для вирішення поставлених задач.

Завдання до лабораторної роботи

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

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

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

- Поняття алгоритму, властивості. Алгоритмічні системи.

- Поняття складності обчислення. Функція складності обчислень (за часом).

- Класи складності.Опис класів P і NP. Приклади NP-повних задач. Проблема перебору (P = NP?). Застосування теорії NP-повноти для аналізу складності завдань.

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

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

Основними мірами обчислювальною складності алгоритмів є:

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

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

Часова та ємнісна складність тісно пов'язані між собою. Обидві є функціями від розміру вхідних даних.

Надалі обмежимося тільки аналізом часової складності.

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

Асимптотичні позначення

- «О велике». Цей клас складається з функцій, що ростуть не швидше функції .

Визначення. Кажуть, що f(n) = O (g(n)), якщо існує така константа с > 0, що для будь-якого n виконується нерівність: |f(n)| <= с |g(n)|.

Оскільки і розмір вхідних даних, і кількість операцій є величинами невід'ємними (а фактично - додатними), модулі можна опустити.

- «Омега велике». Клас функцій, що ростуть принаймні так само швидко як функція .

Визначення. Кажуть, що f(n) = (g(n)), якщо існує така константа с > 0, що для будь-якого n виконується нерівність: f(n) ≥ с g(n).

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

Визначення. Кажуть, що f(n) = (g(n)), якщо існує такі константи с₁ > 0, с₂>0, що для будь-якого n виконується нерівність: с₁ g(n)≤ f(n) ≤с₂ g(n).

Виділяють такі основні класи алгоритмів:

- логарифмічні: f(n) = O (log₂n);

- лінійні: f(n) = O (n);

- поліноміальні: f(n) = O (n^m); тут m ̶ натуральне число, більше від одиниці; при m = 1 алгоритм є лінійним;

- експоненційні: f(n) = O (aⁿ); a ̶ натуральне число, більше від одиниці.

Для однієї й тієї ж задачі можуть існувати алгоритми різної складності.

Приклади аналізу алгоритмів

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

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

Алгоритм MaxElement

// Вхідні дані: масив дійсних чисел

// Вихідні дані: повертається значення найбільшого елементу масиву A

Очевидно, що в цьому алгоритмі розмір вхідних даних треба оцінювати по кількості елементів в масиві, тобто числом . Операції, що виконуються найчастіше, знаходяться у внутрішньому циклі алгоритму. Таких операцій дві: порівняння та привласнення . Яку з них вважати базовою? Оскільки порівняння виконується на кожному кроці циклу, а привласнення – ні, логічно вважати, що основною операцією алгоритму є операція привласнення. (Зверніть увагу, що для будь-якого масиву розміром n кількість операцій порівняння в даному алгоритмі постійна. Тому не требо окремо розглядати ефективність алгоритму для гіршого, середнього і кращого випадків).

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

Приклад 2. Розглянемо задачу знаходження максимального елемента в матриці

Цю задачу можна вирішити за допомогою приведеного нижче нескладного алгоритму.

Алгоритм MaxElements

// Вхідні дані: масив дійсних чисел

// Вихідні дані: повертається значення max

Max=A[0][0];

;}

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

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

Таким чином, отримаємо:

Задача знаходження максимального елемента в матриці має складність О(n²).

Приклад 3. Розглянемо задачу перевірки єдиності елементів. Іншими словами, треба переконатися, що усі елементи масиву різні. Цю задачу можна вирішити за допомогою приведеного нижче нескладного алгоритму.

Алгоритм Elements

// Вхідні дані: масив дійсних чисел

// Вихідні дані: повертається значення true, якщо усі елементи масиву

// різні, та falseу іншому випадку.

boolean l=true;

{

{

l=false;}}

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

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

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

Приклад 4. Розглянемо алгоритм Решето Ератосфена. Решето Ератосфена ̶ це алгоритм знаходження простих чисел до заданого числа n. У процесі виконання даного алгоритму поступово відсіваються складені числа, кратні простим, починаючи з 2.

Цю задачу можна вирішити за допомогою приведеного нижче нескладного алгоритму.

Оцінимо складність алгоритму. Перше викреслення вимагає n / 2 дій, друге ̶ n / 3, третє ̶ n / 5 і т. д. За формулою Мертенса

.

Так що для решета Ератосфена буде потрібно O (n log log n) операцій. Споживання пам'яті ж складе O (n).

План аналізу ефективності алгоритмів:

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

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

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

4. запишіть суму, що виражає кількість виконуваних основних операцій алгоритму;

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

Контрольні питання

1. У чому полягає задача аналізу алгоритмів?

2. Які два види ефективності розглядаються у даному курсі?

3. У чому вимірюється час роботи алгоритму?

4. Як відбувається оцінка вхідних даних?

5. Які існують випадки вхідних даних?

6. Що таке порядок зростання алгоритмів? Які класи зростання ви знаєте?

7. У чому полягає асимптотичний аналіз алгоритмів?

8. Які асимптотичні позначення ви знаєте?

Завдання до лабораторної роботи

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

2. Побудувати алгоритм знаходження n-го простого числа.

3. Побудувати алгоритм знаходження біноміального коефіцієнта Cn ^k для цілих n та k, де 0≤k≤n . Використайте наступні співвідношення:

C_n ⁰=C_n ⁿ=1,C_n+1 ^k+1=C_n .^k+1.+C_n ^k.

4. Побудувати алгоритм знаходження всіх натуральних розв'язків нерівності

x²+y².<n для заданого натурального числа n.

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

6. Побудувати алгоритм, який для заданого цілого числа x шукатиме найбільш близикий до √x дріб n/m , де m<100 .

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

8. Побудувати алгоритм знаходження суми 1/0!+ 1/1!+ 1/2!+..... +1/n! , складність якого була б лінійною.

9. Є 25 золотих монет. Всі вони мають однакову вагу, за винятком однієї монети з дефектом, яка важить менше інших. Розробіть алгоритм, що визначає дефект за три зважування. Яка максимальна кількість монет, для яких можна визначити монету з дефектом не більш ніж за три зважування на вагах з чашками?

10. Три місіонери і три канібали знаходяться на одному березі річки; човен може перевезти двох чоловік. Всі вони хочуть перебратися через річку. Не можна допустити, щоб на одному березі знаходилася група місіонерів з численнішою групою канібалів. Розробіть процедуру, що дозволяє всім шістьом перебратися через річку.

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

12. Побудувати алгоритм знаходження найбільшої спільної підпослідовності двох послідовностей.

13. Побудувати алгоритм, який набиратиме суму N копійок з набору монет 1, 2, 5,10, 25 та 50 копійок.