На головну

Порівняльні оцінки алгоритмів

  1. VI. Основні критерії оцінки законодавства
  2. Абсолютні і порівняльні модальності
  3. Айфарез і процедура оцінки
  4. Алгоритм комплексної оцінки якості продукції
  5. Алгоритми (властивості, реалізація алгоритмів)
  6. Аналіз об'єкта оцінки
  7. Апеляція за результатами регулярної оцінки

При використанні алгоритмів для вирішення практичних завдань ми стикаємося з проблемою раціонального вибору алгоритму розв'язання задачі. Рішення проблеми вибору пов'язане з побудовою системи порівняльних оцінок, яка в свою чергу суттєво спирається на формальну модель алгоритму.

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

З метою подальшого аналізу приймемо такі припущення:

- Кожна команда виконується не більше ніж за фіксований час;

- Вихідні дані алгоритму подаються машинними словами по ? бітів кожне.

Конкретна проблема задається N словами пам'яті, таким чином, на вході алгоритму - N?= N-?біт інформації. Відзначимо, що в ряді випадків, особливо при розгляді матричних задач N є мірою довжини входу алгоритму, що відбиває лінійну розмірність.

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

Крім того, алгоритм може вимагати наступних додаткових ресурсів абстрактної машини:

- S?- Пам'ять для зберігання проміжних результатів;

- S?- Пам'ять для організації обчислювального процесу (пам'ять, необхідна для реалізації рекурсивних викликів і повернень).

При вирішенні конкретної проблеми, заданої N словами пам'яті алгоритм виконує не більше, ніж кінцеве кількість «елементарних» операцій абстрактної машини в силу умови розгляду тільки фінітного алгоритмів. У зв'язку з цим введемо наступне визначення:

під трудомісткістю алгоритму для даного конкретного входу - F?(N), будемо розуміти кількість «елементарних» операцій, що здійснюються алгоритмом для вирішення конкретної проблеми в даній формальній системі.

Комплексний аналіз алгоритму може бути виконаний на основі комплексної оцінки ресурсів формальної системи, необхідних алгоритмом для вирішення конкретних проблем. Очевидно, що для різних областей застосування ваги ресурсів будуть різні, що призводить до наступної комплексної оцінки алгоритму:

?A= С1 - F?(N)+ З2 -М + С3 -S?+ З4 - S?, де Сi - Ваги ресурсів.




Структурна схема базової моделі МП фірми Intel представлена ??на малюнку 4.15. | ОЗУ призначена для зберігання змінної інформації, працює в режимах запису, читання і зберігання. | Ці два різновиди пам'яті розрізняються швидкодією і питомоющільністю (ємністю зберігається). | Накопичувачі на магнітних дисках. | Накопичувачі на оптичних дисках | Флеш-пам'ять | Стратегія вирішення завдань. | Алгоритми (властивості, реалізація алгоритмів) | структури даних | Складові (складні). |

© um.co.ua - учбові матеріали та реферати