PA_full (1127144), страница 22
Текст из файла (страница 22)
Коды ХэммингаГрупповые (линейные) коды303 / 432Прикладная алгебраТеория перечисления ПойаЗадачиРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств304 / 432Прикладная алгебраТеория перечисления ПойаЗадачиРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у.
множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать305 / 432Прикладная алгебраТеория перечисления ПойаЗадачиЗадача (ТП-1)Найти цикловой индекс группы симметрии правильноготреугольника.306 / 432Прикладная алгебраТеория перечисления ПойаЗадачи306 / 432Задача (ТП-1)Найти цикловой индекс группы симметрии правильноготреугольника.РешениеГруппа симметрии правильного треугольника � группа диэдраD3 ⇠= S3 .
D3 = h t, s i, t3 = s2 = e, t2 s = st, |D3 | = 6.Элемент группы ge = (1)(2)(3)t = (123), t2 = (132)s = (1)(23), st, st2T ype(g)h 3, 0, 0 ih 0, 0, 1 ih 1, 1, 0 iw(g)x31x3x1 x2Цикловой индекс �PS3 =⇤1 ⇥ 3· x1 + 2x3 + 3x1 x2 .6Прикладная алгебраТеория перечисления ПойаЗадачиЗадача (ТП-2)Найти цикловой индекс транзитивного самодействия группы Z6 .307 / 432Прикладная алгебраТеория перечисления ПойаЗадачи307 / 432Задача (ТП-2)Найти цикловой индекс транзитивного самодействия группы Z6 .РешениеZ6 = hgi , действие g � циклическаяперестановка элементов Z6 .Элемент группы ge = (1) .
. . (6)g = (123456)g 2 = (135)(246)g 3 = (14)(25)(36)g 4 = (153)(264)g = (165432)T ype(g)h 6, 0, . . . ih 0, 0, 0, 0, 0, 1 ih 0, 0, 2, 0, . . . ih 0, 3, 0, . . . ih 0, 0, 2, 0, . . . ih 0, 0, 0, 0, 0, 1 iPZ 6 =w(g)x61x6x23x23x23x6⇤1 ⇥ 6· x1 + x32 + 2x6 + 2x23 .6Прикладная алгебраТеория перечисления ПойаЗадачиЗадача (ТП-3)Определить число различных раскрасок правильной 4-х угольнойпирамиды П в 3 цвета.308 / 432Прикладная алгебраТеория перечисления ПойаЗадачи308 / 432Задача (ТП-3)Определить число различных раскрасок правильной 4-х угольнойпирамиды П в 3 цвета.РешениеT � множество граней П, нумерация граней: боковые грани � с1 по 4 по часовой стрелке, основание � 5.Группа вращений П: ⇠= 4 = h t i, t � вращение на 90 почасовой стрелке t4 = e.PЭлемент группы gT ype(g)e = (1)(2)(3)(4)(5) h 5, 0, 0, 0, 0 ir = (1234)(5)h 1, 0, 0, 1, 0 ir2 = (12)(34)(5)h 1, 2, 0, 1, 0 ir3 = (1432)(5)h 1, 0, 0, 1, 0 i⇤1⇥ 5=x1 + x1 x4 + x1 x22 + x1 x4 , P (2)4w(g)x51x1 x4x1 x22x1 x4136== 34.4Прикладная алгебраТеория перечисления ПойаЗадачиЗадача (ТП-4)Найти число раскрасок усечённой правильной 4-х угольнойпирамиды в 2 цвета.309 / 432Прикладная алгебраТеория перечисления ПойаЗадачи309 / 432Задача (ТП-4)Найти число раскрасок усечённой правильной 4-х угольнойпирамиды в 2 цвета.РешениеT � множество граней пирамиды П; |T | = N = 6.Пронумеруем грани П следующим образом: боковые грани � с1 по 4 по часовой стрелки, основания � 5 и 6.⇠= 4 = h t i , t4 = e, t � 90 по часовой стрелке.Элемент группы ge = (1) .
. . (6)t = (1234)(5)(6)t2 = (12)(34)(5)(6)T ype(g)h 6, 0, . . . ih 2, 0, 0, 1, 0, 0 ih 2, 2, 0, . . . iw(g)x61x21 x4x21 x22Прикладная алгебраТеория перечисления ПойаЗадачи310 / 432Решение (ТП-4, продолжение)Цикловой индексP (x1 , . . . , x4 ) =⇤1⇥ 5x1 + 2x1 x4 + x1 x22 .4Число различных раскрасок граней в 3 цвета:P (3, . . . , 3) =⇤⇤1⇥ 51⇥3 + 2 · 32 + 3 3 =243 + 18 + 27 =44288== 72.4Прикладная алгебраТеория перечисления ПойаЗадачиЗадача (ТП-5)Сколько различных ожерелий можно составить из 7-ми бусиндвух цветов (красного и синего).Или: сколькими различными способами можно раскраситьвершины правильного семиугольника в два цвета?311 / 432Прикладная алгебраТеория перечисления ПойаЗадачи311 / 432Задача (ТП-5)Сколько различных ожерелий можно составить из 7-ми бусиндвух цветов (красного и синего).Или: сколькими различными способами можно раскраситьвершины правильного семиугольника в два цвета?РешениеГруппа симметрии правильного семиугольника � группадиэдра: D7 = h t, f i , t7 = f 2 = e , |D7 | = 2 · 7 = 14.D7 = h e, t, t2 , t3 , t4 , t5 , t6 , f, tf, t2 f, t3 f, t4 f, t5 f, t6 f i.Элемент группы get, t2 , .
. . , t6f, tf, . . . , t6 fT ype(g)h 7, 0, . . . ih 0, 0, 0, 0, 0, 0, 1 ih 1, 3, 0, . . . iw(g)x71x7x1 x32Прикладная алгебраТеория перечисления ПойаЗадачи312 / 432Решение (ТП-6)Цикловой индексPD7 (x1 , . . . , x7 ) =⇤1⇥ 7x1 + 6x7 + 7x1 x32 .14Число различных раскрасок в r цветов �P (r, . . . , r) =Для r = 2 имеемP (2, . . . , 2) =⇤1⇥ 7r + 6r + 7r4 .14⇤1⇥ 7128 + 12 + 1122 + 12 + 7 · 16 ==1414252== 18.14Прикладная алгебраТеория перечисления ПойаЧто надо знатьРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаГрупповые (линейные) коды313 / 432Прикладная алгебраТеория перечисления ПойаЧто надо знатьРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств314 / 432Прикладная алгебраТеория перечисления ПойаЧто надо знатьРаздел IIIОсновные понятия теории ч.у.
множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать315 / 432Прикладная алгебраТеория перечисления ПойаЧто надо знатьДействие группы на множестве: два определения. g-циклы,тип перестановки. Орбиты.Неподвижные точки группы преобразований: фиксатор истабилизатор. Лемма Бёрнсайда.Группы вращений платоновых тел. Примеры.Применение леммы Бёрнсайда для решениякомбинаторных задач. Примеры.Действие группы вращений куба на его элементы.Цикловой индекс: определение и свойства.
Вычислениечисла орбит через цикловой индекс. Примеры.Решения комбинаторной задачи об ожерельях.Теорема Редфилда-Пойа и её применение для решениякомбинаторных задач. Примеры.316 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаГрупповые (линейные) коды317 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у.
множествРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств318 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у.
множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать319 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множеств320 / 432Частично упорядоченные множества: определение и примерыОпределениеПару P = h P, 6 i, где P � непустое множество, а 6 �рефлексивное, антисимметричное и транзитивное бинарноеотношение на нём, называют частично упорядоченныммножеством (сокращённо ч.у. множеством).Рефлексивность: x 6 x;Антисимметричность: (x 6 y) N (y 6 x) ) x = y;Транзитивность: (x 6 y) N (y 6 z) ) x 6 z.Примерыh P(M ), ✓ i � классический пример ч.у.
множества(упорядочивание множеств по включению, M 6= ?);h , 6 i и h , | i � два упорядочивания одного множества.Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествЧ.у. множество P = h P, 6 i � основные понятия:если (x 6 y) _ (y 6 x), то x и y сравнимы (x ⇠ y), иначе онинесравнимы (x ⌧ y);полный (линейный) порядок, если 8x, y (x ⇠ y);если в P нет ни одной пары различных сравнимых элементов,то это тривиально упорядоченное множество;x непосредственно предшествует y (y непосредственно следуетза x), если x 6 z 6 y ) (z = x) _ (z = y) (x l y);{ x 2 P | a 6 x 6 b } � интервал [ a, b ];defv1 6 .
. . 6 vn = [v1 , . . . , vn ] � цепь (n или n), а совокупностьпопарно несравнимых элементов � антицепь в P;цепь максимальная (или насыщенная), если при добавлении кней любого элемента она перестаёт быть цепью;если 8x, y ( (x 6 y) ) (y x) ), то � двойственныйdefпорядок на P , > = или 6d =>.321 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествДиаграммы ХассеРис.
4. Диаграммы 4-х нетривиальных непомеченных 3-элементныхч.у. множеств322 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествЧ.у. множества: особые элементыОпределениеЭлемент u 2 P ч.у. множества h P, 6 i называют:максимальным, если u 6 x ) u = x,минимальным, если u > x ) u = x,наибольшим, если x 6 u,наименьшим, если x > uдля любых x 2 P .323 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОсновные понятия теории ч.у. множествЧ.у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
