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