Наверх

Стивен С.Скиена, Мигель А.Ревилла, 2005 (Rus)
Олимпиадные задачи по программированию
Руководство по подготовке к соревнованиям Programming Challenges

Это бестселлер, признанный Journal of Object Technology как "Лучшая книга 2003 г.". 14 глав книги охватывают все основные категории задач международных соревнований. Каждая глава содержит необходимое теоретико-алгоритмическое введение, разбор типовых задач и серию тренировочных заданий уровня ACM (комментарий CHAS: по каждой из тем приведены условия 6-и задач. Не следует рассчитывать на полные пояснения, алгоритмы, разборы и т.п. Книга представляет собой список тем и типовых задач, рассматриваемых на олимпиадах АСМ. Языком частичных пояснений выбран С++)

Книга предназначена для учащихся, их преподавателей и тренеров, а также других специалистов, интересующихся олимпиадным программированием и алгоритмами. Не относится к серии "Учебник"


СОДЕРЖАНИЕ
ВВЕДЕНИЕ

ГЛАВА 1. НАЧАЛО РАБОТЫ
1.1 Начало работы с автоматической тестирующей системой
1.2 Выбор оружия
1.3 Советы по программированию
1.4 Элементарные типы данных
1.5 О задачах
1.6 Задачи (1.6.1 - 1.6.8)
1.7 Подсказки
1.8 Замечания

ГЛАВА 2. СТРУКТУРЫ ДАННЫХ
2.1 Элементарные структуры данных
2.2 Объектные библиотеки
2.3 пример разработки программы: сборы на войну
2.4 Что касается колоды
2.5 Строковый ввод/вывод
2.6 Победа на войне
2.7 Тестирование и отладка
2.8 Задачи (2.6.8 - 2.8.8)
2.9 Подсказки
2.10 Замечание

ГЛАВА 3. СТРОКИ
3.1 Коды символов
3.2 Представление строк
3.3 Пример разработки программы: корпоративные переименования
3.4 Поиск шаблонов
3.5 Управление строками
3.6 Завершение программы
3.7 Функции библиотеки для работы со строками
3.8 Задачи (3.8.1 - 3.8.8)
3.9 Подсказки
3.10 Замечания

ГЛАВА 4. СОРТИРОВКА
4.1 Приложения сортировки
4.2 Алгоритмы сортировки
4.3 Пример разработки программы: рейтинг ухажеров
4.4 Функции библиотеки сортировки
4.5 рейтинг ухажеров
4.6 Задачи (4.6.1 - 4.6.8)
4.7 Подсказки
4.8 Замечания

ГЛАВА 5. АРИФМЕТИКА И АЛГЕБРА
5.1 Машинная арифметика
5.2 Высокоточные целые числа
5.3 Высокоточная арифметика
5.4 Системы счисления и соответствующие переходы
5.5 Вещественные числа
5.6 Алгебра
5.7 Логарифмы
5.8 Математические библиотеки
5.9 Задачи (5.9.1 - 5.9.8)
5.10 Подсказки
5.11 Замечания

ГЛАВА 6. КОМБИНАТОРИКА
6.1 Базовые методы счета
6.2 Рекуррентные соотношения
6.3 Биномиальные коэффициенты
6.4 Другие счетные последовательности
6.5 Рекурсия и индукция
6.6 Задачи (6.6.1 - 6.6.8)
6.7 Подсказки
6.8 Замечания

ГЛАВА 7. ТЕОРИЯ ЧИСЕЛ
7.1 Простые числа
7.2 Делимость
7.3 Арифметика остатков
7.4 Сравнимости
7.5 Библиотека по теории чисел
7.6 Задачи (7.6.1 - 7.6.8)
7.7 Подсказки
7.8 Замечания

ГЛАВА 8. ПОИСК С ВОЗВРАТОМ
8.1 Поиск с возвратом
8.2 Построение всех подмножеств
8.3 Построение всех перестановок
8.4 Пример разработки программы: задачи восьми ферзей
8.5 Поиск с отсечением вариантов
8.6 Задачи (8.6.1 - 8.6.8)
8.7 Подсказки
8.8 Замечания

ГЛАВА 9. ОБХОДЫ ГРАФОВ
9.1 Особенности графов
9.2 Структура данных для графов
9.3 Обход графа в ширину
9.4 Обход графа в глубину
9.5 Топологическая сортировка
9.6 Задачи (9.6.1 - 9.6.8)
9.7 Подсказки

ГЛАВА 10. ГРАФОВЫЕ АЛГОРИТМЫ
10.1 Теория графов
10.2 Минимальные остовные деревья
10.3 Кратчайшие пути
10.4 Потоки в сети и паросочетания в двудольных графах
10.5 Задачи (10.5.1 - 10.5.8)
10.6 Подсказки

ГЛАВА 11. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
11.1 Не нужно жадничать
11.2 Стоимость редактирования
11.3 Восстановление пути
11.4 Варианты стоимости редактирования
11.5 Пример разработки программы: оптимизация лифта
11.6 Задачи (11.6.1 - 11.6.8)
11.7 Подсказки
11.8 Замечания

ГЛАВА 12. СЕТКИ
12.1 Прямолинейные сетки
12.2 Треугольные и гексагональные сетки
12.3 Пример разработки программы: вес тарелки
12.4 Упаковка кругов
12.5 Широта и долгота
12.6 Задачи (12.6.1 - 12.6.8)
12.7 Подсказки

ГЛАВА 13. ГЕОМЕТРИЯ
13.1 Прямые
13.2 Треугольники и тригонометрия
13.3 Окружности
13.4 Пример разработки программы: быстрее пули
13.5 Библиотека тригонометрических функций
13.6 Задачи (13.6.1 - 13.6.8)
13.7 Подсказки

ГЛАВА 14. ВЫЧИСЛИТЕЛЬНАЯ ГЕОМЕТРИЯ
14.1 Отрезки и пересечения
14.2 Многоугольники и вычисление углов
14.3 Выпуклые оболочки
14.4 Триангуляция: алгоритмы и смежные задачи
14.5 Алгоритмы для сеток
14.6 Геометрические библиотеки
14.7 Задачи (14.6.1 - 14.6.8)
14.8 Подсказки

ПРИЛОЖЕНИЕ А
А1. ACM International Collegiate Programming Contest
  1.1 Подготовка
  1.2 Проведение: стратегия и тактика
А2. International Olimpiad on informatics
(международная олимпиада по информатике)
  2.1 Участие
  2.2 Формат
  2.3 Подготовка
А3. TopCoder.com
A4. Аспирантура
А5. Благодарности за задачи

СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ