WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Eфективні операції на функціях та множинах - Реферат

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


Реферат на тему:
Eфективні операції на функціях та множинах
Множину всіх n-арних функцій на N, тобто функцiй iз Nп в N, позначимо Fп. Об'єднання множин Fп для всіх п 1 позначимо F. Множину всіх тотальних функцій із Fп та множину всіх тотальних функцій із F відповідно позначимо Tп та T . Cкінченні множини в цьому розділі позначаємо F, скінченні функції позначаємо .
Довільну функцію вигляду : (2N)m?2N назвемо m-арним множинним оператором (скорочено МО).
Довільну функцію вигляду ?: (F)m?F назвемо m-арним функціональним оператором (скорочено ФО).
Функціональні оператори називають також операціями на функціях, або композиціями.
Приклад. Операції суперпозиції Sn+1 : (F)m?F, примітивної рекурсії R : F F ?F та мінімізації M : F F?F є прикладами ФО.
МО : (2N)m?2N називається монотонним, якщо із умови А1 В1 , А2 В2 , ..., Ат Вт випливає (А1 , ..., Ап) (В1 , ..., Вп).
ФО : (F)m?F називається монотонним, якщо із умови f1 g1 , f2 g2 , ..., fт gт випливає (f1 , ..., fп) (g1 , ..., gп).
МО : (2N)m?2N називається неперервним, якщо для всіх х N, A (2N)m маємо х (A) F A : х (F).
ФО : Fп?F називається неперервним, якщо для всіх х Nп, y N та f Fп маємо (х, у) (f) f : (х, у) ( ).
Легко довести, що кожний неперервний оператор є монотонним.
11.1. ОПЕРАТОРИ ПЕРЕЛІКУ. ЧАСТКОВО РЕКУРСИВНІ ТА РЕКУРСИВНІ ОПЕРАТОРИ
Ефективність множинного оператора : 2N?2N означає можли-вість ефективно задати множину (A), якщо ефективно задається множина А. Ефективні множинні оператори називаються [10] операторами переліку (скорочено ОП).
Для кожного z N оператор переліку z : 2N?2N задається співвідношенням z(A) ={x | u(Fu А C(x, u) Dz)}.
Інакше кажучи, x z(A) u(Fu А C(x, u) Dz).
Теорема 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}.
Кожний функціональний оператор : Fm?Fn задає множинний оператор : CF?CF та навпаки:
: Fm ? Fn
Сm+1 (Сm+1)-1 Сn+1 (Сn+1)-1
: CF ? CF
Звідси (f)=(Сn+1)-1( (Сm+1(f))) та (A)=Сn+1( ((Сm+1)-1(A))).
ФО : Fm?Fn називається частково рекурсивним оператором (ЧРО), якщо існує z N таке, що для всіх f Fm маємо:
(f)=
В цьому випадку кажуть, що ОП z визначає ЧРО .
Тотальний ЧРО назвемо рекурсивним оператором (РО).
Інакше кажучи, ФО : Fm?Fn рекурсивний оператор, якщо
існує z N таке: для всіх f Fm (f)=(Сn+1)-1( z(Сm+1(f))) (df1)
Дамо безпосереднє визначення РО, не використовуючи поняття оператора переліку. Вживатимемо скорочення для х1 , ..., хп.
ФО : Fm?Fn рекурсивний оператор, якщо
існує z N таке: для всіх f Fm, ( , у) Nп+1 маємо
( , у) (f) и( f у= (и, )) (df2)
Зрозуміло, що таке визначення РО еквівалентне наступному:
існує ЧРФ така: для всіх f Fm, ( , у) Nп+1 маємо
( , у) (f) и( f у= (и, )) (df3)
Теорема 11.1.2. Визначення df1, df2 та df3 еквівалентні.
Надалі для РО будемо, як правило, використовувати df3.
Теорема 11.1.3. Кожний РО є неперервним та монотонним.
Приклад 1. Нехай оператор : F1?F1 задається співвідношеням
Тоді немонотонний, отже, не РО.
Візьмемо скінченну f та нескінченну f . Тоді ( )= f та (f)=f . Маємо f та (f) ( ). Отже, не є монотонним.
Приклад 2. Нехай оператор : F1?F1 задається співвідношеням
Тоді не неперервний і не РО.
Візьмемо функцію f із нескінченною Еf (наприклад, f тотожна функція). Тоді (f)=f f та ( )=f для кожної скінченної f. Тому якщо (х, у) (f), то не існує скінченної функції f такої, що (х, у) ( ), бо ( )=f = . Отже, не є неперервним.
Для доведення рекурсивності операторів корисним є наступний критерій рекурсивності:
Теорема 11.1.4. Оператор : Fт?Fп є рекурсивним оператором неперервний та функція
є ЧРФ.
Розглянемо приклади використання теореми 11.1.4.
Приклад 3. Оператор : Fт?Fп задається умовою (f)=g для всіх f Fт, де g фіксована ЧРФ. Тоді є РО.
Оператор неперервний: умова ( , у) (f) ( , у) ( ) виконується для довільної скінченної f , адже (f)= ( )=g. Функція (и, )= є ЧРФ за ТЧ.
Приклад 4. Задамо оператор : F1?F1 таким співвідношенням: (f)(x)= f(f(x+2))+5x для всіх f F1. Тоді є РО.
Оператор неперервний: (х, у) (f) (х, у) ( ) виконується для кожної скінченної f такої, що x+2 D та f(x+2) D . Тепер
(и, х) =
є ЧРФ за ТЧ.
Приклад 5. Оператор мінімізації М: Fп+1?Fп задається умовою М(f)( ) = у(f( , у)=0) для всіх f Fп+1. Тоді М є РО.
Оператор М неперервний: у= у(f( , у)=0) у= у( ( , у)=0) виконується для кожної f такої, що ( , 0), ( , 1), ..., ( , у) D ; тому y=М(f)( ) y=М( )( ) для кожної такої f. Тепер функція
(и, ) = є ЧРФ за ТЧ.
Приклад 6. Нехай ФО 0 : F1?F1 задається співвідношенням 0({(0,0)})={(0,0)} та 0({(1,0)})={(0,1)}; для інших f F1 значення 0(f) невизначене. Тоді 0 розширюється до ЧРО та не розширюється до жодного РО.
Позаяк {C(0,0)}={0}=F1 та {C(1,0)}={2}=F4 , беремо z таке, що Dz ={C(0,20), C(1,22)}. Нехай ОП z задається таким Dz , тобто x z(A) u(Fu А C(x, u) Dz). Зрозуміло, що для кожних A 2N z(A) l(Dz)={0,1}. Маємо:
якщо А та А, то z(A)={0,1};
якщо А та А, то z(A)={0};
якщо А та А, то z(A)={1};
якщо 0 А та 2 А, то z(A)= .
Для ЧРО , який визначається таким ОП z , маємо:
1) Якщо (0,0) f та (1,0) f, то 0 C(f) та 2 C(f), звідки z(C(f))= . Отже, для таких f (f)=f .
2) Якщо (0,0) f та (1,0) f, то 0 C(f) та 2 C(f), звідки z(C(f))={0}=C(0,0). Отже, для таких f (f)={(0,0)};
3) Якщо (0,0) f та (1,0) f, то 0 C(f) та 2 C(f), звідки z(C(f))={1}=C(0,1). Отже, для таких f (f)={(0,1)};
4) Якщо (0,0) f та (1,0) f, то 0 C(f) та 2 C(f), звідки z(C(f))={0,1} неоднозначна множина. Отже, для таких f (f) невизначене, тому не РО.
Із 2) та 3) випливає, що ЧРО є розширенням оператора 0 .
Нехай ={(0,0), (1,0)}. Для довільного ЧРО , що є розширенням 0 , маємо: якщо ( ) , то ( ) ({(0,0)})=0({(0,0)})={(0,0)} та ( ) ({(1,0)})= 0({(1,0)})={(0,1)}. Але тоді ( ) як множина не є функція, тобто ( ) . Отже, кожний такий ЧРО нетотальний, тобто не РО. Таким чином, 0 не можна розширити до РО.
Приклад 7. ЧРО із прикладу 6 немонотонний.
Для ={(0,0), (1,0)} маємо ( ) , але ({(0,0)})={(0,0)}. Тому з умови {(0,0)} не випливає ({(0,0)} ( ).
ЧРО називають загальнорекурсивним оператором (ЗРО), якщо Tт D та (Tт) Fn.
Теорема 11.1.5. Нехай ЧРО : Fт?Fп такий, що Tт D . Тоді є РО.
Наслідок. Для класів ЗРО, РО та ЧРО маємо строгі включення ЗРО РО ЧРО.
За теоремою 11.1.5 ЗРО РО. Але РО прикладу 3 не є, очевидно, ЗРО, якщо ЧРФ g взяти нетотальною, тобто не РФ. За визначенням РО ЧРО. Але ЧРО із прикладу 6 немонотонний, тому не РО.
ВПРАВИ
1. Нехай z оператор переліку. Дослідити співвідношення:
1) між множинами z(А В) та z(А) z(В);
2) між множинами z(А В) та z(А) z(В).
2. Нехай та монотонні оператори (тут та
Loading...

 
 

Цікаве