Лекція 3 АМО 13.10.2008
Характеристики абстрактних алгоритмів

Абстрактні алгоритми лише називають правило безпосереднього перероблення, але не описують, як реалізується обчислювальний процес.
EMBED Visio.Drawing.11
Моделі абстрактних
алгоритмів
Приклади моделі “математична залежність”:
EMBED Equation.3
EMBED Equation.3
Наведіть приклади абстрактних алгоритмів для інших моделей
Спосіб визначення часової складності абстрактних алгоритмів
Часова складність абстрактного алгоритму визначається кількістю операцій, необхідних для його реалізації. Кількість операцій алгоритму залежить від кількості вхідних даних. Розмірність вхідних даних називають розміром входу та позначають через N . Наприклад, для одного і того ж алгоритму – множення двох чисел 11*10 і 11111001* 10101010 має різну часову складність. Така розбіжність значень часової складності не дозволяє порівнювати ступень ефективності алгоритмів. Для цього потрібно зафіксувати значення розміру входу, щоб він був однаковим для будь-якого алгоритму.
Математики запропонували прийнять розмір входу, який би асимптотично наближувався до нескінченності: EMBED Equation.3 . Мірою часової складності у цьому випадку є конструкція O(Q(N)), де О – означає порядок складності алгоритму (О перша буква слова Order – порядок), Q(N) – кількість операцій, необхідних для його реалізації. Міра часової складності O(Q(N)) називається асимптотичною складністю алгоритму
Дві оцінки асимптотичної складності
Розрізняють поліноміальну та експоненціальну оцінку складності
1. Алгоритм має поліноміальну складність, якщо відношення кількості операцій необхідної для розв’язання задачі зростає не швидше ніж поліном К-го ступеня від розміру входу.
Алгоритм з поліноміальною складністю визначається виразом:
EMBED Equation.3 ,
Де Q(N) – кількість операцій, необхідних для реалізації алгоритму.
PK(N)=a0+a1N+a2N2+…+aKNK , аі – коефіцієнт полінома
Приклад. Визначити, яку асимптотичну складність має алгоритму сортування “бульбашками”. Для цього алгоритму Q(N)Ср EMBED Equation.3 0,8N2
EMBED Equation.3 ,
Приймаємо значення коефіцієнтів поліному а0,а1,а3,…,аК = 0; а2 = 0,8, тогда
EMBED Equation.3 EMBED Equation.3
Приклади алгоритмів з поліноміальною складністю:
Сумування масивів чисел –О(N)
Множення масивів чисел – О(N)
Дискретне перетворення Фур’є – (ДПФ) О(N2)
Швидке перетворення Фур’є (ШПФ) – О(Nlog2N)
Розв’язання система лінійних алгебраїчних рівнянь методом Гауса – О(N3)
О(N!) – Задача Комівояжера.
2. Алгоритм має експоненціальну складність, якщо відношення кількості операцій необхідної для розв’язання задачі зростає швидше ніж поліном К-го ступеня від розміру входу.
Алгоритм з експоненціальною складністю визначається виразом:
EMBED Equation.3 ,
складність – маємо тоді коли відношення кількості операцій необхідних для розв’язання задачі, зростає швидше ніж поліном (К-го) ступеня від (N).
Приклад. Визначити, яку асимптотичну складність має алгоритм комівояжера
– Q(N) =N !
EMBED Equation.3 ,
Приймаємо значення коефіцієнтів поліному а0,а1,а2,…,аК-1 = 0; аК =1, тоді
EMBED Equation.3 EMBED Equation.3
Зростання N !, починаючі з деяких відносно не великих початкових чисел, йде скоріше у порівняні з NK, тому алгоритм комівояжера має експоненціальну складність.
Задачі з експоненціальною складністю називаються ?? - повними задачами.
( NP – не детерміновані поліноміальні). Такі задачі сучасними обчислювальними засобами не розв’язуються. До цих задач відноситься задача проектування комп’ютерних систем та багато інших. (Прогнозування погоди, дослідження соціальних, економічних та інших систем).
3. Евристичні алгоритми. Для розв’язання задач з експоненціальною складністю використовуємо евристичні алгоритми. Евристичними алгоритмами називаються такі алгоритми, які дозволяють розв’язати задачу за сприятливий час, але не гарантують точного розв’язання.
Способи побудови ефективних алгоритмів
І. Розбиття задачі на підзадачі (Розділяй та пануй)
Всі великі задачі використовують цей спосіб. Розв’язання без декомпозиції, з “нуля” в багатьох випадках просто неможливо. Розділення задачі на підзадачі дозволяє отримати розв’язання великих задач, скоротити інтелектуальне навантаження розробників, суттєво зменшити час розв’язання. Основні переваги такого підходу великої задачі за рахунок:
зменшується програмна складність кожної підзадачі
зменшується часова складність виконання окремих підзадач
спрощується оптимізація структури керування проектом.
збільшується економічна ефективність кінцевого продукту
Основні властивості декомпозиції задач:
ієрархічність
модульність
наслідування даних (вхідними даними наступної підзадачі є вихідні дані попередньої за ієрархією підзадачі).
Ефективність способу декомпозиції великої задачі розглянемо на прикладі наступної графічної моделі.
EMBED Visio.Drawing.11
Хай розмір входу концептуальної моделі N= EMBED Equation.3 ; часова складність EMBED Equation.3 . Припустимо нам вдалося розбити велику задачу на дев’ять підзадач з наступними значеннями розміру входу і часової складності (Табл):

Часова складність концептуальної моделі EMBED Equation.3 . Сукупна часова складність для всіх дев’яти підзадач менше майже на три порядка. Можна зробити висновок – декомпозиція великої задачі була вдалою. Розглянемо реальні приклади декомпозиції.
Проектування комп’ютера
Проектування проводиться за чотирма основними етапами: системним, функціонально-логічним, схемо-технічним та конструкторським. В таблиці наведені основні відомості про ці етапи.