Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Інформаційні технології
Група:
КН- 411
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
Кафедра автоматизованих систем управління
Лабораторна робота № 3
з дисципліни
“Математичні методи представлення знань”
Мета: автоматизувати процес доведення рекурсивності (алгоритм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в).
ЗАГАЛЬНІ ПОЛОЖЕННЯ
Розглянемо математичне визначення [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 данної інструкції.
Тексти програм
V2.opr
1 | 1
y2 = 0
y3 = x0 + 1
q7 y1 = x0
y3 = y3 - 1
p0(y3) (q2)
q1 P0(y1) (q7)
y2 = y2 + 1
y1 = y1 - 1 (q1)
q2 x1 = y2
y2 = 0
y3 = x1 + 1
q8 y1 = x0
y3 = y3 - 1
p0(y3) (q4)
q3 P0(y1) (q8)
y2 = y2 + 1
y1 = y1 - 1 (q3)
q4 x2 = y2
x3 = x0
y1 = x0
q9 P0(y1) (q10)
x3 = x3 + 1
y1 = y1 - 1 (q9)
q10 y1 = x1
q11 P0(y1) (q12)
x1 = x1 + 1
x1 = x1 + 1
y1 = y1 - 1 (q11)
q12 y2 = 1
y1 = x0 + 1
q5 y1 = y1 - 1
P0(y1) (q6)
y3 = y2
q13 y2 = y2 + 1
y3 = y3 - 1
p0(y3) (q5, q13)
q6 x4 = y2
y0 = x2
q14 P0(x1) (q15)
y0 = y0 - 1
x1 = x1 - 1 (q14)
q15 P0(x3) (q16)
y0 = y0 + 1
x3 = x3 - 1 (q15)
q16 P0(x4) (R)
y0 = y0 + 1
x4 = x4 - 1 (q16)
V65.opr
3 | 0
z0 = x0 \ x1
z1 = x1 \ x2
z2 = 0
q1 P0(z0) (q2, q3)
q2 z2 = 1
q3 P0(z1) (q4, q5)
q4 z2 = z2 + 1
q5 z2 = z2 \ 1
P0(z2) (F, T)
V15.txt
; {1}
;F(w)=(w^r)(w)(w)(w)(w^r)
y0 = ""
x1 = x0
q15 x3 = ""
p(x1, @) (q4)
q0 x2 = x1
x1 = d(x1)
p(x1, @) (q10)
p(x2, 'a') (q1)
p(x2, 'b') (q2)
p(x2, 'c') (q3)
q1 x3 = w(x3, 'a') (q0)
q2 x3 = w(x3, 'b') (q0)
q3 x3 = w(x3, 'c') (q0)
q10 p(x2, 'a') (q11)
p(x2, 'b') (q12)
p(x2, 'c') (q13)
q11 y0 = w(y0, 'a') (q14)
q12 y0 = w(y0, 'b') (q14)
q13 y0 = w(y0, 'c') (q14)
q14 x1 = x3 (q15)
q4 x3 = y0
x1 = x0
q5 p(x1, @) (q16)
p(x1, 'a') (q6)
p(x1, 'b') (q7)
p(x1, 'c') (q8)
q6 y0 = w(y0, 'a')
x1 = d(x1) (q5)
q7 y0 = w(y0, 'b')
x1 = d(x1) (q5)
q8 y0 = w(y0, 'c')
x1 = d(x1) (q5)
q16 x1 = x0
q17 p(x1, @) (q22)
p(x1, 'a') (q18)
p(x1, 'b') (q19)
p(x1, 'c') (q20)
q18 y0 = w(y0, 'a')
x1 = d(x1) (q17)
q19 y0 = w(y0, 'b')
x1 = d(x1) (q17)
q20 y0 = w(y0, 'c')
x1 = d(x1) (q17)
q22 x1 = x0
q23 p(x1, @) (q27)
p(x1, 'a') (q24)
p(x1, 'b') (q25)
p(x1, 'c') (q26)
q24 y0 = w(y0, 'a')
x1 = d(x1) (q23)
q25 y0 = w(y0, 'b')
x1 = d(x1) (q23)
q26 y0 = w(y0, 'c')
x1 = d(x1) (q23)
q27 x1 = x3
q28 p(x1, @) (R)
p(x1, 'a') (q29)
p(x1, 'b') (q9)
p(x1, 'c') (q21)
q29 y0 = w(y0, 'a')
x1 = d(x1) (q28)
q9 y0 = w(y0, 'b')
x1 = d(x1) (q28)
q21 y0 = w(y0, 'c')
x1 = d(x1) (q28)
V27.opr
;{1}
;L27={ (c^n)(a^3n)(b^2n)(c^2n) | n>=1}
x1 = ""
x2 = x0
p(x0,'c') (q1, F)
q1 x1 = w(x1, 'c')
x2 = d(x2)
p(x2, 'c') (q1, q2)
q2 x3 = x1
q0 p(x2, 'a') (q3, F)
q3 x2 = d(x2)
p(x2, 'a') (q4, F)
q4 x2 = d(x2)
p(x2, 'a') (q5, F)
q5 x2 = d(x2)
x3 = d(x3)
p(x3, 'c') (q0, q6)
q6 x3 = x1
q7 p(x2, 'b') (q8, F)
q8 x2 = d(x2)
p(x2, 'b') (q9, F)
q9 x2 = d(x2)
x3 = d(x3)
p(x3, 'c') (q7, q10)
q10 x3 = x1
q11 p(x2, 'c') (q12, F)
q12 x2 = d(x2)
p(x2, 'c') (q13, F)
q13 x2 = d(x2)
x3 = d(x3)
p(x3, 'c') (q11, q14)
q14 p(x2, @) (T, F)
Висновок: в даній роботі я розробив програмну реалізацію шифрування тексту із створенням ключа та шифрованого тексту, та розшифрування зашифрованого тексту за відомим ключем.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора