?
Сложность линейных функций и функции голосования в базисе антицепных функций
Вестник Московского университета. Серия 1: Математика. Механика. 2016. № 2. С. 51–52.
Подольская О. В.
Изучается сложность реализации булевых функций схемами из функциональных элементов в базисе, состоящем из всех характеристических функций антицепей булева куба. Установлено, что сложность реализации функции четности от $n$ переменных есть $\lfloor \frac{n+1}{2} \rfloor,$ сложность ее отрицания равна сложности функции голосования от $n$ переменных и составляет $\lceil \frac{n+1}{2} \rceil$.
Язык:
русский
Михайлович А. В., Кочергин В. В., XXI век: итоги прошлого и проблемы настоящего плюс 2017 № 4(38) С. 98–105
Рассматривается задача об экономной реализации булевых функций и функций многозначной логики схемами из функциональных элементов в бесконечном базисе, состоящем из всех монотонных и конечного числа немонотонных функций, причем мерой качества реализации является немонотонная сложность — число использований немонотонных элементов (монотонные функции «бесплатны»). Для случая реализации систем булевых функций в базисе, содержащем помимо монотонных функций только ...
Добавлено: 28 сентября 2017 г.
Подольская О. В., В кн.: Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.).: М.: Изд-во механико-математического факультета МГУ, 2016. С. 150–152.
В работе изучается сложность реализации булевых функций схемами из функциональных элементов в двух бесконечных полных базисах. Первый базис состоит из линейных и антицепных функций от любого числа переменных. В этом базисе установлена верхняя оценка сложности реализации произвольной булевой функции от n переменных порядка (logn)*n^{1/2}. Также в этом базисе доказана нижняя оценка порядка n^{1/2} наибольшей сложности ...
Добавлено: 14 марта 2017 г.
Подольская О. В., Дискретная математика 2015 Т. 27 № 3 С. 95–107
Изучается сложность реализации булевых функций схемами из функциональных элементов в бесконечном базисе, состоящем из всех характеристических функций антицепей на булевом кубе. Установлено точное значение сложности реализации произвольной симметрической функции схемами в этом базисе. В частности, для функций четности и голосования от $n$ переменных при всех натуральных $n\geq1$ получены точные значения сложности: $\lfloor \frac{n+1}{2} \rfloor$ и ...
Добавлено: 14 марта 2017 г.
Нижняя оценка мощности области определения универсальных функций для класса линейных булевых функций
Вялый М. Н., Вороненко А. А., Дискретная математика 2016 Т. 28 № 4 С. 50–57
Доказана нетривиальная нижняя оценка (2+1/6)n для мощности области определения универсальной функции для класса линейных булевых функций, где n — число переменных. ...
Добавлено: 13 января 2017 г.
Кочергин В. В., Михайлович А. В., Прикладная дискретная математика 2015 № 4 С. 24–31
Исследуется сложность реализации булевых функций и систем булевых функций схемами в базисе, состоящем из элементов двух сортов. Элементами первого сорта являются произвольные монотонные функции, таким элементам приписан нулевой вес. Конечное число немонотонных функций образует непустое множество элементов второго сорта, каждой такой функции приписан положительный вес. Для случая, когда отрицание является единственным элементом второго сорта, А. ...
Добавлено: 8 декабря 2015 г.
Подольская О. В., Вестник Московского университета. Серия 1: Математика. Механика 2013 Т. 2 С. 17–23
Антицепной функцией называется характеристическая функция антицепи в булевом кубе. Множество всех антицепных функций образует бесконечный полный базис. В работе изучается сложность реализации булевых функций схемами в этом базисе. Доказаны нижние оценки порядка $\sqrt n$ для сложности реализации линейной функции, функции голосования и почти всех функций от $n$ переменных. ...
Добавлено: 30 мая 2015 г.
Дюсуше О. М., Экономический журнал Высшей школы экономики 2006 Т. 10 № 1 С. 3–32
В классе линейных функций спроса и издержек фирм исследуется проблема статичного равновесия Курно с использованием некооперативных статических и стратегических рефлексивных игр различных порядков. В статье вводятся: концепция конкурентоспособности фирмы в равновесии Курно для n фирм; определение предположительных вариаций как первых производных от функций постоянной прибыли Штакельберга; и понятие последовательно-группового порядка в игре n персон. Анализируются ...
Добавлено: 19 октября 2012 г.