48693

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

Контрольная

Математика и математический анализ

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

Русский

2014-03-25

2 MB

40 чел.

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

Оглавление

[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 является общим делителем для чисел (ab, 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).
Построим таблицу: слева – диагональная матрица размерности 2
q – (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


 

А также другие работы, которые могут Вас заинтересовать

10643. Технология программирования. Основные понятия и подходы 585.5 KB
  Технология программирования. Основные понятия и подходы Технология программирования и основные этапы ее развития Жизненный цикл и этапы разработки программного обеспечения ВВЕДЕНИЕ Программирование сравнительно молодая и быстро развивающаяся...
10644. Приемы обеспечения технологичности программных продуктов 295 KB
  Приемы обеспечения технологичности программных продуктов Понятие технологичности программного обеспечения. Модули и их свойства. Нисходящая и восходящая разработка программного обеспечения. ВВЕДЕНИЕ В условиях индуст...
10645. Обеспечения технологичности программных продуктов 617 KB
  Тема: Обеспечения технологичности программных продуктов 1.Структурное и неструктурное программирование. Средства описания структурных алгоритмов. Стиль оформления программы. 2. Эффективность и технологичность. 3. Программирование
10646. Тестирование программных продуктов 1.29 MB
  Тестирование программных продуктов Виды контроля качества разрабатываемого программного обеспечения Ручной контроль программного обеспечения Структурное тестирование Функциональное тестирование Тестирования модулей и к...
10647. Обеспечение функциональности и надежности программного средства 83.5 KB
  Обеспечение функциональности и надежности программного средства 1. Примитивы качества программных средств. 2. Защитное программирование. В спецификации качества ПС могут быть дополнительные характеристики критериев качества обеспечен...
10648. Управление конфигурацией в жизненном цикле программных средств 200.5 KB
  Управление конфигурацией в жизненном цикле программных средств 1. Процессы управления конфигурацией программных средств 2. Этапы и процедуры при управлении конфигурацией программных средств Вопрос 1. Процессы управления конфигурацией пр...
10649. Разработка требований к программным средствам 196 KB
  Тема: Разработка требований к программным средствам 1. Организация разработки требований к сложным программным средствам 2. Процессы разработки требований к характеристикам сложных программных средств 3. Структура основных документов отражающих требования к прогр
10650. Пакеты программ MathCad и Excel 247 KB
  Лабораторная работа 1 Пакеты программ MathCad и Excel Подавляющее большинство лабораторных работ по курсу €œЧисленные методы€œ может быть выполнено на базе программ MathCad и Excel которые содержат все необходимые вычислительные инструменты; удобны в испо...
10651. Действия над приближенными числами 153.5 KB
  Лабораторная работа 2 Действия над приближенными числами Цель работы. Изучить правила округления приближенных чисел на примере сходимости степенного ряда к известному значению и с заданной точностью. Освоить понятия абсолютной и относительной погрешностей и ...