Математика МАТЕМАТИКА УДК 519.718 М. А. Алехина, А. В. Рыбаков СИНТЕЗ И СЛОЖНОСТЬ АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫХ ПО НАДЕЖНОСТИ КЛЕТОЧНЫХ СХЕМ1 Аннотация. <...> Работа относится к одному из важнейших разделов математической кибернетики – теории синтеза, надежности и сложности управляющих систем. <...> Эти схемы как из абсолютно надежных, так и ненадежных элементов изучаются давно, для них получено большое число результатов. <...> Однако в реальных схемах приходится учитывать не только функционирование элементов, но и геометрию схемы. <...> В связи с этим была предложена модель клеточных схем из функциональных элементов, где схема представляется в виде прямоугольника, разделенного на клетки, в которых располагаются элементы схемы, имеющие определенные размеры и занимающие некоторую площадь. <...> Клеточные элементы могут быть как функциональными, т.е. реализующими какую-то функцию от своих входов, так и коммутационными, которые служат для передачи сигнала к следующему элементу с возможным изменением направления. <...> В работе предполагается, что коммутационные элементы абсолютно надежны, а на любом из двух выходов каждого из функциональных элементов с одной и той же вероятностью независимым образом появляются инверсные неисправности. <...> Такие схемы являются естественной математической моделью интегральных схем, в связи с чем имеют множество приложений в различных разделах науки и техники и являются актуальными для исследований. <...> Цель работы – построить асимптотически оптимальные по надежности клеточные схемы и оценить их сложность. <...> Для этого метода были построены клеточные схемы, доказаны соответствующие теоремы о верхней и нижней оценках ненадежности и оценена сложность построенных схем. <...> Получены верхняя и нижняя оценки ненадежности этих схем. <...> Впервые доказана оценка сложности асимптотически оптимальных по надежности клеточных схем. <...> Для построения асимптотически оптимальных по надежности клеточных схем можно использовать <...>