У нашій онлайн базі вже 23511 рефератів!

Навігація
Перелік розділів
Найпопулярніше
Нові реферати
Пошук
Замовити реферат
Додати реферат
В вибране
Контакти
Російські реферати
Статьи
Об'яви

Новини
На сайті всього 23511 рефератів!
Ласкаво просимо на UA.TextReferat.com
Реферати, курсові і дипломні українською мовою, які можна скачати цілком або переглядати по сторінкам.

Усе доступно безкоштовно, тому ми не платимо винагороди за додавання. Авторські права на реферати належать їх авторам.

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

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, u)ÎDz)}.

Інакше кажучи, xÎFz(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}.

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

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 розширюється до ЧРО та не розширюється до жодного РО.

[1] 2

завантажити реферат завантажити реферат
Нове
Цікаві новини
Замовлення реферату
Замовлення реферату

Лічильники

Rambler's Top100

Усі права захищено. @ 2005-2017 textreferat.com