Формальне визначення алгоритму

Формальне визначення алгоритму змінювалося у часі залежно від того, за допомогою яких понять воно формулювалося.

Визначення алгоритму в математичних термінах вперше з'явилися в 1930-1940 р.р. ХХ століття. Часткова формалізація поняття алгоритму почалась зі спроб розв'язання задачі розв'язності. Було запропоновано декілька математичних моделей, які одержали назву формальних алгоритмічних систем (ФАС). ФАС ініціювали розвиток матричної теорії алгоритмів, предметом досліджень якої були характеристики складності алгоритмів.

Загалом можна виділити три основні типи універсальних алгоритмічних моделей, що розрізняються вихідними евристичними міркуваннями відносно означення того, що таке алгоритм:

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

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

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

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

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

ALG = (α₁→α₂, α₃ →α₄, ..., α₇ →.α₈).

Переваги даного типу алгоритмічних моделей – у їх максимальній абстрактності та можливості застосувати поняття алгоритму до об'єктів довільної (не обов'язково числової) природи.

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

Незважаючи на різноманіття алгоритмів, в них можна знайти багато спільного. Ці спільні риси називаються властивостями алгоритмів.

Основні властивості алгоритмів:

1. Скінченність.

Алгоритм має завершуватися за скінченну кількість кроків (скінченність процесу перетворення інформації).

2. Результативність.

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

3. Дискретність.

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

4. Визначеність (детермінованість або однозначність).

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

5. Формальність.

Будь-які виконавці, здатні сприймати і виконувати вказівки алгоритму (навіть не розуміючи їх змісту), діючи за алгоритмом, можуть виконати поставлене завдання і отримати однакові результати.

6. Масовість (універсальність).

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

У цьому випадку еквівалентність алгоритмів може бути визначена таким чином: два алгоритми еквівалентні, якщо збігаються їх області застосовності і результати переробки будь-якого слова з цієї області. Якщо області застосовності співпадають частково, алгоритми називають слабо еквівалентними.

7. Зрозумілість.

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

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

Щоб побудувати алгоритм, необхідно дотримуватись певних умов:

• вхідні та вихідні дані задаються у вигляді послідовності слів;

• процес розв’язання задачі - це є процес перетворення вхідних даних у вихідні;

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

• допустима елементарна операція — це проста, чисто механічна дія, результат якої не залежить від виконавця (машини чи людини);

• послідовність допустимих операцій не залежить від конкретних вхідних даних;

• порядок виконання допустимих операцій визначений однозначно;

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

Складні алгоритми будуються із простих шляхом застосування різних способів їх композиції. Основні способи композиції алгоритмів (для класу нормальних алгоритмів):

1. Суперпозиція.

Суперпозиція алгоритмів ALG1 та ALG2 означає їх послідовне застосування до даного слова α:

ALG3(α) = ALG2(ALG1(α)) ,

тобто, вихідне слово алгоритму ALG1 є вхідним словом до алгоритму ALG2.

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

2. Об’єднання.

Об’єднання алгоритмів ALG1 і ALG2 - це їх паралельне застосування до вхідного слова α, що належить перетину областей визначення даних алгоритмів, і формування вихідного слова у вигляді записаних поруч слів ALG1(α) і ALG2(α):

ALG3(α) = ALG1(α) ALG2(α),

тобто, це алгоритм ALG3, який перетворює вхідне слово α в об’єднання слів ALG1(α) і ALG2(α), де слово .

3. Розгалуження

Розгалуження алгоритмів — це така композиція трьох алгоритмів ALG1, ALG2, ALG3, що для будь-якого α, що належить перетину областей визначення даних алгоритмів,

,

де  – пусте слово.

Наприклад,

ALG1 = (ab → ba),

ALG2 = (ba → ab),

ALG3 = (ab → a, ba → ),

ALF = {a, b},

α₁ = aba.

Тут

ALG1(aba) = baa ,

ALG2(aba) = aab,

ALG3(aba) = aa ≠ .

Таким чином, отримуємо

ALG4(aba) = ALG2(aba) = aab .

Для α₂ = bab :

ALG1(bab) = bba,

ALG2(bab) = abb,

ALG3(bab) =  ,

ALG4(bab) = ALG1(bab) = bba .

4. Повторення (ітерація, цикл).

Цикл – це така композиція алгоритмів ALG1 і ALG2, що для будь-якого вхідного слова α відповідне вихідне слово ALG3(α) отримується в результаті послідовного багаторазового застосування алгоритму ALG1 до тих пір, поки не вийде слово, що може бути перетворене алгоритмом ALG2.

Наприклад,

ALF ={a, b},

ALG1 = (ab → ba),

ALG2 = (bbbaa → ab) .

Дедуктивний ланцюжок:

α = ab abb  baabb  babab  bbaab  bbaba  bbbaa  ab

З поняттям алгоритму пов’язані такі поняття, як область його задання, складність, еквівалентність, алгоритмічна розв’язність та ін.

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

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

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

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

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

Формалізуємо дане поняття. Нехай

• А - алгоритм розв’язання деякого класу задач;

• n-розмірність однієї із задач цього класу (n може бути, наприклад, довжиною послідовності в алгоритмі, кількістю слів в тексті, що аналізується, розмірністю оброблюваного масиву, числом вершин оброблюваного графа тощо);

• функція f_A(n) - верхня межа для максимального числа основних операцій (додавання, множення і т.д.), які повинен виконати алгоритм А для розв’язання будь-якої задачі розмірності n.

Тоді алгоритм А називається поліноміальним, якщо f_A(n) зростає не швидше, ніж деякий поліном від n; в противному випадку алгоритм А вважається експоненціальним. Так, функції типу kn, kn², kn³ ,..., де k - коефіцієнт, можуть розглядатися як поліноміальні, а функції типу 2ⁿ, nⁿ, n! ... як експоненціальні.

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

Характеристика часу, витраченого на реалізацію алгоритму, як функція розмірності задачі, називається часовою складністю алгоритму і позначається як O [ f_A (n)]. Цей час є в більшості випадків властивістю самого алгоритму і слабо залежить від ЕОМ, на якій виконується відповідна алгоритму програма.

Окрім часової складності алгоритмів існують і інші міри складності. Так, складність можна характеризувати числом операцій N (стосовно конкретної ЕОМ) і загальним обсягом інформації Р (загальною кількістю слів, що використовуються при виконанні алгоритму). Тоді час виконання алгоритму на конкретній ЕОМ пов'язаний з числом операцій, а обсяг інформації пов'язаний з об'ємом пам'яті, необхідним машині для реалізації відповідної програми. Отже, часом реалізації алгоритму є функція T = f (N). При такому підході значення Т і Р називають відповідно обчислювальною та ємнісною складністю алгоритму.

Часова та ємнісна складність тісно пов'язані між собою. Обидві вони є функціями від розміру вхідних даних n.

Структурний взаємозв’язок основних понять та елементів, що становлять суть алгоритму, зображено на рис. 2.

Рис. 2. Структурний взаємозв’язок характеристик алгоритму