Математика и алгоритмы
Страница 23 из 24.
Теорема ван Кампена: фундаментальная группа склейки
Теорема ван Кампена вычисляет фундаментальную группу объединения через свободное произведение с амальгамой по группе пересечения: формулировка, условия и применения.
Биномиальная куча: операции и слияние за 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). Разбираем разделители, массив радиусов и зеркальную симметрию на понятном примере.
Сплетение групп: конструкция и силовские подгруппы
Сплетение групп: регулярное и перестановочное определение через полупрямое произведение, формула порядка, силовские подгруппы симметрических групп, примеры и учебные задачи.