Емуляція на ПЕОМ багаторегiстрових машин. Лабораторна робота з Теорiя алгоритмiв i математичнi основи представленння знань. Робота № 121141

Емуляція на ПЕОМ багаторегiстрових машин

Інформація про навчальний заклад

ВУЗ:

Інші

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

Інформація про роботу

Рік:

2015

Тип роботи:

Лабораторна робота

Предмет:

Теорiя алгоритмiв i математичнi основи представленння знань

Група:

КН

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Національний університет „Львівська політехніка” Лабораторна робота №2 з дисципліни: Теорія алгоритмів і математичні основи представлення знань на тему: ” Емуляція на ПЕОМ багаторег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+x^2-4*x-4 -2^x ( X < Y) OR ( Y = Z) R R R W) =W W W W W { (b^n)(a^2n)(b^n)(c^3n) | n>=1} ІІІ. Тексти розроблених і відлагоджених програм 1. 1 | 1 // y44=x^3+x^2-(4*x+4+2^x) z1=x0 z9=1 q1 p0(z1) (q5) z1=z1-1 z2=z9 q2 p0(z2) (q1) z9=z9+1 z2=z2-1 (q2) //z9=2^x q5 z1=x0 z3=x0 z3=z3-1 z0=z1 q6 z2=z0 p0(z3) (q9) q7 p0(z2) (q8) z2=z2-1 z1=z1+1 (q7) q8 z3=z3-1 (q6) //z1=x0^2 q9 z4=z1 z3=x0 z3=z3-1 z0=z1 q10 z2=z0 p0(z3) (q13) q11 p0(z2) (q12) z2=z2-1 z1=z1+1 (q11) q12 z3=z3-1 (q10) //z1=x0^3 q13 z5=z1 //z5=x0^3, z4=x0^2, z9=3^x0 z1=z5 z2=z4 q14 p0(z2) (q16) z1=z1+1 z2=z2-1 (q14) q16 z5=z1 //z5=x0^3+2*x0^2 z1=x0 z2=z9 q17 p0(z2) (q18) z1=z1+1 z2=z2-1 (q17) q18 z4=z1+1 z4=z4+1 z4=z4+1 z4=z4+1 z2=x0 //z4=2^x0+x0+4 q19 p0(z2) (q21) z2=z2-1 z4=z4+1 z4=z4+1 z4=z4+1 (q19) //z4=2^x0+4*x0+4 q21 z1=z5 z2=z4 q22 p0(z1) (q23,q24) q23 y0=z2 (R) q24 p0(z2) (q25,q26) q25 y0=z1 (R) q26 z1=z1-1 z2=z2-1 (q22) 2. 3 | 1 // (X<Y) OR (Y=z) z1=x0 z2=x1 z3=x2 q1 p0(z1) (q2,q4) q2 p0(z2) (q3,T) q3 p0(z3) (T,F) q4 p0(z2) (T,q5) q5 p0(z3) (T) z1=z1-1 z2=z2-1 z3=z3-1 (q1) 3. ; {1} ;F33(w)=(w)(w^r)(w^r)(w)(w^r) x1=x0 x2=x0 q00 p(x2,@) (q01) x3=x2 x4=w(x4,'1') x2=d(x2) (q00) q01 p(x3,'a') (q02) p(x3,'b') (q03) p(x3,'c') (q04) q02 x6=w(x6,'a') (q05) q03 x6=w(x6,'b') (q05) q04 x6=w(x6,'c') (q05) q05 x2=x1 x4=d(x4) p(x4,@) (q08) x5=x4 q06 p(x4,@) (q07) x3=x2 x2=d(x2) x4=d(x4) (q06) q07 x4=x5 (q01) q08 x1=x6 x2=x0 y1=x0 x0=x6 z1=x6 q09 p(x0,@) (q13) p(x0,'a') (q10) p(x0,'b') (q11) p(x0,'c') (q12) q10 y1=w(y1,'a') x0=d(x0) (q09) q11 y1=w(y1,'b') x0=d(x0) (q09) q12 y1=w(y1,'c') x0=d(x0) (q09) q13 p(x1,@) (q17) p(x1,'a') (q14) p(x1,'b') (q15) p(x1,'c') (q16) q14 y1=w(y1,'a') x1=d(x1) (q13) q15 y1=w(y1,'b') x1=d(x1) (q13) q16 y1=w(y1,'c') x1=d(x1) (q13) q17 p(x2,@) (q21) p(x2,'a') (q18) p(x2,'b') (q19) p(x2,'c') (q20) q18 y1=w(y1,'a') x2=d(x2) (q17) q19 y1=w(y1,'b') x2=d(x2) (q17) q20 y1=w(y1,'c') x2=d(x2) (q17) q21 p(z1,@) (R) p(z1,'a') (q22) p(z1,'b') (q23) p(z1,'c') (q24) q22 y1=w(y1,'a') z1=d(z1) (q21) q23 y1=w(y1,'b') z1=d(z1) (q21) q24 y1=w(y1,'c') z1=d(z1) (q21) 4. ; {1} ;L30(w)={(b^n)(a^2n)(b^n)(c^3n)| n>=1} p(x0,'b') (q00,q28) q00 x0=d(x0) x1=w(x1,'a') p(x0,'b') (q00) ;--------------------------------- a p(x0,'a') (q04,q28) q04 x2=x1 q05 x0=d(x0) x2=d(x2) p(x0,'a') (q06,q28) q06 p(x2,@) (q07,q05) q07 x2=x1 q08 x0=d(x0) x2=d(x2) p(x0,'a') (q09) p(x2,@) (q10,q28) q09 p(x2,@) (q28,q08) ;--------------------------------- b q10 p(x0,'b') (q11,q28) q11 x2=x1 q12 x0=d(x0) x2=d(x2) p(x0,'b') (q13) p(x2,@) (q14,q28) q13 p(x2,@) (q28,q12) ;--------------------------------- c q14 p(x0,'c') (q15,q28) q15 x2=x1 q16 x0=d(x0) x2=d(x2) p(x0,'c') (q17,q28) q17 p(x2,@) (q18,q16) q18 p(x0,'c') (q19,q28) q19 x2=x1 q20 x0=d(x0) x2=d(x2) p(x0,'c') (q21,q28) q21 p(x2,@) (q22,q20) q22 p(x0,'c') (q23,q28) q23 x2=x1 q24 x0=d(x0) x2=d(x2) p(x0,'c') (q25) p(x2,@) (q26,q28) q25 p(x2,@) (q28,q24) ;--------------------------------- q26 p(x0,@) (q27,q28) q27 y0="True" (R) q28 y0="False" (R)

Лабораторна робота Теорiя алгоритмiв i математичнi основи представленння знань

2015

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись