Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Оцінка складності алгоритмів

Теоретичні відомості

Важливим етапом розробки алгоритмів є аналіз алгоритмів та оцінка їх складності. Cкладністю алгоритму a називають деяке число s, яке є результатом обчислення функціоналу М(a)=s, заданого на множині алгоритмів А'a. Причинами, які приводять до необхідності аналізу складності алгоритмів є:

· потреба в попередній оцінці ресурсів ЕОМ (об’єму оперативної та постійної пам’яті, швидкодії процесора), достатніх для реалізації алгоритмів;

· встановлення кількісних критеріїв для порівнянні різних алгоритмів вирішення одної задачі;

· встановлення критерію оптимальності алгоритму (оптимальність в даному випадку слід розуміти як неможливість покращення заданих характеристик алгоритму.)

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

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

Об’єм оперативної та постійної пам’яті, необхідної для розміщення даних алгоритму можна визначити виходячи з переліку змінних програми, їх типів, характеру розміщення змінних у пам’яті (так, наприклад, розміщення змінних у пам’яті та час їх існування для алгоритмів, реалізованих мовами програмування С++ або Паскаль визначається моделлю пам’яті програми, класом пам’яті конкретних змінних, та порядком використання функцій виділення та вивільнення динамічної пам’яті та роботи з файлами), тобто залежить як від самого алгоритму так і від засобів його реалізації.

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

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

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

Кажуть що функція порядку (позначають ), якщо .

Функція вищого порядку малості ніж (позначають ), якщо .

Алгоритм називають поліноміальним якщо його робоча функція , де – поліном від n степені m: . В іншому випадку алгоритм називають експоненціальним.

Аналогічні оцінки можна провести і для середньої та мінімальної кількості операцій. На практиці поліноміальні алгоритми добре піддаються виконанню на ЕОМ при зростанні n, а експоненціальні швидко перевантажують ЕОМ. Так алгоритм вирішення задачі комівояжера, який має робочу функцію , при n=20 вимагає для вирішення близько 70 століть машинного часу.

Для оцінки середньої кількості операцій можна використати ймовірностний опис розподілів вхідних даних і провести оцінку математичного сподівання кількості операцій. Проте, такий підхід є дуже складним і, як правило, вимагає більших зусиль для оцінки ніж для побудови алгоритму. Тому крім теоретичних методів оцінки складності використовують також експериментальні, які полягають в багатократному виконанні програми при різних, випадковим чином вибраних вхідних даних, і знаходженні середнього часу виконання програми або її фрагменту. Для алгоритмів, реалізованих на мовах програмування С++ або Паскаль зручним засобом експериментальної оцінки складності є програма Turbo Profiler фірми Borland. Ця програма дозволяє визначити:

як і на що витрачається час роботи програми;

скільки разів виконується кожна стрічка програми;

скільки раз і якими модулями викликається даний модуль програми;

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

 

Завдання до лабораторної роботи.

 

Згідно умови задачі:

1. Розробити алгоритм вирішення задачі;

2. Реалізувати алгоритм у програмі на С++;

3. Провести теоретичну оцінку складності алгоритму, використовуючи правила аналізу алгоритмів.

4. Обчислити кількість тактів процесора при різних вхідних даних.

 

Зміст звіту

Звіт повинен містити:

1. Завдання до роботи.

2. Блок-схему програми.

3. Текст програми.

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

 

Завдання

Для виконання наступних завдань необхідно обчислити номер завдання наступним чином: (n + 7) % 9 + 1, де n – порядковий номер студента за списком групи.

 

1. а) Дано два числа: обчислити їх середнє арифметичне, їх середнє геометричне.

б) Дано основу і висоту рівнобедреної трапеції, знайти периметр.

 

2. а) Скласти програму розв’язання лінійного вирівняні ax+b=0.

б) Дано координати двох точок на площині. Скласти програму, яка обчислює відстані між ними.

 

3. а) Дано двозначне число. Визначити: число десятків, число одиниць, суму і добуток цифр.

б) Трикутник задано координатами трьох вершин. Знайти довжини сторін і периметр.

 

4. а) Дано катети прямокутного трикутника. Знайти гіпотенузу.

б) Дано тризначне число. Визначити: число сотень, десятків, одиниць, суму і добуток його цифр.

 

5. а) Опуклий чотирикутник заданий координатами вершин. Знайти його площу як суму площ трикутників.

б) Дано тризначне число. Визначити число, яке утворюється при прочитанні його справа наліво.

 

6. а) Скласти програму обчислення значення функцій:

б) Дана довжина ребра куба. Визначити об’єм і площу поверхні.

 

7. а) Скласти програму обчислення функції:

б) Дано основу рівнобедреної трапеції і кут при більшому основі. Знайти площу.

 

8. а) У тризначному числі поміняли місцями першу зліва і першу справа цифри. Знайти отримане число.

б) Скласти програму обчислення значення функції для x, y:

 

9. а) Дано радіус кола. Знайти довжину кола і площу круга.

б) Дано основу і висоту рівнобедреної трапеції. Знайти периметр, площу.




Дата добавления: 2015-09-12; просмотров: 133 | Поможем написать вашу работу | Нарушение авторских прав

<== предыдущая лекция | следующая лекция ==>
Жылдамдық бойынша және үзілу тоғы бойынша теріс кері байланысы бар жетекті есептеу және сипаттамаларын тұрғызу| Alfred Nobel

lektsii.net - Лекции.Нет - 2014-2024 год. (0.018 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав