Математика и алгоритмы
Страница 26 из 28.
Теорема Борсука-Улама: антиподы, бутерброд и комбинаторика
Теорема Борсука-Улама (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), равномерная ограниченность и равностепенная непрерывность, доказательство и применение в теории ОДУ и компактных операторов.
Теорема Руше: подсчёт нулей аналитической функции
Теорема Руше в комплексном анализе: если на контуре , то и имеют одинаковое число нулей внутри. Локализация корней многочлена с примерами.
Алгоритм Ахо-Корасик: поиск множества образцов в тексте
Разбираем алгоритм Ахо-Корасик: как из бора паттернов и суффиксных ссылок собрать автомат и найти все вхождения множества образцов в тексте за один линейный проход.
Символ Лежандра: квадратичные вычеты по простому модулю
Символ Лежандра: определение через квадратичные вычеты по простому модулю, критерий Эйлера, мультипликативность, квадратичный закон взаимности Гаусса и быстрый алгоритм вычисления.
Теорема Вильсона: критерий простоты и факториал по модулю
Теорема Вильсона: формулировка , доказательство через спаривание обратных, обратное утверждение Лагранжа, обобщение Гаусса и почему это не практический тест простоты.
Центральный ряд группы и класс нильпотентности
Разбираем, что такое центральный ряд группы: как строятся нижний и верхний ряды, чем определяется класс нильпотентности и как это связано с разрешимостью, на примерах.