Алгоритмика / CS

Анализ алгоритмов
Вычислительная сложность

Асимптотический анализ
Мастер-теорема

Сортировки

Сортировка пузырьком
Сортировка выбором
Сортировка вставками
Сортировка кучей
Сортировка подсчетом
Цифровая сортировка

Бинпоиск и интерактивки

Бинарный поиск
Бинарный поиск по ответу

Последовательности

Сжатие координат

Декомпозиция задач

Сканирующая прямая
Откатывание состояний
Корневые эвристики
Алгоритм Мо
Meet-in-the-middle

Арифметика

Битовое представление чисел
Векторизация

Структуры данных
Базовые структуры данных

Массивы и кортежи
Итераторы
Динамический массив
Двоичная куча

Деревья поиска

Деревья в STL
Декартово дерево
Неявный ключ

Структуры для множеств

Битсет и битовое сжатие
Система непересекающихся множеств

Запросы на отрезках

Префиксные суммы
Дерево Фенвика
Разреженная таблица
Корневые структуры

Персистентность

Структуры с откатами
Метод копирования пути
Персистентное дерево отрезков
Персистентное декартово дерево

Дерево отрезков

Дерево отрезков на указателях
Отложенные операции
Отложенное построение

Динамическое программирование
Общие приёмы динамики

Динамика по подотрезкам
Ленивая динамика

Комбинаторная оптимизация

Жадные алгоритмы
Матроиды
Метод отжига

Пересчет динамики по слоям

Оптимизация через разделяй-и-властвуй
Оптимизация Кнута
Convex Hull Trick
Дискретный метод Лагранжа

Теория игр

Игра «Ним»

Математика
Алгебра

Бинарное возведение в степень
Матрицы
Задачи на умножение матриц
Линейные уравнения
Многочлены
Интерполяция
Алгоритм Карацубы
Быстрое преобразование Фурье

Модулярная арифметика

Алгоритм Евклида
Расширенный алгоритм Евклида
«Деление» по модулю

Факторизация и простые числа

Решето Эратосфена
Ро-алгоритм Полларда

Графы
Обходы графов

Хранение графов
Поиск в глубину
Поиск компонент связности
Двудольные графы и раскраски
Нахождение цикла
Топологическая сортировка
Эйлеров цикл
Мосты и точки сочленения
Компоненты сильной связности
2-SAT

Кратчайшие пути

Пути в ациклических графах
Поиск в ширину
Алгоритм Дейкстры

Связность и остовные деревья

Лемма о безопасном ребре
Алгоритм Прима
Алгоритм Краскала
Алгоритм Борувки
Динамическая связность

Корневые деревья

Запросы на деревьях
Связь задачи LCA и static RMQ
Метод двоичных подъемов
Центроидная декомпозиция
Heavy-light декомпозиция

Паросочетания

Лемма Бержа
Алгоритм Куна
Задачи на паросочетания
Теорема о свадьбах

Потоки

Поток минимальной стоимости

Геометрия
Геометрические примитивы

Точки и вектора
Скалярное и векторное произведение
Прямые и отрезки
Многоугольники

Выпуклые оболочки

Применения выпуклых оболочек
Алгоритм Джарвиса
Алгоритм Грэхэма
Алгоритм Чана
Верхние и нижние огибающие

Строки
Поиск подстроки

Префикс-функция
Z-функция
Алгоритм Манакера

Хеширование

Полиномиальное хеширование
Коллизии хешей
Проверки на изоморфизм

Строковые структуры

Префиксное дерево
Алгоритм Ахо-Корасик
Дерево палиндромов
Суффиксный массив

Разное
Численные методы

Метод Ньютона
Методы Монте-Карло

Технологии программирования

Стресс-тестирование
Просто интересные задачи

Алгоритмы

Алгоритмы

Анализ алгоритмов

Вычислительная сложность

Асимптотический анализ
Мастер-теорема

Сортировки

Сортировка пузырьком
Сортировка выбором
Сортировка вставками
Сортировка кучей
Сортировка подсчетом
Цифровая сортировка

Бинпоиск и интерактивки

Бинарный поиск
Бинарный поиск по ответу

Последовательности

Сжатие координат

Декомпозиция задач

Сканирующая прямая
Откатывание состояний
Корневые эвристики
Алгоритм Мо
Meet-in-the-middle

Арифметика

Битовое представление чисел
Векторизация

Структуры данных

Базовые структуры данных

Массивы и кортежи
Итераторы
Динамический массив
Двоичная куча

Деревья поиска

Деревья в STL
Декартово дерево
Неявный ключ

Структуры для множеств

Битсет и битовое сжатие
Система непересекающихся множеств

Запросы на отрезках

Префиксные суммы
Дерево Фенвика
Разреженная таблица
Корневые структуры

Персистентность

Структуры с откатами
Метод копирования пути
Персистентное дерево отрезков
Персистентное декартово дерево

Дерево отрезков

Дерево отрезков на указателях
Отложенные операции
Отложенное построение

Динамическое программирование

Общие приёмы динамики

Динамика по подотрезкам
Ленивая динамика

Комбинаторная оптимизация

Жадные алгоритмы
Матроиды
Метод отжига

Пересчет динамики по слоям

Оптимизация через разделяй-и-властвуй
Оптимизация Кнута
Convex Hull Trick
Дискретный метод Лагранжа

Теория игр

Игра «Ним»

Математика

Бинарное возведение в степень
Матрицы
Задачи на умножение матриц
Линейные уравнения
Многочлены
Интерполяция
Алгоритм Карацубы
Быстрое преобразование Фурье

Модулярная арифметика

Алгоритм Евклида
Расширенный алгоритм Евклида
«Деление» по модулю

Факторизация и простые числа

Решето Эратосфена
Ро-алгоритм Полларда

Графы

Обходы графов

Хранение графов
Поиск в глубину
Поиск компонент связности
Двудольные графы и раскраски
Нахождение цикла
Топологическая сортировка
Эйлеров цикл
Мосты и точки сочленения
Компоненты сильной связности
2-SAT

Кратчайшие пути

Пути в ациклических графах
Поиск в ширину
Алгоритм Дейкстры

Связность и остовные деревья

Лемма о безопасном ребре
Алгоритм Прима
Алгоритм Краскала
Алгоритм Борувки
Динамическая связность

Корневые деревья

Запросы на деревьях
Связь задачи LCA и static RMQ
Метод двоичных подъемов
Центроидная декомпозиция
Heavy-light декомпозиция

Паросочетания

Лемма Бержа
Алгоритм Куна
Задачи на паросочетания
Теорема о свадьбах

Поток минимальной стоимости

Геометрия

Геометрические примитивы

Точки и вектора
Скалярное и векторное произведение
Прямые и отрезки
Многоугольники

Выпуклые оболочки

Применения выпуклых оболочек
Алгоритм Джарвиса
Алгоритм Грэхэма
Алгоритм Чана
Верхние и нижние огибающие

Строки

Поиск подстроки

Префикс-функция
Z-функция
Алгоритм Манакера

Хеширование

Полиномиальное хеширование
Коллизии хешей
Проверки на изоморфизм

Строковые структуры

Префиксное дерево
Алгоритм Ахо-Корасик
Дерево палиндромов
Суффиксный массив

Разное

Численные методы

Метод Ньютона
Методы Монте-Карло

Технологии программирования

Стресс-тестирование
Просто интересные задачи

В этот раздел с течением времени будут переноситься статьи с алгокода, емакса и старой алгоритмики.

Copyleft 2017–2022 Algorithmica.org
Материалы распространяются под CC BY-SA