СИСТЕМЫ АНАЛИЗА И ОБРАБОТКИ ДАННЫХ

Многие приложения требуют исчерпывающих перечней строк, на которые могут налагаться различные требования, например, такие как их неэквивалентность при действии на них групп симметрии. Ожерелье – это класс эквивалентности r-арных строк при вращении. Непомеченное r-арное ожерелье – это класс эквивалентности r-арных строк при вращении и перестановке символов алфавита. Пусть G – группа симметрий, действующая на заданном множестве ожерелий Т. Ожерелье  называется симметричным, если существует элемент    такой, что  Возможны другие, эквивалентные приведенному определения симметрии ожерелий. Все они так или иначе связаны с определением симметрии фигуры, сопоставляемой с непомеченным ожерельем. Плоская фигура называется симметричной, если она самосовмещается при движениях пространства  т.?е. при его изометрических преобразованиях.

Частным случаем фигур и, соответственно, ожерелий являются хордовые диаграммы. Хордовые диаграммы представляют объект для исследования, интересный с разных сторон (теория узлов, диаграммы Фейнмана, представления алгебр Ли), и изучались многими авторами. В статье представлены алгоритмы перечисления симметричных хордовых диаграмм и на простых примерах по­казана их связь с теорией узлов. Перечень симметричных хордовых диаграмм может, в частности, представлять интерес в области математического стихо­ведения, занимающегося исследованием динамики стихотворных строф по горизонтали (ритм, слоговый объем стихов) и по вертикали (схемы рифмовок, рефренов, и других стилистических средств).

1. Fast algorithms to generate necklaces, unlabeled necklaces, and irreducible polynomials over GF(2) / K. Cattell, F. Ruskey, J. Sawada, С.М. Serra, R. Miers // Journal of Algorithms. – 2000. – Vol. 37 (2). – P. 267–282.

2. Sawada J. Generating bracelets in constant amortized time // Manuscript, 1999.

3. Sawada J. A fast algorithm for generating nonisomorphic chord diagrams // SIAM Journal on Discrete Mathematics. – 2002. – Vol. 15 (4). – P. 546–561.

4. Григорьев Ю.Д. Восьмистишия как симметричные ожерелья: перечисление и свойства // Квантитативная филология. – 2022. №1 (3). – С. 16-31. http://qpcenter.org/upload/uf/dc2/ r0q9y9mndceowq3wpc9gtv7rtk0psbkn.pdf

5. Григорьев Ю.Д. Перечисление симметричных ожерелий // Вестник ТГУ. Управление, вычислительная техника и информатика. – 2022. – Т. 61. – С. 97–107. – DOI: 10.17223/19988605/61/10.

6. Григорьев Ю.Д. Разработка архитектурного решения программного обеспечения для устройств интернет-вещей // Системы анализа и обработки данных. – 2023. – № 3 (91). – С. 19–36. – DOI: 10.1721212182-2001-202з-3-19-36.

7. Дужин С.В. Инварианты Васильева – Гусарова // Математика XX века. Взгляд из Петербурга / под ред. А.М. Вершика. – М.: МЦНМО, 2010. – С. 87–116.

8. Мантуров В.О. Теория узлов. – М.; Ижевск: Ин-т компьютер. исслед., 2005. – 312 с.

9. Аллёнов С.В. Диаграммно-стрелочные формулы для инвариантов узлов четвертого порядка // Фундаментальная и прикладная математика. – 2005. – Т. 11, № 5. – С. 3–17.

10. Аллёнов С.В., Лексин В.П. О диаграммных формулах инвариантов узлов // Геометрическая топология, дискретная геометрия и теория множеств. – М.: Наука, 2006. – С. 10–17. – (Труды МИАН; вып. 252).

11. Lyndon R.С. On burnside’s problem // Transactions of the American Mathematical Society. – 1954. – Vol. 77 (2). – P. 202–215.

12. Jacobson N. Lie algebras. – New York; London: Interscience Publishers, 1961. – 331 p.

13. Краско Е.С. Перечисление непомеченных хордовых диаграмм максимального рода // Записки научных семинаров ПОМИ. – 2017. – Т. 464: Комбинаторика и теория графов. IX. – C. 77–87.

14. Proskurowski A., Ruskey F., Smith М. Analysis of algorithms for listing equivalence classes of k-ary strings induced by simple group actions // SIAM Journal on Discrete Mathematics. – 1998. – Vol. 11 (1). – P. 94–109. – DOI: 10.1137/S0895480192234009.

15. Ruskey F., Sawada J. An efficient algorithm for generating necklaces with fixed density // SIAM Journal on Discrete Mathematics. – 1999. – Vol. 29 (2). – P. 671–684. – DOI: 10.1137/S0097539798344112.

16. Оре О. Теория графов. – М.: Наука, 1968. – 352 с.

17. Фор Р., Кофман А., Дени-Папен М. Современная математика. – М.: Мир, 1966. – 272 с.

18. Прасолов В.В., Сосинский А.Б. Узлы, зацепления, косы и трехмерные многообразия. – М.: МНЦМО, 1997. – 352 с.