8. Понятие группы. Группа подстановок.

 Группой(А=<M,*>) называется множество элементов, на котором задана операция умножения , которая удовлетворяет следующим четырём аксиомам: Замкнутость группы относительно операции умножения. Для любых двух элементов группы существует третий, который является их произведением: Ассоциативность операции умножения. Порядок выполнения умножения несущественен: Существование единичного элемента. В группе существует некоторый элемент E, произведение которого с любым элементом A группы даёт тот же самый элемент A: Существование обратного элемента. Для любого элемента A группы существует такой элемент A⁻¹, что их произведение даёт единичный элемент E:

Группа подстановок -совокупность подстановок на некотором множестве X, образующих группу относительно операции умножения подстановок.  Иначе, группа подстановок.- это пара (G, X), где G - группа, X - множество и каждому   соответствует подстановка   множества X такая, что 1)  ,   , и 2) х ^a=х для любого   тогда и только тогда, когда a=e - единица группы G

9.Понятие кольца. Кольцо вычетов.

Определение кольца

Кольцом   называется множество элементов, на котором определены две операции – сложение и умножение, и в   выполняются следующие аксиомы:

1. R.1. Множество   является аддитивной абелевой группой.

2. R.2. Для любых двух элементов   и   из   определено их произведение:   (замкнутость операции умножения).

3. R.3. Для любых трех элементов  ,   и   из   выполняется ассоциативный закон, т.е.   и  .

4. R.4. Для любых трех элементов  ,   и   из   выполняется дистрибутивный закон, т.е. справедливы равенства:   и  .

Пример 5.8. Все целые положительные и отрицательные числа и нуль образуют коммутативное кольцо с единицей относительно обычных операций сложения и умножения.

Пример 5.9. Легко убедиться, что полная система вычетов по модулю   также образует коммутативное кольцо с единицей относительно операций сложения и умножения по модулю  .

Кольцо вычетов по модулю 

При описании блочных кодов [25, 30, 33] широко используется понятие кольца вычетов по модулю некоторого полинома   с коэффициентами из поля  .

Для полиномов существуют понятия, аналогичные введенным в 5.8 для чисел, если заменить в этих понятиях слово «число» словом «полином». Так, если при делении полиномов   и   из   на   получаются одинаковые остатки, то многочлены   и   сравнимы между собой по модулю многочлена   из   или  .

Все полиномы, сравнимые между собой по модулю  , образуют класс вычетов по модулю  , а каждый полином класса называется вычетом по модулю  . Каждый класс характеризуется своим представителем, в качестве которого обычно выбирают полином, степень которого меньше степени  . Количество классов вычетов по модулю   равно числу многочленов, степени которых меньше степени  .

Совокупность классов вычетов по модулю   образует кольцо вычетов по модулю  . В качестве операций сложения и умножения в этом кольце используются сложение и умножение по модулю  .

Пример 5.13. Рассмотрим кольцо классов вычетов по модулю полинома   над двоичным полем. Полиномы вида  , где   – произвольный полином, степень которого меньше 2, при фиксированном   образуют класс вычетов по модулю  . Так как всего имеется 4 разных полинома   степени меньше 2, то возможны 4 следующие класса вычетов:

Здесь   – произвольный полином. В качестве представителей классов обычно выбирают вычеты наименьшей степени, которые совпадают с полиномами   и образуют кольцо классов вычетов по модулю полинома  , т.е. множество  .