En Ru
Вход
ISSN: 0137-0782
ISSN: 0137-0782
En Ru
Расширенный поиск
О некоторых результатах кафедры математической кибернетики в области дискретных структур и сложности алгоритмов

О некоторых результатах кафедры математической кибернетики в области дискретных структур и сложности алгоритмов

Скачать в формате PDF

Поступила: 12.07.2024

Принята к публикации: 15.08.2024

Ключевые слова: k-значная логика, замкнутый класс, полином, алгебраическая сложность, алгоритм, сложность

DOI: 10.55959/MSU/0137-0782-15-2024-47-4-3-14

Для цитирования статьи

Алексеев В.Б., Марченков С.С., Селезнева С.Н. О некоторых результатах кафедры математической кибернетики в области дискретных структур и сложности алгоритмов // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2024. № 4. С. 3-14 https://doi.org/10.55959/MSU/0137-0782-15-2024-47-4-3-14.

Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция-Некоммерчески») 4.0 Всемирная
Номер 4, 2024
Алексеев В.Б. (Московский государственный университет им. М.В. Ломоносова (МГУ))
Марченков С.С. (Московский государственный университет им. М.В. Ломоносова (МГУ))
Селезнева С.Н. (Московский государственный университет им. М.В. Ломоносова (МГУ))

Аннотация

В работе приведены наиболее значимые результаты, полученные на кафедре математической кибернетики проф. В. Б. Алексеевым, проф. С. С. Марченковым и проф. С. Н. Селезневой, а также их аспирантами и студентами с начала 2000-х годов по настоящее время.

Литература

  1. М а р ч е н к о в С. С. Конечная порождаемость замкнутых классов булевых функций // Дискретный анализ и исследование операций. Сер. 1. 2005. 12. Вып. 1. С. 101-118.

  2. Л а р и о н о в В. Б. Замкнутые классы k-значной логики, содержащие классы монотонных или самодвойственных функций: Дис. . . . канд. физ.-мат. наук. М У. М., 2010.

  3. А л е к с е е в В. Б., В о р о н е н к о А. А. О некоторых замкнутых классах в частичной двузначной логике // Дискретная математика. 1994. 30. Вып. 2. С. 3-13.

  4. А л е к с е е в В. Б. О замкнутых классах в частичной k-значной логике, содержащих класс монотонных функций // Дискретная математика. 2021. 33. Вып. 2. С. 6-19.

  5. А л е к с е е в В. Б. О замкнутых классах в частичной k-значной логике, содержащих все полиномы // Дискретная математика. 2021. 6. Вып. 4. С. 58-79.

  6. A l e k s e e v V. B. On some intervals of partial clones // Journal of Multiple-Valued Logic and Soft Computing. 2022. 38. N 1-2. P. 3-22.

  7. А л е к с е е в В. Б. О мощности интервала Int(Polk) в частичной k-значной логике // Вестн. Моск. ун-та. Сер. 1. Матем. Мех. 2022. № 2. С. 11-17.

  8. А л е к с е е в В. Б. О некоторых замкнутых классах самодвойственных частичных многозначных функций // Ученые записки Казанского университета. Сер. Физ.-матем. науки. 2009. 151. № 2. С. 16-24.

  9. С е л е з н е в а С. Н. Описание замкнутого класса полиномиальных функций по модулю степени простого числа посредством отношения // Дискретная математика. 2023. 35. Вып. 4. С. 115-125.

  10. С е л е з н е в а С. Н. Описание замкнутого класса полиномиальных функций по модулю квадрата простого числа посредством отношения // Международная конференция «Математика в созвездии наук». К юбилею ректора МГУ Виктора Антоновича Садовничего: Тезисы докладов. М.: Изд-во Моск. ун-та, 2024. С. 344-345.

  11. С е л е з н е в а С. Н. О сложности представления функций многозначных логик поляризированными полиномами // Дискретная математика. 2002. 14. Вып. 2. С. 48-53.

  12. С е л е з н е в а С. Н. О сложности поляризованных полиномов функций многозначных логик, зависящих от одной переменной // Дискретная математика. 2004. 16. Вып. 2. С. 117-121.

  13. М а р к е л о в Н. К. Нижняя оценка сложности функций трехзначной логики в классе поляризованных полиномов // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2012. № 3. С. 40-45.

  14. Б а ш о в М. А., С е л е з н е в а С. Н. О длине функций k-значной логики в классе полиномиальных нормальных форм по модулю k // Дискретная математика. 2014. 26. Вып. 3. С. 3-9.

  15. С е л е з н е в а С. Н. Порядок длины функций алгебры логики в классе псевдополиномиальных форм // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2016. № 3. С. 27-31.

  16. С е л е з н е в а С. Н. Верхняя оценка длины функций над конечным полем в классе псевдополиномов // ЖВМиМФ. 2017. 57. № 5. С. 899-904.

  17. С е л е з н е в а С. Н. Сложность систем функций алгебры логики и систем функций трехзначной логики в классах поляризованных полиномиальных форм // Дискретная математика. 2015. 27. Вып. 1. С. 111-122.

  18. С е л е з н е в а С. Н., о р д е е в М. М. Сложность систем функций над конечным полем в классе поляризованных полиномиальных форм // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2017. № 4. С. 41-46.

  19. S e l e z n e v a S. N., L o b a n o v A. A. On length of Boolean functions of a small number of variables in the class of pseudo-polynomials // Известия Иркутского гос. ун-та. Сер. Математика. 2020. 33. С. 96-105.

  20. С е л е з н е в а С. Н. О пpиближении с заданной точностью функций k-значных логик полиномами // Дискретная математика. 2008. 20. Вып. 2. С. 32-45.

  21. А л е к с е е в В. Б. О числе функций в классах, задаваемых центральными предикатами // Математические заметки. 1985. 37. Вып. 6. С. 880-886.

  22. А л е к с е е в В. Б. О числе функций в некоторых замкнутых классах частичной k-значной логики // Дискретная математика. 1989. 1. Вып. 1. С. 32-42.

  23. С е л е з н е в а С. Н. О числе полиномиальных функций k-значной логики по составному модулю k // Дискретная математика. 2016. 28. Вып. 2. С. 81-91.

  24. М а р ч е н к о в С. С. Эквациональное замыкание // Дискретная математика. 2005. 17. Вып. 2. С. 117-126.

  25. М а р ч е н к о в С. С. О строении эквационально замкнутых классов // Дискретная математика. 2006. 18. Вып. 4. С. 18-30.

  26. М а р ч е н к о в С. С. Оператор замыкания в многозначной логике, базирующийся на функциональных уравнениях // Дискретный анализ и исследование операций. 2010. 17. № 4. С. 18-31.

  27. М а р ч е н к о в С. С. FE-класси икация функций многозначной логики // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2011. № 2. С. 32-39.

  28. М а р ч е н к о в С. С. Оператор позитивного замыкания // Докл. АН. 2012. 442. № 5. С. 598-599.

  29. М а р ч е н к о в С. С. Задание позитивно замкнутых классов посредством полугрупп эндоморфизмов // Дискретная математика. 2012. 24. Вып. 4. С. 19-26.

  30. М а р ч е н к о в С. С., К а л и н и н а И . С . Оператор FE-замыкания в счетнозначной логике // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2013. № 3. С. 42-47.

  31. М а р ч е н к о в С. С. Позитивно замкнутые классы трехзначной логики // Дискретный анализ и исследование операций. 2014. 21. № 1. С. 67-83.

  32. М а р ч е н к о в С. С. Об операторе замыкания по перечислению в многозначной логике // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2015. № 2. С. 33-39.

  33. М а р ч е н к о в С. С. О FE-предполных классах счетнозначной логики // Дискретная математика. 2016. 28. Вып. 2. С. 51-57.

  34. М а р ч е н к о в С. С. Операторы замыкания с позитивными связками и кванторами // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2017. № 1. С. 33-38.

  35. М а р ч е н к о в С. С. асширения оператора позитивного замыкания с помощью логических связок // Дискретный анализ и исследование операций. 2018. 25. № 4. С. 46-58.

  36. М а р ч е н к о в С. С. Критерий полноты для оператора замыкания по перечислению в трехзначной логике // Дискретная математика. 2018. 30. Вып. 4. С. 47-54.

  37. М а р ч е н к о в С. С. Сильные операторы замыкания. М.: МАКС Пресс, 2017.

  38. М а р ч е н к о в С. С., Ф ё д о р о в а В. С. О решениях систем функциональных булевых уравнений // Дискретный анализ и исследование операций. 2008. 15. № 6. С. 48-57.

  39. М а р ч е н к о в С. С., Ф ё д о р о в а В. С. Решения систем функциональных уравнений многозначной логики // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2009. № 4. С. 29-33.

  40. М а р ч е н к о в С. С. О числе максимальных подгрупп в группах автоматных подстановок // Дискретный анализ и исследование операций. Сер. 1. 2004. 11. № 2. С. 73-79.

  41. М а р ч е н к о в С. С. О максимальных подалгебрах в алгебрах одноместных рекурсивных функций // Дискретный анализ и исследование операций. 2016. 23. № 3. С. 81-92.

  42. К о л м а к о в Е. А., М а р ч е н к о в С. С. О максимальных подгруппах группы рекурсивных перестановок // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2016. № 3. С. 32-36.

  43. М а р ч е н к о в С. С. Критерий полноты в классе экспоненциально-полиномиальных функций // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2020. № 2. С. 37-44.

  44. М а р ч е н к о в С. С. Суперпозиции элементарных арифметических функций // Дискретный анализ и исследование операций. Сер. 1. 2006. 13. № 4. С. 33-48.

  45. М а р ч е н к о в С. С. Элементарные арифметические функции. М.: Книжный дом «Либроком», 2009.

  46. М а р ч е н к о в С. С. Представление функций суперпозициями. М.: Комкнига, 2010.

  47. М а р ч е н к о в С. С. Операция ограниченной префиксной конкатенации и конечные базисы по суперпозиции // Дискретная математика. 2016. 28. Вып. 4. С. 91-99.

  48. С а в и ц к и й И. В. О совпадении сложностных классов BPC и TC0 // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 1. С. 36-45.

  49. В о л к о в С. А. Экспоненциальное расширение класса функций, элементарных по Сколему, и ограниченные суперпозиции арифметических функций // Математические вопросы кибернетики. Вып. 16. М.: Физматлит, 2007. С. 163-190.

  50. В о л к о в С. А. Конечная порождаемость некоторых групп рекурсивных перестановок // Дискретная математика. 2008. 20. Вып. 4. С. 61-78.

  51. М а р ч е н к о в С. С. О невозможности получения (n + 1)-местных непрерывных функций из n-местных с помощью некоторых непрерывных операторов // Математический сборник. 2001. 192. Вып. 6. С. 71-88.

  52. М а р ч е н к о в С. С., К р и в о с п и ц к и й С. И. Суперпозиции непрерывных функций, заданных на бэровском пространстве // Проблемы передачи информации. 2009. 45. Вып. 4. С. 107-114.

  53. М а р ч е н к о в С. С. Операторы итерирования на множестве непрерывных функций бэровского пространства // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2011. № 4. С. 33-37.

  54. А л е к с е е в В. Б., С м и р н о в А. В. О точной и приближенной билинейных сложностях умножения матриц размеров 4 × 2 и 2 × 2 // Современные проблемы математики. 2013. 17. С. 135-152.

  55. П о с п е л о в А. Д. Сложность умножения в ассоциативных алгебрах: Дис. . . . канд. физ.-мат. наук. МГУ. М., 2008.

  56. Ч о к а е в Б. В. Мультипликативная сложность умножения в алгебрах: Дис. . . . канд. физ.-мат. наук. МГУ. М., 2012.

  57. А л е к с е е в В. Б., П о с п е л о в А. Д. Сложность умножения в некоторых групповых алгебрах // Дискретная математика. 17. Вып. 1. 2005. С. 3-17.

  58. Ч о к а е в Б. В. Сложность умножения в коммутативных групповых алгебрах над полями простой характеристики // Дискретная математика. 22. Вып. 4. 2010. С. 121-137.

  59. Ч о к а е в Б. В. Сложность умножения в коммутативных групповых алгебрах над полями характеристики 0 // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2010. № 4. С. 30-40.

  60. Л ы с и к о в В. В. Некоторые вопросы теории сложности билинейных отображений. Дис. . . . канд. физ.-мат. наук. МГУ. М., 2014.

  61. Л ы с и к о в В. В. Об алгебрах почти минимального ранга // Дискретная математика. 24. Вып. 4. 2012. С. 3-17.

  62. Л ы с и к о в В. В. О билинейных алгоритмах над полями различных характеристик // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2013. № 4. С. 33-38.

  63. А л е к с е е в В. Б. Ступенчатые билинейные алгоритмы и распознавание полноты в k-значных логиках // Известия высших учебных заведений. Математика. 1988. Вып. 7. С. 19-27.

  64. А л е к с е е в В. Б. Логические полукольца и их использование для построения быстрых алгоритмов // Вестн. Моск. ун-та. Сер. 1. Матем. Мех. 1997. № 1. С. 22-29.

  65. А л е к с е е в В. Б. От метода А. А. Карацубы для быстрого умножения чисел к быстрым алгоритмам для дискретных функций // Труды МИ АН. 1997. 218. С. 22-27.

  66. С е л е з н е в а С. Н. Быстрый алгоритм построения для k-значных функций полиномов по модулю k при составных k // Дискретная математика. 2011. 23. Вып. 3. С. 3-22.

  67. S e l e z n e v a S. N. Constructing polynomials for functions over residue rings modulo a composite number in linear time // Lecture Notes in Computer Science. Vol. 7353. Springer, 2012. P. 303-312.

  68. С е л е з н е в а С. Н. Линейная оценка схемной сложности распознавания полиномиальности функций над кольцом вычетов по составному модулю // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2013. № 1. С. 27-31.

  69. С е л е з н е в а С. Н. О проверке полиномиальности функций k-значной логики одной переменной по составному модулю k // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2024. № 2. С. 47-57.

  70. С е л е з н е в а С. Н. О сложности распознавания полноты множеств булевых функций, реализованных полиномами Жегалкина // Дискретная математика. 1997. 9. Вып. 4. С. 24-31.

  71. С е л е з н е в а С. Н. Полиномиальный алгоритм для распознавания принадлежности реализованной полиномом функции k-значной логики предполным классам самодвойственных функций // Дискретная математика. 1998. 10. Вып. 3. С. 64-72.

  72. С е л е з н е в а С. Н. О некоторых свойствах многочленов над конечным полем // Дискретная математика. 2001. 13. Вып. 2. С. 111-119.

  73. С е л е з н е в а С. Н. Полиномиальный алгоритм распознавания принадлежности функций k-значных логик, представленных полиномами, к предполным классам линейных функций // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2001. № 3. С. 40-43.

  74. S e l e z n e v a S. N. Polynomial-time algorithms for verification of some properties of k-valued functions represented by polynomials // Procceedings of 31th International Symposium of Multiple-Valued Logic.IEEE Computer Society, 2001. P. 233-238.

  75. С е л е з н е в а С. Н. О поиске периодов многочленов Жегалкина // Дискретная математика. 2021. 33. Вып. 3. С. 107-120.

  76. С е л е з н е в а С. Н. О сложности поиска периодов функций, заданных многочленами над конечным простым полем // Дискретный анализ и исследование операций. 2022. 29. Вып. 1. С. 56-73.

  77. С е л е з н е в а С. Н. О мультиа инных многочленах над конечным полем // Дискретная математика. 2020. 32. Вып. 3. С. 85-97.

  78. С е л е з н е в а С. Н. О проверке мультиаффинности функций алгебры логики по их многочленам Жегалкина // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2022. № 1. С. 42-49.

  79. С е л е з н е в а С. Н. О проверке мультиаффинности многочленов над конечным полем // Дискретная математика. 2023. 35. Вып. 2. С. 109-124.

  80. С е л е з н е в а С. Н. Полиномиальные представления дискретных функций: Дис. . . . д-ра физ.-мат. наук. МГУ. М., 2016.

  81. М а р ч е н к о в С. С. Булева сводимость // Дискретная математика. 2003. 15. Вып. 3. С. 40-53.

  82. М а р ч е н к о в С. С. Булева сводимость и булевы степени. М.: МАКС Пресс, 2020.

  83. М а р ч е н к о в С. С. Сводимость почти полиномиальными функциями // Известия вузов. Математика. 2022. Вып. 12. С. 68-78.

  84. М а р ч е н к о в С. С. О сложности возвратных последовательностей // Дискретная математика. 2003. 15. Вып. 2. С. 52-62.

  85. М а р ч е н к о в С. С. О сложности полиномиальных возвратных последовательностей // Проблемы передачи информации. 2018. 54. Вып. 3. С. 67-72.

  86. М а р ч е н к о в С. С. Почти полиномиальные возвратные последовательности с алгоритмически неразрешимыми проблемами // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2023. № 3. С. 49-55.

  87. М а р ч е н к о в С. С. Об алфавитном кодировании сверхслов // Проблемы передачи информации. 2019. 55. Вып. 3. С. 83-92.

  88. С а в и ц к и й И. В. Вычисления на регистровых машинах со счетчиками // Дискретная математика. 2017. 29. Вып. 1. С. 95-113.

  89. М а р ч е н к о в С. С., С а в и ц к и й И. В. Вычисления на счетчиковых машинах с сумматором // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 1. С. 31-39.

  90. М а р ч е н к о в С. С., С а в и ц к и й И. В. Машины в теории вычислимых функций. М.; Вологда: Инфра-Инженерия, 2024.