линейная алгебра

Статьи

DP Приём Динамика на отрезках Состояние — отрезок [i, j], переход — где его разрезать: дерево поиска, порядок умножения матриц, распил. O(n³) 2 задачи NUM Алгоритм Китайская теорема об остатках Число по остаткам от нескольких модулей: алгоритм Гарнера и точные вычисления по многим простым. O(k²) операций с машинными числами 2 задачи NUM Алгоритм Матрицы и рекуррентности Степень матрицы: пути длины k в графе, линейные рекуррентности, матрица переноса и цепи Маркова. O(m³ log k) для A^k размера m × m 2 задачи NUM Алгоритм Метод Гаусса Линейная система исключением: ведущий элемент, LU, обусловленность, разреженные матрицы и заполнение. O(n³): около n³/3 умножений на прямой ход 2 задачи NUM~ Алгоритм Симплекс-метод 24 числа вместо 88 клавиш — и симплекс-метод восстанавливает каждый аккорд прелюдии Шопена точно. Наименьшие квадраты — ни одного.

шаг — O(m·n); число шагов на практике порядка m, в худшем случае экспоненциальное

1 задача ML Алгоритм Линейная регрессия Подбирает коэффициенты модели так, чтобы сумма квадратов промахов по данным была наименьшей. O(n·d² + d³) 2 задачи ML Алгоритм Метод главных компонент Находит направления наибольшего разброса данных и описывает каждую точку немногими числами вдоль них. O(n·d² + d³) 2 задачи ML Алгоритм Рекомендации через разложение матрицы Тысяча книг, четыре тысячи читателей и десять чисел на каждого. Отметьте, что вам нравится, — и посмотрите, что предложит разложение матрицы. раунд ALS — O(N·k² + (u + i)·k³) 1 задача

Задачи

Вдоль какой линии Проверка за сервером Самый длинный безопасный шаг Сопротивление цепи Все остовные деревья Неявный шаг сквозь стену Погасить все лампочки Сжать климат до k чисел Сплав из лома Прямые генератора

Часто рядом

матрица 7 классика 6 граф 3 наука и физика 3 итерации 3 динамика 2 оптимизация 2 биоинформатика 2 олимпиады 2 подсчёт вариантов 2 точность вычислений 2 регрессия 2