Лекции по прикладной алгебре. v2.0 (1127112)
Текст из файла
Прикладная алгебра1 / 432Прикладная алгебраЛекции для III потока,5-й семестрЛектор — Гуров Сергей Исаевичассистент — Кропотов Дмитрий АлександровичФакультет Вычислительной математики и кибернетики,МГУ имени М.В. ЛомоносоваКафедра Математических методов прогнозированиякомн. 530, 682e-mail: sgur@cs.msu.ruПрикладная алгебраЛитератураВоронин В.П. Дополнительные главы дискретнойматематики. — М.: ф-т ВМК МГУ, 2002.http://padabum.com/d.php?id=10281Гуров С.И.
Булевы алгебры, упорядоченные множества,решетки: Определения, свойства, примеры. — М.: Либроком,2013.Журавлёв Ю.И., Флёров Ю.А., Вялый М.Н. Дискретныйанализ. Основы высшей алгебры. — М.: МЗ Пресс, 2007.Лидл Р., Нидеррайтер Г. Конечные поля: В 2-х т. — М.: Мир,1988.Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов,исправляющих ошибки. — М.: Связь, 1979.Нефедов В.Н., Осипова В.А.
Курс дискретной математики. —М.: Изд-во МАИ, 1992.Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.:Мир, 1976.2 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаГрупповые (линейные) коды3 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств4 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаРаздел IIIОсновные понятия теории ч.у.
множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать5 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа6 / 432Поле GF (p)Z — евклидово кольцо целых чисел (без делителей нуля +деление с остатком); p — простое число.(p) = {np | n ∈ Z} = pZ = {0, ±p, ±2p, . . .} — идеалZ/(p) — кольцовычетовпо модулю этого идеала —Z/(p) = 0, 1, . . . , p − 1 — классы остатков от деления на p:01...p−1= 0 + pZ ,= 1 + pZ ,= (p − 1) + pZ .⇒Z= 0 ∪ 1 ∪ . . .
∪ p − 1.Часто черту над символами классов вычетов не пишут.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа6 / 432Поле GF (p)Z — евклидово кольцо целых чисел (без делителей нуля +деление с остатком); p — простое число.(p) = {np | n ∈ Z} = pZ = {0, ±p, ±2p, . . .} — идеалZ/(p) — кольцовычетовпо модулю этого идеала —Z/(p) = 0, 1, . . .
, p − 1 — классы остатков от деления на p:01...p−1= 0 + pZ ,= 1 + pZ ,= (p − 1) + pZ .⇒Z= 0 ∪ 1 ∪ . . . ∪ p − 1.Часто черту над символами классов вычетов не пишут.Поскольку p — простое, то Z/(p) — не просто кольцо, а поле(возможно деление без остатка на любой ненулевой элемент).Это простейшее поле Галуа, обозначение — Fp или GF (p) (всеоперации в нём — по mod p).Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПолеF3 :7 / 432F3 = Z/(3) и факторкольцо Z/(4)+012001211202201×012000010122021Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПоле7 / 432F3 = Z/(3) и факторкольцо Z/(4)F3 :+012001211202201Z/(4) :+012300123112302230133012×012000010122021×012300000101232020230321Дважды два равно нулю!Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаХарактеристика поляПусть k — произвольное поле, 1 — единица k.
Складываем их:1 = 1 , 2 = 1 + 1 , . . ..8 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа8 / 432Характеристика поляПусть k — произвольное поле, 1 — единица k. Складываем их:1 = 1 , 2 = 1 + 1 , . . .. В конечном поле всегда найдётсяпервое k такое, что 1| + .{z. .
+ 1} = 0. Тогдаk разk = порядок аддитивной группы поля k == характеристика поля k = char kdefПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа8 / 432Характеристика поляПусть k — произвольное поле, 1 — единица k. Складываем их:1 = 1 , 2 = 1 + 1 , . . .. В конечном поле всегда найдётсяпервое k такое, что 1| + .{z. .
+ 1} = 0. Тогдаk разk = порядок аддитивной группы поля k == характеристика поля k = char kdef{ 1, 2, . . . , char k − 1, 0 } — минимальное подполе в поле k.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа8 / 432Характеристика поляПусть k — произвольное поле, 1 — единица k. Складываем их:1 = 1 , 2 = 1 + 1 , . . .. В конечном поле всегда найдётсяпервое k такое, что 1| + .{z. .
+ 1} = 0. Тогдаk разk = порядок аддитивной группы поля k == характеристика поля k = char kdef{ 1, 2, . . . , char k − 1, 0 } — минимальное подполе в поле k.Если все суммы вида 1 + . . . + 1 различны, то char k = 0.Примеры: Q, R — поля нулевой (или бесконечной :))характеристики.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаБесконечное поле с положительной характеристикой9 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаБесконечное поле с положительной характеристикойk — произвольное (конечное или бесконечное) поле.
Построим:1k[x] — кольцо многочленов P (x) = a0 + a1 x + . . . + an xn ,a0 , . . . , an ∈ k от формальной переменной x.9 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаБесконечное поле с положительной характеристикойk — произвольное (конечное или бесконечное) поле. Построим:12k[x] — кольцо многочленов P (x) = a0 + a1 x + . . . + an xn ,a0 , . . . , an ∈ k от формальной переменной x.k(x) — поле рациональных функций над k9 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаБесконечное поле с положительной характеристикойk — произвольное (конечное или бесконечное) поле. Построим:12k[x] — кольцо многочленов P (x) = a0 + a1 x + .
. . + an xn ,a0 , . . . , an ∈ k от формальной переменной x.k(x) — поле рациональных функций над k; в нём:элементы — “дроби” P/Q (если Q 6= 0), где P, Q ∈ k[x];умножение — (P/Q) · (U/V ) = (P U )/(QV );эквивалентность — P1 /Q1 = P2 /Q2 , если P1 Q2 = P2 Q1 ;сложение — дроби можно приводить к общемузнаменателю и складывать:P/Q+U/V = (P V )/(QV )+(QU )/(QV ) = (P V +QU )/(QV );включение — Поскольку k[x] ⊂ k(x), то каждыймногочлен P отождествляется с P/1.9 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаБесконечное поле с положительной характеристикойk — произвольное (конечное или бесконечное) поле.
Построим:12k[x] — кольцо многочленов P (x) = a0 + a1 x + . . . + an xn ,a0 , . . . , an ∈ k от формальной переменной x.k(x) — поле рациональных функций над k; в нём:элементы — “дроби” P/Q (если Q 6= 0), где P, Q ∈ k[x];умножение — (P/Q) · (U/V ) = (P U )/(QV );эквивалентность — P1 /Q1 = P2 /Q2 , если P1 Q2 = P2 Q1 ;сложение — дроби можно приводить к общемузнаменателю и складывать:P/Q+U/V = (P V )/(QV )+(QU )/(QV ) = (P V +QU )/(QV );включение — Поскольку k[x] ⊂ k(x), то каждыймногочлен P отождествляется с P/1.Если в качестве k взять конечное поле Fp , то Fp (x) —бесконечное поле положительной характеристики p.9 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаСильное упрощение вычислений в поле положительнойхарактеристикиЛеммаВ поле характеристики p > 0 выполнено тождество(a + b)p = ap + bp .10 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа10 / 432Сильное упрощение вычислений в поле положительнойхарактеристикиЛеммаВ поле характеристики p > 0 выполнено тождество(a + b)p = ap + bp .ДоказательствоВ любом коммутативном кольце верна формула для бинома(a + b)p = ap + Cp1 ap−1 b + .
. . + Cpp−1 abp−1 + bp .Но при i = 1, . . . , p − 1 числитель коэффициента Cpi =делится на p, а знаменатель — нет, ∴ Cpi ≡p 0.p!i!(p−i)!Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа10 / 432Сильное упрощение вычислений в поле положительнойхарактеристикиЛеммаВ поле характеристики p > 0 выполнено тождество(a + b)p = ap + bp .ДоказательствоВ любом коммутативном кольце верна формула для бинома(a + b)p = ap + Cp1 ap−1 b + . .
. + Cpp−1 abp−1 + bp .Но при i = 1, . . . , p − 1 числитель коэффициента Cpi =делится на p, а знаменатель — нет, ∴ Cpi ≡p 0.p!i!(p−i)!СледствиеnnnВ поле характеристики p > 0 справедливо (a + b)p = ap + bp .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаМультипликативная группа и примитивный элемент поляF∗pdef=Fp r {0} — мультипликативная группа поля Fp .11 / 432FpПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаМультипликативная группа и примитивный элемент поляF∗pdef=Fp r {0} — мультипликативная группа поля Fp .УтверждениеF∗p — циклическая группа порядка p − 1 по умножению.11 / 432FpПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа11 / 432Мультипликативная группа и примитивный элемент поляF∗pdef=Fp r {0} — мультипликативная группа поля Fp .УтверждениеF∗p — циклическая группа порядка p − 1 по умножению.Как любая конечная циклическая группа,генератор = примитивный элемент α:F∗p содержитлюбой элемент β ∈ F∗p является некоторой его натуральнойстепенью — т.е.
β = αi , i ∈ { 1, . . . , p − 1};причём 1 = αp−1 — т.е. αi 6= 1 для 1 6 i 6 p − 2.FpПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа11 / 432Мультипликативная группа и примитивный элемент поляF∗pdef=Fp r {0} — мультипликативная группа поля Fp .УтверждениеF∗p — циклическая группа порядка p − 1 по умножению.Как любая конечная циклическая группа,генератор = примитивный элемент α:F∗p содержитлюбой элемент β ∈ F∗p является некоторой его натуральнойстепенью — т.е.
β = αi , i ∈ { 1, . . . , p − 1};причём 1 = αp−1 — т.е. αi 6= 1 для 1 6 i 6 p − 2.УтверждениеГруппаF∗p имеет ϕ(p − 1) примитивных элементов.FpПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаФункция Эйлераϕ(n) — функция Эйлера — количество чисел из интервала[ 1, . . . , n − 1 ], взаимно простых с n:ϕ(1) = 1 (по определению), ϕ(2) = 1, ϕ(3) = ϕ(4) = 2,ϕ(5) = 4, ϕ(6) = {1, 5} = 2, . . .12 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаФункция Эйлераϕ(n) — функция Эйлера — количество чисел из интервала[ 1, . .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
