22949

СБС-ПРОГРАМИ ТА РЕКУРЕНТНІ ПОСЛІДОВНОСТІ

Лекция

Информатика, кибернетика и программирование

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

Русский

2013-08-04

599 KB

1 чел.

ЛЕКЦІЯ 2:    СБС-ПРОГРАМИ   ТА   РЕКУРЕНТНІ ПОСЛІДОВНОСТІ.

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

  Послідовності

         

називаються рекурентними відносно конструкторів  , якщо всі їх члени, за виключенням перших,  пов’язані співвідношеннями:

(*)   ,  ,  .... , ,  .

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

Приклади рекурентних послідовностей. 

1) Найпростіша рекурентна послідовність - послідовність-константа . Конструктор  – тотожня функція .

2) Арифметична прогресія . з різницею :, . Конструктор  –  функція

3) Геометрична прогресія  зі знаменником  :, . Конструктор  –  функція

4) Гармонічні числа  , ,  задаються системою рекурентних співвідношень:

    .

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

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

Позначимо сукупність натуральних чисел без 1. Кожна система рекурентних послідовностей (*) породжує певну  функцію вигляду ,  яка вектору початкових членів ставить у відповідність послідовність векторів, складених  з решти їх членів, тобто сукупність  . Відповідність  будемо називати   рекурентною. Як правило цікавить не все  значення рекурентної відповідностії, а тільки окремі його члени. Щоб відокремити потрібні  члени,   вводять умову   (предикат)   , яка серед усіх членів значення для даного входу    виділяє вектори, що задовольняють або порушують  . Щоб зробити вибір однозначним, можна обмежитись, наприклад, першим з  членів значення (тобто членом  з найменшим індексом), що задовольняють (порушують) . Якщо всі ці члени  порушують ( задовольняють)  , то такий  вибір  на даному вході  не визначено. Надалі будемо розглядати випадок, коли вибирається перший з членів значення,  що порушує умову.  Будемо позначати нову функцію  і  називати її обмеженням відповідності  за  умовою . Функція  є частковою і має вигляд .     можна розглядати як спеціальну композицію – оператор,  визначений на  відповідностях типу  та ,  результатом якого є функція . Результат  оператора,  застосованого до певної  рекурентної відповідності будемо  називати рекурентною функцією.

Приклади рекурентних функцій….

Нехай певне фіксоване натуральне число. Послідовності

         

називаються рекурентними відносно конструкторів  , якщо всі їх члени, за виключенням  перших,  пов’язані співвідношеннями:

(**)  ,

       ,

         ....

       

Щоб повністю  задати таку систему послідовностей, достатньо задати перші   членів кожної послідовності Решта членів знаходиться за допомогою конструкторів.  Дійсно,  для  2-рекурентної послідовності , наприклад, ,  , … ,   і  т.д.  

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

Індуктивні визначення……

Структурні блок схеми та СБС-програми. Структурні блок-схеми будуються зі своїх базових елементів за допомогою певних  конструкторів і задають певні композиції алгоритмів. Композиція алгоритмів – це операція на алгоритмах, що дозволяють будувати з більш простих алгоритмів більш складні. СБС -програми  - це інтерпретовані структурні блок-схеми.

Послідовне виконання

 

До початкового стану застосовується А1 , його результат подається на А2. Результат А2 є результатом нового алгоритму.

Розгалуження

 

Р є алгоритмом розпізнавання. Семантика: на початковому етапі обчислюється Р. Якщо Р – істина, то обчислюється А1, і його результат є результатом нового алгоритму. Інакше те ж саме з А2.

Обхід

Р є алгоритмом розпізнавання. Семантика: на початковому стані  обчислюється значення Р. Якщо Р – істина, то обчислюється А і його результат є результатом нового алгоритму. Інакше початковий стан залишається без зміни.        

Вибір

Композиція недетермінованого вибору алгоритмам розпізнавання Р12,...Рn та довільним алгоритмам А1, А2,...,Аn ставить у відповідність новий алгоритм. На початковому етапі обчислюється значення всіх Р12,...Рn. якщо серед них є Рі, що приймає значення істини, то запускається відповідний алгоритм Аі. Його результат є результатом алгоритму вибору. Якщо області істинності предикатів Рі попарно не перетинаються, то такий вибір називається детермінованим.в такому алгоритмі існує єдиний шлях до вирішення.

Приклад детермінованого вибору:

 

Приклад недетермінованого вибору:

Циклічна композиція

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

Повторення

                             

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

.

Має місце наступна

Теорема.  Рекурентні функції і тільки вони обчислюється СБС-програмами.

Доведення.  Покажемо,  як за допомогою СБС-програми обчислити   певну рекурентну функцію  . Розглянемо для простоти випадок . Для кожної рекурентної послідовності введемо пару  змінних відповідного типу: ;; … RR,R:.  Потрібна СБС-програма   подана на Мал.? . Чергові нові члени рекурентних послідовностей спочатку зберігаються в додаткових змінних , а потім вже в кінці пересилаються в змінні . Якщо відразу їх записати в  , то будуть втрачені попередні члени, які можуть знадобитися  для обчислення  нових членів інших послідовностей.  Позначимо  функцію, що обчислює дана СБС –програма і покажемо, що для будь-якого набору початкових значеньз .  Нехай  для деяких . Це означає, що існує таке  і такі послідовності значень змінних   , що

(i)      і   (ii)  .  

За побудовою,   для всіх    вектор   співпадає з вектором  з визначення рекурентної функції  і  є тим комопонентом значенням  функції на   початковому векторі  . Але з умов  (і)  та  ( іі) випливає, що   є найменшим  індексом таким, що  , а це означає , що  (.

 

Мал.?

Зауваження. (*)(**)  задають тільки загальну схему можливих співвідношень. На практиці ці співвідношення можуть виявитись досить простими. Зокрема, реально вони можуть залежати  не від усіх, а тільки від окремих аргументів. Наприклад, член рекурентної послідовності  може не залежати від свої власних попередників, а тільки від “чужих” попередників. У цьому разі не має потреби в початкових членах для даної послідовності. У деяких випадках за рахунок підбору порядку оновлення змінних  можна уникнути   дублювання  нових членів (всіх чи частини),  а значить і введення змінних    і т.д.

Прикл. 1.   Дано , . Побудувати СБС-програму для обчислення суми  sin x + sin x2 + ... + sin xn.

Аналіз.

Вх: , .

Вих: .

Зал: .

Вим: для побудови СБС-програми допустимі арифметичні операції та предикати:  +, –, *, /, =, <, а також функція sin.

Проект

 

 

,   

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

Аналогічний вигляд має СБС-програма для  рекурентних послідовностей. Тільки у цьому разі необхідно зберігати останніх членів кожної з  послідовностей. Для цього  вводиться  змінних, а також, як і вище,  ще  змінних для обчислення  нових  членів послідовностей. В тілі циклу після визначення нових членів, необхідно поновити значення решти  змінних.

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

Аналіз

         Вх:  .

 Вих:  .

 Зал: ,,

Вим:  для побудови СБС-програми допустимі арифметичні операції та предикати:  +, –, *, /, =, <.

Проект 

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

Прикл. 3

Аналіз

Вх:

Вих.:

Зал:

Вим: Побудувати СБС –програму без вкладених циклів, арифметика.

Проект

. Покладемо , .

Покладемо , . Тоді  ,  .  і  .

Покладемо , . Тоді  ,  .  і  .

Блок-схема ….

Прикл. 4

Аналіз

Вх:

Вих.:

Зал:

Вим: Побудувати СБС-програму без вкладених циклів, арифметика.

Проект

. Покладемо , .

Покладемо . Тоді  ,   і

, .

Далі нехай  , . Тоді      і .

Блок-схема ….

Прикл. 5  Дано , .Реалізувати „швидке” піднесення до степеня xn з кількістю множень ~ [log2 n].

Аналіз

Вх:  , .

Вих: .

Зал: .

Вим:  Побудувати СБС-програму зі складністю алгоритму ~[log2 n].

Проект

Якщо вибрати стандартний підхід до розв’язку задачі то отримаємо наступні  рекурентні співвідношення

p1 = x

pi = xi-1 * x

C(n) = n-1 – множеннь буде виконано.

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

=

{0, 1} – цифри числа n в двійковій системі.

- випливає з алгоритму переведення числа з десяткової системи числення в двійкову.

Буде виконано k+1 множення.

Наприклад:

                  

b0, b1, ... , bk;         q0, q1, ... , qk

q0 = n

b0 = q0 mod 2

bi = qi mod 2

qi = qi-1 mod 2

pk =

pk – часткові добутки, pn = xn - результат

p0 =  = ( n mod 2 = 0 → 1 # x)

pi = pi-1 * 

ai =

a0 = x

ai-1 =

ai = ai-1*ai-1

pi = (bi = 1 → pi-1*ai # pi-1)

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

Аналіз

Вх:

Вих.:

Зал: . Покладемо .

Вим: Побудувати СБС, базис складають наступні операції на :,  ,  ,  .

Проект

Нехай деяка послідовність і . Покладемо ,  Тоді  має місце . Покладемо , , . Тоді ,  . Виберемо предикат .

PAGE  11


Var X, A, P : Real;

      Q, N : Real;

N := !; X := !; Q := N; A := X;

N mod 2 = 0

P := 1;

P := X;

Q > 0

A := A*A;

    Q := Q div 2;

Q mod 2 = 1

P := P * A;

P!

Р

А2

А1

А2

А1

!

V := tail(V);

                  U := c(head(V),U);

                  

V EMBED Equation.3   EMBED Equation.3  

               F := !; U := head(F); V := F

B := B*X;

                  S := S + sin(B);

                  Inc(I);

I<N

X := !; N := !; S := sin(X); I :=1; B :=X;

Var X, S, B : real;

      N, I : int;

Begin

   Read(X);

   S:=X;

   A:=X;

   B:=X;

   Read(N);

   I:=1;

   While I<N Do

         Begin

             B:=B*X*X;

             A:=A*B;

             S:=S+A;

             Inc(I);

         End;

   Writeln(S);

End.A, B : Real;

      N, I : Word;

K:=K+1

S:=S+A

A:=A×B

B:=B×X×X

Вихід

K<N

X:=! k:=1; S:=A:=B:=X;N:=!

результат

A = an;

B = bn;

C = cn;

           ...

A :=AA;

B := BB;

…R :=RR;

            

AA := f EMBED Equation.3   (A, B, C, ...);

BB := f EMBED Equation.3  (A, B, C, ...);…;

RR := f EMBED Equation.3  (A, B, C, ...);

   ... ;

Q(A, B,  ...,R)

A := a1; B:= b1; ... ;R:=r EMBED Equation.3  ;

Var  EMBED Equation.3  ;  

       EMBED Equation.3  ; …

     RR,R: EMBED Equation.3  

      

      

      ...

- EMBED Equation.3  

EMBED Equation.3  

x≥0

x>0

А

Р

A1

An

A2

Р1

Рn

Р2

А

Р

А2

А1

F := F1 + F2;

F1 := F2;

F2 := F;

Inc(I);

I < N

F1 := 1; F2 := 1;

         F := 1; I :=2;N:=!

Var F, F1, F2, N, I : int;

EMBED Equation.3  

-1

1

0

x<0

x>0

x=0

sign(x)

Р

А


 

А также другие работы, которые могут Вас заинтересовать

83483. Режим Антарктики. Секторальний принцип розподілу арктичних просторів 38.21 KB
  Природні ресурси військовостратегічна безпека міжнародні сполучення ось причини уваги яка приділяється режиму Арктики. Правовий режим Арктики встановлюється міжнародним правом а також законами приарктичних держав. Простори Арктики історично поділені між Росією Канадою США Данією та Норвегією на п\'ять секторів.
83484. Концепція загальної спадщини людства 38.35 KB
  З часом вона стала концепцією загальної спадщини людства поширивши захист на інтереси не тільки нинішнього але і майбутніх поколінь. У позитивне міжнародне право концепція загальної спадщини була введена Договором про принципи діяльності держав по дослідженню і Використанню космічного простору включаючи Місяць і інші небесні тіла 1967 р. Вони отримали право на участь у встановленні режиму загальної спадщини і в його використанні за ними закріплене праві виходу до моря через територію прибережних держав.
83485. Населення та громадянство в міжнародному праві 38.91 KB
  Населення будьякої держави складається з наступних категорій: громадян даної держави іноземних громадян осіб без громадянства. Виділяють наступні способи набуття громадянства: філіація; натуралізація укорінення; поновлення в громадянстві реінтеграція; дарування громадянства; оптація; трансферт. Філіація або набуття громадянства за народженням базується на двох принципах: права крові jus snguinis та права ґрунту jus soli. Різновидом натуралізації є спрощений порядок набуття громадянства певними категоріями осіб.
83486. Громадянство і підданство 33.42 KB
  У доктрині міжнародного права і національного законодавства деяких держав замість терміна громадянство використовується термін підданство причому в якості цілком рівнозначних. Підданство відрізняється від громадянства насамперед тим що воно: поперше є інститутом монархічної держави і означає політикоправовий зв\'язок підданого з монархом; подруге такий правовий зв\'язок характеризується не взаємним і рівнообов\'язковим як при громадянстві а одностороннім характером: підданий виконує перед монархом тільки обов\'язки а монарх щодо...
83487. Придбання і втрата громадянства 37.17 KB
  Виділяють наступні способи набуття громадянства: філіація; натуралізація укорінення; поновлення в громадянстві реінтеграція; дарування громадянства; оптація; трансферт. Філіація або набуття громадянства за народженням базується на двох принципах: права крові jus snguinis та права ґрунту jus soli. Різновидом натуралізації є спрощений порядок набуття громадянства певними категоріями осіб.
83488. Режим іноземців. Особи без громадянства 35.93 KB
  До іноземців окрім іноземних громадян також відносять осіб без громадянства. Режим правове положення іноземців визначають як сукупність прав та обовязків іноземців на території даної держави. Режим іноземців встановлюється внутрішнім законодавством держав з врахуванням їх міжнародних зобовязань.
83489. Біженці, вимушені переселенці. Право притулку 39.38 KB
  В якості біженців не розглядаються особи що винні у скоєнні: злочину проти миру воєнного злочину або злочину проти людяності; важкого злочину аполітичного характеру поза країною що надала притулок; дій що суперечать цілям та принципам ООН. Право притулку право кожної людини шукати притулок від переслідування в інших державах та користатися цим притулком а також право держави дозволяти вїзд та проживання на її території особі яка переслідується в іншій державі за політичними мотивами. Територіальний притулок означає що держави...
83490. Покоління прав людини 37.26 KB
  До першого покоління відносяться лише громадянські і політичні права. Тому права першого покоління іменуються негативними оскільки їх реалізація передбачає невтручання держави Початок формування другого покоління прав людини здебільшого повязують із прийняттям Веймарської конституції 1919 р. Друге покоління складають соціальні економічні та культурні права. Це покоління позитивних прав оскільки їх реалізація потребує втручання з боку держави та зі лежить від рівня економічного розвитку держави.
83491. Класифікація прав і свобод людини 34.69 KB
  До громадських відносяться наприклад право на життя і особисту недоторканністьправо дотримуватися своєї думки і вільно її висловлювати свобода пересування. До політичних прав перш за все відноситься право брати участь у веденні державних справ обирати і бути обраним на основі загального і рівного виборчого права. Зокрема виділяють: право на працю включаючи право на справедливі і сприятливі умови праці; право на створення профспілок і на проведення страйків; право на соціальне забезпечення право сімї на охорону і допомогу право на...