2.5. Структурні програми й рекурентні функції

• Структурні схеми програми і структурні алгоритми

• Системи рекурентних послідовностей

• Рекурентні функції

• Техніка побудови стандартних програм

Ключові слова: структурна схема програм, інтерпретація ССП, структурний алгоритм, абстрактна струкутрна програма, система рекурентних послідовностей, конструктор рекурентної послідовності, система m-рекурентних послідовностей, вхідна, опорна та проміжна послідовність, вимір системи рекурентних послідовностей, -оператор, рекурентна та m-рекурентна функція, параметризована рекурентна функція.

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

Однак спочатку розглянемо лінійну форму структурних алгоритмів.

2.5.1. Структурні схеми програм і структурні алгоритми

Структурні схеми програм (ССП) є словесними формами структурних блок-схем. Вони теж визначаються алгебрично як елементи замикання, породженого базовими схемами , , за допомогою ключових слів while, do, case, detcase, if, else та допоміжних символів {, }, (, ), :.Схеми та подають довільний та заключний предикати²¹. Нехай – довільні ССП. Нові ССП будуються таким чином:

1) складена CСП: ;

2) розгалуження: else ;

3) обхід: ;

4) недетермінований вибір: case ;

5) детермінований вибір: detcase , де – це або ;

6) ітерація: while ( )P;

7) повторення: do P while ( ).

Отже, ССП є або базовими, або мають вигляд 1)–7). Фактично ССП є термами регулярної алгоритмічної алгебри, записаними в стилі, наближеному до мов програмування (див. 1.4.3). При цьому в ССП, на відміну від регулярних термів, логічні вирази не структуризовані.

Інтерпретуються ССП так само, як і структурні блок-схеми. Входження елементів Box та Con1, Con2 замінюються елементарними перетвореннями станів і предикатами певного обчислювального простору .

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

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

Для покладемо = .

Увага! Щоб зробити ССП і алгоритми зрозумілішими, будемо вставляти в їхній текст коментарі-пояснення вигляду /*…*/, які не впливають на дію програм і можуть бути без усяких наслідків вилучені з них.

Для = . /* Множення */

Для . /* Розгалуження */

Для = . /* Обхід */

Для … .

/* Вибір */

Для detcase = | … | .

/* Детермінований вибір */

Для = ./* Ітерація */

Для = . /* Повторення */

Повернемося до структурних алгоритмів із прикл. 5.3.

Приклад 2.22. Структурні алгоритми для обчислення функцій , і найбільшого спільного дільника двох чисел:

/*обчислює функцію */;

/*обчислює */;

{ do } /*обчислює НСД ( ), де елементарні операції і предикати ті самі, що й у прикл. 3.3*/■

Важливу роль відіграють абстрактні структурні програми. Це структурні алгоритми, зі спеціально структурованими станами й операторами присвоювання в якості елементарних перетворень станів. Праві частини цих операторів задаються термами певної алгебричної системи (будемо називати її базовою), а ліві є іменами, що належать деякій сукупності імен . При цьому терми (у тому числі і предикатні) трактуються як еквітонні -арні операції, імена змінних у яких розглядаються як операції читання (див. прикл. 5.2). Предикатні терми називаються умовами. Стани таких програм – це інформаційні поля об’єктів з іменами з і значеннями з універсума U. Абстрактні програми можуть мати параметри - фрейми і , які визначають відповідно вхідні і вихідні змінні. Графіками таких програм є певні оператори . Говорять, що абстрактна програма обчислює векторний аналог свого оператора. Якщо абстрактна програма не містить схем детермінованого вибору, то її називають стандартною. Базова алгебрична система може бути багатосортною системою.

Абстрактні структурні програми над багатосортними базовими системами є формальними моделями програм мов програмування з простими структурами даних.

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

Приклад 2.23. Обчислення через залишки від ділення чисел:

/*Вх: x,y Вих: x*/

while (x y) do if (x<y) y y%x; else x x%y;

Параметризований векторний аналог даної програми зі вхідними змінними і вихідною збігається з (див. прикл. 5.4). Станами програми є інформаційні поля з двома змінними: , де , які змінюються в процесі обчислення операторами присвоювання y y%x; та x x%y;. У результуючому стані значення змінних однакові й дорівнюють ■