Алгебраические алгоритмы и их сложность
Название спецкурса на английском языке
Algebraic algorithms and their complexity
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра МаТИС]
Семестр
Полгода (осень)
Тип курса
Спецкурс по выбору кафедры
Учебный год
2024/25
Список тем
Элементарное представление о сложности вычислений
Задача представления данных для числовых областей
Наибольший общий делитель в кольце целых чисел
Дискретное логарифмирование в конечных полях
Проверка чисел на простоту. Кармайкловы числа
Вероятностные тесты на простоту
Факторизация больших чисел
p-адические числа и коды Гензеля
Многочлены и рациональные функции
Полиномиальная арифметика
Алгоритмы вычисления НОД в кольцах многочленов над кольцом целых чисел и над произвольным полем
Факторизация многочленов
Алгоритм Берлекэмпа
Гензелев подъём
Уравнения, идеалы, многообразия
Определение базисов Грёбнера
Алгоритмы построения базисов Грёбнера
Задача представления данных для числовых областей
Наибольший общий делитель в кольце целых чисел
Дискретное логарифмирование в конечных полях
Проверка чисел на простоту. Кармайкловы числа
Вероятностные тесты на простоту
Факторизация больших чисел
p-адические числа и коды Гензеля
Многочлены и рациональные функции
Полиномиальная арифметика
Алгоритмы вычисления НОД в кольцах многочленов над кольцом целых чисел и над произвольным полем
Факторизация многочленов
Алгоритм Берлекэмпа
Гензелев подъём
Уравнения, идеалы, многообразия
Определение базисов Грёбнера
Алгоритмы построения базисов Грёбнера
Список источников
Панкратьев Е.В. Элементы компьютерной алгебры. - М.: БИНОМ. Лаборатория знаний, 2007. – 248 c.
Абрамов С.А. Лекции о сложности алгоритмов. – М.: Издательство МЦНМО, 2009. – 254 c.
Н. Коблиц, Курс теории чисел и криптографии. – М.: ТВП, 2001. – 262 c.
Т. Кормен, Ч. Лейзерсон, Р. Ривест, «Алгоритмы: построение и анализ» (MIT Press, Massachusets, 1990; МЦНМО, Москва, 2000).
Д. Кнут, "Искусство программирования" в 3х тт. (Addison-Wesley Longman Inc., Reading, 1998; Вильямс, Москва, 2000-2001)
Абрамов С.А. Лекции о сложности алгоритмов. – М.: Издательство МЦНМО, 2009. – 254 c.
Н. Коблиц, Курс теории чисел и криптографии. – М.: ТВП, 2001. – 262 c.
Т. Кормен, Ч. Лейзерсон, Р. Ривест, «Алгоритмы: построение и анализ» (MIT Press, Massachusets, 1990; МЦНМО, Москва, 2000).
Д. Кнут, "Искусство программирования" в 3х тт. (Addison-Wesley Longman Inc., Reading, 1998; Вильямс, Москва, 2000-2001)
День недели
пятница
Время
16:45-18:20
Аудитория
436
Дата первого занятия
Аудитория первого занятия
436
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.