Математика для программиста: карта трека и зачем она нужна на практике

Есть два одинаково вредных мифа: «программисту математика не нужна, всё уже написано в библиотеках» и «сначала весь матанализ, потом можно программировать». Оба неверны, потому что оба неправильно ставят вопрос.

Математика для инженера — не набор формул, которые надо помнить, а набор языков, на которых можно точно сформулировать свойство системы и потом проверить, что оно выполняется. Пишете UNIQUE в схеме таблицы — утверждаете теоретико-множественный факт; пишете reduce в Spark — полагаетесь на ассоциативность; ставите таймаут и ретрай — на модель хвостов распределения. Разница между инженером, который «просто знает», что так работает, и тем, кто понимает почему, проявляется ровно в момент, когда система ломается нестандартно. Этот трек собирает тот минимум, который окупается в промышленной разработке, и объясняет его так, чтобы за каждым определением стояла картинка, а за каждой картинкой — код.

Что мы понимаем под «математикой для программиста»

Формально трек покрывает то, что в западных программах называют Discrete Mathematics, Theory of Computation, Linear Algebra и Probability for CS. Мы намеренно НЕ покрываем матанализ с эпсилон-дельта, аналитическую геометрию и дифуравнения в общем виде: на единицу времени они дают инженеру меньше, чем комбинаторика, линейная алгебра и теория сложности. Производные появятся ровно в объёме, нужном для градиентного спуска и численной устойчивости.

Пять уровней, на которых математика окупается:

1. Корректность — инвариант, предусловие, постусловие. Язык логики предикатов.
2. Производительность — асимптотика, амортизация, нижние оценки. Комбинаторика и сложность.
3. Моделирование — чем представить домен: множествами, графами, алгебраическими структурами.
4. Пределы возможного — что нельзя в принципе: неразрешимость, NP-трудность, CAP.
5. Численная надёжность — почему 0.1 + 0.2 != 0.3 и когда это уронит биллинг.

Уровни 1–2 обычно осваиваются на практике «случайно», уровни 3–5 — только осознанно, и именно они отличают человека, проектирующего систему, от человека, её кодирующего.

Карта трека

Граф зависимостей: в каком порядке читать

Читать подряд не обязательно. Ниже — реальные зависимости по предпосылкам.

Видно три независимых входа: 01 (вся дискретная ветка), 05 (линейная алгебра) и 11 (метатеория, хотя логику 02 лучше прочитать раньше). Стартовать можно с любого.

Сам этот граф — прикладной пример: «в каком порядке учить» есть топологическая сортировка DAG, ровно та задача, что решают make, cargo, Airflow и любой пакетный менеджер.

from graphlib import TopologicalSorter, CycleError   # стандартная библиотека, Python 3.9+

deps = {  # "чтобы прочитать ключ, полезно знать значения"
    "02": ["01"], "03": ["01"], "04": ["03"], "08": ["01"], "09": ["08"],
    "10": ["09"], "06": ["05"], "07": ["06"], "11": ["02"], "12": ["11", "04"],
    "13": ["11"], "14": ["03"], "15": ["06", "14"], "16": ["14"], "17": ["06"],
}
print(list(TopologicalSorter(deps).static_order()))
# ['01', '05', '02', '03', '08', '06', '11', '04', '14', '09', '07', '17', '13', '12', '15', '16', '10']

try:                                                  # а вот так выглядит цикл
    list(TopologicalSorter({"a": ["b"], "b": ["a"]}).static_order())
except CycleError as e:
    print("CycleError:", e.args[0])                   # nodes are in a cycle

Внутри — алгоритм Кана, O(V + E) по времени и памяти; разбор в теории графов. Теория даёт две детали, не видные из кода: топологических порядков обычно много (алгоритм выдаёт один), а при цикле порядка не существует вовсе. Ровно это сообщает npm фразой про circular dependency.

Где математика реально всплывает: шесть сюжетов с кодом

Сюжет 1. Множества — это ваш SQL и ваша система типов

Определение. Множество A — совокупность различимых объектов, принадлежность пишется x ∈ A. Операции: объединение A ∪ B, пересечение A ∩ B, разность A \ B, декартово произведение A × B = {(a, b) | a ∈ A, b ∈ B}.

Интуиция. Реляционная таблица — подмножество декартова произведения доменов колонок. Строка (id, email, created_at) живёт в INT × TEXT × TIMESTAMP. Всё, что делает SQL, — операции над такими подмножествами: INNER JOIN — пересечение по ключу, UNION — объединение, EXCEPT — разность, CROSS JOIN — буквально декартово произведение.

active = {"alice", "bob", "carol", "dave"}
paying = {"bob", "dave", "erin"}

print(active & paying)   # {'bob', 'dave'}   -> INNER JOIN
print(active | paying)   # объединение       -> FULL OUTER JOIN
print(active - paying)   # {'alice','carol'} -> LEFT JOIN ... WHERE right IS NULL
print(active ^ paying)   # симметрическая разность: ровно у одного, но не у обоих

Где обжигаются. Три классические ошибки, у каждой — теоретико-множественная причина:

• NOT IN (SELECT ...) с NULL внутри возвращает пустой результат: SQL работает не в булевой логике, а в трёхзначной (TRUE / FALSE / UNKNOWN), и x NOT IN {NULL} даёт UNKNOWN. Это уже логика, а не множества.
• JOIN размножает строки при неуникальном ключе справа: вы соединяете не функции, а произвольные отношения. Функция — отношение, где каждому x соответствует ровно один y; без UNIQUE вы такой гарантии не давали.
• |A ∪ B| = |A| + |B| - |A ∩ B| — формула включений-исключений. Без неё метрика «всего уникальных пользователей» завышена ровно на величину пересечения.

Теория типов — вторая ипостась того же аппарата: sum type (Either A B) — размеченное объединение, product type (кортеж) — декартово произведение, Option[T] — это T + 1. Число обитателей типа считается по правилам арифметики множеств — отсюда и «алгебраические типы данных».

Сюжет 2. Моноиды — почему ваш reduce вообще параллелится

Определение. Моноид — тройка (S, ⊕, e), где ⊕: S × S -> S ассоциативна ((a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)), а e нейтрален (e ⊕ a = a ⊕ e = a).

Зачем в проде. Ассоциативность — разрешение переставлять скобки, а перестановка скобок — разрешение разбить данные на шарды, свернуть каждый независимо и слить результаты. Без неё параллельный reduce даёт не тот ответ, что последовательный. Поэтому Combiner в MapReduce, Semigroup в Cats и merge в CRDT требуют одного и того же.

import random

def is_associative(op, samples, trials=200):
    """Эмпирическая проверка ассоциативности на выборке значений."""
    return all(op(op(a, b), c) == op(a, op(b, c))
               for a, b, c in (random.choices(samples, k=3) for _ in range(trials)))

vals = [random.uniform(-1e6, 1e6) for _ in range(50)]
print(is_associative(lambda x, y: x + y, vals))      # False — float НЕ ассоциативен!
print(is_associative(lambda x, y: max(x, y), vals))  # True  — max ассоциативен
print(is_associative(lambda x, y: x - y, vals))      # False — вычитание не моноид

Первый результат стоит осознать: сложение чисел с плавающей точкой не ассоциативно. Минимальный контрпример — a = 1.0, b = 1e16, c = -1e16:

a, b, c = 1.0, 1e16, -1e16
print((a + b) + c)   # 0.0 — единица утонула при округлении к 1e16
print(a + (b + c))   # 1.0 — здесь b и c сократились первыми, единица уцелела

То же выражение, разные скобки, разный ответ. Значит, параллельная сумма в Spark и последовательная сумма в Python дадут разные числа, и расхождение растёт с объёмом данных. Не баг, а свойство IEEE 754 — разбор в численных методах.

Практический вывод: моноидальный агрегат можно шардить, кэшировать по частям и досчитывать инкрементально; немоноидальный — нельзя, нужны приближённые структуры.

Сюжет 3. Вероятность — Bloom filter и почему он не врёт в одну сторону

Bloom filter отвечает на «есть ли элемент в множестве» с односторонней ошибкой: «нет» всегда правда, «да» может быть ложным. Вероятность ложноположительного ответа при m битах, n элементах и k хеш-функциях, и проверка формулы симуляцией (сверять теорию с экспериментом — привычка дороже любой формулы):

p ≈ (1 - e^(-k*n/m))^k
оптимальное k = (m/n) * ln 2, тогда p ≈ 0.6185^(m/n)

import math, random
import numpy as np

def bloom_fp_rate(m, n, k, trials=20000, seed=42):
    rng = random.Random(seed)
    bits = np.zeros(m, dtype=bool)
    for _ in range(n):                       # вставляем n элементов по k позиций
        for _ in range(k):
            bits[rng.randrange(m)] = True
    fp = sum(all(bits[rng.randrange(m)] for _ in range(k)) for _ in range(trials))
    return fp / trials                       # доля ложных срабатываний

m, n = 100_000, 10_000
k_opt = round((m / n) * math.log(2))         # ≈ 7
theory = (1 - math.exp(-k_opt * n / m)) ** k_opt
print(f"k={k_opt}  теория={theory:.4f}  эксперимент={bloom_fp_rate(m, n, k_opt):.4f}")
# k=7  теория=0.0082  эксперимент=0.0093

Что это даёт инженеру. Вы считаете заранее, сколько памяти нужно под целевую долю ошибок: примерно 9.6 бит на элемент на каждый порядок точности. Не «попробуем и посмотрим», а расчёт на салфетке до написания кода. Так же считаются размер HyperLogLog, число реплик под целевую доступность и длительность A/B-теста под нужную мощность — про вероятность. Оригинал: Burton Bloom, Space/Time Trade-offs in Hash Coding, CACM 1970.

Сюжет 4. Линейная алгебра — эмбеддинги и векторный поиск

Определение. Скалярное произведение u, v ∈ R^n: <u, v> = sum(u_i * v_i). Косинус угла: cos(u, v) = <u, v> / (||u|| * ||v||), где ||u|| = sqrt(<u, u>).

Интуиция. Скалярное произведение измеряет, насколько два вектора смотрят в одну сторону. На этом стоит весь поиск по смыслу: текст превращают в вектор, близость отождествляют с малым углом.

import numpy as np

def cosine(a, b):
    return float(a @ b / (np.linalg.norm(a) * np.linalg.norm(b)))

docs = {
    "инструкция по деплою": np.array([0.9, 0.1, 0.2, 0.0]),
    "рецепт борща":         np.array([0.0, 0.8, 0.1, 0.9]),
    "runbook по откату":    np.array([0.85, 0.05, 0.3, 0.1]),
}
query = np.array([0.88, 0.08, 0.25, 0.05])   # "как выкатить релиз"

for name, vec in sorted(docs.items(), key=lambda kv: -cosine(query, kv[1])):
    print(f"{cosine(query, vec):.4f}  {name}")
# 0.9966  инструкция по деплою
# 0.9960  runbook по откату
# 0.1206  рецепт борща

Нюанс, который стоит денег. У двух релевантных документов косинус 0.9966 и 0.9960 — различить их почти невозможно. Это проклятие размерности: в пространстве высокой размерности расстояния между случайными точками концентрируются вокруг одного значения, и «ближайший сосед» теряет смысл. Поэтому продакшн нормализует векторы, понижает размерность через PCA/SVD и использует ANN-индексы (HNSW, IVF-PQ) вместо перебора. Теория — в векторах и SVD.

Сюжет 5. Конечные поля — вся ваша криптография и erasure coding

Определение. Поле — множество с + и *, где обе операции ассоциативны и коммутативны, есть нейтральные 0 и 1, у каждого элемента есть противоположный, а у каждого ненулевого — обратный по умножению. GF(p) при простом p — это {0, ..., p-1} с арифметикой по модулю p.

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

p, m = 7, 8      # 7 простое -> поле; 8 составное -> только кольцо

def has_inverse(a, mod):
    return any((a * b) % mod == 1 for b in range(mod))

print([a for a in range(1, p) if not has_inverse(a, p)])  # [] — обратим каждый
print([a for a in range(1, m) if not has_inverse(a, m)])  # [2, 4, 6] — необратимы

# малая теорема Ферма: a^(p-1) = 1 (mod p) для всех a, не делящихся на p
print(all(pow(a, p - 1, p) == 1 for a in range(1, p)))    # True
# следствие: обратный элемент = a^(p-2) mod p, считается за O(log p)
print([(a, pow(a, p - 2, p)) for a in range(1, p)])
# [(1, 1), (2, 4), (3, 5), (4, 2), (5, 3), (6, 6)]

Из этих строк вырастают RSA, обмен ключами Диффи — Хеллмана, ECDSA, коды Рида — Соломона в QR-кодах, erasure coding в объектных хранилищах и схема разделения секрета Шамира: всё это арифметика в конечных полях, отличаются лишь детали — см. абстрактную алгебру и Menezes, van Oorschot, Vanstone, Handbook of Applied Cryptography.

Сюжет 6. Пределы вычислимости — почему у вас нет идеального линтера

Утверждение (Тьюринг, 1936). Не существует программы halts(prog, input), корректно отвечающей для любой программы и входа, завершится ли выполнение.

Доказательство в несколько строк кода. Предположим, halts существует, и построим:

def halts(prog_source, inp):
    """ГИПОТЕТИЧЕСКАЯ функция. Предположим, она существует и всегда права."""
    ...

def diagonal(prog_source):
    if halts(prog_source, prog_source):
        while True:            # зацикливаемся, если предсказано завершение
            pass
    return "остановился"       # завершаемся, если предсказано зацикливание

# Что делает diagonal(diagonal)? "завершится" -> зацикливается; "зациклится" -> завершается.
# Противоречие в обе стороны => halts не существует.

Это диагональный аргумент — приём, которым Кантор доказал несчётность вещественных чисел, а Гёдель — теоремы о неполноте. Следствие для практики (теорема Райса): любое нетривиальное семантическое свойство программ неразрешимо. Поэтому статанализатор обязан выбирать между ложными срабатываниями и пропусками; система типов делается консервативной, отвергая часть корректных программ, лишь бы не пропустить некорректные; go vet, ESLint и Sonar намеренно ловят синтаксис, а не семантику; а полной автоверификации произвольного кода не будет никогда — только для ограниченных языков (SPARK Ada, TLA+) или с участием человека (Coq, Lean).

Подробности — вычислимость и сложность. Первоисточник: A. M. Turing, On Computable Numbers, 1936.

Как выбрать, что учить первым

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

Читать так: логика, асимптотика, вероятность и численная устойчивость — то, незнание чего регулярно приводит к инцидентам. Численная устойчивость встречается редко, но цена ошибки максимальна (финансы, симуляции, обучение моделей). Теория категорий, наоборот, редко бывает причиной инцидента: это инструмент проектирования абстракций, а не тушения пожаров — не «не учить», а «не первым». Если у вас есть только 20 часов, потратьте их на 02 (логика), 03 (комбинаторика), 14 (вероятность) и главы про асимптотику из 12.

Немного истории: как эти идеи попали в компьютеры

Здесь важна не хронология, а сюжет: почти вся эта математика создавалась до компьютеров и не для них. Кантор изучал бесконечности, Буль — законы мышления, Гильберт хотел формализовать всю математику; компьютеры оказались побочным продуктом попытки понять, что такое доказательство. Отсюда и ответ на «учить только то, что пригодится завтра»: то, что пригодится завтра, обычно придумали позавчера ради чего-то совсем другого.

Типичные заблуждения

«Библиотека уже всё реализовала, мне не надо понимать». Библиотека реализовала алгоритм, но не выбрала за вас параметры и не проверила предпосылки. np.linalg.solve решит систему — и молча вернёт мусор на плохо обусловленной матрице. scipy.stats.ttest_ind посчитает p-value — и оно ничего не будет значить, если вы подсматривали в данные до конца эксперимента. Знание нужно не чтобы писать код, а чтобы понимать, когда результату можно верить.

«Математика — это про вычисления». Ровно наоборот: вычисления — самая механическая её часть, и её как раз делегируют машинам. Математика — про определения и следствия. Хорошее определение (моноид, регулярный язык, NP-полнота) сжимает сотню частных случаев в одно утверждение.

«Строгость — формализм ради формализма». Строгость — способ не обманывать себя. Интуитивно «монотонно растущая и ограниченная сверху последовательность сходится» очевидно, но в рациональных числах это ложь. Ровно такие «очевидные, но ложные» утверждения порождают баги в конкурентном коде и финансовой арифметике.

«Нужно знать доказательства наизусть». Нет — нужно понимать идею настолько, чтобы восстановить доказательство за полчаса с бумагой, и понимать границы применимости теоремы. Знание того, где теорема перестаёт работать, практичнее знания самой теоремы. А «не понял с первого раза» — нормальное состояние: абстрактное определение не понимает сразу никто, рабочий цикл описан ниже.

Как работать с треком: методика

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

Шаг «Код» удобно делать через property-based тест: Hypothesis проверяет математические свойства на сгенерированных данных — лучший мост между «доказал» и «работает»:

from hypothesis import given, strategies as st

def merge(a: dict, b: dict) -> dict:
    """Слияние счётчиков — кандидат в моноид (это G-Counter из CRDT)."""
    return {k: max(a.get(k, 0), b.get(k, 0)) for k in a.keys() | b.keys()}

counters = st.dictionaries(st.text(max_size=3), st.integers(0, 100), max_size=5)

@given(counters, counters, counters)
def test_associative(a, b, c):
    assert merge(merge(a, b), c) == merge(a, merge(b, c))

@given(counters)
def test_identity(a):
    assert merge(a, {}) == a

@given(counters, counters)
def test_commutative(a, b):        # сеть не гарантирует порядок доставки
    assert merge(a, b) == merge(b, a)

@given(counters, counters)
def test_idempotent(a, b):         # повторная доставка ничего не меняет
    assert merge(merge(a, b), b) == merge(a, b)

Эти четыре теста — не абстрактное упражнение. Ровно эти свойства (ассоциативность, нейтральный элемент, коммутативность, идемпотентность) делают структуру CvRDT — конвергентным реплицируемым типом данных, который синхронизируется между узлами без консенсуса, без блокировок и при произвольных задержках сети. Разбор — в абстрактной алгебре; первоисточник — Shapiro et al., A Comprehensive Study of Convergent and Commutative Replicated Data Types, INRIA 2011.

Нотация: минимальный словарь

Половина трудностей с математическими текстами — незнакомые значки, а не сложные идеи.

Отдельно про кванторы: порядок имеет значение. ∀x ∃y: P(x, y) («для каждого x найдётся свой y») и ∃y ∀x: P(x, y) («есть один y, годный для всех x») — принципиально разные утверждения. Первое — «у каждого запроса есть обработчик», второе — «есть один обработчик на все запросы». Огромная доля недопониманий в требованиях и SLA сводится ровно к этой перестановке.

Связь с другими треками портала

Математика здесь фундамент под остальные курсы: алгоритмы и структуры данных — комбинаторика, графы, анализ сложности; машинное обучение и нейронные сети — линейная алгебра, вероятность, оптимизация; парадигмы — категории и лямбда-исчисление; инженерия данных — моноиды и оценки кардинальностей; архитектурные паттерны — CRDT и теория игр в дизайне протоколов.

Источники, к которым стоит возвращаться

• Lehman, Leighton, Meyer, «Mathematics for Computer Science» — единый вход, свободный доступ. Если читать что-то одно — читайте это.
• Graham, Knuth, Patashnik, «Concrete Mathematics» — суммы, рекуррентности, производящие функции.
• CLRS, «Introduction to Algorithms» — приложения A–D содержат отличную математическую справку.
• Gilbert Strang, MIT 18.06 — линейная алгебра с геометрической интуицией.
• Sipser, «Introduction to the Theory of Computation» — эталон по автоматам, вычислимости, сложности; Blitzstein, Hwang, «Introduction to Probability» — то же по вероятности.
• Goldberg, «What Every Computer Scientist Should Know About Floating-Point Arithmetic» — обязательное чтение перед любой численной работой. 3Blue1Brown — визуальная интуиция, готовит к строгому тексту.

Мини-итог

• Математика для программиста — язык точных формулировок, а не запас формул.
• Пять уровней отдачи: корректность, производительность, моделирование, пределы возможного, численная надёжность. Первые два приходят с практикой, остальные три — только осознанно.
• Трек читается не подряд: три независимых входа — множества (01), векторы (05), вычислимость (11).
• Методика: интуиция -> строгое определение -> свои примеры -> контрпример -> код и property-based тест -> поиск того же паттерна в своём проекте. Контрпример полезнее примера: он объясняет, зачем в определении каждое слово.
• Мало времени — начните с логики, комбинаторики, вероятности и асимптотики: незнание именно этого чаще всего превращается в инцидент.

Что дальше

Начинаем с фундамента: что такое множество, почему наивное определение приводит к парадоксу Рассела, как аксиоматика ZFC его чинит и почему это напрямую касается систем типов и реляционных БД.

Теория множеств: от наивной к аксиоматической