|
Вестник Московского университета. Серия 1: Математика. Механика, 2015, номер 5, страницы 47–50
(Mi vmumm268)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Краткие сообщения
Верхняя оценка сложности реализации линейных функций схемами в одном базисе из многовходовых элементов
Ю. А. Комбаров Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
Аннотация:
Заметка посвящена реализации линейных булевых функций схемами из функциональных элементов в базисе $U_\infty$, состоящем из всех элементов, реализующих функции вида $(x_1^{\sigma_1}\&\ldots \& x_k^{\sigma_k})^{\beta}$. Описан способ построения схем, реализующих линейную функцию от $n$ переменных со сложностью $\lfloor (7n-4)/3\rfloor$. Тем самым улучшена предыдущая известная верхняя оценка сложности линейных функций в базисе $U_\infty$, составляющая $\lceil (5n-1)/2\rceil$. Также для очень малых $n$ ($n<7$) проверена минимальность построенных схем.
Ключевые слова:
схемы из функциональных элементов, сложность схем, линейная булева функция, минимальная схема.
Поступила в редакцию: 11.06.2014
Образец цитирования:
Ю. А. Комбаров, “Верхняя оценка сложности реализации линейных функций схемами в одном базисе из многовходовых элементов”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2015, № 5, 47–50; Moscow University Mathematics Bulletin, 70:5 (2015), 226–229
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vmumm268 https://www.mathnet.ru/rus/vmumm/y2015/i5/p47
|
Статистика просмотров: |
Страница аннотации: | 137 | PDF полного текста: | 103 | Список литературы: | 23 |
|