Нумерації. Теореми про нерухому точку, Детальна інформація

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

Нумерації. Теореми про нерухому точку

1. КОДУВАННЯ ТА НУМЕРАЦІЇ. КАНТОРОВІ НУМЕРАЦІЇ

Під кодуванням множини А на множині В будемо розуміти ін’єктивне та сюр’єктивне відображення ( : А\x2192В таке, що існують алгоритми A та B:

\xF02D\xF020для кожного а(А A(а)(((а);

\xF02D\xF020для кожного b(B B(b)=( -1(b).

Нумерацiєю множини А називають сюр’єктивне функцiональне вiдображення (: N \x2192А.

Однозначною нумерацiєю множини А називають бієктивне вiдображення (: N \x2192А.

Нумерацiю (: N \x2192А називають ефективною, якщо iснують алгоритми A та B такі:

\xF02D\xF020для кожного а(А A(а)((-1(а);

\xF02D\xF020для кожного n(N B(п)=((п).

Таким чином, (: N \x2192А \xF02D ефективна нумерація ( (-1: А\x2192N \xF02D кодування А на N.

Введемо однозначні ефективні нумерацiї пар та n-ок натуральних чисел, які називаються канторовими нумераціями.

Всi пари натуральних чисел розташуємо в послiдовнiсть так:

пара (x, y) передує парі (u, v) ( x+y
Номер пари (x, y) в такiй послiдовностi позначають C(x, y) та називають канторовим номером пари (x, y).

Неважко переконатись, що C(x, y) = [(x+y+1)((x+y)/2]+x

Лiву та праву компоненти пари з номером n позначають вiдповiдно l(n) та r(n). Функцiї l(n) та r(n) називають вiдповiдно лiвою та правою координатними функцiями.

Функцiя C(x, y) задає бiєкцiю N(N\x2192N, пара функцiй (l(n), r(n)) задає бiєкцiю N\x2192N(N. При цьому функцiї C, l та r зв’язaнi такими тотожностями:

C(l(n), r(n)=n; l(C(x, y))=x; r(C(x, y))=y.

Маючи нумерацiю пар натуральних чисел, можна ввести нумерацiю n-ок натуральних чисел для довiльного n>2:

Cп(x1, x2,..., xп)=Cп\xF02D1(C(x1, x2), x3,..., xп)=C(...С(C(x1, x2), x3),...), xп).

Координатнi функцiї Cn1 , ..., Cnn вводимо так:

Нехай Cп(x1, x2,..., xп)=m; тоді Cn1(m)=x1; Cn2(m)=x2; ... , Cnn(m)=xn.

Для функцiй Cп, Cn1 , ..., Cnn справджуються такi тотожностi:

Cп(Cn1(x), ..., Cnn(x))=x;

Cnk(Cп(x1, x2,..., xп))=xk, 1(k(n.

Теорема 1.1. 1) Функцiї C(x, y), l(n) та r(n) є ПРФ.

2) Функцiї Cп, Cn1 , ..., Cnn є ПРФ.

Приклад 1. Знайдемо l(100) та r(100). Для х=l(100) та у=r(100) маємо рівняння С(х, у)=100. Нехай х+у=р. Тоді р є найбільшим натуральним числом, для якого р((р+1)(2(100. Звідси р=13. Маємо х+у=13, х=100-[(13(14)/2]=9, y=13-9=4. Отже, l(100)=9 та r(100)=4.