Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №14, Москва, 2005
Авторы: Редькин Н.П.
Минимальные самокорректирующиеся схемы для оператора поразрядного сравнения булевых наборов
Аннотация:
Рассматриваются 1-самокорректирующиеся схемы из функциональных элементов в базисе Б = {&, V, —}, каждая из которых реализует одну и ту же булеву функцию как в исправном состоянии, так и при переходе в неисправное состояние любого одного ненадежного элемента. Каждый надежный элемент имеет вес Р и всегда реализует одну и ту же приписанную ему функцию из Б. Каждый ненадежный элемент имеет вес 1 и реализует в исправном состоянии некоторую приписанную ему функцию из Б, в неисправном состоянии — булеву константу δ. Пусть L(f) — наименьшая из сложностей 1-самокорректирующихся схем, реализующих булеву функцию f; под сложностью схемы понимается сумма весов элементов этой схемы. Для булевой функции sn(x, y) = (¬x1\/у1)&…&(¬xn\/уn) при n≥2, Р ≥3 и δ ϵ{0, 1} показано, что L(sn(x, y)) = 6n+P-2.
Ключевые слова:
функциональные элементы, самокорректирующиеся схемы, сложность
Язык публикации: русский, страниц: 16 (с. 19-34)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст: Сведения об авторах:
  • Редькин Николай Петрович,  ,  Механико-математический факультет МГУ, Кафедра дискретной математики