|
Труды по дискретной математике, 2000, том 3, страницы 21–28
(Mi tdm34)
|
|
|
|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
Системы случайных булевых уравнений со случайным выбором неизвестных в каждом уравнении
Г. В. Балакин
Аннотация:
Рассматриваются системы случайных булевых уравнений вида $\varphi_i(x_{r_{i1}}\dots,s_{r_{is}})=a_i$, $i=1,\dots,t$, относительно неизвестных $x_1,\dots,x_n$, где функции $\varphi_i(y_1,\dots,y_s)$ выбираются случайно и равновероятно из множества всех булевых функций от $s$ переменных, а наборы индексов $(r_{i1},\dots,r_{is})$ для разных уравнений независимы и получаются по схеме равновероятного выбора с возвращением из множества $\{1,\dots,n\}$. Для случая, когда правые части $a_1,\dots,a_t$ систем независимы и равновероятны, найдены асимптотические формулы для математического ожидания числа решений и оценки для вероятности совместности системы уравнений. Для случая, когда $a_i=\varphi_i(x_{i_{i1}}^0,\dots,x_{i_{is}}^0)$, $i=1,\dots,t$, для некоторого фиксированного вектора $\bar x^0=(x_1^0,\dots,x_n^0)$, найдены асимптотики математического ожидания и предельные распределения числа решений.
Образец цитирования:
Г. В. Балакин, “Системы случайных булевых уравнений со случайным выбором неизвестных в каждом уравнении”, Тр. по дискр. матем., 3, Физматлит, М., 2000, 21–28
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/tdm34 https://www.mathnet.ru/rus/tdm/v3/p21
|
Статистика просмотров: |
Страница аннотации: | 284 | PDF полного текста: | 117 |
|