Динамическое программирование в методе развертки решения третьей проблемы Кэмерона

Липницкий, В. А.; Сергей, А. И.; Спичекова, Н. В.

Динамическое программирование в методе развертки решения третьей проблемы Кэмерона

Липницкий, В. А., Сергей, А. И., Спичекова, Н. В.

Дата публикации: 2018

Дата публикации в реестре: 2021-05-18T14:08:26Z

Аннотация:

Рассматривается модификация предложенного ранее авторами алгоритма развертки для вычисления количества орбит на множестве бинарных квадратных матриц порядка n, n > 2, содержащих в точности n единиц, которые образуются под действием квадрата Sn2 симметрической группы Sn. Предлагаемая модификация алгоритма требует выполнения O(p(n)n4) арифметических операций, где p(n) – количество неупорядоченных разбиений числа n.

Ключевые слова:
бинарная матрица, симметрическая группа, орбита, мощность орбиты, третья проблема Питера Кэмерона, лемма Бёрнсайда, цикленный тип подстановки

Тип: Article