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)

Р

А


 

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

22488. Навигация и интерфейс в средах виртуальной реальности 510 KB
  Работа посвящена исследованию и сравнительному анализу сред навигации интерфейса в средах виртуальной реальности для систем компьютерной визуализации, предназначенных для представления больших и очень больших объемов информации, генерируемых при супервычислениях. В ходе работы будут предложены средства навигации и интерфейса для виртуальной среды.
22489. ЦЕНТРАЛЬНАЯ РАЙОННАЯ ПОЛИКЛИНИКА. ОБЗОР. ПРИНЦИПЫ И ТЕХНОЛОГИЯ ОРГАНИЗАЦИИ РАБОТЫ, СОСТОЯНИЕ ПРОБЛЕМЫ И ПЕРСПЕКТИВЫ РАЗВИТИЯ В РЕСПУБЛИКЕ БЕЛАРУСЬ 133 KB
  Повышение роли профилактики заболеваний и формирование здорового образа жизни. Развитие современных медицинских технологий и расширение их доступности. Улучшение финансового обеспечения государственных гарантий бесплатной медицинской помощи. Сглаживание неравенства в доступности медицинской помощи для различных групп населения. Расширение возможностей граждан влиять на систему здравоохранения.
22490. Разработка методик визуализации для представления работы параллельных программ 582 KB
  Объект исследования: система RiDE, разрабатываемая для программирования в параллельных распределённых средах. Цель работы: разработка методик визуализации для представления работы параллельных программ, написанных для системы RiDE. Разработка программы-визуализатора.
22491. Разработка специализированной среды трехмерной динамической визуализации 479.62 KB
  Трехмерная графика реального времени связана с анимацией и интерактивным взаимодействием с пользователем. Одной из первых сфер применения трехмерной графики реального времени были военные авиатренажеры...
22492. Визуальная среда обучения программированию на языке Haskell 450 KB
  Язык программирования Haskell – это «ленивый» функциональный язык программирования с полиморфизмом типов. Основное понятие в нем – это функции. Но функции есть в любом языке программирования! В языках Pascal, Java...
22493. Разработка средств поддержки процесса проектирования интерфейсов 230 KB
  Однако качество цифровых продуктов с точки зрения взаимодействия с пользователем оставляло желать лучшего. Причина кроется в том, что определением конечной формы и поведения программ занимались программисты, ориентированные на качественное и быстрое выполнение технической стороны.
22494. SELECT в SQL Oracle. Основные возможности 335 KB
  1] Основные фразы запроса: SELECT и FROM [3.1] Фраза SELECT [3. В противном случае вы должны иметь привилегию SELECT по отношению к таблице.
22495. ОБРАБОТКА, ХРАНЕНИЕ И ВИЗУАЛИЗАЦИЯ ДАННЫХ ДЛЯ ЗАДАЧ КАРДИОМОНИТОРИНГА 1.92 MB
  В данной работе изучается задача кардиомониторинга; рассматриваются основные понятия, связанные с построением электрокардиограммы; вводится понятие кардиорегистратора, описываются виды регистрации показаний. Ставится задача о разработке программного обеспечения, которое будет принимать поток данных, разбивать его на отведения