?
О сложности реализации симметрических булевых функций в одном бесконечном базисе
С. 56-58.
Подольская О. В.
Доказано, что сложность реализации произвольной симметрической булевой функции f от n переменных для f не равной тождественно единице при реализации схемами в базисе антицепных функций, т.е. функций, принимающих значение 1 лишь на попарно несравнимых наборах, равна min(k(f),n-k(f)+2), где k(f) - количество слоев, на которых функция f равна 1.
В книге
М. : Издательство ИПМ РАН, 2015
Подольская О. В., В кн. : Материалы IX молодежной научной школы по дискретной математике и ее приложениям (Москва, 16-21 сентября 2013 г.). : М. : Издательство ИПМ РАН, 2013. С. 97-100.
В работе рассматривается задача о сложности реализации булевых функций схемами из функциональных элементов в бесконечном полном базисе, который состоит из всевозможных булевых функций, принимающих единичное значение лишь на попарно несравнимых наборах. Известны нижние оценки порядка $\sqrt n$ для сложности реализации линейной функции, функции голосования и почти всех булевых функций от $n$ переменных. Установлена верхняя оценка ...
Добавлено: 31 мая 2015 г.
Kochergin V.V., Mikhailovich A.V., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2018 Vol. 12 No. 1 P. 40-58
Добавлено: 11 марта 2018 г.
Кочергин В. В., Михайлович А. В., В кн. : Проблемы теоретической кибернетики. Материалы заочного семинара XIX международной конференции. : Издательство Казанского (Приволжского) федерального университета, 2021. С. 75-78.
В работе исследуется сложность реализации функций многозначной логики над базисами, содержащими все монотонные функции и конечное число немонотонных функций. Получены верхняя и нижняя оценка, отличающиеся на константу, не зависящую от базиса. ...
Добавлено: 6 декабря 2021 г.
V.V. Kochergin, A.V. Mikhailovich, Computational Mathematics and Modeling 2019 Vol. 30 No. 1 P. 13-25
Добавлено: 22 апреля 2019 г.
Михайлович А. В., В кн. : Материалы 5-й Российской школы-семинара "Синтаксис и семантика логических систем". : Улан-Удэ : Издательство Бурятского госуниверситета, 2017. С. 91-95.
В работе описана решётка всех замкнутых классов, содержащихся в замыкании всех функций из примеров Ю. И. Янова и А. А. Мучника. ...
Добавлено: 22 сентября 2017 г.
Кочергин В. В., Михайлович А. В., Дискретный анализ и исследование операций 2018 Т. 25 № 1 С. 42-74
Исследуется сложность реализации функций k-значной логики (k > 2) схемами из функциональных элементов в бесконечном базисе, состоящем из отрицания Поста, т.е. функции x+1 (mod k), и всех монотонных функций. Под сложностью понимается общее число элементов в схеме. Для произвольной функии f установлены отличающиеся друг от друга не более чем на единицу нижняя и верхняя оценки ...
Добавлено: 28 сентября 2017 г.
Михайлович А. В., В кн. : Материалы XVIII международной конференции "Проблемы теоретической кибернетики" (Пенза, 19-23 июня 2017 г.). : М. : МАКС Пресс, 2017. С. 166-168.
В работе описаны все замкнутые классы функций многозначной логики, содержащиеся в классе из примера А. А. Мучника замкнутого класса со счётным базисом. ...
Добавлено: 21 сентября 2017 г.
V.V. Kochergin, A.V. Mikhailovich, Mathematical notes 2019 Vol. 105 No. 1 P. 28-35
Добавлено: 22 апреля 2019 г.
Кочергин В. В., Чебышевский сборник 2022 Т. 23 № 2(83) С. 121-150
В работе предпринята попытка не только дать обзор результатов, полученных
О. М. Касим–Заде, крупнейшим специалистом по дискретной математике и математической кибернетике, но и осознать его научное наследие в таких направлениях как исследование мер схемной сложности булевых функций, связанных с функционированием схем,
проблематика неявной и параметрической выразимости в конечнозначных логиках, вопросы глубины и сложности булевых функций и функций ...
Добавлено: 29 октября 2022 г.
Подольская О. В., Вестник Московского университета. Серия 1: Математика. Механика 2013 Т. 2 С. 17-23
Антицепной функцией называется характеристическая функция антицепи в булевом кубе. Множество всех антицепных функций образует бесконечный полный базис. В работе изучается сложность реализации булевых функций схемами в этом базисе. Доказаны нижние оценки порядка $\sqrt n$ для сложности реализации линейной функции, функции голосования и почти всех функций от $n$ переменных. ...
Добавлено: 30 мая 2015 г.
Михайлович А. В., Кочергин В. В., В кн. : Материалы XIII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова. : Изд-во механико-математического факультета МГУ, 2019. С. 129-131.
Добавлено: 7 декабря 2021 г.
Кочергин В. В., Михайлович А. В., Прикладная дискретная математика 2015 № 4 С. 24-31
Исследуется сложность реализации булевых функций и систем булевых функций схемами в базисе, состоящем из элементов двух сортов. Элементами первого сорта являются произвольные монотонные функции, таким элементам приписан нулевой вес. Конечное число немонотонных функций образует непустое множество элементов второго сорта, каждой такой функции приписан положительный вес. Для случая, когда отрицание является единственным элементом второго сорта, А. ...
Добавлено: 8 декабря 2015 г.
Ольшанский Г. И., Journal of Combinatorial Theory, Series A 2019 Vol. 162 P. 65-117
Добавлено: 25 мая 2019 г.
Ольшанский Г. И., Функциональный анализ и его приложения 2017 Т. 51 № 3 С. 56-76
Хорошо известно, как по произвольной системе ортогональных полиномов на прямой построить систему симметрических ортогональных полиномов от произвольного конечного числа переменных. В специальном случае больших полиномов q-Якоби число переменных удается сделать бесконечным. В результате возникает неоднородный базис в алгебре симметрических функций, элементы которого ортогональны по некоторой вероятностной мере. Эта мера определена на некотором пространстве бесконечных точечных ...
Добавлено: 26 декабря 2017 г.
Захаров В. А., Варновский Н. П., Шокуров А. В., Вестник Московского университета. Серия 15: Вычислительная математика и кибернетика 2017 № 1 С. 38-44
Рассматриваются простейшие математические модели баз конфиденциальных данных в системах облачных вычислений. Для этих моделей предложено понятие дедуктивной безопасности запросов к базам данных. Установлены необходимые и достаточные условия дедуктивной безопасности и описаны некоторые классы запросов, удовлетворяющие этим условиям. ...
Добавлено: 13 октября 2016 г.
Максимов Ю. В., Doklady Mathematics 2012 Vol. 86 No. 3 P. 854-856
Добавлено: 30 октября 2015 г.
Ольшанский Г. И., Cuenca C., Moscow Mathematical Journal 2020 Vol. 20 No. 4 P. 645-694
Добавлено: 19 января 2021 г.
Кочергин В. В., Михайлович А. В., Ученые записки Казанского университета. Серия: Физико-математические науки 2020 Т. 162 № 3 С. 311-321
Исследована задача о сложности реализации функций многозначной логики логическими схемами в базисе, состоящем из элементов двух типов. Элементами первого типа являются произвольные монотонные (относительно стандартного порядка) функции, таким элементам приписан нулевой вес. Конечное число немонотонных функций образует непустое множество элементов второго типа, каждой такой функции приписан единичный вес. Установлены верхняя и нижняя оценки немонотонной сложности ...
Добавлено: 6 декабря 2021 г.
Максимов Ю. В., / Cornell University. Series arXiv "math". 2015.
Добавлено: 30 октября 2015 г.
Ульянов В. В., Goetze F., A. Naumov, Journal of Theoretical Probability 2017 Vol. 30 No. 3 P. 876-897
In this paper we consider asymptotic expansions for a class of sequences of symmetric functions of many variables. Applications to classical and free probability theory are discussed. ...
Добавлено: 17 марта 2016 г.
A.V. Mikhailovich, V. V. Kochergin, / Cornell University. Series math "arxiv.org". 2015.
Добавлено: 15 июня 2015 г.
Высоцкий Л. И., Жуков В. В., Шуплецов М. С., В кн. : Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС-2018). Вып. 1.: М. : ИППМ РАН, 2018. С. 30-37.
При обнаружении ошибок или изменении
спецификации
проектируемой
сверхбольшой
интегральной схемы (СБИС) на поздних этапах
маршрута проектирования откат на более ранние этапы
проектирования и их повторное выполнение очень часто
становится непрактичным в силу существенных
временных затрат. Для целей сокращения времени
проектирования
в
современные
маршруты
проектирования интегрируют специальные этапы
функциональной коррекции схемы (англ. Engineering
Change Order, ECO). В основе указанного подхода лежит
анализ уже спроектированной схемы и построение
небольшой подсхемы-заплатки, внедрение которой в уже
синтезированную ...
Добавлено: 10 ноября 2020 г.
Максимов Ю. В., Computational Mathematics and Mathematical Physics 2015 Vol. 55 No. 7 P. 1242-1255
Добавлено: 30 октября 2015 г.
Gottlob G., Kikot S., Kontchakov R. и др., Artificial Intelligence 2014 Vol. 213 P. 42-59
Добавлено: 24 марта 2015 г.