|
Среднее и дисперсия числа подфункций случайной булевой функции, близких к множеству аффинных функций
А. А. Серов Математический институт им. В. А. Стеклова РАН
Аннотация:
Для случайных равновероятных булевых функций изучается распределение количеств подфункций от заданного числа переменных, близких к множеству аффинных булевых функций. Показано, например, что для булевых функции от $n$ переменных математическое ожидание числа подфункций от $s\geqslant 3+\log_2 n$ переменных, расстояние Хэмминга от которых до множества аффинных функций меньше $2^{s-2}$, стремится к $0$ при $n\rightarrow\infty$.
Ключевые слова:
случайная булева функция, подфункция, аффинные булевы функции, расстояние Хэмминга.
Статья поступила: 17.02.2015
Образец цитирования:
А. А. Серов, “Среднее и дисперсия числа подфункций случайной булевой функции, близких к множеству аффинных функций”, Дискрет. матем., 27:3 (2015), 108–122; Discrete Math. Appl., 27:1 (2017), 23–34
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1338https://doi.org/10.4213/dm1338 https://www.mathnet.ru/rus/dm/v27/i3/p108
|
Статистика просмотров: |
Страница аннотации: | 470 | PDF полного текста: | 149 | Список литературы: | 53 | Первая страница: | 26 |
|