Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.msu.ru/projects/presentation/ryabov.doc Äàòà èçìåíåíèÿ: Wed Jul 2 10:26:33 2008 Äàòà èíäåêñèðîâàíèÿ: Tue Oct 2 08:57:38 2012 Êîäèðîâêà: koi8-r

Î ïóòåâîì êîäèðîâàíèè k-ãðàíåé â n-êóáå.
Ã.Ã.Ðÿáîâ (ÍÈÂÖ ÌÃÓ)
Äåòàëüíîå ìîäåëèðîâàíèå êðóïíûõ íàó÷íî-òåõíè÷åñêèõ ïðîåêòîâ íà
ñóïåðêîìïüþòåðíûõ ñèñòåìàõ ñòàëî íåîáõîäèìûì òåõíîëîãè÷åñêèì ýòàïîì
ðàçðàáîòîê. Âû÷èñëèòåëüíàÿ ñðåäà äëÿ òàêîãî ìîäåëèðîâàíèÿ â âèäå ñåòîê,
ðåøåòîê, êîìïëåêñîâ â íàñòîÿùåå âðåìÿ ñîñòàâëÿåò 108-109 êîíå÷íûõ ýëåìåíòîâ
(â òðåõìåðíîì ñëó÷àå). Íåñìîòðÿ íà ñóùåñòâåííîå ðàçëè÷èå îáëàñòåé, â
êîòîðûõ èñïîëüçóåòñÿ ïîäîáíàÿ ñðåäà (òåîðåòè÷åñêàÿ ôèçèêà,
ãèäðîàýðîäèíàìèêà, êîìïüþòåðíîå çðåíèå è äð.) îò÷åòëèâî ïðîñëåæèâàþòñÿ
òåíäåíöèè:
1.Óâåëè÷åíèå îáúåìîâ ñðåäû-1010-1012 êîíå÷íûõ ýëåìåíòîâ.
2.Ó÷åò ðàçíîîáðàçíûõ ãåîìåòðèêî-òîïîëîãè÷åñêèõ îñîáåííîñòåé â ñòðóêòóðå
ýòîé ñðåäû .
3.Íåîáõîäèìîñòü îïåðàòèâíîé ïåðåñòðîéêè ñòðóêòóðû ñðåäû â ïðîöåññå
ìîäåëèðîâàíèÿ.
Ïðîãðåññ â ýòîé îáëàñòè ÷àùå âñåãî ñâÿçûâàþò ñ íàðàùèâàíèåì òåõíè÷åñêèõ
ñðåäñòâ â âèäå òûñÿ÷ è äàæå ìèëëèîíîâ ìèêðîïðîöåññîðîâ â êëàñòåðíûõ
ñèñòåìàõ. Ìåíåå ïðîðàáîòàíû ìåæäèñöèïëèíàðíûå âîïðîñû âçàèìîäåéñòâèÿ
êîìïüþòåðà ñ îáúåêòàìè êîìáèíàòîðíîé òîïîëîãèè, ãåîìåòðèè ÷èñåë è ãðóïïàìè
ïðåîáðàçîâàíèé.
Äëÿ èññëåäîâàíèÿ îáùèõ âîïðîñîâ ýôôåêòèâíîãî êîäèðîâàíèÿ, ìåòîäîâ õðàíåíèÿ
â ïàìÿòè êîìïüþòåðà, ãåíåðàöèè è ïðåîáðàçîâàíèé ïîäîáíûõ ñòðóêòóð ñ ó÷åòîì
ñèììåòðèé (ïîäîáèé) è ïîòåíöèàëüíîãî ïàðàëëåëèçìà âû÷èñëåíèé â ÍÈÂÖ ÌÃÓ
ðàçðàáàòûâàåòñÿ ýêñïåðèìåíòàëüíàÿ èíñòðóìåíòàëüíàÿ ñèñòåìà ïîä óñëîâíûì
íàçâàíèåì «òîïîëîãè÷åñêèé ïðîöåññîð».
Ìíîãèå êîíñòðóêöèè ïðåäñòàâëåíèÿ òîïîëîãè÷åñêèõ îáúåêòîâ â âèäå
êóáè÷åñêèõ êîìïëåêñîâ ñâÿçàíû ñ îòîáðàæåíèåì â n-ìåðíûé êóá (In). Îïèñàíèÿ
òàêèõ ïîñòðîåíèé ïðàêòè÷åñêè ÿâëÿþòñÿ îñíîâîé äëÿ àëãîðèòìîâ ïðè
êîìïüþòåðíîé ðåàëèçàöèè òàêèõ ïîñòðîåíèé.[3] Êîìáèíàòîðíûé õàðàêòåð
îáúåêòîâ ïðè òàêèõ ïîñòðîåíèÿõ ñóùåñòâåííî ïîâûøàåò çíà÷åíèå ôîðìû
ìàøèííîãî ïðåäñòàâëåíèÿ èíôîðìàöèè î ñòðóêòóðíûõ åäèíèöàõ ðàçëè÷íîé
ðàçìåðíîñòè [5]. Íåêîòîðûì âàðèàíòàì òàêèõ ïðåäñòàâëåíèé îòíîñèòåëüíî In è
ïîñâÿùåí ïðåäëàãàåìûé äîêëàä.
Ïóñòü In-åäèíè÷íûé n-êóá â åâêëèäîâîì ïðîñòðàíñòâå Rn, à âåêòîð
f(In)=(f0,f1,.fn), ãäå fk-÷èñëî ãðàíåé ðàçìåðíîñòè k (k-ãðàíåé). Äëÿ In:

fk= C(n,k) • 2n-k ;ãäå C(n,k)-
÷èñëî ñî÷åòàíèé èç n ïî k; (1)
Îáîçíà÷èì ÷åðåç V(n,k,l)-÷èñëà â ïèðàìèäå Ïàñêàëÿ, êîòîðûå ÿâëÿþòñÿ
òðèíîìèàëüíûìè êîýôôèöèåíòàìè â ðàçëîæåíèè òðèíîìà (x+y+z)n. [2]
Ïîñêîëüêó ìîæíî ïðåäñòàâèòü:

V(n,k,l)=C(n,k)C(n-k,l) ; è
n-k n-
k n-k
? Ñ(n,k)C(n-k,l) =C(n,k) ? C(n-k,l) = C(n,k) 2n-k = ?
V(n,k,l);
l=1
l=1 l=1
è èç (1) cëåäóåò: n-k
fk= ? V(n,k,l);
( 2 )
l=1
Ãåîìåòðè÷åñêàÿ èíòåðïðåòàöèÿ ( 2 ) ïðåäñòàâëåíà íà ðèñ.1
Ñ äðóãîé ñòîðîíû V(n,k,l) - ÷èñëî êðàò÷àéøèõ ïóòåé ïî åäèíè÷íûì ðåáðàì
3d ðåøåòêè èç âåðøèíû ïèðàìèäû ñ äåêàðòîâûìè êîîðäèíàòàìè (0,0,0) â âåðøèíó
ñ êîîðäèíàòàìè (õ,y,z), äëÿ êîòîðûõ âûïîëíåíî:
l=x; k=y; n=x+y+z;
Îòñþäà êàæäîé k-ãðàíè â In ñîîòâåòñòâóåò åäèíñòâåííûé êðàò÷àéøèé ïóòü â 3d-
ðåøåòêå, êîòîðûé ìîæåò áûòü çàêîäèðîâàí òðîè÷íûì êîäîì. Ñóììà âñåõ ÷èñåë â
n-îì ñëîå ïèðàìèäû Ïàñêàëÿ ðàâíà 3n è ñëåäîâàòåëüíî:


n
? fk = 3n;
k=0
Ñëåäóåò çàìåòèòü, ÷òî ïðè ðàññìîòðåíèè ôóíäàìåíòàëüíûõ ñîîòíîøåíèé Äåíà-
Ñîììåðâèëÿ è óðàâíåíèÿ Ýéëåðà îáû÷íî ðàññìàòðèâàåòñÿ f-âåêòîð ñ
êîìïîíåíòàìè (f0,f1,.fn-1).  íàøåì ñëó÷àå âñåãäà fn=1.
Ðàññìîòðèì ìíîæåñòâî âñåõ òðîè÷íûõ n-ðàçðÿäíûõ êîäîâ {a1,a2,.an},ãäå
ai[pic]{0,1,2}. Ïîëîæèì, ÷òî «äâîéêè» ñîîòâåòñòâóþò ðåáðàì, à íîìåð ðàçðÿäà
ñ «äâîéêîé» íîìåðó åäèíè÷íîãî áàçèñíîãî âåêòîðà, êîëëèíåàðíîãî äàííîìó
ðåáðó. ×èñëî äâîåê â êîäå ðàâíî ðàçìåðíîñòè ãðàíè. «Îñòàâøàÿñÿ» ÷àñòü êîäà
èç 0 è 1 ñîîòâåòñòâóåò òðàíñëÿöèè ýòîé ãðàíè èç âåðøèíû (0,0,.0) â
ñîîòâåòñòâóþùóþ âåðøèíó In. Òàê äëÿ I4 êîä 2021 ñîîòâåòñòâóåò äâóìåðíîé
ãðàíè (êâàäðàòó), îáðàçîâàííîãî äåêàðòîâûì ïðîèçâåäåíèåì å2 õ å4 (êâàäðàò ñ
âåðøèíàìè (0000),(1000),(0010),(1010)) è òðàíñëèðîâàííûé â âåðøèíó (0001),
ò.å. èìåþùèì âåðøèíû (0001),(1001),(0011),(1011). (ðèñ.2)
Òðîè÷íûå êîäû, íå ñîäåðæàùèå «äâîåê», ñîîòâåòñòâóþò âåðøèíàì n-êóáà â
òðàäèöèîííîé êîäèðîâêå.

[pic][pic]
Ðèñ1. à).Ïèðàìèäà Ïàñêàëÿ ñî ñëîåì n=4 (ñîîòâåòñòâóåò I4) ; òîëñòîé ëèíèåé
ïîêàçàí êðàò÷àéøèé ïóòü ïî öåëûì òî÷êàì, ñîîòâåòñòâóþùèé 2-ãðàíè ñ êîäîì
2120. b).Ïîëîæåíèå 2-ãðàíåé â I4 ñ êîäàìè 2020, 2021, 2120 è 2121.

Ðàñïîëîæåíèå âñåõ n-ðàçðÿäíûõ òðîè÷íûõ êîäîâ â ïîðÿäêå âîçðàñòàíèÿ
îáðàçóåò âïîëíå óïîðÿäî÷åííîå ìíîæåñòâî êîäîâ k-ãðàíåé In. Òàêîå
êîäèðîâàíèå ìîæíî íàçâàòü ïóòåâûì êîäèðîâàíèåì.
Ëåãêî âèäåòü, ÷òî ïðîñòåéøèå ëîãè÷åñêèå îïåðàöèè íàä ëþáîé ïàðîé òàêèõ
êîäîâ äàþò îòâåò íà âîïðîñû íàëè÷èÿ îáùèõ âåðøèí, ðåáåð è ãðàíåé ðàçíîé
ðàçìåðíîñòè, ÷òî ýôôåêòèâíî ïðè êîìïüþòåðíûõ ïðåäñòàâëåíèÿõ.
Çàìåòèì òàêæå, ÷òî òàêîå êîäèðîâàíèå áîëåå êîìïàêòíî, ÷åì êîäèðîâàíèå k-
ãðàíåé äâîéíûì äâîè÷íûì êîäîì, ãäå ïåðâûé n-ðàçðÿäíûé äâîè÷íûé êîä îòðàæàåò
êàêèì k áàçèñíûì âåêòîðàì êîëëèíåàðíû ðåáðà äàííîé k-ãðàíè (åäèíèöû â
ðàçðÿäàõ êîäà ñîîòâåòñòâóþò íîìåðàì áàçèñíûõ âåêòîðîâ). Âòîðîé n-ðàçðÿäíûé
äâîè÷íûé êîä-êîä òðàíñëÿöèè â ñîîòâåòñòâóþùóþ âåðøèíó n-êóáà. Òàê äëÿ 2-
ãðàíè ñ ïóòåâûì òðîè÷íûì êîäîì 2120 â ýòîì ïðåäñòàâëåíèè áóäåò
ñîîòâåòñòâîâàòü âîñüìèðàçðÿäíûé êîä 10100100. Åñëè ðàñïîëîæèòü â ïîðÿäêå
âîçðàñòàíèÿ âñå 2n-ðàçðÿäíûå êîäû, òî ñðåäè íèõ áóäåò 22n - 3n êîäîâ, íå
ñîîòâåòñòâóþùèõ íèêàêèì k-ãðàíÿì.
Âî ìíîãèõ êîìáèíàòîðíûõ êîíñòðóêöèÿõ èãðàþò ñóùåñòâåííóþ ðîëü òðèàíãóëÿöèè
n-êóáà. Â [1] ðàññìàòðèâàåòñÿ ïðèìèòèâíàÿ òðèàíãóëÿöèÿ, îïðåäåëåííàÿ êàê
ðàçáèåíèå In íà ñèìïëåêñû ðàâíîãî îáúåìà 1/n! Â ñîîòâåòñòâèå êàæäîìó
ñèìïëåêñó èç ÷èñëà n! ñòàâèòñÿ ïîäñòàíîâêà èç ñèììåòðè÷åñêîé ãðóïïû Sn ïî
ñëåäóþùåìó ïðàâèëó.
Ïóñòü èìååòñÿ îðòîíîðìèðîâàííûé áàçèñ â Rn : å1, å2, .ån. Äëÿ
ïîäñòàíîâêè

1 2 3 . n
i1 i2 i3 . in

îïðåäåëèì ïîñëåäîâàòåëüíîñòü îáõîäà âåðøèí n-êóáà, êàê ñîîòâåòñòâóþùóþ
ïîñëåäîâàòåëüíîñòè âåêòîðîâ: ei1, ei1+ei2, ei1+ei2+ei3, .ei1+ei2+ei3+.+ein.
Ïî ìåðå îáõîäà â òàêîì ïîðÿäêå âåðøèí ñòðîÿòñÿ ðåáðà ñèìïëåêñà, ñîåäèíÿÿ
òåêóùóþ âåðøèíó ñî âñåìè ïðåäûäóùèìè â ýòîé ïîñëåäîâàòåëüíîñòè. Òàêîé ìåòîä
ïîñòðîåíèÿ áûë íàçâàí ìåòîäîì ïóòåâûõ ñèìïëåêñîâ. Òàì æå äîêàçûâàåòñÿ, ÷òî
òàê ïåðå÷èñëÿþòñÿ âñå ñèìïëåêñû ïðèìèòèâíîé òðèàíãóëÿöèè è â ýòîé ñâÿçè
êàæäîìó ñèìïëåêñó ïðèìèòèâíîé òðèàíãóëÿöèè ìîæíî ïîñòàâèòü â ñîîòâåòñòâèå
ïåðåñòàíîâêó öåëûõ ÷èñåë îò 1 äî n. Ðàñïîëîæèâ âñå òàêèå ïåðåñòàíîâêè â
ëåêñèêîãðàôè÷åñêîì ïîðÿäêå è ïðèñâîèâ êàæäîé èç íèõ ñîîòâåòñòâóþùèé
ïîðÿäêîâûé íîìåð, â äàëüíåéøåì ìîæíî ñ÷èòàòü ýòîò íîìåð êîäîì
ñîîòâåòñòâóþùåãî ñèìïëåêñà.
Çäåñü óäîáíî âîñïîëüçîâàòüñÿ ôàêòîðèàëüíîé ñèñòåìîé ñ÷èñëåíèÿ [4], êîãäà
÷èñëî s ïðåäñòàâëÿåòñÿ êàê (dm,dm-1,.d1), ãäå dk âçÿòû èç ðàçëîæåíèÿ:
m
s=? dk
k!; (dk ˜ k)

k=1
Òàê äëÿ I4 ÷èñëî ñèìïëåêñîâ â òðèàíãóëÿöèè ðàâíî 24 ,ò.å. äîñòàòî÷íî 5-è
ðàçðÿäíîãî äâîè÷íîãî êîäà. Ïîýòîìó ñèìïëåêñó íà âåðøèíàõ
(0000)(1000)(1010)(1110)(1111) ñîîòâåòñòâóåò ïåðåñòàíîâêà (4231), êîòîðàÿ â
ñâîþ î÷åðåäü èìååò ïîðÿäêîâûé íîìåð 21 (ïåðåñòàíîâêà (1234) èìååò íîìåð 0)
è ñîîòâåòñòâóþùèé äâîè÷íûé êîä 10101 èëè â ôàêòîðèàëüíîé çàïèñè (3,1,1) âî
âïîëíå óïîðÿäî÷åííîé ïîñëåäîâàòåëüíîñòè ñèìïëåêñîâ ïðèìèòèâíîé òðèàíãóëÿöèè
I4. (ðèñ.2) Ôàêòîðèàëüíàÿ çàïèñü óäîáíà äëÿ âîññòàíîâëåíèÿ ïî íåé ñàìîé
ïåðåñòàíîâêè. Òàê ïåðâîå ÷èñëî â ïåðåñòàíîâêå ðàâíî dm+1, íà âòîðîì ìåñòå
dm-1+1-îå ÷èñëî èç îñòàâøèõñÿ, ðàñïîëîæåííûõ ïî ïîðÿäêó, è ò.ä.
[pic][pic]


Ðèñ.2 à). Ïðèìèòèâíàÿ òðèàíãóëÿöèÿ I4 - ïîñòðîåíèå ñèìïëåêñà äëÿ
ïåðåñòàíîâêè 4231 (áîëåå òîëñòûå ëèíèè). b).Ñõåìà âêëàäà ñèìïëåêñîâ â
çâåçäó âåðøèíû (00.0) ñî ñòîðîíû n-êóáîâ, ñîäåðæàùèõ (00.0).

Ïðè êîìïüþòåðíûõ êîìáèíàòîðíî-òîïîëîãè÷åñêèõ ïîñòðîåíèÿõ è ïðåîáðàçîâàíèÿõ
âàæíóþ ðîëü èãðàåò ìàøèííîå ïðåäñòàâëåíèå ñòðóêòóðû çâåçäû âåðøèíû, êàê
ïîëèýäðà.[6].  ñëó÷àå ïðèìèòèâíîé òðèàíãóëÿöèè Rn ïðè çàäàííîì
îðòîíîðìèðîâàííîì áàçèñå, çâåçäà êàæäîé âåðøèíû ïðåäñòàâëÿåò òðàíñëèðóåìûé
ïîëèýäð. Îí îáðàçîâàí êàê ñèìïëèöèàëüíûé êîìïëåêñ, âêëþ÷àþùèé ñèìïëåêñû èç
âñåõ «îêòàíòîâ»(n-êóáîâ), êîòîðûå ñîäåðæàò ýòó âåðøèíó (öåëóþ òî÷êó). ×èñëî
òàêèõ îêòàíòîâ-êóáîâ ðàâíî 2n. Èç êàæäîãî òàêîãî êóáà â ðàññìàòðèâàåìûé
êîìïëåêñ âõîäÿò òîëüêî òå ñèìïëåêñû, êîòîðûå ñîäåðæàò ýòó îáùóþ âåðøèíó ïðè
ðàññìàòðèâàåìîé òðèàíãóëÿöèè. Áóäåì ñ÷èòàòü, ÷òî êàæäîìó èç òàêèõ êóáîâ
ïðèäàíà «ìåñòíàÿ ñèñòåìà êîîðäèíàò»- êîäèðîâêà âåðøèí In. Îáîçíà÷èì ÷èñëî
âåðøèí n-êóáà ñ äëèíîé êðàò÷àéøåãî ïóòè ðàâíîãî k îò âåðøèíû (0.0.0) äî íèõ
÷åðåç W(k), à ÷èñëî ñèìïëåêñîâ ñ îäíîé èç òàêèõ âåðøèí S(k). Èç ìåòîäà
ïóòåâûõ ñèìïëåêñîâ ñëåäóåò:
S(k)=k!(n-k)! ;
Ïîñêîëüêó:
W(k)=C(n,k);

Îáùåå ÷èñëî ñèìïëåêñîâ â çâåçäå:

n n

S =?W(k)S(k)=?Ñ(n,k)
k!(n-k)!=(n+1)! ;

k=0 k=0
Îòñþäà ñëåäóåò âîçìîæíîñòü òàêîãî æå ïðèåìà êîäèðîâàíèÿ äëÿ ñèìïëåêñîâ â
çâåçäå, êàê è äëÿ n-êóáà.
Êðîìå òîãî, îòñþäà æå îáúåì òðàíñëèðóåìîãî çâåçäíîãî ïîëèýäðà äëÿ Rn :


V(Pn)=(n+1)!•1/n!=n+1;



Ëèòåðàòóðà:
1.Steingrimsson E. Permutations Statistics of Indexed and Poset
Permutations. Proc.MIT. 1992
2.Êóçüìèí Î.Â. Òðåóãîëüíèê è ïèðàìèäà Ïàñêàëÿ, ñâîéñòâà è îáîáùåíèÿ. ÑÎÆ.
2000. 35-41
3.Áóõøòàáåð Â.Ì., Ïàíîâ Ò.Å. Òîðè÷åñêèå äåéñòâèÿ â òîïîëîãèè è
êîìáèíàòîðèêå. ÌÖÍÌÎ.2004
4.Ãàøêîâ Ñ.Á. Ñèñòåìû ñ÷èñëåíèÿ è èõ ïðèìåíåíèÿ. ÌÖÍÌÎ.2004
5.Ðÿáîâ Ã.Ã. Àëãîðèòìè÷åñêèå îñíîâû òîïîëîãè÷åñêîãî ïðîöåññîðà
(òîïîêàðòû). Òðóäû êîíô. ÌÑÎ-2005.ÌÃÓ. 53-58.
6.Ryabov G., Serov V. Simplicial-Lattice Model and Metric-Topological
Constructions. Proc. conf. PRIP-2007.v.2. 135-140