class Algorithms {
public:
Algorithms lecture {
.author = "Р.А. Нестеров"
.year = "2026/27"
.course = "НИУ ВШЭ ПИ, 2 курс"
};
алгоритмы
и структуры данных
// 01. Мастер-теоремы для быстрого анализа рекуррентных соотношений
void divide_and_conquer();
void decrease_and_conquer();
void akra_bazzi();
// 02. Генерация случайных чисел — основа случайных алгоритмов
class TrueRandomNumberGenerator {...};
class PseudoRandomNumberGenerator {...};
// 03. Алгоритм Монте-Карло со случайной корректностью
double estimate_area();
bool verify_mmult(const Matrix& A, const Matrix& B, const Matrix& C);
->05
05.00
краткая ретроспектива и мастер-теоремы
первая мастер-теорема "разделяй-и-властвуй"
$T(n) = a\cdot T(n\,/\,b) +\mathrm{O}(n^k\cdot f(n))$
вторая мастер-теорема "уменьшай-и-властвуй"
$T(n) = a\cdot T(n - b) +\mathrm{O}(n^k\cdot f(n))$
теорема Акра-Баззи для рекуррентных
соотношений "разделяй-и-властвуй" общего вида
полное рекуррентное соотношение
параметры дерева рекурсии
- высота / число уровней $h = \mathrm{O}(\log_2 n)$
- сложность $i$-го уровня $3^i\cdot kn\,/\,2^i$
-
общая сложность:
$$\sum\limits_{i=0}^{h} kn \cdot \left(\frac{3}{2}\right)^i = kn \left(\frac{3^{h+1}}{2^h}-2\right) = \mathrm{O}(3^h) = \mathrm{O}(n^{\log_2 3})$$
void multiply_dac(const Matrix& A, const Matrix& B);
алгоритм Штрассена
семь рекурсивных умножений вместо восьми
теорема Ш. Винограда (1971)
для перемножения двух матриц размерности $2 \times 2$ необходимо и достаточно 7 умножений
задача 04.03
разработать такой рекурсивный алгоритм перемножения двух матриц $A$ и $B$ размерности $n \times n$, что число рекурсивных умножений блоков матриц составляет 7:
$T(n) = \begin{cases} \mathrm{O}(1) & n \leqslant 1 \\ 7\cdot T(n\,/\,2) + kn^2 & n > 1 \end{cases}$
решение
-
вычисляем 10 вспомогательных сумм
$S_1$ | $S_2$ |$S_3$|$S_4$|$S_5$ |$S_6$|$S_7$|$S_8$|$S_9$|$S_{10}$
- $S_1 = B_{12}-B_{22}$
- $S_2 = A_{11}+A_{12}$
- $S_3 = A_{21}+A_{22}$
- $S_4 = B_{21}-B_{11}$
- $S_5 = A_{11}+A_{22}$
- $S_6 = B_{11}+B_{22}$
- $S_7 = A_{12}-A_{22}$
- $S_8 = B_{21}+B_{22}$
- $S_9 = A_{11}-A_{21}$
- $S_{10} = B_{11}+B_{12}$
-
рекурсивно вычисляем 7 главных произведений
$P_1$ | $P_2$ |$P_3$|$P_4$|$P_5$ |$P_6$|$P_7$
- $P_1 = A_{11}\cdot S_{1}$
- $P_2 = S_{2}\cdot B_{22}$
- $P_3 = S_3\cdot B_{11}$
- $P_4 = A_{22}\cdot S_{4}$
- $P_5 = S_{5}\cdot S_{6}$
- $P_6 = S_{7}\cdot S_{8}$
- $P_7 = S_{9}\cdot S_{10}$
-
вычисляем блоки матрицы $C$
$C_{11}$ | $C_{12}$ |$C_{21}$|$C_{22}$
- $C_{11} = P_5 + P_4 - P_2 + P_6$
- $C_{12} = P_1 + P_2$
- $C_{21} = P_3 + P_4$
- $C_{22} = P_5 + P_1 - P_3 - P_7$
$\left( \begin{array}{c|c} A_{11} & A_{12} \\ \hline A_{21} & A_{22} \end{array} \right) \cdot \left( \begin{array}{c|c} B_{11} & B_{12} \\ \hline B_{21} & B_{22} \end{array} \right) = \left( \begin{array}{c|c} C_{11} & C_{12} \\ \hline C_{21} & C_{22} \end{array} \right)$
задача 04.04
выразить в общем виде решение рекуррентного соотношения
$T(n) = \begin{cases} \mathrm{O}(1) & n \leqslant b \\ a \cdot T\left(\dfrac{n}{b}\right) + \mathrm{O}(n^k \cdot f(n)) & n > b \end{cases}$
- $a \geqslant 1$ — фактор ветвления, количество подзадач
- $b > 1$ — коэффициент уменьшения размера задачи
-
$k \geqslant 0$ — порядок полиномиального роста затрат
на слияние решений подзадач - $f(n)$ — монотонная, $\forall m < n \colon f(m) \leqslant f(n)$
решение — итерационный метод
$\begin{aligned} T(n) &\leqslant a \cdot T\left(\dfrac{n}{b}\right) + c n^k f(n) \end{aligned}$
$\begin{aligned} \phantom{T(n)} &\leqslant a\left(a \cdot T\left(\dfrac{n}{b^2}\right) + c\left(\dfrac{n}{b}\right)^k f\left(\frac{n}{b}\right) \right) + c n^k f(n) \end{aligned}$
$\begin{aligned} \phantom{T(n)} &= a^2 \cdot T\left(\dfrac{n}{b^2}\right) + cn^k \left( f(n) + \left(\frac{a}{b^k} \right)f\left(\frac{n}{b}\right)\right) \end{aligned}$
$\begin{aligned} \phantom{T(n)} &= a^3 \cdot T\left(\dfrac{n}{b^3}\right) + cn^k \left( f(n) + \left(\frac{a}{b^k} \right) f\left(\frac{n}{b}\right) + \left(\frac{a}{b^k} \right)^2 f\left(\frac{n}{b^2}\right)\right) \end{aligned}$
$\begin{aligned} \phantom{T(n)} &= \dots \end{aligned}$
$\begin{aligned} \phantom{T(n)} &= a^h \cdot T\left(\dfrac{n}{b^h}\right) + cn^k \cdot \sum\limits_{i = 0}^{h-1}\left(\frac{a}{b^k} \right)^i f\left(\frac{n}{b^i}\right) \end{aligned}$
с учетом предельного значения $h = \log_b n$ получаем:$\begin{aligned} T(n) &= n^{\log_b a} \cdot \mathrm{O}(1) + \mathrm{O}(n^k \cdot f(n)) \cdot \sum\limits_{i = 0}^{\log_b-1}\left(\frac{a}{b^k} \right)^i \end{aligned}$
void divide_and_conquer();
первая мастер-теорема
быстрый анализ рекуррентных соотношений «разделяй-и-властвуй»
задача 04.04
выразить в общем виде решение рекуррентного соотношения
$T(n) = \begin{cases} \mathrm{O}(1) & n \leqslant b \\ a \cdot T\left(\dfrac{n}{b}\right) + \mathrm{O}(n^k \cdot f(n)) & n > b \end{cases}$
- $a \geqslant 1$ — фактор ветвления, количество подзадач
- $b > 1$ — коэффициент уменьшения размера задачи
-
$k \geqslant 0$ — порядок полиномиального роста затрат
на слияние решений подзадач - $f(n)$ — монотонная, $\forall m < n \colon f(m) \leqslant f(n)$
решение — вывод случаев
$\begin{aligned} T(n) &= n^{\log_b a} \cdot \mathrm{O}(1) + \mathrm{O}(n^k \cdot f(n)) \cdot \sum\limits_{i = 0}^{\log_b n-1}\left(\frac{a}{b^k} \right)^i \end{aligned}$
сравниваем значения порядков $k$ и $\log_b a$:-
$k = \log_b a \Rightarrow T(n) = \mathrm{O}(n^k \cdot f(n) \cdot \log n)$
[ разделяй уравновешивается с властвуй ] -
$k < \log_b a \Rightarrow T(n) = \mathrm{O}(n^{\log_b a} \cdot f(n))$
[ разделяй доминирует над властвуй ] -
$k > \log_b a \Rightarrow T(n) = \mathrm{O}(n^k \cdot f(n))$
[ властвуй доминирует над разделяй ]
void divide_and_conquer();
первая мастер-теорема
быстрый анализ рекуррентных соотношений «разделяй-и-властвуй»
теорема 04.01
$T(n) = \begin{cases} \mathrm{O}(1) & n \leqslant b \\ a \cdot T\left(\dfrac{n}{b}\right) + \mathrm{O}(n^k \cdot f(n)) & n > b \end{cases}$
верны следущие утверждения о сложности:- $k = \log_b a \Rightarrow T(n) = \mathrm{O}(n^k \cdot f(n) \cdot \log n)$
- $k < \log_b a \Rightarrow T(n) = \mathrm{O}(n^{\log_b a} \cdot f(n))$
- $k > \log_b a \Rightarrow T(n) = \mathrm{O}(n^k \cdot f(n))$
задача 04.05
найти верхнюю асимптотическую границу $\mathrm{O}(g(n))$ для соотношения $T(n) = T\left(\dfrac{n}{2}\right) + T\left(\dfrac{n}{4}\right) + cn\log n$
решение — выбор случая мастер-теоремы
в силу монотонности, $T\left(\dfrac{n}{b}\right) \leqslant T(n)$ для любого $b \geqslant 1$
- $T\left(\dfrac{n}{4}\right) \leqslant T\left(\dfrac{n}{2}\right) \Rightarrow T(n) \leqslant 2\cdot T\left(\dfrac{n}{2}\right)+ cn\log n$
- $a = 2$, $b = 2$, $k = 1$, $f(n) = \log n$
- $\log_b a = 1 = k \Rightarrow T(n) = \mathrm{O}(n^k \cdot f(n) \cdot \log n)$
ответ $g(n) = n \cdot \log^2 n$
задача 05.01
выразить в общем виде решение рекуррентного соотношения
$T(n) = \begin{cases} \mathrm{O}(1) & n \leqslant b \\ a \cdot T\left(n-b\right) + \mathrm{O}(n^k \cdot f(n)) & n > b \end{cases}$
- $a \geqslant 1$ — фактор ветвления, количество подзадач
- $b > 1$ — коэффициент уменьшения размера задачи
-
$k \geqslant 0$ — порядок полиномиального роста затрат
на слияние решений подзадач - $f(n)$ — монотонная, $\forall m < n \colon f(m) \leqslant f(n)$
решение — итерационный метод
$\begin{aligned} T(n) &\leqslant a \cdot T\left(n-b\right) + c n^k f(n) \end{aligned}$
$\begin{aligned} \phantom{T(n)} &\leqslant a\left(a \cdot T\left(n-2b\right) + cn^k f\left(n-b\right) \right) + c n^k f(n) \end{aligned}$
$\begin{aligned} \phantom{T(n)} &= a^2 \cdot T\left(n-2b\right) + cn^k \left( f(n) + a \cdot f(n-b)\right) \end{aligned}$
$\begin{aligned} \phantom{T(n)} &= a^3 \cdot T\left(n-3b\right) + cn^k \left( f(n) + a \cdot f(n-b) + a^2 \cdot f(n-2b) \right) \end{aligned}$
$\begin{aligned} \phantom{T(n)} &= \dots \end{aligned}$
$\begin{aligned} \phantom{T(n)} &= a^h \cdot T\left(n-hb\right) + cn^k \cdot \sum\limits_{i = 0}^{h-1}a^i f\left(n-ib\right) \end{aligned}$
с учетом предельного значения $h = n\,/\,b$ получаем:$\begin{aligned} T(n) &= a^{n\,/\,b} \cdot \mathrm{O}(1) + \mathrm{O}(n^k \cdot f(n)) \cdot \sum\limits_{i = 0}^{n\,/\,b - 1}a^i \end{aligned}$
void decrease_and_conquer();
вторая мастер-теорема
быстрый анализ рекуррентных соотношений «уменьшай-и-властвуй»
задача 05.01
выразить в общем виде решение рекуррентного соотношения
$T(n) = \begin{cases} \mathrm{O}(1) & n \leqslant b \\ a \cdot T\left(n-b\right) + \mathrm{O}(n^k \cdot f(n)) & n > b \end{cases}$
- $a \geqslant 1$ — фактор ветвления, количество подзадач
- $b > 1$ — коэффициент уменьшения размера задачи
-
$k \geqslant 0$ — порядок полиномиального роста затрат
на слияние решений подзадач - $f(n)$ — монотонная, $\forall m < n \colon f(m) \leqslant f(n)$
решение — вывод случаев
$\begin{aligned} T(n) &= a^{n\,/\,b} \cdot \mathrm{O}(1) + \mathrm{O}(n^k \cdot f(n)) \cdot \sum\limits_{i = 0}^{n\,/\,b - 1}a^i \end{aligned}$
значение $a$ определяет порядок роста верхней границы $T(n)$:-
$a = 1 \Rightarrow T(n) = \mathrm{O}(n^{k+1} \cdot f(n))$
[ на каждом уровне остается одна подзадача ] -
$a < 1 \Rightarrow T(n) = \mathrm{O}(n^{k} \cdot f(n))$
[ трудно интерпретируемый случай ] -
$a > 1 \Rightarrow T(n) = \mathrm{O}(a^{n\,/\,b} \cdot n^k \cdot f(n))$
[ экспоненциальный рост сложности ]
void akra_bazzi();
теорема Акра-Баззи
быстрый анализ рекуррентных соотношений «разделяй-и-властвуй» с подзадачами разного размера
теорема 05.01
$T(n) = \begin{cases} \mathrm{\Theta}(1) & 1\leqslant n \leqslant n_0 \\ \sum\limits_{i=1}^{k} a_i \cdot T(b_i\cdot n) + g(n) & n > n_0 \end{cases}$
пусть $p$ — это решение уравнения $a_1b_1^p + ... + a_kb_k^p = 1$, тогда верно соотношение для точной асимптотической границы:
$\displaystyle T(n) = \Theta\left(n^p \cdot \left(1 + \int_{1}^{n} \dfrac{g(u)}{u^{p+1}}du \right) \right)$
задача 05.02
найти точную асимптотическую границу $\mathrm{\Theta}(g(n))$ для соотношения $T(n) = 2\cdot T\left(\dfrac{n}{4}\right) + 3\cdot T\left(\dfrac{n}{6}\right) + dn\log_2 n$
решение — применение теоремы Акра-Баззи
- $\displaystyle 2 \cdot \left(\frac{1}{4}\right)^p + 3 \cdot \left(\frac{1}{6}\right)^p \Rightarrow p = 1$
-
подставим $p = 1$ и $g(u) = u \cdot \log_2 u$ в выражение:
$\displaystyle T(n) = \Theta\left(n^p \cdot \left(1 + \int_{1}^{n} \dfrac{u \cdot \log_2 u}{u^{2}}du \right) \right)$ - $T(n) = \Theta(n(1 + \ln^2 n - \ln^2 1))$
ответ $g(n) = n \cdot \log^2 n$
неделя №5
--> квиз Л4
05.01
генерация случайных чисел
простой линейный конгруэнтный генератор
стандартные средства библиотеки C++
и продакшен-библиотеки
проверка качества генераторов случайных чисел
справочник случайных чисел
class TrueRandomNumberGenerator {...};
истинно случайные числа
аппаратные источники энтропии
| категория | источник | принцип работы | применение |
|---|---|---|---|
| механика | монеты, кубики | микроизменения силы броска и трения | настольные игры, казино |
| поведение | ввод с мыши и клавиш | замер пауз между кликами / нажатиями | генерация криптокошельков |
| оптика | лавовые лампы | съемка хаотичного движения воска | защита веб-трафика (Cloudflare) |
| термодинамика | шум радиоэфира | фиксация атмосферных помех и гроз | генераторы в серверах (Random.org) |
| кванты | поведение фотонов | измерение направления частиц света | научные суперкомпьютеры |
сложности применения TRNG
- физические процессы протекают крайне медленно
- высокая стоимость сопровождения
- невоспроизводимость результатов экспериментов
- риск «истощения» пула энтропии при частых запросах
class PseudoRandomNumberGenerator {...};
псевдослучайные числа
детерминированные алгоритмы в стандартной библиотеке C++
| генератор | основа в c++ | принцип работы | применение и риски |
|---|---|---|---|
| линейный конгруэнтный · LCG | std::rand() |
$X_{n+1} = (aX_n + c) \mod m$ | быстрые тесты, высокая предсказуемость результатов |
| вихрь Мерсенна | std::mt19937 |
рекуррентные соотношения над двоичными полями | стандарт для игр и симуляций Монте-Карло с периодом $2^{19937}-1$ |
| перестановочный конгруэнтный · PCG | внешняя библиотека | комбинация LCG и нелинейных перестановок | современный продакшен, быстрее и компактнее mt19937 |
| на основе счетчиков · Philox (добавлен С++26) | std::philox4x64 |
блочное шифрование без состояний | масштабируемые параллельные вычисления, симуляции на GPU |
#include <random>
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> distrib(1, 6);
int dice = distrib(gen);
критерии оценки качества PRNG
- период генератора
- батареи статистических тестов [Dieharder, TestU01, PractRand]
- эффективность по памяти [состояние] и времени
провал генератора RANDU [IBM, 1960-1970]
- $X_{n+1} = 65539 \cdot X_n \mod 2^{31}$
- точки будут распределяться по ограниченному числу гиперплоскостей в пространстве
вихрь Мерсенна MT19937 [1997]
- период $2^{19937} - 1 \approx 4,3 \cdot 10^{6001}$
- точки распределяются по всему пространству равномерно, что делает генератор пригодным для использования
#include <iostream>
#include <cstdint>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
uint64_t state = 1;
while (true) {
state = (65539 * state) % 2147483648ULL;
uint32_t val = static_cast<uint32_t>(state);
std::cout.write(
reinterpret_cast<const char*>(&val),
sizeof(val)
);
if (!std::cout) break;
}
return 0;
}
#include <iostream>
#include <cstdint>
#include <cstdlib>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::srand(42);
while (true) {
uint32_t val = static_cast<uint32_t>(
std::rand()
);
std::cout.write(
reinterpret_cast<const char*>(&val),
sizeof(val)
);
if (!std::cout) break;
}
return 0;
}
#include <iostream>
#include <cstdint>
#include <cstdlib>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::mt19937 gen(42);
while (true) {
uint32_t val = gen();
std::cout.write(
reinterpret_cast<const char*>(&val),
sizeof(val)
);
if (!std::cout) break;
}
return 0;
}
#include <iostream>
#include <cstdint>
#include "pcg_random.hpp"
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
pcg32 rng;
rng.seed(42ULL, 54ULL);
while (true) {
uint32_t val = rng();
std::cout.write(
reinterpret_cast<const char*>(&val),
sizeof(val)
);
if (!std::cout) break;
}
return 0;
}
| std::rand() | std::mt19937 | pcg32 | |
|---|---|---|---|
| статус | <cstdlib>, наследие C | <random>, стандарт ISO | внешняя библиотека, де-факто стандарт |
| алгоритм | LCG, параметры зависят от реализации | вихрь Мерсенна | LCG + нелинейная перестановка (XSH-RR) |
| состояние | ≈ 4-8 байт, глобальное | ≈ 2.5 килобайта | 16 байт |
| период | $2^{31}$ | $2^{19937}-1$ | $2^{64}$ на поток $\times\,2^{63}$ потоков |
| качество · PractRand | провал на сотнях МБ | чисто до многих ГБ, отдельные провалы в BigCrush | чисто на масштабах ТБ |
| портируемость последовательности | ❌ glibc / macOS / MSVC дают разные | ✅ гарантирована стандартом | ✅ фиксирована библиотекой |
| потоки и параллелизм | нет: глобальное состояние | только ручные seed'ы | seed(seed, stream) |
| распределения <random> | ❌ ручной % со смещением |
✅ | ✅ |
| скорость | ★★☆ формально высокая, качество нулевое | ★★☆ средняя: состояние не живёт в регистрах | ★★★ высокая: всё в регистрах |
* std::mt19937 без явного значения seed всегда выдает одну и ту же последовательность — воспроизводимость (default = 5489)
05.02
алгоритм Монте-Карло
оценка площади фигуры: пробуем,
а не исследуем пространство
верификация матричного умножения: случайная
линейная проекция матрицы ошибок
double estimate_area();
метод Монте-Карло: оценка ошибки
стандартное отклонение результатов симуляции
утверждение 05.01
доказательство
- вероятность попадания $p = S_{\bigcirc}\,/\,S_{\square} = \pi \,/\,4$
- параметры $X_i$ $\mathbb{E}(X_i) = p, \mathrm{Var}(X_i) = p(1-p)$
- $N_{in} = X_1 +\dots +X_N \Rightarrow \mathrm{Var}(N_{in})=N\cdot p(1-p)$
- $\hat{\pi} = 4N_{in}\,/\,N \Rightarrow \mathrm{Var}(\hat{\pi})= 16p(1-p)\,/\,N = 2.7\,/\,N$
$X_i = 1$, если точка $X_i$ попала в круг и $X_i = 0$, если не попала
ответ $\sigma(\hat{\pi}) = 1.64 \,/\,\sqrt{N} = \mathrm{O}(1\,/\,\sqrt{N})$
| точность | общее число точек |
|---|---|
| $\pm 0.1$ | $\approx 300$ |
| $\pm 0.01$ | $\approx 30\,\,000$ |
| $\pm 0.001$ | $\approx 3\,\,000\,\,000$ |
| $\pm 10^{-6}$ | $\approx 3\cdot 10^{12}$ |
* каждая следующая значащая цифра стоит в 100 раз больше точек
[ погрешность в одно стандартное отклонение $\sigma$ ]
template<typename F> double integrate(F f, int d, uint64_t steps);
проклятие размерности
когда метод Монте-Карло безальтернативен
задача 05.02
решение — сетка
для хорошей точности вычислений используем сетку $10^d$ точек
- $d=1\Rightarrow$ отмечаем 10 точек на линии
- $d=2\Rightarrow$ проверка 100 квадратов
- $d=3\Rightarrow$ проверка 1 000 кубов
| $d$ | сетка | Монте-Карло | 🏆 |
|---|---|---|---|
| 1 | $N^{-2}$ | $N^{-1\,/\,2}$ | сетка |
| 2 | $N^{-1}$ | $N^{-1\,/\,2}$ | сетка |
| 4 | $N^{-1\,/\,2}$ | $N^{-1\,/\,2}$ | паритет |
| 10 | $N^{-1\,/\,5}$ | $N^{-1\,/\,2}$ | Монте-Карло |
| 100 | $N^{-1\,/\,50}$ | $N^{-1\,/\,2}$ | Монте-Карло |
* ошибка метода Монте-Карло не зависит от размерности!
bool verify_mmult(const Matrix& A, const Matrix& B, const Matrix& C);
верификация матричного умножения
в чем сложность проверки $AB = C$ и где закралась ошибка?
задача 05.03
на проверку поступили три матрицы:
$A = \begin{pmatrix} a & b \\ c & d \end{pmatrix} B = \begin{pmatrix} e & f \\ g & h \end{pmatrix} C = \begin{pmatrix} \textcolor{#FB7171}{X} & y \\ z & w \end{pmatrix}$
- пусть, например, в матрице $C$ ошибочным является только один блок $X$ [ ошибок может быть больше ]
-
необходимо установить истинность $AB = C$ за $\mathrm{O}(n^2)$,
не пересчитывая результат $AB$ заново
решение — идея Русиньша фрейвальдса
определим матрицу ошибок $D$:
$D = AB - C = \begin{pmatrix} \textcolor{#FB7171}{\Delta} & 0 \\ 0 & 0 \end{pmatrix}$
умножаем матрицу ошибок $D$ на случайный бинарный вектор-детектор $r = (r_1 \,\, r_2)^T$, то есть, $r \in \{0, 1\}^2$:
$Dr = \begin{pmatrix} \textcolor{#FB7171}{\Delta} & 0 \\ 0 & 0 \end{pmatrix} \cdot \begin{pmatrix} r_1 \\ r_2 \end{pmatrix} = \begin{pmatrix} \textcolor{#FB7171}{\Delta}\cdot r_1 \\ 0 \end{pmatrix}$
- если $r_1 = 1$, то $Dr = (\textcolor{#FB7171}{\Delta}\,\,0)^T \neq 0$, ошибка обнаружена!
- если $r_1 = 0$, то $Dr = (0\,\,0)^T \neq 0$, ошибка скрылась...
bool verify_mmult(const Matrix& A, const Matrix& B, const Matrix& C);
верификация матричного умножения
обман вычислительной сложности
задача 05.03
на проверку поступили три матрицы:
$A = \begin{pmatrix} a & b \\ c & d \end{pmatrix} B = \begin{pmatrix} e & f \\ g & h \end{pmatrix} C = \begin{pmatrix} \textcolor{#FB7171}{X} & y \\ z & w \end{pmatrix}$
- пусть, например, в матрице $C$ ошибочным является только один блок $X$ [ ошибок может быть больше ]
-
необходимо установить истинность $AB = C$ за $\mathrm{O}(n^2)$,
не пересчитывая результат $AB$ заново
решение — идея Русиньша фрейвальдса
боремся с тяжелым матричным умножением в:
$Dr = (AB - C)r = \textcolor{#FB7171}{(}AB\textcolor{#FB7171}{)}r - Cr$
умножение матриц ассоциативно, поэтому:
$\textcolor{#FB7171}{(}AB\textcolor{#FB7171}{)}r - Cr = A\textcolor{#34D399}{(}Br\textcolor{#34D399}{)} - Cr$
итоговая последовательность шагов вычисления $Dr$:
- $b = Br \Longrightarrow \mathrm{O}(n^2)$
- $a = Ab \Longrightarrow \mathrm{O}(n^2)$
- $c = Cr \Longrightarrow \mathrm{O}(n^2)$
- $Dr = a - c$
сложность $\mathrm{O}(n^2)$, и никакого умножнеия матриц!
bool verify_mmult(const Matrix& A, const Matrix& B, const Matrix& C);
верификация матричного умножения
вероятность ошибки ниже 50%
задача 05.03
на проверку поступили три матрицы:
$A = \begin{pmatrix} a & b \\ c & d \end{pmatrix} B = \begin{pmatrix} e & f \\ g & h \end{pmatrix} C = \begin{pmatrix} \textcolor{#FB7171}{X} & y \\ z & w \end{pmatrix}$
- пусть, например, в матрице $C$ ошибочным является только один блок $X$ [ ошибок может быть больше ]
-
необходимо установить истинность $AB = C$ за $\mathrm{O}(n^2)$,
не пересчитывая результат $AB$ заново
решение — оценка вероятности ошибки
$r$ — случайный бинарный вектор в пространстве $\{0, 1\}^n$
- алгоритм ошибается, если $D = AB - C \neq 0$, а $Dr = 0$
- если $D \neq 0$, то в ней найдется хотя бы один элемент $\textcolor{#FB7171}{d_{ij}} \neq 0$, через который мы выразим из $Dr = 0$ случайный бит $r_j$, скрывающий ошибку в матрице $C$:
- тогда правая часть в выражении для $r_j$ — это константа, с которой должен совпасть случайный бит $r_j \in \{0, 1\}$
$d_{i1}r_1 + \dots + \textcolor{#FB7171}{d_{ij}}r_j + \dots + d_{in}r_n = 0 \Rightarrow r_j = \dfrac{\sum_{k \neq j} d_{ik}r_k}{\textcolor{#FB7171}{d_{ij}}}$
ошибка $\mathbb{P}(Dr = 0 \mid D \neq 0) \leqslant 0.5$
bool verify_mmult(const Matrix& A, const Matrix& B, const Matrix& C);
верификация матричного умножения
усиление надежности через независимые запуски
задача 05.ХХ
на проверку поступили три матрицы:
$A = \begin{pmatrix} a & b \\ c & d \end{pmatrix} B = \begin{pmatrix} e & f \\ g & h \end{pmatrix} C = \begin{pmatrix} \textcolor{#FB7171}{X} & y \\ z & w \end{pmatrix}$
- пусть, например, в матрице $C$ ошибочным является только один блок $X$ [ ошибок может быть больше ]
-
необходимо установить истинность $AB = C$ за $\mathrm{O}(n^2)$,
не пересчитывая результат $AB$ заново
решение — усиление надежности
$r$ — случайный бинарный вектор в пространстве $\{0, 1\}^n$
один случайный вектор $r$ дает вероятность ошибки $\leqslant$ 50% $\Rightarrow$
$k$ раз повторяем тест $A(Br) - Cr = 0$
с независимыми векторами $r^{(1)},r^{(2)} \dots, r^{(k)}$
- алгоритм ошибается, если каждый из $k$ тестов ошибется:
- например, при $k = 30$ достигается $\mathbb{P} \leqslant 9.3 \cdot 10^{-10}$, что делает алгоритм надежным
$\mathbb{P}(\text{глобальная ошибка}) \leqslant \dfrac{1}{2} \cdot \dots \dfrac{1}{2} = \dfrac{1}{2^k}$
итог сложность возрастает до $\mathrm{O}(kn^2)$, а вероятность неверного ответа падает экспоненциально
| ошибок в матрице | k = 1 | k = 2 | k = 3 | k = 4 | k = 5 |
|---|---|---|---|---|---|
| 1 ошибка | 50.13% | 24.65% | 12.79% | 6.10% | 3.20% |
| 2 ошибки | 24.76% | 6.22% | 1.55% | 0.38% | 0.09% |
| 3 ошибки | 25.00% | 6.19% | 1.49% | 0.40% | 0.11% |
* эмпирическая оценка вероятности неверного ответа алгоритма Фрейвальдса по 50 000 запускам
05.03
SET 2: домашняя работа
получение новых задач из upstream-репозитория
задачи и баллы новой работы
void set_hw_environment();
домашняя работа set_2
разделяй-и-властвуй · асимптотический анализ · рекуррентные соотношения
| ID | Баллы | Комментарий |
|---|---|---|
| a1_rec_complexity CORE | 7 | анализ временной сложности $T(n)$ рекурсивного алгоритма |
| a2_faster_strassen CORE | 6 | сравнение рекуррентных соотношений |
| a3_master_theorem CORE | 11 | применение мастер-теорем и метода Акра-Баззи |
| p1_intervals CORE | 7 | применение парадигмы "разделяй-и-властвуй" |
| p2_nmult CORE | 9 | "разделяй-и-властвуй" умножение больших целых чисел |
| p3_mmult CORE | 8 | "разделяй-и-властвуй" умножение квадратных матриц |
| p4_dunes CORE | 6 | применение парадигмы "разделяй-и-властвуй" |
| p5_clpair2d CORE | 7 | "разделяй-и-властвуй" поиск пары ближайших точек в 2D |
| p6x_clpair3d EXTRA | 10 | "разделяй-и-властвуй" поиск пары ближайших точек в 3D |
| k_mreduce CORE | 10 + 5 | реализация ядра движка MapReduce |
// Лекция 05 завершена
// Резюме основных моментов
что мы
рассмотрели сегодня:
-
мастер-теоремы и теорема Акра-Баззи
быстрый вывод асимптотической сложности
по виду рекуррентного соотношения -
генератор псевдослучайных чисел
основа надежности работы случайного алгоритма,
оценка качества генераторов -
алгоритмы Монте-Карло
случайная корректность и вероятность ошибки,
оценка площадей и проверка матричного умножения
--> на следующей лекции
--> алгоритм Лас-Вегас, быстрая сортировка,
--> ADT Очередь с приоритетами и HEAP SORT
};
return 0;
05->