Алгебра КНАД 2022/2023 — различия между версиями
(→Ведомости текущего контроля) |
|||
(не показано 13 промежуточных версии 2 участников) | |||
Строка 60: | Строка 60: | ||
'''Лекция 7''' (17.10.2022). Характеристика поля. Расширение полей, расширение корнем. Конечные поля: количество элементов в конечном поле, цикличность мультипликативной группы конечного поля, классификация конечных полей (без доказательства). Конструкция построения конечных полей. Случайные генераторы Галуа и Фибоначчи. Потоковое шифрование. | '''Лекция 7''' (17.10.2022). Характеристика поля. Расширение полей, расширение корнем. Конечные поля: количество элементов в конечном поле, цикличность мультипликативной группы конечного поля, классификация конечных полей (без доказательства). Конструкция построения конечных полей. Случайные генераторы Галуа и Фибоначчи. Потоковое шифрование. | ||
+ | |||
+ | '''Лекция 8''' (31.10.2022). Коды с исправлением ошибок. Расстояние Хэмминга, минимальное расстояние кода, количество исправляемых ошибок. Линейные коды, вес элемента, проверочная матрица, количество исправляемых ошибок в терминах проверочной матрицы. Коды Хэмминга. Неравенство Синглтона. Коды Рида-Соломона. | ||
+ | |||
+ | '''Лекция 9''' (07.11.2022). Многочлены от нескольких переменных. Лексикографический порядок, стабилизация убывающих цепочек мономов. Элементарная редукция, редукция относительно множества многочленов, остатки, базис Грёбнера. Остановка процесса редукции. | ||
+ | |||
+ | '''Лекция 10''' (14.11.2022). S-многочлен и критерий Бухбергера. Идеалы в кольце многочленов от нескольких переменных, алгоритм Бухбергера для построения базиса Грёбнера идеала. Проблема принадлежности идеалу и исключения переменных. Техническая лемма. | ||
+ | |||
+ | '''Лекция 11''' (21.11.2022). Diamond Lemma. Доказательство критерия Бухбергера. Лемма Диксона и остановка алгоритма Бухбергера. | ||
+ | |||
+ | '''Лекция 12''' (28.11.2022). Отношения эквивалентности и фактормножества. Конгруэнция на группе. Построение структуры группы на классах эквивалентности. Описание конгруэнтностей в терминах нормальных подгрупп. | ||
+ | |||
+ | '''Лекция 13''' (05.12.2022). Две теоремы о гомоморфизме. Базис в абелевых группах, свободные абелевы группы с конечным базисом и их описание. Связь с конечными абелевыми группами. | ||
+ | |||
+ | '''Лекция 14''' (12.12.2022). Факторкольца. Отношение конгруэнтности на кольцах и его описание в терминах идеалов. Структура кольца на факторе. Теоремы о гомоморфизме. Связь с кольцами остатков. Свободные кольца. Алгебры над полями. Многочлены как свободные алгебры. Конечно порожденные алгебры и их связь с базисами Грёбнера. | ||
= Домашнее задание = | = Домашнее задание = | ||
Строка 81: | Строка 95: | ||
[https://disk.yandex.ru/i/3I4DK-8WTWQlJw Семинар и ДЗ 9]. Дедлайн - 19.11.2022, 14.00. | [https://disk.yandex.ru/i/3I4DK-8WTWQlJw Семинар и ДЗ 9]. Дедлайн - 19.11.2022, 14.00. | ||
+ | |||
+ | [https://disk.yandex.ru/i/1STmJvMqywgZMg Семинар и ДЗ 10]. Дедлайн - 24.11.2022, 14.40. | ||
+ | |||
+ | [https://disk.yandex.ru/d/unVErAe1QkCMDw Семинар и ДЗ 11]. Дедлайн - 1.12.2022, 11.10. | ||
+ | |||
+ | [https://disk.yandex.ru/i/2Nl4ISU2AcWkkg Семинар и ДЗ 12] | ||
+ | |||
+ | [https://disk.yandex.ru/i/HusNr78xWVJsWw Семинар и ДЗ 13] | ||
+ | |||
+ | = Контрольная работа = | ||
+ | |||
+ | Контрольная работа пройдет в понедельник 12-го декабря с 15:10 до 18:10. Сбор в 15:00. Все ссылки, номера вариантов и прочую информацию можно найти в файле с [https://disk.yandex.ru/i/g5dNjjC8OZxp7g правилами]. | ||
+ | |||
+ | = Экзамен = | ||
+ | |||
+ | * [https://disk.yandex.ru/i/zaUAe2Muyxe_2w Список] определений и формулировок. | ||
+ | |||
+ | * [https://disk.yandex.ru/i/WpN8LRweLAizsg Список] вопросов на доказательства. | ||
+ | |||
+ | * [https://disk.yandex.ru/i/pll8OlNJZUn5yA Правила] проведения экзамена со всеми ссылками и информацией. | ||
= Ведомости текущего контроля = | = Ведомости текущего контроля = | ||
Строка 89: | Строка 123: | ||
|- | |- | ||
! [https://docs.google.com/spreadsheets/d/1UIRPXKImpm70VKWbKftNvy9Z9OoOuU7laIKc9cZiowg/edit?usp=sharing 211/212] | ! [https://docs.google.com/spreadsheets/d/1UIRPXKImpm70VKWbKftNvy9Z9OoOuU7laIKc9cZiowg/edit?usp=sharing 211/212] | ||
+ | |} | ||
+ | |||
+ | * Результаты Контрольной работы | ||
+ | |||
+ | {| class="wikitable" style="text-align:center" | ||
+ | |- | ||
+ | ! [https://docs.google.com/spreadsheets/d/1CsDYeMZWIZmB_zxvCt43VjebtoRKVYB53y8kEjCxx5U/edit?usp=sharing 211/212] | ||
+ | |} | ||
+ | |||
+ | * Итоговая ведомость | ||
+ | |||
+ | {| class="wikitable" style="text-align:center" | ||
+ | |- | ||
+ | ! [https://docs.google.com/spreadsheets/d/1UIRPXKImpm70VKWbKftNvy9Z9OoOuU7laIKc9cZiowg/edit#gid=2130102052 211/212] | ||
|} | |} | ||
Текущая версия на 12:55, 10 января 2023
Содержание
Преподаватели и учебные ассистенты
Группа | БКНАД211/212 |
---|---|
Лектор | Дима Трушин |
Семинарист | Галина Калеева |
Ассистент | Марина Груздева |
Контакты
Преподаватель/Ассистент | Как связаться | Когда | |
---|---|---|---|
|
Дима Трушин | telegram | Напишите мне и мы договоримся о времени проведения консультации |
|
Галина Калеева | см. конспект 1 семинара | Напишите мне и мы договоримся о времени проведения консультации |
|
Марина Груздева |
Формы контроля знаний студентов
- Еженедельные домашние задания
- Письменная контрольная работа по задачам
- Устный экзамен по теории
Порядок формирования итоговой оценки
Итоговая оценка считается по формуле
F = 0,3 * H + 0,3 T + 0,4 E
где H -- оценка за еженедельные домашние задания, T -- оценка за письменную контрольную, E -- оценка за устный экзамен.
Только финальная оценка F округляется. Правила округления арифметические.
Краткое содержание лекций
Лекция 1 (05.09.2022). Бинарные операции. Ассоциативность, нейтральный элемент, обратный элемент, коммутативность. Определение группы. Аддитивная и мультипликативная нотации. Подгруппы и циклические подгруппы. Порядок элемента. Классификация циклических групп.
Лекция 2 (12.09.2022). Описание подгрупп в группе Z. Описание подгрупп в группе Z_n. Левые и правые смежные классы. Нормальные подгруппы. Теорема Лагранжа и ее следствия.
Лекция 3 (19.09.2022). Гомоморфизмы и изоморфизмы групп. Ядро и обрз гомоморфизма их свойства. Произведение групп. Конечные абелевы группы. Китайская теорема об остатках. Структура конечных абелевых групп.
Лекция 4 (26.09.2022). Вторая версия Китайской теоремы об остатках. Структура Z_{p^n}^*. Криптография. Быстрое возведение в квадрат. Проблема дискретного логарифмирования. Система Диффи-Хелмана. RSA.
Лекция 5 (03.10.2022). Кольца, коммутативные кольца, поля, подкольца. Обратимые элементы, делители нуля, нильпотенты, идемпотенты. Идеалы. Описание идеалов в Z и Z_n. Гомоморфизмы и изоморфизмы колец. Китайская теорема об остатках для колец. Ядро и образ гомоморфизма колец и их свойства.
Лекция 6 (10.10.2022). Многочлены от одной переменной. Алгоритм Евклида деления с остатком, наибольший общий делитель, идеалы в F[x]. Неприводимые многочлены и однозначное разложение на множители в F[x]. Кольца полиномиальных остатков, Китайская теорема об остатках для колец полиномиальных остатков.
Лекция 7 (17.10.2022). Характеристика поля. Расширение полей, расширение корнем. Конечные поля: количество элементов в конечном поле, цикличность мультипликативной группы конечного поля, классификация конечных полей (без доказательства). Конструкция построения конечных полей. Случайные генераторы Галуа и Фибоначчи. Потоковое шифрование.
Лекция 8 (31.10.2022). Коды с исправлением ошибок. Расстояние Хэмминга, минимальное расстояние кода, количество исправляемых ошибок. Линейные коды, вес элемента, проверочная матрица, количество исправляемых ошибок в терминах проверочной матрицы. Коды Хэмминга. Неравенство Синглтона. Коды Рида-Соломона.
Лекция 9 (07.11.2022). Многочлены от нескольких переменных. Лексикографический порядок, стабилизация убывающих цепочек мономов. Элементарная редукция, редукция относительно множества многочленов, остатки, базис Грёбнера. Остановка процесса редукции.
Лекция 10 (14.11.2022). S-многочлен и критерий Бухбергера. Идеалы в кольце многочленов от нескольких переменных, алгоритм Бухбергера для построения базиса Грёбнера идеала. Проблема принадлежности идеалу и исключения переменных. Техническая лемма.
Лекция 11 (21.11.2022). Diamond Lemma. Доказательство критерия Бухбергера. Лемма Диксона и остановка алгоритма Бухбергера.
Лекция 12 (28.11.2022). Отношения эквивалентности и фактормножества. Конгруэнция на группе. Построение структуры группы на классах эквивалентности. Описание конгруэнтностей в терминах нормальных подгрупп.
Лекция 13 (05.12.2022). Две теоремы о гомоморфизме. Базис в абелевых группах, свободные абелевы группы с конечным базисом и их описание. Связь с конечными абелевыми группами.
Лекция 14 (12.12.2022). Факторкольца. Отношение конгруэнтности на кольцах и его описание в терминах идеалов. Структура кольца на факторе. Теоремы о гомоморфизме. Связь с кольцами остатков. Свободные кольца. Алгебры над полями. Многочлены как свободные алгебры. Конечно порожденные алгебры и их связь с базисами Грёбнера.
Домашнее задание
Каждый листок содержит задачи с семинара и соответствующее ДЗ. Дедлайн сдачи домашнего задания - начало следующего семинара. Дедлайн мягкий. При опоздании на t часов, оценка умножается на 0.7 t / 24.
Семинар и ДЗ 7. Дедлайн - 3.11.2022, 11.10.
Семинар и ДЗ 9. Дедлайн - 19.11.2022, 14.00.
Семинар и ДЗ 10. Дедлайн - 24.11.2022, 14.40.
Семинар и ДЗ 11. Дедлайн - 1.12.2022, 11.10.
Контрольная работа
Контрольная работа пройдет в понедельник 12-го декабря с 15:10 до 18:10. Сбор в 15:00. Все ссылки, номера вариантов и прочую информацию можно найти в файле с правилами.
Экзамен
- Список определений и формулировок.
- Список вопросов на доказательства.
- Правила проведения экзамена со всеми ссылками и информацией.
Ведомости текущего контроля
- Домашние задания
211/212 |
---|
- Результаты Контрольной работы
211/212 |
---|
- Итоговая ведомость
211/212 |
---|
Ссылки
- Записи лекций
- Виртуальные доски с лекций.
- Конспекты семинаров.
Литература
Основная
- Курс алгебры, Винберг, Э. Б.
- Заметки по теории кодирования, Ромащенко, А. Е.
- Введение в алгебру: основы алгебры: учебник для вузов, Кострикин, А. И.
- Идеалы, многообразия и алгоритмы. Кокс, Литтл, О'Ши.
Дополнительная
- Практическая криптография, Фергюсон, Нильс
- Базисы Гребнера и системы алгебраических уравнений, Аржанцев, И. В.
- Сборник задач по алгебре, учебник, под ред. А. И. Кострикина, 3-е изд., испр. и доп.