?
Об оценках сложности схем в одном бесконечном базисе
С. 97–100.
Подольская О. В.
В работе рассматривается задача о сложности реализации булевых функций схемами из функциональных элементов в бесконечном полном базисе, который состоит из всевозможных булевых функций, принимающих единичное значение лишь на попарно несравнимых наборах. Известны нижние оценки порядка $\sqrt n$ для сложности реализации линейной функции, функции голосования и почти всех булевых функций от $n$ переменных. Установлена верхняя оценка $n$ для сложности реализации произвольной булевой функции от $n$ переменных.
В книге
М.: Издательство ИПМ РАН, 2013.
V. V. Kochergin, A. V. Mikhailovich, Mathematical notes 2025 Vol. 117 No. 4 P. 579–594
Добавлено: 28 февраля 2026 г.
Добавлено: 30 июня 2025 г.
Кочергин В. В., Михайлович А. В., Математические заметки 2025 Т. 117 № 4 С. 523–542
Для каждой булевой функции установлено точное значение сложности реализации логическими схемами в бесконечном базисе, состоящем из отрицания и всех монотонных булевых функций. Под сложностью функции понимается минимально возможное число элементов базиса, достаточное для построения схемы для данной функции. ...
Добавлено: 8 апреля 2025 г.
Бурков А. А., Тюрликов А. М., Вопросы радиоэлектроники. Серия: Техника телевидения 2020 № 1 С. 74–83
Рассмотрена система передачи с гибридной решающей обратной связью при наличии медленных релеевских замираний. Описана методика для нахождения верхней оценки спектральной эффективности для такой системы при ограничении на вид модуляции. ...
Добавлено: 26 сентября 2023 г.
Кочергин В. В., Чебышевский сборник 2022 Т. 23 № 2(83) С. 121–150
В работе предпринята попытка не только дать обзор результатов, полученных
О. М. Касим–Заде, крупнейшим специалистом по дискретной математике и математической кибернетике, но и осознать его научное наследие в таких направлениях как исследование мер схемной сложности булевых функций, связанных с функционированием схем,
проблематика неявной и параметрической выразимости в конечнозначных логиках, вопросы глубины и сложности булевых функций и функций ...
Добавлено: 29 октября 2022 г.
Burkov A. A., Shneer S., Turlikov A. M., , in: WAVE ELECTRONICS AND ITS APPLICATION IN INFORMATION AND TELECOMMUNICATION SYSTEMS. 2021. (WECONF 2021) St. Petersburg, Russia, 31 May - 4 June 2021.: IEEE, 2021. Ch. 9470700 P. 1–8.
Добавлено: 28 октября 2022 г.
Михайлович А. В., Кочергин В. В., В кн.: Материалы XIII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова.: Изд-во механико-математического факультета МГУ, 2019. С. 129–131.
Добавлено: 7 декабря 2021 г.
Кочергин В. В., Михайлович А. В., В кн.: Проблемы теоретической кибернетики. Материалы заочного семинара XIX международной конференции.: Издательство Казанского (Приволжского) федерального университета, 2021. С. 75–78.
В работе исследуется сложность реализации функций многозначной логики над базисами, содержащими все монотонные функции и конечное число немонотонных функций. Получены верхняя и нижняя оценка, отличающиеся на константу, не зависящую от базиса. ...
Добавлено: 6 декабря 2021 г.
Кочергин В. В., Михайлович А. В., Ученые записки Казанского университета. Серия: Физико-математические науки 2020 Т. 162 № 3 С. 311–321
Исследована задача о сложности реализации функций многозначной логики логическими схемами в базисе, состоящем из элементов двух типов. Элементами первого типа являются произвольные монотонные (относительно стандартного порядка) функции, таким элементам приписан нулевой вес. Конечное число немонотонных функций образует непустое множество элементов второго типа, каждой такой функции приписан единичный вес. Установлены верхняя и нижняя оценки немонотонной сложности ...
Добавлено: 6 декабря 2021 г.
Высоцкий Л. И., Жуков В. В., Шуплецов М. С., В кн.: Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС-2018)Вып. 1.: М.: ИППМ РАН, 2018. С. 30–37.
При обнаружении ошибок или изменении
спецификации
проектируемой
сверхбольшой
интегральной схемы (СБИС) на поздних этапах
маршрута проектирования откат на более ранние этапы
проектирования и их повторное выполнение очень часто
становится непрактичным в силу существенных
временных затрат. Для целей сокращения времени
проектирования
в
современные
маршруты
проектирования интегрируют специальные этапы
функциональной коррекции схемы (англ. Engineering
Change Order, ECO). В основе указанного подхода лежит
анализ уже спроектированной схемы и построение
небольшой подсхемы-заплатки, внедрение которой в уже
синтезированную ...
Добавлено: 10 ноября 2020 г.
Данилов Б. Р., Известия высших учебных заведений. Поволжский регион. Физико-математические науки 2014 Т. 3 № 31 С. 78–100
Актуальность и цели
Проблема синтеза дискретных управляющих систем является одной из основных проблем математической кибернетики. В общем виде она состоит в построении для заданной дискретной функции ее оптимальной (в том или ином смысле) структурной реализации в рассматриваемом классе управляющих систем. Теоретические результаты, полученные при решении указанной проблемы, находят применение в различных прикладных областях, к числу которых ...
Добавлено: 2 декабря 2019 г.
Данилов Б. Р., Известия высших учебных заведений. Поволжский регион. Физико-математические науки 2015 Т. 4 № 36 С. 58–77
Актуальность и цели
Проблема синтеза дискретных управляющих систем является одной из основных проблем математической кибернетики. В общем виде она состоит в построении для заданной дискретной функции ее оптимальной (в том или ином смысле) структурной реализации в рассматриваемом классе управляющих систем. Теоретические результаты, полученные при решении указанной проблемы, находят применение в различных прикладных областях, к числу которых ...
Добавлено: 2 декабря 2019 г.
Данилов Б. Р., Ложкин С. А., Прикладная математика и информатика 2018 № 59 С. 40–49
В работе предлагается метод синтеза усилительных схем из функциональных элементов (УСФЭ), позволяющий установить асимптотику функции Шеннона для обобщённой глубины УСФЭ – то есть глубины самой «плохой» функции алгебры логики, зависящей от заданных переменных – в специальном базисе (модели глубины), где глубина элемента определяется как его типом, так и степенью ветвления выхода в схеме. Асимптотическое поведение ...
Добавлено: 2 декабря 2019 г.