Верхние и нижние оценки количества некоторых k-мерных подпространств заданного веса над конечным полем
Запропоновано метод прискореного моделювання, що дозволяє будувати верхні та нижні оцінки кількості k-вимірних підпросторів довільної ваги ω n-вимірного векторного простору над полем Галуа, що містить q елементів. Точність оцінок ілюструють чисельні приклади. A fast simulation method enabling to con...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2010 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/45646 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Верхние и нижние оценки количества некоторых -мерных подпространств заданного веса над конечным полем / И.Н. Кузнецов // Кибернетика и системный анализ. — 2010. — № 6. — С. 51–64. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859792912316891136 |
|---|---|
| author | Кузнецов, И.Н. |
| author_facet | Кузнецов, И.Н. |
| citation_txt | Верхние и нижние оценки количества некоторых -мерных подпространств заданного веса над конечным полем / И.Н. Кузнецов // Кибернетика и системный анализ. — 2010. — № 6. — С. 51–64. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Запропоновано метод прискореного моделювання, що дозволяє будувати верхні та нижні оцінки кількості k-вимірних підпросторів довільної ваги ω n-вимірного векторного простору над полем Галуа, що містить q елементів. Точність оцінок ілюструють чисельні приклади.
A fast simulation method enabling to construct upper and lower estimates for the number of k-measurable subspaces of an arbitrary weight ω of n-measurable vector space over the Galois field containing q components is proposed. Numerical examples demonstrate the accuracy of the estimates.
|
| first_indexed | 2025-12-02T12:10:26Z |
| format | Article |
| fulltext |
ÓÄÊ 519.12
È.Í. ÊÓÇÍÅÖÎÂ
ÂÅÐÕÍÈÅ È ÍÈÆÍÈÅ ÎÖÅÍÊÈ ÊÎËÈ×ÅÑÒÂÀ ÍÅÊÎÒÎÐÛÕ
k-ÌÅÐÍÛÕ ÏÎÄÏÐÎÑÒÐÀÍÑÒÂ ÇÀÄÀÍÍÎÃÎ ÂÅÑÀ
ÍÀÄ ÊÎÍÅ×ÍÛÌ ÏÎËÅÌ
Êëþ÷åâûå ñëîâà: âåêòîðíîå ïðîñòðàíñòâî, ïîëå Ãàëóà, âåñ ïîäïðîñòðàíñòâà,
óñêîðåííîå ìîäåëèðîâàíèå, ìíîãîïðîöåññîðíûé êîìïëåêñ ÑÊÈÒ-3 .
Äàííàÿ ñòàòüÿ ÿâëÿåòñÿ ïðîäîëæåíèåì ðàáîòû [1]. Íàïîìíèì ïîñòàíîâêó çàäà÷è,
íåêîòîðûå îïðåäåëåíèÿ è îáîçíà÷åíèÿ.
Ðàññìàòðèâàåòñÿ n-ìåðíîå âåêòîðíîå ïðîñòðàíñòâî Vn íàä êîíå÷íûì ïîëåì
GF( )q (ïîëå Ãàëóà), ñîäåðæàùèì q ýëåìåíòîâ, ãäå q — ñòåïåíü ïðîñòîãî ÷èñëà.
Èçâåñòíî [2, ñ. 219], ÷òî îáùåå êîëè÷åñòâî ðàçëè÷íûõ k-ìåðíûõ ïîäïðîñòðàíñòâ
Vk n, ïðîñòðàíñòâà Vn ðàâíî
n
k
q
q
k n
n i
k i
i
k
�
��
�
��
�
�
�
1
1
1
0
1
, .
(1)
Âåñîì âåêòîðà v Vn� íàçûâàåòñÿ ÷èñëî îòëè÷íûõ îò íóëÿ êîìïîíåíò ýòîãî âåê-
òîðà. Âåñîì k-ìåðíîãî ïîäïðîñòðàíñòâà Vk n, ïðîñòðàíñòâà Vn íàçûâàåòñÿ ÷èñëî,
ðàâíîå ìèíèìàëüíîìó âåñó âåêòîðà v Vk n� , , îòëè÷íîãî îò íóëåâîãî. ×èñëî k-ìåð-
íûõ ïîäïðîñòðàíñòâ Vk n, ïðîñòðàíñòâà Vn , êàæäîå èç êîòîðûõ èìååò âåñ �, îáîçíà-
÷èì
n
k
�
�
�
�
�
�
� . Èç àëãîðèòìà [3] ïîñòðîåíèÿ ìíîæåñòâà áàçèñíûõ âåêòîðîâ k-ìåðíîãî
ïîäïðîñòðàíñòâà Vk n, ñëåäóåò, ÷òî åãî âåñ íå ìîæåò ïðåâûøàòü n k
1, ïîýòîìó
n
k
n
k
k n
n k�
�
�
�
�
� �
�
�
�
�
�
�
�
�
�
�
1
1
1, . (2)
Îöåíêè êîëè÷åñòâà ïîäïðîñòðàíñòâ Vk n, çàäàííîãî âåñà � ïðåäñòàâëÿþò èíòå-
ðåñ êàê äëÿ çàäà÷ êîäèðîâàíèÿ [4, 5], òàê è äëÿ ðåøåíèÿ ïðîáëåìû çàùèòû èíôîð-
ìàöèè îò íåñàíêöèîíèðîâàííîãî äîñòóïà.
Ñëåäóåò îòìåòèòü ïîëíîå îòñóòñòâèå êàêèõ-ëèáî ðåçóëüòàòîâ, ïîçâîëÿþùèõ
âû÷èñëÿòü èëè îöåíèâàòü
n
k
�
�
�
�
�
�
� äëÿ ïðîèçâîëüíûõ çíà÷åíèé n k, è �. Èìåþòñÿ
ëèøü ÷àñòíûå ðåçóëüòàòû. Òàê, â [6, 7] ïðèâåäåíû ðåêóððåíòíûå ôîðìóëû âû÷èñëå-
íèÿ
n
k
�
�
�
�
�
�
� ïðè � �1 è � � 2 . Â [1] ïðåäëîæåí ïðèíöèïèàëüíî íîâûé ïîäõîä, îñíî-
âàííûé íà óñêîðåííîì ìîäåëèðîâàíèè ìàëûõ âåðîÿòíîñòåé. Â åãî îñíîâå ëåæèò
èäåÿ È.Í. Êîâàëåíêî [8–10] î ðàçëîæåíèè èñêîìîé õàðàêòåðèñòèêè ïî ñòåïåíÿì íå-
êîòîðîãî ïàðàìåòðà. Â òåîðèè íàäåæíîñòè òàêîé ïîäõîä áûë ìíîãîêðàòíî óñïåøíî
èñïîëüçîâàí äëÿ ïîâûøåíèÿ òî÷íîñòè âû÷èñëåíèé. Îöåíèâàåìàÿ õàðàêòåðèñòèêà
ðàñêëàäûâàëàñü â ðÿä ïî ñòåïåíÿì ìàëîãî ïàðàìåòðà (àíàëèòè÷åñêàÿ ÷àñòü), à êîýô-
ôèöèåíòû ýòîãî ðÿäà îöåíèâàëèñü ìåòîäîì Ìîíòå-Êàðëî (ñòàòèñòè÷åñêàÿ ÷àñòü).
Âûäåëåíèå ìàëîãî ïàðàìåòðà ïîçâîëÿëî ñóùåñòâåííî ïîâûñèòü òî÷íîñòü îöåíîê,
à áûñòðàÿ ñõîäèìîñòü ðÿäà ñïîñîáñòâîâàëà ïîâûøåíèþ ýôôåêòèâíîñòè âû÷èñëå-
íèé.  îòëè÷èå îò çàäà÷ òåîðèè íàäåæíîñòè â [1] ïðåäëîæåíî ðàçëîæèòü
n
k
�
�
�
�
�
�
� ïî
ñòåïåíÿì áîëüøîãî ïàðàìåòðà q (òèïè÷íûå çíà÷åíèÿ q � 28 , q � 216 è âûøå). Ìåòîä
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 51
© È.Í. Êóçíåöîâ, 2010
óñêîðåííîãî ìîäåëèðîâàíèÿ ïîçâîëèë ñòðîèòü íåñìåùåííûå îöåíêè äëÿ
n
k
�
�
�
�
�
�
� ïðè
� �1è � � 2, à òàêæå âåðõíèå è íèæíèå îöåíêè ïðè � � 3. Ïðè ýòîì äîêàçàíà îãðàíè-
÷åííîñòü îòíîñèòåëüíîé ñðåäíåêâàäðàòè÷åñêîé ïîãðåøíîñòè îöåíîê ïðè q � � .
 íàñòîÿùåé ñòàòüå ðåçóëüòàòû ðàáîòû [1] îáîáùàþòñÿ äëÿ ïðîèçâîëüíîãî
çíà÷åíèÿ �, à èìåííî, ïðè k �1è k � 2 äëÿ
n
k
�
�
�
�
�
�
� ïðèâåäåíû àíàëèòè÷åñêèå ôîðìó-
ëû â ÿâíîì âèäå, à äëÿ k � 2 ñôîðìóëèðîâàí àëãîðèòì óñêîðåííîãî ìîäåëèðîâàíèÿ,
ïîçâîëÿþùèé ñòðîèòü âåðõíèå è íèæíèå îöåíêè. Òî÷íîñòü îöåíîê èññëåäóåòñÿ íà
÷èñëåííûõ ïðèìåðàõ. Èñïîëüçîâàíèå óñêîðåííîãî ìîäåëèðîâàíèÿ íà ìíîãîïðîöåñ-
ñîðíîì êîìïëåêñå ÑÊÈÒ-3 ïîçâîëèëî ïîëó÷èòü îöåíêè âûñîêîé òî÷íîñòè äëÿ
áîëüøèõ çíà÷åíèé n k, è �.
ÎÁÙÀß ÑÕÅÌÀ ÓÑÊÎÐÅÍÍÎÃÎ ÌÎÄÅËÈÐÎÂÀÍÈß
Äëÿ ïåðå÷èñëåíèÿ âñåõ k-ìåðíûõ ïîäïðîñòðàíñòâ Vk n, âåêòîðíîãî ïðîñòðàíñòâà
Vn êëþ÷åâóþ ðîëü èãðàåò àëãîðèòì [3] ïîñòðîåíèÿ ìíîæåñòâà áàçèñíûõ âåêòîðîâ
ýòîãî ïîäïðîñòðàíñòâà. Äàííûé àëãîðèòì ñâîäèòñÿ ê ïîñòðîåíèþ ìàòðèöû A
ðàçìåðà k n� . Ïóñòü r r rk� ( , , )1 � — k-ìåðíûé âåêòîð, êîìïîíåíòàìè êîòîðîãî
ÿâëÿþòñÿ óïîðÿäî÷åííûå íàòóðàëüíûå ÷èñëà, U r r r r nk�
� � �
{ : }1 1 2 � .
1. Âûáèðàåì ïðîèçâîëüíûé âåêòîð r U� .
2.  ìàòðèöå A ñ k ñòðîêàìè è n ñòîëáöàìè îáðàçóåì åäèíè÷íóþ ìàòðèöó ðàç-
ìåðà k k� , ñòîëáöû êîòîðîé èìåþò íîìåðà, çàäàâàåìûå âåêòîðîì r.
3. Â i-é ñòðîêå ìàòðèöû A ( )1
i k çàïèñûâàåì íóëü âî âñå ïîçèöèè j ri� .
4. Îñòàâøèåñÿ ìåñòà â ìàòðèöå A çàïîëíÿåì ýëåìåíòàìè ïîëÿ íåçàâèñèìûì
îáðàçîì.
Ñòðîêè ïîñòðîåííîé ìàòðèöû A ÿâëÿþòñÿ áàçèñíûìè âåêòîðàìè íåêîòîðîãî
ïîäïðîñòðàíñòâà V Vk n n, � . Ïîýòîìó çàäà÷à íàõîæäåíèÿ êîëè÷åñòâà k-ìåðíûõ ïîä-
ïðîñòðàíñòâ âåñà � ñâîäèòñÿ ê îïðåäåëåíèþ êîëè÷åñòâà ìàòðèö A ñ áàçèñíûìè âåê-
òîðàìè, ëèíåéíàÿ êîìáèíàöèÿ êîòîðûõ äàåò âîçìîæíîñòü ïîñòðîèòü âåêòîð, ñîäåð-
æàùèé ðîâíî � íåíóëåâûõ êîìïîíåíò, è â òî æå âðåìÿ íå ñóùåñòâóåò ëèíåéíîé
êîìáèíàöèè áàçèñíûõ âåêòîðîâ ñ ìåíüøèì ÷èñëîì íåíóëåâûõ êîìïîíåíò.
Îáîçíà÷èì:
n
k
r�;
�
�
�
�
�
� — êîëè÷åñòâî k-ìåðíûõ ïîäïðîñòðàíñòâ âåñà � ïðè ôèêñèðîâàííîì
âåêòîðå r U� ;
U L r U r r r r k Lk� �( ) { : , ( ) ( ) ( ) }� � �
�1 2 32 3 � ,
( )( ) ( )( )k L k n k
1 1 1� ;
| ( )|U L� — ÷èñëî ýëåìåíòîâ âî ìíîæåñòâå U L� ( ) .
 ðàáîòå [1] äîêàçàíî ñîîòíîøåíèå
n
k
Z c� � �� � � �
�
�
�
�
�
� � M M{ ( ) | }, (3)
ãäå
Z U L qL
L k
k n k
� �
�
�
�
�
� | ( )|
( )( )
( )( )
1
1 1
1
, c r
q
n
k
r
L� �
�( ) ;�
�
�
�
�
�
�
1
1
,
(4)
ìàòåìàòè÷åñêîå îæèäàíèå M� áåðåòñÿ ïî ðàñïðåäåëåíèþ ñëó÷àéíîé âåëè÷è-
íû �, ïðèíèìàþùåé çíà÷åíèå L k k n k� {( )( ), , ( )( )}1 1 1� � ñ âåðîÿòíîñòüþ
1 1
Z
U L qL
�
�
�| ( )|
; ïðè ôèêñèðîâàííîì � � L ñëó÷àéíûé âåêòîð � L èìååò ðàâíî-
ìåðíîå ðàñïðåäåëåíèå íà ìíîæåñòâå U L� ( ) .
52 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 53
Ôîðìóëà (3) — òèïè÷íûé ïðèìåð èñïîëüçîâàíèÿ ìåòîäà ñóùåñòâåííîé âûáîð-
êè. Ðàçëîæåíèå ïî ñòåïåíÿì q (ñì. àëãîðèòì ìîäåëèðîâàíèÿ ñëó÷àéíîé âåëè÷èíû �)
ïîçâîëÿåò ðàíæèðîâàòü ñëàãàåìûå â ñîîòâåòñòâèè ñ èõ «âåñîì». Ïðè ýòîì êîýôôè-
öèåíò c r� ( ) ðàâíîìåðíî îãðàíè÷åí äëÿ ëþáûõ çíà÷åíèé r , � è q. Ðåêóððåíòíûå
ôîðìóëû äëÿ âû÷èñëåíèÿ | ( )|U L� ïðèâåäåíû â [1]. Ïðîáëåìà îöåíêè c r� ( ) äëÿ ïðî-
èçâîëüíûõ çíà÷åíèé n k r, , è � ñóùåñòâåííî áîëåå ñëîæíàÿ. Èìåííî ýòîìó âîïðîñó
óäåëÿåòñÿ îñíîâíîå âíèìàíèå â äàííîé ñòàòüå.
Åñëè ïðåäïîëîæèòü, ÷òî èçâåñòåí êàêîé-ëèáî ñïîñîá âû÷èñëåíèÿ êîýôôèöèåí-
òà c r� ( ) ïðè ëþáûõ çíà÷åíèÿõ ïàðàìåòðîâ n k r, , ,� è L , òî èç ñîîòíîøåíèé (3), (4)
ñëåäóåò ïðîñòîé àëãîðèòì ïîñòðîåíèÿ íåñìåùåííûõ îöåíîê äëÿ
n
k
�
�
�
�
�
�
� .
1. Ñ ïîìîùüþ ðåêóððåíòíîãî àëãîðèòìà [1] âû÷èñëÿåì | ( )|U L� äëÿ âñåõ
L k k n k� ( ), ( ), , ( ), ( )1 1 1� � .
2. Ñîãëàñíî (4) âû÷èñëÿåì Z� .
3. Ñòðîèì ðåàëèçàöèþ ñëó÷àéíîé âåëè÷èíû �, êîòîðàÿ ðàâíà L k� �{( )1
� ( ), , ( )( )}� 1 1� k n k ñ âåðîÿòíîñòüþ
| ( )|U L q
Z
L
�
�
�
1
. Ïóñòü � � L .
4. Ñòðîèì ðåàëèçàöèþ ñëó÷àéíîãî âåêòîðà �L , èìåþùåãî ðàâíîìåðíîå ðàñïðå-
äåëåíèå íà ìíîæåñòâå U L� ( ) . Ïóñòü � L r� .
5. Âû÷èñëÿåì c r� ( ) .
6.  êà÷åñòâå îöåíêè äëÿ
n
k
�
�
�
�
�
�
� , ïîñòðîåííîé â îäíîé ðåàëèçàöèè àëãîðèòìà,
âûáèðàåì � ( , ) ( )�� � �n k Z c r� .
Çàìå÷àíèÿ. 1. Ïðè ôèêñèðîâàííîì � âû÷èñëåíèå Z� (ïåðâûå äâà øàãà àëãî-
ðèòìà) ïðîâîäèòñÿ îäèí ðàç.
2. Íåñìåùåííîñòü îöåíêè � ( , )�� n k âûòåêàåò íåïîñðåäñòâåííî èç ôîðìóë (3), (4).
Ïóñòü r r rk� ( , , )1 � — âåêòîð, îïðåäåëÿþùèé íîìåðà ñòîëáöîâ, îáðàçóþùèõ
åäèíè÷íóþ ìàòðèöó â ìàòðèöå A. Äàëüíåéøèå ðàññóæäåíèÿ ïðîâîäÿòñÿ ïðè ôèêñè-
ðîâàííîì r. Êîëè÷åñòâî ïîçèöèé â i-é ñòðîêå ( , , )i k�1 � , äîñòóïíûõ äëÿ çàïîëíå-
íèÿ ýëåìåíòàìè ïîëÿ, ðàâíî r i r ii i � 1 1( ) . Î÷åâèäíî, ÷òî r i r ji j
ïðè i j� .
 äàëüíåéøåì èñêëþ÷èì èç ðàññìîòðåíèÿ ñòîëáöû ìàòðèöû A ñ íîìåðàìè, çàäàâà-
åìûìè âåêòîðîì r, à òàêæå ñòîëáöû ñ íîìåðàìè j rk� .  ðåçóëüòàòå ïîëó÷èì ïðÿ-
ìîóãîëüíóþ ìàòðèöó B b
ij
� ( ) ðàçìåðà k r kk� ( ) òàêóþ, ÷òî bij � 0 ïðè j r ii� ; íà
âñåõ îñòàëüíûõ ïîçèöèÿõ ( , )i j ìîæåò ðàçìåùàòüñÿ îäèí èç q ýëåìåíòîâ ïîëÿ. Åñëè
N r( ) — îáùåå êîëè÷åñòâî âàðèàíòîâ ðàçìåùåíèÿ ýëåìåíòîâ ïîëÿ â ìàòðèöå B, òî
N r q q
r i
i
k r i
i
i
i
k
( )
( )
� �
�
�
� �
1
1 . (5)
Îáîçíà÷èì Y r� ( ) ñîáûòèå, ñîñòîÿùåå â òîì, ÷òî ïðè ñëó÷àéíîì ðàâíîâåðîÿò-
íîì âûáîðå b j r iij i,
, ñîîòâåòñòâóþùèå ñòðîêè ìàòðèöû A îáðàçóþò áàçèñ
k-ìåðíîãî âåêòîðíîãî ïîäïðîñòðàíñòâà âåñà �. Òîãäà
n
k
r N r Y r� �; ( ) { ( )}
�
�
�
�
�
� � P . (6)
Ïîñêîëüêó L r ii
i
k
�
�
� ( )
2
, èç ôîðìóë (4)–(6) ñëåäóåò
c r
q
n
k
r
N r
q
Y r q
L L
r
� � � �
��( ) ;
( )
{ ( )}�
�
�
�
�
�
� � �
1
1 1
1P P{ ( )}Y r� . (7)
 äàëüíåéøåì ñîñðåäîòî÷èì âíèìàíèå íà îöåíêàõ âåðîÿòíîñòè P{ ( )}Y r� .
ÂÑÏÎÌÎÃÀÒÅËÜÍÛÉ ÀËÃÎÐÈÒÌ
 íàñòîÿùåì ðàçäåëå èçëîæåí âñïîìîãàòåëüíûé àëãîðèòì, ëåæàùèé â îñíîâå ïî-
ñòðîåíèÿ âåðõíèõ è íèæíèõ îöåíîê âåðîÿòíîñòè P{ ( )}Y r� .
Ðàññìîòðèì ïîëå Ãàëóà ñ s íåíóëåâûìè ýëåìåíòàìè. Ïóñòü x — ôèêñèðîâàí-
íûé m-ìåðíûé âåêòîð, êîìïîíåíòàìè êîòîðîãî ÿâëÿþòñÿ íåíóëåâûå ýëåìåíòû ýòî-
ãî ïîëÿ. Îáîçíà÷èì � �m s( ) ( , )1 ÷èñëî âåêòîðîâ y, îáëàäàþùèõ äâóìÿ ñâîéñòâàìè: ñó-
ùåñòâóåò ýëåìåíò ïîëÿ Ãàëóà � � 0 òàêîé, ÷òî âåêòîð x y
� ñîäåðæèò ðîâíî � íåíó-
ëåâûõ êîìïîíåíò (âåñ ëèíåéíîé êîìáèíàöèè x è y ðàâåí �); äëÿ âñåõ � �� âåêòîð
x y
� ñîäåðæèò íå ìåíåå � íåíóëåâûõ êîìïîíåíò. Èíà÷å ãîâîðÿ, ìèíèìàëüíûé âåñ
âåêòîðîâ x y
� ðàâåí �. Êðîìå òîãî, îáîçíà÷èì
� � � � � � �m m m ms s s m s( ) ( ) ( ) ( )( , ) ( , ) ( , ) ( , ),0 1 1 11 1�
� 0 1
� m . (8)
Ëåììà. Ïðè � � m 1 ñïðàâåäëèâû ðåêóððåíòíûå ñîîòíîøåíèÿ:
� � � �
� �
m m j s
j
j
s s
m
m m j m
C( ) ( )( , ) ( , )
!
[( ) !] [ ( )]!
0 0 1�
�
�
��
�
��
�
1
m
m
jc m s
�
�( , , ) , (9)
� �
� �
�
m j s
j
j
m
m
s
m
m m j m
C( ) ( , )
!
[( ) !] [ ( )]!
1
1
�
�
�
��
�
��
� c m sj ( , , )� , (10)
ãäå
c m s
s j
s j s jj
m j
m
m j
( , , )
,
( ) ,
( ) ( ),
(
( )
( )
( )
( )
�
�
��
�
�
1
0 m j m s j
m j
�
�
�
�
�
�
�
�
� �
�
( ) ( ) , ),
( ) ,
� 1
0
0
åñëè
åñëè m j m
m j m
m j m
� �
� �
� �
( ) ,
( ) ,
( ) ,
�
�
�
åñëè
åñëè
m j m j m� � ( ) ( )� .
Íà÷àëüíûå óñëîâèÿ: � �m s( ) ( , )0 0� , åñëè � � m èëè s � 0 ; �m m s( ) ( , )0 1 0 � , åñëè
s m� ;
� �m m
j
m
m s m s s j s m( ) ( )( , ) ( , ) ( ),0 1
1
1 1 1 � �
�
�
� . (11)
Äîêàçàòåëüñòâî. Ñëó÷àé � � m 1(ñì. ôîðìóëó (11)) ÿâëÿåòñÿ ñàìûì ïðîñòûì.
Äåéñòâèòåëüíî, ïåðâàÿ êîìïîíåíòà âåêòîðà y ìîæåò ïðèíèìàòü ëþáîå èç s çíà÷å-
íèé, âòîðàÿ êîìïîíåíòà ïî î÷åâèäíûì ïðè÷èíàì ìîæåò ïðèíèìàòü íà îäíî çíà÷å-
íèå ìåíüøå (èíà÷å âåñ ëèíåéíîé êîìáèíàöèè îïóñòèòñÿ íèæå, ÷åì m 1).
Àíàëîãè÷íî, òðåòüÿ êîìïîíåíòà ìîæåò ïðèíèìàòü íà äâà çíà÷åíèÿ ìåíüøå, è ò.ä.
Èç (8) âûòåêàåò, ÷òî ïðè � � m 1
� � � � � �m m ms s s( ) ( ) ( )( , ) ( , ) ( , )0 0 11�
. (12)
Ïîýòîìó äîñòàòî÷íî äîêàçàòü ðàâåíñòâî (10); ñîîòíîøåíèå (9) ñëåäóåò èç (10) è (12).
Ðàâåíñòâî (10) âûòåêàåò èç ñëåäóþùèõ ñîîáðàæåíèé. Âåêòîð x y
� ñîäåðæèò
ðîâíî � íåíóëåâûõ êîìïîíåíò ëèøü â ñëó÷àå, êîãäà äëÿ íåêîòîðîãî � � 0 ñóùåñòâó-
åò ãðóïïà èç m � êîìïîíåíò âåêòîðà y, óäîâëåòâîðÿþùèõ ñîîòíîøåíèÿì
x yi il l
�� 0 , l m� 1, ,� � . Òàêèõ ãðóïï ìîæåò áûòü íå áîëåå ÷åì
m
m
�
��
�
���
. Ðàñ-
ñìîòðèì ñëó÷àé, êîãäà âåêòîð y ñîäåðæèò ðîâíî j ãðóïï êîìïîíåíò, óäîâëåòâîðÿþ-
ùèõ óêàçàííîìó ñâîéñòâó. Èç ïðàâèë êîìáèíàòîðèêè ñëåäóåò, ÷òî ÷èñëî ñïîñîáîâ,
êîòîðûìè âåêòîð èç m ýëåìåíòîâ ìîæíî ðàçáèòü íà j ãðóïï èç m � ýëåìåíòîâ è
54 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 55
îäíó ãðóïïó èç m m j m� � ( )� ýëåìåíòîâ, ðàâíî
C m m m
m
m m
m j
( , , , )
!
[( )!] !
� �
�
� �
�
� .
Ïðè ýòîì j ãðóïïàì â êà÷åñòâå ñîîòâåòñòâóþùèõ êîýôôèöèåíòîâ { }� j äîëæíû
áûòü âûäåëåíû j ïîïàðíî ðàçëè÷íûõ ýëåìåíòîâ ïîëÿ Ãàëóà (÷òî ìîæíî ñäåëàòü Cs
j
ñïîñîáàìè). Êîýôôèöèåíò c m sj ( , , )� îïðåäåëÿåò ÷èñëî m �-ìåðíûõ âåêòîðîâ y � òà-
êèõ, ÷òî äëÿ ëþáîãî íåíóëåâîãî ýëåìåíòà � ïîëÿ Ãàëóà, ïðèíèìàþùåãî s j çíà÷å-
íèé, âåñ ëèíåéíîé êîìáèíàöèè �
�x y� áóäåò áîëüøå, ÷åì � m m( )� . Çäåñü x � —
m �-ìåðíûé âåêòîð, ïîëó÷àåìûé èç x èñêëþ÷åíèåì êîìïîíåíò èç j óêàçàííûõ ãðóïï.
Åñëè m � � 0, òî c m sj ( , , )� �1 . Åñëè 0 � � � m m �, òî êîìïîíåíòû âåêòîðà �y ìîãóò
ïðèíèìàòü ëþáûå çíà÷åíèÿ, çà èñêëþ÷åíèåì j ôèêñèðîâàííûõ çíà÷åíèé, ò.å.
c m s s jj
m( , , ) ( )� � �. Åñëè m m� � �, òî èç âñåõ âîçìîæíûõ êîìáèíàöèé íàäî èñ-
êëþ÷èòü òå ñëó÷àè, êîãäà âñå êîìïîíåíòû âåêòîðà �y îòëè÷àþòñÿ îò ñîîòâåòñòâóþ-
ùèõ êîìïîíåíò âåêòîðà x � íà îäèí è òîò æå ìíîæèòåëü ( s j âîçìîæíûõ çíà÷åíèé).
Ïîýòîìó c m s s j s jj
m( , , ) ( ) ( )� � � . Ïóñòü m m� � �.  ýòîì ñëó÷àå çàäà÷à ñâî-
äèòñÿ ê îïðåäåëåíèþ êîëè÷åñòâà âåêòîðîâ �y òàêèõ, ÷òî âåñ ëþáîé ëèíåéíîé êîì-
áèíàöèè x y�
�� áóäåò íå ìåíüøå, ÷åì � �� � �
m m( ) 1 . Ïîýòîìó
c m s sj m
( , , ) ( , )( )� � �� � �
�
0 , ãäå s s j� � . Ïðîñóììèðîâàâ ïî âñåì âîçìîæíûì çíà÷å-
íèÿì j (ñîîòâåòñòâóþùèå ìíîæåñòâà âåêòîðîâ y íå ïåðåñåêàþòñÿ), ïîëó÷èì ôîðìó-
ëó (10). Ëåììà äîêàçàíà.
ÍÀÕÎÆÄÅÍÈÅ
n
k
�
�
�
�
�
�
� ÏÐÈ k �1 2,
Äëÿ ïðîñòåéøèõ ñëó÷àåâ k �1 è k � 2 çíà÷åíèå
n
k
�
�
�
�
�
�
� ìîæåò áûòü íàéäåíî â ÿâ-
íîì âèäå.
Òåîðåìà 1. Ñïðàâåäëèâû ñëåäóþùèå ðàâåíñòâà:
n
q C
r
r
n
1
1 1
1
1� � �
�
�
�
�
�
�
� �
�
�( ) , (13)
n
C q
r
l l
l
r
r r
n
r
2
1
1
1
2 11
1
1
1
1
�
��
�
�
�
�
�
� �
�
�
�
��
�
�
�
�� ( )
n
l
s
r l
s s
s s S l
C C q l s s
�
� �
1
2 1 2
1
2
2 2
1 2
1( ) ( , , )
( , ) ( )
�
�C q C C q l s s
r
l l
l
r
l
s
r l
s s
1
1
1
2
2 2
1
1
2 1 21 1( ) ( ) ( , ,
�
)
( , ) ( )s s U l1 2 �
�
�
�
�
��
. (14)
Çäåñü
S s s s s r s s( ) {( , ): , , }� � � � �
� 1 0 1 0 1 11 2 1 2 2 1 2 , (15)
S l s s s s s r l l( ) {( , ): , min { , }}, ,�
�
�1 2 1 2 2 21 0 1 2� � � � , r1 1 , (16)
U l s s s s s l s r l l r( ) {( , ): , , }, , ,�
�
�1 2 1 2 1 2 2 10 0 2� � � 1, (17)
� �
� �
( , , ) ( , )( )l s s q
s
s s l
s
1 2
1
2
1
1
1 2
1
1�
�
� , åñëè s s l1 2 2 0
�� , (18)
( , , ) ( )l s s q
s
1 2 1 1� , åñëè s s l1 2 2 0
� , (19)
� �( , , ) ( , )( )l s s s s l q
s1 2
1
1 2
1
2 1�
, åñëè 0 21 2 1
�s s l s� , (20)
( , , )l s s1 2 0� â ïðîòèâíîì ñëó÷àå, (21)
{ ( , )}( )� �
s
q
1
1 1 îïðåäåëÿþòñÿ ñîãëàñíî ðåêóððåíòíûì ôîðìóëàì (9)–(11).
Äîêàçàòåëüñòâî. Ïóñòü k �1. Ñîáûòèå Y r� ( ) íàñòóïàåò òîãäà è òîëüêî òîãäà,
êîãäà åäèíñòâåííàÿ ñòðîêà ìàòðèöû B ñîäåðæèò ðîâíî � 1 íåíóëåâûõ ýëåìåíòîâ.
Ïîýòîìó
P{ }Y r C
q
q qr
r
�
�
� �
( ) �
�
!!
"
#
$$
�
!!
"
#
$$
1
1
1
1
1
1 1
. (22)
Âîñïîëüçîâàâøèñü ñîîòíîøåíèÿìè (5), (6) è (22), ïîëó÷èì ôîðìóëó (13):
n n
r q C
r
n
r
r
n
1 1
11
1
1
1
1 1
� �
�
� �
�
�
�
�
�
�
� �
�
�
�
�
�
� �
�
�
� �; ( ) .
Ñëó÷àé k � 2 ñóùåñòâåííî áîëåå ñëîæåí. Èìååò ìåñòî
n n
r r
r r
n
r
n
2 2
1 2
1
1
2 11
� �
�
�
�
�
�
�
� �
�
�
�
�
�
�
�
�
�� ; , . (23)
Âû÷èñëèì âåðîÿòíîñòü ñîáûòèÿ Y r� ( ) , à äàëåå âîñïîëüçóåìñÿ ôîðìóëàìè (5)
è (6). Ââåäåì ñîáûòèÿ:
% Z1 � {ïåðâàÿ ñòðîêà ìàòðèöû B ñîäåðæèò � 1 íåíóëåâûõ ýëåìåíòîâ, âòî-
ðàÿ — íå ìåíåå � 1 íåíóëåâûõ ýëåìåíòîâ; ëþáàÿ ëèíåéíàÿ êîìáèíàöèÿ ïåðâûõ
äâóõ ñòðîê ìàòðèöû B èìååò ïî êðàéíåé ìåðå � 2 íåíóëåâûõ ýëåìåíòîâ};
% Z2 � {ïåðâàÿ ñòðîêà ìàòðèöû B ñîäåðæèò áîëåå � 1 íåíóëåâûõ ýëåìåíòîâ,
âòîðàÿ — � 1 íåíóëåâûõ ýëåìåíòîâ; ëþáàÿ ëèíåéíàÿ êîìáèíàöèÿ ïåðâûõ äâóõ
ñòðîê ìàòðèöû B èìååò ïî êðàéíåé ìåðå � 2 íåíóëåâûõ ýëåìåíòîâ};
% Z1 2, � {ïåðâûå äâå ñòðîêè ìàòðèöû B ñîäåðæàò áîëåå � 1íåíóëåâûõ ýëåìåí-
òîâ; ñóùåñòâóåò ëèíåéíàÿ êîìáèíàöèÿ ïåðâûõ äâóõ ñòðîê ýòîé ìàòðèöû, ñîäåðæà-
ùàÿ � 2 íåíóëåâûõ ýëåìåíòîâ, à ëþáûå äðóãèå ëèíåéíûå êîìáèíàöèè ñîäåðæàò íå
ìåíåå � 2 íåíóëåâûõ ýëåìåíòîâ}.
Äàííûå ñîáûòèÿ íåñîâìåñòíû, ïîýòîìó
P P P P{ ( )} { } { } { },Y r Z Z Z� �
1 2 1 2 . (24)
Âåðîÿòíîñòü ñîáûòèÿ Z1 âû÷èñëÿåòñÿ ñëåäóþùèì îáðàçîì. Ñðåäè r1 1 ïîçè-
öèé ïåðâîé ñòðîêè âûáèðàåì � 1 ïîçèöèé, íà êîòîðûõ ðàñïîëîæåíû íåíóëåâûå
ýëåìåíòû (âåðîÿòíîñòü ÷åãî ðàâíà C
q
q qr
r
1
1
1
1
1
1 1
�
!!
"
#
$$
�
!!
"
#
$$
�
� �
). Ìíîæåñòâî ýòèõ ïîçè-
öèé îáîçíà÷èì E. Ðàññìîòðèì ðàñïîëîæåíèå ñèìâîëîâ âî âòîðîé ñòðîêå. Ââåäåì
ñîáûòèå H s s( , )1 2 � {âî âòîðîé ñòðîêå íà ïîçèöèÿõ èç ìíîæåñòâà E ðàñïîëîæåíî s1
íåíóëåâûõ ñèìâîëîâ, à íà îñòàëüíûõ äîñòóïíûõ äëÿ çàïîëíåíèÿ ïîçèöèÿõ ðàñïîëî-
æåíî s2 íåíóëåâûõ ñèìâîëîâ}. Î÷åâèäíî, ÷òî ( , ) ( )s s S1 2 1� � (ñì. (15)).
Âåðîÿòíîñòü äàííîãî ñîáûòèÿ ðàâíà
p l s s C
q
q q
C
l
s
s l s
r l
( , , )1 2 2
1
1 1
2
1 1
�
�
!!
"
#
$$
�
!!
"
#
$$
s
s r l s
q
q q
2
2 2 21 1
2
�
!!
"
#
$$
�
!!
"
#
$$
(25)
ïðè l � � 1. Â ñèëó ðàñïîëîæåíèÿ íóëåâûõ è íåíóëåâûõ ñèìâîëîâ â êàæäîé èç
56 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
ñòðîê ëèíåéíàÿ êîìáèíàöèÿ ýòèõ ñòðîê ñîäåðæèò íå ìåíåå ( )�
1 1 2s s íåíó-
ëåâûõ ñèìâîëîâ. Åñëè s s2 1 1� , òî òðåòüå óñëîâèå ñîáûòèÿ Z1 âûïîëíåíî.
 ýòîì ñëó÷àå ïîëîæèì � �( , , ) �1 11 2s s . Åñëè s s2 1 1� , òî, âîñïîëüçîâàâøèñü
ëåììîé ïðåäûäóùåãî ðàçäåëà, äëÿ âåðîÿòíîñòè âûïîëíåíèÿ òðåòüåãî óñëîâèÿ ñî-
áûòèÿ Z1 ïîëó÷èì ðàâåíñòâî
� �
�
( , , )
( , , )
( )
�
1
1
1
1 2
1 2
1
s s
s s
q
s
,
ãäå �( , , ) 1 1 2s s âû÷èñëÿåòñÿ ñîãëàñíî ôîðìóëàì (18), (19). Îêîí÷àòåëüíî èìååì
P{ } ( ,Z C
q
q q
p s
r
r
1 1
1
1
1
11 1
1�
�
!!
"
#
$$
�
!!
"
#
$$
�
� �
� 1 2 1 2
1
1
1 2
, ) ( , , )
( , ) ( )
s s s
s s S
� �
�
�
� . (26)
Àíàëîãè÷íûìè ðàññóæäåíèÿìè ïîëó÷àåì ôîðìóëû äëÿ âåðîÿòíîñòåé ñîáûòèé
Z2 è Z1 2, :
P{ }Z C
q
q q
p
r
l
l r l
l
r
2 1
1
1
11 1
1 1
�
�
!!
"
#
$$
�
!!
"
#
$$
�
�
�
( , , )
( , , )
( )( , ) ( )
l s s
l s s
q
s
s s S l
1 2
1 2
1 1
1 2
�
� , (27)
P{ },Z C
q
q qr
l
l r l
l
r
1 2 1
1
1
11 1
1 1
�
�
!!
"
#
$$
�
!!
"
#
$$
�
�
� �
�
p l s s
l s s
q
s
s s U l
( , , )
( , , )
( )( , ) ( )
1 2
1 2
1 1
1 2
, (28)
ãäå S l( ) , U l( ) , { ( , , )} l s s1 2 è { ( , , )}
l s s1 2 âû÷èñëÿþòñÿ ñîãëàñíî ôîðìóëàì
(16)–(21). Îáúåäèíÿÿ (5), (6), (23)–(28), ïîëó÷àåì ôîðìóëó (14).
Òåîðåìà äîêàçàíà.
ÂÅÐÕÍÈÅ È ÍÈÆÍÈÅ ÎÖÅÍÊÈ ÂÅÐÎßÒÍÎÑÒÈ P{ ( )}Y r�
Ïóñòü, êàê è ðàíåå, âåêòîð r ôèêñèðîâàí (îí ãåíåðèðóåòñÿ ñ ïîìîùüþ îïèñàííî-
ãî âûøå àëãîðèòìà ïîñòðîåíèÿ íåñìåùåííûõ îöåíîê äëÿ
n
k
�
�
�
�
�
�
� ). Ïðåäïîëîæèì,
÷òî â êàæäîé äîñòóïíîé äëÿ çàïîëíåíèÿ ïîçèöèè ìàòðèöû B bij� ( ) ñ âåðîÿòíîñ-
òüþ 1/ q ìîæåò áûòü ðàñïîëîæåí îäèí èç ýëåìåíòîâ ïîëÿ Ãàëóà. Ñîáûòèå
Y r� ( ) � {ñòðîêè ìàòðèöû A ÿâëÿþòñÿ áàçèñîì k-ìåðíîãî âåêòîðíîãî ïîäïðîñòðà-
íñòâà âåñà �} íàñòóïèò òîãäà è òîëüêî òîãäà, êîãäà ïðîèçîéäåò îäíî èç k íåñîâ-
ìåñòíûõ ñîáûòèé D ri
�
( ) ( ) , i k�1, ,� . Âûïîëíåíèå ñîáûòèÿ D ri
�
( ) ( ) îáóñëîâëåíî
òðåìÿ óñëîâèÿìè:
à) ïåðâûå i – 1ñòðîêè ìàòðèöû A — áàçèñ ( – )i 1 -ìåðíîãî âåêòîðíîãî ïðîñòðàí-
ñòâà âåñà íå ìåíåå �
1;
á) i-ÿ ñòðîêà ìàòðèöû A ñîäåðæèò ðîâíî � íåíóëåâûõ ýëåìåíòîâ ëèáî äëÿ íå-
êîòîðûõ m i� { , , }1 1� , 1 11 2
� � �
j j j im� ñóùåñòâóåò ëèíåéíàÿ êîìáèíàöèÿ
i -é ñòðîêè ñî ñòðîêàìè j jm1 , ,� , â êîòîðîé áóäåò � íåíóëåâûõ ýëåìåíòîâ; â òî æå
âðåìÿ íå ñóùåñòâóåò ëèíåéíûõ êîìáèíàöèé i-é ñòðîêè ñ ïðåäûäóùèìè, îïðåäåëÿþ-
ùèõ âåêòîð ñ ìåíüøèì ÷èñëîì íåíóëåâûõ ýëåìåíòîâ;
â) äëÿ âñåõ j i k�
1, ,� ïåðâûå j ñòðîê ìàòðèöû A — áàçèñ j-ìåðíîãî âåêòîð-
íîãî ïðîñòðàíñòâà âåñà �.
Î÷åâèäíî, ÷òî
P P{ ( )} { ( )}( )Y r D ri
i
k
� ��
�
�
1
. (29)
Âû÷èñëèòü òî÷íîå çíà÷åíèå âåðîÿòíîñòè ñîáûòèÿ D ri
�
( ) ( ) íå ïðåäñòàâëÿåòñÿ âîç-
ìîæíûì. Êàê áóäåò âèäíî èç äàëüíåéøåãî, ýòî ñâÿçàíî ñ ïðîáëåìîé íàõîæäåíèÿ âåðî-
ÿòíîñòè íàñòóïëåíèÿ îäíîãî èç s çàâèñèìûõ ñîáûòèé. Íè÷åãî áîëåå ýôôåêòèâíîãî, ÷åì
ôîðìóëà âêëþ÷åíèé–èñêëþ÷åíèé, äî ñèõ ïîð íå íàéäåíî. Åñëè s — ÷èñëî ñî ìíîãèìè
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 57
íóëÿìè, òî çàäà÷à íàõîæäåíèÿ âåðîÿòíîñòåé âñåõ ïîïàðíûõ ïåðåñå÷åíèé óêàçàííûõ
ñîáûòèé ñòàíîâèòñÿ íåðåàëüíîé. Ïîýòîìó â êà÷åñòâå âåðõíåé îöåíêè èñïîëüçóåì
ñóììó âåðîÿòíîñòåé ñîîòâåòñòâóþùèõ ñîáûòèé; íèæíÿÿ îöåíêà òðèâèàëüíà.
Îáùàÿ ñõåìà ïðåäëàãàåìîãî ïîäõîäà ñîñòîèò â ñëåäóþùåì. Îáîçíà÷èì:
�jl
l j B
�
0, åñëè â é ïîçèöèè é ñòðîêè ìàòðèöû
ðàñïîëîæåí íóëåâîé ýëåìåíò,
1
�
�
�
��
l r k j k v vk jl� � �1 1, , , , , , ( )� � ;
p l r C
q q
Cj r j
l
l r j l
r j
l
j
j
j
( ; ) �
�
!!
"
#
$$
�
!!
"
#
$$ �
1
1 1 ( )
, , , , , , ,
q
q
j k l r j
l
r j j
j
� �
1
1 0� � (30)
— âåðîÿòíîñòü òîãî, ÷òî j-ÿ ñòðîêà ìàòðèöû B ñîäåðæèò l íåíóëåâûõ ýëåìåíòîâ
(ñîîòâåòñòâóþùàÿ ñòðîêà ìàòðèöû A ñîäåðæèò l
1 íåíóëåâûõ ýëåìåíòîâ). Âû-
ïîëíåíèå óñëîâèé à) – â) îçíà÷àåò, ÷òî êàæäàÿ èç ñòðîê 1 1, ,� i ìàòðèöû A ñî-
äåðæèò íå ìåíåå �
1 íåíóëåâûõ ýëåìåíòîâ, à ñòðîêè i k, ,� — íå ìåíåå � íåíó-
ëåâûõ ýëåìåíòîâ. Ïîýòîìó
P{ ( )} ( ; ) ( ; )( )D r p l r p l ri
j
l
r j
j
i
j
l
r jj j
�
� �
�
�
�
�
��
1
1
1
� ��
�
�
p s r D r si
s
r i
j i
k
s
i
i
( ; ) { ( ) | ( )},( )
( )
�
� � �
11
M P (31)
ãäå ñîîòâåòñòâóþùèå ìàòåìàòè÷åñêèå îæèäàíèÿ áåðóòñÿ ïî çíà÷åíèÿì ñëó-
÷àéíûõ âåêòîðîâ � �( ) { ( )}s sjl� . Êàæäàÿ èç êîìïîíåíò � jl js l r j( ), , ,� 1 � , ïðè-
íèìàåò çíà÷åíèå 0 ñ âåðîÿòíîñòüþ
1
q
è 1 — ñ âåðîÿòíîñòüþ
q
q
1
ïðè óñëîâèè,
÷òî � � �j j r js s
j1 ( ) ( )
� � , j i� 1 1, ,� , � �
i i r is s s
i1
( ) ( )
� � , � j s1 ( )
�
� �
� �
� �j r jj
s j i k( ) , , ,1 1 .
Ïîñòðîèì âíà÷àëå âåðõíþþ îöåíêó äëÿ âåðîÿòíîñòè P{ ( ) | ( )}( )D r si
� � , ñ÷èòàÿ
êîìïîíåíòû âåêòîðà �( )s èçâåñòíûìè. Îòáðîñèâ óñëîâèÿ à) è â), ïîëó÷èì îöåíêè
P{ ( )| ( )}( )D r si
� �
1 ïðè s � � 1, (32)
P P{ ( ) | ( )} {( )
, ,
(D r s Ei
j j j im
i
s m
m
� ��
� � �
�
��
1 11
1
1 2 �
i r j s) ( , ) | ( )}� ïðè s r ii� �, , ,�
(33)
ãäå E r js m
i
�, ,
( ) ( , ) � {ñóùåñòâóåò ëèíåéíàÿ êîìáèíàöèÿ i-é ñòðîêè ìàòðèöû A,
ñîäåðæàùåé s íåíóëåâûõ ýëåìåíòîâ, è ñòðîê, îïðåäåëÿåìûõ âåêòîðîì
j j jm� ( , , )1 � , â êîòîðîé � íåíóëåâûõ ýëåìåíòîâ; â òî æå âðåìÿ íå ñóùåñòâóåò
óêàçàííûõ ëèíåéíûõ êîìáèíàöèé, îïðåäåëÿþùèõ âåêòîð ñ ìåíüøèì ÷èñëîì íå-
íóëåâûõ ýëåìåíòîâ}.
Ïîñòðîèì âåðõíþþ îöåíêó âåðîÿòíîñòè P{ ( , )| ( )}, ,
( )E r j ss m
i
� � . Äëÿ êàæäîãî
l r ii� 1, ,� âû÷èñëèì
�
�
l
j ls
s z m
z( )
, ( ) , , ,
�
� ��
�
�
0 0 1
1
åñëè äëÿ âñåõ
â ïðîòèâíîì
�
Îáîçíà÷èì w ÷èñëî èíäåêñîâ l òàêèõ, ÷òî � l s( ) �1è � il s( ) �1, à
— ÷èñëî èí-
äåêñîâ l òàêèõ, ÷òî � �l ils s( ) ( )
�1. Î÷åâèäíî, ÷òî ëþáàÿ ëèíåéíàÿ êîìáèíàöèÿ i-é
ñòðîêè ñî ñòðîêàìè, çàäàâàåìûìè âåêòîðîì j , ñîäåðæèò ïî êðàéíåé ìåðå
m
1
íåíóëåâûõ ýëåìåíòîâ. Åñëè m
�1
�, òî P{ ( , ) | ( )}, ,
( )E r j ss m
i
� � � 0 . Ïóñòü
� �
�
�( )m 1 0.  ýòîì ñëó÷àå
58 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
ñëó÷àå.
â ïðîòèâíîì ñëó÷àå,
P{ ( , ) | ( )} ( )
( , )
( )
, ,
( )
( )
E r j s q
q
q
s m
i m w
w� �
� �
� 1
1
1
1
1
( ) ( , )( )q qm w
w 1 11 1� � . (34)
Äåéñòâèòåëüíî, ( )q m 1 1 — ÷èñëî ñïîñîáîâ, êàêèìè ìîæíî ïîñòðîèòü ðàçëè÷-
íûå (ñ òî÷íîñòüþ äî ìíîæèòåëÿ) ëèíåéíûå êîìáèíàöèè ñòðîê, îïðåäåëÿåìûõ âåê-
òîðîì j. Ïóñòü � — ôèêñèðîâàííàÿ ëèíåéíàÿ êîìáèíàöèÿ m ñòðîê. Òîãäà ( ) —q w 1
÷èñëî âñåõ âîçìîæíûõ ñïîñîáîâ çàïîëíåíèÿ íåíóëåâûìè ñèìâîëàìè w ïîçèöèé â i-é
ñòðîêå, � �w q( ) ( , )1 1 — ÷èñëî ñïîñîáîâ çàïîëíåíèÿ íåíóëåâûìè ñèìâîëàìè w ïîçè-
öèé â i-é ñòðîêå, ïðè êîòîðûõ ñóùåñòâóåò ëèíåéíàÿ êîìáèíàöèÿ i-é ñòðîêè è âåêòî-
ðà � , â êîòîðîé ðîâíî � íåíóëåâûõ ýëåìåíòîâ, è íå ñóùåñòâóåò ëèíåéíûõ êîìáèíà-
öèé i-é ñòðîêè è âåêòîðà �, îïðåäåëÿþùèõ âåêòîð ñ ìåíüøèì ÷èñëîì íåíóëåâûõ
ýëåìåíòîâ.
Ñîîòíîøåíèÿ (29)–(34) ïîçâîëÿþò ñôîðìóëèðîâàòü àëãîðèòì ïîñòðîåíèÿ
âåðõíèõ îöåíîê âåðîÿòíîñòè P{ ( )}Y r� .
Òåîðåìà 2. Èìååò ìåñòî ñîîòíîøåíèå
P M{ ( )} ( )( )Y r r� ��
up .
Àëãîðèòì ïîñòðîåíèÿ ðåàëèçàöèé ñëó÷àéíîé âåëè÷èíû ��
( ) ( )up r ôîðìóëèðóåò-
ñÿ ñëåäóþùèì îáðàçîì.
1. Ïî ôîðìóëå (30) âû÷èñëÿåì âåðîÿòíîñòè { ( ; )}p l rj .
2. Äëÿ êàæäîãî i k�1, ,� îñóùåñòâëÿåì ñëåäóþùèå øàãè:
% âû÷èñëÿåì (ñì. (31) è (32))
d r p r p l r p l ri
i j
l
r j
j
i
j
l
j
�
� �
�( ) ( ) ( ; ) ( ; ) ( ; )�
�
�
�
��1
1
1
�
��
11
r j
j i
k j
; (35)
% îïðåäåëÿåì ìîäåëèðîâàíèåì, êàêèå èç êîìïîíåíò âåêòîðà � ��{ }jl íóëåâûå,
êàêèå íåò, à èìåííî, êîìïîíåíòà � jl ïðèíèìàåò çíà÷åíèå 0 ñ âåðîÿòíîñòüþ
1
q
è 1 — ñ âåðîÿòíîñòüþ
q
q
1
ïðè óñëîâèè, ÷òî � � �j jr jj1
� � , j i�1, ,� ,
�
j1
�
� � �j r jj
1, j i k�
1, ,� .
3. Âû÷èñëÿåì îöåíêó (ñì. (31), (33) è (34))
� � �� � �
( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ( )up r d r h r q ji i m w j
w�
1 1 1 , ) ,q
j j j im
i
i
k
m
�
�
�
�
�
�
�
�
� � �
�
�
��� 1
1 11
1
1 1 2 �
(36)
ãäå
h r p l r p l ri
j
l
r j
j
i
j
l
r j
j i
j j
�
� �
( ) ( ) ( ; ) ( ; )�
�
� �
�
�� �
1 11
k
� , (37)
à çíà÷åíèÿ w j j( ), ( )� âû÷èñëÿþòñÿ ïî òåì æå ïðàâèëàì, ÷òî è w,� â ôîðìóëå
(34); çäåñü, êàê è ðàíåå, j j jm� ( , , )1 � .
Ïîñòðîèì íèæíþþ îöåíêó äëÿ âåðîÿòíîñòè P{ ( )}( )D ri
� . Èç ôîðìóëû (31) ñëå-
äóåò îöåíêà
P{ ( )} ( ; ) ( ; ) ( ; )( )D r p r p l r p l ri
i j
l
r j
j
i
j
j
�
�
��
�
�
��1
1
1
l
r j
j i
k
i i
j
i D r
�
�
��
�
� � �
11
M P( ) { ( )| },( ) ( ) (38)
ãäå ñîîòâåòñòâóþùèå ìàòåìàòè÷åñêèå îæèäàíèÿ áåðóòñÿ ïî çíà÷åíèÿì ñëó÷àé-
íûõ âåêòîðîâ � �( ) ( )i
jl
i� { }. Êàæäàÿ èç êîìïîíåíò �
jl
i
jl r j( ) , , ,� 1 � , ïðèíèìàåò
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 59
çíà÷åíèå 0 ñ âåðîÿòíîñòüþ
1
q
è 1 — ñ âåðîÿòíîñòüþ
q
q
1
ïðè óñëîâèè, ÷òî
� � �
j
i
jr j
i
j1
( ) ( )
�
� , j i� 1 1, ,� , � � �
i
i
ir i
i
i1
1( ) ( )
�
� , � � �
j
i
jr j
i
j1
1( ) ( )
�
� ,
j i k�
1, ,� .
Ïîñòðîèì íèæíþþ îöåíêó äëÿ âåðîÿòíîñòè P{ ( ) | }( ) ( )D ri i
� � , ñ÷èòàÿ êîìïîíåí-
òû âåêòîðà � ( )i èçâåñòíûìè. Ââåäåì ñîáûòèÿ: V ri
� �( ) ( , ) � {ïåðâûå � ñòðîê ìàòðèöû
A — áàçèñ �-ìåðíîãî âåêòîðíîãî ïðîñòðàíñòâà âåñà íå ìåíåå �
1 }, � �1, ,� k.
Î÷åâèäíî, ÷òî V r V r ki i
� �� � �( ) ( )( , ) ( , ), , ,
� � 1 1 1� , ïðè÷åì ñîáûòèå V ri
�
( ) ( , )1
äîñòîâåðíî. Òîãäà
D r V r V ri i
i
i
i
k
� �
�
�
�
� �( ) ( ) ( )( ) ( , ) ( , )�
�
�
2
1
1
1
� �� .
Ïîýòîìó
P P{ ( ) | } { ( , ) | ; ( , )}( ) ( ) ( ) ( ) ( )D r V r V ri i i i i
� � �
�
� � � ��
�
1
2
1i
� �
�
�
� P{ ( , ) | ; ( , )}( ) ( ) ( )V r V ri i i
i
k
� �
�
� � �
1 1
1
1 (39)
(â ñèëó îïðåäåëåíèÿ âåêòîðà � ( )i âåñ �-ìåðíîãî âåêòîðíîãî ïðîñòðàíñòâà ïðè
� �
i 1 íå ìîæåò áûòü áîëüøå �). Â òî æå âðåìÿ
P P{ ( , ) | ; ( , )} { ( , ) |( ) ( ) ( ) ( ) (V r V r V ri i i i i
� � �� � � � � � 1 1 ) ( ); ( , )}V ri
� � 1 , (40)
ãäå V ri
� �( ) ( , ) îáîçíà÷àåò ñîáûòèå, äîïîëíèòåëüíîå ê V ri
� �( ) ( , ) . Íàñòóïëåíèå ñî-
áûòèÿ V ri
� �( ) ( , ) ïðè óñëîâèè, ÷òî ïðîèçîøëî ñîáûòèå V ri
� �( ) ( , ) 1 , îçíà÷àåò, ÷òî
ýëåìåíòû â ñòðîêå � ðàñïîëîæåíû òàêèì îáðàçîì, ÷òî ëèíåéíàÿ êîìáèíàöèÿ
ýòîé ñòðîêè ñ ïðåäûäóùèìè ïîçâîëèò ïîëó÷èòü âåêòîð ñ ÷èñëîì íåíóëåâûõ êîì-
ïîíåíò, ìåíüøèì, ÷åì �
1. Äëÿ ïîñòðîåíèÿ âåðõíåé îöåíêè âåðîÿòíîñòè ñîáû-
òèÿ V ri
� �( ) ( , ) âîñïîëüçóåìñÿ òåì æå ïðèåìîì, ÷òî è ðàíåå. Äåéñòâèòåëüíî, ïðè
� � 2
P{ ( , ) | ; ( , )}( ) ( ) ( )V r V ri i i
� �� � �
1
� � �
P{ ( , , ) | ; ( , )},
( ) ( ) ( )W r j V rm
i i i
j j jm
� �
�
� � � 1
1 1 2 � �
��
11
1
m
�
,
(41)
ãäå W r jm
i
� �,
( ) ( , , ) � {ñóùåñòâóåò ëèíåéíàÿ êîìáèíàöèÿ ñòðîêè � ìàòðèöû A è
ñòðîê, îïðåäåëÿåìûõ âåêòîðîì j j jm� ( , , )1 � , â êîòîðîé íå áîëåå � íåíóëåâûõ
ýëåìåíòîâ}. Äàëåå äëÿ êàæäîãî l r� 1, ,� � � âû÷èñëÿåì
�
�
l
j l
i
z
z m
�
� ��
�
�
��
0 0 1
1
, , , ,( )åñëè äëÿ âñåõ
â ïðîòèâíîì
�
Îáîçíà÷èì w ÷èñëî èíäåêñîâ l òàêèõ, ÷òî � l �1è �
�l
i( ) �1, à
— ÷èñëî èíäåê-
ñîâ l òàêèõ, ÷òî � �
�l l
i
�( ) 1. Î÷åâèäíî, ÷òî ëþáàÿ ëèíåéíàÿ êîìáèíàöèÿ ñòðîêè �
ñî ñòðîêàìè, çàäàâàåìûìè âåêòîðîì j, ñîäåðæèò ïî êðàéíåé ìåðå m
1
íåíóëå-
âûõ ýëåìåíòîâ. Åñëè m
�1
� , òî P{ ( , , ) | ; ( , )},
( ) ( ) ( )W r j V rm
i i i
� �� � � �1 0 . Ïóñòü
� �
�
�( )m 1 0 .  ýòîì ñëó÷àå
60 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
ñëó÷àå.
P{ ( , , ) | ; ( , )} ( )
(
,
( ) ( ) ( )
( )
W r j V r qm
i i i m
w
� �� � �
�
1 1 1
1 �
�
�
, )
( )
q
q w
��
� 1
1
0
�
�
�( ) ( , )( )q qm w
w1 11 1
0
� �
�
�
. (42)
Äåéñòâèòåëüíî, ( )q m 1 1 — ÷èñëî ñïîñîáîâ, êàêèìè ìîæíî ïîñòðîèòü ðàç-
ëè÷íûå (ñ òî÷íîñòüþ äî ìíîæèòåëÿ) ëèíåéíûå êîìáèíàöèè ñòðîê, îïðåäåëÿå-
ìûõ âåêòîðîì j. Ïóñòü � — ôèêñèðîâàííàÿ ëèíåéíàÿ êîìáèíàöèÿ m ñòðîê. Òîãäà
( )q w 1 — ÷èñëî âñåõ âîçìîæíûõ ñïîñîáîâ çàïîëíåíèÿ íåíóëåâûìè ñèìâîëàìè w ïî-
çèöèé â ñòðîêå �, à � �
�
�
w q( ) ( , )1
0
1
�
� — ÷èñëî ñïîñîáîâ çàïîëíåíèÿ íåíóëåâûìè ñèì-
âîëàìè w ïîçèöèé â ñòðîêå �, ïðè êîòîðûõ ñóùåñòâóåò ëèíåéíàÿ êîìáèíàöèÿ ñòðî-
êè � è âåêòîðà �, â êîòîðîé íå áîëåå � íåíóëåâûõ ýëåìåíòîâ.
Àíàëîãè÷íî îöåíèâàþòñÿ è âåðîÿòíîñòè P{ ( , ) | ; ( , )}( ) ( ) ( )V r V ri i i
� �
� � �
1 1
1 ïðè
� �
i k1, ,� .
Ñîîòíîøåíèÿ (29), (30), (38)–(42) ïîçâîëÿþò ñôîðìóëèðîâàòü àëãîðèòì ïî-
ñòðîåíèÿ íèæíèõ îöåíîê âåðîÿòíîñòè P{ ( )}Y r� .
Òåîðåìà 3. Èìååò ìåñòî ñîîòíîøåíèå
P M{ ( )} ( )( )Y r r� ��� low .
Àëãîðèòì ïîñòðîåíèÿ ðåàëèçàöèé ñëó÷àéíîé âåëè÷èíû ��
( ) ( )low r ôîðìóëèðó-
åòñÿ ñëåäóþùèì îáðàçîì.
1. Ïî ôîðìóëå (30) âû÷èñëÿåì âåðîÿòíîñòè { ( ; )}p l rj .
2. Äëÿ êàæäîãî i k�1, ,� îñóùåñòâëÿåì ñëåäóþùèå øàãè:
% ïî ôîðìóëå (35) âû÷èñëÿåì d ri
�
( ) ( ) ;
% îïðåäåëÿåì ìîäåëèðîâàíèåì, êàêèå èç êîìïîíåíò âåêòîðà � �( ) ( ){ }i
jl
i� íóëå-
âûå, êàêèå íåò, à èìåííî, êîìïîíåíòà �
jl
i( ) ïðèíèìàåò çíà÷åíèå 0 ñ âåðîÿòíîñòüþ
1
q
è 1 — ñ âåðîÿòíîñòüþ
q
q
1
ïðè óñëîâèè, ÷òî � � �
j
i
j r j
i
j1
( ) ( )
�
� , j i� 1 1, ,� ,
� � �
i
i
ir i
i
i1
1( ) ( )
�
� , � � �
j
i
j r j
i
j1
1( ) ( )
�
� , j i k�
1, ,� ;
% ïî ôîðìóëàì (38)–(40) ñòðîèì íèæíèå îöåíêè { ( , )}( )g ri
� � äëÿ âåðîÿòíîñòåé
P{ ( , ) | ; ( , )}, , ,( ) ( ) ( )V r V r ii i i
� �� � � � � 1 2 1� , è íèæíèå îöåíêè { ( , )}( )g ri
�
�
1
äëÿ âå-
ðîÿòíîñòåé P{ ( , ) | ; ( , )}( ) ( ) ( )V r V ri i i
� �
� � �
1 1
1 , � �
i k1, ,� .
3. Âû÷èñëÿåì îöåíêó (ñì. (29), (36) è (37))
� � �� � � �
��
( ) ( ) ( ) ( )( ) ( ) ( , ) ( , )low r d r g r g ri i i
i
k
�
�
�
� 1
12
1
1
i
i
k
�
��
�
�
�
�
�
�
�
�
. (43)
Ñôîðìóëèðîâàííûå àëãîðèòìû (òåîðåìû 2 è 3) â ñî÷åòàíèè ñ ôîðìóëàìè (3),
(4) è (7) ïîçâîëÿþò ñòðîèòü âåðõíèå è íèæíèå îöåíêè äëÿ
n
k
�
�
�
�
�
�
� . Â òî æå âðåìÿ,
êàê ïîêàçûâàþò ìíîãî÷èñëåííûå ïðèìåðû, íàèáîëåå òî÷íîé ÿâëÿåòñÿ àïïðîêñè-
ìàöèÿ, îñíîâàííàÿ íà êîìáèíàöèè âåðõíèõ è íèæíèõ îöåíîê (ñì. (37) è (45)), à èìåííî
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 61
� � �� � � �
��
( ) ( ) ( ) ( )( ) ( ) ( , ) ( , )appr r d r g r g ri i i
i
k
�
�
� 1
1�
�
��
�
�
�
� 2
1
1
i
i
k
� � �
h r q j qi m w j
w
j j jm
� � �( ) ( ) ( )( ) ( ) ( ( ), )1 11 1
1 1 2 � im
i
�
��
�
�
�
�11
1
, (44)
ãäå { ( )}( )d ri
� è { ( )}( )h ri
� âû÷èñëÿþòñÿ ñîãëàñíî (35) è (37); îñòàëüíûå îáîçíà÷å-
íèÿ — ñì. ôîðìóëèðîâêè àëãîðèòìîâ ïîñòðîåíèÿ âåðõíèõ è íèæíèõ îöåíîê (òå-
îðåìû 2 è 3).
×ÈÑËÅÍÍÛÅ ÐÅÇÓËÜÒÀÒÛ
Ïðîèëëþñòðèðóåì òî÷íîñòü îöåíîê íà ÷èñëåííûõ ïðèìåðàõ.  ïåðâîì ïðèìåðå
ïðèâåäåí ñëó÷àé, êîãäà èçâåñòíî òî÷íîå çíà÷åíèå
n
k
�
�
�
�
�
�
� , âî âòîðîì ðàññìîòðåíû òå
çíà÷åíèÿ k è �, äëÿ êîòîðûõ îòñóòñòâóþò êàêèå-ëèáî îöåíêè. Âñå ïðèâåäåííûå
íèæå îöåíêè ïîñòðîåíû ñ îòíîñèòåëüíîé ïîãðåøíîñòüþ � �1% è äîñòîâåðíî-
ñòüþ 0,99. Èñïîëüçîâàíèå óñêîðåííîãî ìîäåëèðîâàíèÿ íà ìíîãîïðîöåññîðíîì êîì-
ïëåêñå ÑÊÈÒ-3 ïîçâîëèëî ïîëó÷èòü îöåíêè âûñîêîé òî÷íîñòè äëÿ äîñòàòî÷íî áîëü-
øèõ çíà÷åíèé n k, è �. Âûáîð ÷èñëà çàäåéñòâîâàííûõ ïðîöåññîðîâ ïðîâîäèëñÿ èñ-
õîäÿ èç óñëîâèÿ, ÷òîáû âðåìÿ âû÷èñëåíèé äëÿ êàæäîãî âàðèàíòà íå ïðåâûøàëî
30 ìèíóò. Ïîëîæèì n q� � �50 2 325, . Ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ:
� ( , )( )��
low n k è � ( , )( )��
up n k — âåðõíèå è íèæíèå îöåíêè äëÿ
n
k
�
�
�
�
�
�
� , ïîñòðîåííûå
ñ óêàçàííûìè âûøå äîñòîâåðíîñòüþ è îòíîñèòåëüíîé ïîãðåøíîñòüþ;
� ( , )( )��
appr n k — àïïðîêñèìàöèÿ äëÿ
n
k
�
�
�
�
�
�
� , îñíîâàííàÿ íà îöåíêàõ âèäà (44).
Ïðèìåð 1. Ðàññìàòðèâàþòñÿ äâà ñëó÷àÿ, êîãäà óäàåòñÿ íàéòè òî÷íîå çíà÷åíèå
n
k
�
�
�
�
�
�
� : k � 2 , � — ïðîèçâîëüíîå (ñì. (14)); � � 2, k — ïðîèçâîëüíîå (ðåêóððåíòíûå
ôîðìóëû ñì. [6]). Ñîîòâåòñòâóþùèå îöåíêè ïðåäñòàâëåíû â òàáë. 1 (n � 50, k � 2,
q � �2 105, , %� ) è òàáë. 2 (n � 50, � � 2, q � �2 105, , %� ).
 îáîèõ ñëó÷àÿõ âûñîêóþ òî÷íîñòü äåìîíñòðèðóåò àïïðîêñèìàöèÿ � ( , )( )��
appr n k
ïðè ñàìûõ ðàçíûõ çíà÷åíèÿõ � ( k � 2 ) è k ( � � 2 ).  øèðîêîì äèàïàçîíå èçìåíå-
íèÿ k è � âûñîêîé òî÷íîñòüþ îáëàäàþò òàêæå èõ âåðõíÿÿ è íèæíÿÿ îöåíêè
62 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
�
n
k
�
�
�
�
�
�
� � ( , )( )��
low n k � ( , )( )��
appr n k � ( , )( )��
up n k
6 8 30 1086, & 8 24 1086, & 8 32 1086, & 8 32 1086, &
12 5 63 1099, & 5 33 1099, & 5 61 1099, & 5 61 1099, &
18 7 42 10110, & 6 48 10110, & 7 33 10110, & 7 33 10110, &
24 4 44 10120, & 3 41 10120, & 4 41 10120, & 4 41 10120, &
30 1 53 10129, & 0 97 10129, & 1 52 10129, & 1 52 10129, &
36 2 70 10136, & 1 31 10136, & 2 70 10136, & 2 70 10136, &
42 1 37 10142, & 0 40 10142, & 1 36 10142, & 1 36 10142, &
45 1 14 10144, & 0 26 10144, & 114 10144, & 117 10144, &
48 5 26 10138, & 5 00 10138, & 5 26 10138, & 8 27 10143, &
49 0 0 0 1 48 10143, &
Ò à á ë è ö à 1
� ( , )( )��
up n k è � ( , )( )��
low n k . Òîëüêî ïðè � � 48 , � � 49 (òàáë. 1) è k � 47 , k � 48 (òàáë. 2)
îöåíêà � ( , )( )��
up n k äàåò íåñêîëüêî çàâûøåííûå çíà÷åíèÿ. Ñ âîçðàñòàíèåì � (òàáë. 1)
òî÷íîñòü îöåíêè � ( , )( )��
low n k âíà÷àëå ïàäàåò, à çàòåì íåçíà÷èòåëüíî âîçðàñòàåò.
Àíàëîãè÷íî èçìåíÿåòñÿ îöåíêà � ( , )( )��
low n k è ñ âîçðàñòàíèåì k (òàáë. 2).
Ïðèìåð 2. Ðàññìîòðèì ñëó÷àé k �10. Åñëè � � 2 , òî íå ñóùåñòâóåò êàêèõ-ëèáî
àíàëèòè÷åñêèõ èëè ïðèáëèæåííûõ ôîðìóë äëÿ âû÷èñëåíèÿ
n
k
�
�
�
�
�
�
� . Î òî÷íîñòè îöå-
íîê ìîæíî ñóäèòü òîëüêî ïî êîñâåííûì äàííûì. Òàê, ñîãëàñíî ôîðìóëå (2) ñóììà
ïî � çíà÷åíèé
n
k
�
�
�
�
�
�
� ðàâíÿåòñÿ
n
k
�
��
�
��
, êîòîðîå âû÷èñëÿåòñÿ â ÿâíîì âèäå ïî ôîðìó-
ëå (1). Ïðîâåðèì, òàê ëè ýòî äëÿ ðàññìàòðèâàåìûõ n è k. Äåéñòâèòåëüíî,
50
10
119 10602�
��
�
��
� &, . Ðåçóëüòàòû âû÷èñëåíèé ïðè ðàçëè÷íûõ � ïðåäñòàâëåíû
â òàáë. 3 (n � 50, k q� � �10 2 105, , , %� ). Ñîãëàñíî ýòèì äàííûì � ( , )( )��
�
appr 5010
1
41
'
�
�
' &122 10602, , ò.å. ðåçóëüòàòû äîñòàòî÷íî áëèçêè. Ðàñ÷åò äëÿ ìíîãî÷èñëåííûõ çíà÷å-
íèé íàáîðîâ n, k è q â øèðîêîì äèàïàçîíå èõ èçìåíåíèÿ (5 100
n , 3
k n,
2 210
q ) ïîêàçàë, ÷òî âî âñåõ ñèòóàöèÿõ � ( , )( )��
�
appr n k
�
�
1
41
ÿâëÿåòñÿ âåðõíåé îöåí-
êîé äëÿ
n
k
�
��
�
��
, ïðè÷åì ïðåâûøåíèå ñîñòàâëÿåò íå áîëåå 15%. Ïðîàíàëèçèðóåì äàí-
íûå, ïðåäñòàâëåííûå â òàáë. 3. Êàê è â òàáë. 1, ïðè áîëüøèíñòâå çíà÷åíèé � îöåíêè
� ( , )( )��
appr n k è � ( , )( )��
up n k ïðàêòè÷åñêè èäåíòè÷íû; òîëüêî ïðè �, áëèçêèì ê ìàêñè-
ìàëüíî äîïóñòèìûì, âåðõíèå îöåíêè íà÷èíàþò ðåçêî òåðÿòü òî÷íîñòü. Ê ñîæàëå-
íèþ, òî÷íîñòü íèæíèõ îöåíîê ïàäàåò êàê ñ âîçðàñòàíèåì �, òàê è ñ âîçðàñòàíèåì k.
Òåì íå ìåíåå âåðõíèå è íèæíèå îöåíêè ïîçâîëÿþò óñòàíàâëèâàòü äèàïàçîí èçìåíå-
íèÿ
n
k
�
�
�
�
�
�
� ïðè � � 3 è k � 2 , ÷åãî ðàíåå íå óäàâàëîñü äîñòè÷ü. Ïðè ýòîì åñòü îñíîâà-
íèÿ ïîëàãàòü, ÷òî îöåíêà � ( , )( )��
appr n k ÿâëÿåòñÿ äîñòàòî÷íî òî÷íîé àïïðîêñèìàöèåé
äëÿ
n
k
�
�
�
�
�
�
� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 63
k
n
k
�
�
�
�
�
�
� � ( , )( )��
low n k � ( , )( )��
appr n k � ( , )( )��
up n k
2 6 93 1076, & 6 86 1076, & 6 96 1076, & 6 96 1076, &
8 1 28 10447, & 1 25 10447, & 1 28 10447, & 1 28 10447, &
14 1 01 10709, & 0 94 10709, & 1 01 10709, & 1 01 10709, &
20 3 38 10862, & 2 86 10862, & 3 37 10862, & 3 36 10862, &
26 4 83 10907, & 3 53 10907, & 4 82 10907, & 4 81 10907, &
32 2 93 10844, & 1 74 10844, & 2 93 10844, & 2 92 10844, &
38 7 59 10672, & 3 23 10672, & 7 60 10672, & 7 61 10672, &
44 8 36 10392, & 1 90 10392, & 8 36 10392, & 8 33 10392, &
46 3 26 10275, & 0 50 10275, & 3 25 10275, & 3 28 10275, &
47 1 20 10212, & 0 17 10212, & 1 20 10212, & 1 84 10212, &
48 3 07 10144, & 118 10144, & 3 04 10144, & 20 35 10144, &
49 1 19 1073, & 119 1073, & 119 1073, & 119 1073, &
Ò à á ë è ö à 2
64 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
Àâòîð áëàãîäàðåí äîêòîðó ôèç.-ìàò. íàóê, ïðîôåññîðó Â.È. Ìàñîëó çà
ïîñòàíîâêó çàäà÷è, à òàêæå Î.À. Êîðîëü çà ïîìîùü ïðè ðåàëèçàöèè àëãîðèòìîâ íà
ìíîãîïðîöåññîðíîì êîìïëåêñå ÑÊÈÒ-3.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ì à ñ î ë  . È . , Ê ó ç í å ö î â È . Í . Ïðèìåíåíèå óñêîðåííîãî ìîäåëèðîâàíèÿ ê îöåíêå êîëè÷åñòâà
íåêîòîðûõ k-ìåðíûõ ïîäïðîñòðàíñòâ íàä êîíå÷íûì ïîëåì // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. —
2010. — ¹ 3. — Ñ. 69–83.
2. Ý í ä ð þ ñ Ã . Òåîðèÿ ðàçáèåíèé. — Ì.: Íàóêà, 1982. — 256 ñ.
3. C a l a b i E . , W i l f H . On the sequential and random selection of subspaces over a finite field //
J. Combin. Theory. Ser. A. — 1977. — 22, N 1. — P. 107–109.
4. Ì à ê - Â à ë ü ð à ñ Ô . Ä æ . , Ñ ë î ý í Í . Ä æ . Òåîðèÿ êîäîâ, èñïðàâëÿþùèõ îøèáêè. — Ì.: Ñâÿçü,
1979. — 744 ñ.
5. M a s o l V . V . Investigation of linear codes possessing some extra properties // Cryptography and
Coding. — 2001. — P. 301–306.
6. Ì à ñ î ë  . È . Íåêîòîðûå ïðèìåíåíèÿ àëãîðèòìîâ ïîñòðîåíèÿ ïîäïðîñòðàíñòâ íàä êîíå÷íûì
ïîëåì // Óêð. ìàò. æóðí. — 1989. — 41, ¹ 8. — Ñ. 1146–1148.
7. Ì à ñ î ë  . È . Àñèìïòîòèêà ÷èñëà íåêîòîðûõ k-ìåðíûõ ïîäïðîñòðàíñòâ íàä êîíå÷íûì ïîëåì //
Ìàò. çàìåòêè. — 1996. — 59, âûï. 5. — Ñ. 729–736.
8. Ê î â à ë å í ê î È . Í . Èññëåäîâàíèÿ ïî àíàëèçó íàäåæíîñòè ñëîæíûõ ñèñòåì. — Êèåâ: Íàóê. äóìêà,
1975. — 210 ñ.
9. Ê î â à ë å í ê î È . Í . Àíàëèç ðåäêèõ ñîáûòèé ïðè îöåíêå ýôôåêòèâíîñòè è íàäåæíîñòè ñèñòåì. —
Ì.: Ñîâ. ðàäèî, 1980. — 209 ñ.
10. K o v a l e n k o I . N . , K u z n e t s o v N . Y u . , P e g g P h . A . Mathematical theory of reliability of
time dependent systems with practical applications. — Chichester: Wiley, 1997. — 303 p.
Ïîñòóïèëà 16.03.2010
� � ( , )( )��
low n k � ( , )( )��
appr n k � ( , )( )��
up n k
5 1 07 10554, & 1 46 10554, & 1 46 10554, &
10 7 02 10564, & 2 02 10565, & 2 02 10565, &
15 1 53 10574, & 1 29 10575, & 1 29 10575, &
20 2 32 10582, & 7 52 10583, & 7 56 10583, &
25 3 07 10589, & 5 79 10591, & 5 78 10591, &
30 3 14 10595, & 6 19 10598, & 6 16 10598, &
31 3 55 10596, & 1 23 10600, & 1 24 10600, &
32 3 45 10597, & 2 14 10601, & 2 27 10601, &
33 2 19 10598, & 9 92 10601, & 2 45 10602, &
34 3 79 10596, & 3 11 10599, & 5 07 10602, &
35 0 0 7 02 10602, &
Ò à á ë è ö à 3
|
| id | nasplib_isofts_kiev_ua-123456789-45646 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-02T12:10:26Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Кузнецов, И.Н. 2013-06-17T06:26:45Z 2013-06-17T06:26:45Z 2010 Верхние и нижние оценки количества некоторых -мерных подпространств заданного веса над конечным полем / И.Н. Кузнецов // Кибернетика и системный анализ. — 2010. — № 6. — С. 51–64. — Бібліогр.: 10 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45646 519.12 Запропоновано метод прискореного моделювання, що дозволяє будувати верхні та нижні оцінки кількості k-вимірних підпросторів довільної ваги ω n-вимірного векторного простору над полем Галуа, що містить q елементів. Точність оцінок ілюструють чисельні приклади. A fast simulation method enabling to construct upper and lower estimates for the number of k-measurable subspaces of an arbitrary weight ω of n-measurable vector space over the Galois field containing q components is proposed. Numerical examples demonstrate the accuracy of the estimates. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Верхние и нижние оценки количества некоторых k-мерных подпространств заданного веса над конечным полем Верхні та нижні оцінки кількості деяких k-вимірних підпросторів заданої ваги над скінченим полем Upper and lower estimates for the number of some k-measurable subspaces of a given weight over a finite space Article published earlier |
| spellingShingle | Верхние и нижние оценки количества некоторых k-мерных подпространств заданного веса над конечным полем Кузнецов, И.Н. Кибернетика |
| title | Верхние и нижние оценки количества некоторых k-мерных подпространств заданного веса над конечным полем |
| title_alt | Верхні та нижні оцінки кількості деяких k-вимірних підпросторів заданої ваги над скінченим полем Upper and lower estimates for the number of some k-measurable subspaces of a given weight over a finite space |
| title_full | Верхние и нижние оценки количества некоторых k-мерных подпространств заданного веса над конечным полем |
| title_fullStr | Верхние и нижние оценки количества некоторых k-мерных подпространств заданного веса над конечным полем |
| title_full_unstemmed | Верхние и нижние оценки количества некоторых k-мерных подпространств заданного веса над конечным полем |
| title_short | Верхние и нижние оценки количества некоторых k-мерных подпространств заданного веса над конечным полем |
| title_sort | верхние и нижние оценки количества некоторых k-мерных подпространств заданного веса над конечным полем |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45646 |
| work_keys_str_mv | AT kuznecovin verhnieinižnieocenkikoličestvanekotoryhkmernyhpodprostranstvzadannogovesanadkonečnympolem AT kuznecovin verhnítanižníocínkikílʹkostídeâkihkvimírnihpídprostorívzadanoívaginadskínčenimpolem AT kuznecovin upperandlowerestimatesforthenumberofsomekmeasurablesubspacesofagivenweightoverafinitespace |