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

Статья в сборнике "Математические вопросы кибернетики" №15, Москва, 2006
Авторы: Красулина Е.Г.
О сложности реализации системы всех симметрических функций в классе контактно-вентильных схем
Аннотация:
В настоящей работе рассматривается задача реализации всех симметрических функций в классе контактно-вентильных схем. Строится асимптотически минимальная контактно-вентильная схема, реализующая все симметрические функции. Доказано, что для реализации всех симметрических функций от n переменных контактно-вентильной схемой требуется асимптотически 7 ·2n-1 элементов.
Ключевые слова:
симметрические функции, контактно-вентильные схемы, теория сложности
Язык публикации: русский,  страниц: 18 (с. 165-182)
Полный текст на русском языке: Сведения об авторах:
  • Красулина Елена Геннадьевна,  ,  Математический институт им. В. А. Стеклова РАН