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)

Р

А


 

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

43710. Структура дистанционного курса (ДК) «Изготовление и испытание ПТМ» 6.4 MB
  В работе представлена структура дистанционного курса (ДК) «Изготовление и испытание ПТМ»; даны рекомендации по оформлению ДК, предложена информационная, содержательная и контрольно-мониторинговая части ДК «Изготовление и испытание ПТМ».
43711. Розробка моделі цінності інформаційних ресурсів для оптимізації побудови системи захисту інформації 302.91 KB
  Мета роботи розробка моделі цінності інформаційних ресурсів для оптимізації побудови системи захисту інформації. Обєкт дослідження цінність інформації якою володіє організація що в даній роботі позиціонується як інформаційні ресурси та входить до складу активів організації. Результатом роботи є адитивна модель цінності інформації яка включає основні елементи цінності легка для сприйняття та передбачає можливість модернізації в залежності від специфіки області в якій застосовується. Продовжити вдосконалення даної моделі можна більш...
43712. Разработка программного обеспечения для сжатия изображения 4.51 MB
  Особенность изображений состоит в том, что отдельные элементы изображения находятся в определенной связи с соседними элементами. Поэтому большинство алгоритмов преобразования изображений носит групповой характер (то есть группа пикселей)
43713. Разработка мероприятия по совершенствованию системы управления персоналом на ОАО АКБ «РОСБАНК» 17.41 MB
  Управление людьми имеет практически такую же древнюю историю, как и человечество. По мере экономического развития и появления крупных организаций, управление персоналом превратилось в особую управленческую функцию, требующую специальных знаний и навыков.
43714. Повышение технического уровня подземного горношахтного оборудования 91.49 KB
  Запасы угля Вскрытие шахтного поля. Основной базой каменного угля Украины по-прежнему остаётся Донбасс. Обогащение угля не осуществляется. Основными потребителями угля являются ТЭЦ.
43715. Дослідження методів обробки пластикових матеріалів при виготовленні пакування 12.3 MB
  В результаті розробки проекту необхідно забезпечити високу продуктивність гнучкість оперативність випуску високоякісної продукції. Сучасні тенденції виробництва пластикового пакування в Україні Сучасні тенденції розвитку ринку пакувальної продукції України Використання полімерних матеріалів при виготовленні поліграфічної продукції Види полімерних матеріалів що використовуються у поліграфії Система маркування пластику Переробка пластикових відходів Етапи і методи переробки пластикових відходів
43717. Туристический кластер Псковской области 1.72 MB
  Отечественные туристские кластеры в контексте национальной стратегии отраслевого развития История развития туризма в Псковской области выступает своеобразным катализатором социально экономического развития. Задачи: Дать характеристику понятию туристский кластер; Рассмотреть классификацию туризма; Исследовать состояние и перспективы туризма в Псковской области; Охарактеризовать роль кластеров в современной экономики; Выявить возможные пути развития данной отрасли.