Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 137
Текст из файла (страница 137)
4. Найдите расстояние между строками 110011001 и 111100001. 5. Найдите три строки, ортогональные к строке 110011001. 6. Найдите три строки, ортогональные к строке 010101111. 7. Для заданной порождающей матрицы а) найдите матрицу Сй, б) используя только матрицу С-~, исправьте ошибки (если они имеются) в переданных сообщениях 1110110, 1011000, 1101100 и 1111110.
8. Для заданной порождающей матрицы Пусть Н„обозначает матрицу, полученную из матрицы А„заменой 0 на 1, а 1— на — 1, для каждого элемента А; для 1 < А,З < г~. Таким образом, Н, ~111 Матрица Н„обладает свойством: Н„Н„' = п1, где 1 — единичная матрица. Матрицы, обладающие таким свойством, называются матрицами Адамара. Порождаемый ими код называется кодом Адамара. 774 ГЛАВА За. Теория косое 1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 1 1 О 0 0 1 1 0 1 0 1 0 0 0 1 1 [!!!!!1!] 11.
Докажите теорему 18.4: Функция расстояния Хемминга обладает следую- шими свойствами; а) для строк с и с' расстояние б(с, с') = 0 тогда и только тогда, когда с = с', б) для строк с и с' расстояние б(с, с') = б(с', с). 12. Постройте код Рида-Мюллера, Ян 13. Постройте матрицы Адамара Нз, Н4, На и Н1е. а) найдите матрицу СВ~; б) используя только матрицу СзВ, неправые ошибки (если они имеются) в переданных сообщениях 1111110, 1011001, 1101100 и 1111101. 9.
Для каждой матрицы Хемминга из упражнений 7 и 8, если строка 1001110 передана как 1011010, то каков исправленный код? Как это повлияло на исходное закодированное слово? 10. Какие из приведенных ниже матриц являются матрицами Хемминга? 776 ГЛАВА 19. Перечисление цветов Раскраска, изображенная на рис.
19.3, эквивалентна только самой себе, т.к. любое вращение или отражение дает в результате ту же раскраску. Аналогично, раскраска, изображенная на рис. !9.4, эквивалентна только самой себе. В В Я Я Рис. 19.3 В В Рис. 19.4 Следующие две раскраски на рис. !9.5 эквивалентны, поскольку каждая получена из другой вращением на 90', и никакие другие раскраски в результате вращения или отражения не могут быть получены.
В В В В Рис, 19Б Наконец, легко видеть, что все раскраски множества на рис. !9.6 эквивалентны, так как каждая раскраска может быть получена из другой вращением. В В Я Рис. 19.б В В В В Можно заметить, что в случае двухцветных раскрасок квадрата отражения фактически не нужны, т.к. всевозможные эквивалентные раскраски можно получить в результате одних лишь вращений. Вспомним раздел 9.4, в котором вращения и отражения квадрата описаны подгруппой Я~ (группой перестановок четырех элементов). Эта группа называется октической груллой, или групаой симметрий квадрата.
Для квадрата, изображенного на рис. !9.7, 3 2 1 4 4 3 являются отражениями, которые меняют местами вершины 1 и 3 и вершины 2 и 4, соответственно. РАЗДЕЛ 19.1. Теорема Бернсайда 777 4 Рос. 19.7 Перестановки и Фг= 2 1 4 4 3 2 1 отражают квадрат относительно горизонтальной оси, проходящей через центр квадрата, и относительно вертикальной оси, проходящей через центр квадрата. Перестановки р,, рг и рз вращают квадрат по часовой стрелке соответственно на 90', 180' и 270'.
Р 2 3 4 1 ' Рг 3 4 1 2 ' Рз 4 1 — тождественная перестановка 1 2 3 4 Заметим, что группа симметрий правильного и-угольника всегда содержит 2и преобразований. Всегда имеется и вращений. Если число и нечетное, то имеется и отражений относительно осей, проходящих через каждую вершину и середину противоположной стороны. Если число и четное, то имеется —" отражений от- г носительно осей, проходящих через противоположные вершины, и -" отражений относительно осей, проходящих через середины противоположных сторон многоугольника.
В каждом случае получаем и вращений и и отражений, Возвращаясь к двухцветным раскраскам квадрата, отметим, что для каждой перестановки и можно образовать перестановку д раскрасок, такую что о(С,) = С„ где С, — раскраска, полученная в результате того, что квадрат с раскраской С; преобразуется перестановкой о. Например, р~(С1) = Сг и рг(Сы) = С~г. Для простоты будем писать вместо д просто о и использовать о как для обозначения перестановок вершин, так и для обозначения перестановок цветов. Ранее мы говорили об эквивалентных раскрасках.
Теперь, согласно такой эквивалентности раскрасок, введем отношение эквивалентности. Определим отношение Л на множестве раскрасок соотношением С,ЛС, если в циклической группе существует перестановка о такая, что о(С;) = С . Покажем, что Л вЂ” отношение эквивалентности. Рефлексивность отношения Л очевидна, поскольку г'(С,) = С, для любой раскраски С,. Если С,ЛС,, то существует перестановка о такая, что о(С,) = С .
Но поскольку перестановка о принадлежит октической группе и о. '(С,) = С„то С,ЛС,. Если С,ЛС, и С,ЛСю то существуют такие перестановки о и с', что о(С,) = С и о(С1) = Сь. Следовательно, о'о(С,) = Сю и, поскольку о'о также является перестановкой из 778 ГПКВА 19. перечисление цветов группы симметрий квадрата, имеем С,гсСь. Следовательно, )т — отношение эквивалентности, которое можно аналогичным образом получить для произвольного множества К раскрасок на множестве Я и группы перестановок 5.
Это дает нам следующую теорему. ТЕОРЕМА 19.1. Пусть К вЂ” множество раскрасок на множестве 5, и С вЂ” группа перестановок 5. Пусть отношение В на К определено следующим образом: С,ЛС,, если существует перестановка о е С такая, что о.(С,) = С . Отношение Л есть отношение эквивалентности. Возвращаясь к двухцветным раскраскам квадрата, отметим, что когда впервые упоминалась эквивалентность раскрасок, мы имели в виду, что одна раскраска может быть получена из другой посредством вращения и отражения. Говоря об эквивалентных раскрасках в упомянутой выше теореме, мы имеем в виду, что одна раскраска может быть получена из другой посредством перестановки. Поскольку каждую перестановку можно рассматривать как вращение или отражение, становится очевидным, что это, по сути, одна и та же эквивалентность.
Необходимо помнить, что наша цель — найти количество "различных" раскрасок, где раскраски, принадлежащие одному классу эквивалентности, считаются "одинаковыми". Следовательно, нас фактически интересует количество классов эквивалентности, поскольку оно совпадает с количеством "различных" раскрасок. Например, рассмотрим круглый стол, за которым сидит п человек. Предположим, что оба способа разместить людей являются одинаковыми, если у каждого из сидящих тот же сосед справа и тот же сосед слева. Следовательно, если стол вращать, то взаимное расположение людей за столом при этом не меняется.
Мы не будем рассматривать отражения, т.к. в результате сосед слева и сосед справа поменяются местами, а вся еда окажется на полу. Существует гй способов разместить п человек за столом. Поскольку два способа размещения людей эквивалентны, или одинаковы, если один способ получен из другого вращением и всего имеется п вращений, то количество различных способов разместить людей равно количеству классов эквивалентности.
Но число классов эквивалентности равно и! (число способов разместить п человек за столом), деленному на и (число таких размещений в каждом классе эквивалентности), и поэтому равно †'„' = (и — 1)!. Такой метод подсчета оправдывает себя, потому что каждое вращение дает новый элемент в классе эквивалентности.
На вопрос, куда подевались цвета, ответим, что каждого человека можно рассматривать как представителя своего собственного цвета, поэтому фактически рассматривается п-угольник, в котором все вершины окрашены в различные цвета. Снова, возвращаясь к двухцветной раскраске квадрата, заметим, что не каждая перестановка дает другую раскраску. Например, рз(Сы) = Сы = бг(Сы) = бз(Сы). На самом деле нам уже известно, что классы эквивалентности различны по размеру. Поэтому нужен иной подход. Для фиксированной раскраски С пусть Сс = (о: а.(С) = С), так что Сс — множество всех перестановок в С, которые не меняют С.
Множество Сс называется стабилизатором, или стационарной подгруппой С. ТЕОРЕМА 19.2. Для фиксированной раскраски С стабилизатор Сс есть подгруп- па группы С, группы перестановок. РАЗДЕЛ 19.1, георемв Бернсвйда 779 ДОКАЗАТЕЛЬСТВО. Для доказательства, что Сгг — группа, покажем сначала, что если «т;,«т, е Сс, то а; о а е Сс. Но «т,(С) = С и «т (С) = С, а значит, «т, о о (С) = а,(сг.(С)) = «т,(С) = С и а; о о; Е Сс. Очевидно, что тождественная перестановка 1 принадлежит Са, поскольку 1(С,) = С, для каждой раскраски С;.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
