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

Материал из Wiki - Факультет компьютерных наук
Перейти к навигации Перейти к поиску
← Предыдущая правка
Нет описания правки
 
(не показано 15 промежуточных версий 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.2024). Коды с исправлением ошибок. Расстояние Хэмминга, минимальное расстояние кода, количество исправляемых ошибок. Линейные коды, вес элемента, проверочная матрица, количество исправляемых ошибок в терминах проверочной матрицы. Коды Хэмминга. Неравенство Синглтона. Коды Рида-Соломона.
 
'''Лекция 9''' (18.11.2024). Многочлены от нескольких переменных. Лексикографический порядок, стабилизация убывающих цепочек мономов. Элементарная редукция, редукция относительно множества многочленов, остатки, базис Грёбнера. Остановка процесса редукции.
 
'''Лекция 10''' (25.11.2024). S-многочлен и критерий Бухбергера. Идеалы в кольце многочленов от нескольких переменных, алгоритм Бухбергера для построения базиса Грёбнера идеала. Проблема принадлежности идеалу и исключения переменных.
 
'''Лекция 11''' (02.12.2024). Diamond Lemma. Доказательство критерия Бухбергера. Лемма Диксона и остановка алгоритма Бухбергера.
 
'''Лекция 12''' (09.12.2024). Отношения эквивалентности и фактормножества. Конгруэнция на группе. Построение структуры группы на классах эквивалентности. Описание конгруэнтностей в терминах нормальных подгрупп.


= Домашнее задание =
= Домашнее задание =
Строка 81: Строка 91:


* [https://disk.yandex.ru/i/QKB9fVSnLDyu-g Домашнее задание 8]
* [https://disk.yandex.ru/i/QKB9fVSnLDyu-g Домашнее задание 8]
* [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]


= Куда сдавать домашнее задание =
= Куда сдавать домашнее задание =
Строка 93: Строка 111:
Дата экзамена --  
Дата экзамена --  


* [ Список] определений и формулировок.
* [https://disk.yandex.ru/i/jj64fd3fEYVZKA Список] определений и формулировок.


* [ Список] вопросов на доказательства.
* [https://disk.yandex.ru/i/QcrGDRgkCDHjsQ Список] вопросов на доказательства.


* [ Правила] проведения экзамена со всеми ссылками и информацией.
* [https://disk.yandex.ru/i/ghlKylWq4X2rVA Правила] проведения экзамена со всеми ссылками и информацией.


= Ведомости текущего контроля =
= Ведомости текущего контроля =
Строка 109: Строка 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]
|}


= Ссылки =
= Ссылки =
Строка 116: Строка 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 Конспекты] лекций.

Текущая версия от 19: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-е изд., испр. и доп.
Источник — https://wiki.cs.hse.ru/index.php?title=Алгебра_КНАД_2024/2025&oldid=88712