Олимпиадное программирование : изучение и улучшение алгоритмов на соревнованиях

Содержание книги "Олимпиадное программирование : изучение и улучшение алгоритмов на соревнованиях"

От автора
Вступительное слово Алексея Малеева, основателя Moscow Workshops
Отзыв Дмитрия Гришина, основателя Mail.Ru Group
Благодарность от редакции
Отзыв Нияза Нигматуллина, двукратного чемпиона мира ACM ICPC 2012 и 2013 годов
Предисловие ко второму изданию
Предисловие к первому изданию
Глава 1. Введение
1.1. Что такое олимпиадное программирование?
1.1.1. Соревнования по программированию
1.1.2. Рекомендации желающим поучаствовать
1.2. Об этой книге
1.3. Сборник задач CSES
1.4. Другие ресурсы
Глава 2. Техника программирования
2.1. Языковые средства
2.1.1. Ввод и вывод
2.1.2. Работа с числами
2.1.3. Сокращение кода
2.2. Рекурсивные алгоритмы
2.2.1. Порождение подмножеств
2.2.2. Порождение перестановок
2.2.3. Перебор с возвратом
2.3. Поразрядные операции
2.3.1. Поразрядные операции
2.3.2. Представление множеств
Глава 3. Эффективность
3.1. Временная сложность
3.1.1. Правила вычисления
3.1.2. Часто встречающиеся оценки временной сложности
3.1.3. Оценка эффективности
3.1.4. Формальные определения
3.2. Примеры проектирования алгоритмов
3.2.1. Максимальная сумма подмассивов
3.2.2. Задача о двух ферзях
3.3. Оптимизация кода
3.3.1. Результат работы компилятора
3.3.2. Особенности процессора
Глава 4. Сортировка и поиск
4.1. Алгоритмы сортировки
4.1.1. Пузырьковая сортировка
4.1.2. Сортировка слиянием
4.1.3. Нижняя граница временной сложности сортировки
4.1.4. Сортировка подсчетом
4.1.5. Сортировка на практике
4.2. Решение задач с применением сортировки
4.2.1. Алгоритмы заметающей прямой
4.2.2. Составление расписания
4.2.3. Работы и сроки исполнения
4.3. Двоичный поиск
4.3.1. Реализация поиска
4.3.2. Двоичный поиск по ответу
Глава 5. Структуры данных
5.1. Динамические массивы
5.1.1. Векторы
5.1.2. Итераторы и диапазоны
5.1.3. Другие структуры данных
5.2. Множества
5.2.1. Множества и мультимножества
5.2.2. Отображения
5.2.3. Очереди с приоритетом
5.2.4. Множества, основанные на политиках
5.3. Эксперименты
5.3.1. Сравнение множества и сортировки
5.3.2. Сравнение отображения и массива
5.3.3. Сравнение очереди с приоритетом и мультимножества
Глава 6. Динамическое программирование
6.1. Основные понятия
6.1.1. Когда жадный алгоритм не работает
6.1.2. Нахождение оптимального решения
6.1.3. Подсчет решений
6.2. Другие примеры
6.2.1. Наибольшая возрастающая подпоследовательность
6.2.2. Пути на сетке
6.2.3. Задачи о рюкзаке
6.2.4. От перестановок к подмножествам
6.2.5. Подсчет количества замощений
Глава 7. Алгоритмы на графах
7.1. Основы теории графов
7.1.1.Терминология
7.1.2. Представление графа
7.2. Обход графа
7.2.1. Поиск в глубину
7.2.2. Поиск в ширину
7.2.3. Применения
7.3. Кратчайшие пути
7.3.1. Алгоритм Беллмана–Форда
7.3.2. Алгоритм Дейкстры
7.3.3. Алгоритм Флойда–Уоршелла
7.4. Ориентированные ациклические графы
7.4.1. Топологическая сортировка
7.4.2. Динамическое программирование
7.5. Графы преемников
7.5.1. Нахождение преемников
7.5.2. Обнаружение циклов
7.6. Минимальные остовные деревья
7.6.1. Алгоритм Краскала
7.6.2. Система непересекающихся множеств
7.6.3. Алгоритм Прима
Глава 8. Избранные вопросы проектирования алгоритмов
8.1. Алгоритмы с параллельным просмотром разрядов
8.1.1. Расстояние Хэмминга
8.1.2. Подсчет подсеток
8.1.3. Достижимость в графах
8.2. Амортизационный анализ
8.2.1. Метод двух указателей
8.2.2. Ближайшие меньшие элементы
8.2.3. Минимум в скользящем окне
8.3. Нахождение минимальных значений
8.3.1. Тернарный поиск
8.3.2. Выпуклые функции
8.3.3. Минимизация сумм
Глава 9. Запросы по диапазону
9.1. Запросы к статическим массивам
9.1.1. Запросы о сумме
9.1.2. Запросы о минимуме
9.2. Древовидные структуры
9.2.1. Двоичные индексные деревья
9.2.2. Деревья отрезков
9.2.3. Дополнительные приемы
Глава 10. Алгоритмы на деревьях
10.1. Базовые понятия
10.1.1. Обход дерева
10.1.2. Вычисление диаметра
10.1.3. Все максимальные пути
10.2. Запросы к деревьям
10.2.1. Нахождение предков
10.2.2. Поддеревья и пути
10.2.3. Наименьшие общие предки
10.2.4. Объединение структур данных
10.3. Более сложные приемы
10.3.1. Центроидная декомпозиция
10.3.2. Heavy-light декомпозиция
Глава 11. Математика
11.1. Теория чисел
11.1.1. Простые числа и разложение на простые множители
11.1.2. Решето Эратосфена
11.1.3. Алгоритм Евклида
11.1.4. Возведение в степень по модулю
11.1.5. Теорема Эйлера
11.1.6. Решение уравнений в целых числах
11.2. Комбинаторика
11.2.1. Биномиальные коэффициенты
11.2.2. Числа Каталана
11.2.3. Включение-исключение
11.2.4. Лемма Бёрнсайда
11.2.5. Теорема Кэли
11.3. Матрицы
11.3.1. Операции над матрицами
11.3.2. Линейные рекуррентные соотношения
11.3.3. Графы и матрицы
11.3.4. Метод Гаусса
11.4. Вероятность
11.4.1. Операции с событиями
11.4.2. Случайные величины
11.4.3. Марковские цепи
11.4.4. Рандомизированные алгоритмы
11.5. Теория игр
11.5.1. Состояния игры
11.5.2. Игра ним
11.5.3. Теорема Шпрага–Гранди
11.6. Преобразование Фурье
11.6.1. Работа с полиномами
11.6.2. Алгоритм БПФ
11.6.3. Вычисление свертки
Глава 12. Дополнительные алгоритмы на графах
12.1. Сильная связность
12.1.1. Алгоритм Косарайю
12.1.2. Задача 2-выполнимости
12.2. Полные пути
12.2.1. Эйлеровы пути
12.2.2. Гамильтоновы пути
12.2.3. Применения
12.3. Максимальные потоки
12.3.1. Алгоритм Форда–Фалкерсона
12.3.2. Непересекающиеся пути
12.3.3. Максимальные паросочетания
12.3.4. Покрытие путями
12.4. Деревья поиска в глубину
12.4.1. Двусвязность
12.4.2. Эйлеровы подграфы
12.5. Потоки минимальной стоимости
12.5.1. Алгоритм путей минимальной стоимости
12.5.2. Паросочетания минимального веса
12.5.3. Улучшение алгоритма
Глава 13. Геометрия
13.1. Технические средства в геометрии
13.1.1. Комплексные числа
13.1.2. Точки и прямые
13.1.3. Площадь многоугольника
13.1.4. Метрики
13.2. Алгоритмы на основе заметающей прямой
13.2.1. Точки пересечения
13.2.2. Задача о ближайшей паре точек
13.2.3. Задача о выпуклой оболочке
Глава 14. Алгоритмы работы со строками
14.1. Базовые методы
14.1.1. Префиксное дерево
14.1.2. Динамическое программирование
14.2. Хеширование строк
14.2.1. Полиномиальное хеширование
14.2.2. Применения
14.2.3. Коллизии и параметры
14.3. Z-алгоритм
14.3.1. Построение Z-массива
14.3.2. Применения
14.4. Суффиксные массивы
14.4.1. Метод удвоения префикса
14.4.2. Поиск образцов
14.4.3. LCP-массивы
14.5. Строковые автоматы
14.5.1. Регулярные языки
14.5.2. Автоматы для сопоставления с образцом
14.5.3. Суффиксные автоматы
Глава 15. Дополнительные темы
15.1. Квадратный корень в алгоритмах
15.1.1. Структуры данных
15.1.2. Подалгоритмы
15.1.3. Целые разбиения
15.1.4. Алгоритм Мо
15.2. И снова о деревьях отрезков
15.2.1. Ленивое распространение
15.2.2. Динамические деревья
15.2.3. Структуры данных в вершинах
15.2.4. Двумерные деревья
15.3. Дучи
15.3.1. Разбиение и слияние
15.3.2. Реализация
15.3.3. Дополнительные методы
15.4. Оптимизация динамического программирования
15.4.1. Трюк с выпуклой оболочкой
15.4.2. Оптимизация методом «разделяй и властвуй»
15.4.3. Оптимизация Кнута
15.5. Методы перебора с возвратом
15.5.1. Отсечение ветвей дерева поиска
15.5.2. Эвристические функции
15.6. Разное
15.6.1. Встреча в середине
15.6.2. Подсчет подмножеств
15.6.3. Параллельный двоичный поиск
15.6.4. Динамическая связность
Приложение. Сведения из математики
Формулы сумм
Множества
Математическая логика
Функции
Логарифмы
Системы счисления
Библиография
Предметный указатель