Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Оцінка складності алгоритмів
Інформація про навчальний заклад
ВУЗ:
Тернопільський національний економічний університет
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Теорія алгоритмів
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Тернопільський національний технічний університет
імені Івана Пулюя
Кафедра комп’ютерних наук
ЛАБОРАТОРНА РОБОТА №6
з дисципліни “Теорія алгоритмів”
Тема роботи: Оцінка складності алгоритмів
Лабораторна робота №6
Тема роботи: Оцінка складності алгоритмів
Мета роботи: Вивчення теоретичних та практичних методів оцінки складності алгоритмів.
Теоретичні відомості
Оцінка складності алгоритмів
Важливим етапом розробки алгоритмів є аналіз алгоритмів та оцінка їх складності. Cкладністю алгоритму ( називають деяке число (, яке є результатом обчислення функціоналу М(()=(, заданого на множині алгоритмів А((. Причинами, які приводять до необхідності аналізу складності алгоритмів є:
потреба в попередній оцінці ресурсів ЕОМ (об’єму оперативної та постійної пам’яті, швидкодії процесора), достатніх для реалізації для реалізації алгоритмів;
встановлення кількісних критеріїв для порівнянні різних алгоритмів вирішення одної задачі;
встановлення критерію оптимальності алгоритму (оптимальність в даному випадку слід розуміти як неможливість покращення заданих характеристик алгоритму.)
прогнозування змін вимог до обчислювальних ресурсів та критеріїв оцінки алгоритмів при зміні характеру та кількості вхідних даних.
Складність алгоритму, як правило, включає необхідний об’єм оперативної та постійної пам’яті, та час виконання алгоритму, взяті з певними ваговими коефіцієнтами. В окремих випадках доступні ресурси ЕОМ можуть бути більші за необхідні для виконання алгоритму (наприклад об’єм оперативної пам’яті ЕОМ більший за об’єм пам’яті, необхідний алгоритму). В таких випадках при розрахунку складності алгоритму можна не враховувати відповідні складові.
Об’єм оперативної та постійної пам’яті, необхідної для розміщення даних алгоритму можна визначити виходячи з переліку змінних програми, їх типів, характеру розміщення змінних у пам’яті (так, наприклад, розміщення змінних у пам’яті та час їх існування для алгоритмів , реалізованих мовами програмування С++ або Паскаль визначається моделлю пам’яті програми, класом пам’яті конкретних змінних, та порядком використання функцій виділення та вивільнення динамічної пам’яті та роботи з файлами), тобто залежить як від самого алгоритму так і від засобів його реалізації.
Час виконання алгоритму залежить від структури алгоритму (тобто послідовності і виду команд), часу виконання кожної команди, об’єму і характеру вхідних даних. Оскільки час виконання команди є характеристикою ЕОМ а не алгоритму, то при оцінці складності алгоритму доцільно замість часу виконання взяти кількість команд, виконану алгоритмом, або, якщо час виконання команд різний, кількість тактів процесора.
При оцінці впливу вхідних даних на складність алгоритму використовують такий показник як розмірність задачі n. В багатьох задачах n є просто скаляр, рівний, наприклад, числу вершин графа задачі. В загальному випадку n може бути вектором або матрицею, елементи якої є розмірами масивів вхідних даних. Вплив характеру вхідних даних на складність алгоритму (особливо актуально для алгоритмів з розгалуженнями) враховують, проводячи оцінку максимальної, мінімальної та середньої кількості операцій.
Функцію , яка дає верхню границі кількості операцій, що виконує алгоритм при вирішенні будь-якої задачі розмірності n, називають робочою функцією.
Кажуть що функція порядку (позначають ), якщо .
Функція вищого порядку малості ніж (позначають ), якщо .
Алгоритм називають поліноміальним якщо його робоча функція , де - поліном від n степені m: . В іншому випадку алгоритм називають експоненціальним.
Аналогічні оцінки можна провести і для середньої та мінімальної кількості опер0,ацій. На практиці поліноміальні алгоритми добре піддаються виконанню на ЕОМ при зростанні n, а експоненціальні швидко перевантажують ЕОМ. Так алгоритм вирішення задачі комівояжера, який має робочу функцію , при n=20 вимагає для вирішення близько 70 століть машинного часу.
Для оцінки середньої кількості операцій можна використати ймовірностний опис розподілів вхідних даних і провести оцінку математичного сподівання кількості операцій. Проте, такий підхід є дуже складним і, як правило, вимагає більших зусиль для оцінки ніж для побудови алгоритму. Тому крім теоретичних методів оцінки складності використовують також експериментальні, які полягають в багатократному виконанні програми при різних, випадковим чином вибраних вхідних даних, і знаходженні середнього часу виконання програми або її фрагменту. Для алгоритмів, реалізованих на мовах програмування С++ або Паскаль зручним засобом експериментальної оцінки складності є програма Turbo Profiler фірми Borland. Ця програма дозволяє визначити:
як і на що витрачається час роботи програми;
скільки разів виконується кожна стрічка програми;
скільки раз і якими модулями викликається даний модуль програми;
до яких файлів звертається програма і скільки часу на це витрачається.
Завдання до лабораторної роботи.
Згідно умови задачі (табл.1.):
Розробити алгоритм вирішення задачі;
Реалізувати алгоритму у програмі на мові паскаль або С++;
Провести теоретичну оцінку складності алгоритму, яка включає визначення:
а. Об’єму необхідної оперативної та постійної пам’яті;
b. Робочої функції алгоритму в найгіршому випадку;
с. Експоненціальний алгоритм чи поліноміальний, та порядку полінома (якщо алгоритм поліноміальний).
Використовуючи програму Turbo Profiler, провести експериментальну оцінку складності алгоритму в середньому випадку, яка включає визначення:
а. Середнього часу виконання програми (якщо програма використовує випадкові вхідні дані, то кількість проходів програми не менше 100 разів);
b. Ділянок програми, на виконання яких йде найбільше часу;
c. Ділянки програми, які виконуються максимальну кількість разів та середній час їх виконання.
Провести порівняння складності алгоритму в найгіршому та середньому випадках.
Зміст звіту
Звіт повинен містити:
Завдання до роботи.
Блок-схему програми.
Текст програми.
Результати теоретичної та експериментальної оцінки складності алгоритму.
Висновки.
Контрольні запитання
Перетворення Фур’є, Лапласа, Z-перетворення. Перехід від часової до спектральної форми опису.
Опис структури алгоритму у вигляді структурної схеми, граф-схеми, системи рівнянь.
Особливості реалізації алгоритмів на спеціалізованих ЕОМ. Серіалізм та паралелізм операцій у обчислювальних алгоритмах.
Рекомендована література
Гоноровский И.С. Радиотехнические цепи и сигналы. М. Радио и связь. 1986.
Баскаков С.И. Радиотехнические цепи и сигналы. М. Высшая школа. 1988.
Бабак В.П. Хандецький В.С. Шрюфер Е. Обробка сигналів. К. Либідь 1996.
Залманзон Л.А. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. М. Наука. 1989.
Голд. Цыфровая обработка сигналов.
Цыфровая обработка сигналов.
Карташев В.Г. Основы теории дискретных сигналов и цифровых фильтров. М. Высшая школа. 1982.
Варіанти завдань
Варіант
Завдання
1
Згенерувати послідовність N випадкових натуральних чисел 0(Xі(100, і=1..N і знайти кількістьелементів цієї послідовності, рівних 5. Провести оцінку складності отриманого алгоритму теоретичним та експериментальним методами. N=200
2
Згенерувати послідовність N випадкових натуральних чисел 0(Xі(100, і=1..N і посортувати її в порядку зростання елементів, використовуючи алгоритм quicksort [1]. Провести оцінку складності отриманого алгоритму теоретичним та експериментальним методами. N=250
3
Згенерувати послідовність N випадкових натуральних чисел 0(Xі(100, і=1..N і посортувати її в порядку зростання елементів, використовуючи метод бульбашки. Провести оцінку складності отриманого алгоритму теоретичним та експериментальним методами. N=100
4
Згенерувати послідовність N випадкових натуральних чисел 0(Xі(100, і=1..N і посортувати її в порядку зростання елементів, використовуючи алгоритм heapsort [1]. Провести оцінку складності отриманого алгоритму теоретичним та експериментальним методами. N=120
5
Реалізувати алгоритм генерації простих чисел на основі методу Ератосфена і провести теоретичний та експериментальний аналіз складності алгоритму.
6
Задано перелік міст та їх населення: A-100000, B-39000, C-3367000, D-37000, E-100, F-400, G-7868000, H-114000, P-109, організований у вигляді двійкового дерева, впорядкованого по кількості жителів (А- корінь дерева). На основі алгоритму BTSI [1], реалізувати алгоритм пошуку та вставки нового елемента у двійкове дерево і з його допомогою:
знайти міста з населенням 37000, 100, 50000;
вставити у дерево місто Q з населенням 80000.
Провести оцінку складності отриманого алгоритму теоретичним та експериментальним методами.
7
Згенерувати впорядковану послідовність N випадкових натуральних чисел 0(Xі(100, і=1..N і, використовуючи алгоритм двійкового пошуку (алгоритм bsearth [1]), знайти позицію найменшого елемента цієї послідовності, більшого 20. Провести оцінку складності отриманого алгоритму теоретичним та експериментальним методами. N=40
8
Дано прерлік населених пунктів і вартості проїзду між ними (табл.1). Реалізувати алгоритм пошуку маршруту, який:
Починається і завершується у пункті 1;
Проходить через кожний пункт хочаб 1 раз;
Має мінімальну вартість. Провести оцінку складнос
ним та експериментальни
Табл. 1
№п
1
2
3
4
5
6
1
0
12
43
2
13
5
2
12
0
14
22
3
23
3
40
11
0
25
10
2
4
5
31
22
0
27
5
5
17
1
11
31
0
8
6
5
23
3
7
8
0
ті отриманого алгоритму теоретич-
м методами.
9
Задано розміщення та відстані
між пунктами 1-9. На основі
алгортиму Дейкстри [1], розробити
алгоритм пошуку шляху від
пункту 1 до пункту 9 з
мінімальною довжиною.
Модифікувати алгоритм
для довільної сукупності
пунктівта відстаней.
Провести оцінку складності
отриманого алгоритму
теоре тичним та експери-
ментальним методами.
10
Задано розміщення та відстані
між пунктами 1-9. Розробити
алгоритм пошуку шляху
мінімальної довжини від
пункту 1 до пункту 9,
альтернативний
алгортиму Дейкстри.
Провести оцінку склад-
ності отриманого алгоритму
теоре тичним та експери-
нентальним методами.
11
Згенерувати послідовність N випадкових натуральних чисел 0(Xі(100, і=1..N і посортувати її в порядку зростання елементів, використовуючи алгоритм сортування прямим включенням (алгоритм sis [1]). Провести оцінку складності отриманого алгоритму теоретичним та експериментальним методами. N=80
12
Реалізувти алгоритм пошуку позиції початку заданого слова у стрічці і провести теоретичний та експериментальний аналіз складності алгоритму в залежності від довжини стрічки та заданого слова.
13
14
Згенерувати послідовність N випадкових натуральних чисел 0(Xі(100, і=1..N і посортувати її в порядку зростання елементів, використовуючи метод вибору найменшого елемента. Провести оцінку складності отриманого алгоритму теоретичним та експериментальним методами. N=40
07.02.2013 19:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора