Алгебра КНАД 2024/2025 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(→‎Краткое содержание лекций)
(→‎Ссылки)
 
(не показано 9 промежуточных версии 2 участников)
Строка 57: Строка 57:
 
'''Лекция 4''' (30.09.2024). Мультипликативная версия Китайской теоремы об остатках. Структура Z_{p^n}^*. Криптография. Быстрое возведение в степень. Проблема дискретного логарифмирования. Система Диффи-Хелмана и Эль-Гамаля. Опционально RSA (в конспекте).
 
'''Лекция 4''' (30.09.2024). Мультипликативная версия Китайской теоремы об остатках. Структура Z_{p^n}^*. Криптография. Быстрое возведение в степень. Проблема дискретного логарифмирования. Система Диффи-Хелмана и Эль-Гамаля. Опционально RSA (в конспекте).
  
−
'''Лекция 5''' (07.10.2023). Кольца, коммутативные кольца, поля, подкольца. Обратимые элементы, делители нуля, нильпотенты, идемпотенты. Идеалы. Описание идеалов в Z и Z_n. Гомоморфизмы и изоморфизмы колец. Китайская теорема об остатках для колец. Ядро и образ гомоморфизма колец и их свойства.
+
'''Лекция 5''' (07.10.2024). Кольца, коммутативные кольца, поля, подкольца. Обратимые элементы, делители нуля, нильпотенты, идемпотенты. Идеалы. Описание идеалов в Z и Z_n. Гомоморфизмы и изоморфизмы колец. Китайская теорема об остатках для колец. Ядро и образ гомоморфизма колец и их свойства.
  
−
'''Лекция 6''' (14.10.2023). Многочлены от одной переменной. Алгоритм Евклида деления с остатком, наибольший общий делитель, идеалы в F[x]. Неприводимые многочлены и однозначное разложение на множители в F[x]. Кольца полиномиальных остатков, Китайская теорема об остатках для колец полиномиальных остатков.
+
'''Лекция 6''' (14.10.2024). Многочлены от одной переменной. Алгоритм Евклида деления с остатком, наибольший общий делитель, идеалы в F[x]. Неприводимые многочлены и однозначное разложение на множители в F[x]. Кольца полиномиальных остатков, Китайская теорема об остатках для колец полиномиальных остатков.
  
−
'''Лекция 7''' (21.10.2022). Доказательство Китайской теоремы для колец полиномиальных остатков. Идеалы в кольце полиномиальных остатков. Характеристика поля. Расширение полей, расширение корнем. Конечные поля: количество элементов в конечном поле, цикличность мультипликативной группы конечного поля (формулировка), классификация конечных полей (без доказательства). Конструкция построения конечных полей. Случайные генераторы Галуа. Потоковое шифрование.
+
'''Лекция 7''' (21.10.2024). Доказательство Китайской теоремы для колец полиномиальных остатков. Идеалы в кольце полиномиальных остатков. Характеристика поля. Расширение полей, расширение корнем. Конечные поля: количество элементов в конечном поле, цикличность мультипликативной группы конечного поля (формулировка), классификация конечных полей (без доказательства). Конструкция построения конечных полей. Случайные генераторы Галуа. Потоковое шифрование.
  
−
'''Лекция 8''' (11.11.2022). Коды с исправлением ошибок. Расстояние Хэмминга, минимальное расстояние кода, количество исправляемых ошибок. Линейные коды, вес элемента, проверочная матрица, количество исправляемых ошибок в терминах проверочной матрицы. Коды Хэмминга. Неравенство Синглтона. Коды Рида-Соломона.
+
'''Лекция 8''' (11.11.2024). Коды с исправлением ошибок. Расстояние Хэмминга, минимальное расстояние кода, количество исправляемых ошибок. Линейные коды, вес элемента, проверочная матрица, количество исправляемых ошибок в терминах проверочной матрицы. Коды Хэмминга. Неравенство Синглтона. Коды Рида-Соломона.
  
−
'''Лекция 9''' (18.11.2022). Многочлены от нескольких переменных. Лексикографический порядок, стабилизация убывающих цепочек мономов. Элементарная редукция, редукция относительно множества многочленов, остатки, базис Грёбнера. Остановка процесса редукции.
+
'''Лекция 9''' (18.11.2024). Многочлены от нескольких переменных. Лексикографический порядок, стабилизация убывающих цепочек мономов. Элементарная редукция, редукция относительно множества многочленов, остатки, базис Грёбнера. Остановка процесса редукции.
  
−
'''Лекция 10''' (25.11.2022). S-многочлен и критерий Бухбергера. Идеалы в кольце многочленов от нескольких переменных, алгоритм Бухбергера для построения базиса Грёбнера идеала. Проблема принадлежности идеалу и исключения переменных.
+
'''Лекция 10''' (25.11.2024). S-многочлен и критерий Бухбергера. Идеалы в кольце многочленов от нескольких переменных, алгоритм Бухбергера для построения базиса Грёбнера идеала. Проблема принадлежности идеалу и исключения переменных.
 +
 
 +
'''Лекция 11''' (02.12.2024). Diamond Lemma. Доказательство критерия Бухбергера. Лемма Диксона и остановка алгоритма Бухбергера.
 +
 
 +
'''Лекция 12''' (09.12.2024). Отношения эквивалентности и фактормножества. Конгруэнция на группе. Построение структуры группы на классах эквивалентности. Описание конгруэнтностей в терминах нормальных подгрупп.
  
 
= Домашнее задание =
 
= Домашнее задание =
Строка 89: Строка 93:
  
 
* [https://disk.yandex.ru/i/lPu_eyC_zdQY7Q Домашнее задание 9]
 
* [https://disk.yandex.ru/i/lPu_eyC_zdQY7Q Домашнее задание 9]
 +
 +
* [https://disk.yandex.ru/i/x2LaDCgUwrpdIQ Домашнее задание 10]
 +
 +
* [https://disk.yandex.ru/i/r7YbjtO5p1II2w Домашнее задание 11]
 +
 +
* [https://disk.yandex.ru/i/ijDbY8bP1MUkpw Домашнее Задание 12]
  
 
= Куда сдавать домашнее задание =
 
= Куда сдавать домашнее задание =
Строка 101: Строка 111:
 
Дата экзамена --  
 
Дата экзамена --  
  
−
* [ Список] определений и формулировок.
+
* [https://disk.yandex.ru/i/jj64fd3fEYVZKA Список] определений и формулировок.
  
−
* [ Список] вопросов на доказательства.
+
* [https://disk.yandex.ru/i/QcrGDRgkCDHjsQ Список] вопросов на доказательства.
  
−
* [ Правила] проведения экзамена со всеми ссылками и информацией.
+
* [https://disk.yandex.ru/i/ghlKylWq4X2rVA Правила] проведения экзамена со всеми ссылками и информацией.
  
 
= Ведомости текущего контроля =
 
= Ведомости текущего контроля =
Строка 117: Строка 127:
  
 
* Результаты Контрольной работы
 
* Результаты Контрольной работы
 +
 +
{| class="wikitable" style="text-align:center"
 +
|-
 +
! [https://docs.google.com/spreadsheets/d/1rMUzp6MPWx6OSuky2Ic0IDCgKShavpStgY-xR5uOUGw/edit?usp=sharing 231] !! [https://docs.google.com/spreadsheets/d/1rMUzp6MPWx6OSuky2Ic0IDCgKShavpStgY-xR5uOUGw/edit?usp=sharing 232]
 +
|}
  
 
* Итоговая ведомость
 
* Итоговая ведомость
 +
 +
{| class="wikitable" style="text-align:center"
 +
|-
 +
! [https://docs.google.com/spreadsheets/d/1K9UCjiPU0fzGbeU8kWQZjz3Hozl24lgYtg53Pbh_Qrg/edit?gid=0#gid=0 231] !! [https://docs.google.com/spreadsheets/d/1K9UCjiPU0fzGbeU8kWQZjz3Hozl24lgYtg53Pbh_Qrg/edit?gid=986694007#gid=986694007 232]
 +
|}
  
 
= Ссылки =
 
= Ссылки =
Строка 124: Строка 144:
 
* [https://t.me/+Y6ImXb3vcdFmYTQy Группа] курса в телеграме.
 
* [https://t.me/+Y6ImXb3vcdFmYTQy Группа] курса в телеграме.
  
−
* [https://us06web.zoom.us/j/82020049937?pwd=HY4uhWYYWxxmkO4Ubi0pDXWzBAtyw2.1 Трансляция] лекции по понедельникам с 11:10 до 12:30.
+
* [Трансляция] лекции по понедельникам с 11:10 до 12:30.
  
 
* [https://github.com/DimaTrushin/Algebra-CDS/tree/2024 Конспекты] лекций.
 
* [https://github.com/DimaTrushin/Algebra-CDS/tree/2024 Конспекты] лекций.

Текущая версия на 22:42, 23 декабря 2024

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

Группа БКНАД231 БКНАД232
Лектор Дима Трушин
Семинарист Галина Калеева
Ассистент [] []

Контакты

Преподаватель/Ассистент Как связаться Когда
1
 Дима Трушин telegram Напишите мне и мы договоримся о времени проведения консультации. Для тех кто в Москве, очные консультации по средам с 17:00 до 20:00 в S812.
2
 Галина Калеева Среда, 19:00
3
 Женя Пахомов telegram
4
 Дина Шакирова telegram

Формы контроля знаний студентов

  • Еженедельные домашние задания
  • Письменная контрольная работа по задачам
  • Устный экзамен по теории

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

Итоговая оценка считается по формуле

F = 0,3 * H + 0,3 T + 0,4 E

где H -- оценка за еженедельные домашние задания, T -- оценка за письменную контрольную, E -- оценка за устный экзамен.

Только финальная оценка F округляется. Правила округления арифметические.

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

Лекция 1 (09.09.2024). Бинарные операции. Ассоциативность, нейтральный элемент, обратный элемент, коммутативность. Определение группы. Аддитивная и мультипликативная нотации. Подгруппы и циклические подгруппы. Порядок элемента.

Лекция 2 (16.09.2024). Классификация циклических групп. Описание подгрупп в группе Z. Описание подгрупп в группе Z_n. Левые и правые смежные классы. Нормальные подгруппы. Теорема Лагранжа и ее следствия.

Лекция 3 (23.09.2024). Гомоморфизмы и изоморфизмы групп. Ядро и обрз гомоморфизма их свойства. Произведение групп. Конечные абелевы группы. Китайская теорема об остатках. Структура конечных абелевых групп.

Лекция 4 (30.09.2024). Мультипликативная версия Китайской теоремы об остатках. Структура Z_{p^n}^*. Криптография. Быстрое возведение в степень. Проблема дискретного логарифмирования. Система Диффи-Хелмана и Эль-Гамаля. Опционально RSA (в конспекте).

Лекция 5 (07.10.2024). Кольца, коммутативные кольца, поля, подкольца. Обратимые элементы, делители нуля, нильпотенты, идемпотенты. Идеалы. Описание идеалов в Z и Z_n. Гомоморфизмы и изоморфизмы колец. Китайская теорема об остатках для колец. Ядро и образ гомоморфизма колец и их свойства.

Лекция 6 (14.10.2024). Многочлены от одной переменной. Алгоритм Евклида деления с остатком, наибольший общий делитель, идеалы в F[x]. Неприводимые многочлены и однозначное разложение на множители в F[x]. Кольца полиномиальных остатков, Китайская теорема об остатках для колец полиномиальных остатков.

Лекция 7 (21.10.2024). Доказательство Китайской теоремы для колец полиномиальных остатков. Идеалы в кольце полиномиальных остатков. Характеристика поля. Расширение полей, расширение корнем. Конечные поля: количество элементов в конечном поле, цикличность мультипликативной группы конечного поля (формулировка), классификация конечных полей (без доказательства). Конструкция построения конечных полей. Случайные генераторы Галуа. Потоковое шифрование.

Лекция 8 (11.11.2024). Коды с исправлением ошибок. Расстояние Хэмминга, минимальное расстояние кода, количество исправляемых ошибок. Линейные коды, вес элемента, проверочная матрица, количество исправляемых ошибок в терминах проверочной матрицы. Коды Хэмминга. Неравенство Синглтона. Коды Рида-Соломона.

Лекция 9 (18.11.2024). Многочлены от нескольких переменных. Лексикографический порядок, стабилизация убывающих цепочек мономов. Элементарная редукция, редукция относительно множества многочленов, остатки, базис Грёбнера. Остановка процесса редукции.

Лекция 10 (25.11.2024). S-многочлен и критерий Бухбергера. Идеалы в кольце многочленов от нескольких переменных, алгоритм Бухбергера для построения базиса Грёбнера идеала. Проблема принадлежности идеалу и исключения переменных.

Лекция 11 (02.12.2024). Diamond Lemma. Доказательство критерия Бухбергера. Лемма Диксона и остановка алгоритма Бухбергера.

Лекция 12 (09.12.2024). Отношения эквивалентности и фактормножества. Конгруэнция на группе. Построение структуры группы на классах эквивалентности. Описание конгруэнтностей в терминах нормальных подгрупп.

Домашнее задание

Каждый листок содержит задачи с семинара и соответствующее ДЗ. Дедлайн сдачи домашнего задания – начало следующего семинара. Дедлайн мягкий. При опоздании на t часов, оценка умножается на 0.7 t / 24.

Куда сдавать домашнее задание

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

Экзамен

Дата экзамена --

  • Список определений и формулировок.
  • Список вопросов на доказательства.
  • Правила проведения экзамена со всеми ссылками и информацией.

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

  • Домашние задания
231 232
  • Результаты Контрольной работы
231 232
  • Итоговая ведомость
231 232

Ссылки

  • [Трансляция] лекции по понедельникам с 11:10 до 12:30.
  • [ Конспекты] семинаров.
  • [ Видеозаписи].

Литература

Основная

  • Курс алгебры, Винберг, Э. Б.
  • Заметки по теории кодирования, Ромащенко, А. Е.
  • Введение в алгебру: основы алгебры: учебник для вузов, Кострикин, А. И.
  • Идеалы, многообразия и алгоритмы. Кокс, Литтл, О'Ши.

Дополнительная

  • Практическая криптография, Фергюсон, Нильс
  • Базисы Гребнера и системы алгебраических уравнений, Аржанцев, И. В.
  • Сборник задач по алгебре, учебник, под ред. А. И. Кострикина, 3-е изд., испр. и доп.
Источник — «http://wiki.cs.hse.ru/index.php?title=Алгебра_КНАД_2024/2025&oldid=88712»