asyan.org
добавить свой файл
1




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

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


Моделі абстрактних

алгоритмів

Приклади моделі “математична залежність”:





Наведіть приклади абстрактних алгоритмів для інших моделей
^ Спосіб визначення часової складності абстрактних алгоритмів

Часова складність абстрактного алгоритму визначається кількістю операцій, необхідних для його реалізації. Кількість операцій алгоритму залежить від кількості вхідних даних. Розмірність вхідних даних називають розміром входу та позначають через N . Наприклад, для одного і того ж алгоритму – множення двох чисел 11*10 і 11111001* 10101010 має різну часову складність. Така розбіжність значень часової складності не дозволяє порівнювати ступень ефективності алгоритмів. Для цього потрібно зафіксувати значення розміру входу, щоб він був однаковим для будь-якого алгоритму.

Математики запропонували прийнять розмір входу, який би асимптотично наближувався до нескінченності: . Мірою часової складності у цьому випадку є конструкція O(Q(N)), де О – означає порядок складності алгоритму (О перша буква слова Order – порядок), Q(N) – кількість операцій, необхідних для його реалізації. Міра часової складності O(Q(N)) називається асимптотичною складністю алгоритму
^ Дві оцінки асимптотичної складності

Розрізняють поліноміальну та експоненціальну оцінку складності

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

Алгоритм з поліноміальною складністю визначається виразом:

,

Де Q(N) – кількість операцій, необхідних для реалізації алгоритму.

PK(N)=a0+a1N+a2N2+…+aKNK , аі – коефіцієнт полінома

Приклад. Визначити, яку асимптотичну складність має алгоритму сортування “бульбашками”. Для цього алгоритму Q(N)Ср 0,8N2

,

Приймаємо значення коефіцієнтів поліному а013,…,аК = 0; а2 = 0,8, тогда

Приклади алгоритмів з поліноміальною складністю:

Сумування масивів чисел –О(N)

Множення масивів чисел – О(N)

Дискретне перетворення Фур’є – (ДПФ) О(N2)

Швидке перетворення Фур’є (ШПФ) – О(Nlog2N)

Розв’язання система лінійних алгебраїчних рівнянь методом Гауса – О(N3)

О(N!) – Задача Комівояжера.
^ 2. Алгоритм має експоненціальну складність, якщо відношення кількості операцій необхідної для розв’язання задачі зростає швидше ніж поліном К-го ступеня від розміру входу.

Алгоритм з експоненціальною складністю визначається виразом:

,

складність – маємо тоді коли відношення кількості операцій необхідних для розв’язання задачі, зростає швидше ніж поліном (К-го) ступеня від (N).

Приклад. Визначити, яку асимптотичну складність має алгоритм комівояжера

– Q(N) =N !

,

Приймаємо значення коефіцієнтів поліному а012,…,аК-1 = 0; аК =1, тоді


Зростання N !, починаючі з деяких відносно не великих початкових чисел, йде скоріше у порівняні з NK, тому алгоритм комівояжера має експоненціальну складність.

Задачі з експоненціальною складністю називаються ΝΡ - повними задачами.

( NPне детерміновані поліноміальні). Такі задачі сучасними обчислювальними засобами не розв’язуються. До цих задач відноситься задача проектування комп’ютерних систем та багато інших. (Прогнозування погоди, дослідження соціальних, економічних та інших систем).

3. ^ Евристичні алгоритми. Для розв’язання задач з експоненціальною складністю використовуємо евристичні алгоритми. Евристичними алгоритмами називаються такі алгоритми, які дозволяють розв’язати задачу за сприятливий час, але не гарантують точного розв’язання.
^ Способи побудови ефективних алгоритмів

І. Розбиття задачі на підзадачі (Розділяй та пануй)

Всі великі задачі використовують цей спосіб. Розв’язання без декомпозиції, з “нуля” в багатьох випадках просто неможливо. Розділення задачі на підзадачі дозволяє отримати розв’язання великих задач, скоротити інтелектуальне навантаження розробників, суттєво зменшити час розв’язання. Основні переваги такого підходу великої задачі за рахунок:

  1. зменшується програмна складність кожної підзадачі

  2. зменшується часова складність виконання окремих підзадач

  3. спрощується оптимізація структури керування проектом.

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

Основні властивості декомпозиції задач:

  • ієрархічність

  • модульність

  • наслідування даних (вхідними даними наступної підзадачі є вихідні дані попередньої за ієрархією підзадачі).

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



Хай розмір входу концептуальної моделі N=; часова складність . Припустимо нам вдалося розбити велику задачу на дев’ять підзадач з наступними значеннями розміру входу і часової складності (Табл):





X1

X2

X3

X4

X5

X6

X7

X8

X9

N



















Q(N)



















L


















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

Проектування проводиться за чотирма основними етапами: системним, функціонально-логічним, схемо-технічним та конструкторським. В таблиці наведені основні відомості про ці етапи.




Системний

Функціонально-логічний

схемо-технічний

Конструкторський

Підзадача, розроблення

концептуальної

моделі, системи команд, ТЗ

алгоритмів, мікропрограм, функц. та логіч схем,

мікро, нано елементів.та пристроїв

топології НВІС

ВІС друк. плат,

системи з’едн.,

конструцій

Графічні матеріали

Структурні сх.

Функціональні та логічні сх.

Електричні сх.

Комутаційні сх., таблиці

Математичний апарат

Імітаційне моделювання

Імітаційне моделювання

Рівняння мат. фіз., квант мех.

Лінійна алгебр. Теор. графов

Приклади САПР

GPSS

VHDL

ORCAD

VHDL

Оцінка N













Оцінка L