Лабораторна робота № 2
"Параметри та характеристики складності алгоритму. ".
Мета роботи : Аналіз впливу параметрів алгоритму на характеристики складності алгоритму.
Зміст роботи:
I. Теоретична частина.
Основні поняття та визначення
Параметри алгоритму.
Характеристики алгоритму.
II. Практична частина
Скласти блок-схему алгоритму знаходження найбільшого спільного дільника (НСД) двох чисел методом перебору, починаючи з 1.
Визначити програмну складність алгоритму та часову складність для деякої пари 2-значних чисел
Модифікувати алгоритм, змінивши правило початку (Починати перебор з меншого числа).
Визначити програмну складність алгоритму та часову складність.
Порівняти складність двох алгоритмів.
Модифікувати алгоритм, змінивши правило безпосереднього перероблення (Алгоритм Евкліда).
Визначити програмну складність алгоритму та часову складність.
Порівняти складність алгоритмів.
III. Лабораторна робота
Скласти програму (Pascal , C), яка дозволяє провести порівняння трьох алгоритмів знаходження НСД за характеристикою "часова складність".
Вимоги до програми:
Программа виконується циклічно.
В кожному циклі вибирається пара випадкових чисел з заданого діапазону.
Для вибраної пари чисел знаходиться НСД трьома методами.
Визначається часова складність для кожного з методів.
Для кожного методу підраховується середне та найбільше значення часової складності .
Отримані результати оперативно відображуються на екрані.
Оператор може зупинити програму в довільний момент.
IV. Висновки.
_______________________________________________________________________________

Контрольні запитання
Показати зв'язок між параметрами та характеристикамі складності алгоритму.
Порівняти за часовою складністю алгоритм пошуку НСД методом перебору з більших чисел , з одиниці, та методом Евкліда.
Дати тлумачення поняттю "задача".
Пояснити спосіб мінімізації часової складності зміною правила початку, правила безпосереднього перероблення, правила закінчення.
Структура алгоритму.
Структура пари : задача-алгоритм.
Схема побудови алгоритму.