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)

Р

А


 

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

81679. Критика просветительского реализма. Критическая деятельность А.Н.Радищева, Н.И.Новикова,И.А.Крылова,В.И.Лукина и др.Н.И.Новиков как создатель 1й рус.литерат.энциклопедии «Опыт исторического словаря о российских писателях» 34.82 KB
  Оживление журнальной и книгоиздательской деятельности во многом изменили характер и проблематику литературно-критических споров: от обсуждения вопросов версификации выдержанности жанрового канона стилевых и грамматических норм критики обращаются к постановке более широкого круга проблем: подражательности и самобытности литературы природы писательского таланта роли отдельных жанров в современном литературном процессе назначения сатиры исторического пути развития отечественной словесности и др. Развитию литературной критики способствовал...
81680. Сентименталистская критика. Типологический анализ литературно-критических статей Н.М.Карамзина («Что нужно автору?», «Отчего в России мало авторских талантов?», предисловие к переводу «Юлия Цезаря» Шекспира, «Пантеон российских авторов» и др.) 37.9 KB
  Пересматривая представление о подчиненности индивидуальной сферы жизни государственному бытию свойственное эпохе классицизма сентименталисты отстаивали приоритет жизни частной подчеркивали внесословную ценность личности нельзя не вспомнить карамзинское: И крестьянки любить умеют. В произведениях русских писателейсентименталистов Н М Карамзина П. Крупнейшим представителем русской критики эпохи сентиментализма был основатель этого литературного направления в России Николаи Михайлович Карамзин 1766 1826. Многогранная деятельность...
81681. Развитие журналистики как стимул развития русской критики 18в.(проблема взаимосвязи критики и журналистики; проблема читательской аудитории периодического издания). «Московский журнал» Н.М.Карамзина 32.38 KB
  проблема взаимосвязи критики и журналистики; проблема читательской аудитории периодического издания. Московский журнал Н. Журналистика как особая сфера общественной деятельности возникала у каждого народа на достаточно высокой ступени социального развития.
81682. Біологічне, психічне і соціальне в людині 25.58 KB
  Тобто людина є біологічним творінням. Однак як і будьякий біологічний вид людина характеризується певною сукупністю видових ознак. Кожна людина унікальна неповторна своєрідна в практичній діяльності.
81683. Взаємодія свободи і необхідності в житті людини 27.07 KB
  Природа та класифікація цінностей За традиційною класифікацією цінності поділяють на матеріальні цінності які існують у формі речей одяг продукти харчування техніка храм картина і духовні моральні релігійні художні політичні та ін. Їх також не можна однозначно кваліфікувати як матеріальні чи духовні цінності. При цьому матеріальними цінностями їх іноді називають благами вважають економічні технічні і вітальні стан здоров\'я екології цінності які задовольняють тілесне буття людини а духовними релігійні святість...
81684. Функціональний аспект цінностей 24.82 KB
  Загалом цінності виконують такі функції. Зясовуючи що є добро прекрасне істина справедливість тощо цінності конституюють сенс людського життя утворюють його духовну основу. У житті людини і суспільства цінності визначають напрями зразки діяльності.
81685. Оцінка та істина 24.83 KB
  Оцінка як підведення під норму правило закон. За такої ситуації оцінка виявляє себе як акт пізнання щодо відповідності вчинку чи творіння людини нормі. Як і в першому випадку підведення під норму є конституюванням визнанням цінності; 3 оцінка як вибір з поміж двох і більше цінностей.
81686. Сутнісні принципи культури 26.79 KB
  Одним із головних завдань культури є формування освіченої цивілізовано розвиненої особистості. У структурі культури як певного цілісного організму розрізняють такі елементи: а субстанціональні ціннісно культурні інститути і системи норм мораль релігія побутова поведінка спілкування індивідів етикет; б функціональні традиції обряди звичаї заборони табу які є неписаними регуляторами процесу функціонування культури. Байта у структурі культури як системи правомірно розрізняти технологічну соціальну та ідеологічну підсистеми...
81687. Культурний Рух, простір і час – атрибутивні властивості матерії 27.75 KB
  Рух його джерело та причини завжди були у полі зору філософів і вченихприродознавців. Так уже Геракліт не лише визнавав усе загальний характер руху але й виявив його суперечливість: все існує і в той же час не існує; все тече й постійно змінюється; все перебуває у постійному процесі виникнення та зникнення. Отже рух матеріальних тіл викликають їх внутрішні і зовнішні взаємодії поза якими існування цих тіл неможливе.