Читать онлайн «Кибернетический сборник. Новая серия. Выпуск 01»

Кибернетический сборник НОВАЯ СЕРИЯ ВЫПУСК I Сборник переводов Под редакцией А. А. ЛЯПУНОВА и О. Б. ЛУПАНОВА ИЗДАТЕЛЬСТВО «МИР» Москва 1965 Научный совет по кибернетике УДК 519. 95 Академии наук СССР В 1960—1964 гг. Издательством иностранной литературы и издательством «Мир» выпускалась серия кибернетических сборников (выпуски 1—9). Этот выпуск открывает новую серию, которая является в известном смысле продолжением предыдущей, но будет отличаться от нее более раз- разнообразной тематикой. В разделе «Математические вопросы» представлены работы по теории кодирования (статьи Дж. Мак-Вильяме и Э. Гилберта), а также по теории автоматов и теории управляющих систем. Раздел «Вычислительные машины и программирование» в основном посвящен описанию новейших вычислитель- вычислительных машин системы 1ВМ-360. Вопросам математической лингвистики посвя- посвящена обзорная статья Н. Хомского и Дж. Миллера. Это первая из трех статей, в которых обсуждаются математические модели языка; остальные статьи будут включены в следующие выпуски сборника. Сборник рассчитан на научных работников, инженеров, аспирантов и студентов различных специальностей, занимающихся и интересующихся ки- кибернетикой. Редакция литературы по математическим наукам Математические вопросы О базисах симметрической группы1) С. Пи кар От редакции. Книга Софи Пикар «О базисах симметрической группы», вышедшая в 1946 г. , посвящена детальному изучению пар подстановок, по- порождающих симметрическую группу е^п. В книге содержится большое коли- количество критериев, позволяющих распознавать полноту пар подстановок опре- определенного вида. Некоторые результаты, изложенные в книге, имеют прило- приложение в вопросах описания работы электрических схем, теории кодирования и др. В настоящем сборнике публикуется перевод части книги, содержащей основной результат и весь материал, необходимый для его доказательства 2). ВВЕДЕНИЕ Пусть л>3 (^-4)—целое число и &*п {<Ап)—симметри- {<Ап)—симметрическая (знакопеременная) группа степени п и порядка п\ (п\/2). Обозначим через 1, 2, ... , п элементы подстановок груп- группы <^п. Известно, что ни группа <^Л (п>-3), ни группа <Лп (я>4) не могут быть порождены одной подстановкой. Напротив, для всех п^-Ъ (п^-4) существуют пары подстановок в группе <&* п (с^п), порождающие эту группу. Пара 5, Т подстановок группы ъ?п (<Ап) называется бази- базисом этой группы, если все подстановки из &\ (сЛп) могут быть получены в виде суперпозиции (конечной) 5 и Т. Мы докажем, что при любом целом п >- 3 (^-4) для каждой нетождественной подстановки 5 группы о?п (Лп) существует по крайней мере одна подстановка Т группы 4?п {<Ап), которая вместе с 5 составляет базис группы &п (Лп), за исключением трех подстановок A 2) C 4), A 3) B 4), A 4) B 3), которые не входят ни в один базис группы ^ 1) Р 1 с с а г 6 5. , 5иг 1ез Ьазез Aи дгоире зутёЧ^ие, Рапз, 1946. 2) Позднее вышла книга того же автора «О базисах групп конечного порядка» E. Р1ссагс1, 5иг 1ез Ьазез дез &пшрез д'огдге т1п1. Ауес ипе ргё!. де М. Агпаид Эе^оу. ЫеисЬа1еГ, 1957), в которой многие результаты первой книги обобщаются на случай произвольных групп конечного порядка. 8 С. Пикар ОПРЕДЕЛЕНИЯ И ПРЕДВАРИТЕЛЬНЫЕ ЗАМЕЧАНИЯ Определение 1. Пусть 5 и Т — две подстановки из эле- элементов 1, 2, ... , п (л^-3). Назовем их связанными, если не су- существует собственного подмножества Е4 множества Е — = {1, 2, ... , /г}, состоящего из множества элементов некоторых циклов как для 5, так и для Т. Например, подстановки 5 = = A 2) C 4) и Т=A) B 3) D)—связанные, а подстановки 5=A 2 3) D) и Г=A 2) C) D) — несвязанные; здесь = {1, 2, 3}.