Продвинутые темы

Имея основы и базовые концепции, мы переходим к территории, соединяющей чистую математику и реальные алгоритмы: теория графов, рекуррентные соотношения и производящие функции.

Теория графов

Граф $G = (V, E)$ состоит из множества вершин $V$ и множества рёбер $E$ .

Представления графов

from collections import defaultdict

# Список смежности
граф = defaultdict(list)
рёбра = [(0, 1), (0, 2), (1, 2), (2, 3)]
for u, v in рёбра:
    граф[u].append(v)
    граф[v].append(u)

for вершина, соседи in sorted(граф.items()):
    print(f"  {вершина}: {соседи}")

Обход графов

BFS (поиск в ширину) использует очередь, DFS (поиск в глубину) использует стек (или рекурсию).

Формула Эйлера для планарных графов

V - E + F = 2

Рекуррентные соотношения

Последовательность Фибоначчи

F(n) = F(n-1) + F(n-2), \quad F(0) = 0, \quad F(1) = 1

Формула Бине (замкнутая форма):

F(n) = \frac{\phi^n - \hat{\phi}^n}{\sqrt{5}}, \quad \phi = \frac{1+\sqrt{5}}{2}

Основная теорема (Master Theorem)

Для рекуррентностей вида $T(n) = aT(n/b) + O(n^d)$ :

Алгоритм	Рекуррентность	Сложность
Бинарный поиск	$T(n) = T(n/2) + O(1)$	$O(\log n)$
Сортировка слиянием	$T(n) = 2T(n/2) + O(n)$	$O(n \log n)$

Производящие функции

Производящая функция кодирует последовательность $(a_0, a_1, a_2, \ldots)$ как формальный степенной ряд:

G(x) = \sum_{n=0}^{\infty} a_n x^n