Лекции по прикладной алгебре. v1.0 (1127110), страница 10
Текст из файла (страница 10)
. . , α2r(êàê è ϕ).Êîäîâîå ðàññòîÿíèå = min keγ k, γe ýëåìåíò êîäà.Çíà÷èò, íàäî äîêàçàòü ñëåäóþùååÓòâåðæäåíèåÅñëè ìíîãî÷ëåí ψ ∈ (ϕ) èìååò êîðíè αs , s = 1, . . . , 2r, òî ó ψíå ìåíåå 2r + 1 íåíóëåâîãî êîýôôèöèåíòà.137 / 225Ïðèêëàäíàÿ àëãåáðà138 / 225Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Á×ÕÎöåíêà êîäîâîãî ðàññòîÿíèÿ...ÄîêàçàòåëüñòâîÐàññìîòðèì ìíîãî÷ëåíψ(x) = a0 + a1 x + . . . + an−1 xn−1 ,óäîâëåòâîðÿþùèé óêàçàííîìó óñëîâèþ.Êîýôôèöèåíòû ψ(x) ñîñòàâëÿþò ðåøåíèå ñëåäóþùåé ñèñòåìûëèíåéíûõ óðàâíåíèé:1αα2...αn−1a00 1 α2 (α2 )2 .
. . (α2 )n−1 a1 = 0 . ... .................. 2r2r22rn−11 α(α ) . . . (α )an−10Ïðèêëàäíàÿ àëãåáðàÊîäû, èñïðàâëÿþùèå îøèáêèÊîäû Á×ÕÅñëè íàáîð a = (a0 , . . . , an−1 ) ðåøåíèå óêàçàííîé ñèñòåìû,òî ìåæäó kak ñòîëáöàìè ìàòðèöû ñèñòåìû åñòü ëèíåéíàÿçàâèñèìîñòü. Ïîýòîìó äîñòàòî÷íî ïîêàçàòü, ÷òî ëþáûå 2rñòîëáöîâ ýòîé ìàòðèöû ëèíåéíî íåçàâèñèìû.Òåîðèÿ ðåøåíèÿ ÑËÀÓ êîíå÷íûì ïîëåì íè÷åì íå îòëè÷àåòñÿ îòïðèâû÷íîé òåîðèè ðåøåíèÿ ÑËÀÓ íàä R (îíà âîâñå íå çàâèñèòîò ïîëÿ çàäàíèÿ). ÷àñòíîñòè, ëèíåéíàÿ çàâèñèìîñòü ìåæäó ñòîëáöàìèêâàäðàòíîé ìàòðèöû ðàâíîñèëüíà îáðàùåíèþ â íóëüîïðåäåëèòåëÿ ýòîé ìàòðèöû.Íàì òðåáóåòñÿ ïîêàçàòü, ÷òî â a íå ìåíåå 2r + 1 íåíóëåâûõýëåìåíòîâ ⇒ âûáåðåì èç ìàòðèöû ñòîëáöû j1 , j2 , . .
. , j2r .139 / 225Ïðèêëàäíàÿ àëãåáðà140 / 225Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Á×ÕÏîëó÷èì êâàäðàòíóþ ìàòðèöóαj1α j22j1 (α )(α2 )j2 ......(α2r )j1 (α2r )j2...αj2r. . . (α2 )j2r ......2rj2r. . . (α )Âûíåñåì èç âñåõ ýëåìåíòîâ ñòîëáöà t îáùèé ìíîæèòåëü αjt .Ïîëó÷èì, ÷òî îïðåäåëèòåëü íàøåé ìàòðèöû ñ òî÷íîñòüþ äîíåíóëåâîãî ìíîæèòåëÿ αj1 +j2 +...+j2r ðàâåí11...1jjjα1α2...α 2rj1j2j2122r.(α )...(α )V = (α )............j2r−1j2r−1j2r−1 (α 1 )(α 2 ).
. . (α 2r )Ïðèêëàäíàÿ àëãåáðà141 / 225Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Á×ÕÝòî õîðîøî èçâåñòíûé îïðåäåëèòåëü Âàíäåðìîíäà. Âû÷èñëÿåòñÿîí íàä êîíå÷íûì ïîëåì òî÷íî òàê æå, êàê è íàä R:YV =αjt2 − αjt1 .t1 <t2 êà÷åñòâå α âçÿò ïîðîæäàþùèé ýëåìåíò ìóëüòèïëèêàòèâíîéãðóïïû ïîëÿ F2∗2 , ïîýòîìó âñå ñòåïåíè α âïëîòü äî (n − 1)-éðàçëè÷íû.Ïîýòîìó V 6= 0.Ïðèêëàäíàÿ àëãåáðà141 / 225Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Á×ÕÝòî õîðîøî èçâåñòíûé îïðåäåëèòåëü Âàíäåðìîíäà. Âû÷èñëÿåòñÿîí íàä êîíå÷íûì ïîëåì òî÷íî òàê æå, êàê è íàä R:YV =αjt2 − αjt1 .t1 <t2 êà÷åñòâå α âçÿò ïîðîæäàþùèé ýëåìåíò ìóëüòèïëèêàòèâíîéãðóïïû ïîëÿ F2∗2 , ïîýòîìó âñå ñòåïåíè α âïëîòü äî (n − 1)-éðàçëè÷íû.Ïîýòîìó V 6= 0.Óòâåðæäåíèå äîêàçàíî: ðàññòîÿíèå ìåæäó êîäîâûìè ñëîâàìèíå ìåíüøå 2r + 1 ⇒ ïîñòðîåííûé êîä äåéñòâèòåëüíîèñïðàâëÿåò r îøèáîê.Ïðèêëàäíàÿ àëãåáðà142 / 225Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Á×Õ×òî äàëüøå?Äëÿ âûáîðà ìèíèìàëüíûõ ìíîãî÷ëåíîâ ïðè ïîñòðîåíèè Á×Õêîäîâ ñîñòàâëåíû ñïåöèàëüíûå òàáëèöû.Äëÿ äåêîäèðîâàíèÿ Á×Õ-êîäîâ èñïîëüçóþò ñïåöèàëüíîðàçðàáîòàííûå ýôôåêòèâíûå àëãîðèòìû(íàïðèìåð, àëãîðèòì Ïèòåðñîíà-Ãîðåíñòåéíà-Öèðëåðà).Øèðîêî èñïîëüçóåìûì ïîäìíîæåñòâîì êîäîâ Á×Õ ÿâëÿþòñÿêîäû Ðèäà-Ñîëîìîíà, êîòîðûå ïîçâîëÿþò èñïðàâëÿòü ïàêåòûîøèáîê.Ïàêåò îøèáîê ïðåäñòàâëÿåò ñîáîé âåêòîð îøèáîê (1 ñèìâîëîøèáî÷åí, 0 íåò) òàêèõ, ÷òî ïåðâûé è ïîñëåäíèé èç íèõîòëè÷íû îò íóëÿ.Ïðèêëàäíàÿ àëãåáðàÒåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÐàçäåë I1Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏîñòðîåíèå ïîëåé ÃàëóàËèíåéíàÿ àëãåáðà íàä êîíå÷íûì ïîëåìÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåì2Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èç pnýëåìåíòîâÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÇàäà÷è3Êîäû, èñïðàâëÿþùèå îøèáêèÎñíîâíàÿ çàäà÷à òåîðèè êîäèðîâàíèÿÖèêëè÷åñêèå êîäû143 / 225Ïðèêëàäíàÿ àëãåáðàÒåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÐàçäåë IIÊîäû Á×Õ4Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿêîìáèíàòîðíûõ çàäà÷5×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎïåðàöèè íàä ÷.ó.
ìíîæåñòâàìèËèíåàðèçàöèÿ6Àëãåáðàè÷åñêèå ðåø¼òêèÐåø¼òêè144 / 225Ïðèêëàäíàÿ àëãåáðà145 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÄåéñòâèå ãðóïïû íà ìíîæåñòâå: äâà îïðåäåëåíèÿÃðóïïà G = h G, ◦, e i, |G| = n.Ìíîæåñòâî T , |T | = N . ìíîæåñòâî âñåõ áèåêöèé íà T. ñèììåòðè÷åñêàÿ ãðóïïà ìíîæåñòâà T :Bij(T )Symm(T )Symm(T ) = h Bij(T ), ∗, 1T i ,Äåéñòâèå α ãðóïïûÄâà îïðåäåëåíèÿ.Gíà ìíîæåñòâå T Îïðåäåëåíèå (1)α ∈ Hom ( G, Symm(T ) ).G α: T .Ïðèêëàäíàÿ àëãåáðà146 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÄåéñòâèå ãðóïïû íà ìíîæåñòâå: äâà îïðåäåëåíèÿ...Îïðåäåëåíèå (2)α = h G, T, ◦, ∗, e, 1T i ,ãäå-◦G × G → G ãðóïïîâàÿ îïåðàöèÿ;∗G × T → T íîâàÿ îïåðàöèÿ.Àêñèîìû äëÿ îïåðàöèé:e ∗ t = t;(g ◦ h) ∗ t = h ∗ (g ∗ t).Çàïèñü îïåðàöèè ∗: g(t) = t 0 .Àêñèîìû: e(t) = t è (g ◦ h)(t) = h(g(t)).Ò.å.
g ïåðåñòàíîâêè íà T , îáëàäàþùèå âûøåóêàçàííûìèñâîéñòâàìè.Ïðèêëàäíàÿ àëãåáðà147 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÄëÿ äàííîé ïåðåñòàíîâêè g :Ââåä¼ì îòíîøåíèå ýêâèâàëåíòíîñòè ∼g íà T deft ∼g t 0 = ∃ k g k (t) = t 0 .Êëàññû ýêâèâàëåíòíîñòè íàçûâàþò g -öèêëàìè. Âñåãî C(g)êëàññîâ.Êîëè÷åñòâà öèêëîâ äëèíû 1, 2, . . . , N îáîçíà÷àþòν1 , ν2 , . . .
, νN èëè ν1 (g), ν2 (g), . . . , νN (g).Èõ óïîðÿäî÷åííóþ ñîâîêóïíîñòü, çàïèñàííóþ êàêT ype(g) = h ν1 , ν2 , . . . , νN ièëèh 1 ν1 , 2 ν2 , . . . , N νN iíàçûâàþò òèïîì ïåðåñòàíîâêè g .NNPPÏîíÿòíî, ÷òî C(g) =νk (g) èk · νk (g) = N .k=1k=1Ïðèêëàäíàÿ àëãåáðà148 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÏðèìåðÏóñòüT = { 1, . . . , 10 },1 2 3 4 5 6 7 8 9 10g ==9 6 1 8 5 2 7 10 3 4= (1, 9, 3)(2, 6)(4, 8, 10)(5)(7)ÒîãäàT ype(g)h 2, 1, 2, 0, . . .
, 0 iè C(g) = 5.=h 12 , 21 , 32 , 40 , . . . , 100 i=Ïðèêëàäíàÿ àëãåáðà149 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÏî âñåé ãðóïïå G:Îòíîøåíèå ýêâèâàëåíòíîñòè ∼G íà T deft ∼G t 0 = ∃ g g(t) = t0 .GÊëàññû ýòîé ýêâèâàëåíòíîñòè íàçûâàþò îðáèòàìè.×èñëî îðáèò (êëàññîâ ýêâèâàëåíòíîñòè) C(G).Åñëè C(G) = 1 (ëþáîé ýëåìåíò T ìîæåò áûòü ïåðåâåä¼í âëþáîé), òî äåéñòâèå G : T íàçûâàþò òðàíçèòèâíûì.αÊëàññ ýêâèâàëåíòíîñòè, â êîòîðóþ ïîïàäàåò ýëåìåíò t áóäåìîáîçíà÷àòü Orb (t).Ïðèêëàäíàÿ àëãåáðà150 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÍåïîäâèæíûå òî÷êè ãðóïïû ïðåîáðàçîâàíèé G: g(t) = tÏðè âûïîëíåíèè ýòîãî ðàâåíñòâà ìîæíî ôèêñèðîâàòü t èëè g .1Ôèêñèðóåì g , ò.å. íàõîäèì âñå ýëåìåíòû ìíîæåñòâà T , êîòîðûåïåðåñòàíîâêà g îñòàâëÿåò íà ìåñòå:def{ t ∈ T | g(t) = t } = ν1 (g) = Fix (g) ⊆ T .2Ôèêñèðóåì t, ò.å íàõîäèì âñå ïåðåñòàíîâêè g , êîòîðûå îñòàâëÿþòäàííûé ýëåìåíò íåïîäâèæíûì:def{ g ∈ G | g(t) = t } = Stab (t) ⊆ G .Ñïðàâåäëèâû ðàâåíñòâàC(G) =1 X 1 X Fix (g) = Stab (t) .|G||G|g∈Gt∈TÏåðâîå ðàâåíñòâî íàçûâàåòñÿ ëåììîé Áåðíñàéäà (1911).Ïðèêëàäíàÿ àëãåáðà151 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÑòàáèëèçàòîð åñòü ïîäãðóïïà12Fix (g) ñòàáèëèçàòîð ïåðåñòàíîâêè g ;Stab (t) ñòàáèëèçàòîð ýëåìåíòà t.ËåììàStab (t) 6G.ÄîêàçàòåëüñòâîÇàôèêñèðóåì t ∈ T è ðàññìîòðèì g, h ∈ Stab (t).
Òîãäà g(t) =h(t) = t è h−1 (t) = 1. Ñëåäîâàòåëüíî,(g ◦ h−1 ) ∗ t = t ⇒ g ◦ h−1 ∈ Stab (t) .| Stab (t)| > 1, ïîñêîëüêó âñåãäà e ∈ Stab (t).Ïðèêëàäíàÿ àëãåáðà152 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÑòàáèëèçàòîðËåììàÄëèíà îðáèòû Orb (t) ðàâíà èíäåêñó Stab (t) â ãðóïïåG, ò.å.| Orb (t)| = |G| : | Stab (t)| .ÏðèìåðO ãðóïïà âðàùåíèé êóáà (ãðóïïà îêòàýäðà). Íàéòè Stab (t).Ðåøåíèå: Stab (t) ∼= Z3 ãðóïïà âðàùåíèé íà 120◦ âîêðóãäèàãîíàëè êóáà, ïðîõîäÿùåé ÷åðåç äàííóþ âåðøèíó.Óòâåðæäåíèå×èñëî ýëåìåíòîâ â ãðóïïå âðàùåíèÿ ïðàâèëüíîãî ìíîãîãðàííèêàåñòü |V | · |E0 |, ãäå |V | ÷èñëî âåðøèí, à |E0 | ÷èñëî ð¼áåð,âûõîäÿùèõ èç îäíîé âåðøèíû.Ïðèêëàäíàÿ àëãåáðà153 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÏëàòîíîâû òåëà (ïðàâèëüíûå 3-õ ìåðíûå ìíîãîãðàííèêè)Ïëàòîíîâû òåëàòåòðàýäðêóá è îêòàýäðèêîñàýäð è äîäåêàýäðÎêòàýäðÃðóïïà ñèììåòðèèTOYÈêîñàýäðÏîðÿäîê ãðóïïû4 · 3 = 128 · 3 = 2412 · 5 = 60ÄîäåêàýäðÏðèêëàäíàÿ àëãåáðà154 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÏðèìåðÄåéñòâèå ãðóïïû V4 íà ìíîæåñòâå T = { t1 , .
. . t6 }◦eab abg ∗ t t1 t2 t3 t4 t5eababeababaeabbbabeaabbaeeababt1t2t3t4t2t1t4t3t3t4t1t2t4t3t2t1t5t6t5t6t6t6t5t6t5Ïðèêëàäíàÿ àëãåáðà155 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåT ype(e) = h 6, 0, 0, 0, 0, 0 i ,T ype(a) = h 0, 3, 0, 0, 0, 0 i ,T ype(b) = h 2, 2, 0, 0, 0, 0 i ,T ype(ab) = h 0, 3, 0, 0, 0, 0 i .C(e) = 6 , C(a) = C(ab) = 3 , C(b) = 4 .Stab (t1 ) = Stab (t2 ) = Stab (t3 ) = Stab (t4 ) = e 6 V4 ,Stab (t5 ) = Stab (t6 ) = h e, b i 6 V4 .Fix (a) = Fix (ab) = ∅ , Fix (b) = { t5 , t6 } , Fix (e) = T .44= 4 , | Orb (t5 )| == 2.| Orb (t1 )| =121X6+2| Fix (g)| == 2,44g∈G1X4t∈T| Stab (t)| =4·1+2·2= 2.4Ïðèêëàäíàÿ àëãåáðàÒåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Ðàçäåë I1Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏîñòðîåíèå ïîëåé ÃàëóàËèíåéíàÿ àëãåáðà íàä êîíå÷íûì ïîëåìÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåì2Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èç pnýëåìåíòîâÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÇàäà÷è3Êîäû, èñïðàâëÿþùèå îøèáêèÎñíîâíàÿ çàäà÷à òåîðèè êîäèðîâàíèÿÖèêëè÷åñêèå êîäû156 / 225Ïðèêëàäíàÿ àëãåáðàÒåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Ðàçäåë IIÊîäû Á×Õ4Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿêîìáèíàòîðíûõ çàäà÷5×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎïåðàöèè íàä ÷.ó.
ìíîæåñòâàìèËèíåàðèçàöèÿ6Àëãåáðàè÷åñêèå ðåø¼òêèÐåø¼òêè157 / 225Ïðèêëàäíàÿ àëãåáðàÒåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷Çàäà÷à (ïðî ñëîâà)Ñîñòàâëÿþòñÿ ñëîâà äëèíû l > 2 èç àëôàâèòà A ={ a1 , . . . , am }. Ñëîâà ñ÷èòàþòñÿ ýêâèâàëåíòíûìè, åñëè îíèïîëó÷àþòñÿ îäíî èç äðóãîãî òðàíñïîçèöèåé êðàéíèõ áóêâ.Îïðåäåëèòü ÷èñëî S íåýêâèâàëåíòíûõ ñëîâ.ÐåøåíèåT ìíîæåñòâî ñëîâ äëèíû l â àëôàâèòå A, N = |T | = ml .Íàäî ïðåäñòàâèòü ýêâèâàëåíòíîñòè êàê îðáèòû íåêîòîðîãîäåéñòâèÿ ïîäõîäÿùåé ãðóïïû G íà T .Î÷åâèäíî, g 2 = e è ïîýòîìó ïîäõîäèò G ∼= Z2 = { e, g }. Ëåãêîïðîâåðèòü, ÷òî âûøå îïðåäåëåíî äåéñòâèå Z2 íà T .158 / 225Ïðèêëàäíàÿ àëãåáðà159 / 225Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿ êîìáèíàòîðíûõ çàäà÷×èñëî S íåýêâèâàëåíòíûõ ñëîâ åñòüýêâèâàëåíòíîñòè C(G) äåéñòâèÿ Z2 : T ÷èñëîêëàññîâα| Fix (e)| = |T | = ml ,| Fix (g)| = ml−2 · m = ml−1 .ml + ml−1ml−1 (m + 1)1X| Fix (g)| ==.S = C(Z2 ) =222g∈GÄëÿ l = 3, m = 2 ⇒ S = 4·32 = 6 (èç 8)Ïóñòü A = {a, b}.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
