Міністерство освіти і науки України Вінницький національний технічний університету Факультет інтелектуальних інформаційних технологій та автоматизації Кафедра комп’ютерних наук Лабораторна робота №3 з дисципліни “Теорія алгоритмів” Тема: вивчення основ аналізу складності алгоритмів. Основні критерії оцінювання складності алгоритмів. Асимптотичні позначення. Мета: засвоїти основи та навчитися практично виконувати оцінювання складності алгоритмів. Хід роботи Завдання №1 Розташуйте, вказані згідно Вашого варіанта (таблиця 1) функції, у порядку збільшення їх ступеня зростання. Якщо серед наведених функцій є такі, що мають однакову швидкість зростання – вкажіть ці функції. Відповідь: → → → → Завдання № 2 (Визначення доцільності застосування алгоритму із заданою складність для заданого розміру входу) 2.1. У Вас є 5 алгоритмів а1, а2, а3, а4, а5 з часовими складностями, що наведені у таблиці 2. Обґрунтуйте, які з цих алгоритмів доцільно використовувати для різних n≥2 (де n – розмір входу). 2.2. A) Визначте розмір входу, який може бути оброблений вищевказаними алгоритмами за 1 секунду, 1 хвилину та 1 годину, якщо одиницею часу прийняти 1 мікросекунду. 1 cекунда = 1000000 мікросекунд 1 хвилина= 60000000 мікросекунд 1 година= 3600000000 мікросекунд Б) Покажіть, як зміниться розмір входу, для кожного з цих алгоритмів, якщо швидкодія комп’ютера зросте на порядок. Час обробки даних при цьому в обох випадках (до підвищення швидкодії комп’ютера та після неї) повинен бути однаковим. Прийміть, що час розв’язання = 1 година. В) Покажіть, як зміниться максимальний розмір входу, що можна обробити за 1 годину, якщо алгоритм а5 замінити на а4, а також, якщо алгоритм а4 замінити на а2. А)Якщо алгоритм а5 замінити на а4, то розмір входу збільшиться у 71,29 рази: 2210/31=71,29 Б) Якщо алгоритм а4 замінити на а2, то розмір входу збільшиться у 13,09 рази: 28934/2210=13,09 Висновок: у ході виконання лабораторної вивчено практичне оцінювання складності алгоритмів: порівняння швидкості зростання, доцільність використання алгоритмів під певні задачі, визначення максимального розміру входу та максимального розміру входу після прискорення а також порівняння алгоритмів по швидкодії. Контрольні питання 1. Наведіть основні критерії оцінювання складності алгоритмів. 2. Поясніть, чому для нас найбільшу цікавість становлять саме асимптотичні оцінки? 3. Поясніть, чому у час стрімкого зростання потужностей обчислювальної техніки питання розробки ефективних алгоритмів залишається дуже важливим та актуальним. 4. Які асимптотичні позначення найчастіше застосовують для визначення складності алгоритмів? В чому суть цих позначень? Наведіть відповідні приклади. 5. Наведіть основні властивості асимптотичних позначень. 6. Є два алгоритма, що мають однакову асимптотичну складність. Можна стверджувати, що ефективність алгоритмів однакова? Відповідь мотивуйте.