О СЛОЖНОСТИ МУЛЬТИПЛЕКСОРНОЙ ФУНКЦИИ В КЛАССЕ ФОРМУЛ |
5 | |
2012 |
научная статья | 519.714 | ||
38-41 | мультиплексорная функция, формулы, индивидуальная сложность |
Рассматривается задача синтеза формул для мультиплексорной функции алгебры логики, которая часто является составной частью интегральных схем, а также используется в теоретических исследованиях. В стандартном базисе устанавливаются оценки сложности реализации мультиплексорной функции от n адресных переменных, близкие к асимптотическим оценкам высокой степени точности, вида 2 |
1 . Лупанов О.Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984. 2 . Ложкин С.А. Лекции по основам кибернетики. М.: Издательский отдел ф-та ВМиК МГУ, 2004. 3 . Коровин В.В. О сложности реализации универсальной функции схемами из функциональных элементов // Дискретная математика. 1995. Т. 7. Вып. 2. С. 95–102. 4 . Румянцев П.В. О сложности реализации мультиплексорной функции схемами из функциональных элементов // Проблемы теоретической кибернетики. Тезисы докладов XIV Международной конференции (Пенза, 23–28 мая 2005 г.). М.: Изд-во мех.-мат. факультета МГУ, 2005. С. 133. 5 . Ложкин C.А., Власов Н.В. О сложности мультиплексорной функции в классе ?-схем // Ученые записки Казан. ун-та. Сер. Физ.-матем. науки. 2009. Т. 151. Кн. 2. С. 98–106. 6 . Ложкин С.А. О синтезе формул, сложность и глубина которых не превосходят асимптотически наилучших оценок высокой степени точности // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. 2007. № 3. С. 20–26. 7 . Ложкин C.А., Власов Н.В. О глубине муль-типлексорной функции // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2011. №2. С. 40–46. 8 . Власов Н.В. О сложности мультиплексорной функции в классе формул // Проблемы теорети-ческой кибернетики. Материалы XVI Международ-ной конференции (Нижний Новгород, 20–25 июня 2011 г.). Н.Новгород: Изд-во Нижегородского гос-университета, 2011. С. 96–97. |