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

Всього в базі: 75834
останнє поновлення: 2016-11-29
за 7 днів додано 10

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

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

 

ПОШУК:   

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

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

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

 

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

 

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

 

Під кодуванням множини А на множині В будемо розуміти ін’єктивне

та сюр’єктивне відображення ( : А?В таке, що існують алгоритми 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

x

 

Номер пари (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) є ПРФ.

 

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.

 

Приклад 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.

 

?N таких послідовностей:

 

((()=0;

 

((а1, ..., ап)= C(Cп(а1, ..., ап), п-1)+1.

 

Зрозуміло, що таке відображення бієктивне. Тепер обернене відображення

-----> Page:

0 [1] [2] [3] [4] [5] [6]

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