ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
40
1
(
)
(
)(
1)
1
1
.
2
2
l
i k
s
s
l k
m
m
i
l k l k
n n
n
n
m m
m
m
−
=
⎡
⎤ ⎛ ⎞
⎛ ⎞
−
⎜ ⎟
⎜ ⎟
⎢
⎥
− − −
⎝ ⎠
⎝ ⎠
⎢
⎥
− − > −
−
⎛ ⎞ ⎛ ⎞
⎛ ⎞
⎛ ⎞
⎢
⎥
⎜ ⎟ ⎜ ⎟
⎜ ⎟
⎜ ⎟
⎢
⎥
⎝ ⎠ ⎝ ⎠
⎝ ⎠
⎝ ⎠
⎣
⎦
∏
(11)
Оценим отношение
127
127
(1/ 2)
2 .
m
s
m s
n n
m
−
⎛ ⎞
⎜ ⎟ ⎡ ⎤
⎝ ⎠ < <
=
⎢ ⎥
⎛ ⎞ ⎣ ⎦
⎜ ⎟
⎝ ⎠
(12)
Учитывая, что 0,5(
l
–
k
–
1
)
<
,
s
m
⎛ ⎞
⎜ ⎟
⎝ ⎠
получаем, что и выражение (9),
и (8) отличаются от (1) не более, чем на
127
96
2(
) 2
2 .
l k
−
−
− ⋅
<
Таким образом, при интересных на практике значениях парамет-
ров матриц, вероятность наличия среди
l
строк не менее
k
строк, все
единицы которых содержатся в заданных
s
столбцах, можно вычис-
лить по следующей формуле:
.
n
s
k
m m
l k
k
p
n
m
l
⎛
⎞ ⎛
⎞
⎛ ⎞
⎛ ⎞
− ⎜
⎟ ⎜
⎟
⎜ ⎟
⎜ ⎟
⎝ ⎠
⎝ ⎠
⎜
⎟ ⎜
⎟
⎜
⎟ ⎜
⎟
− ⎝
⎠ ⎝
⎠
≈
⎛
⎞ ⎛ ⎞
⎜
⎟ ⎜ ⎟
⎝ ⎠ ⎜
⎟
⎜
⎟
⎝
⎠
(13)
Отметим,что верность этого утверждения зависит от соотноше-
ния размера матрицы
n
,
веса строки
m
и количества вычислитель-
ных узлов
Np
,
kN
p
=
n
.
Оценка сложности заведомо применима, если
2
m
<=
N
p
и
n
>>
m
.
Представляет интерес анализ функции (13), однако не всегда пред-
ставляется возможным, вычислить ее в нужных точках. Для упроще-
ния вычисления функции были выполнены некоторые преобразова-
ния, описываемые далее.
Представим знаменатель выражения (13) в следующем виде:
1
0
!
l
i
n i
n
m
m
l
l
−
=
⎡
⎤
⎛ ⎞ − ⎜ ⎟
⎛
⎞
⎢
⎥
⎛ ⎞
⎝ ⎠ ⎣
⎦
⎜ ⎟ ⎜
⎟ = ⎝ ⎠ ⎜
⎟
⎝
⎠
∏
(14)
и выразим отношение первого сомножителя числителя к знаменате-
лю, воспользовавшись формулой (8):