Алгоритмика / 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