Математика и алгоритмы

Страница 27 из 28.

Интегральная теорема Коши: формулировка, формула и следствия

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

18 февраля 202611 минут

Лемма Бернсайда: число орбит через неподвижные точки

Лемма Бернсайда: формула числа орбит группы преобразований через неподвижные точки, доказательство двойным счётом, раскраски граней куба и бусин, обобщение в теорему Пойа.

17 февраля 202611 минут

Теорема Перрона-Фробениуса: спектральный радиус и вектор

Теорема Перрона-Фробениуса для неотрицательных матриц: спектральный радиус, положительный собственный вектор, условия неприводимости и примитивности, связь с цепями Маркова, PageRank и моделями Лесли.

17 февраля 20269 минут

Лемма Цорна: максимальный элемент и аксиома выбора

Лемма Цорна: формулировка для частично упорядоченных множеств, эквивалентность аксиоме выбора и теореме Цермело, классические применения: базис Гамеля, максимальный идеал, Хан-Банах.

16 февраля 202611 минут

Splay-дерево: самобалансирующееся BST с поворотами к корню

Splay-дерево Слейтора и Тарьяна: операция splay через zig, zig-zig и zig-zag, амортизированная сложность O(log n) через potential function и сравнение с AVL/Red-Black.

14 февраля 202610 минут

Алгоритм Эдмондса-Карпа: поиск максимального потока

Алгоритм Эдмондса-Карпа находит максимальный поток в сети: BFS ищет дополняющий путь, что даёт полиномиальную сложность. Разбираем идею, реализацию и оценку.

13 февраля 202610 минут

Функция Мёбиуса: определение, свойства и обращение

Функция Мёбиуса $μ (n)$ : значения на бесквадратных числах, мультипликативность, тождество $\sum_{d ∣ n} μ (d) = [n = 1]$ , обращение Мёбиуса и связь с дзета-функцией Римана.

12 февраля 20267 минут

Метод Симпсона: численное интегрирование

Метод Симпсона: квадратурная формула на параболе через три точки, составная формула, погрешность $O (h^{4})$ , сравнение с прямоугольниками и трапециями, правило 3/8.

12 февраля 20269 минут

Лемма Гензеля: поднятие корня от mod p к p-адическим целым

Лемма Гензеля: классическая формулировка, итерация p-адического Ньютона, поднятие корня $x^{2} \equiv 2 (mod 7)$ до $Z_{7}$ , геометрический смысл и применения в теории чисел.

10 февраля 202610 минут

Теорема Хана-Банаха: продолжение функционала и разделение

Теорема Хана-Банаха в аналитической и геометрической форме: продолжение линейного функционала, разделение выпуклых множеств, нормирующий функционал, рефлексивность и LP-двойственность.

9 февраля 202612 минут

Алгоритм Куна: как найти максимальное паросочетание

Алгоритм Куна шаг за шагом: ищем увеличивающие цепи обычным DFS и находим максимальное паросочетание в двудольном графе за O(V·E), с разбором идеи и сложности.

8 февраля 20269 минут

Признак Лейбница: знакочередующиеся ряды

Признак Лейбница сходимости знакочередующегося ряда $\sum (- 1)^{n} b_{n}$ : условия, набросок доказательства, оценка остатка $∣ R_{n} ∣ \leq b_{n + 1}$ , абсолютная и условная сходимость, примеры.

8 февраля 20268 минут

Символ Якоби: обобщение Лежандра и тест простоты

Символ Якоби для нечётного составного знаменателя: определение через произведение символов Лежандра, обобщённый закон взаимности и тест простоты Соловея-Штрассена без факторизации.

8 февраля 202611 минут

Алгоритм Кадане: максимальная сумма подмассива

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

6 февраля 202610 минут

Алгоритм Манакера: поиск всех палиндромов за O(n)

Алгоритм Манакера находит все палиндромные подстроки за линейное время O(n). Разбираем разделители, массив радиусов и зеркальную симметрию на понятном примере.

4 февраля 20269 минут

Сплетение групп: конструкция и силовские подгруппы

Сплетение групп: регулярное и перестановочное определение через полупрямое произведение, формула порядка, силовские подгруппы симметрических групп, примеры и учебные задачи.

4 февраля 20268 минут

Лемма Бореля-Кантелли: формулировка и доказательство

Лемма Бореля-Кантелли: первая и вторая формы, понятие limsup событий «бесконечно часто», доказательство через монотонность меры и оценку $1 - x \leq e^{- x}$ , связь с законом 0-1 Колмогорова.

3 февраля 20269 минут

Теорема Радона-Никодима: плотность и условное матожидание

Теорема Радона-Никодима: формулировка для σ-конечных мер, производная dν/dμ, связь с плотностью распределения, условное матожидание и разложение Лебега с контрпримерами.

2 февраля 20269 минут

Неравенство Маркова в теории вероятностей

Неравенство Маркова в теории вероятностей: формулировка для неотрицательной случайной величины, доказательство, типовые задачи на оценку хвоста, связь с неравенством Чебышёва и граница применимости.

31 января 20267 минут

Признак Дирихле для рядов: формулировка и применение

Признак Дирихле сходимости числовых рядов: формулировка, условия применимости, отличия от признака Абеля, разбор тригонометрических рядов и типовых задач.

31 января 20268 минут

Алгоритм Луна: как проверить номер карты по модулю 10

Разбираем алгоритм Луна: как пошагово проверить номер банковской карты, IMEI или SIN по модулю 10, какие опечатки он ловит, а какие пропускает, и чем отличается от Verhoeff.

30 января 202611 минут

Признак Абеля для несобственных интегралов: применение

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

30 января 20269 минут

Линейное уравнение методом Бернулли: пошаговый разбор

Метод Бернулли для решения линейных дифференциальных уравнений первого порядка: идея подстановки y = u·v, пошаговый алгоритм, подробный пример и типичные ошибки.

29 января 20267 минут

Алгоритм Тарьяна: поиск компонент связности орграфа

Алгоритм Тарьяна находит сильно связные компоненты орграфа за один проход DFS. Разбираем идею с disc и low, псевдокод и пример, чтобы вы научились раскладывать граф на SCC.

28 января 20269 минут