Зубенко, Омельчук - Програмування. Поглиблений курс

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

Аналіз.

Вхід: ε R . Вихід: s R .

1 ≤ k ≤ n |(−1)[lg k ] /k |> ε&|(−1)[lg(n +1)] /(n +1)|≤ ε.

Вимоги: побудувати стандартну програму Prog9.10 для обчислення s . Інші вимоги – ті самі, що й у прикл. 2.29.

Проектування. Початок такий, як і для обчислення сум. Знову ві- зьмемо три послідовності: вхідну послідовність-константу ε , лічиль-

ник k і опорну – із часткових сум s1 ,s2,...,sn ,sn +1,... таку, що sn = s .

Таким чином, маємо потрібну рекурентну систему. Лишилося знайти фільтр Q . Щоб припинити ітерацію, достатньо перевірити на наступно-

му кроці, чи буде модуль нового доданка ( = 1/(k +1)) більшим ніж ε . Як-

що так, то продовжити ітерацію, якщо ні – вийти з неї. Отже, фільтром Q(k,ε) може бути умова 1/(k +1) > ε. Остаточно система (*) має вигляд:

a1 = 0,ak = (k < bk −1 → ak −1|ak −1 +1);b1 =10,bk = (k < bk −1 → bk −1|bk −1 *10);s1 =1,sk = sk −1 + (ak %2 = 0 →1|−1)/k;k1 =1,k = (k −1) +1;

ε − константа.

За побудовою s = μQ* (ε).

Кодування. Змінні програми Prog9.10: a,b,s,k та ε – без дублі- катів. Сама програма Prog9.10 має вигляд:

211

ПРОГРАМУВАННЯ

{ ε :=!; k:=1;s:=1;a:=0;b:=10; while (1/(k+1)> ε ) {k:=k+1; a:=(k<b →a |a+1);

b:=(k<b →b | b*10); s:=s+(a%2=0 →1 | -1)/k;

}

}

Тут, як і в усіх попередніх програмах, удалося уникнути введення дублікатів змінних за рахунок спеціального порядку їхнього оновлен- ня: спочатку змінився лічильник, потім – змінна a (це принципово, тому що її оновлення залежить від поточного, а не нового значення b), а потім, у довільному порядку, – змінні b та s ■

Приклад 2.31. Швидке піднесення до степеня. Дано n N . Реалі- зувати піднесення до степеня в півгрупі P = (A,o) з кількістю множень

в обчисленні c(n) = О(log2 n) .

Аналіз

Вхід: x A , n N . Вихід: p R .

Залежність: p = xn .

Вимоги: побудувати стандартну програму Prog9.11 для обчислення p із кількістю множень c(n) =О(log2 n) . Базовою Ω -системою є пів-

група P = (A,o) і натуральна арифметика зі стандартними операціями

та предикатами.

Проектування. Якщо вибрати прямий підхід до обчислення степе- ня й покласти p1 = x, pk = pk −1 o x , то отримаємо кількість множень c(n) = n −1.

Щоб підвищити ефективність алгоритму, подамо показник степеня n

212

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

результаті ai −1 . Залишилось визначитись із фільтром обчислення.

Фільтр із лічильником не зовсім влаштовує, оскільки він потребує до- даткового обчислювання значення k . Менш очевидним, але набагато простішим, є фільтр Q(qi ) = (qi > 0). З ним отримуємо систему (*):

Кодування. Змінні програми Prog9.11 a,b,x,n,p,q – без дубліка- тів. Програма Prog9.11:

{x:=!;n:=!;a:=x;q:=n;b:=n%2; p:=(n%2=1 →x|1);

while (q>0) {a:=a oa; q:=q/2;

b:=q%2;

p:=p o(b=1 →a|1);

}

}

Її можна дещо удосконалити, усунувши змінну b. Ця змінна віді- грає роль логічного прапорця, який можна замінити його поточним значенням q%2. Новий варіант програми Prog9.11 може бути таким:

213

ПРОГРАМУВАННЯ

{x:=!;n:=!;a:=x;q:=n; p:=(n%2=1 →x|1);

while (q>0) do {a:=a oa; q:=q/2;

p:=P o(q%2=1 →a|1);

}

}■

Нескладно перевірити, що кількість множень c(n) у обчисленнях за програмою перебуває в межах c(n) ≤ 2[log2 n], що задовольняє

умову задачі.

Приклад 2.32. Дзеркальне обернення кортежів.

Аналіз.

Вхід: f T * , k ≥ 0 . Вихід: g T * .

Залежність: g = f R , де f R – дзеркальне обернення кортежу f . Вимоги: побудувати стандартну програму Prog9.12 для обернення

кортежів. Нехай f = [f1,..., fn ]. Базовими операціями є: взяття голови head (f ) = f1 , взяття хвоста tail (f ) = [f2...fn ] та pre - додавання ком-

поненти в початок кортежу. Базовим предикатом є рівність = . Проектування. Нехай f = [f1,..., fn ] і u1,...,ui ,...,uk – опорна послі-

За побудовою g = μQ* (f ).

214

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

Кодування. Змінними в програмі є v,u,f без дублікатів. Програма Prog9.12 будується стандартно за рекурентною системою (*) :

{f:=!;v:=f;u:=head(f); while (v ≠ []) {v:=tail(v);

u:=pre(head(v),u));

}

}

■

Увага! Коректність побудованих у прикл. 2.27–2.32 програм нескладно довести математично. Для цього достатньо перевірити коректість рекурентних функцій, породжених відповідними системами (*), і потім послатися на теорему 2.5 ►

Повернемося до прикл. 2.27. Небхідно довести, що s = μQ* (n,x ). Для

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

індуктивний перехід має місце і з повноти індукції випливає P (x ).

215

ПРОГРАМУВАННЯ

коньюнктивного члена випливає з означення лінійного порядку на множині натуральних чисел. Отже, ми довели, що μQ* (n,x ) = sn = s ■

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

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

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

*Література для CР: СБС і алгоритми – [19, 32, 49, 50]; pекурентні співвідношення й функції – [19, 28, 122].

Контрольні запитання та вправи

1.Дати визначення структурних композицій.

2.Що таке ССП?

3.Як інтерпретуються ССП?

4.Що таке структурний алгоритм і абстрактна структурна програма? Яка між ними різниця?

5.Що таке циклічний структурний алгоритм?

6.Що таке рекурентна послідовність?

7.Що таке конструктор рекурентної послідовності?

8.Дати визначення системи m -рекурентних послідовностей.

9.Що таке рекурентна функція?

10.Дати визначення μ -оператора.

11.Як пов'язані рекурентні функції й циклічні блок-схеми?

12.Довести теорему 2.5 для параметризованих функцій і програм.

13.Показати, що теорема 2.5 залишається вірною, якщо у стандартних програмах зафіксуквати базову алгебричну систему, а серед конструкторів у μ -операторах припустити будь-які її похідні операції.

14.Показати, що композиція мінімізації (див. вправу 15 із підрозд. 1.3) є частковим випадком μ -оператора.

Вказівка. У вправах 15-21 необхідно побудувати стандартні

У вправі 20 мається на увазі стандартний арифметичний базис. Усі числа розглядаються в десятковій системі.

216

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

15.Дано n N.

а) З'ясувати, чи містить десяткове подання числа n вхо- дження цифри 7, і підрахувати кількість таких входжень.

б) Поміняти місцями першу й останню цифри в числі. в) Приписати одиницю ліворуч і праворуч до числа n.

16.Дано a,b,c,d N. Знайти найбільший спільний дільник цих

чисел. Використати алгоритм Евкліда для відшукання НСД двох натуральних чисел за допомогою віднімання.

18.Дано a R ,n N . Обчислити:

а) sin x + sin2 x +... + sinn x; б) sin x + sin2x +... + sinnx;

б) sin x + sinsin x +... + sin...sin x .

144444424444443

n

20. Дано x R,n N. Обчислити, уникнувши вкладених циклів:

21.Даноx R,n N . Реалізувати швидке множення n ×m із кількістю додавань O([log2 n]).

22.Довести коректність стандартних програм із прикл. 2.28-2.32.

217

ПРОГРАМУВАННЯ

2.6. Індуктивні означення

¾Індуктивні означення множин та їхніх систем

¾Індуктивні означення функцій

¾Рекурсивні специфікації

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

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

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

2.6.1. ІНДУКТИВНІ ОЗНАЧЕННЯ МНОЖИН ТА ЇХНІХ СИСТЕМ

Індуктивні означення базуються на понятті алгебричного замикання (див. підрозд. 1.4.1). Тому повернемося до нього й розглянемо детальніше.

усім множинам Bi , i ≥ k, для деякого k N . Тоді за означенням або

218

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

b Bk −1 , або b побудований з елементів сукупності Bk −1 за допомогою

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

Лема 2.2. Кожний з елементів замикання B* є значенням певного Ω -терму.

Доведення. Зафіксуємо певну сигнатуру констант Ωc для елементів

елементам із Bi , i N , відповідають терми елементів із Bi −1 і побудо- вані з них терми вигляду fini (t1,...,tn i ) ■

Нехай U – певний універсум елементів. Структура індуктивного означення (ІО) довільної підмножини M елементів універсума має такий вигляд:

(Б) База індукції. Фіксується певна підмножина M0 U апріорі виділених базових об'єктів.

(І) Індуктивний перехід. Вибирається певна сукупність {Fi }

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

(ПС) Повнота cлабка. Вибирається певний предикат-фільтр P (x ), визначений на універсумі U , який здійснює відбір елементів

def

замикання U0* до означуваної множиниM : M = P(U 0* ).

Фільтри, подібні P (x ), називаються термінаторами, а елементи, які вони пропускають – термінальними. Наприклад, добре відома роль термінатора P (x )= "x Σ* " у КВ-граматиках, який з усіх слів, що виводяться з аксіоми, відбирає слова в основному алфавіті.

219

ПРОГРАМУВАННЯ

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

Увага! Якщо всі базові й усі нові побудовані за ними елементи на- лежать означуваній множині, то M =U0* і фільтр стає непотрібним. У

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

Індуктивно означені множини будемо називати також просто інду- ктивними й позначати M = M (M0,{F i },P ). У математичній логіці

елементи з M0 – аксіомами. Виведенням елемента a з аксіом назива- ється послідовність елементів a1,...,am = a така, що для всіх 0 ≤ i ≤ m ai є або аксіомою, або висновком певного правила виведення з гіпо- тез, що належать a1,...,ai −1 . Індуктивно означену множину M (M0,{F i },P ) складають теореми – ті елементи, що можуть бути ви-

ведені з аксіом і є термінальними.

Наведемо кілька важливих прикладів індуктивних множин. Увага! На практиці при введенні індуктивних означень фіксують

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

Приклад 2.33. Натуральні числа (ІО1 ). (Б1 ) 0 – натуральне число.

(І1 ) Конструктор s : N → N породжує наступне за порядком число, тобто s (n )= n +1.

Дійсно, 0 s (0)(=1) s (s (0))(= 2) тощо ■

Приклад 2.34. Слова (ІО2 ).

Нехай Σ = {a1,a2,...,an } – довільний алфавіт.

(Б2 ) ε Σ* – порожнє слово й літери алфавіту Σ є базовими. (І2 ) Конструктор pre : Σ× Σ* → Σ* визначимо так:

pre(a,b1b2...bm ) = ab1b2...bm .

220