Please use this identifier to cite or link to this item:
https://libr.msu.by/handle/123456789/11510| Title: | Быстрое преобразование Фурье в подсчете количества Sₙ-орбит кэмероновских матриц |
| Authors: | Липницкий, В. А. Сергей, А. И. Спичекова, Н. В. |
| Keywords: | бинарная матрица симметрическая группа орбита мощность орбиты третья проблема Питера Кэмерона лемма Бёрнсайда цикленный тип подстановки дискретное преобразование Фурье быстрое умножение многочленов |
| Issue Date: | 2019 |
| Publisher: | Магілёўскі дзяржаўны ўніверсітэт імя А. А. Куляшова |
| Citation: | Липницкий, В. А. Быстрое преобразование Фурье в подсчете количества Sₙ-орбит кэмероновских матриц / В. А. Липницкий, А. И. Сергей, Н. В. Спичекова // Веснік Магілёўскага дзяржаўнага ўніверсітэта імя А. А. Куляшова. Сер. В. Прыродазнаўчыя навукі (матэматыка, фізіка, біялогія). – 2019. – № 1 (53). – С. 4–13. |
| Abstract: | В данной работе предлагается алгоритм, основанный на быстром умножении многочленов, для подсчета количества орбит, на которые разбивается множество Pn квадратных (0,1) -матриц под действием квадрата sI симметрической группы Sn. Рассматриваемый алгоритм имеет вычислительную сложность O(p(n)n25 log n), где p(n) – количество неупорядоченных разбиений числа n. Наилучший алгоритм, известный до публикации данной работы, имеет вычислительную сложность O(p(n)n4). |
| URI: | http://libr.msu.by/handle/123456789/11510 |
| Appears in Collections: | 2019, № 1 (53) |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.