Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №8, Москва, 1999
Авторы: Глухов М.М., Зубов А.Ю.
О длинах симметрических и знакопеременных групп подстановок в различных системах образующих
Аннотация:
В статье даётся обзор результатов о системах образующих симметрических и знакопеременных групп подстановок конечных степеней. В первой части обзора приводятся методы, позволяющие ответить на вопрос, порождает ли данное множество подстановок симметрическую (Sn) или знакопеременную (An) группу. Указываются как хорошо известные, так и специфические системы образующих групп Sn и An, состоящие из подстановок с одинаковой цикловой структурой, системы образующих, использующиеся в таких приложениях как теория автоматов, криптография и др. Вторая часть обзора посвящена оценкам длин групп Sn и An, порождаемых теми или иными системами образующих. Длина группы совпадает с диаметром графа Кэли группы и представляет собой максимум длин кратчайших представлений элементов группы через данные образующие элементы. Для ряда систем образующих групп подстановок приводятся алгоритмы, позволяющие находить представления элементов группы в виде произведений данных образующих (в частности кратчайшие). Наряду с опубликованными результатами авторы приводят отдельные результаты, известные им из различных научных отчётов.
Ключевые слова:
система образующих элементов группы; симметрическая и знакопеременная группы подстановок; длина элемента группы и длина группы в системе образующих элементов; диаметр графа Кэли группы
Язык публикации: русский, страниц: 28 (с. 5-32)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст: Сведения об авторах:
  • Глухов Михаил Михайлович,  МГУ им. М.В.Ломоносова
  • Зубов Анатолий Юрьевич,  ,  ООО «Центр сертификационных исследований»