Прикладная алгебра. Суровый теормин (1127343)
Текст из файла
Прикладная алгебра. Суровый теормин.ContentsПонятие группы, подгруппы, факторгруппы, индекса группы по подгруппе. Примеры. Теорема Лагранжа. ....... 1Понятие циклической группы. Структура подгрупп циклической группы. Количество порождающих элементов...........................................................................................................................................................................................
2Понятие кольца, подкольца, факторкольца, евклидова кольца, идеала в кольце. Примеры. ................................ 2Расширенный алгоритм Евклида и его применение. .................................................................................................. 3Понятие поля.
Построение конечных полей с помощью неприводимых многочленов (привести пример).Полиномиальное и степенное представление элементов поля. ............................................................................... 4Алгоритм нахождения всех корней многочлена f(x) над полем . ........................................................................ 5Минимальные многочлены для элементов конечного поля. Алгоритм нахождения минимального ................... 5Теорема Хэмминга.
Пример построения кода Хэмминга. .......................................................................................... 5Коды БЧХ: определение, примеры кодов с исправлением одной, двух и трех ошибок. ......................................... 5Коды БЧХ: общая схема декодирования. ..................................................................................................................... 6Понятие действия группы на множестве, фиксатор и стабилизатор. Примеры. ......................................................
6Лемма Бернсайда и её применение. ............................................................................................................................ 7Цикловой индекс действия группы. .............................................................................................................................. 7Группы симметрий правильных многоугольников (диэдральные группы) и группы вращений правильныхмногогранников.
Примеры. Их цикловые индексы. .................................................................................................... 7Теорема Редфилда-Пойа и её применение. ................................................................................................................. 7Идеалы и фильтры частично упорядоченного множества. Конусы. Точные грани .................................................. 8Теорема Шпильрайна.
Линейное продолжение частично упорядоченного множества. ........................................ 8Спектр и размерность частично упорядоченного множества. ................................................................................... 8Фундаментальная теорема о конечных дистрибутивных решётках. ......................................................................... 9Соответствия Галуа. ......................................................................................................................................................... 9Понятие группы, подгруппы, факторгруппы, индекса группы поподгруппе. Примеры.
Теорема Лагранжа.a. {(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).b. {(1) – стр. 24}Подгруппа.Пусть G – группа, и для какого-то множества H ⊂ G выполнены свойства: ∈H Если , ∈ H, то ∙ ∈ H Если ∈ H, то −1 ∈ HH называется подгруппой G.c. {(1) – стр. 52}Факторгруппа.Группа смежных классов группы G по нормальному делителю H.d. {(1) – стр.
28}Индекс группы по подгруппе.Количество смежных классов группы G по подгруппе H называется индексом подгруппы иобозначается через (G : H).e. Примерыf. {(1) – стр. 29}Теорема Лагранжа.Пусть H — подгруппа группы G. Тогда порядок H является делителем порядка G: |G| = (G : H) · |H|.Понятие циклической группы. Структура подгрупп циклическойгруппы.
Количество порождающих элементов.g. {(1) – стр. 22}Циклическая группа.В циклической группе есть такой элемент (он называется порождающим элементом группы), чтокаждый элемент группы может быть получен (многократным) применением групповой операции кпорождающему.h. {(1) – стр. 30}Структура подгрупп циклической группы.Всякая подгруппа циклической группы — циклическая.i.
{(2)}Количество порождающих элементов.У циклической группы порядка n существует ровно φ(n) порождающих элементов, где φ — функцияЭйлера.Понятие кольца, подкольца, факторкольца, евклидова кольца, идеала вкольце. Примеры.j. {(1) – стр. 85}Кольцо.Кольцо — это множество R с двумя бинарными операциями сложения + и умножения · такими, что R1: относительно сложения R — коммутативная группа (которая называется аддитивной группойкольца); R2: умножение ассоциативно; (в других источниках может не быть аксиомой – могут выделятьсяотдельно ассоциативные кольца) R3: a · (b + c) = a · b + a · c; (b + c) · a = b · a + c · a (дистрибутивность умножения относительносложения слева и справа).Если в кольце имеется единичный элемент для умножения, то кольцо называется кольцом сединицей. Если умножение коммутативно, то такое кольцо называется коммутативным кольцом.k.
Подкольцо.Такое подмножество кольца, которое является подгруппой по сложению и замкнуто относительнооперации умножения.l. {(2)}Факторкольцо.Пусть I – идеал кольца R. Определим на R отношение эквивалентности: ∼ тогда и только тогда,когда − ∈ I. Класс эквивалентности элемента обозначается как + I.Факторкольцо R|I – множество классов смежности элементов кольца R по модулю его идеала I, накотором определены операции сложения и умножения: (a + I) + (b + I) = (a + b) + I (a + I) · (b + I) = ab + Im. {(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)).n. {(1) – стр. 93}Идеал в кольце.Подмножество I ∈ R называется левым идеалом , если выполняются два следующих условия: если a, b ∈ I , то a − b ∈ I; если a ∈ I, r ∈ R, то ra ∈ I .Аналогично определяются правые и двусторонние идеалы.o. ПримерыРасширенный алгоритм Евклида и его применение.{(3) – слайд 86}Задача вычисления НОД(a, b) натуральных чисел a и b (a b).Если d – общий делитель пары чисел (a, b), то d является общим делителем для чисел (a – b, b).
Отсюда:p. пары чисел (a, b) и (a – kb, b) (k ∈ Z) имеет одинаковые общие делители;q. вместо a - kb можно взять остаток r0 от деления нацело a на b: a = bq + r0, q ∈ Z, 0 ≤ r0 < b;r. затем, переставив числа в паре, можно повторить процедуру; она закончится, т.к. числа в пареуменьшаются, но остаются неотрицательными.В результате: за конечное число шагов образуется пара (rn, 0).Ясно, что НОД(a, b) = rn.Для нахождения по паре натуральных чисел (a; b) натурального d и пары целых (x, y) таких, чтоd = НОД(a, b) = ax + ay, применяют расширенный алгоритм Евклида.Расширенный алгоритм Евклида повторяет схему простого метода, в котором на каждом шаге:a.
дополнительно вычисляются xi и yi по формулам = −2 − −1 , = −2 − −1 , = 0,1,2, … −2 = −1 = 1b. справедливо соотношение = −2 − −1 = (−2 + −2 ) − (−1 + −1 ) = (−2 − −1 ) + (−2 − −1 )= + Алгоритм Евклида и его расширенная версия остаётся справедливым в любом евклидовом кольце,следовательно, и в любом поле Галуа.
Поэтому: обратный элемент y(x) для некоторого многочлена b(x) вполе = []/(()) определяется соотношением () ∙ () = 1 ⟺ () ∙ () + () ∙ () = 1Оно может быть решено путем применения расширенного алгоритма Евклида для пары многочленов (a; b)в поле F. Решение данных уравнений существует всегда: поскольку a — неприводимый многочлен иdeg < deg ⟹ НОД(, ) = 1Понятие поля. Построение конечных полей с помощью неприводимыхмногочленов (привести пример).
Полиномиальное и степенноепредставление элементов поля.s. Поле.{(4) – стр. 135}Поле – коммутативное кольцо с единицей, содержащее не менее двух элементов, в котором каждыйотличный от нуля элемент имеет обратный элемент.{(1) – стр. 98}Поле – это такое кольцо, ненулевые элементы которого образуют группу относительно умножения, т.е. выполняются дополнительные свойства: существует единичный элемент относительно умножения 1, для любого другого элемента aвыполнено a · 1 = 1 · a = a; для a ≠0 существует обратный элемент a−1, для которого a−1· a = a · a−1= 1.t. {(3) – слайд 67}Построение конечных полей с помощью неприводимых многочленов (с примером)̅ , 1̅, … , ̅̅̅̅̅̅̅ Выбираем простое p и фиксируем поле = 〈{0 − 1}, +mod ,∙mod 〉. Образуем кольцо [] многочленов над ним. Выбираем натуральное n и неприводимый многочлен () = + ⋯ + 1 1 + 0 ∈ [] Идеал (()) порождает фактормножество []/(()), элементы которого суть совокупность{()} остатков от деления многочленов ∈ [] на (): () = () ∙ () + ().Множество {()} является полем Галуа ( ) – расширение n-ой степени поля (обозначается ).Пример: построение поля 23 (слайд 71).u.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.