Xreferat.com » Рефераты по математике » Алгоритмічні проблеми

Алгоритмічні проблеми

x1., xn, y, і x1., xn називаються вхідними змінними, а y – вихідною змінною.

Ми визначили СП, СОА і СОП як деякі формальні, синтаксичні конструкції. Яка ж семантика (сенс) цих конструкцій? Як із них отримати справжні алгоритми (програми)?

Семантика схем задається за допомогою інтерпретацій. Інтерпретація схеми алгоритму W задається парою (D, I), де D – множина довільної природи, а I – це певне відображення, яке: а) кожному символу змінної z із пам"яті W ставить у відповідність елемент I(z) із множини D; б) кожному символу константи b із сигнатури W ставить у відповідність елемент I(b) із D; в) кожному m-арному функціональному f(m) (предикатному P(m)) символу співставляє, відповідно, всюдиозначені функцію I (f(m)): Dm ->D, або предикат I (P(m)) ->.t..f.

2. Нижче в данному розділі будемо розглядати тількі підклас схем алгоритмів 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 = xi при 1<= i <= n, і zm = y. Через Q(A) позначимо всі мітки A. Станом пам'яті A будемо називати послідовність (a1..am) натуральних чисел, тобто елемент Nm. Станом (конфігурацією) алгоритму A будемо називати елемент <q; a1., am> із D(A) = Q & Nm.

Стан <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]: Nn –> 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 реалізує предикат;

Алгоритмічні проблеми

і q* = q [.t.]; .t., коли T(A) – скінченна,

P[Aq] (<a1., an>) = * .f., коли T(A) – скінченна, i

і q* = 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: Nk –> 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) є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-рекурсивності функцій і предікатьв наведені далі.

Побудуємо алгоритм, що обчислює функцію


z:= f1 (x, y) = x + y.

x, y! z

q10

q11

q12

q13

q14

q15

q16

q17

q18

q19

x1 = x (q11, q11)

y1 = y (q12, q12)

z1 = 0 (q13, q13)

P0 (x1) (q16, q14)

z1 = z1 + 1 (q15, q15)

x1 = x1 -^ 1 (q13, q13)

P0 (y1) (q19, q17)

z1 = z1 + 1 (q18, q18)

y1 = y1 -^ 1 (q16, q16)

z = z1 (Я, Я)


Побудуємо алгоритм (не оптимальний), що заносить в z значення функції добутку x i y, тобто z:= f1 (x, y) = x * y.


x, y! Z


q20

q21

q22

q23

x2 = x (q21, q21)

y2 = y (q22, q22)

z2 = 0 (q23, q23)

P0 (y2) (q25, q10)

q10

q11

q12

q13

q14

q15

q16

q17

q18

q19

x1 = z2 (q11, q11)

y1 = x (q12, q12)

z1 = 0 (q13, q13)

P0 (x1) (q16, q14)

z1 = z1 + 1 (q15, q15)

x1 = x1 -^ 1 (q13, q13)

P0 (y1) (q19, q17)

z1 = z1 + 1 (q18, q18)

y1 = y1 -^ 1 (q16, q16)

z2 = z1 (q24, q24)

q24

q25

z2 = z1 (q23, q23)

z = z2 (Я, Я)


Нехай алфавіт Е = a, b. Побудуємо алгоритм, що обчислює предикат Pe(w), де Pe(w) = T тоді і тільки тоді, коли w є пусте слово із E*, тобто w = e.


x! q [.t.], q [.f.]

q10 x1 = x (q11, q11)

q11 ha(x1) (q [.f.], q12)

q12 hb(x1) (q [.f.], q [.t.])


Побудуємо алгоритм (не оптимальний), що заносить в z значення функції con (x, y) = xy, тобто z:= g1 (x, y) = con (x, y) = = xy для слів із Е = a, b.


x, y! Z


q20

q21

q22

x2 = x (q21, q21)

y2 = y (q22, q22)

z2 = e (q10, q10)

q10

q11

q12

x1 = y2 (q11, q11)

ha(x1) (q22, q12)

hb(x1) (q22, q28)

q22

q23

q24

ha(y2) (q23, q25)

x2 = con (x2, a) (q24, q24)

y2 = del(y2) (q22, q22)

q25

q26

q27

q28

hb(y2) (q26, q10)

x2 = con (x2, b) (q27, q27)

y2 = del(y2) (q25, q25)

z = x2 (Я, Я)


4. Операторні та предикатні алгоритми -ІІ


(Рекурсивні функції на областях, що відмінні від N)

Оскільки БРМ працює тільки з натуральними числами, наше визначення обчислюваності і можливості розв'язання застосовано тільки до функцій і предикатів від натуральних чисел. Ці поняття легко поширюються на інші види об'єктів (тобто цілі числа, поліноми, матриці і т.д.) за допомогою кодування.

Кодуванням області D об'єктів називається явне й ефективне відображення α: D →N. Ми будемо говорити, що об'єкт α ? D кодується натуральним числом α (d). Припустимо, що f є функцією з D в D; тоді f природно кодується функцією f* з N в N, що відображає код кожного об'єкта d ? Dom(f) у код об'єкта f (d). У явному виді це можна записати як


f*=α · f ·a-1


Тепер можна поширити визначення Мнр-обчислюваності на область D, рахуючи функцію f обчислюваною, якщо f*–обчислювана функція натуральних чисел.

Приклад. Розглянемо область Z. Явне кодування можна задати функцією α, де


Алгоритмічні проблеми2n, якщо n і 0,

α-(n) =

-2n-1, якщо n < 0.


Тоді α-1 задається так:


Алгоритмічні проблеми(1/2) m, якщо m парне,

α-1 (m) =

(-1/2) (m+1), якщо m непарне.


Тепер розглянемо функцію х-1 на Z; позначаючи цю функ-ю через f, одержуємо f*:N →N, що задається:


Алгоритмічні проблеми1, якщо x:==0 (тобто х=α(0)),

f*(x)= х-2, якщо х> 0 і х парне (тобто х=а(п), п>0),

х +2, якщо х непарне (тобто х=α(n), п < 0).


Написання програми, що обчислює f*, є рутинною вправою; отже, х-1 є обчислювана функція на Z.

Приведене вище визначення очевидним образом розширюється на n-місцеві обчислювальні функції на області D і розв'язні предикати на D.


5. Алгоритмічні проблеми для L


Нижче дається огляд нерозв'язних проблем, що виникають у самій теорії обчислювальності, і обговорюються деякі методи доказу нерозв'язності. Нагадаємо, що предикат М(х) називається розв'язним, якщо його характеристична функція, що задається формулою


Алгоритмічні проблеми1, якщо M(x) правдиве,

Cm (x) =

0, якщо M(x) неправдиве


обчислювана. Це рівносильно твердженню про те, що предикат М (х) рекурсивний Предикат М (х) називається нерозв'язним, якщо він не є розв'язним. У літературі використовуються наступні терміни, еквівалентні твердженню про те, що предикат М (х) розв'язний:

М (х) рекурсивний,

М (х) має рекурсивну проблему дозволу,

М (х) рекурсивно розв'язний,

М (х) обчислювальний.

Алгоритм, що обчислює см, називається обчислювальною процедурою, для M(x).

1. Нерозв'язні проблеми в теорії обчислюваності

У більшості випадків докази нерозв'язності ґрунтуються на діагональному методі, як, наприклад, у наступному важливому прикладі.

1.1. Теорема. Проблема «x ОWx» (чи, що еквівалентно, «функція fx(х) визначена», чи «Рx(х)Ї», чи «функціяyu(х, х) визначена») нерозв'язна.

Доведення. Характеристична функція цієї проблеми задається наступною формулою:


Алгоритмічні проблеми1, якщо xО Wx

f(x)=0, якщо xП Wx


Припустимо, що функція f обчислювана, і приведемо це припущення до протиріччя. Саме за допомогою діагонального методу ми побудуємо обчислювану функцію g, таку, що Dom(g)№Wx(= Dom(фx)), при всіх х, чого, мабуть, бути не може.

Як завжди при використанні діагонального методу, ми будемо прагнути до того, щоб множина Dom(g) відрізнялося від Wx у njxці х. Тому будемо домагатися того, щоб


x О Dom (g) Ыx ПWx


Визначимо тепер функцію g у такий спосіб:


g(x)= 0, якщо xП Wx (тобто якщо f(x)=0),


не визначена, якщо xО Wx (тобто якщо f(x)= 1).

Оскільки функція f обчислювана, то (по тезі Черча) обчислювана і функція g, що і дає необхідне протиріччя. (Більш докладно, оскільки функція g обчислювана, візьмемо таке т, що g=fm, тоді т О Wm Ы т О Dom (g)Ыт П Wm, чого не може бути.)

Отже, ми робимо висновок, що функція f не є обчислюваною, і, отже, проблема «x ОWx» нерозв'язна. я

Зауважимо, що ця теорема зовсім не затверджує, що ми не можемо для будь-якого конкретного числа а сказати, чи буде визначене значення fa (a). Для деяких чисел зробити це дуже просто. Наприклад, якщо ми написали програму Р, що обчислює тотальну функцію, і Р=Рa, то ми відразу знаємо, що значення fa (a) визначено. Теорема говорить лише, що не існує єдиного загального методу рішення питання про те, чи буде fx(х) визначено; іншими словами, не існує методу, що працює при всіх х.

Простий наслідок цього результату полягає в наступному.

1.2. Наслідок. Існує обчислювана функція h, для якої обидві проблеми «x О Dom(h)» і «х О Ran(h)» нерозв'язні.

Доведення. Покладемо

Алгоритмічні проблемиx, якщо xО Wx

h(x)=

не визначена, якщо xП Wx


Тоді в силу тези Черча і обчислюваності універсальної функції yu функція h обчислювана (більш формально ми маємо h(x)@ x1 (yu(х, х)), а ця функція обчислювана як результат підстановки). Ясно, що x О Dom(h)Ы xО Wx Ыx О Ran (h), так що обидві проблеми «x О Dom(h)» і «х О Ran(h)» нерозв'язні.

З теореми 1.1 виводиться ще одна важлива нерозв'язна проблема:

1.3. Теорема (проблема зупинки). Проблема «функція фx(у) визначена» (чи в еквівалентній формі «Рx(y)Ї, чи «y О Wx» нерозв'язна.

Доведення. Міркуючи неформально, ми відразу бачимо, що якби проблема «функція фx(у) визначена» була б розв'язна, то була б розв'язна і більш проста проблема «функція фx(х) визначена», що суперечить теоремі 1.1.

Щоб провести всі ці міркування більш докладно, розглянемо характеристичну функцію проблеми^ «функція фх(у) визначена», що має наступний вид:


Алгоритмічні проблеми1, якщо фх(у) визначена

g (x, y)=

0, якщо фх(у) не визначена


Якби функція g була обчислювана, то обчислюваною була б і функція f(x)=g (x, х), але f є характеристична функція проблеми «х О Wx» і, отже, не обчислювана в силу теореми 1.1. Отже, функція g не обчислювана, і тим самим проблема «фx(y) визначена» нерозв'язна. я

Теорему 1.3 часто інтерпретують як твердження про нерозв'язність проблеми зупинки (для МНР-программ), у якому говориться про те, що не існує ніякого ефективного загального методу установити, чи зупиниться деяка конкретна програма, запущена після введення в неї деякого конкретного набору початкових даних. Зміст цього твердження для теоретичного програмування очевидний: не існує зовсім загального методу перевірки програм на наявність у них нескінченних циклів.

Розглянута в теоремі 1.1 нерозв'язна проблема «х О Wx» важлива з кількох причин. Одна з них полягає в тому, що нерозв'язність багатьох проблем можна довести, показавши, що вони принаймні не простіші, ніж ця. Саме таким шляхом ми довели, що проблема зупинки (теорема 1.3) нерозв'язна: цей процес називається зведенням однієї проблеми до іншої.

Узагалі розглянемо деяку проблему М (х). Часто вдається показати, що рішення загальної проблеми М (х) привело б до рішення загальної проблеми «х О Wx», Тоді говорять, що проблема «х О Wx» зводиться до проблеми М (х). Іншими словами, якщо мається дозволяюча процедура для проблеми М (x), то ми можемо дати і дозволяючу процедуру для проблеми «х О Wx». Таким чином, з можливості розв'язання М(х) випливає можливість розв'язання «х О Wx», звідки ми негайно робимо висновок, що М (х) нерозв'язна.

Для зведення проблеми «х О Wx» до інших проблем часто використовується s-m-n-теорема, як показує, наприклад, доведення наступного результату.

1.4. Теорема. Проблема «фx=0» нерозв'язна.

Доведення. Розглянемо функцію f, визначену формулою


Алгоритмічні проблеми

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: