PA_full (1127144), страница 18
Текст из файла (страница 18)
Поэтому здесь не выполняетсясвойство (↵2 ) = ( (↵))2 .244 / 432Прикладная алгебраКоды, исправляющие ошибкиЗадачи244 / 432Решение (продолжение 2)(↵11 ) = ↵9 + ↵2 + 1 = ↵3 + ↵2 + ↵ + 1,(↵12 ) = ↵11 + ↵3 + 1 = ↵2 + ↵ + 1,(↵13 ) = ↵13 + ↵4 + 1 = ↵3 + ↵2 + ↵ + 1,(↵14 ) = 1 + ↵5 + 1 = ↵2 + ↵,(↵15 ) = ↵2 + ↵6 + 1 = ↵3 + 1.Заметим, что полином локаторов ошибок (x) являетсяполиномом над полем 42 . Поэтому здесь не выполняетсясвойство (↵2 ) = ( (↵))2 .Обратные элементы для обнаруженных корней ↵5 и ↵8 равны,соответственно, ↵10 и ↵7 . Отсюда получаем, что полиномошибокe(x) = x10 + x7 .Прикладная алгебраКоды, исправляющие ошибкиЧто надо знатьРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды245 / 432Прикладная алгебраКоды, исправляющие ошибкиЧто надо знатьРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств246 / 432Прикладная алгебраКоды, исправляющие ошибкиЧто надо знатьРаздел IIIОсновные понятия теории ч.у.
множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать247 / 432Прикладная алгебраКоды, исправляющие ошибкиЧто надо знатьЗадачи построения кодов, исправляющих ошибки.Основные понятия метрики на единичном кубе.Групповые коды: определения, свойства.
Кодовоерасстояние. Построение кода как задача плотной упаковки.Теорема Хэмминга. Пример построения кода Хэмминга.Циклические коды: определение, построение идекодирование.Коды БЧХ как частный случай циклических кодов. Идеяпостроения кода БЧХ и оценка его кодового расстояния.Коды БЧХ: алгоритмы кодирования и декодирования.248 / 432Прикладная алгебраТеория перечисления ПойаДействие группы на множествеРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды249 / 432Прикладная алгебраТеория перечисления ПойаДействие группы на множествеРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств250 / 432Прикладная алгебраТеория перечисления ПойаДействие группы на множествеРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать251 / 432Прикладная алгебраТеория перечисления ПойаДействие группы на множестве252 / 432Действие группы на множестве: два определенияГруппа= h G, , e i, |G| = n.Множество T , |T | = N .Bij(T ) � множество всех биекций на T.Symm(T ) � симметрическая группа множества T :Symm(T ) = h Bij(T ), ⇤, 1T i ,Прикладная алгебраТеория перечисления ПойаДействие группы на множестве252 / 432Действие группы на множестве: два определенияГруппа= h G, , e i, |G| = n.Множество T , |T | = N .Bij(T ) � множество всех биекций на T.Symm(T ) � симметрическая группа множества T :Symm(T ) = h Bij(T ), ⇤, 1T i ,Определение (1)↵ 2 Hom ( , Symm(T ) ).Действие ↵ группына множестве T : символически �: T.↵Прикладная алгебраТеория перечисления ПойаДействие группы на множестве253 / 432Действие группы на множестве: два определения...Определение (2)где↵ = h , T ; , ⇤, e, 1T i ,G ⇥ G ! G � групповая операция;⇤G ⇥ T ! T � новая операция.Аксиомы для операций:e ⇤ t = t;(g h) ⇤ t = h ⇤ (g ⇤ t).Запись операции ⇤: g(t) = t 0 .Аксиомы: e(t) = t и (g h)(t) = h(g(t)).Т.е.
g � перестановки на T , обладающие вышеуказаннымисвойствами.Прикладная алгебраТеория перечисления ПойаДействие группы на множествеРис. 2. K определению действия группы на множестве254 / 432Прикладная алгебраТеория перечисления ПойаДействие группы на множествеДля данной перестановки g:Введём отношение эквивалентности ⇠g на T �⇣⌘deft ⇠g t 0 = 9 k g k (t) = t 0 .Классы эквивалентности называют g-циклами. Всего C(g)циклов (классов эквивалентности).Количества циклов длины 1, 2, . .
. , N обозначают⌫1 , ⌫2 , . . . , ⌫N или ⌫1 (g), ⌫2 (g), . . . , ⌫N (g).255 / 432Прикладная алгебраТеория перечисления ПойаДействие группы на множестве255 / 432Для данной перестановки g:Введём отношение эквивалентности ⇠g на T �⇣⌘deft ⇠g t 0 = 9 k g k (t) = t 0 .Классы эквивалентности называют g-циклами. Всего C(g)циклов (классов эквивалентности).Количества циклов длины 1, 2, . . . , N обозначают⌫1 , ⌫2 , . . . , ⌫N или ⌫1 (g), ⌫2 (g), . . . , ⌫N (g).Их упорядоченную совокупность, записанную какT ype(g) = h ⌫1 , ⌫2 , .
. . , ⌫N iилиh 1 ⌫ 1 , 2 ⌫2 , . . . , N ⌫ N iназывают типом перестановки g.NNPPПонятно, что C(g) =⌫k (g) иk · ⌫k (g) = N .k=1k=1Прикладная алгебраТеория перечисления ПойаДействие группы на множествеПримерПустьT = { 1, . . . , 10 },✓◆1 2 3 4 5 6 7 8 9 10g ==9 6 1 8 5 2 7 10 3 4= (1, 9, 3)(2, 6)(4, 8, 10)(5)(7)ТогдаT ype(g) = h 12 , 21 , 32 , 40 , . . .
, 100 i = h 2, 1, 2, 0, . . . , 0 iи C(g) = 5.256 / 432Прикладная алгебраТеория перечисления ПойаДействие группы на множествеПо всей группе257 / 432:Отношение эквивалентности ⇠ на T �deft ⇠ t 0 = 9 g g(t) = t0 .GКлассы этой эквивалентности называют орбитами.Прикладная алгебраТеория перечисления ПойаДействие группы на множествеПо всей группе257 / 432:Отношение эквивалентности ⇠ на T �deft ⇠ t 0 = 9 g g(t) = t0 .GКлассы этой эквивалентности называют орбитами.Число орбит (классов эквивалентности) � C( ).Прикладная алгебраТеория перечисления ПойаДействие группы на множествеПо всей группе257 / 432:Отношение эквивалентности ⇠ на T �deft ⇠ t 0 = 9 g g(t) = t0 .GКлассы этой эквивалентности называют орбитами.Число орбит (классов эквивалентности) � C( ).Если C( ) = 1 (любой элемент T может быть переведён влюбой), то действие : T называют транзитивным.↵Класс эквивалентности, в которую попадает элемент t будемобозначать Orb (t).Прикладная алгебраТеория перечисления ПойаДействие группы на множестве258 / 432Неподвижные точки группы преобразований: g(t) = tПри выполнении этого равенства можно фиксировать t или g.1Фиксируем g, т.е.
находим все элементы множества T ,которые перестановка g оставляет на месте (фиксатор):def{ t 2 T | g(t) = t } = Fix (g) ✓ T .Прикладная алгебраТеория перечисления ПойаДействие группы на множестве258 / 432Неподвижные точки группы преобразований: g(t) = tПри выполнении этого равенства можно фиксировать t или g.1Фиксируем g, т.е. находим все элементы множества T ,которые перестановка g оставляет на месте (фиксатор):def{ t 2 T | g(t) = t } = Fix (g) ✓ T .2Фиксируем t, т.е. находим все перестановки g, которыеоставляют данный элемент неподвижным (стабилизатор):def{ g 2 G | g(t) = t } = Stab (t) ✓ G.Прикладная алгебраТеория перечисления ПойаДействие группы на множестве258 / 432Неподвижные точки группы преобразований: g(t) = tПри выполнении этого равенства можно фиксировать t или g.1Фиксируем g, т.е.
находим все элементы множества T ,которые перестановка g оставляет на месте (фиксатор):def{ t 2 T | g(t) = t } = Fix (g) ✓ T .2Фиксируем t, т.е. находим все перестановки g, которыеоставляют данный элемент неподвижным (стабилизатор):def{ g 2 G | g(t) = t } = Stab (t) ✓ G.Справедливы равенстваC( ) =1 X1 XFix (g) =Stab (t) ;|G||G|g2Gt2TПрикладная алгебраТеория перечисления ПойаДействие группы на множестве258 / 432Неподвижные точки группы преобразований: g(t) = tПри выполнении этого равенства можно фиксировать t или g.1Фиксируем g, т.е. находим все элементы множества T ,которые перестановка g оставляет на месте (фиксатор):def{ t 2 T | g(t) = t } = Fix (g) ✓ T .2Фиксируем t, т.е.
находим все перестановки g, которыеоставляют данный элемент неподвижным (стабилизатор):def{ g 2 G | g(t) = t } = Stab (t) ✓ G.Справедливы равенстваC( ) =1 X1 XFix (g) =Stab (t) ;|G||G|g2Gt2Tпервое называется леммой Бёрнсайда (W.Burnside, 1911).Прикладная алгебраТеория перечисления ПойаДействие группы на множестве259 / 432Стабилизатор есть подгруппа12Fix (g) � фиксатор перестановки g;Stab (t) � стабилизатор элемента t.ЛеммаStab (t) 6.Прикладная алгебраТеория перечисления ПойаДействие группы на множестве259 / 432Стабилизатор есть подгруппа12Fix (g) � фиксатор перестановки g;Stab (t) � стабилизатор элемента t.ЛеммаStab (t) 6.ДоказательствоЗафиксируем t 2 T и рассмотрим g, h 2 Stab (t).
Тогдаg(t) = h(t) = t и h 1 (t) = t. Следовательно,(g h1)⇤t = t ) g h12 Stab (t) .Прикладная алгебраТеория перечисления ПойаДействие группы на множестве259 / 432Стабилизатор есть подгруппа12Fix (g) � фиксатор перестановки g;Stab (t) � стабилизатор элемента t.ЛеммаStab (t) 6.ДоказательствоЗафиксируем t 2 T и рассмотрим g, h 2 Stab (t). Тогдаg(t) = h(t) = t и h 1 (t) = t. Следовательно,(g h1)⇤t = t ) g h12 Stab (t) .| Stab (t)| > 1, поскольку всегда e 2 Stab (t).Прикладная алгебраТеория перечисления ПойаДействие группы на множестве260 / 432СтабилизаторЛеммаДлина орбиты Orb (t) равна индексу Stab (t) в группе, т.е.| Orb (t)| = |G| : | Stab (t)|.ПримерO � группа вращений куба (группа октаэдра) и t � некотораяего вершина. Найти Stab (t).Прикладная алгебраТеория перечисления ПойаДействие группы на множестве260 / 432СтабилизаторЛеммаДлина орбиты Orb (t) равна индексу Stab (t) в группе, т.е.| Orb (t)| = |G| : | Stab (t)|.ПримерO � группа вращений куба (группа октаэдра) и t � некотораяего вершина.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
