Математика и алгоритмы
Разборы математических методов, формул и классических алгоритмов. Объясняем то, что обычно остаётся за кадром на лекциях.
Этот раздел собирает разборы математических методов, формул и классических алгоритмов: то, что на лекциях обычно проговаривают бегло, а на семинаре или экзамене внезапно требуют понимать по существу. Здесь мы не пересказываем учебник дословно, а показываем логику: откуда берётся условие, зачем нужен каждый шаг и где обычно теряют баллы. Материалы пригодятся студенту, который готовится к коллоквиуму, разбирает домашнее задание или хочет наконец увидеть смысл за сухой записью.
Тематически категория покрывает несколько направлений. В математическом анализе это исследование рядов на сходимость, например через признак Дирихле для знакопеременных рядов или более тонкий признак Раабе на границе применимости Даламбера. По дискретной математике и теории графов разбираем такие сюжеты, как хроматический полином и подсчёт правильных раскрасок и построение минимального остовного дерева алгоритмом Прима.
Отдельный пласт статей посвящён вероятности, статистике и эконометрике, где важно правильно прочитать таблицы и тесты, в том числе проверку автокорреляции остатков по критерию Дарбина-Уотсона. Сюда же примыкают прикладные алгоритмы и криптография. Каждая статья разбирает один сюжет до уровня, на котором его можно объяснить своими словами, а не просто подставить числа в готовую формулу.
Алгоритм Рабина-Карпа: поиск подстроки за O(n+m)
Разбираем алгоритм Рабина-Карпа: как полиномиальный хеш и скользящее окно ускоряют поиск подстроки до O(n+m) в среднем, почему бывают ложные совпадения и при чём тут плагиат.
Распределение Фишера критические значения: как искать F-квантили
Распределение Фишера и его критические значения: что такое F-распределение, как читать таблицу критических значений по двум степеням свободы, как применять F-квантили в F-тесте на равенство дисперсий и в дисперсионном анализе.
Модель Гордона: рост дивидендов и цена акции
Модель Гордона (Gordon Growth Model) оценивает справедливую стоимость акции через дивиденды с постоянным темпом роста. Формула, вывод, расчёт, ставка дисконтирования и ошибки.
Гетероскедастичность тест Уайта: проверка дисперсии
Гетероскедастичность тест Уайта: разбираем суть теста White, вспомогательную регрессию, статистику nR², число степеней свободы, проверку гипотез по хи-квадрат и типичные ошибки интерпретации в эконометрике.
Вычет в существенно особой точке: как считать
Вычет в существенно особой точке функции комплексного переменного: ряд Лорана, коэффициент при минус первой степени, теорема Сохоцкого, примеры для exp(1/z) и sin(1/z), типичные ошибки.
Алгоритм Прима - как построить остовное дерево по шагам
Разбираем, как алгоритм Прима шаг за шагом строит минимальное остовное дерево графа: идея жадного выбора, лемма о разрезе и трассировка на конкретном примере.
Тест Дарбина-Уотсона: автокорреляция остатков
Тест Дарбина-Уотсона показывает, есть ли автокорреляция остатков регрессии. Разбираем статистику DW, границы dL и dU, проверку гипотез и как не ошибиться в выводах.
Цифровая подпись ECDSA: как устроена и как проверяется
Разбираем цифровую подпись ECDSA на эллиптических кривых: как из приватного ключа и хэша рождается пара (r, s), как идет проверка и почему важен nonce k.
Теорема Дарбу о промежуточном значении производной: свойство без непрерывности
Теорема Дарбу о промежуточном значении производной: формулировка, доказательство через вспомогательную функцию, связь со свойством Дарбу, точки разрыва производной и типичные ошибки.
Коэффициент Трейнора: премия за риск на единицу беты
Коэффициент Трейнора — мера эффективности портфеля: избыточная доходность на единицу систематического риска (беты). Формула, расчёт, отличие от Шарпа и интерпретация.
Хроматический полином графа: как считать и применять
Что такое хроматический полином графа, как его вычислить через теорему об удалении и стягивании ребра, свойства коэффициентов и связь с хроматическим числом. Формулы и пошаговый пример.
Многозначные функции и ветви: точки ветвления и разрезы
Многозначные функции и их ветви в ТФКП: точки ветвления, разрезы плоскости, главная ветвь логарифма и корня, аналитическое продолжение вдоль пути и монодромия.
Признак Раабе сходимости: формулировка и примеры
Признак Раабе сходимости числовых рядов через предел : формулировка, доказательство сравнением с рядом Дирихле, граничный случай , примеры и сравнение с признаком д’Аламбера.
Признак Дирихле: ряды и пошаговый разбор задач
Признак Дирихле для рядов на практике: алгоритм проверки сходимости, оценка частичных сумм, монотонность, разбор примеров с синусами и косинусами, типовые ошибки и FAQ.
Погрешность метода трапеций: оценка остатка
Погрешность метода трапеций: оценка остаточного члена через вторую производную, порядок , формула , выбор шага и правило Рунге.
Теорема Кантора о равномерной непрерывности: суть и доказательство
Теорема Кантора о равномерной непрерывности: формулировка для функции на компакте (отрезке), отличие от обычной непрерывности, доказательство через лемму Гейне–Бореля и контрпримеры.
Алгоритм Шора: зачем он ломает RSA и как работает
Разбираем, как алгоритм Шора сводит факторизацию к поиску периода и за счет квантового преобразования Фурье находит делители быстро, угрожая стойкости RSA.
Метод Хаусхолдера отражения: схема и пример
Метод Хаусхолдера отражения: построение матрицы отражения, обнуление поддиагональных элементов столбца, QR-разложение через преобразования Хаусхолдера, выбор знака и численная устойчивость.
Модель CAPM: оценка капитальных активов через бету
Модель CAPM (capital asset pricing model) связывает ожидаемую доходность капитального актива с систематическим риском (бетой) и рыночной премией. Формула, расчёт, SML, допущения и ошибки.
Достаточная статистика: что это и критерий факторизации
Достаточная статистика простыми словами: строгое определение через условное распределение и критерий факторизации Неймана-Фишера, разбор связи с правдоподобием и примеры.
Неравенство Йенсена для выпуклых функций: формулы и применение
Неравенство Йенсена для выпуклых функций: дискретная и интегральная формулировки, доказательство, условие равенства, связь с математическим ожиданием и применение в анализе и теории вероятностей.
Теорема о неявной функции: доказательство по шагам
Теорема о неявной функции: доказательство через принцип сжимающих отображений, условия применимости, формула производной неявно заданной функции, геометрический смысл и типичные ошибки.
Вариационный метод Ритца: приближённое решение краевых задач
Вариационный метод Ритца: как свести краевую задачу к минимуму функционала, выбрать базисные функции, собрать систему Ритца и оценить погрешность приближённого решения.
Метод Монте-Карло Метрополис: схема, баланс, сходимость
Метод Монте-Карло Метрополис: выборка из распределения Больцмана через цепь Маркова, вероятность принятия, детальный баланс, расчёт термодинамических средних в модели Изинга и подбор шага.
Уравнение Бернулли первого порядка: решение
Уравнение Бернулли первого порядка вида y′+p(x)y=q(x)yⁿ: подстановка z=y^(1−n), пошаговый алгоритм сведения к линейному ОДУ, подробный пример и проверка.
Аппроксимация полиномами Чебышёва - как строить
Разбираем, как работает аппроксимация полиномами Чебышёва: строим разложение по узлам Чебышёва, добиваемся почти минимальной ошибки на отрезке и оцениваем погрешность.
Коэффициент Шарпа: доходность и риск в одном числе
Коэффициент Шарпа — мера доходности с поправкой на риск: избыточная доходность на единицу волатильности. Формула, расчёт, интерпретация и отличие от Сортино и Трейнора.
Метод касательных Ньютона для корня уравнения
Метод касательных Ньютона для корня уравнения : вывод итерационной формулы, геометрический смысл касательной, условие и квадратичная скорость сходимости, выбор начального приближения и типичные ошибки.
Метод штрафных функций: оптимизация с ограничениями
Метод штрафных функций в оптимизации: внешние и внутренние штрафы, барьерные функции, сведение задачи с ограничениями к безусловной, выбор коэффициента штрафа и пошаговая схема решения.
Коэффициент инфляции дисперсии VIF: как измерить мультиколлинеарность
Коэффициент инфляции дисперсии VIF: формула, расчёт через вспомогательную регрессию, связь с tolerance и R², пороговые значения 5 и 10 и способы борьбы с мультиколлинеарностью в линейной регрессии.
Конформное отображение Жуковского: профиль крыла из окружности
Конформное отображение Жуковского в ТФКП: функция Жуковского, образы окружностей и отрезков, профиль крыла, точки разветвления, обратное отображение и применение в аэродинамике.
Метод моментов: оценивание параметров распределения
Метод моментов оценивание параметров: суть приёма, приравнивание выборочных и теоретических моментов, пошаговый алгоритм, примеры для нормального, показательного и равномерного распределений, свойства и ошибки.
Модель Фамы–Френча: три фактора доходности
Трёхфакторная модель Фамы–Френча расширяет CAPM факторами размера (SMB) и стоимости (HML). Формула, смысл коэффициентов, регрессия, пример расчёта и типичные ошибки.
Метод стрельбы для краевой задачи: алгоритм и пример
Метод стрельбы для краевой задачи: сведение к задаче Коши, подбор недостающего начального условия, функция невязки, секущие и метод Ньютона, нелинейный случай и устойчивость.
Алгоритм Диффи-Хеллмана: обмен ключами без передачи ключа
Как алгоритм Диффи-Хеллмана позволяет двум сторонам выработать общий секрет по открытому каналу: дискретный логарифм, протокол по шагам и защита от атаки посередине.
Машина Тьюринга недетерминированная: модель и сила
Машина Тьюринга недетерминированная (НМТ): чем отличается от детерминированной, как работает дерево вычислений, почему она не сильнее по разрешимости и при чём тут класс NP.
Логарифмически нормальное распределение: смысл и формулы
Логарифмически нормальное распределение: плотность, математическое ожидание и дисперсия через параметры μ и σ, связь с нормальным законом, оценка параметров и типовые задачи с примерами расчётов.
Метод бисекции (половинного деления): как это работает
Метод бисекции (половинного деления) для решения уравнения : теорема о промежуточном значении, выбор отрезка, формула середины, оценка числа итераций, скорость сходимости и типичные ошибки.
Метод конечных разностей для уравнений: схемы и устойчивость
Метод конечных разностей для уравнений: разностные схемы, аппроксимация производных, явная и неявная схема, устойчивость, сходимость и краевые задачи на сетке.
Распределение хи-квадрат таблица значений: как читать
Распределение хи-квадрат и таблица критических значений: как пользоваться таблицей по степеням свободы и уровню значимости, где брать квантили χ² и как применять их в критерии согласия Пирсона.
Число обусловленности матрицы - как посчитать и зачем
Число обусловленности матрицы показывает, насколько решение СЛАУ чувствительно к ошибкам. Разбираем, как его посчитать через нормы и понять, устойчива ли система.
Интерполяционная формула Лагранжа: узлы и базисные полиномы
Интерполяционная формула Лагранжа: базисные полиномы , построение многочлена по узлам, оценка погрешности интерполяции, сравнение с методом Ньютона и пример расчёта по таблице.
Функция Бесселя комплексный аргумент: в плоскости
Функция Бесселя комплексный аргумент: продолжение на всю комплексную плоскость, модифицированные , функции Кельвина, асимптотика и линия Стокса.
F1 score: баланс precision и recall в классификации
Метрика F1 score: как она объединяет precision и recall через гармоническое среднее, когда применять F1-меру вместо accuracy и как считать её при дисбалансе классов.
DCF модель оценки компании - как считать стоимость бизнеса
Как работает DCF модель оценки компании: прогноз свободного денежного потока, дисконтирование по WACC, терминальная стоимость и частые ошибки в расчете.
Критерий согласия Колмогорова-Смирнова: проверка распределения
Критерий согласия Колмогорова-Смирнова: как проверить гипотезу о виде распределения по статистике D, как считать эмпирическую функцию распределения, читать критические значения и интерпретировать p-уровень в одновыборочном и двухвыборочном вариантах.
Неравенство Бесселя: ряд Фурье и оценка коэффициентов
Неравенство Бесселя для ряда Фурье: вывод через ортогональную проекцию, связь с равенством Парсеваля, оценка коэффициентов Фурье, сходимость в среднем и разбор типовых задач.
Неравенство Крамера-Рао: нижняя граница дисперсии
Неравенство Крамера-Рао: строгая формулировка нижней границы дисперсии несмещённой оценки, информация Фишера, условия регулярности, эффективные оценки и примеры вычисления границы.
Группа Брауэра: центральные простые алгебры
Группа Брауэра поля : классы центральных простых алгебр по тензорному произведению, связь с , теорема Веддерберна, инвариант над локальными и числовыми полями.
Модель Калдора циклов: нелинейная динамика деловой активности
Модель Калдора экономических циклов: нелинейные функции инвестиций и сбережений, предельный цикл, устойчивость равновесия и условия самоподдерживающихся колебаний выпуска.
Устойчивость по Ляпунову: первая теорема (по первому приближению)
Первая теорема Ляпунова об устойчивости по первому приближению: как по матрице линеаризации (якобиану) и собственным значениям судить об устойчивости положения равновесия нелинейной системы, разбор критического случая.
Эллиптическая функция Вейерштрасса: ℘ и её свойства
Эллиптическая функция Вейерштрасса ℘(z): определение через двоякопериодическую решётку, дифференциальное уравнение, инварианты g₂, g₃, ряд Лорана, связь с эллиптическими интегралами и функциями Якоби.
Максимальное независимое множество в графе: разбор
Что такое независимое множество вершин графа, чем различаются максимальное и наибольшее множество, как связаны число независимости, кликовое число и вершинное покрытие, как искать ответ вручную и алгоритмами.
Теорема Кёнига: двудольный граф, паросочетания и покрытия
Теорема Кёнига для двудольного графа: почему максимальное паросочетание равно минимальному вершинному покрытию. Формулировка, доказательство, пример и связь с теоремой Холла.
Бета-коэффициент акции - как рассчитать и оценить риск
Разбираем бета-коэффициент акции: что он показывает о систематическом риске, как посчитать через ковариацию и дисперсию или регрессию и как читать значения на примере.
Гипергеометрическая функция Гаусса: ряд, уравнение и свойства
Гипергеометрическая функция Гаусса 2F1: определение через ряд с символом Похгаммера, гипергеометрическое уравнение, область сходимости, частные случаи и формулы преобразования.
Интегральная теорема Вейерштрасса: приближение многочленами
Интегральная теорема Вейерштрасса (аппроксимационная теорема о приближении непрерывной функции многочленами): формулировка, смысл равномерного приближения, доказательство через полиномы Бернштейна и обобщение Стоуна.
Распределение Стьюдента степени свободы: как они задают форму
Распределение Стьюдента и его степени свободы: что такое параметр df, как он меняет форму t-распределения, как считать критические значения и применять в t-тестах и доверительных интервалах.
Эффективная граница портфеля Марковица: форма и смысл
Эффективная граница портфеля Марковица — множество Парето-оптимальных портфелей: максимум доходности при заданном риске. Гипербола в координатах риск-доходность, точка минимальной дисперсии, вывод и интерпретация.
Теорема Тейлора, остаточный член Лагранжа: оценка погрешности
Теорема Тейлора и остаточный член в форме Лагранжа: формула с производной порядка в промежуточной точке, вывод, оценка погрешности приближения функции многочленом Тейлора и примеры.
Доказательство с нулевым разглашением: как это работает
Разбираем доказательство с нулевым разглашением: как убедить проверяющего в истинности, ничего не раскрыв, три ключевых свойства протокола и где такие схемы применяют.
Квантово-устойчивая криптография: схемы против Шора
Квантово-устойчивая криптография: постквантовые схемы на решётках, кодах и хэшах, стандарты NIST (ML-KEM, ML-DSA), почему RSA и ECC падают перед алгоритмом Шора и как готовить миграцию.
Задача Штурма-Лиувилля собственные значения: как искать
Задача Штурма-Лиувилля и её собственные значения: самосопряжённый оператор, краевые условия, спектр, собственные функции, ортогональность с весом и разложение в ряд.
Модель Блэка-Шоулза: цена опциона за пять параметров
Модель Блэка-Шоулза для опционов: вывод формулы цены европейского call и put, параметры d1 и d2, греки, волатильность и типичные ошибки расчёта.
Модель GARCH волатильность: условная дисперсия ряда
Модель GARCH и волатильность: уравнение условной дисперсии, переход от ARCH к GARCH(1,1), условие стационарности, персистентность, прогноз волатильности и оценка параметров по методу максимального правдоподобия.
Метод Рунге-Кутты 4 порядка: численное решение ОДУ
Метод Рунге-Кутты 4 порядка для задачи Коши: формулы коэффициентов –, шаг , локальная и глобальная погрешность , сравнение с методом Эйлера и пример расчёта.
Как работает ANOVA однофакторный дисперсионный анализ
ANOVA однофакторный дисперсионный анализ сравнивает средние в трёх и более группах. Разбираем суммы квадратов, F-критерий и условия применимости на примере с расчётом.
Задача о k-центрах в графе: постановка и алгоритмы
Что такое задача о k-центрах в графе: постановка как минимаксная задача размещения, NP-трудность, жадный 2-приближённый алгоритм Гонзалеса и связь с радиусом графа.
Распределение Пуассона: свойства, формула и моменты
Распределение Пуассона: свойства закона редких событий, формула вероятности, математическое ожидание и дисперсия, аддитивность, связь с биномиальным и экспоненциальным законами, примеры расчётов.
Явный и неявный метод Эйлера: устойчивость и выбор шага
Явный и неявный метод Эйлера для задачи Коши: формулы прямой и обратной схемы, локальная и глобальная погрешность , абсолютная устойчивость, жёсткие уравнения и сравнение методов.
Парадокс Кондорсе голосования: когда большинство себе противоречит
Парадокс Кондорсе голосования: почему попарное большинство даёт циклическое предпочтение, как строить матрицу побед, искать победителя Кондорсе и связь с теоремой Эрроу.
Теорема Четаева о неустойчивости: формулировка и метод
Теорема Четаева о неустойчивости положения равновесия: как через функцию Четаева и область V>0 доказать неустойчивость нелинейной системы там, где прямой метод Ляпунова молчит.
Теорема Гурвица: критерий устойчивости полинома
Теорема Гурвица (критерий Рауса-Гурвица): как по коэффициентам характеристического полинома определить устойчивость системы, построить матрицу Гурвица, вычислить главные миноры и расположение корней.
Алгоритм Литтла: решаем задачу коммивояжёра
Алгоритм Литтла шаг за шагом: как приводить матрицу расстояний, считать штрафы нулей и строить дерево ветвления, чтобы найти оптимальный маршрут коммивояжёра.
Модель Марковица: оптимальный портфель и минимум риска
Модель Марковица строит оптимальный портфель: минимум дисперсии при заданной доходности через ковариации активов. Постановка задачи, диверсификация, формулы весов и типичные ошибки.
Парадокс Эрроу теорема: почему идеальных выборов нет
Парадокс Эрроу теорема о невозможности: четыре аксиомы (неограниченность, единогласие, независимость, отсутствие диктатора), их несовместимость при трёх альтернативах и связь с циклами Кондорсе.
Принцип симметрии Шварца: аналитическое продолжение через отражение
Принцип симметрии Шварца в ТФКП: как продолжить аналитическую функцию через отрезок вещественной оси и через дугу окружности, условия применимости и типичные ошибки.
LU-разложение матрицы алгоритм: схема и пример
LU-разложение матрицы: алгоритм Гаусса для разложения A = LU, выбор ведущего элемента и P, решение СЛАУ через прямую и обратную подстановку, вычисление определителя.
Теорема двойственности линейного программирования: суть и применение
Теорема двойственности линейного программирования: прямая и двойственная задачи, правила построения, слабая и сильная двойственность, теорема о дополняющей нежёсткости и экономический смысл двойственных оценок.
Метод Якоби решение СЛАУ: формулы, сходимость, пример
Метод Якоби для решения СЛАУ Ax = b: итерационные формулы, условие диагонального преобладания, спектральный радиус, сравнение с Гауссом–Зейделем и пошаговый пример.
Линейная система ОДУ с постоянными коэффициентами
Линейная система ОДУ с постоянными коэффициентами: матричная запись, метод собственных значений и собственных векторов, случаи действительных, кратных и комплексных корней, разбор примеров и проверка.
Состоятельная оценка параметра: определение и проверка
Состоятельная оценка параметра: строгое определение через сходимость по вероятности, разница со смещённостью, достаточные условия, закон больших чисел и примеры проверки оценок на состоятельность.
Признак Куммера сходимости: общий критерий рядов
Признак Куммера сходимости положительных рядов через предел : формулировка, доказательство, частные случаи д’Аламбера, Раабе и Бертрана, выбор последовательности и примеры.
Кубический сплайн интерполяция: моменты и прогонка
Кубическая сплайн-интерполяция: построение сплайна по узлам, трёхдиагональная система на вторые производные, метод прогонки, краевые условия и сравнение с многочленом Лагранжа.
Признак Гаусса сходимости: формулировка и применение
Признак Гаусса сходимости положительных рядов через асимптотику : формулировка, связь с признаком Раабе, разбор граничного случая , примеры с гипергеометрическими рядами.
Тест Левена: проверка равенства дисперсий
Тест Левена на равенство дисперсий: разбираем суть критерия Levene, формулу F-статистики, варианты по среднему и медиане (Браун-Форсайт), гипотезы, степени свободы и частые ошибки интерпретации.
Эллиптические интегралы Лежандра: три канонические формы
Эллиптические интегралы Лежандра: нормальные формы первого, второго и третьего рода F, E, Π, модуль k, амплитуда φ, полные интегралы K(k) и E(k), приведение и численный расчёт.
Индекс Джини: расчёт по шагам и формулы
Индекс Джини: расчёт коэффициента концентрации через кривую Лоренца, формулы для сгруппированных и несгруппированных данных, интерпретация значений и типовые ошибки на разборе.
Эксцентриситет вершины графа: определение и расчёт
Что такое эксцентриситет вершины графа: определение через расстояние, формула, пошаговый расчёт по матрице кратчайших путей, свойства и связь с радиусом, диаметром, центром.
Процесс Орнштейна-Уленбека: средневозвратная диффузия
Процесс Орнштейна-Уленбека: стохастическое дифференциальное уравнение , среднее, дисперсия, стационарное распределение, автокорреляция и связь с уравнением Ланжевена.
Сходимость метода простой итерации: условие и оценка
Сходимость метода простой итерации для уравнения : принцип сжимающих отображений, условие , скорость и априорная оценка погрешности, примеры и типичные ошибки.
Квадратурная формула Гаусса: узлы и веса
Квадратурная формула Гаусса: узлы как корни полиномов Лежандра, веса квадратуры, алгебраическая точность 2n−1, формула Гаусса-Лежандра, пересчёт на отрезок [a,b] и оценка погрешности.
Условный экстремум: множители Лагранжа без зубрёжки
Условный экстремум функции нескольких переменных через множители Лагранжа: функция Лагранжа, система уравнений, проверка на минимум и максимум, окаймлённый гессиан и типичные ошибки.
Метод ветвей и границ: задача коммивояжёра по шагам
Метод ветвей и границ для задачи коммивояжёра: матрица расстояний, приведение строк и столбцов, нижняя граница, дерево ветвления и отсечение бесперспективных маршрутов.
Радиус и диаметр графа: как считать эксцентриситет
Что такое радиус и диаметр графа, как через эксцентриситет вершин найти центр и периферию. Формулы, пошаговый пример и связь с расстояниями в графе.
Алгоритм Метрополиса-Гастингса: как работает MCMC
Алгоритм Метрополиса-Гастингса позволяет сэмплировать из сложного распределения через цепь Маркова. Разбираем шаг принятия, detailed balance и сходимость на понятных примерах.
Формула Эйлера-Маклорена: разбор и применение
Формула Эйлера-Маклорена связывает сумму с интегралом через числа Бернулли и остаточный член. Разбор формулировки, доказательства и классических приложений.
Лемма Фату: формулировка, доказательство и применения
Лемма Фату: для неотрицательных измеримых выполнено . Доказательство через монотонную сходимость, связь с DCT.
Локализация кольца: конструкция и геометрия
Локализация кольца в коммутативной алгебре: конструкция через классы дробей, поле частных, локальное кольцо , плоскость, стебли пучка на Spec.
Алгоритм Грэхема: строим выпуклую оболочку точек
Алгоритм Грэхема строит выпуклую оболочку набора точек за O(n log n): опорная точка, сортировка по углу и обход стеком. Разбираем шаги и проверку поворота.
Теоремы Силова: существование, сопряжённость, число подгрупп
Теоремы Силова о -подгруппах конечной группы: существование силовской подгруппы порядка , сопряжённость всех таких подгрупп, арифметика числа и примеры классификации.
Нильпотентная группа: определение, класс, примеры
Нильпотентная группа: стабилизация нижнего и верхнего центральных рядов, класс нильпотентности, теорема о прямом произведении силовских p-подгрупп и примеры.
Теорема Гильберта о базисе: формулировка и доказательство
Теорема Гильберта о базисе 1890 года: если кольцо R нётерово, то R[x] тоже нётерово. Идея доказательства, следствия для алгебраической геометрии и типовые задачи.
Оператор Лапласа-Бельтрами: формула, спектр и тепловое ядро
Оператор Лапласа-Бельтрами — обобщение Лапласа на риманово многообразие: , спектр, тепловое ядро, асимптотика Вейля.
Расслоение Хопфа: со слоем
Расслоение Хопфа — первый нетривиальный пример со слоем , кватернионная и октонионная Hopf-фибрации, число Хопфа, , сфера Блоха.
Сопряжённые функторы: биекция Hom, единица и примеры
Сопряжённые функторы: естественная биекция , левый и правый сопряжённый, единица и коединица, классические примеры, сохранение пределов.
Теорема Лагранжа для групп: порядок, индекс, следствия
Теорема Лагранжа для конечных групп: порядок подгруппы делит порядок группы, индекс и классы смежности, доказательство, малая Ферма и Эйлер, контрпример .
Алгоритм Чана: как строить выпуклую оболочку за O(n log h)
Алгоритм Чана строит выпуклую оболочку n точек за O(n log h): разбор идеи с угадыванием числа вершин h, комбинацией Graham scan и Jarvis march по шагам.
Неравенство Гёльдера для интегралов: формулы и применение
Неравенство Гёльдера для интеграла: формулировка с сопряжёнными показателями p и q, доказательство через неравенство Юнга, частные случаи и применение в пространствах L^p.
B-дерево: вставка ключа и разделение узла
Разбираем вставку в B-дерево по шагам: минимальная степень t, инвариант t-1..2t-1 ключей и разделение переполненного узла с подъёмом среднего ключа к родителю.
Проективный модуль: определения, свойства, K-теория
Проективный модуль над кольцом : подъём гомоморфизма через сюръекцию, прямое слагаемое свободного, эквивалентность для PID и локальных колец, роль в K-теории.
Уравнение Бесселя: решение через и
Уравнение Бесселя: решение методом Фробениуса, функции Бесселя первого и второго рода, цилиндрическая симметрия и физические приложения от мембраны до волноводов.
Метод Гаусса-Зейделя СЛАУ: формулы, сходимость, сравнение с Якоби
Итерационный метод Гаусса-Зейделя для СЛАУ: формулы, условие диагонального преобладания, сравнение с методом Якоби, SOR-релаксация и оптимальный параметр.
Теорема Банаха-Штейнгауза: равномерная ограниченность
Теорема Банаха-Штейнгауза (uniform boundedness principle): поточечная ограниченность семейства операторов в банаховом пространстве влечёт равномерную, доказательство через теорему Бэра.
Квадратичный закон взаимности: золотая теорема Гаусса
Квадратичный закон взаимности Гаусса для символов Лежандра: точная формулировка, два дополнения, восемь доказательств, обобщения Якоби, Эйзенштейна и Артина, алгоритм вычисления.
Теорема Морера: обратная к теореме Коши для голоморфности
Теорема Морера: если непрерывная в области даёт по любому треугольнику, то голоморфна. Обратная теоремы Коши, применения и доказательство.
Преобразование Лапласа: ОДУ и системы
Преобразование Лапласа для дифференциальных уравнений: метод операционного исчисления, учёт начальных условий, разложение на простые дроби и обратное преобразование.
Признак Ермакова: сходимость рядов с логарифмами
Признак Ермакова (1871) для сходимости положительных монотонных рядов через предел : формулировка, примеры с логарифмами, сравнение с Коши.
Симплициальный комплекс: вершины, грани и гомологии
Симплициальный комплекс: симплексы и их грани, цепной комплекс с граничным оператором, группы гомологий и формула Эйлера χ для поверхностей.
Теорема Лебега о мажорируемой сходимости: DCT и применения
Теорема Лебега о мажорируемой сходимости (DCT): условие мажоранты с интегрируемой , переход к пределу под интегралом, доказательство через лемму Фату.
Теорема Борсука-Улама: антиподы, бутерброд и комбинаторика
Теорема Борсука-Улама (1933): для непрерывного отображения сферы в евклидово пространство существует пара антиподов с одинаковым образом. Следствия — ham sandwich, Тверберг, дискретная геометрия.
Теорема Дирихле о простых в арифметической прогрессии
Теорема Дирихле 1837 года: в прогрессии a+nd при взаимно простых a и d бесконечно много простых. Идея доказательства через характеры, L-функции и плотность.
Гомотопическая эквивалентность: суть и инварианты
Гомотопическая эквивалентность — отношение на топологических пространствах через непрерывные деформации, отличие от гомеоморфизма, инварианты π_n, H_n, χ, теорема Уайтхеда.
Характеристическая функция в теории вероятностей
Характеристическая функция : преобразование Фурье плотности, моменты через производные, теорема Леви о непрерывности и вывод центральной предельной теоремы.
Разрешимая группа: производный ряд и теория Галуа
Разрешимая группа: производный ряд , стабилизация на тривиальной подгруппе, отличие от нильпотентности, связь с теорией Галуа и Абелем-Руффини.
AVL-дерево: как работает балансировка и ротации
Разбираем, как AVL-дерево восстанавливает баланс после вставки и удаления: инвариант высоты, balance factor и четыре ротации LL, RR, LR, RL за O(log n).
Лемма Йонеды: формулировка, доказательство, вложение
Лемма Йонеды в теории категорий: биекция , представимый функтор , вложение Йонеды и приложения к алгебре и программированию.
Куча Фибоначчи: ленивая структура и амортизация
Куча Фибоначчи: амортизированный на insert и decrease-key, ленивая консолидация при extract-min, потенциал, каскадный cut и применение в алгоритме Дейкстры.
Алгоритм Бойера-Мура-Хорспула: как работает упрощённый BM
Алгоритм Бойера-Мура-Хорспула простыми словами: одна таблица сдвигов по последнему символу окна, среднее время O(n/m), худший случай и сравнение с BM, KMP и Sunday.
Формула обращения Мёбиуса: вывод и применения
Формула обращения Мёбиуса: если , то . Доказательство, тотиент Эйлера, неприводимые многочлены, ряды Дирихле.
Максимальный идеал кольца: определение и свойства
Максимальный идеал — собственный без строго бо́льшего собственного над-идеала; — поле, лемма Цорна о существовании, простота, MaxSpec и Nullstellensatz.
Теорема Стоуна-Вейерштрасса: плотность подалгебр в C(K)
Теорема Стоуна-Вейерштрасса: плотность подалгебр в C(K) на компакте, обобщение Вейерштрасса о приближении полиномами, разделение точек, доказательство через решётку.
Венгерский алгоритм: задача о назначениях
Венгерский алгоритм (Hungarian, Кун–Манкр) для задачи о назначениях: минимальное паросочетание в двудольном графе, ЛП-двойственность, и сравнение с потоковыми и аукционными методами.
Z-функция строки за O(n): построение и применение
Что такое Z-функция строки, как построить массив за линейное время O(n) с помощью Z-блока, чем она отличается от префикс-функции и какие задачи решает на практике.
Тензор кривизны Римана: формулы, симметрии и роль в ОТО
Тензор кривизны Римана : определение через коммутатор ковариантных производных, формула через символы Кристоффеля, симметрии, тождества Бианки, скаляр Риччи и связь с уравнениями Эйнштейна.
Теорема Гаусса-Бонне: кривизна и эйлерова характеристика
Теорема Гаусса-Бонне в дифференциальной геометрии: , локальная и глобальная версии, связь гауссовой кривизны с топологией поверхностей и классические следствия.
Теорема ван Кампена: фундаментальная группа склейки
Теорема ван Кампена вычисляет фундаментальную группу объединения через свободное произведение с амальгамой: .
Биномиальная куча: операции и слияние за O(log n)
Биномиальная куча: как устроен лес деревьев, зачем нужно слияние двух куч за O(log n) и чем она лучше бинарной. Разбираем операции insert, extract-min и merge на примерах.
Теорема Арцела–Асколи: критерий компактности в C(K)
Теорема Арцела–Асколи: формулировка для C(K), равномерная ограниченность и равностепенная непрерывность, доказательство, применение в ОДУ и операторах.
Теорема Руше: подсчёт нулей аналитической функции
Теорема Руше в комплексном анализе: если на контуре , то и имеют одинаковое число нулей внутри. Локализация корней многочлена с примерами.
Алгоритм Ахо-Корасик: поиск множества образцов в тексте
Разбираем алгоритм Ахо-Корасик: как из бора паттернов и суффиксных ссылок собрать автомат и найти все вхождения множества образцов в тексте за один линейный проход.
Символ Лежандра: квадратичные вычеты по простому модулю
Символ Лежандра : определение через квадратичные вычеты по простому модулю, критерий Эйлера, мультипликативность, квадратичный закон взаимности Гаусса и алгоритм быстрого вычисления.
Теорема Вильсона: критерий простоты и факториал по модулю
Теорема Вильсона: формулировка , доказательство через спаривание обратных, обратное утверждение Лагранжа, обобщение Гаусса и почему это не практический тест простоты.
Центральный ряд группы и класс нильпотентности
Разбираем, что такое центральный ряд группы: как строятся нижний и верхний ряды, чем определяется класс нильпотентности и как это связано с разрешимостью, на примерах.
Интегральная теорема Коши: формулировка, формула и следствия
Интегральная теорема Коши для голоморфных функций: доказательство через Гурса, интегральная формула Коши, производные любого порядка, теорема Лиувилля и связь с вычетами.
Лемма Бернсайда: число орбит через неподвижные точки
Лемма Бернсайда: формула числа орбит группы преобразований через неподвижные точки, доказательство двойным счётом, раскраски граней куба и бусин, обобщение в теорему Пойа.
Теорема Перрона-Фробениуса: спектральный радиус и собственный вектор
Теорема Перрона-Фробениуса для неотрицательных матриц: спектральный радиус, положительный собственный вектор, условия неприводимости и примитивности, связь с цепями Маркова, PageRank и моделями Лесли.
Лемма Цорна: максимальный элемент, аксиома выбора и базис Гамеля
Лемма Цорна: формулировка для частично упорядоченных множеств, эквивалентность аксиоме выбора и теореме Цермело, классические применения — базис Гамеля, максимальный идеал, Хан-Банах.
Splay-дерево: самобалансирующееся BST через продвижение к корню
Splay-дерево Слейтора и Тарьяна: операция splay через zig, zig-zig и zig-zag, амортизированная сложность O(log n) через potential function и сравнение с AVL/Red-Black.
Алгоритм Эдмондса-Карпа: поиск максимального потока
Алгоритм Эдмондса-Карпа находит максимальный поток в сети: BFS ищет дополняющий путь, что даёт полиномиальную сложность. Разбираем идею, реализацию и оценку.
Функция Мёбиуса: определение, свойства и обращение
Функция Мёбиуса : значения на бесквадратных числах, мультипликативность, тождество , обращение Мёбиуса и связь с дзета-функцией Римана.
Метод Симпсона: численное интегрирование
Метод Симпсона: квадратурная формула на параболе через три точки, составная формула, погрешность , сравнение с прямоугольниками и трапециями, правило 3/8.
Лемма Гензеля: поднятие корня от mod p к p-адическим целым
Лемма Гензеля: классическая формулировка, итерация p-адического Ньютона, поднятие корня до , геометрический смысл и применения в теории чисел.
Теорема Хана-Банаха: продолжение функционала и разделение выпуклых множеств
Теорема Хана-Банаха в аналитической и геометрической форме: продолжение линейного функционала, разделение выпуклых множеств, нормирующий функционал, рефлексивность и LP-двойственность.
Алгоритм Куна: как найти максимальное паросочетание
Алгоритм Куна шаг за шагом: ищем увеличивающие цепи обычным DFS и находим максимальное паросочетание в двудольном графе за O(V·E), с разбором идеи и сложности.
Признак Лейбница: знакочередующиеся ряды
Признак Лейбница сходимости знакочередующегося ряда : условия, набросок доказательства, оценка остатка , абсолютная и условная сходимость, примеры.
Символ Якоби: обобщение Лежандра и тест простоты
Символ Якоби для нечётного составного : определение через произведение символов Лежандра, обобщённый закон взаимности и тест простоты Соловея–Штрассена.
Алгоритм Кадане: максимальная сумма подмассива
Алгоритм Кадане за линейное время находит подмассив с наибольшей суммой. Разбираем идею динамического программирования, ловушку отрицательных чисел и реализацию.
Алгоритм Манакера: поиск всех палиндромов за O(n)
Алгоритм Манакера находит все палиндромные подстроки за линейное время O(n). Разбираем разделители, массив радиусов и зеркальную симметрию на понятном примере.
Сплетение групп: конструкция и силовские подгруппы
Сплетение групп : регулярное и перестановочное определение через полупрямое произведение , порядок, силовские подгруппы , примеры и задачи.
Лемма Бореля-Кантелли: формулировка, доказательство и применение
Лемма Бореля-Кантелли: первая и вторая формы, понятие limsup событий «бесконечно часто», доказательство через монотонность меры и оценку , связь с законом 0-1 Колмогорова.
Теорема Радона-Никодима: формулировка, плотности и условное матожидание
Теорема Радона-Никодима: формулировка для σ-конечных мер, производная dν/dμ, связь с плотностью распределения, условное матожидание и разложение Лебега с контрпримерами.
Неравенство Маркова в теории вероятностей
Неравенство Маркова в теории вероятностей: формулировка для неотрицательной случайной величины, доказательство, типовые задачи на оценку хвоста, связь с неравенством Чебышёва и граница применимости.
Признак Дирихле для рядов: формулировка и применение
Признак Дирихле сходимости числовых рядов: формулировка, условия применимости, отличия от признака Абеля, разбор тригонометрических рядов и типовых задач.
Алгоритм Луна: как проверить номер карты по модулю 10
Разбираем алгоритм Луна: как пошагово проверить номер банковской карты, IMEI или SIN по модулю 10, какие опечатки он ловит, а какие пропускает, и чем отличается от Verhoeff.
Признак Абеля для несобственных интегралов: формулировка и применение
Признак Абеля для несобственных интегралов и близкий признак Дирихле: условия, доказательство через формулу Абеля, примеры на коллоквиум и сравнение с абсолютной сходимостью.
Линейное уравнение методом Бернулли: пошаговый разбор
Метод Бернулли для решения линейных дифференциальных уравнений первого порядка: идея подстановки y = u·v, пошаговый алгоритм и подробный пример.
Алгоритм Тарьяна: поиск компонент связности орграфа
Алгоритм Тарьяна находит сильно связные компоненты орграфа за один проход DFS. Разбираем идею с disc и low, псевдокод и пример, чтобы вы научились раскладывать граф на SCC.
Алгоритм Кнута-Морриса-Пратта: поиск подстроки за O(n+m)
Алгоритм Кнута-Морриса-Пратта ищет подстроку без возвратов по тексту. Разбираем префикс-функцию по шагам, оцениваем сложность и смотрим понятный пример работы.
Алгоритм Бойера-Мура: почему он ищет подстроку так быстро
Разбираем алгоритм Бойера-Мура: зачем сравнивать паттерн справа налево, как работают эвристики плохого символа и хорошего суффикса и почему поиск выходит сублинейным.
Алгоритм Дейкстры: как найти кратчайший путь в графе
Разбираем алгоритм Дейкстры на взвешенном графе по шагам: как он находит кратчайшие пути от стартовой вершины и почему ломается на ребрах с отрицательными весами.
Алгоритм Карацубы: умножение длинных чисел быстрее столбика
Разбираем алгоритм Карацубы: почему три умножения вместо четырёх ускоряют перемножение длинных чисел, как выглядит рекуррентность и зачем это нужно на практике.
Замыкания JavaScript: как функция помнит свой контекст
Замыкания JavaScript простыми словами: как lexical scope и [[Environment]] позволяют функции хранить state между вызовами, где это применяют и какие ловушки с var и памятью встречаются на практике.
Якобиан полярных координат: откуда берётся r и зачем он нужен
Подробный вывод якобиана перехода к полярным координатам. Объясняем, почему dx dy превращается в r dr dθ, и разбираем примеры двойных интегралов.
Алгоритм Беллмана-Форда: пути с отрицательными весами
Разбираем алгоритм Беллмана-Форда: как искать кратчайшие пути в графе с отрицательными рёбрами, ловить отрицательные циклы и чем он отличается от Дейкстры.
Цикломатическая сложность: как считать по Маккейбу
Цикломатическая сложность показывает число независимых путей в коде. Разбираем формулу Маккейба V(G)=E-N+2P, подсчёт по решающим точкам и пороги ISO для тестов.