Архів якісних рефератів

Знайти реферат за назвою:         Розширений пошук

Меню сайту

Головна сторінка » Математика

Eфективні операції на функціях та множинах (реферат)

Множину всіх n-арних функцій на N, тобто функцiй iз Nп в N, позначимо Fп. Об'єднання множин Fп для всіх п³1 позначимо F. Множину всіх тотальних функцій із Fп та множину всіх тотальних функцій із F відповідно позначимо Tп та T . Cкінченні множини в цьому розділі позначаємо F, скінченні функції позначаємо q.

Довільну функцію вигляду F: (2N)m→2N назвемо m-арним множинним оператором (скорочено МО).

Довільну функцію вигляду Ψ: (F)m→F назвемо m-арним функціональним оператором (скорочено ФО).

Функціональні оператори називають також операціями на функціях, або композиціями.

Приклад. Операції суперпозиції Sn+1 : (F)m→F, примітивної рекурсії R : F´F →F та мінімізації M : F´F→F є прикладами ФО.

МО F: (2N)m→2N називається монотонним, якщо із умови А1ÍВ1 , А2 ÍВ2 , ..., Ат ÍВт випливає F(А1 , ..., Ап) ÍF(В1 , ..., Вп).

ФО Y: (F)m→F називається монотонним, якщо із умови f1 Íg1 , f2 Íg2 , ..., fт Ígт випливає F(f1 , ..., fп) ÍY(g1 , ..., gп).

МО F: (2N)m→2N називається неперервним, якщо для всіх хÎN, AÎ(2N)m маємо хÎF(A) Û $ FÍA : хÎF(F).

ФО Y: Fп→F називається неперервним, якщо для всіх хÎNп, yÎN та fÎFп маємо (х, у)ÎY(f) Û $q Íf : (х, у)ÎY(q).

Легко довести, що кожний неперервний оператор є монотонним.

11.1. ОПЕРАТОРИ ПЕРЕЛІКУ. ЧАСТКОВО РЕКУРСИВНІ ТА РЕКУРСИВНІ ОПЕРАТОРИ

Ефективність множинного оператора F: 2N→2N означає можли-вість ефективно задати множину F(A), якщо ефективно задається множина А. Ефективні множинні оператори називаються [10] операторами переліку (скорочено ОП).

Для кожного zÎN оператор переліку Fz : 2N→2N задається співвідношенням Fz(A) ={x | $u(Fu ÍА & C(x, uDz)}.

Інакше кажучи, xÎFz(A) Û $u(Fu ÍА & C(x, uDz).

Теорема 11.1.1. Кожний оператор переліку є неперервним та монотонним.

Множина АÍN однозначна, якщо С -1(А)={(l(x), r(x))} є функціо-нальним відношенням. Зрозуміло, що A однозначнa Û (Сm+1)-1(A) є функціональним відношенням для кожного m³1. Отже, множина A однозначнa Û "m³1 $fÎFm : A=Сm+1(f). Тому для множини всіх однозначних множин можна ввести наступне позначення:

CF ={С(f) | fÎF1}={Сm+1(f) | fÎFm}.

Кожний функціональний оператор Y: Fm→Fn задає множинний оператор F: CFCF та навпаки:

Y : Fm → Fn

Сm+1¯­(Сm+1)-1 Сn+1¯­(Сn+1)-1

F : CF CF

Звідси Y(f)=(Сn+1)-1(F(Сm+1(f))) та F(A)=Сn+1(Y((Сm+1)-1(A))).

ФО Y: Fm→Fn називається частково рекурсивним оператором (ЧРО), якщо існує zÎN таке, що для всіх fÎFm маємо:

Y(f)=

В цьому випадку кажуть, що ОП Fz визначає ЧРО Y.

Тотальний ЧРО назвемо рекурсивним оператором (РО).

Інакше кажучи, ФО Y: Fm→Fn - рекурсивний оператор, якщо

існує zÎN таке: для всіх fÎFm Y(f)=(Сn+1)-1(Fz(Сm+1(f))) (df1)

Дамо безпосереднє визначення РО, не використовуючи поняття оператора переліку. Вживатимемо скорочення для х1 , ..., хп.

ФО Y: Fm→Fn - рекурсивний оператор, якщо

існує zÎN таке: для всіх fÎFm, ( , уNп+1 маємо

( , у)ÎY(f) Û $и(q Íf & у= (и, )) (df2)

Зрозуміло, що таке визначення РО еквівалентне наступному:

існує ЧРФ j така: для всіх fÎFm, ( , уNп+1 маємо

( , у)ÎY(f) Û $и(q Íf & у=j(и, )) (df3)

Теорема 11.1.2. Визначення df1, df2 та df3 еквівалентні.

Надалі для РО будемо, як правило, використовувати df3.

Теорема 11.1.3. Кожний РО є неперервним та монотонним.

Приклад 1. Нехай оператор Y: F1→F1 задається співвідношеням

Тоді Y немонотонний, отже, не РО.

Візьмемо скінченну q¹fÆ та нескінченну fÉq. Тоді Y(q)=q¹fÆ та Y(f)=fÆ . Маємо fÉq та Y(f)ÌY(q). Отже, Y не є монотонним.

Приклад 2. Нехай оператор Y: F1→F1 задається співвідношеням

Тоді Y не неперервний і не РО.

Візьмемо функцію f із нескінченною Еf (наприклад, f - тотожна функція). Тоді Y(f)=f¹fÆ та Y(q)=fÆ для кожної скінченної qÌf. Тому якщо (х, у)ÎY(f), то не існує скінченної функції qÌf такої, що (х, у)ÎY(q), бо Y(q)=fÆ =Æ. Отже, Y не є неперервним.

Для доведення рекурсивності операторів корисним є наступний критерій рекурсивності:

Теорема 11.1.4. Оператор Y: Fт→Fп є рекурсивним оператором Û Y неперервний та функція

є ЧРФ.

Розглянемо приклади використання теореми 11.1.4.

Приклад 3. Оператор Y: Fт→Fп задається умовою Y(f)=g для всіх fÎFт, де g - фіксована ЧРФ. Тоді Y є РО.

Оператор Y неперервний: умова ( , у)ÎY(f) Û ( , у)ÎY(q) виконується для довільної скінченної qÍf , адже Y(f)=Y(q)=g. Функція g(и, )= є ЧРФ за ТЧ.

Приклад 4. Задамо оператор Y: F1→F1 таким співвідношенням: Y(f)(x)= f(f(x+2))+5x для всіх fÎF1. Тоді Y є РО.

Оператор Y неперервний: (х, у)ÎY(f) Û (х, у)ÎY(q) виконується для кожної скінченної qÍf такої, що x+2ÎDq та f(x+2)ÎDq. Тепер

g(и, х) =

є ЧРФ за ТЧ.

Приклад 5. Оператор мінімізації М: Fп+1→Fп задається умовою М(f)( ) = mу(f( , у)=0) для всіх fÎFп+1. Тоді М є РО.

Оператор М неперервний: у=mу(f( , у)=0) Û у=mу(q( , у)=0) виконується для кожної qÍf такої, що ( , 0), ( , 1), ..., ( , уDq ; тому y=М(f)( ) Û y=М(q)( ) для кожної такої qÍf. Тепер функція

g(и, ) = є ЧРФ за ТЧ.

Приклад 6. Нехай ФО Y0 : F1→F1 задається співвідношенням Y0({(0,0)})={(0,0)} та Y0({(1,0)})={(0,1)}; для інших fÎF1 значення Y0(f) невизначене. Тоді Y0 розширюється до ЧРО та не розширюється до жодного РО.

Позаяк {C(0,0)}={0}=F1 та {C(1,0)}={2}=F4 , беремо z таке, що Dz ={C(0,20), C(1,22)}. Нехай ОП Fz задається таким Dz , тобто xÎFz(A) Û $u(Fu ÍА & C(x, uDz). Зрозуміло, що для кожних A Î2N Fz(A) Í l(Dz)={0,1}. Маємо:

- якщо 0ÎА та 2ÎА, то Fz(A)={0,1};

- якщо 0ÎА та 2ÏА, то Fz(A)={0};

- якщо 0ÏА та 2ÎА, то Fz(A)={1};

- якщо 0ÏА та 2ÏА, то Fz(A)=Æ.

Для ЧРО Y, який визначається таким ОП Fz , маємо:

1) Якщо (0,0)Ïf та (1,0)Ïf, то 0ÏC(f) та 2ÏC(f), звідки Fz(C(f))=Æ. Отже, для таких f Y(f)=fÆ .

2) Якщо (0,0)Îf та (1,0)Ïf, то 0ÎC(f) та 2ÏC(f), звідки Fz(C(f))={0}=C(0,0). Отже, для таких f Y(f)={(0,0)};

3) Якщо (0,0)Ïf та (1,0)Îf, то 0ÏC(f) та 2ÎC(f), звідки Fz(C(f))={1}=C(0,1). Отже, для таких f Y(f)={(0,1)};

4) Якщо (0,0)Îf та (1,0)Îf, то 0ÎC(f) та 2ÎC(f), звідки Fz(C(f))={0,1} - неоднозначна множина. Отже, для таких f Y(f) невизначене, тому Y не РО.

Із 2) та 3) випливає, що ЧРО Y є розширенням оператора Y0 .

Нехай q={(0,0), (1,0)}. Для довільного ЧРО F, що є розширенням Y0 , маємо: якщо F(q)¯, то F(q)ÊF({(0,0)})=Y0({(0,0)})={(0,0)} та F(q)ÊF({(1,0)})=Y0({(1,0)})={(0,1)}. Але тоді F(q) як множина не є функція, тобто F(q)­. Отже, кожний такий ЧРО F нетотальний, тобто не РО. Таким чином, Y0 не можна розширити до РО.

Приклад 7. ЧРО Y із прикладу 6 немонотонний.

Для q={(0,0), (1,0)} маємо F(q)­, але Y({(0,0)})={(0,0)}. Тому з умови {(0,0)}Íq не випливає Y({(0,0)}ÍY(q).

ЧРО Y називають загальнорекурсивним оператором (ЗРО), якщо Tт ÍDY та Y(Tт)ÍFn.

Теорема 11.1.5. Нехай ЧРО Y: Fт→Fп такий, що TтÍDY . Тоді Y є РО.

Наслідок. Для класів ЗРО, РО та ЧРО маємо строгі включення ЗРОÌРОÌЧРО.

За теоремою 11.1.5 ЗРОÍРО. Але РО прикладу 3 не є, очевидно, ЗРО, якщо ЧРФ g взяти нетотальною, тобто не РФ. За визначенням РОÍЧРО. Але ЧРО Y із прикладу 6 немонотонний, тому не РО.

ВПРАВИ

1. Нехай Fz - оператор переліку. Дослідити співвідношення:

1) між множинами Fz(АÈВ) та Fz(А)ÈFz(В);

2) між множинами Fz(АÇВ) та Fz(А)ÇFz(В).

2. Нехай F та Y - монотонні оператори (тут F та Y - 1-арні МО або ФО вигляду F: Fт→Fр та Y: Fр→Fп). Доведіть, що оператор теж монотонний

3. Нехай F та Y - неперервні оператори (тут F та Y - 1-арні МО або ФО вигляду F: Fт→Fр та Y: Fр→Fп). Доведіть, що оператор теж неперервний

4. Нехай F та Y - рекурсивні оператори вигляду F : Fт→Fр та Y : Fр→Fп. Доведіть, що оператор теж рекурсивний

5. Доведіть рекурсивність оператора F : F1→F1, заданого умовою:

1) F(f)(x) = ;. 2) F(f)(x) = .

6. Доведіть рекурсивність оператора F : F1→F1, заданого так:

1) F(f)(x) = f(f(f(x+1)))+x; 2) F(f)(x) = f(f(x2+3))+2x;

3) F(f)(x) = (f(f(3x)))2+3x; 4) F(f)(x) = f(f(7x+5)))+f(f(f(x))).

7. Доведіть рекурсивність оператора F : F2→F1, заданого умовою: 1) F(f)(x) = f(x, x);

2) F(f)(x) = f(f(2x, x), f(x, 3x));

3) F(f)(x) = f(f(x, x)+1, f(3x, x)+2)+3.

8. Чи буде рекурсивним оператор F : F1→F1, що задається наступною умовою:

1) ?

2) ?

3) ?

4) ?

5) ?

6) ?

9. Сформулюйте визначення п-арного неперервного функціональ-ного оператора вигляду Y: F ´...´ F ´...´F →Fп.

10. Сформулюйте визначення п-арного оператора переліку, п-арного ЧРО, п-арного РО та п-арного ЗРО.

11. Сформулюйте та доведіть для випадку п-арних операторів відпо-відні узагальнення теорем 11.1.1 – 11.1.5.

12. Доведіть рекурсивність операторів примітивної рекурсії R та суперпозиції Sn+1.

11.2. ТЕОРЕМА МАЙХІЛЛА-ШЕПЕРДСОНА. ТЕОРЕМИ ПРО НЕРУХОМУ ТОЧКУ

Кожний ОП при обмеженні на РПМ задає на їх індексах ефективну операцію, тобто рекурсивну функцію.

Теорема 11.2.1. Існує РФ s така, що для всіх z, yÎN маємо Fz(Dy)=Ds(x,y)..

Наслідок. Нехай А є РПМ. Тоді Fz(A) є РПМ.

Кожний РО при обмеженні на ЧРФ задає на їх індексах ефективну операцію, тобто рекурсивну функцію.

Теорема 11.2.2 (Майхілл, Шепердсон). Для кожного РО Y: Fт→Fп існує РФ h така: для кожного kÎN маємо Y( )= .

Наслідок. Нехай Y є РО, f є ЧРФ. Тоді Y(f) є ЧРФ.

Функція h m-n-екстенсійна, якщо з умови випливає . 1-1-екстенсійні функції назвемо просто екстенсійними.

Приклад 1. РФ h із теореми 11.2.2 m-n екстенсійна. Справді, з умови випливає .

Теорема 11.2.3 (Майхілл, Шепердсон). Для кожної m-n-екстенсій-ної РФ h існує єдиний РО Y: Fт→Fп такий, що Y( )= ). для кожного kÎN.

Множина А називається найменшою нерухомою точкою (ННТ) оператора F: 2N→2N , якщо:

1) F(A)=A, тобто A - нерухома точка (НТ) оператора F ;

2) якщо F(B)=B, то AÍB; тобто A - найменша НТ оператора F.

Теорема 11.2.4 (С.Кліні). 1) Кожний неперервний множинний оператор F: 2N→2N має найменшу нерухому точку;

2) якщо F є оператором переліку, то його ННТ є РПМ.

Множину A, що є ННТ оператора F, будуємо методом послідовних наближень. Задамо послідовність множин {An}nÎN так: A0=Æ; An+1=F(An) для n³0. Покладемо .

Враховуючи неперервність, доводимо, що А є ННТ оператора F. Якщо F є оператором переліку, то доводиться, що A є РПМ.

Функція f називається найменшою нерухомою точкою оператора Y: Fп→Fп, якщо:

1) Y(f)=f, тобто f - нерухома точка оператора Y ;

2) якщо Y(g)=g, то f Íg; тобто f - найменша НТ оператора Y.

Приклад 2. Нехай ННТ f оператора Y є тотальною функцією. Тоді f - єдина нерухома точка оператора Y.

Приклад 3. Найменша нерухома точка тотожного оператора - це fÆ. Тотожний оператор є ЗРО. Отже, для ЗРО найменша нерухома точка може бути нетотальною функцією.

Теорема 11.2.5 (С.Кліні). 1) Кожний неперервний ФО Y: Fп→Fп має найменшу нерухому точку;

2) якщо Y є РО, то його ННТ є ЧРФ.

Функцію f, що є ННТ оператора Y, будуємо методом послідовних наближень. Задамо послідовність функцій {fn}nÎN так: f0=fÆ; fn+1=Y(fn) для n³0. Покладемо .

Враховуючи неперервність, доводимо, що f є ННТ оператора Y. Якщо Y є рекурсивним оператором, то доводиться, що f є ЧРФ.

Нехай РО Y: F1→F1 визначений ОП Fz : для всіх fÎF1 маємо Y(f)=С-1(Fz (С(f))). Нехай А є НТ оператора Fz : А=Fz (А). Тоді функція f =С-1(А) є нерухомою точкою РО Y: Y(f)=С-1(Fz (С(f)))= =С-1(Fz (А))=С-1(А)=f . З іншого боку, нехай f - НТ РО Y: Y(f)=f. Тоді множина А=С(f) - НТ оператора Fz : Fz (С(f))=С(Y(f))=С(f).

Приклад 4. Для ЧРО не РО Y найменшої нерухомої точки може не існувати. Це буває тоді, коли множина А, що є ННТ відповідного ОП Fz , неоднозначна. Тоді кожна ВÊА неоднозначна, тому такий Y взагалі не має нерухомих точок.

Приклад 5. Знайдемо ННТ оператора Y : F1→F1, заданого умовою

Оператор Y неперервний: (х, у)ÎY(f) Û (х, у)ÎY(q) виконується при х=0 для довільної скінченної qÍf, при х>0 ця умова викону-ється для кожної скінченної qÍf такої, що x+1ÎDq . Отже, Y має ННТ fH , яку знайдемо методом послідовних наближень.

Маємо f0=fÆ. Тепер знаходимо f1 та f2:

f1(х)=Y(f0)(х) = =

f2(х)=Y(f1)(х) = =

Отже, f2 = f1. Маємо стабілізацію, тому fп = f1 для всіх n>0. Звідси ННТ fH = f1 . Зауважимо, що інші нерухомі точки нашого оператора мають вигляд fТ(х) =

Приклад 6. Знайдемо ННТ оператора Y : F2→F2, заданого умовою

.

Оператор Y неперервний: умова (х, у, z)ÎY(f) Û (х, у, z)ÎY(q) виконується при х=0 для довільної скінченної qÍf, при х>0 ця умова виконується для кожної скінченної qÍf такої, що (х, уDq та (х-1, f(х, у))ÎDq . Отже, Y має ННТ fH , яку знайдемо методом послідовних наближень. Маємо f0=fÆ. Тепер знаходимо f1 та f2:

f1(х, у) =Y(f0)(х, у)) = = =

f2(х, у) =Y(f1)(х, у)) = = = бо f1(х, у) невизначене при x>0.

Отже, f2 = f1 . Маємо стабілізацію, тому fп = f1 для всіх n>0. Звідси ННТ fH = f1 .

Приклад 7. Знайдемо ННТ оператора Y : F1→F1, заданого умовою

.

Оператор Y неперервний: (х, у)ÎY(f) Û (х, у)ÎY(q) виконується при х=0 для довільної скінченної qÍf, при х>0 умова виконується для кожної скінченної qÍf такої, що x-1ÎDq . Отже, Y має ННТ.

Метод послідовних наближень тут вимагає нескінченної кількості кроків, бо fп+1 É fп для всіх n³0. Тому використаємо обхідні шляхи. Нехай fH - ННТ нашого оператора. Тоді для кожного хÎN маємо fН(х)=Y(fН)(х) = 2х-1+ fН(х-1) = 2х-1+Y(fН)(х-1) = 2х-1+2х-3+fН(х-2) = … = 2х-1+2х-3+ … +1+fН(0) = 2х-1+2х-3+ … +1+0 = х2. Отже, для всіх хÎN fН(х) = х2. Тому така fH - єдина нерухома точка нашого Y.

Приклад 8. Знайдемо ННТ оператора Y : F1→F1, заданого умовою

.

Оператор Y неперервний: (х, у)ÎY(f) Û (х, у)ÎY(q) виконується при х>55 для довільної скінченної qÍf, при х£55 умова викону-ється для кожної скінченної qÍf такої, що x+7ÎDq та f(x+7)ÎDq . Отже, Y має ННТ, нехай це функція fH . Для кожного х>55 маємо fН(x)=Y(fН)(х) = х-6. Тепер fН(55)=Y(fН)(55) = fН(fН(62)) = fН(56) = 50. Тоді fН(54)=Y(fН)(54) = fН(fН(61)) = fН(55) = 50. Продовжуючи далі, аналогічно дістаємо fН(53) = fН(54) = 50, …, fН(0) = fН(1) = 50. Отже, fH - єдина нерухома точка оператора Y, причому така fH має вигляд

fН(x) =

ВПРАВИ

1. Доведіть рекурсивність та знайдіть ННТ оператора Y: F1→F1, заданого наступною умовою:

1)

2)

3)

4)

5)

2. Доведіть рекурсивність та знайдіть ННТ оператора Y: F2→F2, заданого наступною умовою:

1)

2)

3)

3. Доведіть рекурсивність та знайдіть ННТ оператора Y: F1→F1, заданого наступною умовою:

1) .

2) .

4. Сформулюйте та доведіть для випадку п-арних операторів відпо-відні узагальнення теорем 11.2.1 – 11.2.3.

5. Нехай F та Y - рекурсивні оператори F1´F1 → F1. Доведіть, що існує найменша пара функцій f, g така, що f=F(f, g) та g=Y(f, g), причому функцїї f та g є ЧРФ.






Реферат на тему: Eфективні операції на функціях та множинах (реферат)


Схожі реферати



5ka.at.ua © 2010 - 2017. Всі права застережені. При використанні матеріалів активне посилання на сайт обов'язкове.    
.