Список выпусков > Серия «Математика». 2026. Том 57
О сложности линейной функции
алгебры логики в некоторых классах
обобщенных контактных схем
Автор(ы)
Е. К. Михалев, С. А. Ложкин
Московский государственный университет им. М. В. Ломоносова, Москва, Российская Федерация
Аннотация
Рассматривается класс обобщенных контактных схем ранга 𝑟, в котором контактами управляют только линейные функции алгебры логики, зависящие
не более чем от 𝑟 булевых переменных, а также два его подкласса с дополнительными ограничениями на расположение контактов. Исследуется сложность реализации
линейной функции алгебры логики 𝑙𝑛 от 𝑛 булевых переменных в указанных классах обобщенных контактных схем. При фиксированном 𝑟 и 𝑛 = 1, 2, ... получены
верхняя и нижняя оценки сложности реализации 𝑙𝑛 в каждом из двух указанных
выше подклассов рассматриваемого класса обобщенных контактных схем. При этом
в первом подклассе полученные оценки асимптотически равны 4𝑛𝑟 и отличаются друг от друга на величину 𝑂(√︀𝑛𝑟), а во втором подклассе дают ее точное значение
вида 4⌈𝑛𝑟⌉ − 4.
Об авторах
Михалев Евгений Константинович, студент, Московский государственный университет им. М. В. Ломоносова, Москва, 119991, Российская Федерация, genya.mikhalev@gmail.com
Ложкин Сергей Андреевич, д-р физ.-мат. наук, проф., Московский государственный университет им. М. В. Ломоносова, Москва, 119991, Российская Федерация, lozhkin@cs.msu.ru
Ссылка для цитирования
Михалев Е. К., Ложкин С. А. О сложности линейной
функции алгебры логики в некоторых классах обобщенных контактных схем //
Известия Иркутского государственного университета. Серия Математика. 2026. Т.
57. C. 128–142.
https://doi.org/10.26516/1997-7670.2026.57.128
Ключевые слова
обобщенная контактная схема, линейная функция алгебры логики, сложность
УДК
519.71
MSC
06E30, 05C99
DOI
https://doi.org/10.26516/1997-7670.2026.57.128
Литература
- Вороненко А. А. Об одном свойстве линейных булевых функций // Вестник Московского университета. Серия 15: Вычислительная математика и кибернетика. 2021. № 2, С. 43–44
- Ложкин С. А., Кошкин Н. А. О сложности реализации некоторых систем функций алгебры логики контактными и обобщёнными контактными схемами // Lecture Notes in Computer Science. 1987. Т. 28, С. 293–296
- Ложкин С. А., Кошкин Н. А. О сложности реализации некоторых систем функций алгебры логики контактными многополюсниками // Докл. АН СССР 1988. Т. 298, № 4, С. 807–811
- Ложкин С. А. Лекции по основам кибернетики. М.: МГУ, 2004. 253 с.
- Ложкин С. А., Михалев Е. К. О сложности линейной функции алгебры логики в некоторых классах обобщенных контактных схем // Прооблемы теоретической кибернетики: материалы XX Международной научной конференции (Москва 5–8 декабря 2024г.) М.:МАКС Пресс. 2025. С. 82–84 https://doi.org/10.29003/m4678.978-5-317-07402-9
- Подольская О. В. Сложность линейных функций и функции голосования в базисе антицепных функций // Вестник Московского университета. Серия 1: Математика, механика. 2016. Т. 71, № 2, С. 51–52 https://doi.org/10.3103/S002713221602008X
- Романов Д. С., Романова Е. Ю. О единичных проверяющих тестах для схем переключательного типа // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. 2015. № 1 (33). С. 5–23
- Романов Д. С., Романова Е. Ю. О единичных проверяющих тестах константной длины для обобщённых итеративных контактных схем // Вестник Московского университета. Серия 15: Вычислительная математика и кибернетика. 2015. № 3. С. 42–50.
- Рычков К. Л. О сложности обобщённых контактных схем. Дискретн. анализ и исслед. опер., 16:5, 2009. C. 78-–87
- Чашкин А. В. О сложности одной системы линейных булевых функций // Вестник Московского университета. Серия 1: Математика, механика. 2025. № 2, С. 76–79 https://doi.org/10.3103/S0027132225700329
- Яблонский С. В. Элементы математической кибернетики. М.: Высшая школа, 2007. 191 с.
- Cardot C. Quelques r`ezultats sur l’application de l’alg`ebre de Boole `a la synth`ese des circuits `a relais. // Ann. Telecomm. 1952. Vol. 7, N. 2. P. 75–84.