48693

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

Контрольная

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

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

Русский

2014-03-25

2 MB

35 чел.

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

Оглавление

[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


 

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

49292. Составление математической модели турбокомпрессора по заданным расходным характеристикам 149.54 KB
  В качестве недостатка таких методов можно привести пример когда для вновь создаваемого или форсируемого двигателя основной технической проблемой становится к примеру выбор параметров турбокомпрессора или топливного насоса высокого давления ТНВД. Применительно к турбокомпрессорам это могут быть расходные характеристики которые широко распространяются их производителями с целью увеличения рынка сбыта. 1 составить математическую модель турбокомпрессора.
49293. Учет заработной платы сотрудников предприятия 354.85 KB
  Задача «Учет заработной платы сотрудников предприятия» решается с целью получения сведений о средней и суммарной заработной плате каждого сотрудника с начала года до указанного месяца, упорядоченные по алфавиту.
49295. Разработка грузового плана нефтеналивного судна т/х «Сейфула Кади» 161.78 KB
  В данной работе разрабатывается грузовой план нефтеналивного судна т х Сейфула Кади выполняется расчет ходовых запасов; размещение груза расчет кренящего момента дифферентовка и соответствующее принятие балласта расчет остойчивости и прочности составления чертежа грузового плана. Основные характеристики и размерения судна: Тип Стальное однопалубное двухвинтовое наливное судно без седловатости с двойным дном двойным бортом с баком с машинным отделением и рубками расположенными в корме с 6 грузовыми танками.9 1438 63257...
49296. Автоматизация поддержания параметров микроклимата в животноводческом помещении 1.02 MB
  Состояние микроклимата закрытых животноводческих помещений определяет комплекс физических факторов температура влажность движение воздуха солнечная радиация атмосферное давление освещение и ионизация газовый состав воздуха кислород углекислый газ аммиак сероводород и др. Описание работы технологической линии ОВС включает калорифер радиальный центробежный вентилятор магистральный воздуховод и воздуховоды равномерной раздачи воздуха выходные отверстия которых оборудованы жалюзийными решетками. Отопительновентиляционная...
49298. Характеристика різних інформаційно-довідкових підсистем, правової підтримки керівництва підприємства Українських розробників 60.96 KB
  2 Проблеми правової підтримки керівництва підприємства Метою державної підтримки підприємництва є: 1 створення умов для позитивних структурних змін в економіці України; 2 сприяння формуванню і розвитку підприємництва становлення підприємництва як провідної сили в подоланні негативних процесів в економіці та забезпечення сталого позитивного розвитку суспільства; 3 підтримка вітчизняних виробників; 4 формування умов для забезпечення зайнятості населення України запобігання безробіттю створення нових робочих місць. Державна підтримка...
49299. Малохвильовий перетворювач WAVELET 581.78 KB
  Дискретне Wvelets перетворення 11 Приклади застосування Wvelets перетворення. Інакше називають Wvelet аналізом. Слово Wvelet в перекладі з англійської мови означає елементарну хвилю.