Лекции по прикладной алгебре. v1.0 (1127110), страница 13
Текст из файла (страница 13)
×åðåç êîíå÷íîå ÷èñëî øàãîâïîëó÷àåì ëèíåéíûé ïîðÿäîê.Ïðèêëàäíàÿ àëãåáðà×.ó. ìíîæåñòâàËèíåàðèçàöèÿÄîêàçàòåëüñòâî (ïðîäîëæåíèå)12(ïðîäîëæåíèå). Ïîñêîëüêó âîçìîæåí ðàçëè÷íûé âûáîð ïàðíåñðàâíèìûõ ýëåìåíòîâ è ïðè êàæäîì âûáîðå ìîæíîïîëàãàòü êàê ëþáîé (èç 2-õ) èõ ïîðÿäîê, òî äåéñòâóÿóêàçàííûì îáðàçîì ìîæíî ïîëó÷èòü ðàçëè÷íûå âîçìîæíûåïðîäîëæåíèÿ èñõîäíîãî ÷àñòè÷íîãî ïîðÿäêà äî ëèíåéíîãî.Ïåðåñå÷åíèå âñåõ òàêèõ öåïåé äàñò èñõîäíîå ÷.ó.
ìíîæåñòâî.Äåéñòâèòåëüíî, åñëè x 6 y , òî àíàëîãè÷íîå ñëåäîâàíèåáóäåò è âî âñåõ ïîëó÷åííûõ ëèíåéíûõ ïîðÿäêàõ, à ïðèx y âñåãäà íàéä¼òñÿ ïàðà öåïåé ñ ïðîòèâîïîëîæíûì èõñëåäîâàíèåì, ÷òî â ïåðåñå÷åíèè öåïåé è äàñò íåñðàâíèìîñòüýòèõ ýëåìåíòîâ.Äëÿ êîíå÷íûõ ìíîæåñòâ ïîèñê òàêîãî ïðîäîëæåíèÿ äëÿ ÷.ó.ìíîæåñòâ, çàäàííûõ ïàðàìè íåïîñðåäñòâåííî ñëåäóþùèõ äðóãçà äðóãîì âåðøèí â òåîðåòè÷åñêîì ïðîãðàììèðîâàíèèíàçûâàþò ¾òîïîëîãè÷åñêîé ñîðòèðîâêîé¿. Èçâåñòíûàëãîðèòìû, ðåøàþùèå äàííóþ çàäà÷ó çà ëèíåéíîå âðåìÿ.209 / 225Ïðèêëàäíàÿ àëãåáðà210 / 225×.ó. ìíîæåñòâàËèíåàðèçàöèÿÍåêîòîðûå ÷.ó. ìíîæåñòâà◦◦...◦hhhh◦hhhh .
. .hhh◦Ðèñ. 6.◦Ìàëàÿ êîðîíà sn['['hb 4[4'['hb 4[4 [[hb 4A4 [Ahb'4h'['[A4 Ah [A[4 h4 h ['hh44 [[[h'hA4[4'A'[A[[h'h4[4''[hh44h[A[A[4AhA[[[[[4 h'['[4h'['[4aaaaab144123452345Ðèñ. 7.Êîðîíà S5Ïðèêëàäíàÿ àëãåáðà211 / 225×.ó. ìíîæåñòâàËèíåàðèçàöèÿ¾e(P)= ?¿ NP-ïîëíàÿ çàäà÷à, íî:|P | + |Q|e(P + Q) =e(P)e(Q);|P | 12ne(2 × n) = ÷èñëà Êàòàëàíà;n+1 nX e(Zn ) xnn>0n!= tg x + sec x ,çíà÷åíèÿ Zn ïðè ÷¼òíûõ n ÷èñëà ñåêàíñà, à ïðè íå÷¼òíûõ ÷èñëà òàíãåíñà;e(Sn ) = (n + 1)!(n − 1)! ;X e(sn )xxn =;n!cos2 xn>1log(e(B n ))t3= log− log e + o(1) .n2bt/2c2Ïðèêëàäíàÿ àëãåáðà×.ó. ìíîæåñòâàËèíåàðèçàöèÿÄëÿ ïðàêòè÷åñêèõ öåëåé (ðåøåíèå çàäà÷ êîìáèíàòîðèêè,äèñêðåòíîé îïòèìèçàöèè è äð.) ÷àñòî ðàññìàòðèâàþòñâÿçàííîå ñ ÷.ó. ìíîæåñòâîì P âåðîÿòíîñòíîå ïðîñòðàíñòâî íàìíîæåñòâå âñåõ e(P) åãî ëèíåàðèçàöèé, â êîòîðîì êàæäàÿëèíåàðèçàöèÿ ðàâíîâåðîÿòíà. ýòîì ïðîñòðàíñòâå äëÿ ýëåìåíòîâ x, y, z, .
. . äàííîãî ÷.ó.ìíîæåñòâà ðàññìàòðèâàþò ñîáûòèÿ E âèäà x 6 y ,(x 6 y) N (x 6 z) è ò.ä. Âåðîÿòíîñòü Pr [E] òàêîãî ñîáûòèÿîïðåäåëÿþò êàê îòíîøåíèå ÷èñëà ëèíåàðèçàöèé, â êîòîðûõèìååò ìåñòî E , ê e(P ).Òåîðåìà (XYZ-òåîðåìà)Ïóñòü h P, 6 i ÷.ó. ìíîæåñòâî è x, y, z ∈ P . ÒîãäàPr [ x 6 y ] · Pr [ x 6 z ] 6 Pr [ (x 6 y) N (x 6 z) ] .212 / 225Ïðèêëàäíàÿ àëãåáðà×.ó. ìíîæåñòâàËèíåàðèçàöèÿÏðîáëåìà ñîðòèðîâêè è 1/3 2/3 ïðåäïîëîæåíèå îïðåäåëèòü ëèíåéíûé ïîðÿäê L ñ ïîìîùüþ ìèíèìàëüíîãîêîëè÷åñòâà âîïðîñîâ ¾âåðíî ëè, ÷òî x < y â L?¿.Îáîáùåíèå: âîññòàíîâèòü çàôèêñèðîâàííóþ, íî íåèçâåñòíóþëèíåàðèçàöèþ L ÷.ó. ìíîæåñòâà P ñ ïîìîùüþ ìèíèìàëüíîãîêîëè÷åñòâà òàêèõ âîïðîñîâ.Îïòèìàëüíàÿ ïðîöåäóðà ïîèñêà L âêëþ÷àåò â ñåáÿ íàõîæäåíèåýëåìåíòîâ x è y , äëÿ êîòîðûõ Pr [ x < y ] ≈ 21 .Ñ.Ñ. Êèñëèöûí (1968) âûñêàçàë ¾1/3 2/3 ïðåäïîëîæåíèå¿:ëþáîå íå ÿâëÿþùååñÿ öåïüþ ÷.ó.
ìíîæåñòâî ñîäåðæèò ïàðóíåñðàâíèìûõ ýëåìåíòîâ x è y , äëÿ êîòîðûõ126 Pr [ x 6 y ] 6”.33Ïîçäíåå âûøåïðèâåä¼ííîå óòâåðæäåíèå íåçàâèñèìî âûäâèíóëèàìåðèêàíñêèå ó÷¼íûå Ì. Ôðåäìàí è Í. Ëèíàë.213 / 225Ïðèêëàäíàÿ àëãåáðà214 / 225×.ó. ìíîæåñòâàËèíåàðèçàöèÿ1/3 2/3 ïðåäïîëîæåíèåÏðèìåð 2 + 1 ïîêàçûâàåò,÷òî óêàçàííûå ãðàíèöûíåñóæàåìû (èìååòñÿ è ïðèìåðäåñÿòèýëåìåíòíîãî ÷.ó. ìíîæåñòâàñî ñâÿçàííîé äèàãðàììîé Õàññå).Äàííîå ïðåäïîëîæåíèå äî ñèõ ïîð óñïåøíî ïðîòèâîñòîèò âñåìïîïûòêàì åãî äîêàçàòü è ïðåäñòàâëÿåò ñîáîé îäíó èç íàèáîëååèíòðèãóþùèõ ïðîáëåì êîìáèíàòîðíîé òåîðèè ÷.ó. ìíîæåñòâ(Ñ. Ôåëñíåð è Ó.Ò. Òðîòòåð).Íà ñåãîäíÿøíèé äåíü íàèáîëåå ñèëüíûé ðåçóëüòàò:√√5+ 55− 56 Pr[x 6 y] 6≈ 0, 7236 .0, 2764 ≈1010Ïðèêëàäíàÿ àëãåáðà215 / 225×.ó.
ìíîæåñòâàËèíåàðèçàöèÿ×.ó. ìíîæåñòâà: ñïåêòðSpec (P ) = {Pr [ a 6 b ] | a, b ∈ P, a 6= b}Ïîñêîëüêó Pr [ a 6 b ] = 1 − Pr [ b 6 a ], ñïåêòð ñèììåòðè÷åíîòíîñèòåëüíî 21 .äëÿ âñåõíåîäíîýëåìåíòíûõòðèâèàëüíî óïîðÿäî÷åííûõ ìíîæåñòâ1Spec 1= 2 ;0, 2 , 1 åäèíñòâåííûé òð¼õýëåìåíòíûé ñïåêòð;âñå ÷åòûð¼õýëåìåíòíûå ñïåêòðû äîëæíû èìåòü âèä{ 0, α, 1 − α, 1 }, ãäå 0 < α < 21 ; ãèïîòåçà (2002): α = 31 .Ïðèêëàäíàÿ àëãåáðà216 / 225×.ó. ìíîæåñòâàËèíåàðèçàöèÿ×.ó. ìíîæåñòâà: ðàçìåðíîñòüÏî òåîðåìå Øïèëüðàéíà ÷.ó. ìíîæåñòâî P ñîâïàäàåò ñïåðåñå÷åíèåì âñåõ e(P) ñâîèõ ëèíåàðèçàöèé.
Îäíàêî òîò æåðåçóëüòàò ìîæíî ïîëó÷èòü, âçÿâ çíà÷èòåëüíî ìåíüøåå ÷èñëîëèíåéíûõ ïðîäîëæåíèé. Íàïðèìåð, ÷.ó. ìíîæåñòâî Pbd[[ c[ aèìååò øåñòü ëèíåàðèçàöèé, íî P = [ a, b, c, d ] ∩ [ a, d, c, b ].Ïóñòü P ÷.ó. ìíîæåñòâî è R = { L1 , . . . , Lk } ñîâîêóïíîñòü öåïåé òàêàÿ, ÷òî P = L1 ∩ . . . ∩ Lk , òî ãîâîðÿò,÷òî R ðåàëèçóåò P.Ïðèêëàäíàÿ àëãåáðà217 / 225×.ó.
ìíîæåñòâàËèíåàðèçàöèÿ×.ó. ìíîæåñòâà: ðàçìåðíîñòü...ÎïðåäåëåíèåÍàèìåíüøåå ÷èñëî ëèíåéíûõ ïîðÿäêîâ, äàþùèõ â ïåðåñå÷åíèèäàííîå ÷.ó. ìíîæåñòâî P íàçûâàåòñÿ åãî (ïîðÿäêîâîé) ðàçìåðíîñòüþ(ñèìâîëè÷åñêè dim(P )).Òåîðåìà (Îðå)Ïîðÿäêîâàÿñîâïàäàþò.èìóëüòèïëèêàòèâíàÿðàçìåðíîñòè÷.ó.ìíîæåñòâà[ 1, 2, 3, 4, 5 ] ∩ [ 2, 4, 1, 3, 5 ]: [ a, b, c ] × [ d, e ]Ïðèêëàäíàÿ àëãåáðà×.ó. ìíîæåñòâàËèíåàðèçàöèÿdim(P) áîëåå òîíêàÿ îöåíêà ÷.ó.
ìíîæåñòâà, ÷åì e(P)Ðàçìåðíîñòü ... èìåþò:1 òîëüêî öåïè;2 òðèâèàëüíî óïîðÿäî÷åííûå ìíîæåñòâà(ò.å. ðàçìåðíîñòü íå ìîæåò èíòåðïðåòèðîâàòüñÿ êàê ìåðàîòëè÷èÿ äàííîãî ÷.ó. ìíîæåñòâà îò ëèíåéíîãî); Zn ; âñå îòëè÷íûå îò öåïåé ÷.ó. ìíîæåñòâ, ïðè |P | 6 6, êðîìå3 s3 , sh è shd :n Sn .218 / 225Ïðèêëàäíàÿ àëãåáðà×.ó. ìíîæåñòâàËèíåàðèçàöèÿÎ ðàçìåðíîñòè ÷.ó. ìíîæåñòâà P = h P, 6 i1234∅ 6= Q ⊆ P ⇒ dim(Q) 6 dim(P), ïðè ýòîì ïðè óäàëåíèèîäíîãî ýëåìåíòà åãî ðàçìåðíîñòü óìåíüøàåòñÿ íå áîëåå, ÷åìíà 1;dim(P + Q) = max { dim(P), dim(Q) }, åñëè õîòÿ áû îäíîèç ìíîæåñòâ íå ÿâëÿåòñÿ öåïüþ è dim(P + Q) = 2, èíà÷å;dim(P × Q) 6 dim(P) + dim(Q);dim(P) 6 |P |/2 ïðè |P | > 4 (òåîðåìà Õèðàãó÷è).Òåîðåìà (¾êîìïàêòíîñòè¿)Ïóñòü P òàêîå ÷.ó. ìíîæåñòâî, ÷òî ëþáîå åãî êîíå÷íîå ÷.ó.ïîäìíîæåñòâî èìååò ðàçìåðíîñòü, íå ïðåâîñõîäÿùóþ d.
Òîãäàdim(P) 6 d.nc1nc21−6 dim(P ) 61−.4log2 n4log2 n219 / 225Ïðèêëàäíàÿ àëãåáðà220 / 225×.ó. ìíîæåñòâàËèíåàðèçàöèÿd-íåñâîäèìûå ÷.ó. ìíîæåñòâàÎïðåäåëåíèå×.ó. ìíîæåñòâî P íàçûâàåòñÿ d-íåñâîäèìûì äëÿ íåêîòîðîãî d >2, åñëè dim(P) = d è dim(P 0 ) < d äëÿ ëþáîãî ñîáñòâåííîãî÷.ó. ïîäìíîæåñòâà P 0 ⊂ P .... íåñâîäèìûå ìíîæåñòâà:2 äâóõýëåìåíòíàÿ àíòèöåïü (åäèíñòâåííîå);3 s3 , sh, shd + ... îïèñàíû, ðåãóëÿðíû è õîðîøî èçó÷åíû;4 äîñòàòî÷íî ÷àñòî âñòðå÷àþòñÿ è âåñüìà ïðè÷óäëèâû;t St (åäèíñòâåííîå 2t-ýëåìåíòíîå) + ...;êàæäîå t-íåñâîäèìîå ÷.ó. ìíîæåñòâî ÿâëÿåòñÿ ÷.ó. ïîäìíîæåñòâîìíåêîòîðîãî (t + 1)-íåñâîäèìîãî.Ïðèêëàäíàÿ àëãåáðà221 / 225×.ó.
ìíîæåñòâàËèíåàðèçàöèÿÏðîáëåìà ÍîãèíàÊàêîâî íàèáîëüøåå çíà÷åíèå π(d, n) ìîùíîñòè ìíîæåñòâàìàêñèìàëüíûõ ýëåìåíòîâ d-íåñâîäèìîãî n-ýëåìåíòíîãî ÷.ó.ìíîæåñòâà ïðè d > 4?Äàííàÿ ïðîáëåìà äî ñèõ ïîð îñòà¼òñÿ îòêðûòîé.Óòâåðæäåíèåπ(d, n) 6 n − d.Ïðèêëàäíàÿ àëãåáðà×.ó. ìíîæåñòâàËèíåàðèçàöèÿ-222 / 225Ïðèêëàäíàÿ àëãåáðàÀëãåáðàè÷åñêèå ðåø¼òêèÐåø¼òêèÐàçäåë I1Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏîñòðîåíèå ïîëåé ÃàëóàËèíåéíàÿ àëãåáðà íàä êîíå÷íûì ïîëåìÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåì2Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èç pnýëåìåíòîâÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÇàäà÷è3Êîäû, èñïðàâëÿþùèå îøèáêèÎñíîâíàÿ çàäà÷à òåîðèè êîäèðîâàíèÿÖèêëè÷åñêèå êîäû223 / 225Ïðèêëàäíàÿ àëãåáðàÀëãåáðàè÷åñêèå ðåø¼òêèÐåø¼òêèÐàçäåë IIÊîäû Á×Õ4Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿêîìáèíàòîðíûõ çàäà÷5×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎïåðàöèè íàä ÷.ó.
ìíîæåñòâàìèËèíåàðèçàöèÿ6Àëãåáðàè÷åñêèå ðåø¼òêèÐåø¼òêè224 / 225Ïðèêëàäíàÿ àëãåáðàÀëãåáðàè÷åñêèå ðåø¼òêèÐåø¼òêè×=225 / 225.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
