22949

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

Лекция

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

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

Русский

2013-08-04

599 KB

0 чел.

ЛЕКЦІЯ 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)

Р

А


 

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

57951. НАСЕЛЕННЯ ТА ДЕРЖАВИ ПІВДЕННОЇ АМЕРИКИ 41.5 KB
  Мета: поглибити та систематизувати знання про освоєння території материка походження та формування населення материка його кількість склад та розміщення; ознайомити з політичною картою Південної Америки...
57952. Географія материків та океанів 87 KB
  За картою географічних поясів та природних зон визначте природні зони Північної Америки та вкажіть зони що займають найбільшу площу. Але окремі природні зони ми з вами ще ніколи не розглядали крім того сьогодні ви довідаєтесь чому особливе місце в розподілі природних комплексів материка належить рельєфу та впливу океану.
57953. Подорож героїв казки Г.К. Андерсена «Снігова Королева» по країні Синтаксис 221 KB
  Але перш ніж розпочати наш урок пропонуємо вам визначити капітана кожної команди експерта який буде слідкувати за роботою кожного учня в групі а також визначитися із назвою команди клас розподілений на 3 команди.
57954. Англія. Бінарний урок всесвітньої історії – англійської мови 180.5 KB
  Мета: Всесвітня історія ознайомити учнів з особливостями розвитку капіталістичних відносин в Англії особливостями Реформації в Англії та основними напрямками зовнішньої політики в 16 ст. Після уроку учні зможуть: Називати час правління Єлизавети...
57955. Антарктида 80 KB
  Мета навчальна: закріпити та узагальнити знання і вміння учнів з теми: «Антарктида»; поглибити їх знання за допомогою цікавих фактів про вивчений об’єкт, вдосконалювати вміння та навички роботи з картою, формувати нестандартне мислення...
57956. Антарктида і Антарктика. Загальні відомості. Відкриття та сучасні наукові дослідження 248 KB
  Сформувати поняття «Антарктика»; сприяти формуванню в учнів знань про географічне положення; поглибити і систематизувати знання про відкриття та сучасні дослідження Антарктиди в рамках міжнародного співробітництва; продовжити формування навичок встановлювати закономірності поширення природних умов
57957. Антарктида. Своєрідність географічного положення. Відкриття материка. Льодовиковий покрив 33 KB
  Мета уроку: дати поняття Антарктика и Антарктида льодовий материк планети; вивчити загальні відомості про материк: своєрідність ГП материка його розміри; розглянути відкриття Антарктиди та сучасні наукові дослідження материка...
57958. встралия – самый маленький материк Земли 60.5 KB
  Перед началом соревнования вам ребята надо потренироваться повторить изученный материал о природе Австралии. На протяжении трех уроков вы составляли вопросы об особенностях природы Австралии теперь у вас есть возможность задать их своим одноклассникам и выслушать ответы. Какой остров расположен к северу от Австралии Правила игры: В течение изучения материка ученики составляют вопросы по параграфам. По плану ФГП ученики сравнивают физикогеографическое положение Австралии с ФГП...
57959. ГЕОГРАФІЧНОГО ПОЛОЖЕННЯ. ІСТОРІЯ ВІДКРИТТЯ І ДОСЛІДЖЕННЯ. ГЕОЛОГІЧНА БУДОВА. ФОРМИ РЕЛЬЄФУ ТА КОРИСНІ КОПАЛИНИ АВСТРАЛІЇ 108 KB
  Мета: сформувати в учнів загальне уявлення про своєрідність та особливості природи Австралії; продовжити формування навичок учнів складати характеристику географічного положення материка за планом відшукувати закономірності розташування форм рельєфу та корисних копалин...