Відкрити головне меню

Загальні поняттяРедагувати

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

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

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

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

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

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

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

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

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

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

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

Операторні алгоритми Ван ХаоРедагувати

Операторний алгоритм Ван Хао задається послідовністю наказів спеціального вигляду. Кожен наказ має певний номер і містить вказівки: яку операцію слід виконати над заданим об'єктом і наказ з яким номером слід далі виконати над результатом даної операції. Загальний вигляд такого наказу (1):

 

де i — номер наказу; ω — елементарна операція над об'єктом; α, β — номери деяких наказів.

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

Виконати наказ (1) над числом х в операторному алгоритмі — значить знайти число ω(х) і далі перейти до виконання над ω(х) наказу з номером α.

Якщо ж ω(х) не визначено, то перейти до виконання над числом х наказу з номером β.

Наприклад, виконавши над числом 24 наказ

 

отримаємо число 4 і вказівка виконувати далі над 4 наказ з номером 7. Виконавши цей наказ над числом 23, отримаємо знову число 23 і вказівка виконувати над 23 наказ з номером 13.

Заключного станом машини Тьюринга в операторних алгоритмах відповідає наказ виду:

 

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

У загальному випадку результат виконання наказу (1) над числом х будемо зображати парою (z, γ), де z — отримане число, γ — номер наказу, який повинен виконуватися далі над z.

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

 
 
 
 
 

де ω(x),…, ωi+s(x) — задані одномісні часткові функції, що визначають елементарні операції над об'єктом х; αi, βi,…, αi+s, βi+s… — якісь натуральні числа з послідовності i, i+1,…, i+n.

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

i — крок. Знаходимо ωi(x). Якщо ωi(x) визначено, то результатом буде пара чисел [ωi(x), αi]. Якщо ω(x) не визначено, то результатом i — гo кроку буде пара (х, βi).

i+1 — крок, якщо результат попереднього кроку х, βi, де βi= i+1. Знаходимо ωi+1(x). Якщо вона визначена, то результатом буде пара [ωi+1(x), αi+1], якщо не визначена, то результатом буде пара (х, βi+1) і т. д.

i+n-1 — крок. Якщо як результат на цьому кроці вийде пара, яка вказує на заключний оператор (z, i+n), то процес обривається і число z є результатом переробки числа х згідно заданому алгоритму (z = ωi+n-1(х)).

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

Якщо функція усюди визначена, то символ β не робить вплив на процес обчислень і тому зазвичай опускається. У цьому випадку наказ має вигляд i: [ω,α]: Кажуть, що операторний алгоритм А з програмою (х) обчислює часткову функцію f(x), якщо алгоритм А переробляє кожне натуральне число х в f(x). Зокрема, якщо f(x) НЕ визначено, то процес переробки х згідно з програмою (2) повинен бути нескінченним.

Природа функцій, обчислюваних за допомогою операторних алгоритмів Ван — Хао, залежить від того, які функції ω1 входять у записі наказів. Має місце наступна теорема, визначальна природу функцій ωi.

Теорема (3). Для того щоб часткова функція f(x) була обчислюваною за допомогою операторного алгоритму, програма якого містить лише частково рекурсивні функції ωi(х) з рекурсивної областю визначеності, необхідно і достатньо, щоб f(х) була частково рекурсивної.

Необхідність умов очевидна, і ми обмежимося лише доказом їх достатності.

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

Наприклад,

 .

Ясно, що алгоритм з програмою

 

обчислює ніде не визначену функцію f(x).

Нехай частково рекурсивна функція f(x) має непорожній графік. Тоді цей графік можна представити у вигляді сукупності пар <α(t),β(t)>, (t=0,1,…), де α і β — підходящі примітивно рекурсивні функції. Позначимо через υ(x) вираз 2х і введемо часткову функцію ω(x), вважаючи

 

Функція ω(x) частково рекурсивних з рекурсивної областю визначеності. легко переконатися, що операторний алгоритм, що має програму

 

обчислює якраз функцію f(x). Справді, виконавши над довільним числом х наказ 1, отримаємо пару (2х, 2). Якщо x≠α(0), то, виконавши над 2х наказ 2, отримаємо пару (2x31, 2) . Якщо x≠α(1), то, виконавши над 2x31 наказ 2, отримаємо пару (2x32, 2) і т. д. Процес продовжується до тих пір, поки, нарешті, вийде пара (2x3n, 2), для якої х=α(n). так як ω(2x3n) не визначено, то над числом 2x3n тепер треба виконати наказ 3, в результаті якого отримаємо пару (n,4). Виконавши над n наказ 4, отримаємо пару (β(n),0). Так як х=α(n), то β(n)=f(х), і, отже, алгоритм переробляє х в f(x), що й було потрібно.

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

Теорема Мінського (4). Для кожної частково рекурсивної функцій f(х) існує операторний алгоритм, програма якого складається з наказів виду

 

для будь-якого х, переробний 2x в 2f(x).

Іншими словами, будь-яка частково рекурсивна функція f(х) Обчислювана за допомогою підходящого алгоритму, програма якого складається з наказів наведеного виду, при умови, що значення аргументу і функції кодуються числами 2, 2f(x).

Операторні алгоритми О. А. ЛяпуноваРедагувати

Алгоритмічна система радянського вченого Олексія Ляпунова, запропонована ним в 1953 р., є однією з перших, що враховують всі вимоги, пропоновані до конкретних алгоритмам. Вона виникла у зв'язку з реалізацією алгоритмів різних завдань на ЕОМ.

Для опису будови алгоритмів Ляпунов використовує спеціальний математичний апарат — так звана «логічна схема алгоритмів», в яких великими логічними буквами позначаються окремі акти алгоритму, переробні інформацію. Їх називають операторами. Малими літерами позначаються перевіряються логічні умови, при цьому використовується символіка, прийнята в математичній логіці. Наприклад, символом р(х<у) позначають логічне умова, виконане в тому випадку, коли нерівність, що стоїть у дужках, істинно. В іншому випадку це умова помилково.

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

Логічними схемами алгоритму називаються вирази, складені з операторів і логічних умов, наступних один за іншим. Від кожної логічної умови починається стрілка, яка закінчується біля якого-небудь з операторів. Наприклад, з операторів А, В, С і логічних умов р і q можна скласти такі логічні схеми:

 , або  

Знак ↑i позначає початок стрілки, знак ↓i — її кінець. Однаковими номерами позначаються початок і кінець однієї і тієї ж стрілки. Стрілки можуть починатися у будь-якого нелогічного оператора.

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

Для запису алгоритмів використовуються такі основні типи операторів: 1) арифметичні оператори; 2) оператори перевірки логічних умов; 3) оператори переадресації; 4) оператори переносу; 5) оператори формування.

1. Арифметичні оператори служать для запису різних арифметичних дій і позначаються початковими буквами латинського алфавіту. Наприклад, оператор А обчислює величину а = аjk-саik, оператор В — величину с = аij. Вибір букв для позначення операцій довільний.

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

3. Оператори переадресації служать для зміни адрес в наказах; для зміни різних параметрів, від яких залежать оператори програми; для відновлення значень параметрів і адрес, які були змінені в процесі роботи алгоритму (програми).

Оператори переадресації позначаються буквою F із зазначенням у дужках змінюваного адреси або параметра. Так, оператор, що змінює параметр i на одиницю, буде позначатися F(i). Оператор, що збільшує параметр i на n одиниць, буде позначатися Fn(i). оператор, параметр i на n одиниць, буде позначатися F-n(i).

4. Оператор перенесення служить для "перенесення" одного параметра на «місце» іншого, або, іншими словами, для заміни одного параметра іншим. Оператори перенесення позначаються [а → b], де а означає, ніж замінюється (що переноситься), b — що замінюється (замість чого переноситься).

5. Оператори формування служать для формування початкових значень деяких операторів алгоритму. Вони переносять деякі заздалегідь запасені накази в певні місця алгоритму. Оператори формування можна використовувати замість операторів переадресації. це особливо зручно, коли число переадресацій може бути різним, а початкове значення параметра — завжди одне і те ж. Наприклад, якщо початкове значення параметра i=l, то оператор формування може бути записаний у вигляді {l → i}. Розглянемо приклад запису операторного алгоритму Ляпунова для підсумовування п'яти чисел: а1 , a2 , а3 , a4 , a5.

Нехай с — параметр, що являє собою суму аі, і=1,…n, оператор Ai обчислює величину сі = cі-1 + аі. Обчислення суми починаємо з i=1. Алгоритм має вигляд: [1 → i] {0 → ci-1}↑' Ai F(i) p (i=6)↑'

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

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

Перетворення схем можна розглядати з двох точок зору. Перший шлях — досліджувати формальні тотожні перетворення схем алгоритмів, пропонується радянським математиком Ю. І. Яновим.

Другий шлях — дослідити змістовні перетворення схем алгоритмів, враховують індивідуальні особливості розв'язуваної задачі.

ДжерелаРедагувати

  • Алферова З. В. «Теория алгоритмов»