Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Емуляція на ПЕОМ багаторегiстрових машин
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Теорiя алгоритмiв i математичнi основи представленння знань
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
НУ “Львівська політехніка”
Кафедра автоматизованих систем управління
Лабораторна робота №3
з дисципліни:
Теорія алгоритмів і математичні основи представлення знань
на тему:
” Емуляція на ПЕОМ багаторег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. Завдання до лаборатрної роботи;
1. x^3-5*x^2+7*x-3 -2^x
2 . NOT(( X < Y) OR ( Y > Z))
ІІІ. Тексти розроблених і відлагоджених програм 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)
Висновок: на цій лабораторній роботі я засвоїв формування та застосування предикатів на прикладі оперативних алгоритмів
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора