Алгебра на ПМИ 2018/2019 (основной поток) — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Контрольная работа)
(Краткое содержание лекций)
 
(не показана одна промежуточная версия этого же участника)
Строка 74: Строка 74:
  
 
'''Лекция 9''' (3.06.2019). Конечные поля. Порядок конечного поля. Автоморфизм Фробениуса. Существование и единственность конечного поля, порядок которого — степень простого числа. Поле из четырёх элементов. Цикличность мультипликативной группы конечного поля. Неприводимые многочлены над полем вычетов. Описание подполей конечного поля.
 
'''Лекция 9''' (3.06.2019). Конечные поля. Порядок конечного поля. Автоморфизм Фробениуса. Существование и единственность конечного поля, порядок которого — степень простого числа. Поле из четырёх элементов. Цикличность мультипликативной группы конечного поля. Неприводимые многочлены над полем вычетов. Описание подполей конечного поля.
 +
 +
'''Лекция 10''' (10.06.2019). Коды над конечным алфавитом. Расстояние Хэмминга. Коды, исправляющие t ошибок. Минимальное расстояние кода. Теорема о связи минимального расстояния кода с числом ошибок, которые он может исправлять. Линейные коды. Проверочная матрица. Связь минимального расстояния линейного кода с его проверочной матрицей. Бинарный код Хэмминга, его минимальное расстояние и число ошибок, которые он может исправлять. Коды БЧХ. Теорема о числе ошибок, исправляемых кодом БЧХ. Оценка на размерность кода БЧХ.
  
 
= Листки с задачами =
 
= Листки с задачами =
Строка 96: Строка 98:
  
 
[https://www.dropbox.com/s/vbmutttwknuobjq/A_18-19_Stream2_Problems09.pdf?dl=0 '''Задачи к лекции 9''']
 
[https://www.dropbox.com/s/vbmutttwknuobjq/A_18-19_Stream2_Problems09.pdf?dl=0 '''Задачи к лекции 9''']
 +
 +
[https://www.dropbox.com/s/w7qjvspd49mmz96/A_18-19_Stream2_Problems10.pdf?dl=0 '''Задачи к лекции 10''']
  
 
= Контрольная работа =
 
= Контрольная работа =

Текущая версия на 11:46, 13 июня 2019

Преподаватели и учебные ассистенты

Группа БПМИ183 БПМИ185 БПМИ186 БПМИ187 БПМИ188 БПМИ189
Лектор Роман Сергеевич Авдеев
Семинарист Дмитрий Витальевич Трушин Роман Сергеевич Авдеев Сергей Александрович Гайфуллин Станислав Николаевич Федотов Антон Андреевич Шафаревич Роман Сергеевич Авдеев
Ассистент Никита Башаев Наталья Доброхотова-Майкова Марат Саидов Лев Ходжоян Аделина Бакиева Андрей Гусев

Расписание консультаций

Преподаватель/ассистент понедельник вторник среда четверг пятница
1
Роман Сергеевич Авдеев 15:40–17:40, ауд. 623 15:40–16:30, 18:10–19:00, ауд. 623
2
Дмитрий Витальевич Трушин 16:40–18:00, ауд. 503
3
Сергей Александрович Гайфуллин 18:10–19:30, ауд. 623
4
Станислав Николаевич Федотов
5
Антон Андреевич Шафаревич 12:10–19:30, ауд. 623
6
Никита Башаев 12:10–13:30
7
Наталья Доброхотова-Майкова 18:10–19:30, ауд. 300
8
Марат Саидов 16:40–18:00
9
Лев Ходжоян 13:40–18:00
10
Аделина Бакиева 13:40–15:00, ауд. 618
11
Андрей Гусев 18:10–19:30, ауд. 304

Порядок формирования оценок

Накопленная оценка вычисляется по следующей формуле:

Oнакопленная = 0,6 * Oдз + 0,4 * Oк/р,

где Oдз1 — оценка за домашние задания, Oк/р — оценка за контрольную работу.

Итоговая оценка выражается через накопленную и оценку за экзамен следующим образом:

Oитоговая = 0,5 * Oнакопленная + 0,5 * Оэкз.

Округление производится только для итоговой оценки. Способ округления — арифметический.

Краткое содержание лекций

Лекция 1 (1.04.2019). Бинарные операции. Полугруппы, моноиды, группы, коммутативные (абелевы) группы. Порядок группы. Примеры групп. Подгруппы. Описание всех подгрупп в группе целых чисел по сложению. Циклические подгруппы. Порядок элемента группы. Связь между порядком элемента и порядком порождаемой им циклической подгруппы. Циклические группы. Левые смежные классы группы по подгруппе, разбиение группы на левые смежные классы. Индекс подгруппы, теорема Лагранжа.

Лекция 2 (8.04.2019). Пять следствий из теоремы Лагранжа. Нормальные подгруппы. Факторгруппа группы по нормальной подгруппе. Гомоморфизмы групп, простейшие свойства. Изоморфизм групп, изоморфные группы. Ядро и образ гомоморфизма групп. Теорема о гомоморфизме для групп. Классификация циклических групп с точностью до изоморфизма.

Лекция 3 (15.04.2019). Прямое произведение групп и разложение группы в прямое произведение подгрупп. Разложение конечной циклической группы. Подгруппа p-кручения в абелевой группе. Разложение конечной абелевой группы в прямое произведение подгрупп p-кручения. Примарные абелевы группы. Теорема о разложении конечной абелевой группы в прямое произведение примарных циклических групп, доказательство единственности числа и порядков примарных циклических множителей. Экспонента конечной абелевой группы, критерий цикличности. Криптография с открытым ключом. Задача дискретного логарифмирования.

Лекция 4 (22.04.2019). Система Диффи–Хеллмана обмена ключами. Криптосистема Эль–Гамаля. Понятие кольца, примеры. Коммутативные кольца. Обратимые элементы, делители нуля, нильпотенты. Поля. Критерий того, что кольцо вычетов является полем. Подкольца, подполя, гомоморфизмы, изоморфизмы. Идеалы в кольце. Главные идеалы и идеалы, порождённые подмножеством коммутативного кольца. Факторкольцо кольца по идеалу. Ядро и образ гомоморфизма колец. Теорема о гомоморфизме для колец (формулировка).

Лекция 5 (29.04.2019). Доказательство теоремы о гомоморфизме для колец. Делимость в коммутативных кольцах без делителей нуля. Ассоциированные элементы. Наибольший общий делитель двух элементов. Кольца главных идеалов. Существование наибольшего общего делителя для двух элементов a и b кольца главных идеалов и его линейная выразимость через a и b. Простые элементы. Факториальные кольца. Деление с остатком в кольце многочленов от одной переменной над полем. Теорема о том, что кольцо многочленов от одной переменной над полем является кольцом главных идеалов. Факториальность кольца многочленов от одной переменной над полем. Неприводимые многочлены.

Лекция 6 (13.05.2019). Лексикографический порядок на одночленах от нескольких переменных. Лемма о конечности убывающих цепочек одночленов. Старший член ненулевого многочлена. Элементарная редукция многочлена относительно ненулевого многочлена. Нередуцируемые многочлены. Лемма о конечности цепочек элементарных редукций. Остаток многочлена относительно заданной системы многочленов. Системы Грёбнера. Характеризация систем Грёбнера в терминах цепочек элементарных редукций. S-многочлены. Критерий Бухбергера (формулировка).

Лекция 7 (20.05.2019). Доказательство критерия Бухбергера. Теорема Гильберта о базисе идеала (без доказательства). Базис Грёбнера идеала, теорема о трёх эквивалентных условиях. Решение задачи вхождения многочлена в идеал. Лемма о конечности цепочек одночленов, в которых каждый следующий одночлен не делится ни на один из предыдущих. Алгоритм Бухбергера построения базиса Грёбнера идеала. Редуцируемость к нулю S-многочлена двух многочленов с взаимно простыми старшими членами.

Лекция 8 (27.05.2019). Поля. Характеристика поля. Расширение полей, его степень. Степень композиции двух расширений. Критерий того, что факторкольцо K[x]/(h) является полем. Свойства поля K[x]/(h), где h — неприводимый многочлен. Существование конечного расширения исходного поля, в котором заданный многочлен имеет корень. Поле разложения многочлена. Алгебраические и трансцендентные элементы. Минимальный многочлен алгебраического элемента и его свойства. Поле, порождённое алгебраическим элементом.

Лекция 9 (3.06.2019). Конечные поля. Порядок конечного поля. Автоморфизм Фробениуса. Существование и единственность конечного поля, порядок которого — степень простого числа. Поле из четырёх элементов. Цикличность мультипликативной группы конечного поля. Неприводимые многочлены над полем вычетов. Описание подполей конечного поля.

Лекция 10 (10.06.2019). Коды над конечным алфавитом. Расстояние Хэмминга. Коды, исправляющие t ошибок. Минимальное расстояние кода. Теорема о связи минимального расстояния кода с числом ошибок, которые он может исправлять. Линейные коды. Проверочная матрица. Связь минимального расстояния линейного кода с его проверочной матрицей. Бинарный код Хэмминга, его минимальное расстояние и число ошибок, которые он может исправлять. Коды БЧХ. Теорема о числе ошибок, исправляемых кодом БЧХ. Оценка на размерность кода БЧХ.

Листки с задачами

Листок с задачами к лекции N содержит в себе N-е домашнее задание.

Задачи к лекции 1

Задачи к лекции 2

Задачи к лекции 3

Задачи к лекции 4

Задачи к лекции 5

Задачи к лекции 6

Задачи к лекции 7

Задачи к лекции 8

Задачи к лекции 9

Задачи к лекции 10

Контрольная работа

Дата-время-место: 11 июня, 15:10, аудитории 622 (группы 185, 186, 188, 189) и 509 (группы 183, 187)

На контрольной можно пользоваться любыми материалами на бумажных носителях. Использование электронных устройств (кроме тех, у которых единственная функция — калькулятор) запрещено.

Типы задач на контрольной работе

  • Порядки элементов и подгруппы в конечных абелевых группах [60.39, 60.40, 60.42, 60.43, 60.45]
  • Алгоритм Евклида и линейное представление НОД в кольце многочленов [25.2, 25.3, 25.7]
  • Разложение многочленов на неприводимые множители над полями R, C и Z_p [27.1, 27.2, ещё примеры]
  • Базисы Грёбнера и задача вхождения [примеры]
  • Минимальные многочлены и вычисления в конечных расширениях полей [67.3, 67.13]
  • Системы линейных уравнений с коэффициентами в конечном поле [примеры]

Для каждого типа в скобках указаны задачи, рекомендуемые к прорешиванию в качестве тренировки (номера даны по Сборнику задач по алгебре под редакцией А.И. Кострикина).

Экзамен

Формат экзамена: устный, по билетам (в каждом по два вопроса из программы)

Ведомости текущего контроля

183 185 186 187 188 189

Литература

  • Э.Б. Винберг. Курс алгебры. М.: Факториал Пресс, 2002.
  • А.И. Кострикин. Введение в алгебру. Основы алгебры. М.: Наука. Физматлит, 1994.
  • А.И. Кострикин. Введение в алгебру. Основные структуры алгебры. М.: Наука. Физматлит, 2000.
  • Сборник задач по алгебре под редакцией А.Н. Кострикина. Новое издание. М.: МЦНМО, 2009.
  • Р. Лидл, Г. Нидеррайтер. Конечные поля (2 тома). М.: Мир, 1988.
  • И.В. Аржанцев. Базисы Грёбнера и системы алгебраических уравнений. М.: МЦНМО, 2003.