UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваEфективні операції на функціях та множинах (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось1607
Скачало310
Опис
ЗАКАЧКА
Замовити оригінальну роботу

Реферат на тему:

 

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 маємо:

 

 

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

 

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

 

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

 

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

(df1)

 

для х1 , ..., хп.

 

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

 

, у)(Nп+1 маємо

 

)) (df2)

-----> Page:

0 [1] [2] [3] [4]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ