Лааксонен А. Олимпиадное программирование

2-е изд., обновленное и дополненное. — Москва: ДМК Пресс, 2020. — 330 с. — ISBN 978-5-97060-878-4.Перед вами второе, обновленное издание книги, которая уже успела полюбиться читателям. Автор подробно описывает, как проходят олимпиады по программированию и как к ним готовиться, разбирает базовые темы, трюки и алгоритмы. В новых разделах рассматриваются темы повышенного уровня: вычисление преобразования Фурье, нахождение потоков минимальной стоимости в графах и использование конечных автоматов в задачах о строках.
Спортивное программирование - самый перспективный интеллектуальный вид спорта; уже сейчас им увлекаются лучшие умы планеты, и число участников растет год от года. Рост популярности олимпиадного программирования положительно влияет па другие сферы жизнедеятельности человека. Навыки быстрого решения сложнейших задач помогут сегодняшним студентам в будущем эффективно справляться с реальными проблемами человечества.
Издание будет полезно студентам факультетов информационных технологий и участникам олимпиад по программированию.От автора
Вступительное слово Алексея Малеева, основателя Moscow Workshops
Отзыв Дмитрия Гришина, основателя Mail. Ru Group
Благодарность от редакции
Отзыв Нияза Нигматуллина, двукратного чемпиона мира ACM ICPC 2012 и 2013 годов
Предисловие ко второму изданию
Предисловие к первому изданию
Введение
Что такое олимпиадное программирование?
Соревнования по программированию
Рекомендации желающим поучаствовать
Об этой книге
Сборник задач CSES
Другие ресурсы
Техника программирования
Языковые средства
Ввод и вывод
Работа с числами
Сокращение кода
Рекурсивные алгоритмы
Порождение подмножеств
Порождение перестановок
Перебор с возвратом
Поразрядные операции
Поразрядные операции
Представление множеств
Эффективность
Временная сложность
Правила вычисления
Часто встречающиеся оценки временной сложности
Оценка эффективности
Формальные определения
Примеры проектирования алгоритмов
Максимальная сумма подмассивов
Задача о двух ферзях
Оптимизация кода
Результат работы компилятора
Особенности процессора
Сортировка и поиск
Алгоритмы сортировки
Пузырьковая сортировка
Сортировка слиянием
Нижняя граница временной сложности сортировки
Сортировка подсчетом
Сортировка на практике
Решение задач с применением сортировки
Алгоритмы заметающей прямой
Составление расписания
Работы и сроки исполнения
Двоичный поиск
Реализация поиска
Двоичный поиск по ответу
Структуры данных
Динамические массивы
Векторы
Итераторы и диапазоны
Другие структуры данных
Множества
Множества и мультимножества
Отображения
Очереди с приоритетом
Множества, основанные на политиках
Эксперименты
Сравнение множества и сортировки
Сравнение отображения и массива
Сравнение очереди с приоритетом и мультимножества
Динамическое программирование
Основные понятия
Когда жадный алгоритм не работает
Нахождение оптимального решения
Подсчет решений
Другие примеры
Наибольшая возрастающая подпоследовательность
Пути на сетке
Задачи о рюкзаке
От перестановок к подмножествам
Подсчет количества замощений
Алгоритмы на графах
Основы теории графов
Терминология
Представление графа
Обход графа
Поиск в глубину
Поиск в ширину
Применения
Кратчайшие пути
Алгоритм Беллмана-Форда
Алгоритм Дейкстры
Алгоритм Флойда-Уоршелла
Ориентированные ациклические графы
Топологическая сортировка
Динамическое программирование
Графы преемников
Нахождение преемников
Обнаружение циклов
Минимальные остовные деревья
Алгоритм Краскала
Система непересекающихся множеств
Алгоритм Прима
Избранные вопросы проектирования алгоритмов
Алгоритмы с параллельным просмотром разрядов
Расстояние Хэмминга
Подсчет подсеток
Достижимость в графах
Амортизационный анализ
Метод двух указателей
Ближайшие меньшие элементы
Минимум в скользящем окне
Нахождение минимальных значений
Тернарный поиск
Выпуклые функции
Минимизация сумм
Запросы по диапазону
Запросы к статическим массивам
Запросы о сумме
Запросы о минимуме
Древовидные структуры
Двоичные индексные деревья
Деревья отрезков
Дополнительные приемы
Алгоритмы на деревьях
Базовые понятия
Обход дерева
Вычисление диаметра
Все максимальные пути
Запросы к деревьям
Нахождение предков
Поддеревья и пути
Наименьшие общие предки
Объединение структур данных
Более сложные приемы
Центроидная декомпозиция
Heavy-tight декомпозиция
Математика
Теория чисел
Простые числа и разложение на простые множители
Решето Эратосфена
Алгоритм Евклида
Возведение в степень по модулю
Теорема Эйлера
Решение уравнений в целых числах
Комбинаторика
Биномиальные коэффициенты
Числа Каталана
Включение-исключение
Лемма Бёрнсайда
Теорема Кэли
Матрицы
Операции над матрицами
Линейные рекуррентные соотношения
Графы и матрицы
Метод Гаусса
Вероятность
Операции с событиями
Случайные величины
Марковские цепи
Рандомизированные алгоритмы
Теория игр
Состояния игры
Игра ним
Теорема Шпрага-Гранди
Преобразование Фурье
Работа с полиномами
Алгоритм БПФ
Вычисление свертки
Дополнительные алгоритмы на графах
Сильная связность
Алгоритм Косарайю
Задача 2-выполнимости
Полные пути
Эйлеровы пути
Гамильтоновы пути
Применения
Максимальные потоки
Алгоритм Форда-Фалкерсона
Непересекающиеся пути;
Максимальные паросочетания
Покрытие путями
Деревья поиска в глубину
Двусвязность
Эйлеровы подграфы
Потоки минимальной стоимости
Алгоритм путей минимальной стоимости
Паросочетания минимального веса
Улучшение алгоритма
Геометрия
Технические средства в геометрии
Комплексные числа
Точки и прямые
Площадь многоугольника
Метрики
Алгоритмы на основе заметающей прямой
Точки пересечения
Задача о ближайшей паре точек
Задача о выпуклой оболочке
Алгоритмы работы со строками
Базовые методы
Префиксное дерево
Динамическое программирование
Хеширование строк
Полиномиальное хеширование
Применения
Коллизии и параметры
7-алгоритм
Построение Z-массива
Применения
Суффиксные массивы
Метод удвоения префикса
Поиск образцов
LCP-массивы
Строковые автоматы
Регулярные языки
Автоматы для сопоставления с образцом
Суффиксные автоматы
Дополнительные темы
Квадратный корень в алгоритмах
Структуры данных
Подалгоритмы
Целые разбиения
Алгоритм Мо
И снова о деревьях отрезков
Ленивое распространение
Динамические деревья
Структуры данных в вершинах
Двумерные деревья
Дучи
Разбиение и слияние
Реализация
Дополнительные методы
Оптимизация динамического программирования
Трюк с выпуклой оболочкой
Оптимизация методом «разделяй и властвуй»
Оптимизация Кнута
Методы перебора с возвратом
Отсечение ветвей дерева поиска
Эвристические функции
Разное
Встреча в середине
Подсчет подмножеств
Параллельный двоичный поиск
Динамическая связность
Приложение. Сведения из математики
Формулы сумм
Множества
Математическая логика
Функции
Логарифмы
Системы счисления
Библиография
Предметный указатель