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

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

Побудуємо контекстно вільний мову L2. який будемо називати алгоритмическим. Для цього скористаємося нотацією Бекуса. Пропозиція мови L2 будемо позначати метасимволом (запис первинного алгоритму):

<запись первичного алгоритма>:: = <безусловный приказ> ï <условный приказ>

<безусловный приказ>:: = <метка> <разделитель I> <знак действия> <разделитель II> <отсылка> <разделитель III>

<условный приказ>:: = <метка> <разделитель IV> <знак условия> <разделитель V> <отсылка> <разделитель VI> <отсылка> <разделитель III>

<отсылка>:: = <метка> ï <стоп>

Для того щоб L2 був повністю визначений, необхідно задати за допомогою метаформул значення метасимволов:

<метка> <разделитель IV>

<стоп> <разделитель V>

<разделитель I> <разделитель VI>

<разделитель II> <знак действия>

<разделитель III> <знак условия>

Ми цього не будемо робити, визначаючи тим самим не одну мову, а клас мов. Як L2 може бути прийнятий будь-який з конкретних мов цього класу. Зауважимо тільки, що роздільники повинні бути обрані так, щоб вони однозначно поділяли накази на відповідні частини, а роздільник III повинен бути відрізнити від роздільник VI, а також від будь-відсилання і мітки.

Для того, щоб наділити запис первинного алгоритму змістом, задамо наступне правило.

П р а в і л про виконання первинного алгоритму.

1) Переглядаючи запис первинного алгоритму з початку, знайти перший наказ; перейти до п.2.

2) Якщо розглянутий наказ є безумовним, перейти до п.3, інакше до п.5.

3) Застосувати операцію, відповідну знаку дії даного наказу, до операнду; знайти відсилання в даному наказі; перейти до п.4.

4) Якщо обрана відсилання має вигляд <стоп>, то процес закінчено; інакше, переглядаючи запис алгоритму з початку, знайти наказ, мітка якого однакова з відсиланням, і перейти до п.2.

5) Якщо операнд задовольняє умові, відповідному знаку умови даного наказу, то перейти до п.6, інакше - до п.7.

6) Знайти першу відсилання даного наказу; перейти до п.4.

7) Знайти другу відсилання даного наказу; перейти до п.4.

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

Запис первинного алгоритму, що розглядається разом з правилом його виконання, називається первинним алгоритмом.

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

У першому випадку говорять, що первинний алгоритм застосуємо до даного операнду, а в другому і третьому випадках - що непридатний.

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

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

Нехай мова операндів L2 має в якості пропозицій тільки слова в алфавіті А. Будемо вважати, що завданням цього алфавіту визначено граматичний клас <буква в А>. Будемо вважати, що, крім того, для завдання L2 потрібно єдина формула Бекуса <операнд>:: =<буква в А> ï <операнд> <буква в А>

Алгоритмічний мову L1 конкретизуємо наступним чином:

<метка>. = <цифра>ï<метка> <цифра>

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

Широке формальне визначення алгоритму. Ми знаємо вже, що клас первинних алгоритмів заданий, якщо задані дві мови: L1 і L2. причому пропозиції першого з них оголошені записами алгоритмів, а речення другого - записами операндів і, якщо задано правило виконання первинних алгоритмів, яке застосовується до парам: запис алгоритму, запис операнда.

Перший пункт загального визначення алгоритму говорить:

1) Первинні алгоритми - це алгоритми.

Але загальне поняття алгоритму істотно ширше. Його другий пункт говорить:

2) Якщо задані дві мови L1 і L2. причому пропозиції першого оголошені записами алгоритмів, а речення другого - записами операндів, і якщо заданий деякий алгоритм W, операндами якого є конструкції, одержувані зв'язуванням кожного пропозиції з L1 з n пропозиціями мови L2 за допомогою цілком певного зв'язку рангу n + 1, то задано сімейство n-місних алгоритмів.

Нарешті, третій пункт загального визначення говорить:

3) n-місні алгоритми - теж алгоритми.

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

Одномісним називається n-місцевий алгоритм, для якого n = 1. Первинні алгоритми теж будемо називати одномісними.

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

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

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

Такий алгоритм природно назвати алгоритмом виконання для даного сімейства первинних алгоритмів. Наведена теорема, хоча і не дозволяє при визначенні поняття алгоритму відмовитися від визначення первинних алгоритмів, все ж "зрівнює в правах" первинні алгоритми з первинне.

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

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

Нехай L2 =<> - алгоритмічний мову, L1 =<> - мова операндів, z - зв'язок (n + 1) -ого рангу і W - алгоритм виконання. Позначимо через конструкцію, що отримується шляхом зв'язування мови L2 і n пропозицій мови L1. Тоді рівність означає, що t є алгоритмом і що. При цьому - запис бажаного результату.

Для кожного сімейства алгоритмів, що визначається деяким алгоритмом виконання W, безліч L3 = записів усіх можливих шуканих результатів є формальною мовою. Таким чином, кожному сімейству алгоритмів відповідає ще один формальний мову: мова шуканих результатів. В окремому випадку він може бути підмножиною мови операндів.

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

Про п р е д е л е н і е. Два алгоритму, які мають однакові записи і еквівалентні, є одним і тим же алгоритмом (або екземплярами одного і того ж алгоритму).

Тепер неважко уточнити наведене вище загальне визначення алгоритму (вірніше, доповнити його).

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