Нумерація Кантора

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Нумерація — це бієкція між певною множиною об'єктів, та множиною натуральних чисел.

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

Всі пари натуральних чисел розташуємо в послідовність так: пара (x, y) передує парі (u, v) ⇔ x+y<u+v або (x+y = u+v та x<u).

Номер пари (x, y) в такій послідовності позначають C(x, y) та називають канторовим номером пари (x, y). Неважко переконатись, що C(x, y) = [(x+y+1)⋅(x+y)/2]+x[1].

Ось її табулювання:

Нумерація раціональних чисел
 0   1   3   6  10  15  21  28  36  45
 2   4   7  11  16  22  29  37  46  56
 5   8  12  17  23  30  38  47  57  68
 9  13  18  24  31  39  48  58  69  81
14  19  25  32  40  49  59  70  82  95
20  26  33  41  50  60  71  83  96 110
27  34  42  51  61  72  84  97 111 126
35  43  52  62  73  85  98 112 127 143
44  53  63  74  86  99 113 128 144 161
54  64  75  87 100 114 129 145 162 180

КОДУВАННЯ ТА НУМЕРАЦІЇ. КАНТОРОВІ НУМЕРАЦІЇ[ред.ред. код]

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

Подібна нумерація застосовувалась при доведенні зліченності множини раціональних чисел, якщо їх вважати їх парами з цілих чисельника і знаменника.

Функції C, l та r зв'язані тотожностями:

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

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

Cn(x1, x2,..., xn) = Cn-1(C(x1, x2), x3,..., xn) = C(...С(C(x1, x2), x3),...), xn).

Обернена нумерація обчислюється так[2]:

def C_1(S):
	n = int((sqrt(1+8*S)-1)/2)
	k = S - (n+1)*n/2
	return (k, n-k)


Під кодуванням множини А на множині В будемо розуміти ін’єктивне та сюр’єктивне відображення  : А→В таке, що існують алгоритми A та B:
  • для кожного аА A(а)= (а);
  • для кожного bB B(b)= -1(b).

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

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

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

  • для кожного аА A(а)-1(а);
  • для кожного nN B(п)=(п).

Таким чином, : N →А  ефективна нумерація  -1: А→N  кодування А на N.

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

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

пара (x, y) передує парі (u, v)  x+y<u+v або (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→N, пара функцiй (l(n), r(n)) задає бiєкцiю N→N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п1(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) є ПРФ.
1) Функц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.

Приклад 2. Розв'яжемо рівняння C4(x,y,z,v)=207. За визначенням маємо С(С(С(x,y),z),v)=207. Нехай С(С(x,y),z)=а, маємо C(а,v)=207. Нехай a+v=р. Тоді р є найбільшим натуральним числом, для якого р(р+1)2207. Звідси р=19, звідки а=17 та v=2. Тепер маємо С(С(x,y),z)=17. Нехай С(x,y)=b, тоді C(b,z)=17. Нехай b+z=q. Тоді q є найбільшим натуральним числом, для якого q(q+1)217. Звідси q=5, звідки b=2 та z=3. Маємо C(x,y)=2, звідки x=1 та y=0.

Приклад 3. Задамо однозначну ефективну нумерацiю всiх скiнченних послiдовностей натуральних чисел на основі наступного кодування :→N таких послідовностей: ()=0; (а1, ..., ап)= C(Cп(а1, ..., ап), п-1)+1. Зрозуміло, що таке відображення бієктивне. Тепер обернене відображення η=-1 шукана однозначна нумерацiя.

Посилання[ред.ред. код]

  1. CybWiki - кодування і нумерації
  2. CybWiki джерело неавторитетне, але дані можна підтвердити експериментами