Алгоритмы - Алгоритмика (original) (raw)

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

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

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

Сортировки

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

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

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

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

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

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

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

Арифметика

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теория игр

• Игра «Ним»

Математика

Алгебра

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

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

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

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

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

Графы

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

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

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

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

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

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

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

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

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

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

Потоки

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

Геометрия

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

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

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

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

Строки

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

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

Хеширование

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

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

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

Разное

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

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

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

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