Дискретная математика
Рекуррентные соотношения
Сколько способов расставить скобки в произведении $n$ матриц? Ответ - число Каталана $C_{n-1}$ - вычисляется через рекуррентное соотношение за $O(n)$, тогда как наивный перебор занял бы экспоненциальное время.
- Алгоритм Карацубы умножения чисел основан на рекуррентности $T(n) = 3T(n/2) + O(n)$ - Мастер-теорема даёт $O(n^{\log_2 3}) \approx O(n^{1.585})$ против $O(n^2)$ наивного умножения.
- FFT-рекуррентность $T(n) = 2T(n/2) + O(n)$ раскрывается в $O(n \log n)$ - именно это делает обработку сигналов практичной для миллиардов точек.
- Числа Фибоначчи в природе: спирали подсолнуха, соотношения кроликов - описываются линейными рекуррентностями с характеристическим уравнением.
Цели урока
- Составлять и решать линейные рекуррентные соотношения через характеристические корни
- Применять Мастер-теорему для оценки сложности divide-and-conquer алгоритмов
- Вычислять числа Каталана и распознавать задачи, в которых они возникают
Предварительные знания
- Математическая индукция и доказательства по индукции
- Производящие функции - формальные степенные ряды
- Основы комбинаторики: биномиальные коэффициенты
Линейные рекуррентности с постоянными коэффициентами
Линейная рекуррентность $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k}$ имеет общее решение в виде суперпозиции: если $r_1, \ldots, r_k$ - корни характеристического уравнения $r^k = c_1 r^{k-1} + \ldots + c_k$ (попарно различные), то $a_n = \alpha_1 r_1^n + \ldots + \alpha_k r_k^n$. Константы $\alpha_i$ определяются из начальных условий.
Матричный метод: $\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix} = \begin{pmatrix}1&1\\1&0\end{pmatrix}^n \begin{pmatrix}1\\0\end{pmatrix}$. Быстрое возведение в степень за $O(\log n)$ умножений даёт $F_n$ за $O(M(k) \log n)$, где $M(k)$ - стоимость умножения $k\times k$ матриц. Применяется в оптимизации линейных рекуррентностей в competitive programming.
Мастер-теорема и анализ рекурсий
Для рекуррентности $T(n) = aT(n/b) + f(n)$ с $a \geq 1$, $b > 1$ Мастер-теорема сравнивает $f(n)$ с $n^{\log_b a}$. Случай 1: $f(n) = O(n^{\log_b a - \varepsilon})$ - доминирует рекурсия, $T(n) = \Theta(n^{\log_b a})$. Случай 2: $f(n) = \Theta(n^{\log_b a})$ - оба равны, $T(n) = \Theta(n^{\log_b a} \log n)$. Случай 3: $f(n) = \Omega(n^{\log_b a + \varepsilon})$ - доминирует слияние, $T(n) = \Theta(f(n))$.
Мастер-теорема не применима, если $f(n)$ не является полиномиально большим или малым относительно $n^{\log_b a}$. Например, $T(n) = 2T(n/2) + n/\log n$ попадает между случаями 1 и 2 - теорема молчит. В таких случаях используют метод Акра-Баззи или непосредственно разворачивают рекуррентность.
Числа Каталана $C_n = \frac{1}{n+1}\binom{2n}{n}$ впервые систематически изучил
Числа Каталана $C_n = \frac{1}{n+1}\binom{2n}{n}$ впервые систематически изучил Эжен Шарль Каталан в 1838 году, хотя Эйлер знал их ещё в 1751-м при подсчёте триангуляций многоугольника. Они считают: правильные скобочные последовательности, пути решётки ниже диагонали, полные бинарные деревья. Слово «числа Каталана» ввёл Риордан в 1948 году - 107 лет спустя после первой публикации.
Линейные рекуррентности и формула Бине
Сортировка слиянием: T(n) = 2T(n/2) + n. Алгоритм Карацубы: T(n) = 3T(n/2) + n. Master Theorem решает оба за 10 секунд: первый O(n log n), второй O(n^1.585). Разница в 1 ОДУ объяснила, почему Карацуба в 1960 году обогнал стандартное умножение столбиком.
Линейная однородная рекуррентность k-го порядка: a_n = c_1*a_{n-1} + ... + c_k*a_{n-k}. Термин 'однородная' - нет свободного члена f(n). Примеры: Фибоначчи (k=2), трибоначчи (k=3). Неоднородные (с f(n)) - mergesort, binary search.
Матричный метод универсален: любая линейная рекуррентность a_n = c_1*a_{n-1} + ... + c_k*a_{n-k} решается за O(k^3 * log n) через возведение матрицы компаньона в степень. Для больших n и фиксированного k это радикально быстрее итерации.
Почему рекурсивный Фибоначчи без мемоизации имеет сложность O(phi^n) ~ O(1.618^n)?
Число вызовов T(n) удовлетворяет той же рекуррентности T(n) = T(n-1) + T(n-2). По формуле Бине её решение растёт как phi^n/sqrt(5), где phi=(1+sqrt(5))/2~1.618.
Метод характеристических уравнений
Ищем решение a_n = c_1*a_{n-1} + c_2*a_{n-2} в виде a_n = r^n. Подстановка даёт характеристическое уравнение r^2 = c_1*r + c_2. Его корни r_1, r_2 определяют общее решение.
Характеристическое уравнение дало двойной корень r=3. Какова общая форма решения?
При простом корне r - решение A*r^n. Кратность k добавляет полиномиальный множитель степени k-1: при кратности 2 решение имеет вид (A + B*n)*r^n.
Master Theorem: анализ divide-and-conquer
T(n) = a*T(n/b) + f(n): a подзадач размером n/b, f(n) - слияние. Критическая функция n^(log_b a) - «работа рекурсивного дерева». Три случая: f(n) растёт медленнее, одинаково или быстрее критической функции.
| Алгоритм | Рекуррентность | log_b(a) | Асимптотика |
|---|---|---|---|
| Mergesort | 2T(n/2) + n | 1.000 | Theta(n log n) |
| Binary Search | T(n/2) + 1 | 0.000 | Theta(log n) |
| Strassen | 7T(n/2) + n^2 | 2.807 | Theta(n^2.807) |
| Karatsuba | 3T(n/2) + n | 1.585 | Theta(n^1.585) |
| FFT | 2T(n/2) + n | 1.000 | Theta(n log n) |
Master Theorem не применим: если a < 1, b <= 1, если размеры подзадач не n/b (T(n) = T(n-1)+n - worst case quicksort), или если f(n) не полиномиальная (например n*log n между случаями 1 и 2). Для таких случаев - теорема Акра-Бацци.
T(n) = 4T(n/2) + n. Какова асимптотика? Обоснование через Master Theorem.
Master Theorem: T(n) = a*T(n/b) + f(n), a=4, b=2, f(n)=n. Критический показатель p = log_2(4) = 2. Так как f(n) = O(n^{2-1}) (случай 1), рекурсия доминирует: T(n) = Theta(n^2).
Производящие функции и числа Каталана
Производящая функция последовательности (a_n): G(x) = sum a_n * x^n. Рекуррентность -> алгебраическое уравнение для G(x). Числа Каталана C_n = C(2n,n)/(n+1): число корректных скобочных последовательностей длины 2n, число BST из n ключей, число триангуляций (n+2)-угольника.
Числа Каталана в computer science: C_n - число бинарных деревьев поиска из n ключей (это объясняет, почему случайный BST имеет ожидаемую высоту O(log n), но детерминированный может быть O(n)). В парсерах: количество деревьев разбора для неоднозначных грамматик.
C_3 = 5. Перечислите все 5 структур BST из 3 ключей {1,2,3}.
Число BST из n ключей - число Каталана C_n. Для n=3: C_3=5. По корню: корень 1 - 2 дерева (правое поддерево из {2,3}), корень 2 - 1, корень 3 - 2. Итого 2+1+2=5.
Золотое сечение в числах Фибоначчи
Для $F_n = F_{n-1} + F_{n-2}$ характеристическое уравнение $r^2 = r + 1$ даёт корни $\phi = (1+\sqrt{5})/2 \approx 1.618$ и $\hat{\phi} = (1-\sqrt{5})/2$. Из $F_0=0, F_1=1$: $F_n = (\phi^n - \hat{\phi}^n)/\sqrt{5}$. При $n > 1$ член $|\hat{\phi}^n| < 1/2$, поэтому $F_n$ - ближайшее целое к $\phi^n/\sqrt{5}$.
Итоги
- Линейные рекуррентности решаются через характеристические корни.
- Мастер-теорема превращает divide-and-conquer рекуррентности в замкнутые формулы.
- Числа Каталана $C_n = \frac{1}{n+1}\binom{2n}{n}$ считают структуры с рекурсивным самоподобием.
- Матричный метод ускоряет любую линейную рекуррентность до $O(\log n)$.
Связь с другими темами
Производящие функции (dm-14) дают альтернативный путь к тем же замкнутым формулам - через коэффициенты разложения. В динамическом программировании рекуррентность Беллмана имеет ту же структуру: оптимальная подзадача выражается через оптимальные подподзадачи.
- Dm 14 — связан
Вопросы для размышления
- Числа Каталана возникают более чем в 200 комбинаторных задачах. Попробуйте доказать, что количество правильных скобочных последовательностей длины $2n$ равно $C_n$ через биекцию с путями решётки - и убедитесь, что одна рекуррентность $C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$ кодирует всё это разнообразие.?