|
Труды по дискретной математике, 2000, том 3, страницы 235–248
(Mi tdm46)
|
|
|
|
Распределение вероятностей перманентов случайных матриц с независимыми элементами в поле $\mathrm{GF}(p)$
Б. А. Севастьянов
Аннотация:
В работе рассматриваются перманенты $\operatorname{per}(A_{nm})$ булевых матриц $A_{nm}=\|a_{ij}\|$, $n\ge m$, с независимыми одинаково распределенными элементами $a_{ij}$,
$\mathbf P\{a_{ij}=1\}=p_1$, $\mathbf P\{a_{ij}=0\}=p_0=1-p_1$. Получены предельные вероятности $\mathbf P\{\operatorname{per}(A_{nm}=1)\}$ как в схемах серий разреженных матриц, когда $n\to\infty$ $m=\operatorname{const}$, $p_1\to0$ и $np_1\to\lambda<\infty$ или $np^2_1\to\nu<\infty$, так и в схемах серий насыщенных матриц, когда $n\to\infty$, $m=\operatorname{const}$, $p_1\to0$ и либо $np_0^2\to\infty$, либо $np_0\to\nu<\infty$. Получены также предельные распределения перманентов матриц $A_{nm}$ с элементами из поля $\mathrm{GF}(p)$, где $p>2$ – простое число. Вычислена вероятность $\mathbf P\{\operatorname{per}(A_{nm}=1)\}$, когда $A_{nm}$ – булева матрица, $p_1=1/2$ и $m=n-1$. Показано, что число умножений и сложений в предложенной схеме вычисления перманентов матриц $A_{nm}$ в поле $\mathrm{GF}(p)$ при постоянном $m$ линейно зависит от $n$.
Образец цитирования:
Б. А. Севастьянов, “Распределение вероятностей перманентов случайных матриц с независимыми элементами в поле $\mathrm{GF}(p)$”, Тр. по дискр. матем., 3, Физматлит, М., 2000, 235–248
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/tdm46 https://www.mathnet.ru/rus/tdm/v3/p235
|
Статистика просмотров: |
Страница аннотации: | 165 | PDF полного текста: | 150 |
|