ID: 48693

Название работы: Прикладная алгебра

Категория: Контрольная

Предметная область: Математика и математический анализ

Описание: Понятие группы, подгруппы, факторгруппы, индекса группы по подгруппе. Теорема Лагранжа. Понятие поля. Построение конечных полей с помощью неприводимых многочленов (привести пример). Полиномиальное и степенное представление элементов поля.

Язык: Русский

Дата добавления: 2014-03-25

Размер файла: 2 MB

Работу скачали: 44 чел.

Прикладная алгебра

Оглавление

[1] Оглавление [2] Понятие группы, подгруппы, факторгруппы, индекса группы по подгруппе. Примеры. Теорема Лагранжа. [2.1] Группа. [2.2] Подгруппа. [2.3] Факторгруппа. [2.4] Индекс группы по подгруппе. [2.5] Примеры [2.6] Теорема Лагранжа. [3] Понятие циклической группы. Структура подгрупп циклической группы. Количество порождающих элементов. [3.1] Циклическая группа. [3.2] Структура подгрупп циклической группы. [3.3] Количество порождающих элементов. [4] Понятие кольца, подкольца, факторкольца, евклидова кольца, идеала в кольце. Примеры. [4.1] Кольцо. [4.2] Подкольцо. [4.3] Факторкольцо. [4.4] Евклидово кольцо. [4.5] Идеал в кольце. [4.6] Примеры [5] Расширенный алгоритм Евклида и его применение. [6] Понятие поля. Построение конечных полей с помощью неприводимых многочленов (привести пример). Полиномиальное и степенное представление элементов поля. [6.1] Поле. [6.2] Построение конечных полей с помощью неприводимых многочленов [6.3] Полиномиальное и степенное представление элементов поля. [7] Алгоритм нахождения всех корней многочлена  f(x)  над полем [8] Минимальные многочлены для элементов конечного поля. Алгоритм нахождения минимального многочлена. [8.1] Определение минимального многочлена. [8.2] Алгоритм нахождения минимального многочлена. [9] Теорема Хэмминга. Пример построения кода Хэмминга. [9.1] Теорема Хэмминга. [9.2] Пример построения кода Хэмминга. [10] Коды БЧХ: определение, примеры кодов с исправлением одной, двух и трех ошибок. [10.1] Определение кода БЧХ. [10.2] Код с исправлением одной ошибки. [10.3] Код с исправлением двух ошибок. [10.4] Код с исправлением трех ошибок [11] Коды БЧХ: общая схема декодирования. [12] Понятие действия группы на множестве, фиксатор и стабилизатор. Примеры. [12.1] Действие группы на множестве. [12.2] Фиксатор. [12.3] Стабилизатор. [12.4] Примеры [13] Лемма Бернсайда и её применение. [13.1] Лемма Бернсайда. [13.2] Применение. [14] Цикловой индекс действия группы. [15] Группы симметрий правильных многоугольников (диэдральные группы) и группы вращений правильных многогранников. Примеры. Их цикловые индексы. [16] Теорема Редфилда-Пойа и её применение. [17] Идеалы и фильтры частично упорядоченного множества. Конусы. Точные грани. [17.1] Частично упорядоченное множество. [17.2] Порядковый идеал. [17.3] Порядковый фильтр. [17.4] Верхние и нижние конусы и грани. [17.5] Главные идеалы и фильтры. [17.6] Точные грани. [18] Теорема Шпильрайна. Линейное продолжение частично упорядоченного множества. [18.1] Теорема Шпильрайна. [18.2] Линейное продолжение частично упорядоченного множества. [19] Спектр и размерность частично упорядоченного множества. [19.1] Спектр частично упорядоченного множества. [19.2] Размерность частично упорядоченного множества. [20] Фундаментальная теорема о конечных дистрибутивных решётках. [21] Соответствия Галуа. [22] Источники

Понятие группы, подгруппы, факторгруппы, индекса группы по подгруппе. Примеры. Теорема Лагранжа.

Группа. 

{(1) – стр. 12}
Группа G = <M, ∗> — это такая пара из множества M и бинарной операции ∗ на этом множестве, что выполняются следующие свойства (аксиомы группы):

•  G1: (x ∗ y) ∗ z = x ∗ (y ∗ z ) (ассоциативность);
  •  G2: (аксиома единицы) существует единственный единичный элемент e такой, что для любого x выполняется e ∗ x = x ∗ e = x;
    •  G3: для любого элемента x существует ровно один обратный элемент, т. е. такой элемент y, для которого y ∗ x = x ∗ y = e (обратный элемент обозначается x−1).

Подгруппа. 

{(1) – стр. 24}
Пусть G – группа, и для какого-то множества  выполнены свойства:

•  
  •  Если , то
    •  Если , то

H называется подгруппой G.

Факторгруппа. 

{(1) – стр. 52}
Группа смежных классов группы G по нормальному делителю H.

Индекс группы по подгруппе. 

{(1) – стр. 28}
Количество смежных классов группы G по подгруппе H называется индексом подгруппы и обозначается через (G : H).

Примеры

Теорема Лагранжа. 

{(1) – стр. 29}
Пусть H — подгруппа группы G. Тогда порядок H является делителем порядка G: |G| = (G : H) · |H|.

Понятие циклической группы. Структура подгрупп циклической группы. Количество порождающих элементов.

Циклическая группа.

{(1) – стр. 22}
В циклической группе есть такой элемент (он называется порождающим элементом группы), что каждый элемент группы может быть получен (многократным) применением групповой операции к порождающему.

Структура подгрупп циклической группы.

{(1) – стр. 30}
Всякая подгруппа циклической группы — циклическая.

Количество порождающих элементов.

{(2)}
У циклической группы порядка n существует ровно φ(n) порождающих элементов, где φ — функция Эйлера.

Понятие кольца, подкольца, факторкольца, евклидова кольца, идеала в кольце. Примеры.

Кольцо.

{(1) – стр. 85}
Кольцо — это множество R с двумя бинарными операциями сложения + и умножения · такими, что

•  R1: относительно сложения R — коммутативная группа (которая называется аддитивной группой кольца);
  •  R2: умножение ассоциативно; (в других источниках может не быть аксиомой – могут выделяться отдельно ассоциативные кольца)
    •  R3: a · (b + c) = a · b + a · c; (b + c) · a = b · a + c · a (дистрибутивность умножения относительно сложения слева и справа).

Если в кольце имеется единичный элемент для умножения, то кольцо называется кольцом с единицей. Если умножение коммутативно, то такое кольцо называется коммутативным кольцом.

Подкольцо.

Такое подмножество кольца, которое является подгруппой по сложению и замкнуто относительно операции умножения.

Факторкольцо.

{(2)}
Пусть I – идеал кольца R. Определим на R отношение эквивалентности:  тогда и только тогда, когда . Класс эквивалентности элемента обозначается как .
Факторкольцо R|I – множество классов смежности элементов кольца R по модулю его идеала I, на котором определены операции сложения и умножения:

•  (a + I) + (b + I) = (a + b) + I
  •  (a + I) · (b + I) = ab + I
    

Евклидово кольцо.

{(1) – стр. 101}
Коммутативное кольцо R называется евклидовым , если для него выполнены следующие свойства:

•  Кольцо R — целостное (т. е. в нём нет делителей нуля: из ab = 0 следует, что a = 0 или b = 0).
  •  Для каждого ненулевого элемента кольца определена числовая характеристика — норма, которая принимает целые неотрицательные значения. Т. е. норма — это такое отображение N : R \ {0} → Z, что N (r)  0.
    •  Возможность деления с остатком означает, что для любых элементов a, b кольца, b ≠ 0, существуют такие q, r, что a = qb + r и либо r = 0, либо N (r) < N (b). Элемент r называется остатком от деления a на b. Это основное свойство нормы.
    •  Норма произведения двух ненулевых сомножителей больше либо равна норме любого из сомножителей. Формально: для любых a, b ∈ R, a ≠ 0, b ≠ 0 выполнено N (ab)  max(N (a), N (b)).
      

Идеал в кольце.

{(1) – стр. 93}
Подмножество I ∈ R называется левым идеалом , если выполняются два следующих условия:

•  если a, b ∈ I , то a − b ∈ I;
  •  если a ∈ I, r ∈ R, то ra ∈ I .

Аналогично определяются правые и двусторонние идеалы.

Примеры

Расширенный алгоритм Евклида и его применение.

{(3) – слайд 86}
Задача вычисления НОД(a, b) натуральных чисел a и b (a  b).
Если d – общий делитель пары чисел (a, b), то d является общим делителем для чисел (a – b, b). Отсюда:

1.  пары чисел (a, b) и (a – kb, b) (k ∈ Z) имеет одинаковые общие делители;
   1.  вместо a - kb можно взять остаток r0 от деления нацело a на b: a = bq + r0, q ∈ Z, 0 ≤ r0 < b;
   2.  затем, переставив числа в паре, можно повторить процедуру; она закончится, т.к. числа в паре уменьшаются, но остаются неотрицательными.

В результате: за конечное число шагов образуется пара (rn, 0).Ясно, что НОД(a, b) = rn.
Для нахождения по паре натуральных чисел (a; b) натурального d и пары целых (x, y) таких, что
d = НОД(a, b) = ax + ay, применяют расширенный алгоритм Евклида.
Расширенный алгоритм Евклида повторяет схему простого метода, в котором на каждом шаге:

•  дополнительно вычисляются xi и yi по формулам
  
•  справедливо соотношение
  

Алгоритм Евклида и его расширенная версия остаётся справедливым в любом евклидовом кольце, следовательно, и в любом поле Галуа. Поэтому: обратный элемент y(x) для некоторого многочлена b(x) в поле  определяется соотношением

Оно может быть решено путем применения расширенного алгоритма Евклида для пары многочленов (a; b) в поле F. Решение данных уравнений существует всегда: поскольку a — неприводимый многочлен и

Понятие поля. Построение конечных полей с помощью неприводимых многочленов (привести пример). Полиномиальное и степенное представление элементов поля.

Поле.

{(4) – стр. 135}
Поле – коммутативное кольцо с единицей, содержащее не менее двух элементов, в котором каждый отличный от нуля элемент имеет обратный элемент.
{(1) – стр. 98}
Поле – это такое кольцо, ненулевые элементы которого образуют группу относительно умножения, т. е. выполняются дополнительные свойства:

•  существует единичный элемент относительно умножения 1, для любого другого элемента a выполнено a · 1 = 1 · a = a;
  •  для a ≠0 существует обратный элемент a−1, для которого a−1· a = a · a−1= 1.
    

Построение конечных полей с помощью неприводимых многочленов 

{(3) – слайд 67}

•  Выбираем простое p и фиксируем поле
  •  Образуем кольцо  многочленов над ним.
    •  Выбираем натуральное n и неприводимый многочлен 
    •  Идеал  порождает фактормножество , элементы которого суть совокупность  остатков от деления многочленов  на : . Множество  является полем Галуа  – расширение n-ой степени поля  (обозначается ).

Пример: построение поля  (слайд 71).

Полиномиальное и степенное представление элементов поля.

Любой элемент циклической группы можно представить как степень примитивного элемента.
Пример: слайды 265 и далее.

Алгоритм нахождения всех корней многочлена  f(x)  над полем ������������.

Минимальные многочлены для элементов конечного поля. Алгоритм нахождения минимального многочлена.

Определение минимального многочлена.

{(3) – слайд 129}
Рассмотрим поле , а в нем — какой-нибудь элемент β и будем интересоваться многочленами, для которых этот элемент является корнем. Многочлен m(x) называется минимальной функцией (или минимальным многочленом, м.м.) для β, если m(x) —нормированный многочлен минимальной степени, для которого β является корнем.

Алгоритм нахождения минимального многочлена.

Теорема Хэмминга. Пример построения кода Хэмминга.

Теорема Хэмминга.

{(1) – стр. 172}
При 2r < n максимальное число t кодовых слов находится в пределах

r  – максимально допустимое число ошибок.
n – длина кода.

Пример построения кода Хэмминга.

{(1) – стр. 173}
n = 2q – 1, r = 1. Для q = 3 построим код Хэмминга (длины 7).
Построим таблицу: слева – диагональная матрица размерности 2q – (q+1), справа все бинарные наборы длины q, содержащие не менее 2-х единиц. Складывая по mod 2 произвольные совокупности строк, получаем 16 различных бинарных наборов, которыми можно закодировать 16 сообщений.

1	0	0	0	1	1	0
0	1	0	0	1	0	1
0	0	1	0	0	1	1
0	0	0	1	1	1	1

Коды БЧХ: определение, примеры кодов с исправлением одной, двух и трех ошибок.

Определение кода БЧХ.

{(3) – слайд 402 и далее}
Циклический код, исправляющий кратные (2 и более) ошибки.
{(5) – стр. 5}
Пусть . Тогда кодом БЧХ называется (n, k, d)-линейный циклический код, в котором порождающий многочлен g(x) определяется как минимальный многочлен для элементов  из поля , где  – произвольный примитивный элемент поля .

Схема построения:

•  Строим поле неприводимый многочлен степени n = 2m – 1.
•  Выберем в циклической группе  примитивный элемент  и рассмотрим его степени , где r – количество ошибок, которые надо исправить.
•  В разложении многочлена  выберем такие неприводимые многочлены, чтобы каждая из указанных степеней была корнем одного из них (не всегда возможно). Тогда
  1.   есть результат перемножения этих многочленов;
     1.  коды — коэффициенты многочленов из идеала  – исправляют r ошибок.
        

Код с исправлением одной ошибки.

{(5) – стр. 6}
Рассмотрим БЧХ-коды для случая поля  Таким образом, . Полином  является примитивным полиномом над . Обозначим через  его произвольный корень. Построим код БЧХ, исправляющий не менее, чем t = 1 ошибку. Его порождающий полином g(x) строится как минимальный многочлен для элементов . Эти элементы входят в один смежный класс . Поэтому . В результате получаем (7; 4; 3)-код, являющийся кодом Хэмминга.

Код с исправлением двух ошибок.

{(5) – стр. 6 внизу, лень переписывать длинные формулы}

Код с исправлением трех ошибок

Слайд 405.

Коды БЧХ: общая схема декодирования.

{(5) – стр. 7}
– полином локаторов ошибок.

1.  Для принятого слова  найти все синдромы
   1.  Найти полином локаторов ошибок  путем решения уравнения  с помощью расширенного алгоритма Евклида;
   2.  Найти все корниполным перебором; пусть найденные корни равны
   3.  Найти позиции ошибок , где  – порядок примитивного элемента ;
   4.  Исправить ошибки
   5.  Найти все синдромы ; если они не равны нулю, то выдать отказ от декодирования.

Понятие действия группы на множестве, фиксатор и стабилизатор. Примеры.

Действие группы на множестве.

{(1) – стр. 46}
Действием группы G на множестве T называется гомоморфизм  биекций множества T (взаимно однозначных отображений множества T на себя)

Фиксатор.

{(3) – слайд 465}
Фиксируем g, т.е. находим все элементы множества T ,которые перестановка g оставляет на месте

Стабилизатор.

{(3) – слайд 465}
Фиксируем t, т.е. находим все перестановки g, которые оставляют данный элемент неподвижным

Примеры

Лемма Бернсайда и её применение.

Лемма Бернсайда.

{(3) – слайды 461 и 467}

•  Отношение эквивалентности на T – . Классы этой эквивалентности называют орбитами. Число орбит обозначается C(G).
•  Лемма Бернсайда:

Применение.

Лемма Бернсайда применяется для решения комбинаторных задач (определить число неэквивалентных слов, перестановок, раскрасок) – слайды 481 и далее.
Для применения универсального способа вычисления C(G) надо представить эквивалентные элементы множества как классы эквивалентности действия некоторой группы на этом множестве.

Цикловой индекс действия группы.

{(3) – слайд 492}
Сопоставим каждой перестановке  вес по правилу , где  – количество циклов длины k в перестановке (вики). Цикловой индекс действия группы – средний вес подстановок в группе:

Группы симметрий правильных многоугольников (диэдральные группы) и группы вращений правильных многогранников. Примеры. Их цикловые индексы.

Теорема Редфилда-Пойа и её применение.

{(3) – слайд 532}

1.  К множеству T, |T| = N,группе G, |G|= n и действию G:T добавим множество  меток. Дадим вес элементам R: .
2.  Теорема Редфилда-Пойа
   Цикловой индекс действия группы G на RT есть
3.  Применяется в комбинаторных задачах для подсчета количества разметок данного типа (содержащих данное количество элементов конкретного цвета).

Идеалы и фильтры частично упорядоченного множества. Конусы. Точные грани.

Частично упорядоченное множество.

{(3) – слайд 575}
Пару , где P – непустое множество, а ≤ – рефлексивное, антисимметричное и транзитивное бинарное отношение на нём, называют частично упорядоченным множеством.

•  Рефлексивность – x ≤ x
•  Антисимметричность –
•  Транзитивность –
  

Порядковый идеал.

Подмножество J элементов ч.у. множества  называется его (порядковым) идеалом, если

Порядковый фильтр.

Подмножество F элементов P называется его (порядковым) фильтром, если

Верхние и нижние конусы и грани.

Пусть  – ч. у. множество и . Множества , определяемые условиями
называются верхним и нижним конусами множества A, а их элементы — верхними и нижними гранями множества A соответственно.

Главные идеалы и фильтры.

фильтр P. Такие идеалы и фильтры называют главными.

Точные грани.

Наименьший элемент в  называется точной верхней гранью множества A (символически sup A).
Наибольший элемент в  называется точной нижней гранью множества A (символически inf A).

Теорема Шпильрайна. Линейное продолжение частично упорядоченного множества.

Теорема Шпильрайна.

{(3) – слайд 607}
Любой частичный порядок ≤ может быть продолжен до линейного на том же множестве. Каждый порядок есть пересечение всех своих линейных продолжений (линеаризаций).

Линейное продолжение частично упорядоченного множества.

Спектр и размерность частично упорядоченного множества. 

Спектр частично упорядоченного множества.

{(3) – слайд 622}
, Pr(E) – вероятность E.

Размерность частично упорядоченного множества.

{(3) – слайд 627}
Наименьшее число линейных порядков, дающих в пересечении данное ч.у. множество P называется его порядковой размерностью (символически dim(P)).
Наименьшее число линейных порядков, таких, что P вкладывается в их декартово произведение, называется мультипликативной размерностью.

Фундаментальная теорема о конечных дистрибутивных решётках.

{(3) – слайд 696}
Фундаментальная теорема.
Всякая конечная дистрибутивная решётка L изоморфна решётке порядковых идеалов ч.у. множества её неразложимых элементов:

Соответствия Галуа.

{(3) – слайд 715}
Пусть P и Q – частично упорядоченные множества. Пара отображений , удовлетворяющая свойствам:

•   антиизотонны
•  – операторы замыкания (на P и Q соответственно).

называется соответствием Галуа между P и Q.

Источники

1.  Ю. И. Журавлёв, Ю. А. Флёров, М. Н. Вялый – «Дискретный анализ. Основы высшей алгебры»
2.  http://ru.wikipedia.org/
3.  Слайды
4.  Г. Д. Ким – «Линейная алгебра»
5.  PA_coding_algorithms.pdf