Лекции по прикладной алгебре. v1.0 (1127110)
Текст из файла
Ïðèêëàäíàÿ àëãåáðà1 / 225Ïðèêëàäíàÿ àëãåáðàËåêöèè äëÿ III ïîòîêà,5-é ñåìåñòð 2013/2014 ó÷. ãîäàÃóðîâ Ñåðãåé Èñàåâè÷Ôàêóëüòåò Âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêè,ÌÃÓ èìåíè Ì.Â. ËîìîíîñîâàÊàôåäðà Ìàòåìàòè÷åñêèõ ìåòîäîâ ïðîãíîçèðîâàíèÿêîìí. 530, 682e-mail: sgur@cs.msu.ruÏðèêëàäíàÿ àëãåáðàËèòåðàòóðàÂîðîíèíÂ.Ï.Äîïîëíèòåëüíûåãëàâûäèñêðåòíîéìàòåìàòèêè.Ì.:ô-òÂÌÊÌÃÓ,2002.http://padabum.com/d.php?id=10281Ãóðîâ Ñ.È. Áóëåâû àëãåáðû, óïîðÿäî÷åííûå ìíîæåñòâà,ðåøåòêè: Îïðåäåëåíèÿ, ñâîéñòâà, ïðèìåðû. Ì.: Ëèáðîêîì,2013.Æóðàâë¼â Þ.È., Ôë¼ðîâ Þ.À., Âÿëûé Ì.Í.
Äèñêðåòíûéàíàëèç. Îñíîâû âûñøåé àëãåáðû. Ì.: ÌÇ Ïðåññ, 2007.Ëèäë Ð., Íèäåððàéòåð Ã. Êîíå÷íûå ïîëÿ:  2-õ ò. Ì.: Ìèð,1988.Íåôåäîâ Â.Í., Îñèïîâà Â.À. Êóðñ äèñêðåòíîé ìàòåìàòèêè. Ì.:Èçä-âî ÌÀÈ, 1992.Ðîìàùåíêî À.Å., Ðóìÿíöåâ À.Þ., Øåíü À. Çàìåòêè ïî òåîðèèêîäèðîâàíèÿ. Ì.: ÌÖÍÌÎ, 2011.2 / 225Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÐàçäåë I1Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏîñòðîåíèå ïîëåé ÃàëóàËèíåéíàÿ àëãåáðà íàä êîíå÷íûì ïîëåìÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåì2Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èç pnýëåìåíòîâÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÇàäà÷è3Êîäû, èñïðàâëÿþùèå îøèáêèÎñíîâíàÿ çàäà÷à òåîðèè êîäèðîâàíèÿÖèêëè÷åñêèå êîäû3 / 225Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÐàçäåë IIÊîäû Á×Õ4Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿêîìáèíàòîðíûõ çàäà÷5×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎïåðàöèè íàä ÷.ó.
ìíîæåñòâàìèËèíåàðèçàöèÿ6Àëãåáðàè÷åñêèå ðåø¼òêèÐåø¼òêè4 / 225Ïðèêëàäíàÿ àëãåáðà5 / 225Ïîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏîëå GF (p)Z åâêëèäîâî êîëüöî öåëûõ ÷èñåë (áåç äåëèòåëåé íóëÿ +äåëåíèå ñ îñòàòêîì).p ïðîñòîå ÷èñëî.(p) = {np | n ∈ Z} = pZ = {0, ±p, ±2p, . . .} èäåàëZ/pZ êîëüöî âû÷åòîâ ïî ìîäóëþ ýòîãî èäåàëà:{0, 1, . . . , p − 1} êëàññû îñòàòêîâ îò äåëåíèÿ íà p:0 = 0 + pZ ,1 = 1 + pZ ,...p − 1 = (p − 1) + pZ .Z= 0 ∪ 1 ∪ . . . ∪ p − 1.Ïîñêîëüêó p ïðîñòîå, òî Z/pZ ïîëå.Ýòî ïðîñòåéøåå ïîëå Ãàëóà, îáîçíà÷åíèå Âñå îïåðàöèè â ïîëå Fp ïî mod p.Fp èëè GF (p).Z/pZ=Ïðèêëàäíàÿ àëãåáðà6 / 225Ïîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàF3 è Z/4ZF3 :+012001211202201·012000010122021Ïðèêëàäíàÿ àëãåáðà6 / 225Ïîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàF3 è Z/4ZF3 :+012001211202201Z/4Z :+012300123112302230133012·012000010122021·012300000101232020230321Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÕàðàêòåðèñòèêà ïîëÿÏóñòü k ïðîèçâîëüíîå ïîëå, 1 åäèíèöà k.
Ñêëàäûâàåì èõ:1 = 1 , 2 = 1 + 1 , . . ..7 / 225Ïðèêëàäíàÿ àëãåáðà7 / 225Ïîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÕàðàêòåðèñòèêà ïîëÿÏóñòü k ïðîèçâîëüíîå ïîëå, 1 åäèíèöà k. Ñêëàäûâàåì èõ:1 = 1 , 2 = 1 + 1 , . . ..  êîíå÷íîì ïîëå âñåãäà íàéä¼òñÿïåðâîå k òàêîå, ÷òî 1. . + 1} = 1. Òîãäà| + .{zkðàçk = ïîðÿäîê àääèòèâíîé ãðóïïû ïîëÿ k == õàðàêòåðèñòèêà ïîëÿ k = char kdefÏðèêëàäíàÿ àëãåáðà7 / 225Ïîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÕàðàêòåðèñòèêà ïîëÿÏóñòü k ïðîèçâîëüíîå ïîëå, 1 åäèíèöà k. Ñêëàäûâàåì èõ:1 = 1 , 2 = 1 + 1 , . . ..  êîíå÷íîì ïîëå âñåãäà íàéä¼òñÿïåðâîå k òàêîå, ÷òî 1.
. + 1} = 1. Òîãäà| + .{zkðàçk = ïîðÿäîê àääèòèâíîé ãðóïïû ïîëÿ k == õàðàêòåðèñòèêà ïîëÿ k = char kdefÇíà÷åíèå k ïîðîæäàåò èäåàë k = (char k) âZ.Z/(char k) ïîëå i k ïðîñòîå ÷èñëî, ïîäïîëå k.Åñëè âñå ñóììû 1. . + 1} ðàçëè÷íû, òî char k = 0.| + .{zÏðèìåðû:Q, R.kÏðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÌîæåò ëè áåñêîíå÷íîå ïîëå èìåòü ïîëîæèòåëüíóþõàðàêòåðèñòèêó?8 / 225Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÌîæåò ëè áåñêîíå÷íîå ïîëå èìåòü ïîëîæèòåëüíóþõàðàêòåðèñòèêó?k ïðîèçâîëüíîå (êîíå÷íîå èëè áåñêîíå÷íîå) ïîëå. Ïîñòðîèì:1k[x] ìíîæåñòâî ìíîãî÷ëåíîâ P (x) = a0 + a1 x + .
. . + an xn ,a0 , . . . , an ∈ k îò x ñ êîýôôèöèåíòàìè èç k.8 / 225Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÌîæåò ëè áåñêîíå÷íîå ïîëå èìåòü ïîëîæèòåëüíóþõàðàêòåðèñòèêó?k ïðîèçâîëüíîå (êîíå÷íîå èëè áåñêîíå÷íîå) ïîëå. Ïîñòðîèì:12k[x] ìíîæåñòâî ìíîãî÷ëåíîâ P (x) = a0 + a1 x + . . . + an xn ,a0 , . .
. , an ∈ k îò x ñ êîýôôèöèåíòàìè èç k.k(x) ïîëå ðàöèîíàëüíûõ ôóíêöèé íàä k.8 / 225Ïðèêëàäíàÿ àëãåáðà8 / 225Ïîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÌîæåò ëè áåñêîíå÷íîå ïîëå èìåòü ïîëîæèòåëüíóþõàðàêòåðèñòèêó?k ïðîèçâîëüíîå (êîíå÷íîå èëè áåñêîíå÷íîå) ïîëå. Ïîñòðîèì:12k[x] ìíîæåñòâî ìíîãî÷ëåíîâ P (x) = a0 + a1 x + . .
. + an xn ,a0 , . . . , an ∈ k îò x ñ êîýôôèöèåíòàìè èç k.k(x) ïîëå ðàöèîíàëüíûõ ôóíêöèé íàä k.  í¼ìÝëåìåíòû äðîáè P/Q (åñëè Q 6= 0), ãäå P, Q ∈ k[x].Óìíîæåíèå P/Q · U/V = (P U )/(QV ).Ýêâèâàëåíòíîñòü P1 /Q1 = P2 /Q2 , åñëè P1 Q2 = P2 Q1 .Ñëîæåíèå äðîáè ìîæíî ïðèâîäèòü ê îáùåìó çíàìåíàòåëþè ñêëàäûâàòü:P/Q+U/v = (P V )/(QV )+(QU )/(QV ) = (P V +QU )/(QV ).Âêëþ÷åíèå Ïîñêîëüêó k[x] ⊂ k(x), òî êàæäûé ìíîãî÷ëåíP îòîæäåñòâëÿåòñÿ ñ P/1.Ïðèêëàäíàÿ àëãåáðà8 / 225Ïîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÌîæåò ëè áåñêîíå÷íîå ïîëå èìåòü ïîëîæèòåëüíóþõàðàêòåðèñòèêó?k ïðîèçâîëüíîå (êîíå÷íîå èëè áåñêîíå÷íîå) ïîëå.
Ïîñòðîèì:12k[x] ìíîæåñòâî ìíîãî÷ëåíîâ P (x) = a0 + a1 x + . . . + an xn ,a0 , . . . , an ∈ k îò x ñ êîýôôèöèåíòàìè èç k.k(x) ïîëå ðàöèîíàëüíûõ ôóíêöèé íàä k.  í¼ìÝëåìåíòû äðîáè P/Q (åñëè Q 6= 0), ãäå P, Q ∈ k[x].Óìíîæåíèå P/Q · U/V = (P U )/(QV ).Ýêâèâàëåíòíîñòü P1 /Q1 = P2 /Q2 , åñëè P1 Q2 = P2 Q1 .Ñëîæåíèå äðîáè ìîæíî ïðèâîäèòü ê îáùåìó çíàìåíàòåëþè ñêëàäûâàòü:P/Q+U/v = (P V )/(QV )+(QU )/(QV ) = (P V +QU )/(QV ).Âêëþ÷åíèå Ïîñêîëüêó k[x] ⊂ k(x), òî êàæäûé ìíîãî÷ëåíP îòîæäåñòâëÿåòñÿ ñ P/1.Åñëè â êà÷åñòâå k âçÿòü êîíå÷íîå ïîëåáåñêîíå÷íîå ïîëå ñ õàðàêòåðèñòèêîé p.Fp , òî Fp (x) Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÐàçäåë I1Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏîñòðîåíèå ïîëåé ÃàëóàËèíåéíàÿ àëãåáðà íàä êîíå÷íûì ïîëåìÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåì2Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èç pnýëåìåíòîâÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÇàäà÷è3Êîäû, èñïðàâëÿþùèå îøèáêèÎñíîâíàÿ çàäà÷à òåîðèè êîäèðîâàíèÿÖèêëè÷åñêèå êîäû9 / 225Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÐàçäåë IIÊîäû Á×Õ4Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿêîìáèíàòîðíûõ çàäà÷5×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎïåðàöèè íàä ÷.ó.
ìíîæåñòâàìèËèíåàðèçàöèÿ6Àëãåáðàè÷åñêèå ðåø¼òêèÐåø¼òêè10 / 225Ïðèêëàäíàÿ àëãåáðà11 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÑèëüíîå óïðîùåíèå âû÷èñëåíèé â ïîëå ïîëîæèòåëüíîéõàðàêòåðèñòèêèËåììà ïîëå õàðàêòåðèñòèêè p > 0 âûïîëíåíî òîæäåñòâî(a + b)p = ap + bp .Ïðèêëàäíàÿ àëãåáðà11 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÑèëüíîå óïðîùåíèå âû÷èñëåíèé â ïîëå ïîëîæèòåëüíîéõàðàêòåðèñòèêèËåììà ïîëå õàðàêòåðèñòèêè p > 0 âûïîëíåíî òîæäåñòâî(a + b)p = ap + bp .Äîêàçàòåëüñòâî ëþáîì êîììóòàòèâíîì êîëüöå âåðíà ôîðìóëà äëÿ áèíîìà(a + b)p = ap + Cp1 ap−1 b + .
. . + Cpp−1 abp−1 + bp .Íî ïðè i = 1, . . . , p − 1 ÷èñëèòåëü Cpi =çíàìåíàòåëü íåò, ∴ Cpi ≡p 0.p!i!(p−i)!äåëÿòñÿ íà p, àÏðèêëàäíàÿ àëãåáðà11 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÑèëüíîå óïðîùåíèå âû÷èñëåíèé â ïîëå ïîëîæèòåëüíîéõàðàêòåðèñòèêèËåììà ïîëå õàðàêòåðèñòèêè p > 0 âûïîëíåíî òîæäåñòâî(a + b)p = ap + bp .Äîêàçàòåëüñòâî ëþáîì êîììóòàòèâíîì êîëüöå âåðíà ôîðìóëà äëÿ áèíîìà(a + b)p = ap + Cp1 ap−1 b + .
. . + Cpp−1 abp−1 + bp .Íî ïðè i = 1, . . . , p − 1 ÷èñëèòåëü Cpi =çíàìåíàòåëü íåò, ∴ Cpi ≡p 0.p!i!(p−i)!äåëÿòñÿ íà p, àÑëåäñòâèånnn ïîëå õàðàêòåðèñòèêè p > 0 ñïðàâåäëèâî (a + b)p = ap + bp .Ïðèêëàäíàÿ àëãåáðà12 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÌóëüòïëèêàòèâíàÿ ãðóïïà è ïðèìèòèâíûé ýëåìåíò ïîëÿF∗pFp= Fp r {0} = { 1, . . . , p − 1 } ìóëüòïëèêàòèâíàÿ ãðóïïàïîëÿ Fp .defÏðèêëàäíàÿ àëãåáðà12 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÌóëüòïëèêàòèâíàÿ ãðóïïà è ïðèìèòèâíûé ýëåìåíò ïîëÿF∗pFp= Fp r {0} = { 1, . . .
, p − 1 } ìóëüòïëèêàòèâíàÿ ãðóïïàïîëÿ Fp .defÓòâåðæäåíèåF∗p öèêëè÷åñêàÿ ãðóïïà ïîðÿäêà p − 1 ïî óìíîæåíèþ.Ïðèêëàäíàÿ àëãåáðà12 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÌóëüòïëèêàòèâíàÿ ãðóïïà è ïðèìèòèâíûé ýëåìåíò ïîëÿF∗pFp= Fp r {0} = { 1, . . . , p − 1 } ìóëüòïëèêàòèâíàÿ ãðóïïàïîëÿ Fp .defÓòâåðæäåíèåF∗p öèêëè÷åñêàÿ ãðóïïà ïîðÿäêà p − 1 ïî óìíîæåíèþ.F∗p ñîäåðæèò ïðèìèòèâíûé ýëåìåíò α ïîðÿäîê α ðàâåí p − 1, ò.å.αp−1 = 1 è αi 6= 1 äëÿ 0 < i < p − 1.ëþáîé íåíóëåâîé ýëåìåíò β ∈ F∗p ÿâëÿåòñÿ íåêîòîðîé ñòåïåíüþïðèìèòèâíîãî ýëåìåíòà: β = αi , i = 0, 1, . .
. , q − 1.Ïðèêëàäíàÿ àëãåáðà12 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÌóëüòïëèêàòèâíàÿ ãðóïïà è ïðèìèòèâíûé ýëåìåíò ïîëÿF∗pFp= Fp r {0} = { 1, . . . , p − 1 } ìóëüòïëèêàòèâíàÿ ãðóïïàïîëÿ Fp .defÓòâåðæäåíèåF∗p öèêëè÷åñêàÿ ãðóïïà ïîðÿäêà p − 1 ïî óìíîæåíèþ.F∗p ñîäåðæèò ïðèìèòèâíûé ýëåìåíò α ïîðÿäîê α ðàâåí p − 1, ò.å.αp−1 = 1 è αi 6= 1 äëÿ 0 < i < p − 1.ëþáîé íåíóëåâîé ýëåìåíò β ∈ F∗p ÿâëÿåòñÿ íåêîòîðîé ñòåïåíüþïðèìèòèâíîãî ýëåìåíòà: β = αi , i = 0, 1, .
. . , q − 1.ÓòâåðæäåíèåÃðóïïàF∗p èìååò ϕ(p − 1) ïðèìèòèâíûõ ýëåìåíòîâ.Ïðèêëàäíàÿ àëãåáðà13 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÔóíêöèÿ Ýéëåðàϕ(n) ôóíêöèÿ Ýéëåðà ò.å. êîëè÷åñòâî ÷èñåë ðÿäà èçèíòåðâàëà [ 1, . . . , n − 1 ], âçàèìíî ïðîñòûõ ñ n:ϕ(1) = 1 (ïî îïðåäåëåíèþ), ϕ(2) = 1, ϕ(3) = ϕ(4) = 2,ϕ(5) = 4, ϕ(6) = |{1, 5}| = 2, . . .Ïðèêëàäíàÿ àëãåáðà13 / 225Ïîëÿ Ãàëóà - IÏîñòðîåíèå ïîëåé ÃàëóàÔóíêöèÿ Ýéëåðàϕ(n) ôóíêöèÿ Ýéëåðà ò.å. êîëè÷åñòâî ÷èñåë ðÿäà èçèíòåðâàëà [ 1, . . . , n − 1 ], âçàèìíî ïðîñòûõ ñ n:ϕ(1) = 1 (ïî îïðåäåëåíèþ), ϕ(2) = 1, ϕ(3) = ϕ(4) = 2,ϕ(5) = 4, ϕ(6) = |{1, 5}| = 2, .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
