|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Аддитивные цепочки и их обобщенияучебный курс
- Автор: Кочергин В.В.
- Год создания: 2012
- Организация: МГУ имени М.В. Ломоносова
- Описание: Какое минимальное число операций умножения достаточно для возведения $x$ в степень $n$? Или, в аддитивной постановке, какова минимальная длина $r$ цепочки натуральных чисел $$ a_0=1, a_1, a_2, \ldots, a_r=n, $$ начинающейся с $1$ и заканчивающейся числом $n$, в которой каждое число $a_i$, $i=1, 2, \ldots, r$, является суммой двух предыдущих (не обязательно различных)? Если $n=2^k$, то ответ очевиден: $k$. В общем случае простейшие оценки этой величины снизу и сверху отличаются вдвое ($\log_2 n$ и $2 \log_2 n$, соответственно). Оказывается, что эта величина растет как $\log_2 n + \alpha_n$, где $\lim\limits_{n \to \infty} \frac{\alpha_n}{\log_2 n} = 0$. Как уточнить эту оценку? Что можно сказать про минимальное число операций умножения, достаточное для вычисления по переменным $x_1, x_2, \ldots, x_m$ одночлена $x_1^{n_1} x_2^{n_2} \ldots x_m^{n_m}$ (задача Ричарда Беллмана)? Что можно сказать про минимальное число операций умножения, достаточное для вычисления по переменной $x$ набора степеней $x^{n_1}, x^{n_2}, \ldots, x^{n_m}$ (задача Дональда Кнута)? Об этих и близких задачах пойдет речь в курсе. Предварительных знаний не требуется.
- Добавил в систему: Кочергин Вадим Васильевич
Преподавание курса
- с 1 сентября 2013 Кочергин Вадим Васильевич
- МГУ имени М.В. Ломоносова, Механико-математический факультет
- обязательная, по выбору (спецкурс), лекции, 36 часов
- Автор: Кочергин В.В.