Міністерство освіти і науки України НУ “Львівська політехніка” Кафедра автоматизованих систем управління Лабораторна робота №3,4 з дисципліни: Теорія алгоритмів і математичні основи представлення знань на тему: ” Емуляція на ПЕОМ багаторегiстрових машин ” Мета лабораторної роботи - автоматизувати процес доведення рекурсивності (алгоритмiчностi)певних функцій f : N^K -> N i g : E*^k -> E* шляхом емуляції на ПЕОМ N-БРМ i E*-БРМ , що дасть змогу беспосередньо перевiрити правiльнiсть побудови N-БРМ Мf i E*-БРМ М*g, для бiльш глибокого засвоїння прямих методів доведення рекурсивностi функцiй (предикатiв). I. ЗАГАЛЬНІ ПОЛОЖЕННЯ Розглянемо математичне визначення [1,2] класів функцій та предикатів, що вважаються точним аналогом інтуїтивного поняття алгоритму (взагалі кажучи, часткового). 1. Введемо зчисленні множини символів або послідовностей символів (слів ,ідентифікаторів і т.п.) із довільної конструктивної множини: а) індивідні : x,y,z,x0,y0,z0,x1,y1z1, ... xj ,yj,zj, ...; б) функціональні: f,g,h,f0, g0, h0, f0, g1, h1,...fj, gj, hj,...; в) предикатні: P,Q,R,P0,Q0,R0,P1,Q1,R0, ... Pj,Qj,Rj, ...; г) константи: a,b,c,a0,b0,c0,a1,b1,c1, ... aj,bj,cj, ...; д) мітки: q,i,j,q0,i0,j0,q1,i1,j1, ... qk,ik,jk, ... Кожному функціональному та предикатному символу U однозначно ставиться у відповідність натуральне число n, яке називається арністю даного символа. Цей символ позначається через U (n)  , або U(x1,x2,..,xn)та т.п., і називається n-арним символом. Вважається, що ідеалізований об'єкт – 0 - арний функціональний символ U (n) співпадає з символом константи. Схемою оператора присвоювання називається вираз виду: z(i)  =  f (m) 0(x(1),..,x(m)) . (1) Схемою оператора пересилки  називається вираз виду: z(k)  =  y(j) (2) Схемою присвоювання константи  називається вираз виду: z(k)  =  a, або z(k)  =  f j (0)  (3) Схемою умови  називається вираз виду: P (s) (x(1)..x(s)) (4) Схемою програми  (СП)   S  називатимемо об'єкт виду q0 Ф[0] (i0,j0) q1 Ф[1] (i1,j1) ................ (5) qs Ф[s] (is,js) В (1) Qs  = Qs1  U  Qs2, де Qs1 =  {q0,q1,..qs}, і Qs2  =  {i0,j0,..,is,js} - підмножини множин міток. Як правило, якщо не вказане уточнення, будемо вважати, що qi  ≠ qj, якщо i ≠ j, (qi,qj належать Q1).Мітки із Q1 називаються мітками передачі управління, а мітки із (Qs - Qs1) - кінцевими мітками. Для всіх k  3є [0 ÷ s], Ф[k] - це одна із схем (1) - (4). Сукупність всіх індивідних змінних СП (5) називається пам"яттю схеми  S.  Сукупність константанктних, функціональних, предикатних символів і пам"яті   S  називається сигнатурою, або базисом, схеми  S. Конструкція вигляду qr Ф[r] (ir,jr) із (5) називається схемою команди. Схемою операторного алгоритму (СОА), або схемою операторної процедури, називається об"єкт виду : SA    =  (x1,x2,..,xn; S ;y), (6) де x1,..,xn,y - змінні,  S  - СП вигляду (5). Схемою предикатногоо алгоритму (СПА), або схемою предикатної процедури, називається об"єкт виду : SP  =  (x1,x2,..,xn;  S  ;q[.t.],q[.f.]), (7) де x1,..,xn, - змінні,   S  - СП вигляду (5), а q[.t.],q[.f.]) - кінцеві мітки СП   S. Зауважимо, що пам"яттю алгоритмів (6),(7) називається об"єднання пам"ятті  S  і змінних x1,..,xn,y, і x1,..,xn називаються вхідними змінними, а y - вихідною змінною . Ми визначили СП, СОА і СОП як деякі формальні, синтаксичні конструкціє. Яка ж семантика (сенс) цих конструкцій? Як із них отримати справжні алгоритми (програми) ? Семантика схем задається за допомогою _ інтерпретацій. Інтерпретація  схеми алгоритму  Ω задається парою (D,I), де D - множина довільноє природи, а I - це певне відображення, яке: а) кожному символу змінноє z із пам"яті  Ω ставить у відповідність елемент I(z) із множини D; б) кожному символу константи b із сигнатури  Ω ставить у відповідність елемент I(b) із D; в) кожному m - арному функціональному f (m)  (предикатному P (m) 0) символу співставляє, відповідно, всюдиозначені функцію I(f (m) ) : D m   0->D, або предикат I(P 5(m) 0) -> {.t.,.f.}. 2. Нижче в данному розділі будемо розглядати тількі підклас схем алгоритмів 3 KS – 1 , які містять тільки два функціональні унарні символи {f,g}, один константний символ b і один унарний предикатний символ p. Також обмежимо клас інтерпретацій, поклавши, що в цьому класі KI-1 D завжди співпадає з множиною натуральних чисел N (D = N) а відображення I задовільняє наступним вимогам: 1) I(b) = 0; 2) I(f(x)) =  I(x) + 1;       I(x) - 1, коли x>0 3) I(g(x)) =  I(x) -^ 1 =    0 , коли x=0   (8)    .t., коли I(x) = 0; 4) I(p(x)) = P0(x))=  .f., коли I(x) > 0.   5) I(xi)  є N для всіх вхідних змінних СОА і СПА виду (6),(7),і I(y)  = 0 для всіх інших змінних із пам'яті вищезгаданих схем алгоритмів. Опишемо формально функціонування алгоритму A виду (6) . Нехай M(A) = { z1,z2,..zn,..zm} - пам'ять алгориму A, де zi = 0 xi при 1<  I <  =  n, і zm = y. Через Q(A) позначимо всі мітки A. Станом пам'яті A будемо називати послідовність (a1,..am) натуральних чисел, тобто елемент N  5m  0. Станом (конфігурацією) алгоритму A будемо називати елемент <q;a1,..,am> із D(A)  =  Q  * N m. Стан <q;a1,..,am> називається: а) проміжковим, якщо q - мітка передачи управління; б) кінцевим (заключним), якщо q - кінцева мітка алгоритму A. Визначемо функцію переходів F : D(A) --> D(A) алгоритму A. 1. Коли <q;a1,..,am> - кінцевий стан, то F(<q;a1,..,am>)  =  <q;a1,..,am>. 2. Коли <q;a1,..,am> - проміжковий стан, то значення F залежить від виду команди qk Ф[k] (ik,jk) в (5) . Якщо Ф[k] має вигляд : a) zr  =  zt + 1, то F (<q;a1,..,am>)  =  <q*;b1,..,bm>, де q*   =  ik, br  =  at + 1, а bu  =  au для всіх таких u, що u не рівне r; b) zr  =  zt -^ 1, то F(<q;a1,..,am>)  =  <q*;b1,..,bm>, де q*  =  ik, br   =  at -^ 1, а bu   =  au для всіх таких u, що u не рівне r; c) zr   = 0 , то F (<q;a1,..,am>)  =  <q*;b1,..,bm>, де q*  =  ik, br = 0, а bu  =  au для всіх таких u, що u не рівне r; d) zr  =  zt , то F(<q;a1,..,am>)  =  <q*;b1,..,bm>, де q*  =  ik, br = at , а bu   =  au для всіх таких u, що u не рівне r; e) P0 (zr), то F(<q;a1,..,am>)   =  <q*;b1,..,bm>, де bu  =  au для всіх u (1< =  u < =  m), а q*  =  ir, якщо ar  = 0 , і q*  =  jr, якщо ar > 0. Перейдемо до визначення функціє f[A] : N n --> N, яку обчислює алгоритм A при інтерпретаціє I. По означенню інтерпретаціє маємо, що початковий стан пам'яті є I(M(A))  =  <a1,..,an,0,..,0>. Стан c[0] =  <q0;a1,..,an,0,..,0> називається початковим станом алгоритму A при інтерпретаціє I. Скінченна або нескінченна послідовність T(A)  =  c[0],c[1],..,c[k],c[k+1],... (9) називається траєкторією (шляхом) алгоритму A при інтерпретаціє I ( на вході <a1,..,an>), якщо F(c[k])  =  c[k+1] для всіх k із N. Зрозуміло, що траєкторія (9) для A будується конструктивно по програмі цього алгоритму і початковому значенню вхідних змінних, що задає інтерпретація I. При послідовному обчисленні станів c[k] за допомогою функції переходів F можливі два випадки : 1) в траєкторії (9) знайдеться стан с[t]  =  <q*;b1,..,bm> такий, що c[t] -кінцевий стан,а c[0],c[1],..,c[t-1] -проміжкові стани; 2) в траєкторіє (9) всі стани проміжкові, тобто траєкторія T(A) є нескінченною послідовністю станів A. У першому випадку будемо вважати, що A обчислює значення f[A](<a1,..,an> функціє f[A] в точці <a1,..,an>,i f[A](<a1,..,an>)=bm Нагадаємо, що bm природнім чином можна інтерпретувати як число, що знаходиться в вихідній змінній y в стані c[t] алгоритму A, так як, по припущенню, zm  =  y. Якщо в траєкторіє (9) всі стани проміжкові, тобто траєкторія T(A) є нескінченною послідовністю станів A, будемо вважати, що A циклює в точці <a1,..,an> , тому значення f[A](<a1,..,an> функціє f[A] в точці <a1,..,an> не визначено,тобто f[A](<a1,..,an>)  =  @. Іншими словами,     bm, коли T(A) - скінченна f[A](<a1,..,an>)=   @, коли T(A) - нескінченна   (8) Аналогічно визначається траєкторія і функція переходів для предикатного алгорітму Aq, і вважається що Aq реалізує предикат;   .t., коли T(A) - скінченна,   і q*  2= 0 q[.t.]; P[Aq](<a1,..,an>)  = .f., коли T(A) -скінченна, i   і q*  2= 0 q[.f.];   @, коли T(A) -нескінченна. Замінивши у (5) сімволи f,g,b, і p згідно з інтерпретацією I ми отримаємо програмноподібну структуру,рядки якоє будемо називаті командами. Тому схеми алгоритмів (6) і (7) iз класу KS-1 далі інтерпретуються , як відповідні алгоритми (програми) iз класу програм KП-1 , функціонування яких подібно до функціонування програм, що написані на мовах програмування типу Паскаль, Бейсік і т.п. А саме: 1) символ " =  " у схемах (1) -(3) інтерпретується як оператор присвоєння; 2) елементи із Qs інтерпретуються аналогічно міткам в мовах програмування; 3) виконання команди qr x  =  y + 1 (ir,jr) інтерпретується як послідовність команд qr: x   =  y+1; go to ir; 4) виконання команди qr x  =  y -^1 (ir,jr) інтерпретується як послідовність команд qr: x   =  y-^1; go to ir; 5) виконання команди qr x =  y (ir,jr) інтерпретується як послідовність команд qr: x   =  y; go to ir; 6) виконання команди qr x =  0 (ir,jr) інтерпретується як послідовність команд qr: x   =  0; go to ir; 7) виконання команди qr P0 (x) (ir,jr) інтерпретується як умова qr: IF  P0(x) THEN go to ir ELSE go to jr. Як і у більшості мов програмування, оператор "go to ir" при функціонуванні програми передає управління на команду з міткою ir, а оператор "IF P0 (x) THEN go to ir ELSE go to jr" передає управління на команду з міткою ir, якщо предикат P0 (x) = .t. ( x  =  0),і передає управління на команду з міткою jr, якщо предикат P0 (x)  =  .f.(x > 0). В теорії алгоритмів вважається,що операторні   SA  та предикатні   SP алгоритми із KS-1 виконуються на вхідних даних із N абстрактними автоматамиом - багаторегістровими обчислювальними машинами ( N-БРМ ). Для кожного алгоритму А ця машина Ба складається з блоку управління і m регістрів, де кожний регістр (комірка) Rk може зберігати довілне натуральне число. Блок управління містить програму Па і забезпечує її виконання по вищенаведеній схемі. Система команд N-БРМ складається з множини { 0,x+1, x-^1, P0 (0)}, які можуть виконуватися над вмістом кожного Rk, а також команд присвоювання, безумовного і умовного переходу, пересилки і запису в регістр. Часткові або всюдиозначенні k-арні функцію g : N k  0--> N, Яка задана на натуральних числах , або предикат P : E* --> {T,F}, Будемо називати рекурсивною функцією (предикатом),або R-функцією (R-предикатом),якщо існує програма із класу КП-1 П1g, що обчислює g (P). Приклади доведення по побудові рекурсивності функцій наведені у розділі VI данної інструкції. Як відомо [1,2], згідно до тези Тюрінга-Черча, клас всіх R-функцій вважаються точним аналогом інтуєтивного поняття алгоритму (взагалі кажучи, часткового). 3. Аналгічно до класів KS-1 схем алгоритмів   і Інтерпретацій KI-1 введемо, відповідно, класи KS-2 і KI-2. Нехай E  =  {a1,..,an} - деякий алфавит. Через E* позначимо множину всіх слів в алфавіті E, включаючи однолітерні слова виду 'ai' і пусте слово e  = ''. Введемо на E* деякі стандартні функції і предикати. Якщо w = x1x2..xm і v  =  y1y2..yk - слова iз E*, то а) con(w,v) =  wv  =  x1x2..xmy1y2..yk, con(e,v) = con(v,e) =  v; б) del(w)   =  d(w) =  x2x3..xm, del(e)  =  e; в) для всіх літер ai із E предикат hai(w)  =  T (істино), коли x1  =  ai, і hai(w)  =  F (хибно), коли перша літера x1 у слові w не дорівнює ai (1 < =  i < =  m), причому для всіх i hai(e)  =  F. Якщо а - довільна літера із E*, то через ( a^n ) позначається слово, що склдається із n літер a. Клас схем програм KS-2 містить (n + 1) унарних функціональних символів { fa1,fa2,..,fan,g }, один константний символ b і n унарних предикатних символів { pa1,pa2,..,pan, } В класі інтерпретацій KI-2 схем із KS-1 множина D завжди співпадає з множиною E* всіх слів в алфавіті E , а кожне відображення I із KI-2 задовільняє наступним вимогам: 1) I(b)  =  е; 2) I(fai(x)) =  con(I(x),'ai') =  I(x)ai для всіх літер ai із E; 3) I(g(x)) =  del(I(x)); 4) I(pai(x)) =  hai(I(x)) для всіх літер ai із E; 5) I(xi)  3є E* для всіх вхідних змінних СОА і СПА виду (6),(7), і I(y)  =  e для всіх інших змінних із пам'яті вищезгаданих схем алгоритмів. Замінивши у (5) сімволи fai,g,b і hai згідно з інтерпретацією I із класу KI-2 ми отримаємо програмноподібну структуру,рядки якої будемо називати командами. Тому схеми алгоритмів (6) і (7) iз класу KS-2 далі інтерпретуються , як відповідні алгоритми (програми) iз класу прграм KП-2 , функціонування яких подібно до функціонування програм, що написані на мовах програмування типу Паскаль,коли ці програми працюють на даних типу string. Ясно, що функціонуваня команд програм із класу КП-2 аналгічно , з точністю до інтерпретаціє символів єє схеми, до функціонуваня команд програм із класу КП-1, яке було описано вище. Зауважимо також, що по аналогіє з N-БРМ БN можна ввести E-БРМ БE, що реалізує програму із КП-2, а також NE-БРМ БNE. БNE можна розглядати як "об'єднання" програм ПN i ПE для БN i БE в тому сенсі, що множини регістрів БN i БE не перетинаються, але вони мають загальний блок управління(i спільні мітки), в якій поміщена спільна програма ПNE, в яку входять всі команди, як із ПN так і із ПE. Часткові або всюдиозначенні функцію g : E*вх -->E*вх, яка задана на множині слів довільного алфавіту E , або предикат P : E* --> {T,F}, будемо називати E- рекурсивною функцією (предикатом), або RE-функцією (RE-предикатом),якщо існує програма із класу КП-2 П1g, що обчислює g (P). Як відомо [1],[2], за допомгою кодуючоє функціє доводиться, що , в певному сенсі, клас R-функцій (R-предикатів) і клас RE-функцій (RE-предикатів) є еквівалентні. Приклади доведення по побудові RE-рекурсивності функцій і предікатьв наведені у розділі VI данної інструкції. II. Завдання до лаборатрної роботи; x^3-5*x^2+7*x-3 -2^x NOT(( X < Y) OR ( Y > Z)) R R F1(W) = W W W W W L1= { (a^n)(b^2n)(c^3n)(a^n) | n>=1} ІІІ. Тексти розроблених і відлагоджених програм1. 1 | 1 // Обчислення виразу x^3-5*x^2+7*x-3 -2^x y0=0 x1=1 x2=3 x3=1 x5=2 x6=x0-1 x7=-3 x4=1 CALL (q1) x4=-5 CALL (q1) x4=7 CALL (q1,q4) q1 x3=x2 q2 P0(x3) (q3) x1=x1*x0 x3=x3-1 (q2) q3 x2=x2-1 x4=x4*x1 x1=1 y0=y0+x4 RET q4 y0=y0+x7 q5 P0(x6) (q6) x5=x5*2 x6=x6-1 (q5) q6 x5=x5*-1 x8=y0 x8=x8+x5 y0=x8 (R) 2. 3 | 1 z0=x0 z1=x1 q0 p0(z0) (q1,q2) q1 p0(z1) (q3,F) q2 p0(z1) (q3) q4 z0=z0-1 z1=z1-1 (q0) q3 z0=x1 z1=x2 q5 p0(z0) (q6,q7) q6 p0(z1) (T,T) q7 p0(z1) (F) q8 z0=z0-1 z1=z1-1 (q5) 3. y0=0 x1=x0 x2=x0 x3=0 x5=0 q0 x2=x0 P0(x1) (q3) q1 P0(x2) (q2) x3=x3+1 x2=x2-1 (q1) q2 x1=x1-1 (q0) q3 x1=x0 x2=0 q4 P0(x1) (q5) x2=x2+x3 x1=x1-1 (q4) q5 x4=4 x5=x3 q6 P0(x4) (q7) x3=x3+x5 x4=x4-1 (q6) q7 x4=6 x5=x0 q8 P0(x4) (q9) x5=x5+x0 x4=x4-1 (q8) q9 x6=0 x4=x0 q10 P0(x4) (q11) x6=x6+2 x4=x4-1 (q10) q11 y0=x2 y0=y0-x3 y0=y0+x5 y0=y0-3 y0=y0+1 y0=y0-x6 (R) 4. 3 | 1 z0=x0 z1=x1 q0 p0(z0) (q1,q2) q1 p0(z1) (q3,F) q2 p0(z1) (q3) q4 z0=z0-1 z1=z1-1 (q0) q3 z0=x1 z1=x2 q5 p0(z0) (q6,q7) q6 p0(z1) (T,T) q7 p0(z1) (F) q8 z0=z0-1 z1=z1-1 (q5) Висновок: на даній лабораторній роботі я засвоїв формування та застосування предикатів на прикладі оперативних алгоритмів.