Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Емуляція на ПЕОМ багаторегiстрових машин
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2005
Тип роботи:
Лабораторна робота
Предмет:
Теор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)
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора