Chiroqlar assotsiativligi testi - Lights associativity test - Wikipedia

Yilda matematika, Nurning assotsiativligi testi a .ligini tekshirish uchun F. W. Light tomonidan ixtiro qilingan protsedura ikkilik operatsiya a-da belgilangan cheklangan to'plam tomonidan a Keylini ko'paytirish jadvali bu assotsiativ. Har bir uch elementdan hosil bo'lishi mumkin bo'lgan ikkita mahsulotni taqqoslaydigan Keyli jadvali tomonidan belgilangan ikkilik operatsiyani assotsiativligini tekshirishning sodda tartibi og'ir. Lightning assotsiativligi testi ba'zi hollarda vazifani soddalashtiradi (garchi u sodda algoritmning eng yomon ish vaqtini yaxshilamasa ham, ya'ni kattalik to'plamlari uchun ).

Jarayonning tavsifi

Ikkilik operatsiya '·' cheklangan to'plamda aniqlansin A Ceyley stoli tomonidan. Ba'zi elementlarni tanlash a yilda A, ikkita yangi ikkilik operatsiya A quyidagicha:

x y = x · ( a · y )
x y = ( x · a ) · y

Ushbu operatsiyalarning Cayley jadvallari tuzilgan va taqqoslangan. Agar jadvallar o'sha paytga to'g'ri keladigan bo'lsa x · ( a · y ) = ( x · a ) · y Barcha uchun x va y. Bu to'plamning har bir elementi uchun takrorlanadi A.

Quyidagi misol Ceyley jadvallarini tuzish va taqqoslash protseduralarining yanada soddalashtirilganligini ko'rsatadi ' 'va' '.

Keylining jadvallarini tuzishning hojati yo'q 'va' ' uchun barchasi ning elementlari A. Ceyley jadvallarini taqqoslash kifoya 'va' tegishli ishlab chiqaruvchi to'plamdagi elementlarga mos keladi A.

Amaliyot qachon ". "bu kommutativ, keyin x y = y x. Natijada, har bir Cayley jadvalining faqat bir qismini hisoblash kerak, chunki x x = x x har doim ushlab turadi va x y = x y y ni nazarda tutadi x = y x.

Qachon bor hisobga olish elementi e, uni Keyli jadvallariga kiritish shart emas, chunki x y = x x va y dan kamida bittasi e ga teng bo'lsa, har doim y tutadi.

Misol

To'plamdagi '·' ikkilik amalni ko'rib chiqing A = { a, b, v, d, e } quyidagi Keyli jadvali bilan belgilanadi (1-jadval):

1-jadval
·abvde
  a  a  a  a  d  d
  b  a  b  v  d  d
  v  a  v  b  d  d
  d  d  d  d  a  a
  e  d  e  e  a  a

To'plam { v, e } - bu to'plam uchun ishlab chiqaruvchi to'plam A yuqoridagi jadval bilan belgilangan ikkilik amal ostida, uchun, a = e · e, b = v · v, d = v · e. Shunday qilib, ikkilik operatsiyalarni tekshirish kifoya ' 'va' "ga mos keladi v ikkilik operatsiyalarga to'g'ri keladi va 'va' "ga mos keladi e mos keladi.

Ikkilik operatsiyalarni tekshirish uchun ' 'va' "ga mos keladi v mos keladi, 1-jadvaldagi elementga mos keladigan qatorni tanlang v:

Jadval 2
·abvde
  a  a  a  a  d  d
  b  a  b  v  d  d
  v  a  v  b  d  d
  d  d  d  d  a  a
  e  d  e  e  a  a

Ushbu satr yangi jadvalning sarlavha qatori sifatida ko'chirildi (3-jadval):

Jadval 3
     a  v  b  d  d
   
   
   
   
   

Sarlavha ostida a sarlavha ostidagi 1-jadvaldagi tegishli ustunni nusxalash b mos keladigan ustuni 1-jadvaldagi va hokazolardan nusxa oling va 4-jadvalni tuzing.

Jadval 4
     a  v  b  d  d
  a  a  a  d  d
  a  v  b  d  d
  a  b  v  d  d
  d  d  d  a  a
  d  e  e  a  a

4-jadvalning ustun sarlavhalari endi 5-jadvalni olish uchun o'chiriladi:

Jadval 5
                  
  a  a  a  d  d
  a  v  b  d  d
  a  b  v  d  d
  d  d  d  a  a
  d  e  e  a  a

Ikkilik operatsiyaning Cayley jadvali ' 'elementga mos keladi v 6-jadval bilan berilgan.

Jadval 6
  (c)  a  b  v  d  e
  a  a  a  a  d  d
  b  a  v  b  d  d
  v  a  b  v  d  d
  d  d  d  d  a  a
  e  d  e  e  a  a

Keyin tanlang v 1-jadval ustuni:

Jadval 7
·abvde
  a  a  a  a  d  d
  b  a  b  v  d  d
  v  a  v  b  d  d
  d  d  d  d  a  a
  e  d  e  e  a  a

8-jadvalni olish uchun ushbu ustunni indeks ustuniga nusxalash:

Jadval 8
                  
  a
  v
  b
  d
  e

Indeks kiritishiga qarshi a 8-jadvalda 1-jadvaldagi tegishli qatorni indeks yozuviga qarshi nusxa ko'chiring b tegishli jadvalni 1-jadvalga va hokazolarga nusxa oling va 9-jadvalni tuzing.

Jadval 9
                  
  a  a  a  a  d  d
  v  a  v  b  d  d
  b  a  b  v  d  d
  d  d  d  d  a  a
  e  d  e  e  a  a

9-jadvalning birinchi ustunidagi indeks yozuvlari endi 10-jadvalni olish uchun o'chiriladi:

Jadval 10
                  
     a  a  a  d  d
     a  v  b  d  d
     a  b  v  d  d
     d  d  d  a  a
     d  e  e  a  a

Ikkilik operatsiyaning Cayley jadvali ' 'elementga mos keladi v 11-jadval bilan berilgan.

Jadval 11
(c)  a  b  v  d  e
  a  a  a  a  d  d
  b  a  v  b  d  d
  v  a  b  v  d  d
  d  d  d  d  a  a
  e  d  e  e  a  a

6-jadvaldagi har xil kataklardagi yozuvlar 11-jadvalning mos keladigan katakchalaridagi yozuvlar bilan mos kelishini tekshirish mumkin. x · ( v · y ) = ( x · v ) · y Barcha uchun x va y yilda A. Agar biron bir tafovut mavjud bo'lsa, unda bu to'g'ri bo'lmaydi x · ( v · y ) = ( x · v ) · y Barcha uchun x va y yilda A.

Bu x · ( e · y ) = ( x · e ) · y Barcha uchun x va y yilda A shunga o'xshash tarzda quyidagi jadvallarni tuzish orqali tasdiqlash mumkin (12-jadval va 13-jadval):

Jadval 12
 (e)  a  b  v  d  e
  a  d  d  d  a  a
  b  d  d  d  a  a
  v  d  d  d  a  a
  d  a  a  a  d  d
  e  a  a  a  d  d
Jadval 13
 (e)  a  b  v  d  e
  a  d  d  d  a  a
  b  d  d  d  a  a
  v  d  d  d  a  a
  d  a  a  a  d  d
  e  a  a  a  d  d

Keyinchalik soddalashtirish

Ikkilik operatsiyalarning Keyli jadvallarini (6-jadval va 11-jadval) tuzish shart emas ' 'va' '. Sarlavhaga mos keladigan ustunni nusxalash kifoya v 1-jadvalda 5-jadvaldagi indeks ustuniga qo'ying va quyidagi jadvalni (14-jadval) hosil qiling va a-14-jadvalning o'qi bilan bir xil a- 1-jadvalning o'sishi, b-14-jadvalning o'qi bilan bir xil b- 1-jadvalning o'qi va boshqalar. Buni takrorlash kerak mutatis mutandis ning hosil qiluvchi to'plamining barcha elementlari uchun A.

Jadval 14
     a  v  b  d  d
  a  a  a  a  d  d
  v  a  v  b  d  d
  b  a  b  v  d  d
  d  d  d  d  a  a
  e  d  e  e  a  a

Dastur

Kompyuter dasturlari Lightning assotsiativlik testini o'tkazish uchun yozilishi mumkin. Kehayopulu va Argris bunday dasturni ishlab chiqdilar Matematik.[1]

Kengaytma

Lightning assotsiativlik testi umumiy kontekstda assotsiativlikni sinash uchun kengaytirilishi mumkin.[2][3]

Ruxsat bering T = { t1, t2, , tm } bo'lishi a magma unda operatsiya bilan belgilanadi yonma-yon joylashish. Ruxsat bering X = { x1, x2, , xn } to'plam bo'ling. Dan xaritalash mavjud bo'lsin Dekart mahsuloti T × X ga X bilan belgilanadi (t, x) ↦ tx va ushbu xaritada xususiyat mavjudligini tekshirishni talab qilish kerak

(st)x = s(tx) Barcha uchun s, t yilda T va barchasi x yilda X.

Yuqoridagi xususiyat mavjudligini yoki yo'qligini tekshirish uchun Lightning assotsiativlik testini umumlashtirishni qo'llash mumkin. Matematik yozuvlarda umumlashma quyidagicha ishlaydi: har biri uchun t yilda T, ruxsat bering L(t) bo'lishi m × n elementlari matritsasi X kimning men - uchinchi qator

( (tment)x1, (tment)x2, , (tment)xn ) uchun men = 1, , m

va ruxsat bering R(t) bo'lishi m × n elementlari matritsasi X, kimning elementlari j - ustunlar

( t1(txj), t2(txj), , tm(txj) ) uchun j = 1, , n.

Umumlashtirilgan testga ko'ra (Bednarek tufayli), tekshirilishi kerak bo'lgan mulk, agar shunday bo'lsa, saqlanadi L(t) = R(t) Barcha uchun t yilda T. Qachon X = T, Bednarek testi Light testiga kamayadi.

Batafsil rivojlangan algoritmlar

Rajagopalan va tomonidan tasodifiy algoritm mavjud Shulman assotsiativlikni kirish kattaligiga mutanosib vaqt ichida sinab ko'rish. (Shuningdek, usul boshqa identifikatorlarni sinash uchun ham ishlaydi.) Xususan, ish vaqti uchun jadval va xato ehtimoli . Algoritmni uch baravar oshirish uchun o'zgartirish mumkin buning uchun , agar mavjud bo'lsa, o'z vaqtida .[4]

Izohlar

  1. ^ Kehayopulu, Niovi; Filipp Argiris (1993). "Mathematica yordamida Lightning assotsiativligini sinash algoritmi". J. Komput. Xabar bering. 3 (1): 87–98. ISSN  1180-3886.
  2. ^ Bednarek, A R (1968). "Lightning assotsiativlik sinovining kengaytmasi". Amerika matematik oyligi. 75 (5): 531–532. doi:10.2307/2314731. JSTOR  2314731.
  3. ^ Kalman, J A (1971). "Bednarekning Lightning assotsiativlik testini kengaytirishi". Semigroup forumi. 3 (1): 275–276. doi:10.1007 / BF02572966.
  4. ^ Rajagopalan, Sridxar; Schulman, Leonard J. (2000). "Shaxslarni tasdiqlash". Hisoblash bo'yicha SIAM jurnali. 29 (4): 1155–1163. CiteSeerX  10.1.1.4.6898. doi:10.1137 / S0097539797325387.

Adabiyotlar