Методи оцінки алгоритмів

У теорії алгоритмів поняття «алгоритм» звичайно уточнюється за допомогою опису «математичної моделі» обчислювальної машини. Тут можливі два підходи залежно від того, чи оцінюється складність алгоритму (машини, програми) або можливість обчислювального процесу, що протікає відповідно до алгоритму.

Як міра складності алгоритмів розглядається функціонал, що співвідносить кожному алгоритму А деяке число μ(A), що характеризує (у підходящому змісті) його громіздкість, наприклад: число команд в А, довжина запису А, або який-небудь інший числовий параметр, що характеризує обсяг інформації, що міститься в А. Подібні функціонали вже давно застосовуються в теоретико-кібернетичних дослідженнях схем, що реалізують функції алгебри логіки (Шеннон, Яблонский, Ляпунов й ін.), а також в обчислювальній математиці, де потужність схеми, по якій обчислюється багаточлен, виміряється числом арифметичних операцій, що фігурують у схемі. Розходження полягає лише в тім, що в зазначених роботах розглядаються спеціальні вузькі класи функцій і спеціальні способи опису алгоритмів. Ми ж зацікавлені в розробці й застосуванні аналогічних понять у більше загальній ситуації (будь-які обчислювані функції, загальні концепції алгоритму). Перші публікації, у яких такі міри складності знайшли застосування, належать А. А. Маркову й А. Н. Колмогорову.

В якості міри складності обчислень розглядається функціонал, що співвідносить кожній парі (А, α), де A -алгоритм, α — індивідуальна задача з того класу задач, які алгоритм А вирішує, деяке число δ (А, α). Це число характеризує складність роботи алгоритму А стосовно до вихідних даних а до видачі відповідного результату. Наприклад, у якості δ (А, α) можна брати число елементарних кроків, з яких складається ця робота (інакше кажучи, тривалість процесу обчислення) або об'єм пам'яті, що може знадобитися для реалізації всіх викладень по ходу даного процесу, і т.д. Оскільки для кожного алгоритму однозначно визначений той клас задач Ω, що він вирішує (наприклад, та функція f, значення якої він обчислює), то можна вважати, що в розглянутій ситуації кожен алгоритм А характеризується функцією змінного

α δ_A (α) δ (А, α). Іншими словами, мірою складності роботи алгоритму (обчислення) є оператор, що зіставляє з кожним алгоритмом А відповідну функцією δ_A(α).

Визначаючи деяку міру складності для алгоритмів (або обчислень), ми тим самим сподіваємося одержати зручний інструмент для порівняння алгоритмів, а також для оцінки об'єктивних труднощів, властивим різним обчислюваним функціям. У зв'язку із цим можна відзначити розходження в здійсненні такого задуму в зависимости від того, чи розглядається міра складності алгоритму або міра складності його роботи. Оскільки складність алгоритму виміряється дійсним числом, те будь-які два алгоритми порівнянні по складності.

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

Якщо ж вихідної є міра складності обчислень, то виходить інша картина. Дві сигналізуючі функції можуть виявитися непорівнянними, навіть якщо вважати, як звичайно це прийнято, що сигналізуюча ?_A менше сигналізує δ_B, якщо для всіх α, за винятком, бути може, скінченного їхнього числа δ_A (α) <δ_B(α). Тому як тільки зафіксована деяка функція f, то апріорі не ясно, чи існує для неї найкраще обчислення. Тут доводиться власне кажучи обмежуватися більше слабкою характеристикою складності самої функції f а саме відшукуються дві функції φ₁ (нижня оцінка) і φ₂ (верхня оцінка), такі, що:

1) існує алгоритм А₁, що обчислює f із сигналізуючою, не переважаючою φ₂;

2) який би не був алгоритм A, що обчислює f, його сигналізуюча не менше φ_1.

Зрозуміло, чим ближче друг до друга верхня й нижня оцінки φ₁ й φ₂, тим точніше охарактеризована складність самої функції f.

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

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

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

Розглянемо оцінки складності алгоритму стосовно до машин Т'юрінга.

З кожною конфігурацією k, до якої застосовна машина Т'юрінга, можна асоціювати число, що характеризує складність процесу М(k) у тім або іншому змісті.

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

Роботу машини М будемо характеризувати наступними сигналізуючи ми функціями:

Сигналізуючачасу t_м(k) дорівнює тривалості процесу М(k) (тобто числу його конфігурацій),якщо М застосовна кk,і t(k) і не визначена, якщо М не застосовна до k.

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

Сигналізуюча ємності s_м(k) дорівнює довжині активної зони процесу М(k), якщо М застосовна до k и не визначена в протилежному випадку.

Сигналізуюча коливань ω_м(к) дорівнює числу коливань (зміни напрямків) голівки за час t_м(k), якщо М застосовна до k и не визначена в протилежному випадку.

Сигналізуюча режиму r_м(k) дорівнює максимальному числу проходжень голівки через край комірки за час t_м(k), якщо М застосовна до і не визначена в протилежному випадку.

де |р| -довжина слова р, а також функції типу

Зокрема, коли в якості конфігурації k узяті початкові конфігурації для слова р, то процес буде характеризуватися функціями, що сигналізують, tм(р), s_м(p), ω_м(р), r_м(р). Поряд з ними розглядаються й функції типу

де V — найбільше з довжин слів р_i.

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

Має місце теорема, що показує, що при наявності верхньої оцінки, для який-небудь однієї із сигналізучих t, s, ω, r і заданих параметрах тип (т — число символів зовнішнього алфавіту, п — число символів внутрішнього алфавіту) можна одержати верхні оцінки для інших.

Теорема. Для будь-якої машини М и для будь-якого слова р, до якого вона застосовна, справедливі наступні нерівності:

Сигналізуючий оператор, Т ставить у відповідність кожної одномісної функції ?_i(x) її сигналізатор Ф_i(х) (Ф =t, s, ω, r)

Нумераційний функціонал μ(i) називається критерієм складності, а для фіксованого i число μ(i) називається складністю опису функції φ_i, якщо виконані умови:

1) μ(i) усюди певна ефективна функція;

2) при будь-якому фіксованому а рівняння μ(i) = а має скінченне число рішень, причому існує алгоритм, за допомогою якого для будь-якого а всіх рішень можуть бути ефективно знайдені.