Математика и алгоритмы
Разборы математических методов, формул и классических алгоритмов. Объясняем то, что обычно остаётся за кадром на лекциях.
Этот раздел собирает разборы математических методов, формул и классических алгоритмов: то, что на лекциях обычно проговаривают бегло, а на семинаре или экзамене внезапно требуют понимать по существу. Здесь мы не пересказываем учебник дословно, а показываем логику: откуда берётся условие, зачем нужен каждый шаг и где обычно теряют баллы. Материалы пригодятся студенту, который готовится к коллоквиуму, разбирает домашнее задание или хочет наконец увидеть смысл за сухой записью.
Тематически категория покрывает несколько направлений. В математическом анализе это исследование рядов на сходимость, например через признак Дирихле для знакопеременных рядов или более тонкий признак Раабе на границе применимости Даламбера. По дискретной математике и теории графов разбираем такие сюжеты, как хроматический полином и подсчёт правильных раскрасок и построение минимального остовного дерева алгоритмом Прима.
Отдельный пласт статей посвящён вероятности, статистике и эконометрике, где важно правильно прочитать таблицы и тесты, в том числе проверку автокорреляции остатков по критерию Дарбина-Уотсона. Сюда же примыкают прикладные алгоритмы и криптография. Каждая статья разбирает один сюжет до уровня, на котором его можно объяснить своими словами, а не просто подставить числа в готовую формулу.
Темы категории
Агрегатные функции SQL: COUNT, SUM, AVG и GROUP BY
Как работают агрегатные функции SQL: COUNT, SUM, AVG, MIN и MAX, группировка GROUP BY, порядок выполнения запроса, разница HAVING и WHERE и поведение NULL внутри агрегата.
Интегральный синус Si(x): ряд Тейлора и максимум
Интегральный синус Si(x): почему интеграл sin t / t не берётся в элементарных функциях, разложение в ряд, предел π/2, максимум Si(π) и выброс Гиббса. С калькулятором.
Куча как структура данных: массив и просеивание
Куча как структура данных: свойство кучи, хранение в обычном массиве и индексы 2i+1 и 2i+2, просеивание sift-up и sift-down, построение за O(n) и приоритетная очередь.
Линейная зависимость векторов: критерии и примеры
Что такое линейная зависимость векторов, как проверить её определителем и рангом матрицы, чем коллинеарность отличается от компланарности и как всё это связано с базисом.
Линейное уравнение второго порядка: общее решение
Как решить линейное однородное уравнение второго порядка с постоянными коэффициентами: характеристическое уравнение, три случая корней, фундаментальная система и задача Коши с разбором.
Метод вариации постоянных: формулы и разбор примера
Метод вариации произвольных постоянных: как из решений однородного уравнения собрать частное, зачем здесь определитель Вронского и когда быстрее оказывается подбор по виду правой части.
Неопределённый интеграл: методы и как выбрать
Пять методов неопределённого интеграла: таблица и линейность, подведение под дифференциал, замена переменной, по частям, разложение дроби. Признак выбора и калькулятор.
Неравенство Минковского: формула и доказательство
Неравенство Минковского как неравенство треугольника для p-нормы: вывод из неравенства Гёльдера, случаи p = 1, 2 и бесконечность, геометрия единичных шаров и условие равенства.
Обход графа в глубину: как работает DFS по шагам
Разбираем обход графа в глубину на одном примере: три цвета вершин, времена входа и выхода, четыре класса рёбер, поиск цикла и компонент связности за O(V+E).
Обход графа в ширину: очередь, слои и кратчайший путь
Обход графа в ширину: как очередь раскладывает вершины по слоям, почему номер слоя равен кратчайшему расстоянию в невзвешенном графе, как восстановить путь по предкам и проверить двудольность.
Пирамидальная сортировка: heapsort за O(n log n)
Как работает пирамидальная сортировка: построение кучи за O(n), извлечение максимума, гарантия O(n log n) в худшем случае, сортировка на месте, неустойчивость и сравнение с quicksort.
Площадь криволинейной трапеции: формула и примеры
Площадь криволинейной трапеции: определение через предел интегральных сумм Римана, расчёт по формуле Ньютона-Лейбница, случай графика ниже оси и площадь между двумя кривыми.
Показательное распределение: формулы и свойства
Показательное распределение: плотность и функция распределения, вывод среднего 1/λ и дисперсии 1/λ², доказательство отсутствия последействия, связь с пуассоновским потоком и расчёт надёжности.
Построения циркулем и линейкой: правила и критерий
Что разрешают циркуль и линейка, как строят середину отрезка, биссектрису и перпендикуляр, какие длины достижимы алгебраически и почему правильный 17-угольник строится, а девятиугольник нет.
Радиус сходимости: формулы Коши-Адамара и Даламбера
Радиус сходимости степенного ряда: теорема Абеля, формулы Коши-Адамара и Даламбера, интервал сходимости и обязательная проверка концов, случаи нулевого и бесконечного радиуса.
Схема Бернулли: формула, условия и приближения
Схема Бернулли: какие три условия обязаны выполняться, как выводится формула вероятности k успехов, чему равны np и npq и когда точный расчёт заменяют Пуассоном или Муавром-Лапласом.
Скрытая марковская модель: устройство и три задачи
Скрытая марковская модель: чем скрытые состояния отличаются от наблюдений, как заданы матрицы переходов и эмиссий, как работают алгоритмы forward, Витерби и Баума-Велча.
SQL соединения таблиц: типы JOIN и число строк
Разбираем соединение таблиц в SQL на строках: условие ON, отличие INNER JOIN от LEFT, RIGHT и FULL, откуда берутся NULL и почему фильтр в WHERE ломает внешнее соединение.
Стек и очередь: чем LIFO отличается от FIFO
Стек и очередь рядом: дисциплины LIFO и FIFO и порядок выхода элементов, очередь на кольцевом буфере за O(1), дек, таблица сложности операций и примеры применения.
Свойства определителя: правила и геометрический смысл
Все свойства определителя с геометрическим объяснением: перестановка строк меняет знак, пропорциональные строки дают нуль, а приведение к треугольному виду считает ответ за пару шагов.
Теорема Кронекера-Капелли: ранги и число решений
Теорема Кронекера-Капелли: система линейных уравнений совместна, когда ранг основной матрицы равен рангу расширенной. Три исхода, число свободных переменных, разбор системы с параметром.
Теорема о вычетах: формула и вычисление интегралов
Теорема о вычетах: формулировка, множитель 2πi и сумма вычетов внутри контура. Как найти вычет в полюсе порядка m, посчитать контурный интеграл и свести к нему вещественный.
Топологическая сортировка: алгоритм Кана и обход DFS
Топологическая сортировка орграфа: как алгоритм Кана через степени входа строит линейный порядок вершин, чем полезен вариант через обход в глубину и как по остатку вершин увидеть цикл.
Правило Крамера: решение СЛАУ через определители
Правило Крамера для систем линейных уравнений: формулы, вычисление главного и вспомогательных определителей, случай нулевого определителя, разбор систем 2 и 3 порядка.