Экзаменационный теоретический минимум (ответы) (1127336)
Текст из файла
Материал из Прикладная алгебраСодержание1 Понятие группы, подгруппы, фактор-группы, индекса группы по подгруппе. Примеры. Теорема Лагранжа.1.1 Группа1.1.1 Свойства1.2 Факторгруппа1.3 Индекс подгруппы в группе1.4 Теорема Лагранжа1.5 Примеры2 Понятие циклической группы. Структура подгрупп циклической группы. Количество порождающих элементов.2.1 Циклическая группа2.1.1 Свойства2.1.2 Пример2.2 Функция Эйлера3 Понятие кольца, подкольца, фактор-кольца, евклидова кольца, идеала в кольце. Примеры.3.1 Кольцо3.1.1 Свойства3.1.2 Дополнительные требования3.1.3 Подкольцо3.2 Идеал3.2.1 Свойства3.3 Факторкольцо3.3.1 Примеры:3.4 Евклидово кольцо3.4.1 Примеры:4 Расширенный алгоритм Евклида и его применение.4.1 Алгоритм4.2 Python4.3 Применение5 Понятие поля.
Построение конечных полей с помощью неприводимых многочленов (привести пример). Полиномиальное истепенное представление элементов поля.5.1 Поле5.1.1 Характеристика поля5.1.2 Свойства:5.1.3 Примеры полей:5.2 Построение поля Галуа5.2.1 Пример построения поля GF(9)5.2.2 Таблица сложения в GF(9)5.2.3 Таблица умножения в GF(9)5.3 Степенное представление элементов поля6 Алгоритм нахождения всех корней многочлена $ f(x) $ над полем $ \mathbb{F}{p} $7 Минимальные многочлены для элементов конечного поля. Алгоритм нахождения минимального многочлена.7.1 Построение:8 Теорема Хэмминга.
Пример построения кода Хэмминга.9 Определение9.1 Теорема Хэмминга9.2 Пример10 Коды БЧХ: определение, примеры кодов с исправлением одной, двух и трех ошибок.10.1 Построение БЧХ кодов:10.2 Пример кода, исправляющего 1 ошибку10.3 Пример кода, исправляющего 2 ошибки10.4 Пример кода, исправляющего 3 ошибки11 Понятие действия группы на множестве, фиксатор и стабилизатор. Примеры.11.1 Действие слева11.2 Действие справа11.3 Комментарии11.4 Фиксатор11.5 Стабилизатор12 Лемма Бернсайда и её применение.12.1 Лемма Бернсайда12.2 Пример13 Цикловой индекс действия группы14 Группы симметрий правильных многоугольников (диэдральные группы) и группы вращений правильных многогранников.Примеры.
Их цикловые индексы.15 Теорема Редфилда-Пойа и её применение15.1 Цикловой индекс действия группы15.2 Теорема Редфилда-Пойа15.3 Пример16 Идеалы и фильтры частично упорядоченного множества. Конусы. Точные грани.16.1 Определение17 Идеал частично упорядоченного множества18 Фильтр частично упорядоченного множества19 Конус20 Точные грани21 Теорема Шпильрайна.
Линейное продолжение частично упорядоченного множества22 Определение22.1 Теорема Шпильрайна23 Спектр и размерность частично упорядоченного множества23.1 Определение23.2 Спектр частично упорядоченного множества23.3 Размерность24 Фундаментальная теорема о конечных дистрибутивных решётках.24.1 Определения24.2 Фундаментальная теорема о конечных дистрибутивных решётках25 Соответствия Галуа.25.1 ОпределениеяПонятие группы, подгруппы, фактор-группы, индекса группы по подгруппе.Примеры.
Теорема Лагранжа.ГруппаНепустое множество G с заданной на нём бинарной операциейследующие аксиомы:∗ : G × G → G называется группой (G, ∗), если выполнены1. ассоциативность: ∀(a, b, c ∈ G) : (a ∗ b) ∗ c =2. наличие нейтрального элемента: ∃e ∈ G ∀a ∈3. наличие обратного элемента: ∀a∈G∃a−1a ∗ (b ∗ c);G : (e ∗ a = a ∗ e = a);∈ G : (a ∗ a−1 = a−1 ∗ a = e)Подгруппа — подмножество H группы G , которое является группой относительно операции, определённой в G .Подгруппа N группы G называется нормальной, если она инвариантна относительно сопряжений, то есть для любогоэлемента n из N и любого g из G , элемент gng −1 лежит в N :СвойстваСвойство сократимости {a, b, c}∈ G, a ≠ b → c ∗ a ≠ c ∗ bФакторгруппаПусть G — группа, и H — её нормальная подгруппа. Тогда на классах смежности H в GaH = { ah ∣ h ∈ H}можно ввести умножение:(aH)(bH) = abHЛегко проверить что это умножение не зависит от выбора элементов в классах смежности, то есть если aH = a′ H и bH =abH = a′ b′ H.
Это умножение определяет структуру группы на множестве классов смежности, а полученная группа G/Hназывается факторгруппой G по H .b′ H, тоИндекс подгруппы в группеИндекс подгруппы H в группе G ― число классов смежности в каждом (правом или левом) из разложений группы G по этойподгруппе H (в бесконечном случае ― мощность множества этих классов).Индекс подгруппы H в группе G обычно обозначается [G: H].Теорема ЛагранжаПусть группа G конечна и H — её подгруппа. Тогда порядок G равен порядку H, умноженному на количество её левых или правыхклассов смежности (индекс). |G| = |H| ∗ (G : H).
Обратное утверждение неверно.ПримерыЦелые числа с операцией сложения. (Z, +) — коммутативная группа с нейтральным элементом 0.Положительные рациональные числа с операцией умножения. Произведение рациональных чисел — снова рациональноечисло, обратный элемент к рациональному числу представляется обратной дробью, имеется ассоциативность и единица.Циклические группы состоят из степеней ⟨a⟩Примеры таких групп — упомянутые уже= {an | n ∈ Z} одного элемента a.
Такие группы всегда коммутативны.целые числа по сложению и группа корней из единицы.Симметрическая группа группа перестановок.Понятие циклической группы. Структура подгрупп циклической группы.Количество порождающих элементов.Циклическая группаГруппа (G, ⋅) называется циклической, если она может быть порождена одним элементом a, то есть все её элементы являютсястепенями a. Обозначение: G = ⟨a⟩.Любая конечная циклическая группа порядка n изоморфна аддитивной группе классов вычетов Zn . Отсюда вытекает, что, сточностью до изоморфизма, существует только одна конечная циклическая группа данного порядка.СвойстваЛюбая подгруппа циклической группы тоже циклична. Циклической будет и всякая фактор-группа циклической группы G/H.У циклической группы порядка n существует ровно φ(n) порождающих элементов, где φ — функция ЭйлераУ циклических подгрупп всегда найдется единственная подгруппа, порядок которой равен порядку делителя.ПримерZ6 = {0, 1, 2, 3, 4, 5}порядок подгруппа k количество порождающих0{0}1{1,2,3,4,5,0} 6 21 12{2,4,0}3{3,0}2 14{4,2,0}3 25{5,4,3,2,1,0} 6 23 2берем порядок, складываем с собой.
получаем подгруппу.Функция ЭйлераФункция Эйлера φ(n) — мультипликативная арифметическая функция, равная количеству натуральных чисел, меньших n ивзаимно простых с ним. При этом полагают, что число 1 взаимно просто со всеми натуральными числами, и φ(1) = 1.Понятие кольца, подкольца, фактор-кольца, евклидова кольца, идеала в кольце.Примеры.КольцоКольцо — это множество R, на котором заданы две бинарные операции: + и × (называемые сложение и умножение), со следующимисвойствами, выполняющимися для любых a, b, c ∈ R:СвойстваПо сложению абелева группаПо умножению дистрибутивность (левая и правая)1.2.a + b = b + a — коммутативность сложения;a + (b + c) = (a + b) + c— ассоциативность сложения;∃0 ∈ R (a + 0 = 0 + a = a) — существование нейтрального элемента относительно сложения;∀a ∈ R ∃b ∈ R(a + b = b + a = 0)— существование противоположного элемента относительно сложения;(a × b) × c = a × (b × c)— ассоциативность умноженияa × (b + c) = a × b + a × c6.
{— дистрибутивность.(b + c) × a = b × a + c × a3.4.5.Дополнительные требованияОтсутствие делителей нуля (целостное кольцо)Наличие единицы по умножениюКоммутативность по умножениюОбратный элемент по умножениюЕсли все свойства выполнены, то получим поле.ПодкольцоПодмножество A ⊂ R называется подкольцом R, если A само является кольцом относительно операций, определенных в R. Поопределению, оно непусто, поскольку содержит нулевой элемент.
Эквивалентно, непустое подмножество A ⊂ R являетсяподкольцом, если для любых x и y из A, x + y, xy и −x также принадлежат A.ИдеалДля кольца R идеалом I называется подкольцо, замкнутое относительно умножения на элементы из R. При этом идеал называетсялевым (соответственно правым), если он замкнут относительно умножения слева (соответственно справа) на элементы из R. Идеал,являющийся одновременно левым и правым, называется двусторонним.
Двусторонний идеал часто называется просто идеалом. Вкоммутативном случае все эти три понятия совпадают и всегда применяется термин идеал.СвойстваПо сложению подгруппа группы кольца∀i ∈ I, r ∈ R → r ∗ i ∈ IФакторкольцоПусть I — двусторонний идеал кольца R. Определим на R отношение эквивалентности:a ∼ b тогда и только тогда, когда a − b ∈ I.Класс эквивалентности элемента a обозначается как [a] или a + I и называется классом смежности по модулю идеала.Факторкольцо R/I — это множество классов смежности элементов R по модулю I , на котором следующим образом определеныоперации сложения и умножения:Примеры:Пусть Z — кольцо целых чисел, nZ — идеал, состоящий из чисел, кратных n .
Тогда Z/nZ — кольцо вычетов по модулю n .Рассмотрим кольцо многочленов с действительными коэффициентами R[x] и идеал, состоящий из многочленов, кратныхx2 + 1. Факторкольцо R[x]/(x2 + 1) изоморфно полю комплексных чисел: класс [x] соответствует мнимой единице.Действительно, в факторкольце элементы x2 + 1 и 0 эквивалентны, то есть x2 = −1.Обобщая предыдущий пример, факторкольца часто используют для построения расширений полей. Пусть K — некоторое полеи f(x) — неприводимый многочлен в K[x] . Тогда K[x]/(f(x)) является полем, и это поле содержит по крайней мере одинкорень многочлена f(x) — класс смежности элемента x.Важный пример использования предыдущей конструкции — построение конечных полей. Рассмотрим конечное поле Z/2Z издвух элементов и в этом контексте обычно обозначается как F2 .
Многочлен x2 + x + 1 неприводим над этим полем (так как неимеет корней), следовательно, факторкольцо F2 [x]/(x2 + x + 1) является полем. Это поле состоит из четырёх элементов: 0,1, x и x+1. Все конечные поля можно построить аналогичным образом.Евклидово кольцоЕвклидово кольцо — это область целостности(ассоциативное коммутативное кольцо без делителей нуля) R, для которой определенаевклидова функция (евклидова норма) d: R → N 0 ∪ {−∞}, причём d(a) = −∞ ⇔ a = 0, и возможно деление с остатком, понорме меньшим делителя, то есть для любых a, b ∈ R, b ≠ 0 имеется представление a = bq + r, для которого d(r) < d(b)илиr = 0.
В Евклидовом кольце работает алгоритм Евклида.Примеры:Кольцо целых чисел Z . Пример евклидовой функции — | ⋅ |.Произвольное поле K является евклидовым кольцом с нормой, равной 1 для всех элементов, кроме 0.Кольцо многочленов одной переменной K[x] над полем K . Пример евклидовой функции — степень Deg.Расширенный алгоритм Евклида и его применение.Алгоритмr0 = ax0 = 1y0 = 0r1 = bx1 = 0y1 = 1…ri+1 = ri−1 − qi rixi+1 = xi−1 − qi xiyi+1 = yi−1 − qi yi…Алгоритм завершается, когда ri+1= 0.Pythondef egcd(a, b):if a == 0:return (b, 0, 1)else:g, y, x = egcd(b % a, a)return (g, x - (b // a) * y, y)ПрименениеРешение уравнений a ∗ x + b ∗ y = GCD(a, b)Обратный элемент в полях Галуа Fp [x]/(a(x)).
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.