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

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

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

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

1-арні МО або ФО вигляду : Fт?Fр та : Fр?Fп). Доведіть, що оператор теж монотонний
3. Нехай та неперервні оператори (тут та 1-арні МО або ФО вигляду : Fт?Fр та : Fр?Fп). Доведіть, що оператор теж неперервний
4. Нехай та рекурсивні оператори вигляду : Fт?Fр та : Fр?Fп. Доведіть, що оператор теж рекурсивний
5. Доведіть рекурсивність оператора : F1?F1, заданого умовою:
1) (f)(x) = ;. 2) (f)(x) = .
6. Доведіть рекурсивність оператора : F1?F1, заданого так:
1) (f)(x) = f(f(f(x+1)))+x; 2) (f)(x) = f(f(x2+3))+2x;
3) (f)(x) = (f(f(3x)))2+3x; 4) (f)(x) = f(f(7x+5)))+f(f(f(x))).
7. Доведіть рекурсивність оператора : F2?F1, заданого умовою: 1) (f)(x) = f(x, x);
2) (f)(x) = f(f(2x, x), f(x, 3x));
3) (f)(x) = f(f(x, x)+1, f(3x, x)+2)+3.
8. Чи буде рекурсивним оператор : F1?F1, що задається наступною умовою:
1)
2)
3)
4)
5)
6)
9. Сформулюйте визначення п-арного неперервного функціональ-ного оператора вигляду : 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 маємо z(Dy)=Ds(x,y)..
Наслідок. Нехай А є РПМ. Тоді z(A) є РПМ.
Кожний РО при обмеженні на ЧРФ задає на їх індексах ефективну операцію, тобто рекурсивну функцію.
Теорема 11.2.2 (Майхілл, Шепердсон). Для кожного РО : Fт?Fп існує РФ h така: для кожного k N маємо ( )= .
Наслідок. Нехай є РО, f є ЧРФ. Тоді (f) є ЧРФ.
Функція h m-n-екстенсійна, якщо з умови випливає . 1-1-екстенсійні функції назвемо просто екстенсійними.
Приклад 1. РФ h із теореми 11.2.2 m-n екстенсійна. Справді, з умови випливає .
Теорема 11.2.3 (Майхілл, Шепердсон). Для кожної m-n-екстенсій-ної РФ h існує єдиний РО : Fт?Fп такий, що ( )= ). для кожного k N.
Множина А називається найменшою нерухомою точкою (ННТ) оператора : 2N?2N , якщо:
1) (A)=A, тобто A нерухома точка (НТ) оператора ;
2) якщо (B)=B, то A B; тобто A найменша НТ оператора .
Теорема 11.2.4 (С.Кліні). 1) Кожний неперервний множинний оператор : 2N?2N має найменшу нерухому точку;
2) якщо є оператором переліку, то його ННТ є РПМ.
Множину A, що є ННТ оператора , будуємо методом послідовних наближень. Задамо послідовність множин {An}n N так: A0= ; An+1= (An) для n 0. Покладемо .
Враховуючи неперервність, доводимо, що А є ННТ оператора . Якщо є оператором переліку, то доводиться, що A є РПМ.
Функція f називається найменшою нерухомою точкою оператора : Fп?Fп, якщо:
1) (f)=f, тобто f нерухома точка оператора ;
2) якщо (g)=g, то f g; тобто f найменша НТ оператора .
Приклад 2. Нехай ННТ f оператора є тотальною функцією. Тоді f єдина нерухома точка оператора .
Приклад 3. Найменша нерухома точка тотожного оператора це f . Тотожний оператор є ЗРО. Отже, для ЗРО найменша нерухома точка може бути нетотальною функцією.
Теорема 11.2.5 (С.Кліні). 1) Кожний неперервний ФО : Fп?Fп має найменшу нерухому точку;
2) якщо є РО, то його ННТ є ЧРФ.
Функцію f, що є ННТ оператора , будуємо методом послідовних наближень. Задамо послідовність функцій {fn}n N так: f0=f ; fn+1= (fn) для n 0. Покладемо .
Враховуючи неперервність, доводимо, що f є ННТ оператора . Якщо є рекурсивним оператором, то доводиться, що f є ЧРФ.
Нехай РО : F1?F1 визначений ОП z : для всіх f F1 маємо (f)=С-1( z (С(f))). Нехай А є НТ оператора z : А= z (А). Тоді функція f =С-1(А) є нерухомою точкою РО : (f)=С-1( z (С(f)))= =С-1( z (А))=С-1(А)=f . З іншого боку, нехай f НТ РО : (f)=f. Тоді множина А=С(f) НТ оператора z : z (С(f))=С( (f))=С(f).
Приклад 4. Для ЧРО не РО найменшої нерухомої точки може не існувати. Це буває тоді, коли множина А, що є ННТ відповідного ОП z , неоднозначна. Тоді кожна В А неоднозначна, тому такий взагалі не має нерухомих точок.
Приклад 5. Знайдемо ННТ оператора : F1?F1, заданого умовою
Оператор неперервний: (х, у) (f) (х, у) ( ) виконується при х=0 для довільної скінченної f, при х>0 ця умова викону-ється для кожної скінченної f такої, що x+1 D . Отже, має ННТ fH , яку знайдемо методом послідовних наближень.
Маємо f0=f . Тепер знаходимо f1 та f2:
f1(х)= (f0)(х) = =
f2(х)= (f1)(х) = =
Отже, f2 = f1. Маємо стабілізацію, тому fп = f1 для всіх n>0. Звідси ННТ fH = f1 . Зауважимо, що інші нерухомі точки нашого оператора мають вигляд fТ(х) =
Приклад 6. Знайдемо ННТ оператора : F2?F2, заданого умовою
Оператор неперервний: умова (х, у, z) (f) (х, у, z) ( ) виконується при х=0 для довільної скінченної f, при х>0 ця умова виконується для кожної скінченної f такої, що (х, у) D та (х 1, f(х, у)) D . Отже, має ННТ fH , яку знайдемо методом послідовних наближень. Маємо f0=f . Тепер знаходимо f1 та f2:
f1(х, у) = (f0)(х, у)) = = =
f2(х, у) = (f1)(х, у)) = = = бо f1(х, у) невизначене при x>0.
Отже, f2 = f1. Маємо стабілізацію, тому fп = f1 для всіх n>0. Звідси ННТ fH = f1 .
Приклад 7. Знайдемо ННТ оператора : F1?F1, заданого умовою
Оператор неперервний: (х, у) (f) (х, у) ( ) виконується при х=0 для довільної скінченної f, при х>0 умова виконується для кожної скінченної f такої, що x 1 D . Отже, має ННТ.
Метод послідовних наближень тут вимагає нескінченної кількості кроків, бо fп+1 fп для всіх n 0. Тому використаємо обхідні шляхи. Нехай fH ННТ нашого оператора. Тоді для кожного х N маємо fН(х)= (fН)(х) = 2х 1+ fН(х 1) = 2х 1+ (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 єдина нерухома точка нашого .
Приклад 8. Знайдемо ННТ оператора : F1?F1, заданого умовою
Оператор неперервний: (х, у) (f) (х, у) ( ) виконується при х>55 для довільної скінченної f, при х 55 умова викону-ється для кожної скінченної f такої, що x+7 D та f(x+7) D . Отже, має ННТ, нехай це функція fH . Для кожного х>55 маємо fН(x)= (fН)(х) = х 6. Тепер fН(55)= (fН)(55) = fН(fН(62)) = fН(56) = 50. Тоді fН(54)= (fН)(54) = fН(fН(61)) = fН(55) = 50. Продовжуючи далі, аналогічно дістаємо fН(53) = fН(54) = 50, …, fН(0) = fН(1) = 50. Отже, fH єдина нерухома точка оператора , причому така fH має вигляд
fН(x) =
ВПРАВИ
1. Доведіть рекурсивність та знайдіть ННТ оператора : F1?F1, заданого наступною умовою:
1)
2)
3)
4)
5)
2. Доведіть рекурсивність та знайдіть ННТ оператора : F2?F2, заданого наступною умовою:
1)
2)
3)
3. Доведіть рекурсивність та знайдіть ННТ оператора : F1?F1, заданого наступною умовою:
1)
2)
4. Сформулюйте та доведіть для випадку п-арних операторів відпо-відні узагальнення теорем 11.2.1 - 11.2.3.
5. Нехай та рекурсивні оператори F1 F1 ? F1. Доведіть, що існує найменша пара функцій f, g така, що f= (f, g) та g= (f, g), причому функцїї f та g є ЧРФ.
Loading...

 
 

Цікаве