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

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

національний університет “Львівська політехніка”

 

Кафедра ЕОМ

 

 

 

Аналіз складності алгоритмів

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

До лабораторної роботи № 3

 

з дисципліни

" AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ"

 

для студентів напряму

6.050102 “Комп’ютерна інженерія”

 

 

 

 

Львів – 2010

Методичні вказівки до комплексу лабораторних робіт з дисципліни "AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ" для підготовки студентів напряму 6.050102 “Комп’ютерна інженерія” / Укл. Т.А.Лисак – Львів: Видавництво НУ “Львівська політехніка”, 2010 – 18 с.

 

 

Укладач: Матвейчук Т.А., ст. викладач каф.ЕОМ

 

Відповідальний

за випуск: Мельник А.О., д-р техн. наук, проф.

 

 

Рецензенти: Мороз І.В., ст. викладач каф.ЕОМ

 

Юрчак І.Ю., доцент кафедри САПР, к.т.н.

 

МЕТА РОБОТИ

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

ТЕОРЕТИЧНІ ВІДОМОСТІ

Складність алгоритмів

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

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

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

Саме асимптотична складність визначає розмір задач, які алгоритм здатен обробити. Наприклад, якщо алгоритм обробляє вхідні дані розміром n за час cn², де c - деяка стала, то кажуть, що часова складність такого алгоритму O(n²).

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

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

В основах аналізу алгоритмів до одного класу відносять всі функції, чий порядок росту однаковий з точністю до постійного множника. Ці класи, їх назви, а також деякі пояснення та приклади, наведені в таблиці 1 у відповідності до зростання їхнього порядку росту. Функції, які зростають повільніше, наведені першими. В таблиці прийнято, що n ∞, с - константа.

 

Таблиця 1. Основні асимптотичні класи ефективності

Часова складність	Назва класу	Коментар	Приклади
O(1)	Константний	Сталий час роботи не залежно від розміру задачі	Індексація масиву
O(log log n)	Log log n	Дуже повільне зростання необхідного часу	Очікуваний час роботи інтерполюючого пошуку n елементів
O(log n)	Логарифмічний	Логарифмічне зростання — под-воєння розміру задачі збільшує час роботи на сталу величину	Обчислення x^n, двійковий пошук в масиві з n елементів
O(n)	Лінійний	Лінійне зростання — подвоєння розміру задачі подвоїть і необхідний час	Додавання / віднімання чисел з n цифр; лінійний пошук в масиві з n елементів
O(n log n)	Лінеаритмічний (або n-log-n)	Лінеаритмічне зростання — подвоєння розміру задачі збільшить необхідний час трохи більше ніж вдвічі	Сортування злиттям, швидке сортування
O(n²)	Квадратичний	Квадратичне зростання — подвоєння розміру задачі вчетверо збільшує необхідний час	Прості методи сортування
O(n³)	Кубічний	Кубічне зростання — подвоєння розміру задачі збільшує необхідний час у вісім разів	Звичайне множення матриць
O(n^с)	Поліноміальний	Поліноміальне зростання — подвоєння розміру задачі збільшує необхідний час в 2^с раз	Задача комівояжера
O(c^n)	Експоненціальний	Експоненціальне зростання — збільшення розміру задачі на 1 призводить до c -кратного збіль-шення необхідного часу; подво-єння розміру задачі підносить необхідний час у квадрат	Алгоритми пошуку повним перебором
O(n!)	Факторіальний	Факторіальне зростання — збільшення розміру задачі на 1 збільшує необхідний час в n+1 раз	Обробка всіх перестано-вок деякої множини, що складається з nелементів

2.2. Функція трудомісткості і система позначень

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

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

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

Нехай D_A — множина допустимих конкретних проблем даної задачі, що розв'язується алгоритмом А (наприклад, множина комбінацій розміщення елементів вхідного масиву для алгоритму сортування). — конкретна проблема (вхід алгоритму А), що представляє собою впорядковану множину елементів (слів) d:

У загальному випадку існує підмножина множини D_A, що містить всі конкретні проблеми, що мають розмірність n. Позначимо її через D_n:

Позначимо потужність множини D_n через М_Dn =|D_n|. Тоді алгоритм А, маючи на вході різні множини , буде, можливо, задавати в деякому випадку найбільшу, а в деякому випадку найменшу кількість операцій.

Введемо наступні позначення:

1. – найгірший випадок – найбільша кількість операцій, які необхідно виконати алгоритмом А для вирішення конкретної проблеми розмірністю n:

1. – найкращий випадок – найменша кількість операцій, які необхідно виконати алгоритмом А для вирішення конкретної проблеми розмірністю n:

1. – середній випадок – середня кількість операцій, які необхідно виконати алгоритмом А для вирішення конкретної проблеми розмірністю n:

.

 

ПОРЯДОК ВИКОНАННЯ РОБОТИ

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

2. Згідно з індивідуальним завданням розробити алгоритм розв’язання задачі.

3. Підготувати програмну реалізацію розробленого алгоритму. Засобами вбудованого тексто-вого редактора інтегрованого середовища набрати текст підготовленої програми. Відкомпілювати, налагодити та виконати програму.

4. Протестувати програму згідно зі складеною системою тестів і, при потребі, відкоректувати текст програми. Проаналізувати отримані результати.

5. Написати контрольне опитування по темі.

6. Оформити звіт по роботі.

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

 

Завдання

Розробити алгоритм розв'язання задачі згідно з індивідуальним завданням. Визначити до якого класу (підкласу) належить цей алгоритм в залежності від тих факторів, що впливають на значення функції трудомісткості. Знайти функцію трудомісткості алгоритму, використовуючи методику аналізу основних алгоритмічних конструкцій та визначення набору "елементарних" операцій. Визначити часову складність алгоритму для великих розмірів вхідних даних. Для її позначення використати нотацію Ландау (велике O). Навести назву асимптотичного класу ефективності алгоритму. Пояснити, як збільшиться час роботи алгоритму при подвоєнні розміру задачі. Побудувати графік функції трудомісткості для різних значень n.

 

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

1. Заданi два вектори дiйсних чисел х та у, кожен з яких має n елементiв. Сформувати третiй вектор, вибравши в нього спiльнi елементи векторiв х та у.

2. Заданi двi послiдовностi по n цiлих чисел в кожнiй. Знайти мiнiмальний елемент першої послiдовностi, який не входять у другу послiдовнiсть.

3. Знайти мiнiмальньнi елементи в кожному рядку прямокутної матрицi дiйсних чисел розмiром n * m i записати їх в окремий одномiрний масив.

4. Задана послiдовнiсть iз n дiйсних чисел. Знайти середнє арифметичне чисел цiєї послiдовностi, якi розмiщенi мiж максимальним та мiнiмальними числами, включаючи цих два числа.

5. Змiннiй k логiчного типу присвоїти значення true в тому випадку, якщо масив n цiлих чисел впорядкований по зростанню, i значення false в iншому випадку.

6. Заданi два вектори дiйсних чисел х та у, кожен з яких має n елементiв. Сформувати третiй вектор, вибравши в нього елементи вектора х, що не входять у вектор у.

7. Задана матриця дiйсних чисел розмiром n * m. Помiняти мiсцями мiнiмальний та максимальний елементи (вважати, що такi елементи єдинi).

8. Задана квадратна матриця дiйсних чисел n-го порядку. Знайти суму елементів матриці, що знаходяться вище допоміжної дiагоналi.

9. Два масиви дiйсних чисел x та y впорядкованi по зростанню значень елементiв. Об'єднати цi масиви в один масив z так, щоб вони знову були впорядкованi по зростанню.

10. Елементи масиву x зсунути циклiчно на k позицiй влiво.

11. Елементи масиву з n дiйсних чисел записати у зворотньому порядку:

12. Продублювати всі непарні елементи заданої послідовності.

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

14. У заданій послідовності визначити кількість сусідств двох чисел різного знака.

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

16. Знайти найбільший парний елемент масиву.

17. Визначити три найбільших елемента заданої послідовності.

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

19. Переписати послідовність таким чином, щоб спочатку були всі від'ємні числа, потім всі нулі, а потім всі додатні числа, зберігаючи порядок їх слідування (не використовувати додаткових масивів, всі перетворення виконувати в масиві А).

20. Задана прямокутна матриця дiйсних чисел n * m елементiв. Елементи матрицi, якi потрапляють в iнтервал [а,b] записати в окремий вектор.

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

22.Перетворити послідовність A₁ , A₂ , …, An дійсніх чисел за таким правилом:

перший елемент дорівнює A₁;

другий = max (A₁ , A₂);

третій = max (A₁ , A₂, A₃);

...

останній = max (A₁ , A₂ , …, An).

23. Задана квадратна матриця цiлих чисел. Транспонувати цю матрицi (помiняти рядки зi стовпцями).

24. Задана квадратна матриця дiйсних чисел. Знайти середнє арифметичне додатнiх елементiв, якi знаходяться на головній дiагоналi.

25. Задана квадратна матриця дiйсних чисел n-го порядку. Знайти мiнiмальний елемент серед елементiв, якi знаходяться нижче головної дiагоналi.

ЗМІСТ ЗВІТУ

I. Оформити титульну сторінку звіту стандартного зразка, на якій обов’язково вказати номер лабораторної роботи, її назву та вибір номера варіанта.

 

 

II. В звіті мають бути відображені наступні пункти:

1. Мета роботи

2. Постановка задачі

2.1. Загальна частина

2.2. Індивідуальне завдання

3. Алгоритм розв’язання задачі

4. Дослідження складності алгоритму

4.1. Визначення класу (підкласу) алгоритму по його трудомісткості.

4.2. Обчислення функцій трудомісткості алгоритму.

а) для найкращого випадку;

б) для найгіршого випадку;

в) для середнього випадку.

4.3. Знаходження часової складності алгоритму (за нотацією Ландау).

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

4.5. Знаходження зміни часу роботи алгоритму при подвоєнні розміру задачі.

5. Результати виконання програми

Висновки

Додатки

 

 

IIІ. Змістовне наповнення пунктів:

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

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

В додатках розміщуються тексти програм з коментарями. Кожний додаток підписується, яка саме інформація в ньому надається.

 

КОНТРОЛЬНІ ПИТАННЯ ТА ЗАВДАННЯ

Задано 2 алгоритми: Алгоритм А: Алгоритм B: void A(int a[]){ int B(float a[],int n){ int k1=0,k2=0,n=6; float min=a[0]; for (int i=0;i<n;i++){ for(int N_min=0,k=0,i=1;i<n;i++){ if (a[i]%2==0) if (a[i]<min){ k1=k1+1; min=a[i]; else N_min=i; k2+=1; k++; } } cout<<k1<<k2; } } return N_min;   } 1) Знайти значення функції трудомісткості алгоритму А в найкращому випадку для n=6. 2) Знайти значення функції трудомісткості алгоритму А в найгіршому випадку для n=6. 3) Знайти значення функції трудомісткості алгоритму B в найкращому випадку для n=10. 4) Знайти значення функції трудомісткості алгоритму B в найгіршому випадку для n=10. 5) До якого класу відносно функції трудомісткості належить алгоритм А а) N б) PR в) NPRS г) NPRV 6) Який порядок має функція трудомісткості алгоритму B в найгіршому випадку: а) Ο(n) б) Ο(n2) в) Ο(log n) г) Ο(n∙log n) 7) Який порядок має функція трудомісткості алгоритму А в найкращому випадку: а) Ο(n) б) Ο(n2) в) Ο(log n) г) Ο(n∙log n)

СПИСОК ЛІТЕРАТУРИ

1. А.Ахо, Дж.Хопкрофт, Дж.Ульман, Д.Джеффри. Структуры данных и алгоритмы.; Пер. с англ.– М.:Изд.дом ”Вильямс”, 2001. – 384 с.

2. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. – М.:Мир, 2000.-360 с.

3. Кнут Д. Искусство програмирования, том 1. Основные алгоритмы. – М.:Изд.дом ”Вильямс”, 2001. – 720 с.

4. Кнут Д. Искусство програмирования, том 2. Получисленные алгоритмы. – М.:Изд.дом ”Вильямс”, 2001. – 763 с.

5. Кнут Д. Искусство програмирования, том 3. Сортировка и поиск. – М.: Изд.дом ”Вильямс”, 2001. – 832 с.

6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы, построение и анализ. Классические учебники: computer science – 2001. - 860 с.

7. Левитин, А. В. Алгоритмы: введение в разработку и анализ.: Пер. с англ. — М.:Издательский дом “Вильямс”, 2006. — 576 с.

8. Матьяш В.А., Путилов В.А., Фильчакрв В.В., Щекин С.В. Структуры и алгоритмы обработки данных. Учебное пособие. – Апатиты, КФ ПетрГУ, 2000 - 80 с.

9. Окулов С. М. Программирование в алгоритмах - М.: БИНОМ. Лаборатория знаний, 2002. — 341 с:

10. Kenneth A. Berman and Jerome L. Paul. Algorithms:Sequential, Parallel, and Distributed. - Thomson Course Technology, 2005 – 962 с.

 

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

національний університет “Львівська політехніка”

 

Кафедра ЕОМ