math

Введение - зачем программисту математика

Математика для программиста - это не абстрактная дисциплина из университетского курса, а рабочий инструмент. Без понимания логарифмов невозможно оценить сложность алгоритма. Без теории вероятностей не получится грамотно провести A/B тест. Без линейной алгебры не разберёшься в машинном обучении. Без дискретной математики не поймёшь, как работают графы, деревья и конечные автоматы.

При этом не вся математика одинаково важна для инженера. Практическая значимость разделов распределяется примерно так:

• Дискретная математика - фундамент компьютерных наук. Логика, множества, графы, комбинаторика - всё это ежедневные инструменты
• Алгебра и логарифмы - анализ сложности алгоритмов невозможен без этих знаний
• Теория вероятностей и статистика - продуктовая аналитика, машинное обучение, принятие решений на основе данных
• Линейная алгебра - машинное обучение, компьютерная графика, рекомендательные системы
• Математический анализ - оптимизация в ML, физические симуляции
• Теория чисел - криптография, хеш-функции
• Геометрия и тригонометрия - разработка игр, компьютерная графика, геолокация

Принцип изучения

Не нужно осваивать всё сразу. Начните с дискретной математики и теории сложности - они пригодятся в первый же день работы. Остальное изучайте по мере необходимости, когда конкретная задача потребует конкретных знаний.

---

Арифметика и числа

Виды чисел

Числа образуют иерархию множеств, где каждое следующее множество включает предыдущее.

Натуральные числа $\mathbb{N}$ - это числа для счёта предметов: $1,2,3,4,\dots$ В некоторых определениях ноль тоже считается натуральным числом. В программировании натуральные числа встречаются повсюду - индексы массивов, количество элементов, номера итераций.

Целые числа $\mathbb{Z}$ расширяют натуральные добавлением нуля и отрицательных чисел: $\dots ,-3,-2,-1,0,1,2,3,\dots$ Типы int, int32, int64 в языках программирования представляют подмножество целых чисел, ограниченное размером типа.

Рациональные числа $\mathbb{Q}$ - это все числа, которые можно представить в виде дроби $\frac{p}{q}$, где $p$ и $q$ - целые числа, а $q\ne 0$. Примеры: $\frac{1}{2}$, $\frac{7}{3}$, $-\frac{5}{8}$. Любое рациональное число при записи десятичной дробью либо конечно, либо образует периодическую последовательность цифр.

Иррациональные числа - это числа, которые нельзя представить дробью. Их десятичная запись бесконечна и непериодична. Примеры: $\sqrt{2}\approx 1.41421356\dots$, $\pi \approx 3.14159265\dots$, $e\approx 2.71828182\dots$

Вещественные числа $\mathbb{R}$ объединяют рациональные и иррациональные числа. Типы float32, float64, double в программировании приближённо представляют вещественные числа.

Целочисленное переполнение

Целые числа в компьютере ограничены размером типа. Для int32 максимальное значение - $2^{31}-1=2147483647$. При превышении этого значения происходит переполнение, и число “оборачивается” через минимальное значение. Это источник серьёзных багов - именно из-за переполнения int в 2014 году счётчик просмотров видео Gangnam Style на YouTube перестал работать.

Системы счисления

Система счисления определяет, как числа записываются с помощью цифр. В повседневной жизни используется десятичная система с основанием 10. В программировании критически важны ещё три системы.

Двоичная система имеет основание 2 и использует только цифры 0 и 1. Компьютер на самом низком уровне работает именно с двоичными числами, потому что транзистор имеет два состояния - включён и выключен. Число в двоичной системе раскладывается по степеням двойки:

$1011_2=1\cdot 2^3+0\cdot 2^2+1\cdot 2^1+1\cdot 2^0=8+0+2+1=11_{10}$

Восьмеричная система использует основание 8 и цифры от 0 до 7. В современном программировании встречается редко, но используется, например, для задания прав доступа к файлам в Unix-системах. Запись chmod 755 означает: владелец - полные права (7 = 111 в двоичной = rwx), группа - чтение и выполнение (5 = 101 = r-x), остальные - чтение и выполнение (5 = 101 = r-x).

Шестнадцатеричная система использует основание 16 и цифры 0-9, а также буквы A-F для значений 10-15. Это компактная запись двоичных данных - каждая шестнадцатеричная цифра представляет ровно 4 бита. Широко используется для записи цветов в CSS (#FF5733), адресов памяти, MAC-адресов, хешей.

${\text{FF}}_{16}=15\cdot 16^1+15\cdot 16^0=240+15=255_{10}=11111111_2$

Перевод между двоичной и шестнадцатеричной системами делается группами по 4 бита:

Двоичное:   1010 1111 0011 1100
Hex:         A    F    3    C
Результат:  0xAF3C

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

42 в двоичную:
42 ÷ 2 = 21, остаток 0
21 ÷ 2 = 10, остаток 1
10 ÷ 2 = 5,  остаток 0
5  ÷ 2 = 2,  остаток 1
2  ÷ 2 = 1,  остаток 0
1  ÷ 2 = 0,  остаток 1

Читаем снизу вверх: 101010
42₁₀ = 101010₂

Битовые операции

Понимание двоичной системы необходимо для работы с битовыми операциями: AND (&), OR (|), XOR (^), NOT (~), сдвиги (<<, >>). Битовые маски используются для компактного хранения флагов, прав доступа, состояний. Например, права пользователя можно хранить как одно число: READ = 1 (001), WRITE = 2 (010), EXECUTE = 4 (100). Проверка наличия права: if (permissions & READ) != 0.

Модулярная арифметика

Модулярная арифметика работает с остатками от деления. Операция “остаток от деления” записывается как $a\mathrm{mod}n$ или $a\%n$ в большинстве языков программирования. Результат - это остаток от деления $a$ на $n$.

$17\mathrm{mod}5=2\text{(потому что }17=3\cdot 5+2\text{)}$

Два числа называются сравнимыми по модулю $n$, если они дают одинаковый остаток при делении на $n$. Записывается как:

$a\equiv b(\mathrm{mod}n)$

Это означает, что разность $a-b$ делится на $n$.

Основные свойства модулярной арифметики:

$(a+b)\mathrm{mod}n=((a\mathrm{mod}n)+(b\mathrm{mod}n))\mathrm{mod}n$ $(a\cdot b)\mathrm{mod}n=((a\mathrm{mod}n)\cdot (b\mathrm{mod}n))\mathrm{mod}n$

Эти свойства позволяют вычислять остатки для очень больших чисел, не вычисляя сами числа. Например, $2^{100}\mathrm{mod}7$ можно вычислить, последовательно возводя в квадрат и беря остаток на каждом шаге.

Программисты используют модулярную арифметику постоянно:

• Хеш-таблицы: индекс корзины вычисляется как hash(key) % table_size
• Циклические буферы: следующая позиция вычисляется как (current + 1) % buffer_size
• Определение чётности: число чётное, если n % 2 == 0
• Криптография: алгоритм RSA полностью основан на модулярной арифметике
• Генераторы случайных чисел: линейный конгруэнтный метод использует формулу $x_{n+1}=(a\cdot x_n+c)\mathrm{mod}m$

Порядок операций

Математические операции выполняются в определённом порядке приоритетов:

1. Скобки
2. Степени и корни
3. Умножение и деление (слева направо)
4. Сложение и вычитание (слева направо)

В программировании добавляются дополнительные уровни для битовых операций, операций сравнения и логических операций. Порядок различается между языками, поэтому при сомнениях лучше использовать явные скобки.

НОД и НОК

Наибольший общий делитель двух чисел $a$ и $b$ - это наибольшее число, на которое оба числа делятся без остатка. Записывается как $\gcd (a,b)$ или НОД$(a,b)$.

Алгоритм Евклида - один из древнейших алгоритмов в математике и при этом один из самых элегантных. Идея проста: $\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$, а $\gcd (a,0)=a$.

gcd(48, 18):
  gcd(48, 18) → gcd(18, 48 % 18) → gcd(18, 12)
  gcd(18, 12) → gcd(12, 18 % 12) → gcd(12, 6)
  gcd(12, 6)  → gcd(6, 12 % 6)   → gcd(6, 0)
  gcd(6, 0)   → 6

НОД(48, 18) = 6

Наименьшее общее кратное вычисляется через НОД:

$\text{lcm}(a,b)=\frac{|a\cdot b|}{\gcd (a,b)}$

Для примера выше: $\text{lcm}(48,18)=\frac{48\cdot 18}{6}=144$.

Где это используется в программировании:

• Сокращение дробей - делим числитель и знаменатель на их НОД
• Синхронизация периодических задач - НОК определяет период совместного повторения
• Криптография - расширенный алгоритм Евклида применяется в RSA для нахождения модулярного мультипликативного обратного

Числа с плавающей точкой и IEEE 754

Один из самых частых источников недоумения у начинающих программистов - это поведение чисел с плавающей точкой. Попробуйте в любом языке выполнить 0.1 + 0.2, и вы получите 0.30000000000000004 вместо ожидаемого 0.3.

Причина кроется в стандарте IEEE 754, который определяет, как вещественные числа хранятся в памяти компьютера. Число представляется в виде:

$(-1{)}^s\times m\times 2^e$

где $s$ - знаковый бит, $m$ - мантисса, $e$ - экспонента. Для 64-битного числа (double, float64) отводится 1 бит на знак, 11 бит на экспоненту и 52 бита на мантиссу.

Проблема в том, что число 0.1 в двоичной системе является бесконечной периодической дробью - аналогично тому, как $\frac{1}{3}=0.333\dots$ является бесконечной в десятичной. При записи в конечное количество бит происходит округление, и точное значение теряется.

$0.1_{10}=0.0001100110011001100110011{\dots }_2$

Практические последствия:

• Никогда не сравнивайте числа с плавающей точкой через ==. Используйте сравнение с допуском: |a - b| < epsilon
• Для финансовых вычислений используйте целые числа (центы вместо долларов) или специальные типы (Decimal в Python, BigDecimal в Java)
• Порядок операций влияет на точность. Сложение очень маленького числа с очень большим может привести к потере маленького числа
• При накоплении ошибок в циклах суммирования используйте алгоритм Кэхэна

Ключевые понятия раздела

Двоичная и шестнадцатеричная системы счисления - основа работы с данными на низком уровне. Модулярная арифметика лежит в основе хеш-таблиц и криптографии. Алгоритм Евклида для НОД - пример элегантного рекурсивного алгоритма. Числа с плавающей точкой имеют фундаментальное ограничение точности - это нужно учитывать при написании кода.

---

Алгебра

Выражения, уравнения, неравенства

Алгебраическое выражение - это комбинация чисел, переменных и операций: $3x^2+2x-5$. Выражение можно вычислить при подстановке конкретных значений переменных.

Уравнение утверждает равенство двух выражений: $3x+7=22$. Решить уравнение - значит найти значения переменных, при которых равенство выполняется.

Неравенство использует знаки сравнения вместо равенства: $2x+3>11$. Решением неравенства является не одно число, а множество значений.

В программировании эти понятия присутствуют повсюду. Каждое условие if - это проверка неравенства или равенства. Каждое выражение в коде - это алгебраическое выражение. Каждый поиск значения в задаче оптимизации - это решение уравнения.

Линейные уравнения и системы

Линейное уравнение с одной переменной имеет вид $ax+b=0$, его решение тривиально: $x=-\frac{b}{a}$ при $a\ne 0$.

Система линейных уравнений с двумя неизвестными:

$\{\begin{array}{l}{a}_{1}x+b_{1}y=c_1\\ a_{2}x+b_{2}y=c_2\end{array}$

Решается методом подстановки, методом сложения или через определители (формулы Крамера):

$x=\frac{c_1{b}_2-c_2{b}_1}{a_1{b}_2-a_2{b}_1},y=\frac{a_1{c}_2-a_2{c}_1}{a_1{b}_2-a_2{b}_1}$

Знаменатель $a_1{b}_2-a_2{b}_1$ - это определитель матрицы коэффициентов. Если он равен нулю, система либо не имеет решений, либо имеет бесконечно много решений.

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

Где линейные уравнения встречаются в программировании: линейная интерполяция между двумя значениями (анимации, градиенты), вычисление пересечения отрезков, линейная регрессия.

Квадратные уравнения

Квадратное уравнение имеет вид:

$a{x}^2+bx+c=0,a\ne 0$

Дискриминант определяет количество корней:

$D=b^2-4ac$

• Если $D>0$ - два различных вещественных корня
• Если $D=0$ - один корень (два совпадающих)
• Если $D<0$ - нет вещественных корней (два комплексных)

Формула корней:

$x_{1,2}=\frac{-b\pm \sqrt{D}}{2a}$

Квадратные уравнения возникают при расчёте траекторий (баллистика в играх), при нахождении точек пересечения окружностей (геолокация), при оптимизации квадратичных функций.

Формулы сокращённого умножения

Эти тождества полезны для упрощения выражений и быстрых вычислений:

(a + b)^2 &= a^2 + 2ab + b^2 \\ (a - b)^2 &= a^2 - 2ab + b^2 \\ (a + b)(a - b) &= a^2 - b^2 \\ (a + b)^3 &= a^3 + 3a^2b + 3ab^2 + b^3 \\ (a - b)^3 &= a^3 - 3a^2b + 3ab^2 - b^3 \\ a^3 - b^3 &= (a - b)(a^2 + ab + b^2) \\ a^3 + b^3 &= (a + b)(a^2 - ab + b^2) \end{align}$$ В программировании разность квадратов используется, например, для оптимизации: вместо вычисления $(n+1)^2 - n^2$ можно сразу записать $2n + 1$. ### Степени и корни Степень с натуральным показателем - это многократное умножение числа на себя: $$a^n = \underbrace{a \cdot a \cdot \ldots \cdot a}_{n \text{ раз}}$$ Основные свойства степеней: $$\begin{align} a^m \cdot a^n &= a^{m+n} \\ \frac{a^m}{a^n} &= a^{m-n} \\ (a^m)^n &= a^{m \cdot n} \\ (a \cdot b)^n &= a^n \cdot b^n \\ a^0 &= 1 \quad (a \neq 0) \\ a^{-n} &= \frac{1}{a^n} \end{align}$$ Корень $n$-й степени из числа $a$ - это число, которое при возведении в степень $n$ даёт $a$: $$\sqrt[n]{a} = a^{1/n}$$ Степени двойки особенно важны в программировании. Вот ключевые значения, которые стоит помнить: | Степень | Значение | Приблизительно | Применение | |---------|----------|---------------|------------| | $2^{8}$ | 256 | - | Байт, ASCII | | $2^{10}$ | 1024 | ~1 тысяча | Килобайт | | $2^{16}$ | 65 536 | ~65 тысяч | `uint16` | | $2^{20}$ | 1 048 576 | ~1 миллион | Мегабайт | | $2^{30}$ | 1 073 741 824 | ~1 миллиард | Гигабайт | | $2^{32}$ | 4 294 967 296 | ~4 миллиарда | `uint32`, IPv4 | | $2^{64}$ | ~1.8 × 10¹⁹ | - | `uint64` | Быстрое возведение в степень - алгоритм, который вычисляет $a^n$ за $O(\log n)$ умножений вместо $O(n)$. Идея: $a^n = (a^{n/2})^2$ для чётного $n$, и $a^n = a \cdot a^{n-1}$ для нечётного: ``` power(a, n): если n == 0: вернуть 1 если n чётное: half = power(a, n/2) вернуть half * half иначе: вернуть a * power(a, n-1) ``` ### Логарифмы Логарифм - это операция, обратная возведению в степень. Если $a^x = b$, то $x = \log_a b$. Иными словами, логарифм отвечает на вопрос: в какую степень нужно возвести основание, чтобы получить данное число? $$\log_2 8 = 3 \quad \text{потому что } 2^3 = 8$$ $$\log_{10} 1000 = 3 \quad \text{потому что } 10^3 = 1000$$ Основные свойства логарифмов: $$\begin{align} \log_a(x \cdot y) &= \log_a x + \log_a y \\ \log_a\frac{x}{y} &= \log_a x - \log_a y \\ \log_a x^n &= n \cdot \log_a x \\ \log_a a &= 1 \\ \log_a 1 &= 0 \end{align}$$ Формула перехода к другому основанию: $$\log_a b = \frac{\log_c b}{\log_c a}$$ > [!important] Логарифмы и сложность алгоритмов > > Логарифм по основанию 2 - это самая важная функция в анализе алгоритмов. Время работы $O(\log n)$ означает, что при удвоении входных данных время увеличивается всего на одну операцию. Вот почему бинарный поиск так эффективен: в массиве из миллиарда элементов он находит нужный за не более чем 30 шагов, потому что $\log_2(10^9) \approx 30$. Логарифм $\log_2 n$ показывает, сколько раз нужно разделить $n$ пополам, чтобы дойти до 1. Это объясняет, почему он появляется в алгоритмах "разделяй и властвуй": | Алгоритм | Сложность | Почему логарифм | |----------|-----------|----------------| | Бинарный поиск | $O(\log n)$ | Каждый шаг делит массив пополам | | Сортировка слиянием | $O(n \log n)$ | $\log n$ уровней разделения, $n$ операций на каждом | | Сбалансированное дерево | $O(\log n)$ | Высота дерева = $\log n$ | | Быстрая сортировка (в среднем) | $O(n \log n)$ | В среднем $\log n$ уровней рекурсии | В контексте анализа сложности основание логарифма не имеет значения, потому что $\log_a n = \frac{\log_b n}{\log_b a}$, а $\frac{1}{\log_b a}$ - это константа, которая скрывается в O-нотации. Поэтому пишут просто $O(\log n)$ без указания основания. Натуральный логарифм $\ln x = \log_e x$ с основанием $e \approx 2.718$ широко используется в математическом анализе, статистике и машинном обучении. Функция потерь в логистической регрессии основана на натуральном логарифме. ### Последовательности и ряды Арифметическая прогрессия - это последовательность, в которой каждый следующий элемент отличается от предыдущего на одну и ту же величину $d$ (разность): $$a_n = a_1 + (n-1)d$$ Сумма первых $n$ членов: $$S_n = \frac{n(a_1 + a_n)}{2} = \frac{n(2a_1 + (n-1)d)}{2}$$ Классический пример: сумма чисел от 1 до $n$ равна $\frac{n(n+1)}{2}$. Это объясняет, почему два вложенных цикла от 1 до $n$ выполняют $\frac{n(n+1)}{2} \approx \frac{n^2}{2}$ итераций, что даёт сложность $O(n^2)$. ``` // Этот код выполняет n*(n+1)/2 итераций for i in range(n): for j in range(i, n): // операция ``` Геометрическая прогрессия - это последовательность, в которой каждый следующий элемент получается умножением предыдущего на одно и то же число $q$ (знаменатель): $$a_n = a_1 \cdot q^{n-1}$$ Сумма первых $n$ членов: $$S_n = a_1 \cdot \frac{q^n - 1}{q - 1}, \quad q \neq 1$$ Сумма бесконечной убывающей прогрессии (при $|q| < 1$): $$S = \frac{a_1}{1 - q}$$ Геометрическая прогрессия встречается в программировании при анализе алгоритмов с удвоением. Например, динамический массив при каждом расширении удваивает размер. Суммарные затраты на копирование: $1 + 2 + 4 + 8 + \ldots + n = 2n - 1$, что даёт амортизированную стоимость $O(1)$ на вставку. > [!summary] Ключевые понятия раздела > > Логарифмы - фундамент анализа алгоритмической сложности. $\log_2 n$ показывает глубину деления пополам. Арифметическая прогрессия объясняет сложность $O(n^2)$ вложенных циклов. Геометрическая прогрессия объясняет амортизированную стоимость динамических массивов. Степени двойки - базовые константы в программировании. --- ## Геометрия ### Базовые фигуры и формулы Геометрия для программиста - это прежде всего вычисления расстояний, площадей, пересечений и трансформаций. Вот основные формулы, которые пригождаются чаще всего. Прямоугольник со сторонами $a$ и $b$: - Периметр: $P = 2(a + b)$ - Площадь: $S = a \cdot b$ - Диагональ: $d = \sqrt{a^2 + b^2}$ Треугольник со сторонами $a$, $b$, $c$: - Периметр: $P = a + b + c$ - Площадь по высоте: $S = \frac{1}{2} a \cdot h$ - Площадь по формуле Герона: $S = \sqrt{p(p-a)(p-b)(p-c)}$, где $p = \frac{a+b+c}{2}$ - полупериметр - Площадь по координатам вершин $(x_1,y_1), (x_2,y_2), (x_3,y_3)$: $$S = \frac{1}{2} |x_1(y_2 - y_3) + x_2(y_3 - y_1) + x_3(y_1 - y_2)|$$ Окружность радиуса $r$: - Длина окружности: $C = 2\pi r$ - Площадь круга: $S = \pi r^2$ Сфера радиуса $r$: - Площадь поверхности: $S = 4\pi r^2$ - Объём: $V = \frac{4}{3}\pi r^3$ ### Координатная геометрия Расстояние между двумя точками в двумерном пространстве вычисляется по теореме Пифагора: $$d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$$ В трёхмерном пространстве добавляется третья координата: $$d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2 + (z_2 - z_1)^2}$$ Уравнение прямой на плоскости записывается в нескольких формах. Общая форма: $ax + by + c = 0$ Через угловой коэффициент и точку: $y - y_1 = k(x - x_1)$, где $k$ - наклон прямой. Угловой коэффициент двух точек: $k = \frac{y_2 - y_1}{x_2 - x_1}$ Расстояние от точки $(x_0, y_0)$ до прямой $ax + by + c = 0$: $$d = \frac{|ax_0 + by_0 + c|}{\sqrt{a^2 + b^2}}$$ > [!info] Манхэттенское расстояние > > В программировании кроме евклидова расстояния часто используется манхэттенское расстояние: $d = |x_2 - x_1| + |y_2 - y_1|$. Оно подходит для задач, где движение возможно только по сетке (шахматная доска, городские кварталы). Ещё одна важная метрика - расстояние Чебышёва: $d = \max(|x_2 - x_1|, |y_2 - y_1|)$, оно равно минимальному числу ходов короля на шахматной доске. ### Тригонометрия Тригонометрические функции определяют соотношения между сторонами и углами прямоугольного треугольника. Для угла $\alpha$: $$\sin\alpha = \frac{\text{противолежащий катет}}{\text{гипотенуза}}, \quad \cos\alpha = \frac{\text{прилежащий катет}}{\text{гипотенуза}}, \quad \tan\alpha = \frac{\sin\alpha}{\cos\alpha}$$ Основное тригонометрическое тождество: $$\sin^2\alpha + \cos^2\alpha = 1$$ Углы измеряются в градусах или радианах. Полный оборот - это $360°$ или $2\pi$ радиан. Перевод: $$\text{радианы} = \text{градусы} \cdot \frac{\pi}{180}$$ Большинство математических библиотек в языках программирования работают с радианами. Тригонометрические функции описывают периодические процессы. Синусоида $y = A\sin(\omega t + \varphi)$ характеризуется амплитудой $A$, частотой $\omega$ и начальной фазой $\varphi$. Это основа обработки звука и сигналов. Точка на окружности радиуса $r$ с центром в начале координат при угле $\theta$: $$x = r\cos\theta, \quad y = r\sin\theta$$ Эта параметризация окружности используется повсеместно в компьютерной графике и разработке игр: вращение объектов, орбитальное движение, генерация точек на окружности. Функция `atan2(y, x)` - одна из самых полезных тригонометрических функций в программировании. Она вычисляет угол точки $(x, y)$ относительно оси X, правильно обрабатывая все четыре квадранта: $$\theta = \text{atan2}(y, x)$$ Результат лежит в диапазоне $(-\pi, \pi]$. Эту функцию используют для определения направления от одной точки к другой, поворота персонажа к цели в играх, вычисления курса в навигации. ### Полярные координаты В полярных координатах точка задаётся расстоянием от начала координат $r$ и углом $\theta$. Связь с декартовыми координатами: $$x = r\cos\theta, \quad y = r\sin\theta$$ $$r = \sqrt{x^2 + y^2}, \quad \theta = \text{atan2}(y, x)$$ Полярные координаты удобны для описания спиралей, роз и других кривых с радиальной симметрией. В программировании они используются для радарных диаграмм, круговых меню, генерации паттернов. > [!info] Формула гаверсинуса > > Для расчёта расстояния между двумя точками на поверхности Земли (по GPS-координатам) используется формула гаверсинуса, которая учитывает кривизну сферы: > $$d = 2R \arcsin\sqrt{\sin^2\frac{\Delta\varphi}{2} + \cos\varphi_1 \cos\varphi_2 \sin^2\frac{\Delta\lambda}{2}}$$ > где $R$ - радиус Земли (6371 км), $\varphi$ - широта, $\lambda$ - долгота. Это основа геолокационных сервисов. > [!summary] Ключевые понятия раздела > > Расстояние между точками и уравнение прямой - базовые вычислительные операции в графике. Тригонометрические функции нужны для вращений, анимаций и обработки сигналов. Функция `atan2` - рабочая лошадка геометрических вычислений. Формула гаверсинуса - стандартный способ расчёта расстояний по GPS. --- ## Линейная алгебра Линейная алгебра - это язык, на котором говорят машинное обучение, компьютерная графика и многие другие области программирования. Если вы работаете с нейронными сетями, рекомендательными системами или 3D-графикой, линейная алгебра - ваш ежедневный инструмент. ### Векторы Вектор - это упорядоченный набор чисел. В двумерном пространстве вектор $\vec{v} = (v_1, v_2)$, в трёхмерном - $\vec{v} = (v_1, v_2, v_3)$, а в общем случае - $\vec{v} = (v_1, v_2, \ldots, v_n)$, где $n$ - размерность. Геометрически вектор можно представить как стрелку, имеющую направление и длину. В программировании вектор - это просто массив чисел. Операции с векторами: Сложение (поэлементное): $$\vec{a} + \vec{b} = (a_1 + b_1, \ a_2 + b_2, \ \ldots, \ a_n + b_n)$$ Умножение на скаляр: $$c \cdot \vec{a} = (c \cdot a_1, \ c \cdot a_2, \ \ldots, \ c \cdot a_n)$$ Длина (норма) вектора: $$|\vec{v}| = \sqrt{v_1^2 + v_2^2 + \ldots + v_n^2}$$ Нормализация - приведение вектора к единичной длине: $\hat{v} = \frac{\vec{v}}{|\vec{v}|}$. Нормализованный вектор сохраняет направление, но имеет длину 1. Это нужно, когда важно только направление, например, направление движения персонажа. Скалярное произведение: $$\vec{a} \cdot \vec{b} = a_1 b_1 + a_2 b_2 + \ldots + a_n b_n = |\vec{a}||\vec{b}|\cos\theta$$ где $\theta$ - угол между векторами. Скалярное произведение - невероятно полезная операция: - Если результат положительный - угол между векторами острый (менее 90°), векторы "смотрят" примерно в одном направлении - Если результат равен нулю - векторы перпендикулярны - Если результат отрицательный - угол тупой (более 90°), векторы "смотрят" в разные стороны В программировании скалярное произведение используется для вычисления освещения в графике (закон Ламберта), проверки видимости объектов, вычисления косинусного сходства текстов (в NLP и рекомендательных системах). Косинусное сходство - мера похожести двух векторов: $$\text{similarity} = \cos\theta = \frac{\vec{a} \cdot \vec{b}}{|\vec{a}||\vec{b}|}$$ Значение лежит в диапазоне $[-1, 1]$. Значение 1 означает полное совпадение направлений, 0 - ортогональность, -1 - противоположные направления. Это основная метрика в поисковых системах и рекомендательных алгоритмах. Векторное произведение определено только в трёхмерном пространстве: $$\vec{a} \times \vec{b} = (a_2 b_3 - a_3 b_2, \ a_3 b_1 - a_1 b_3, \ a_1 b_2 - a_2 b_1)$$ Результат - вектор, перпендикулярный обоим исходным. Длина равна $|\vec{a}||\vec{b}|\sin\theta$, что равно площади параллелограмма, построенного на этих векторах. В 3D-графике векторное произведение используется для вычисления нормалей к поверхности. ### Матрицы Матрица - это прямоугольная таблица чисел. Матрица размера $m \times n$ имеет $m$ строк и $n$ столбцов: $$A = \begin{pmatrix} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} \end{pmatrix}$$ Операции с матрицами: Сложение (поэлементное, только для матриц одинакового размера): $$(A + B)_{ij} = a_{ij} + b_{ij}$$ Умножение матрицы на скаляр: $$(cA)_{ij} = c \cdot a_{ij}$$ Умножение матриц - ключевая операция. Матрицу $A$ размера $m \times k$ можно умножить на матрицу $B$ размера $k \times n$. Результат - матрица $C$ размера $m \times n$: $$C_{ij} = \sum_{p=1}^{k} a_{ip} \cdot b_{pj}$$ Каждый элемент результата - это скалярное произведение строки первой матрицы на столбец второй. Умножение матриц не коммутативно: $AB \neq BA$ в общем случае. Алгоритмическая сложность наивного умножения матриц - $O(n^3)$. Алгоритм Штрассена снижает её до $O(n^{2.807})$. В ML-фреймворках умножение матриц выполняется на GPU параллельно, что ускоряет вычисления на порядки. Транспонирование матрицы - замена строк на столбцы: $$(A^T)_{ij} = A_{ji}$$ Единичная матрица $I$ - квадратная матрица с единицами на диагонали и нулями вне её. Она играет роль "единицы" для умножения матриц: $AI = IA = A$. $$I = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$$ Определитель квадратной матрицы - число, характеризующее матрицу. Для матрицы $2 \times 2$: $$\det\begin{pmatrix} a & b \\ c & d \end{pmatrix} = ad - bc$$ Для матрицы $3 \times 3$ используется разложение по строке (правило Сарруса или формула Лейбница). Определитель равен нулю тогда и только тогда, когда матрица вырождена, то есть строки линейно зависимы. Обратная матрица $A^{-1}$ существует только для квадратных матриц с ненулевым определителем: $$A \cdot A^{-1} = A^{-1} \cdot A = I$$ Для матрицы $2 \times 2$: $$A^{-1} = \frac{1}{ad - bc}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$$ > [!important] Матрицы трансформации в графике > > В компьютерной графике матрицы используются для трансформаций: перемещения, вращения, масштабирования. Каждая трансформация - это умножение координат точки на матрицу. Несколько трансформаций можно объединить в одну, перемножив их матрицы. Матрица вращения на угол $\theta$ в 2D: > $$R = \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix}$$ ### Системы линейных уравнений и метод Гаусса Система линейных уравнений: $$\begin{cases} a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n = b_1 \\ a_{21}x_1 + a_{22}x_2 + \ldots + a_{2n}x_n = b_2 \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \ldots + a_{mn}x_n = b_m \end{cases}$$ В матричной форме: $Ax = b$, где $A$ - матрица коэффициентов, $x$ - вектор неизвестных, $b$ - вектор правых частей. Метод Гаусса (метод исключения переменных) - стандартный алгоритм решения таких систем. Он состоит из двух фаз: Прямой ход - приведение к верхнетреугольному виду путём вычитания строк: $$\begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} \rightarrow \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ 0 & a'_{22} & a'_{23} \\ 0 & 0 & a''_{33} \end{pmatrix}$$ Обратный ход - последовательное нахождение неизвестных, начиная с последнего. Сложность метода Гаусса - $O(n^3)$. ### Собственные значения и собственные векторы Собственный вектор матрицы $A$ - это ненулевой вектор $\vec{v}$, который при умножении на матрицу меняет только свою длину, но не направление: $$A\vec{v} = \lambda\vec{v}$$ где $\lambda$ - собственное значение. Для нахождения собственных значений решается характеристическое уравнение: $$\det(A - \lambda I) = 0$$ Собственные значения и векторы имеют важные применения в программировании: - PageRank - алгоритм Google ранжирования веб-страниц основан на нахождении собственного вектора матрицы ссылок - PCA (метод главных компонент) - снижение размерности данных через собственные векторы ковариационной матрицы - Анализ устойчивости - собственные значения определяют, будет ли динамическая система устойчивой - Вибрационный анализ - собственные частоты механических систем > [!summary] Ключевые понятия раздела > > Векторы и операции с ними - основа ML и графики. Скалярное произведение измеряет "похожесть" направлений. Умножение матриц - центральная операция нейронных сетей. Матрицы трансформации управляют графикой. PageRank и PCA основаны на собственных значениях. --- ## Математический анализ Математический анализ изучает непрерывные изменения. Для программиста он важен прежде всего в контексте машинного обучения, оптимизации и физических симуляций. ### Пределы и непрерывность Предел функции в точке $a$ - это значение, к которому стремится функция при приближении аргумента к $a$: $$\lim_{x \to a} f(x) = L$$ Это означает, что значения $f(x)$ можно сделать сколь угодно близкими к $L$, взяв $x$ достаточно близким к $a$. Ключевые пределы: $$\lim_{x \to 0} \frac{\sin x}{x} = 1$$ $$\lim_{x \to \infty} \left(1 + \frac{1}{x}\right)^x = e \approx 2.71828$$ $$\lim_{x \to 0} \frac{e^x - 1}{x} = 1$$ Функция непрерывна в точке $a$, если предел в этой точке существует и равен значению функции: $\lim_{x \to a} f(x) = f(a)$. Для программиста понятие предела важно при анализе асимптотического поведения алгоритмов. Когда мы говорим, что сложность алгоритма - $O(n^2)$, мы фактически описываем поведение функции времени при $n \to \infty$. ### Производная Производная функции в точке - это мгновенная скорость изменения функции. Геометрически это наклон касательной к графику функции: $$f'(x) = \lim_{\Delta x \to 0} \frac{f(x + \Delta x) - f(x)}{\Delta x}$$ Производная отвечает на вопрос: как быстро и в каком направлении меняется функция в данной точке. Если производная положительная - функция растёт, если отрицательная - убывает, если равна нулю - это потенциальная точка экстремума. Основные правила дифференцирования: $$\begin{align} (c)' &= 0 \\ (x^n)' &= nx^{n-1} \\ (e^x)' &= e^x \\ (\ln x)' &= \frac{1}{x} \\ (\sin x)' &= \cos x \\ (\cos x)' &= -\sin x \end{align}$$ Правила для комбинаций функций: $$\begin{align} (f + g)' &= f' + g' \\ (f \cdot g)' &= f'g + fg' \\ \left(\frac{f}{g}\right)' &= \frac{f'g - fg'}{g^2} \\ (f(g(x)))' &= f'(g(x)) \cdot g'(x) \quad \text{(цепное правило)} \end{align}$$ > [!important] Градиентный спуск > > Производная - это основа градиентного спуска, главного алгоритма оптимизации в машинном обучении. Идея проста: чтобы найти минимум функции, двигайся в направлении, противоположном производной. Если производная положительная - функция растёт, значит, нужно двигаться влево. Если отрицательная - функция убывает, значит, двигаться вправо. > > Формула обновления параметра: > $$\theta_{\text{new}} = \theta_{\text{old}} - \alpha \cdot f'(\theta_{\text{old}})$$ > где $\alpha$ - скорость обучения (learning rate). Частная производная - это производная функции нескольких переменных по одной из них, при фиксированных остальных. Для функции $f(x, y)$: $$\frac{\partial f}{\partial x} \quad \text{- производная по } x \text{ при фиксированном } y$$ Градиент - вектор всех частных производных: $$\nabla f = \left(\frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}, \ldots, \frac{\partial f}{\partial x_n}\right)$$ Градиент указывает направление наибыстрейшего роста функции. Это центральное понятие для обучения нейронных сетей. Алгоритм обратного распространения ошибки (backpropagation) - это по сути цепное правило дифференцирования, применённое к вычислительному графу нейронной сети. ### Интегралы Интеграл - операция, обратная дифференцированию. Геометрически определённый интеграл - это площадь под графиком функции: $$\int_a^b f(x)\,dx = F(b) - F(a)$$ где $F(x)$ - первообразная, то есть функция, производная которой равна $f(x)$: $F'(x) = f(x)$. Основные интегралы: $$\begin{align} \int x^n\,dx &= \frac{x^{n+1}}{n+1} + C, \quad n \neq -1 \\ \int \frac{1}{x}\,dx &= \ln|x| + C \\ \int e^x\,dx &= e^x + C \\ \int \sin x\,dx &= -\cos x + C \\ \int \cos x\,dx &= \sin x + C \end{align}$$ В программировании интегралы используются для: - Вычисления площадей неправильных фигур - Расчёта вероятностей для непрерывных распределений (площадь под кривой плотности) - Физических симуляций (скорость - интеграл ускорения, положение - интеграл скорости) - Метрики AUC-ROC в ML - это буквально площадь под ROC-кривой Часто аналитическое вычисление интеграла невозможно, и тогда используются численные методы: метод прямоугольников, метод трапеций, метод Симпсона. ### Ряды Тейлора Ряд Тейлора позволяет представить функцию в виде бесконечной суммы степеней: $$f(x) = \sum_{n=0}^{\infty} \frac{f^{(n)}(a)}{n!}(x-a)^n = f(a) + f'(a)(x-a) + \frac{f''(a)}{2!}(x-a)^2 + \ldots$$ При $a = 0$ это ряд Маклорена: $$e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \ldots$$ $$\sin x = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \ldots$$ $$\cos x = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \ldots$$ $$\ln(1+x) = x - \frac{x^2}{2} + \frac{x^3}{3} - \ldots, \quad |x| \leq 1$$ Ряды Тейлора - это то, как компьютер вычисляет тригонометрические и экспоненциальные функции. Процессор использует полиномиальные приближения, чтобы получить значение $\sin(0.5)$ за несколько арифметических операций. Точность определяется количеством членов ряда. В машинном обучении линейное приближение Тейлора (первые два члена) используется для аппроксимации сложных функций потерь в окрестности текущей точки. > [!summary] Ключевые понятия раздела > > Производная - скорость изменения, основа градиентного спуска в ML. Градиент - обобщение производной на многомерный случай. Цепное правило - основа backpropagation. Интеграл - площадь под кривой, используется для вычисления вероятностей и метрик. Ряды Тейлора - способ вычисления функций через полиномы. --- ## Дискретная математика Дискретная математика - самая важная область математики для программиста. Она изучает объекты, которые можно перечислить: целые числа, графы, логические выражения, конечные множества. Практически все структуры данных и алгоритмы основаны на дискретной математике. ### Множества Множество - это неупорядоченная коллекция уникальных элементов. В программировании множество реализовано как `Set` (JavaScript, Python, Java, Go). Записывается множество перечислением элементов: $A = \{1, 2, 3, 4, 5\}$ или описанием свойства: $A = \{x \in \mathbb{N} \mid x < 6\}$ (все натуральные числа меньше 6). Принадлежность элемента множеству: $3 \in A$ (3 принадлежит A), $7 \notin A$ (7 не принадлежит A). Подмножество: $B \subseteq A$, если каждый элемент $B$ также принадлежит $A$. Операции над множествами: Объединение $A \cup B$ - все элементы, которые есть хотя бы в одном из множеств: $$A \cup B = \{x \mid x \in A \text{ или } x \in B\}$$ Пересечение $A \cap B$ - элементы, которые есть в обоих множествах: $$A \cap B = \{x \mid x \in A \text{ и } x \in B\}$$ Разность $A \setminus B$ - элементы, которые есть в $A$, но нет в $B$: $$A \setminus B = \{x \mid x \in A \text{ и } x \notin B\}$$ Симметрическая разность $A \triangle B$ - элементы, которые есть только в одном из множеств: $$A \triangle B = (A \setminus B) \cup (B \setminus A)$$ Дополнение $\overline{A}$ - все элементы универсального множества, не принадлежащие $A$. Мощность множества $|A|$ - количество элементов. Для конечных множеств действует формула включений-исключений: $$|A \cup B| = |A| + |B| - |A \cap B|$$ Для трёх множеств: $$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$ > [!info] Множества в SQL > > Операции над множествами напрямую соответствуют операциям SQL: объединение - `UNION`, пересечение - `INTERSECT`, разность - `EXCEPT`. Типы JOIN в SQL тоже описываются через операции множеств: `INNER JOIN` - пересечение, `LEFT JOIN` - все элементы левого множества с расширением из правого. Декартово произведение $A \times B$ - множество всех упорядоченных пар $(a, b)$, где $a \in A$, $b \in B$: $$\{1, 2\} \times \{a, b\} = \{(1,a), (1,b), (2,a), (2,b)\}$$ Мощность декартова произведения: $|A \times B| = |A| \cdot |B|$. В SQL операция `CROSS JOIN` даёт декартово произведение таблиц. ### Логика Математическая логика - это фундамент программирования. Каждое условие `if`, каждый цикл `while`, каждый запрос `WHERE` в SQL - это логическое выражение. Логическое высказывание - это утверждение, которое может быть либо истинным (true, 1), либо ложным (false, 0). Основные логические операции: Отрицание (NOT, $\neg$) - инвертирует значение: | $A$ | $\neg A$ | |-----|----------| | 0 | 1 | | 1 | 0 | Конъюнкция (AND, $\wedge$) - истинна, когда оба операнда истинны: | $A$ | $B$ | $A \wedge B$ | |-----|-----|-------------| | 0 | 0 | 0 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 1 | Дизъюнкция (OR, $\vee$) - истинна, когда хотя бы один операнд истинен: | $A$ | $B$ | $A \vee B$ | |-----|-----|-----------| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 1 | Исключающее ИЛИ (XOR, $\oplus$) - истинно, когда операнды различны: | $A$ | $B$ | $A \oplus B$ | |-----|-----|-------------| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | XOR обладает уникальным свойством: $A \oplus A = 0$ и $A \oplus 0 = A$. Это используется в криптографии (одноразовый блокнот), для обмена значений переменных без третьей переменной, для нахождения единственного непарного числа в массиве. Импликация ($A \Rightarrow B$, "если A, то B") - ложна только когда посылка истинна, а заключение ложно: | $A$ | $B$ | $A \Rightarrow B$ | |-----|-----|-------------------| | 0 | 0 | 1 | | 0 | 1 | 1 | | 1 | 0 | 0 | | 1 | 1 | 1 | Импликация контринтуитивна: "если ложь, то что угодно" - это истина. Это важно при работе с формальной верификацией и типами. Эквивалентность ($A \Leftrightarrow B$) - истинна, когда оба операнда имеют одинаковое значение. Основные законы логики: $$\begin{align} \neg(\neg A) &= A & \text{(двойное отрицание)} \\ A \wedge (B \vee C) &= (A \wedge B) \vee (A \wedge C) & \text{(дистрибутивность)} \\ A \vee (B \wedge C) &= (A \vee B) \wedge (A \vee C) & \text{(дистрибутивность)} \\ \neg(A \wedge B) &= \neg A \vee \neg B & \text{(закон де Моргана)} \\ \neg(A \vee B) &= \neg A \wedge \neg B & \text{(закон де Моргана)} \end{align}$$ > [!important] Законы де Моргана в коде > > Законы де Моргана крайне полезны при рефакторинге условий. Например, `!(a && b)` эквивалентно `!a || !b`, а `!(a || b)` эквивалентно `!a && !b`. Это позволяет упрощать сложные вложенные условия и делать код читаемее. ### Булева алгебра Булева алгебра - это алгебра, работающая с двумя значениями: 0 и 1. Она является математической основой цифровых схем и логики программирования. В цифровых схемах логические операции реализуются элементами (gates): AND, OR, NOT, NAND, NOR, XOR. Интересный факт: элемент NAND (NOT AND) является функционально полным - с помощью только NAND можно реализовать любую логическую функцию. Аналогично для NOR. Минимизация логических функций - важная задача проектирования схем. Карты Карно и метод Квайна-МакКласки позволяют найти минимальное выражение для логической функции. В программировании аналогичная задача - упрощение сложных условий. ### Комбинаторика Комбинаторика отвечает на вопрос "сколько существует вариантов?". Это важно для оценки размера пространства поиска, вычисления вероятностей и понимания сложности задач. Правило произведения: если первый выбор можно сделать $m$ способами, а второй - $n$ способами, то общее число комбинаций равно $m \cdot n$. Правило суммы: если первый вариант возможен $m$ способами, а второй (несовместимый) - $n$ способами, то общее число вариантов равно $m + n$. Факториал - произведение всех натуральных чисел от 1 до $n$: $$n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n$$ По определению $0! = 1$. Факториал растёт невероятно быстро: $10! = 3\,628\,800$, $20! \approx 2.4 \times 10^{18}$. Это объясняет, почему полный перебор всех перестановок непрактичен уже для 20 элементов. Перестановки - количество способов расположить $n$ элементов в ряд: $$P_n = n!$$ Размещения - количество способов выбрать и расположить $k$ элементов из $n$: $$A_n^k = \frac{n!}{(n-k)!}$$ Сочетания - количество способов выбрать $k$ элементов из $n$ без учёта порядка: $$C_n^k = \binom{n}{k} = \frac{n!}{k!(n-k)!}$$ Сочетания обладают симметрией: $C_n^k = C_n^{n-k}$. Это логично - выбрать $k$ элементов из $n$ - это то же, что выбрать $n-k$ элементов, которые не войдут в выборку. Бином Ньютона связывает сочетания и степени: $$(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$$ Комбинаторика в программировании: - Оценка сложности: задача коммивояжёра для $n$ городов имеет $(n-1)!/2$ маршрутов - поэтому полный перебор невозможен уже для 20 городов - Генерация паролей: пароль из 8 символов (буквы + цифры + спецсимволы) - $72^8 \approx 7.2 \times 10^{14}$ вариантов - Хеш-коллизии: вероятность коллизии хешей связана с задачей о днях рождения (combinatorial argument) - Количество подмножеств: множество из $n$ элементов имеет $2^n$ подмножеств - это объясняет, почему задача о рюкзаке сложна ### Принцип Дирихле Принцип Дирихле (pigeonhole principle) утверждает: если $n$ предметов разместить в $m$ ячеек и $n > m$, то хотя бы в одной ячейке окажется более одного предмета. Звучит тривиально, но следствия мощные: - Хеш-коллизии неизбежны. Если хеш-функция выдаёт 32-битное значение ($2^{32}$ возможных хешей), а входных значений больше $2^{32}$, коллизии гарантированы. Это фундаментальный факт, определяющий дизайн хеш-таблиц - Сжатие без потерь не может уменьшить все файлы. Если алгоритм сжатия уменьшает файлы длины $n$ бит, он отображает $2^n$ входов в менее чем $2^n$ выходов, значит, некоторые входы должны отображаться в один выход - В любой группе из 13 человек как минимум двое родились в одном месяце Обобщённый принцип Дирихле: если $n$ предметов разместить в $m$ ячеек, то хотя бы в одной ячейке окажется не менее $\lceil n/m \rceil$ предметов. ### Теория графов Граф - одна из самых универсальных математических структур в компьютерных науках. Граф $G = (V, E)$ состоит из множества вершин $V$ и множества рёбер $E$, где каждое ребро соединяет две вершины. Виды графов: - Неориентированный граф - рёбра не имеют направления. Если есть ребро между $A$ и $B$, можно пройти в обе стороны. Пример: дружба в соцсети - Ориентированный граф (орграф) - рёбра имеют направление. Ребро из $A$ в $B$ не означает ребро из $B$ в $A$. Пример: подписки в Twitter, ссылки между веб-страницами - Взвешенный граф - каждому ребру присвоен вес (число). Пример: дорожная сеть с расстояниями между городами - Дерево - связный граф без циклов. Дерево с $n$ вершинами имеет ровно $n-1$ ребро - DAG (directed acyclic graph) - ориентированный граф без циклов. Используется для зависимостей задач, расписаний, компиляции Степень вершины - количество рёбер, инцидентных вершине. В ориентированном графе различают входящую и исходящую степени. Сумма степеней всех вершин равна удвоенному числу рёбер (лемма о рукопожатиях): $$\sum_{v \in V} \deg(v) = 2|E|$$ Представления графов в памяти: Матрица смежности - двумерный массив $n \times n$, где элемент $[i][j]$ равен 1, если есть ребро из $i$ в $j$, и 0 иначе. Занимает $O(n^2)$ памяти. Подходит для плотных графов, позволяет за $O(1)$ проверить наличие ребра. Список смежности - для каждой вершины хранится список её соседей. Занимает $O(n + m)$ памяти, где $m$ - количество рёбер. Подходит для разреженных графов. В большинстве задач именно это представление оптимально. Обходы графов: BFS (поиск в ширину) - обходит граф "волной", сначала посещая всех соседей текущей вершины, потом соседей соседей. Использует очередь. Находит кратчайший путь в невзвешенном графе. ``` BFS(start): queue = [start] visited = {start} while queue не пуста: v = queue.dequeue() для каждого соседа u вершины v: если u не в visited: visited.add(u) queue.enqueue(u) ``` Сложность BFS: $O(V + E)$. DFS (поиск в глубину) - идёт "вглубь" графа, пока не упрётся в тупик, затем возвращается. Использует стек (или рекурсию). Применяется для поиска компонент связности, топологической сортировки, обнаружения циклов. ``` DFS(v): visited.add(v) для каждого соседа u вершины v: если u не в visited: DFS(u) ``` Сложность DFS: $O(V + E)$. Кратчайшие пути: Алгоритм Дейкстры находит кратчайшие пути от одной вершины до всех остальных во взвешенном графе с неотрицательными весами. Использует приоритетную очередь. Сложность - $O((V + E) \log V)$ с бинарной кучей. Алгоритм Беллмана-Форда работает с отрицательными весами (но без отрицательных циклов). Сложность - $O(VE)$. Алгоритм Флойда-Уоршелла находит кратчайшие пути между всеми парами вершин. Сложность - $O(V^3)$. Топологическая сортировка - линейный порядок вершин ориентированного ациклического графа (DAG) такой, что для каждого ребра $(u, v)$ вершина $u$ идёт перед $v$. Используется для: - Порядка компиляции модулей (зависимости) - Планирования задач с зависимостями - Порядка инициализации компонентов - Разрешения зависимостей пакетов (npm, pip) Минимальное остовное дерево - подграф, соединяющий все вершины с минимальной суммой весов рёбер. Алгоритмы Прима и Крускала решают эту задачу. Применение: проектирование сетей, кластеризация. > [!info] Графы повсюду в программировании > > Социальные сети - граф пользователей и связей. Интернет - граф веб-страниц и ссылок. Файловая система - дерево. Маршрутизация - взвешенный граф сетевых узлов. Системы зависимостей (npm, pip) - DAG. Компилятор - AST (абстрактное синтаксическое дерево). Базы данных - графовые модели (Neo4j). Карты и навигация - взвешенные графы дорог. ### Рекуррентные соотношения Рекуррентное соотношение определяет элемент последовательности через предыдущие элементы. Это математическая модель рекурсии. Числа Фибоначчи - классический пример: $$F_n = F_{n-1} + F_{n-2}, \quad F_0 = 0, \quad F_1 = 1$$ Последовательность: $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots$ Наивная рекурсивная реализация имеет экспоненциальную сложность $O(2^n)$, потому что многократно вычисляет одни и те же значения. Мемоизация (запоминание вычисленных значений) снижает сложность до $O(n)$ - это суть динамического программирования. Рекуррентные соотношения важны для анализа алгоритмов "разделяй и властвуй". Основная теорема (master theorem) позволяет определить сложность алгоритма по его рекуррентному соотношению. Для соотношения вида: $$T(n) = aT\left(\frac{n}{b}\right) + O(n^c)$$ где $a$ - количество подзадач, $b$ - во сколько раз уменьшается размер, $c$ - степень работы на каждом уровне: - Если $\log_b a < c$, то $T(n) = O(n^c)$ - Если $\log_b a = c$, то $T(n) = O(n^c \log n)$ - Если $\log_b a > c$, то $T(n) = O(n^{\log_b a})$ Примеры: | Алгоритм | Рекуррентность | $a$ | $b$ | $c$ | Сложность | |----------|---------------|-----|-----|-----|-----------| | Бинарный поиск | $T(n) = T(n/2) + O(1)$ | 1 | 2 | 0 | $O(\log n)$ | | Сортировка слиянием | $T(n) = 2T(n/2) + O(n)$ | 2 | 2 | 1 | $O(n\log n)$ | | Алгоритм Штрассена | $T(n) = 7T(n/2) + O(n^2)$ | 7 | 2 | 2 | $O(n^{2.807})$ | ### Конечные автоматы и регулярные выражения Конечный автомат (finite automaton) - это математическая модель вычисления с конечным числом состояний. Автомат читает входную строку символ за символом и переходит между состояниями по определённым правилам. Детерминированный конечный автомат (DFA) определяется пятёркой $(Q, \Sigma, \delta, q_0, F)$: - $Q$ - конечное множество состояний - $\Sigma$ - алфавит (множество входных символов) - $\delta: Q \times \Sigma \to Q$ - функция переходов - $q_0 \in Q$ - начальное состояние - $F \subseteq Q$ - множество допускающих состояний Пример: автомат, распознающий двоичные числа, кратные 3. Состояния: $\{q_0, q_1, q_2\}$, где $q_i$ означает, что остаток от деления текущего числа на 3 равен $i$. Начальное состояние $q_0$ (ноль кратен трём). Допускающее состояние - $q_0$. Переходы: при чтении бита $b$ текущее число удваивается и прибавляется $b$, поэтому новый остаток - $(2r + b) \mod 3$, где $r$ - текущий остаток. Недетерминированный конечный автомат (NFA) допускает несколько возможных переходов из одного состояния по одному символу и $\varepsilon$-переходы (без чтения символа). Любой NFA можно преобразовать в эквивалентный DFA, но количество состояний может экспоненциально вырасти. Регулярные выражения и конечные автоматы эквивалентны по выразительной силе: любое регулярное выражение можно преобразовать в NFA (конструкция Томпсона), а любой автомат описывается регулярным выражением. Это теоретическая основа, на которой построены движки регулярных выражений в языках программирования. > [!info] Ограничения регулярных выражений > > Конечные автоматы (и, следовательно, регулярные выражения) не могут распознать языки, требующие подсчёта - например, правильные скобочные последовательности. Нельзя написать регулярное выражение, проверяющее, что в строке одинаковое количество открывающих и закрывающих скобок. Для этого нужны более мощные модели - автоматы с магазинной памятью (контекстно-свободные грамматики), которые используются в парсерах языков программирования. ### Формальные языки и грамматики Иерархия Хомского классифицирует формальные языки по сложности: | Тип | Название | Автомат | Пример | |-----|----------|---------|--------| | 3 | Регулярные | Конечный автомат | `[a-z]+@[a-z]+\\.com` | | 2 | Контекстно-свободные | Автомат с магазинной памятью | Правильные скобочные последовательности | | 1 | Контекстно-зависимые | Линейно ограниченный автомат | Языки программирования (частично) | | 0 | Рекурсивно перечислимые | Машина Тьюринга | Произвольные программы | Парсеры языков программирования используют контекстно-свободные грамматики. Лексический анализ (разбиение на токены) основан на регулярных выражениях, а синтаксический анализ - на контекстно-свободных грамматиках. > [!summary] Ключевые понятия раздела > > Множества и их операции - основа SQL и коллекций. Логика и булева алгебра - фундамент условий и цифровых схем. Законы де Моргана упрощают сложные условия. Комбинаторика оценивает размер пространства поиска. Принцип Дирихле доказывает неизбежность хеш-коллизий. Графы моделируют связи между объектами. Рекуррентные соотношения и master theorem анализируют рекурсивные алгоритмы. Конечные автоматы - теоретическая основа регулярных выражений. --- ## Теория вероятностей Теория вероятностей - это математика неопределённости. Программисты сталкиваются с ней при проектировании A/B тестов, анализе распределения нагрузки, оценке вероятности сбоев, работе с рандомизированными алгоритмами и машинном обучении. ### Основные определения Случайный эксперимент - это действие с неопределённым исходом. Подбрасывание монеты, запрос к серверу, клик пользователя. Пространство элементарных событий $\Omega$ - множество всех возможных исходов. Для монеты: $\Omega = \{\text{орёл}, \text{решка}\}$. Для игрального кубика: $\Omega = \{1, 2, 3, 4, 5, 6\}$. Событие $A$ - подмножество пространства элементарных событий. Событие "выпало чётное число" на кубике: $A = \{2, 4, 6\}$. Вероятность события $P(A)$ для равновероятных исходов: $$P(A) = \frac{|A|}{|\Omega|} = \frac{\text{число благоприятных исходов}}{\text{общее число исходов}}$$ Свойства вероятности: - $0 \leq P(A) \leq 1$ для любого события $A$ - $P(\Omega) = 1$ (что-то обязательно произойдёт) - $P(\emptyset) = 0$ (невозможное событие) - $P(\overline{A}) = 1 - P(A)$ (вероятность противоположного события) Формула сложения вероятностей: $$P(A \cup B) = P(A) + P(B) - P(A \cap B)$$ Для несовместных событий (которые не могут произойти одновременно): $$P(A \cup B) = P(A) + P(B)$$ ### Условная вероятность и формула Байеса Условная вероятность - вероятность события $A$ при условии, что произошло событие $B$: $$P(A|B) = \frac{P(A \cap B)}{P(B)}$$ Пример: в базе данных 60% пользователей - мужчины, 40% - женщины. Среди мужчин 30% купили товар, среди женщин - 50%. Какова вероятность, что купивший товар - женщина? Формула Байеса позволяет "развернуть" условную вероятность: $$P(A|B) = \frac{P(B|A) \cdot P(A)}{P(B)}$$ Разберём пример. Обозначим $Ж$ - пользователь женщина, $К$ - пользователь купил товар. Известно: $P(Ж) = 0.4$, $P(М) = 0.6$, $P(К|М) = 0.3$, $P(К|Ж) = 0.5$. Вероятность покупки (полная вероятность): $$P(К) = P(К|М) \cdot P(М) + P(К|Ж) \cdot P(Ж) = 0.3 \cdot 0.6 + 0.5 \cdot 0.4 = 0.38$$ Вероятность, что покупатель - женщина: $$P(Ж|К) = \frac{P(К|Ж) \cdot P(Ж)}{P(К)} = \frac{0.5 \cdot 0.4}{0.38} \approx 0.526$$ > [!important] Теорема Байеса в программировании > > Наивный байесовский классификатор - один из простейших, но эффективных алгоритмов ML. Он применяет теорему Байеса для классификации текста (спам-фильтры), документов, медицинской диагностики. Также байесовский подход используется в A/B тестировании для непрерывного обновления оценки вероятности успеха варианта. ### Независимые события Два события $A$ и $B$ независимы, если наступление одного не влияет на вероятность другого: $$P(A \cap B) = P(A) \cdot P(B)$$ Эквивалентно: $P(A|B) = P(A)$. Пример из SRE: если вероятность отказа одного сервера - $0.01$, а серверы независимы, то вероятность отказа обоих из двух серверов: $$P(\text{оба отказали}) = 0.01 \times 0.01 = 0.0001$$ Вероятность, что хотя бы один работает: $$P(\text{хотя бы один работает}) = 1 - 0.0001 = 0.9999$$ Это основа резервирования. Три независимых сервера: вероятность полного отказа $0.01^3 = 0.000001$. Каждый добавленный сервер уменьшает вероятность простоя на два порядка. ### Математическое ожидание и дисперсия Математическое ожидание (среднее значение) случайной величины $X$ - это взвешенное среднее всех возможных значений: $$E[X] = \sum_{i} x_i \cdot P(X = x_i)$$ Для непрерывной случайной величины: $$E[X] = \int_{-\infty}^{+\infty} x \cdot f(x)\,dx$$ Свойства: - $E[aX + b] = aE[X] + b$ - $E[X + Y] = E[X] + E[Y]$ (линейность, даже для зависимых величин) Пример: среднее время ответа сервера. Если 80% запросов обрабатываются за 10мс и 20% за 50мс, то среднее время: $$E[T] = 0.8 \cdot 10 + 0.2 \cdot 50 = 8 + 10 = 18 \text{ мс}$$ Дисперсия измеряет разброс значений вокруг среднего: $$D[X] = E[(X - E[X])^2] = E[X^2] - (E[X])^2$$ Стандартное отклонение - квадратный корень из дисперсии: $\sigma = \sqrt{D[X]}$. Стандартное отклонение имеет ту же размерность, что и исходная величина, поэтому оно удобнее для интерпретации. Для мониторинга систем: если среднее время ответа 18мс, а стандартное отклонение 5мс, то значение 35мс отклоняется на $(35-18)/5 = 3.4$ стандартных отклонения - это аномалия, требующая внимания. ### Распределения Распределение описывает, как вероятность распределена по возможным значениям. Равномерное распределение - все значения равновероятны. Для дискретного случая с $n$ значениями: $P(X = x_i) = \frac{1}{n}$. Генераторы случайных чисел обычно выдают равномерно распределённые значения. Распределение Бернулли - одно испытание с двумя исходами (успех/неудача). Параметр $p$ - вероятность успеха: $$P(X = 1) = p, \quad P(X = 0) = 1 - p$$ $$E[X] = p, \quad D[X] = p(1-p)$$ Пример: один клик пользователя - конверсия или нет. Биномиальное распределение - количество успехов в $n$ независимых испытаниях Бернулли: $$P(X = k) = \binom{n}{k} p^k (1-p)^{n-k}$$ $$E[X] = np, \quad D[X] = np(1-p)$$ Пример: из 1000 пользователей с конверсией 3%, сколько совершат покупку? В среднем $1000 \times 0.03 = 30$. Распределение Пуассона моделирует число событий за фиксированный интервал, когда события происходят независимо с постоянной средней интенсивностью $\lambda$: $$P(X = k) = \frac{\lambda^k e^{-\lambda}}{k!}$$ $$E[X] = \lambda, \quad D[X] = \lambda$$ Примеры: количество запросов к серверу за секунду, количество ошибок в коде на 1000 строк, количество писем в минуту. Нормальное распределение (гауссово) - "колокольная кривая". Определяется средним $\mu$ и стандартным отклонением $\sigma$: $$f(x) = \frac{1}{\sigma\sqrt{2\pi}} e^{-\frac{(x-\mu)^2}{2\sigma^2}}$$ Правило трёх сигм: примерно 68% значений лежат в пределах $\mu \pm \sigma$, 95% - в пределах $\mu \pm 2\sigma$, 99.7% - в пределах $\mu \pm 3\sigma$. Нормальное распределение возникает повсюду благодаря центральной предельной теореме: сумма большого числа независимых случайных величин распределена приблизительно нормально, независимо от распределения слагаемых. > [!info] Задача о днях рождения > > Какова вероятность, что в группе из $n$ человек хотя бы у двоих совпадут дни рождения? Интуитивно кажется, что нужно много людей. Но уже при $n = 23$ вероятность превышает 50%, а при $n = 70$ - 99.9%. Эта задача напрямую связана с хеш-коллизиями: для хеша длиной $b$ бит первая коллизия ожидается после примерно $2^{b/2}$ значений. Для 64-битного хеша это $2^{32} \approx 4 \times 10^9$ значений. ### Закон больших чисел Закон больших чисел утверждает: среднее арифметическое большой выборки сходится к математическому ожиданию. Чем больше выборка, тем точнее оценка. Формально: если $X_1, X_2, \ldots, X_n$ - независимые одинаково распределённые случайные величины с конечным $E[X] = \mu$, то: $$\bar{X}_n = \frac{X_1 + X_2 + \ldots + X_n}{n} \xrightarrow{n \to \infty} \mu$$ Практическое значение: если провести достаточно много экспериментов, среднее результата будет близко к "истинному" значению. Это основа: - A/B тестирования - нужно достаточно пользователей для достоверных результатов - Метода Монте-Карло - приближённое вычисление через случайные испытания - Оценки производительности - бенчмарки должны проводиться на большом количестве итераций > [!summary] Ключевые понятия раздела > > Вероятность событий, условная вероятность и теорема Байеса - основа классификации и фильтрации. Независимость событий - основа расчёта надёжности систем. Математическое ожидание и дисперсия характеризуют среднее поведение и разброс. Нормальное распределение и правило трёх сигм - инструмент обнаружения аномалий. Задача о днях рождения объясняет частоту хеш-коллизий. Закон больших чисел обосновывает A/B тестирование. --- ## Математическая статистика Если теория вероятностей идёт от модели к данным ("если монета честная, какова вероятность выпадения 7 орлов из 10?"), то статистика идёт от данных к модели ("выпало 7 орлов из 10 - честная ли монета?"). ### Выборка и генеральная совокупность Генеральная совокупность - это всё множество объектов, которые нас интересуют. Все пользователи сервиса, все запросы за месяц, все серверы в кластере. Выборка - это подмножество генеральной совокупности, которое мы наблюдаем. Мы не можем измерить время ответа каждого запроса за всё время работы сервиса, но можем проанализировать выборку за последний час. Репрезентативная выборка - выборка, которая адекватно представляет генеральную совокупность. Систематические ошибки выборки (selection bias) - одна из главных проблем в анализе данных. Если анализировать отзывы только тех пользователей, которые сами написали отзыв, выборка будет смещена в сторону крайне довольных или крайне недовольных. ### Описательная статистика Среднее арифметическое - сумма всех значений, делённая на их количество: $$\bar{x} = \frac{1}{n}\sum_{i=1}^{n} x_i$$ Среднее чувствительно к выбросам. Если в команде из 5 человек четверо получают 100 000 и один - 1 000 000, среднее - 280 000, что не отражает типичную зарплату. Медиана - значение, которое делит упорядоченную выборку пополам. Для примера выше медиана - 100 000, что гораздо ближе к типичному значению. Медиана устойчива к выбросам. В мониторинге часто используют p50 (медиана), p95 и p99 вместо среднего. Мода - наиболее часто встречающееся значение. Полезна для категориальных данных. Квантили делят упорядоченные данные на части. p50 (медиана) делит пополам, p25 и p75 - на четверти. В мониторинге производительности особенно важны высокие перцентили: - p50 - типичный пользовательский опыт - p95 - опыт 5% самых медленных запросов - p99 - опыт 1% самых медленных запросов > [!info] Почему p99 важнее среднего > > Если среднее время ответа 50мс, но p99 - 5 секунд, то каждый 100-й запрос мучительно долгий. При 1 миллионе запросов в день это 10 000 плохих пользовательских сессий. Высокие перцентили показывают "хвост" распределения, который может содержать критические проблемы. ### Дисперсия и стандартное отклонение Выборочная дисперсия: $$s^2 = \frac{1}{n-1}\sum_{i=1}^{n}(x_i - \bar{x})^2$$ Делим на $n-1$ (а не на $n$) для получения несмещённой оценки - это поправка Бесселя. При большом $n$ разница пренебрежимо мала. Стандартное отклонение $s = \sqrt{s^2}$ показывает типичное отклонение от среднего. Коэффициент вариации $CV = \frac{s}{\bar{x}} \cdot 100\%$ позволяет сравнивать разброс величин с разными масштабами. Если CV времени ответа сервера - 10%, это стабильный сервис. Если 200% - нестабильный. ### Корреляция и регрессия Корреляция Пирсона измеряет линейную связь между двумя переменными: $$r = \frac{\sum_{i=1}^{n}(x_i - \bar{x})(y_i - \bar{y})}{\sqrt{\sum_{i=1}^{n}(x_i - \bar{x})^2 \cdot \sum_{i=1}^{n}(y_i - \bar{y})^2}}$$ Значение $r$ лежит в диапазоне $[-1, 1]$: - $r = 1$ - идеальная положительная линейная зависимость - $r = -1$ - идеальная отрицательная линейная зависимость - $r = 0$ - нет линейной зависимости (но может быть нелинейная) > [!important] Корреляция не означает причинно-следственную связь > > Это одна из самых частых ошибок в анализе данных. Положительная корреляция между количеством мороженого и утоплениями не означает, что мороженое вызывает утопления. Оба явления вызваны третьим фактором - жаркой погодой. В программировании: корреляция между количеством деплоев и количеством багов не обязательно означает, что деплои вызывают баги - возможно, больше деплоев происходит в периоды активной разработки. Линейная регрессия находит прямую $y = ax + b$, наилучшим образом описывающую данные. Метод наименьших квадратов минимизирует сумму квадратов отклонений: $$a = \frac{n\sum x_i y_i - \sum x_i \sum y_i}{n\sum x_i^2 - (\sum x_i)^2}, \quad b = \bar{y} - a\bar{x}$$ Коэффициент детерминации $R^2 = r^2$ показывает, какую долю вариации $y$ объясняет модель. $R^2 = 0.85$ означает, что модель объясняет 85% вариации. ### Проверка гипотез Статистическая проверка гипотез - это формальная процедура принятия решений на основе данных. Нулевая гипотеза $H_0$ - это гипотеза "по умолчанию", обычно утверждающая отсутствие эффекта. Например: "новая версия сайта не влияет на конверсию". Альтернативная гипотеза $H_1$ - то, что мы хотим доказать. Например: "новая версия сайта увеличивает конверсию". P-значение (p-value) - вероятность получить наблюдаемый (или более экстремальный) результат при условии, что нулевая гипотеза верна. Малое p-value означает, что наблюдаемый результат маловероятен при $H_0$. Уровень значимости $\alpha$ - порог для принятия решения. Обычно $\alpha = 0.05$. Если $p < \alpha$, нулевая гипотеза отвергается. Два типа ошибок: - Ошибка I рода (false positive) - отвергли $H_0$, когда она верна. Вероятность равна $\alpha$ - Ошибка II рода (false negative) - не отвергли $H_0$, когда она неверна. Вероятность обозначается $\beta$ Мощность теста $= 1 - \beta$ - вероятность обнаружить реальный эффект. Чем больше выборка, тем выше мощность. ### A/B тестирование для программистов A/B тестирование - это практическое применение проверки гипотез. Пользователи случайно делятся на две группы: контрольную (A) и экспериментальную (B). Группа A видит текущую версию, группа B - новую. Пример: конверсия группы A - 4.2% (4200 покупок из 100 000), конверсия группы B - 4.5% (4500 покупок из 100 000). Значимо ли различие? Для проверки используется z-тест для двух пропорций: $$z = \frac{p_B - p_A}{\sqrt{\hat{p}(1-\hat{p})\left(\frac{1}{n_A} + \frac{1}{n_B}\right)}}$$ где $\hat{p} = \frac{x_A + x_B}{n_A + n_B}$ - объединённая пропорция. Ключевые вопросы при планировании A/B теста: - Минимальный размер выборки: зависит от текущей конверсии, минимального детектируемого эффекта и требуемой мощности. Калькуляторы размера выборки доступны онлайн - Длительность: тест должен длиться минимум один полный цикл (обычно неделю), чтобы учесть дневные и недельные паттерны - Множественные сравнения: при тестировании нескольких метрик одновременно нужна поправка Бонферрони, иначе вероятность ложного срабатывания растёт - Peeking: подглядывание в результаты до завершения теста и раннее прекращение при "значимом" результате увеличивает вероятность ложного срабатывания > [!summary] Ключевые понятия раздела > > Медиана и перцентили важнее среднего для мониторинга. Корреляция не доказывает причинно-следственную связь. P-value - не вероятность того, что гипотеза верна. A/B тестирование требует планирования размера выборки и учёта множественных сравнений. Стандартное отклонение и коэффициент вариации измеряют стабильность системы. --- ## Теория информации и криптография Теория информации отвечает на вопрос: сколько "информации" содержится в сообщении и как её эффективно передать? Криптография использует математические методы для защиты информации. ### Энтропия Шеннона Энтропия - мера неопределённости (или количества информации) в случайной величине. Для дискретной случайной величины с $n$ возможными значениями: $$H(X) = -\sum_{i=1}^{n} p_i \log_2 p_i$$ Единица измерения - бит. Энтропия максимальна, когда все исходы равновероятны: для монеты $H = -2 \cdot 0.5 \cdot \log_2(0.5) = 1$ бит. Если монета всегда падает орлом ($p = 1$), энтропия равна нулю - нет неопределённости. Для равномерного распределения на $n$ исходах: $H = \log_2 n$. Для кубика: $H = \log_2 6 \approx 2.585$ бит. Это минимальное среднее количество бит, необходимых для кодирования одного броска. Энтропия в программировании: - Оценка силы паролей: пароль из $n$ символов из алфавита размера $k$ имеет энтропию $n \cdot \log_2 k$ бит - Сжатие данных: теоретический предел сжатия определяется энтропией источника - Деревья решений в ML: разбиение данных выбирается так, чтобы максимально снизить энтропию (information gain) - Кросс-энтропия - стандартная функция потерь для классификации в нейронных сетях ### Кодирование информации Код Хаффмана - алгоритм оптимального префиксного кодирования. Идея: частым символам присваиваются короткие коды, редким - длинные. Алгоритм: 1. Подсчитать частоту каждого символа 2. Создать лист дерева для каждого символа 3. Извлечь два узла с наименьшей частотой, объединить их в один узел 4. Повторять, пока не останется один узел (корень) 5. Левая ветвь - 0, правая - 1. Путь от корня к листу - код символа Пример: текст "ABRACADABRA". Частоты: A - 5, B - 2, R - 2, C - 1, D - 1. Без кодирования: 11 символов × 3 бита = 33 бита (3 бита хватает для 5 различных символов). С кодом Хаффмана: A получит код длиной 1 бит, остальные - 2-3 бита. Итого примерно 23 бита. Выигрыш - около 30%. Код Хаффмана используется как компонент во многих алгоритмах сжатия: DEFLATE (ZIP, gzip), JPEG, MP3. ### Хеш-функции Хеш-функция отображает данные произвольного размера в значение фиксированного размера. Математически: $h: \{0,1\}^* \to \{0,1\}^n$. Свойства криптографической хеш-функции: - Детерминированность - одинаковый вход всегда даёт одинаковый выход - Быстрота вычисления - Стойкость к нахождению прообраза - по хешу $h$ невозможно за разумное время найти $m$ такое, что $H(m) = h$ - Стойкость к коллизиям - невозможно за разумное время найти $m_1 \neq m_2$ такие, что $H(m_1) = H(m_2)$ - Лавинный эффект - малое изменение входа кардинально меняет выход Парадокс дней рождения определяет стойкость к коллизиям: для хеша длиной $n$ бит первая коллизия ожидается после $\approx 2^{n/2}$ входов. Для SHA-256 (256 бит) это $2^{128}$ - практически недостижимо. Применения хеш-функций: хеш-таблицы, проверка целостности данных (контрольные суммы), хранение паролей (с солью), цифровые подписи, блокчейн (proof of work). ### Основы криптографии RSA RSA - один из первых алгоритмов асимметричного шифрования, основанный на сложности факторизации больших чисел. Математическая основа - модулярная арифметика. Генерация ключей: 1. Выбрать два больших простых числа $p$ и $q$ 2. Вычислить $n = p \cdot q$ 3. Вычислить функцию Эйлера: $\varphi(n) = (p-1)(q-1)$ 4. Выбрать $e$ такое, что $1 < e < \varphi(n)$ и $\gcd(e, \varphi(n)) = 1$ 5. Найти $d$ такое, что $e \cdot d \equiv 1 \pmod{\varphi(n)}$ (с помощью расширенного алгоритма Евклида) Открытый ключ: $(n, e)$. Закрытый ключ: $(n, d)$. Шифрование сообщения $m$: $$c = m^e \mod n$$ Расшифрование: $$m = c^d \mod n$$ Безопасность RSA основана на том, что, зная $n$, трудно найти $p$ и $q$ (задача факторизации). Для современных стандартов безопасности $n$ должно быть не менее 2048 бит. Малая теорема Ферма, на которой основана корректность RSA: если $p$ - простое число и $\gcd(a, p) = 1$, то: $$a^{p-1} \equiv 1 \pmod{p}$$ > [!summary] Ключевые понятия раздела > > Энтропия Шеннона определяет теоретический предел сжатия и измеряет неопределённость. Код Хаффмана - оптимальное префиксное кодирование. Криптографические хеш-функции обеспечивают целостность данных. RSA основан на сложности факторизации и модулярной арифметике. Парадокс дней рождения определяет стойкость хешей к коллизиям. --- ## Прикладная математика для программистов ### Сложность алгоритмов O-нотация (Big O) - формальный способ описания асимптотического поведения функции. Она описывает верхнюю границу скорости роста. Формальное определение: $f(n) = O(g(n))$, если существуют константы $c > 0$ и $n_0$ такие, что для всех $n \geq n_0$: $$f(n) \leq c \cdot g(n)$$ Неформально: $f(n)$ растёт не быстрее, чем $g(n)$ (с точностью до постоянного множителя). Связанные нотации: - $\Omega(g(n))$ - нижняя граница роста (функция растёт не медленнее) - $\Theta(g(n))$ - точная граница (функция растёт с той же скоростью) - $o(g(n))$ - строгая верхняя граница (функция растёт строго медленнее) Иерархия роста функций (от медленной к быстрой): $$O(1) < O(\log n) < O(\sqrt{n}) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$$ Конкретные значения для наглядности: | $n$ | $\log_2 n$ | $n$ | $n \log_2 n$ | $n^2$ | $2^n$ | $n!$ | |-----|-----------|-----|-------------|-------|-------|------| | 10 | 3 | 10 | 33 | 100 | 1024 | 3.6M | | 100 | 7 | 100 | 664 | 10K | $10^{30}$ | $10^{158}$ | | 1000 | 10 | 1000 | 9966 | 1M | $10^{301}$ | - | | $10^6$ | 20 | $10^6$ | $2 \times 10^7$ | $10^{12}$ | - | - | | $10^9$ | 30 | $10^9$ | $3 \times 10^{10}$ | $10^{18}$ | - | - | Правила определения сложности: 1. Константы и коэффициенты отбрасываются: $O(3n + 5) = O(n)$ 2. При сумме берётся доминирующий член: $O(n^2 + n) = O(n^2)$ 3. Последовательные блоки складываются: $O(n) + O(n^2) = O(n^2)$ 4. Вложенные циклы перемножаются: цикл $O(n)$ внутри цикла $O(n)$ даёт $O(n^2)$ Примеры анализа: ``` // O(n) - линейный for i in range(n): print(i) // O(n^2) - квадратичный for i in range(n): for j in range(n): print(i, j) // O(log n) - логарифмический while n > 1: n = n // 2 // O(n log n) for i in range(n): // O(n) внешний цикл j = n while j > 1: // O(log n) внутренний цикл j = j // 2 ``` ### Амортизированный анализ Амортизированный анализ определяет среднюю стоимость операции в худшей последовательности операций. Отличие от среднего случая: амортизированный анализ не использует вероятности, он даёт гарантию. Классический пример - динамический массив (ArrayList, slice в Go, vector в C++). При вставке элемента, если массив полон, он удваивается: - Обычная вставка: $O(1)$ - Вставка с расширением: $O(n)$ (копирование всех элементов) Амортизированная стоимость одной вставки: $O(1)$. Доказательство методом банковского счёта: каждая обычная вставка "платит" 3 монеты - 1 за саму вставку, 2 откладывает на будущее копирование. К моменту расширения накоплено достаточно монет, чтобы оплатить копирование всех элементов. Другие примеры амортизированного $O(1)$: - Операции с расширяемой хеш-таблицей - Операции `push`/`pop` в стеке с мультипоп (удаление нескольких элементов за раз) - Splay-деревья ### Численные методы Метод Ньютона (метод касательных) - итеративный метод нахождения корня уравнения $f(x) = 0$: $$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$ Каждая итерация строит касательную к графику функции в текущей точке и берёт точку пересечения касательной с осью X как следующее приближение. Метод сходится квадратично - количество верных цифр удваивается на каждой итерации. Пример: вычисление квадратного корня $\sqrt{a}$ сводится к решению уравнения $x^2 - a = 0$: $$x_{n+1} = x_n - \frac{x_n^2 - a}{2x_n} = \frac{1}{2}\left(x_n + \frac{a}{x_n}\right)$$ Это формула Герона, известная с античности. Она сходится очень быстро: для $\sqrt{2}$ с начальным приближением $x_0 = 1$: - $x_1 = 1.5$ - $x_2 = 1.4167$ - $x_3 = 1.41421568...$ - $x_4 = 1.41421356...$ За 4 итерации достигнута точность 8 знаков. Метод Ньютона используется в оптимизации (нахождение минимума функции), компьютерной графике (ray marching), финансовых расчётах (вычисление доходности). Численное интегрирование применяется, когда аналитическое вычисление интеграла невозможно. Метод трапеций приближает площадь под кривой суммой площадей трапеций: $$\int_a^b f(x)\,dx \approx \frac{h}{2}\sum_{i=0}^{n-1}(f(x_i) + f(x_{i+1}))$$ где $h = \frac{b-a}{n}$ - шаг, $x_i = a + ih$. Метод Симпсона использует параболические приближения вместо линейных и даёт более точный результат: $$\int_a^b f(x)\,dx \approx \frac{h}{3}\sum_{i=0}^{n/2-1}(f(x_{2i}) + 4f(x_{2i+1}) + f(x_{2i+2}))$$ ### Интерполяция и аппроксимация Интерполяция строит функцию, проходящую точно через заданные точки. Аппроксимация строит функцию, наилучшим образом приближающую данные, но не обязательно проходящую через каждую точку. Линейная интерполяция между двумя точками $(x_0, y_0)$ и $(x_1, y_1)$: $$y = y_0 + (y_1 - y_0) \cdot \frac{x - x_0}{x_1 - x_0}$$ Это можно записать как $y = \text{lerp}(y_0, y_1, t)$, где $t = \frac{x - x_0}{x_1 - x_0}$ - параметр от 0 до 1: $$\text{lerp}(a, b, t) = a + (b - a) \cdot t = a(1 - t) + bt$$ Функция `lerp` - одна из самых используемых в программировании. Она применяется для плавных анимаций, градиентов цвета, интерполяции значений на карте, сглаживания движения камеры в играх. Полиномиальная интерполяция Лагранжа строит полином степени $n-1$, проходящий через $n$ точек: $$L(x) = \sum_{i=0}^{n-1} y_i \prod_{j \neq i} \frac{x - x_j}{x_i - x_j}$$ Сплайн-интерполяция использует кусочные полиномы (обычно кубические) с условиями гладкости на стыках. Кубические сплайны - стандартный метод для гладких кривых в компьютерной графике (кривые Безье, B-сплайны). > [!summary] Ключевые понятия раздела > > O-нотация формально описывает рост сложности алгоритмов. Амортизированный анализ объясняет, почему динамический массив эффективен несмотря на дорогие расширения. Метод Ньютона быстро находит корни уравнений. Линейная интерполяция (lerp) - основа анимаций и плавных переходов. --- ## Физика и механика Физика для программиста важна в трёх основных областях: разработка игр, физические симуляции и обработка сигналов. ### Кинематика Кинематика описывает движение без рассмотрения причин. Основные величины: - Положение $x(t)$ - где находится объект в момент времени $t$ - Скорость $v(t) = \frac{dx}{dt}$ - как быстро изменяется положение (производная от положения) - Ускорение $a(t) = \frac{dv}{dt} = \frac{d^2x}{dt^2}$ - как быстро изменяется скорость (вторая производная от положения) Для равномерного движения (постоянная скорость): $$x = x_0 + vt$$ Для равноускоренного движения (постоянное ускорение): $$v = v_0 + at$$ $$x = x_0 + v_0 t + \frac{at^2}{2}$$ $$v^2 = v_0^2 + 2a(x - x_0)$$ В игровых движках положение объекта обновляется каждый кадр. Простейший метод - метод Эйлера: ``` // Каждый кадр (dt - время между кадрами) velocity += acceleration * dt position += velocity * dt ``` Этот метод прост, но накапливает ошибку. Более точные методы: метод Верле, Рунге-Кутта 4-го порядка. Баллистика - типичная задача в играх: объект запущен с начальной скоростью $v_0$ под углом $\theta$ к горизонту. Под действием гравитации $g$: $$x(t) = v_0 \cos\theta \cdot t$$ $$y(t) = v_0 \sin\theta \cdot t - \frac{g t^2}{2}$$ Дальность полёта: $L = \frac{v_0^2 \sin 2\theta}{g}$. Максимальная дальность при $\theta = 45°$. ### Законы Ньютона Первый закон: тело остаётся в покое или движется с постоянной скоростью, если на него не действуют силы (или сумма сил равна нулю). Второй закон: $\vec{F} = m\vec{a}$. Сила равна массе, умноженной на ускорение. Зная все силы, действующие на объект, можно вычислить его ускорение: $\vec{a} = \frac{\vec{F}}{m}$. Третий закон: действие равно противодействию. При столкновении двух объектов силы, действующие на них, равны по модулю и противоположны по направлению. Физический движок игры на каждом шаге: 1. Вычисляет все силы, действующие на каждый объект (гравитация, трение, пружины, столкновения) 2. По второму закону Ньютона определяет ускорения 3. Интегрирует ускорения для получения скоростей и положений 4. Обнаруживает и разрешает столкновения Гравитация: $F = mg$, где $g \approx 9.81 \text{ м/с}^2$. Сила трения: $F_{\text{тр}} = \mu N$, где $\mu$ - коэффициент трения, $N$ - сила нормальной реакции опоры. Сила упругости (закон Гука): $F = -kx$, где $k$ - жёсткость пружины, $x$ - деформация. Пружинные силы используются в UI-анимациях (spring animations в React Native, iOS). ### Волны и колебания Гармонические колебания описываются формулой: $$x(t) = A\sin(\omega t + \varphi)$$ где $A$ - амплитуда, $\omega = 2\pi f$ - угловая частота, $f$ - частота в герцах, $\varphi$ - начальная фаза. Период колебаний: $T = \frac{1}{f} = \frac{2\pi}{\omega}$. Звук - это колебания давления воздуха. Цифровой звук представляется как последовательность отсчётов (samples). По теореме Найквиста-Шеннона, для точного восстановления сигнала с максимальной частотой $f_{\max}$ частота дискретизации должна быть не менее $2f_{\max}$. CD-качество: 44.1 кГц - чуть больше удвоенной верхней границы слышимого диапазона (20 кГц). Преобразование Фурье разлагает сигнал на составляющие частоты: $$F(\omega) = \int_{-\infty}^{+\infty} f(t) e^{-i\omega t}\,dt$$ Дискретное преобразование Фурье (DFT) и его быстрая версия (FFT) со сложностью $O(n \log n)$ - основа обработки звука, распознавания речи, сжатия изображений (JPEG), анализа вибраций. > [!info] Где программисты применяют физику > > Игровые движки (Unity, Unreal) - полная физическая симуляция: гравитация, столкновения, трение, пружины. Анимации в UI - spring animations основаны на затухающих колебаниях. Обработка звука - FFT для эквалайзеров, фильтров, распознавания речи. Робототехника - кинематика и динамика манипуляторов. Компьютерное зрение - оптический поток, трекинг объектов. > [!summary] Ключевые понятия раздела > > Кинематика и метод Эйлера - основа обновления позиций в играх. Второй закон Ньютона управляет физическими движками. Закон Гука лежит в основе spring-анимаций. Преобразование Фурье раскладывает сигнал на частоты. Теорема Найквиста определяет требования к частоте дискретизации. --- ## Заключение Математика в программировании - это не отдельная дисциплина, а набор инструментов, каждый из которых решает конкретные задачи. Нет необходимости осваивать всё сразу. Начните с того, что нужно прямо сейчас: дискретная математика и сложность алгоритмов - для любого программиста, статистика - для работы с данными, линейная алгебра - для ML и графики. Главное - понимать, какой математический инструмент подходит для конкретной задачи, и уметь его применить.