Алгебраические задачи в теории сложности
Название спецкурса на английском языке
Algebraic problems in complexity theory
Пререквизиты
Отсутствуют
Целевая аудитория
1-2 курс
3-6 курс, магистранты
Подразделение
[Кафедра дискретной математики]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Битовая сложность умножения чисел. Быстрые алгоритмы умножения, их особенности.
Задача об эффективном возведении в степень и задача об аддитивных цепочках.
Векторные аддитивные цепочки. Задача Р. Беллмана. Задача Д. Кнута. Двойственность.
Сборка слов схемами конкатенации. Конструктивная нижняя оценка сложности сборки асимптотически самого сложного слова заданной длины.
Задача О. Б. Лупанова о сложности реализации элементов конечных абелевых групп.
Асимптотически точное решение.
Сложность вычисления элементов конечных нильпотентных и разрешимых групп.
Задача Н. Пиппенджера о сложности вычисления систем одночленов от нескольких переменных. Унивесальная нижняя оценка. Простые случаи: два одночлена или две переменные.
Сравнение задачи Пиппенджера и задачи о сложности вычисления систем элементов конечных абелевых групп.
Сложность аддитивных вычислений целочисленных линейных форм.
Задача о сложности вычисления элементов свободных абелевых групп.
Схемы из делений.
Сложность классических и обобщенных вентильных схем.
Задача об эффективном возведении в степень и задача об аддитивных цепочках.
Векторные аддитивные цепочки. Задача Р. Беллмана. Задача Д. Кнута. Двойственность.
Сборка слов схемами конкатенации. Конструктивная нижняя оценка сложности сборки асимптотически самого сложного слова заданной длины.
Задача О. Б. Лупанова о сложности реализации элементов конечных абелевых групп.
Асимптотически точное решение.
Сложность вычисления элементов конечных нильпотентных и разрешимых групп.
Задача Н. Пиппенджера о сложности вычисления систем одночленов от нескольких переменных. Унивесальная нижняя оценка. Простые случаи: два одночлена или две переменные.
Сравнение задачи Пиппенджера и задачи о сложности вычисления систем элементов конечных абелевых групп.
Сложность аддитивных вычислений целочисленных линейных форм.
Задача о сложности вычисления элементов свободных абелевых групп.
Схемы из делений.
Сложность классических и обобщенных вентильных схем.
Список источников
Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. --- Мир, 1979.
Сэвидж Д. Е. Сложность вычислений. --- М.: Факториал, 1998.
Кнут Д. Е. Искусство программирования. Т. 2. 3-е издание. --- М.: Издательский дом <Вильямс>>, 2000 (раздел 4.6.3).
Кочергин В. В. Задачи Беллмана, Кнута, Лупанова, Пиппенджера и их вариации как обобщения задачи об аддитивных цепочках // Математические вопросы кибернетики. Вып. 20. --- М.: ФИЗМАТЛИТ, 2022. --- С. 119–256.
https://keldysh.ru/papers/2022/mvk/mvk2022_119.pdf
Кочергин В. В. О сложности вычислений в конечных абелевых, нильпотентных и разрешимых группах// Дискретная математика. --- Т. 5, вып. 1. --- 1993. --- С. 91--111.
Кочергин В. В. О сложности вычислений в конечных нильпотентных группах // Дискретный анализ и исследование операций. --- 1996. --- Т. 3, No 1. --- С. 43--51.
Кочергин В. В. О максимальной сложности совместного вычисления систем элементов свободной абелевой группы // Вестник Московского университета. Сер. 1. Математика. Механика. --- 2007, No 3. --- С. 14--19.
Кочергин В. В. Сравнение сложности вычисления одночленов и элементов конечных абелевых групп // Вестник Московского университета. Сер. 1. Математика. Механика. --- 2022, No 3. --- С. 6--11.
Кочергин В. В. О сложности вычисления систем элементов конечных абелевых групп // Вестник Московского университета. Сер. 1. Математика. Механика. --- 2023, No 4. --- С. 22--29.
Сэвидж Д. Е. Сложность вычислений. --- М.: Факториал, 1998.
Кнут Д. Е. Искусство программирования. Т. 2. 3-е издание. --- М.: Издательский дом <Вильямс>>, 2000 (раздел 4.6.3).
Кочергин В. В. Задачи Беллмана, Кнута, Лупанова, Пиппенджера и их вариации как обобщения задачи об аддитивных цепочках // Математические вопросы кибернетики. Вып. 20. --- М.: ФИЗМАТЛИТ, 2022. --- С. 119–256.
https://keldysh.ru/papers/2022/mvk/mvk2022_119.pdf
Кочергин В. В. О сложности вычислений в конечных абелевых, нильпотентных и разрешимых группах// Дискретная математика. --- Т. 5, вып. 1. --- 1993. --- С. 91--111.
Кочергин В. В. О сложности вычислений в конечных нильпотентных группах // Дискретный анализ и исследование операций. --- 1996. --- Т. 3, No 1. --- С. 43--51.
Кочергин В. В. О максимальной сложности совместного вычисления систем элементов свободной абелевой группы // Вестник Московского университета. Сер. 1. Математика. Механика. --- 2007, No 3. --- С. 14--19.
Кочергин В. В. Сравнение сложности вычисления одночленов и элементов конечных абелевых групп // Вестник Московского университета. Сер. 1. Математика. Механика. --- 2022, No 3. --- С. 6--11.
Кочергин В. В. О сложности вычисления систем элементов конечных абелевых групп // Вестник Московского университета. Сер. 1. Математика. Механика. --- 2023, No 4. --- С. 22--29.
Дополнительная информация
https://keldysh.ru/papers/2022/mvk/mvk2022_119.pdf
День недели
вторник
Время
16:45-18:20
Аудитория
1213
Дата первого занятия
Аудитория первого занятия
1213
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.