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

Статья в сборнике "Математические вопросы кибернетики" №5, Москва, 1994
Авторы: Семенов А.А.
Сложность приближенной реализации булевых функций схемами из функциональных элементов
Аннотация:
В данной статье рассматривается проблема приближённой реализации булевых функций. Приближенная реализация булевых функций схемами из функциональных элементов понимается в смысле хэмминговых систем окрестностей (функции считаются близкими, если расстояние Хэмминга между ними мало). Изучены случаи сильной, средней и слабой определённости реализуемой булевой функции, соответствующие малой, средней и большой мощности окрестностей функций. Для каждого из этих случаев при различных дополнительных условиях получен единый результат: асимптотическая эквивалентность функции Шеннона и функции специального вида, зависящей от количества переменных реализуемой булевой функции, мощности хэмминговой системы окрестностей и приведённого веса конечного полного базиса.
Ключевые слова:
приближенная реализация булевых функций, схемы из функциональных элементов, хэмминговы системы окрестностей, функция Шеннона
Язык публикации: русский, страниц: 18 (с. 262-279)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст: Сведения об авторах:
  • Семенов Александр Анатольевич,  ,  Институт динамики систем и теории управления имени В.М. Матросова СО РАН