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

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

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

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

 

ПОШУК:   

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

Українські рефератиРусские рефератыКниги
НазваРешітки (структури) (реферат)
Авторdimich
РозділІнформатика, компютерні науки
ФорматWord Doc
Тип документуРеферат
Продивилось1205
Скачало247
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

Решітки

 

Серед частково впорядкованих множин винятково важливу роль відіграють

так звані решітки або структури.

 

Точною верхньою гранню підмножини A частково впорядкованої множини M

(позначається supA) називають найменшу з верхніх граней підмножини A.

Відповідно, точною нижньою гранню підмножини A частково впорядкованої

множини M (позначається infA) називають найбільшу з нижніх граней

підмножини A.

 

Частково впорядкована множина M називається решіткою (структурою), якщо

для будь-якої пари елементів a,b(M (тобто для будь-якої двоелементної

підмножини множини M ) існують sup{a,b} і inf{a,b}.

 

Приклад 1. 1. Будь-яка лінійно впорядкована множина M (наприклад,

числові множини N, Z, Q і R з традиційними відношеннями порядку) є

решіткою. Якщо a,b(M, то sup{a,b} = max(a,b) і inf{a,b} = min(a,b).

 

2. Розглянемо множину N натуральних чисел з відношенням часткового

порядку "ділить". Для a,b(N означимо sup{a,b} = НСК(a,b) і inf{a,b) =

НСД(a,b) (НСК - найменше спільне кратне, НСД - найбільший спільний

дільник). Тоді sup{12,32 }=96, inf{12,32}= 4, inf{16,27}=1.

 

3. Частково впорядкована за відношенням включення множина ((M) всіх

підмножин множини M є решіткою: sup{A,B}=A(B і inf{A,B}= A(B, A,B(M.

 

4. Розглянемо множину R кортежів дійсних чисел довжини n з відношенням

часткового порядку, означеним у прикладі 1.17(4), тобто

(a1,a2,...,an)((b1,b2,...,bn) тоді і тільки тоді, коли ai(bi,

i=1,2,...n. Частково впорядкована у такий спосіб множина R є решіткою:

sup{(a1,a2,...,an),(b1,b2,...,bn)}=(c1,c2,...,cn), де ci = max(ai,bi),

i=1,2,...n, а inf{(a1,a2,...,an),( b1,b2,...,bn)} = (d1,d2,...,dn), де

di = min(ai,bi), i=1,2,...,n.

 

Аналогічно можуть бути перетворені на решітки множини кортежів Nn, Zn,

Qn і Bn, де B = {0,1 } - множина двійкових цифр.

 

Множина P = {R1,R2,...,Rm} всіх можливих розбиттів деякої скінченної

множини M може бути перетворена в решітку в такий спосіб. Вважаємо, що

розбиття Ri={Ai1,Ai2,..., Aik} і Rj={Aj1,Aj2,...,Ajk} знаходиться у

відношенні Ri < Rj, якщо кожен клас Ait, t=1,2,...,k розбиття Ri

міститься в деякому класі Ajt розбиття Rj. Наприклад, для M ={1,2,3,4,5}

розбиття R'={{1,2},{3},{4,5}} менше розбиття R''={{1,2,3},{4,5}} і менше

розбиття R'''={{1,2},{3,4,5}}, а розбиття R'' і R''' непорівнювані.

 

Мінімальним елементом частково впорядкованої множини P є розбиття { {a}

| a(M}, а максимальним елементом - {M}. Тоді sup{Ri,Rj} = Rk, де Rk -

розбиття, в якому елементи a,b(M входять в один клас тоді і тільки тоді,

коли існує такий c(M, що кожна з пар елементів a і c та c і b належить

одному класу або в Ri, або в Rj ; inf{Ri,Rj} = Rl, де Rl - розбиття, в

якому елементи a,b(M належать одному класу тоді і тільки тоді, коли вони

належать одному класу і в Ri, і в Rj.

 

Наприклад,

 

sup{R'',R'''} = {{1,2,3,4,5}}, sup{R',R''} = {{1,2,3},{4, 5}},

 

inf{R'',R'''} = {{1,2},{3},{4,5}}, inf{R',R''} = {{1,2},{3},{4,5}}.

 

Оскільки за теоремою 1.10 існує взаємно одозначна відповідність між

усіма розбиттями даної множини M і всіма відношеннями еквівалентності на

-----> Page:

0 [1] [2]

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