Аддитивные цепочки и их обобщения
Название спецкурса на английском языке
Addition chains and their generalizations
Пререквизиты
Отсутствуют
Целевая аудитория
1-2 курс
3-6 курс, магистранты
Подразделение
[Кафедра дискретной математики]
Семестр
Полгода (весна)
Тип курса
Спецкурс по выбору студента
Учебный год
2024/25
Список тем
Задача об эффективном возведении в степень и задача об аддитивных цепочках.
Векторные аддитивные цепочки. Задача Р. Беллмана. Задача Д. Кнута. Двойственность.
Сборка слов схемами конкатенации. Конструктивная нижняя оценка сложности сборки асимптотически самого сложного слова заданной длины.
Задача О. Б. Лупанова о сложности реализации элементов конечных абелевых групп.
Задача Н. Пиппенджера о сложности вычисления систем одночленов от нескольких переменных. Унивесальная нижняя оценка. Простые случаи: два одночлена или две переменные.
Сложность аддитивных вычислений целочисленных линейных форм.
Схемы из делений.
Сложность классических и обобщенных вентильных схем.
Векторные аддитивные цепочки. Задача Р. Беллмана. Задача Д. Кнута. Двойственность.
Сборка слов схемами конкатенации. Конструктивная нижняя оценка сложности сборки асимптотически самого сложного слова заданной длины.
Задача О. Б. Лупанова о сложности реализации элементов конечных абелевых групп.
Задача Н. Пиппенджера о сложности вычисления систем одночленов от нескольких переменных. Унивесальная нижняя оценка. Простые случаи: два одночлена или две переменные.
Сложность аддитивных вычислений целочисленных линейных форм.
Схемы из делений.
Сложность классических и обобщенных вентильных схем.
Список источников
Кнут Д. Е. Искусство программирования. Т. 2. 3-е издание. --- М.: Издательский дом <<Вильямс>>, 2000 (раздел 4.6.3).
Кочергин В. В. Задачи Беллмана, Кнута, Лупанова, Пиппенджера и их вариации как обобщения задачи об аддитивных цепочках // Математические вопросы кибернетики. Вып. 20. --- М.: ФИЗМАТЛИТ, 2022. --- С. 119–256.
Кочергин В. В. Задачи Беллмана, Кнута, Лупанова, Пиппенджера и их вариации как обобщения задачи об аддитивных цепочках // Математические вопросы кибернетики. Вып. 20. --- М.: ФИЗМАТЛИТ, 2022. --- С. 119–256.
Дополнительная информация
https://keldysh.ru/papers/2022/mvk/mvk2022_119.pdf
День недели
вторник
Время
16:45-18:20
Аудитория
409
Дата первого занятия
Аудитория первого занятия
409
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.