Система булевых функций n переменных называется рандомизированной, если функции сохраняют свойство своих переменных быть независимыми и равномерно распределенными случайными величинами. Такая система называется t-устойчивой, если при любой замене константами любых i переменных, где 0 ≤ i ≤ t, полученная система функций n-i переменных будет также рандомизированной. Исследуется задача нахождения максимального числа N(n,t,T) функций n переменных, любые T из которых образуют t-устойчивую систему. Эта задача сводится к минимизации размера определенных комбинаторных дизайнов, которые мы называем разделенными ортогональными списками. Для получения верхних и нижних границ N(n,t,T) мы обобщаем некоторые результаты теории кодов и дизайнов, в частности, дуальность в оценивании оптимальных размеров кодов и дизайнов. В некоторых случаях эти границы оказались очень точными. В частности, для некоторой бесконечной последовательности n они позволяют доказать, что N(n,3,3)=2^n-2/n, N(n,3,5)=√(2^n-1/n), N(n,3,n/2-1)=n, N(n,n/2-1,3)=n, N(n,n/2-1,5)=√(2n).

код, дизайн, булевы функции, рандомизация, устойчивость, верхние и нижние границы.

Математические вопросы и теория численных методов