Данный сайт более не обновляется.
Актуальная информация - по адресу vestnik.math.msu.su

УДК 519.95

О сложности самокорректирующихся схем для одной последовательности булевых функций / В. М. Краснов // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2009. № 5. С. 55-57.

Рассматриваются k-самокорректирующиеся схемы из функциональных элементов в базисе {&, -}. Предполагается, что константные неисправности на выходах элементов однотипные. Инверторы предполагаются надежными. Вес каждого инвертора равен 1. Конъюнкторы могут быть надежными и ненадежными. Каждый надежный конъюнктор реализует конъюнкцию двух переменных и имеет вес p > k+2. Каждый ненадежный конъюнктор в исправном состоянии реализует конъюнкцию, а в неисправном - булеву константу δ (δ∈{0,1}). Вес каждого ненадежного конъюнктора равен 1. Установлено, что сложность реализации такими схемами монотонных пороговых симметрических функций f₂ⁿ(x₁,...,x_n) = V_1≤i<j≤nx_ix_j, n= 3,4,..., асимптотически равна (k+3)·n.

Ключевые слова: схемы из функциональных элементов, сложность схемы, булевы функции.

Библиогр. 4.