Лекція №8 (2 год.)

ТЕМА: Формальні перетворення алгоритмів

МЕТА:  

навчальна: ознайомлення з формальними перетвореннями алгоритмів;

розвиваюча: розвивати поняття алгоритму;

виховна: виховувати інтерес до комп’ютерних наук

ОБЛАДНАННЯ: дошка

ПЛАН

1 Еквівалентність як метод формальних перетворень

2 Еквівалентність операторних алгоритмів

3 Формальні перетворення логічних схем

Зміст лекції

1 Еквівалентність як метод формальних перетворень

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

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

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

В «чистому виді» поняття еквівалентності двох алгоритмів U₁ й U₂ будемо визначати в такий спосіб. Для кожного алгоритму вводиться поняття «входу» й «виходу». Для кожного входу, що має сенс для даного алгоритму, виконання алгоритму може приводити до деякого виходу. Нехай x₁ й x₂ — входи алгоритмів U₁ й U₂ відповідно. Алгоритми U₁ й U₂ уважаються еквівалентними, якщо з умови x₁ = x₂ слідує, що якщо хоча б один алгоритм, наприклад U₁, має вихід y₁ то й інший алгоритм також має вихід y₂, причому y₁=y₂.

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

У цьому випадку між деякими входами x₁ алгоритму U₁ і входами x₂ алгоритми U₂ конструктивно задається деякий ізоморфізм I (у цьому випадку просто як однозначну відповідність,). Аналогічно задається деякий ізоморфізм J між виходами y₁ й y₂ алгоритмів U₁ й U₂ відповідно.

Предикат від двох конструктивних об'єктів А и В «бути у відповідності, заданому ізоморфізмом L» будемо позначати через А_L~В.

Еквівалентність тепер буде визначатися в такий спосіб. Алгоритми U₁ й U₂ уважаються еквівалентними, якщо з умови х₁~х₂ випливає, що якщо хоча б один алгоритм має вихід y₁, то й інший алгоритм також має вихід y₂, причому y₁~y₂.

Різні види еквівалентності відрізняються тим, як визначаються «входи» й «виходи» алгоритму, а також тим, як фактично вибираються ізоморфізми I й J.

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

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

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

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

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

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