Алгоритмический тренинг, Решения практических задач на Python и C++, Иванов М.К., 2023

Алгоритмический тренинг, Решения практических задач на Python и C++, Иванов М.К., 2023.

   Опираясь на богатый соревновательный и эвристический опыт, автор предлагает оригинальные реализации классических алгоритмов Computer Science на языках Python и C++. Особое внимание уделено математическим и геометрическим алгоритмам, графовым алгоритмам, структурам данных (в особенности различным деревьям), комбинаторике и работе со строками. Книга поможет заложить и расширить алгоритмическую подготовку, познакомит с эффективными решениями вычислительных задач, а для обучающихся станет настольной. Поможет подготовиться к экзаменам, сертификации, олимпиадам по программированию.




Геометрия на плоскости. Основы.
Несмотря на то что для реализации базовых примитивов вычислительной геометрии достаточно минимальных знаний из области математики, написание надежного, компактного и быстрого кода — не самая простая задача. Многие сложности проистекают от наличия всевозможных особых случаев (например, совпадающие или лежащие на одной прямой точки) и от стремления производить операции в целых числах (для избегания, по возможности, ошибок округления).

Отметим, что приведенные ниже реализации ориентированы на спортивное программирование и на объяснение принципа работы алгоритмов. Повторное использование кода сведено к минимуму, и отсутствуют абстракции вида «отрезок» или «многоугольник», которые были бы в духе объектно-ориентированного или структурного программирования. Цель этой главы, как и книги в целом — не создать переиспользуемую библиотеку стандартных алгоритмов (что имеет мало смысла в реальном мире, где уже существует целый ряд тщательно спроектированных и отлаженных библиотек). Вместо этого акцент в нашей книге — на том, как устроены эти стандартные алгоритмы, из каких предпосылок они выводятся и каким образом можно быстро и компактно самостоятельно реализовать их для конкретной задачи.

ОГЛАВЛЕНИЕ.
ВВЕДЕНИЕ.
Глава 1. Для кого эта книга.
Глава 2. Чему обучит эта книга.
Глава 3. Спортивное и промышленное программирование.
Глава 4. Как пользоваться книгой.
СТУПЕНЬ I. РАЗМИНКА.
Глава 5. Вводные задачи.
5.1. A+B.
5.2. Пример решения задачи. Числа Фибоначчи.
5.3. Пример решения задачи. Манхэттенское расстояние.
5.4. Пример решения задачи. Путь до ксерокса.
5.5. Пример решения задачи. Проверка перестановки.
5.6. Пример решения задачи. Циклы перестановки.
Глава 6. Разминочные конструктивные задачи.
6.1. Пример решения задачи. Пара с минимальным произведением.
6.2. Пример решения задачи. Тайная жизнь деревьев.
6.3. Пример решения задачи. Подписывание открыток.
6.4. Пример решения задачи. Исправление перестановки.
6.5. Пример решения задачи. Минимальный палиндром.
6.6. Пример решения задачи. Исключающее ИЛИ от 1 до n.
6.7. Пример решения задачи. Врачи и посетители.
6.8. Пример решения задачи. Минимизация перепадов.
6.9. Пример решения задачи. Одномерный геометрический центр.
Глава 7. Разминочные реализационные задачи.
7.1. Пример решения задачи. Морской бой.
7.2. Пример решения задачи. Стоимость интернет-связи.
7.3. Пример решения задачи. Пересечение двух прямоугольников.
7.4. Пример решения задачи. Проверка скобочной последовательности.
7.5. Пример решения задачи. Проверка скобочной последовательности с двумя типами.
7.6. Пример решения задачи. Зеркальный лабиринт.
7.6. Пример решения задачи. Троичная сбалансированная система счисления.
Глава 8. Задачи для самостоятельного решения.
8.1. Примеры задач.
8.2. Задачи в онлайн-системах.
Итоги ступени I.
СТУПЕНЬ II. БАЗОВЫЕ АЛГОРИТМЫ.
Глава 9. Оценка скорости работы алгоритмов.
9.1. Эмпирическая скорость процессора.
9.2. Асимптотическая оценка. Основы.
9.3. Практическая применимость асимптотических оценок.
9.4. Библиотечные реализации алгоритмов и их скорость.
Глава 10. Наибольший общий делитель. Алгоритм Евклида.
10.1. Постановка задачи.
10.2. Тривиальный алгоритм.
10.3. Алгоритм Евклида.
10.4. Доказательство алгоритма Евклида.
10.5. Реализация алгоритма Евклида.
10.6. Время работы алгоритма Евклида.
10.7. Пример решения задачи. Сокращение дроби.
10.8. Пример решения задачи. Наименьшее общее кратное.
10.9. Пример решения задачи. НОД нескольких чисел.
10.10. Пример решения задачи. Увеличение НОД массива.
10.11. Упражнения для самостоятельного решения.
Глава 11. Простые задачи на учет асимптотики.
11.1. Пример решения задачи. Префиксы перестановки.
11.2. Пример решения задачи. Парковочные места.
Глава 12. Объединение одномерных отрезков.
12.1. Постановка задачи.
12.2. Алгоритм объединения отрезков.
12.3. Реализация алгоритма объединения отрезков.
12.4. Пример решения задачи. Часы приема.
12.5. Пример решения задачи. Стрельба по отрезкам.
12.6. Пример решения задачи. Многослойная покраска.
Глава 13. Метод двух указателей.
13.1. Пример решения задачи. Пары фиксированной суммы.
13.2. Пример решения задачи. Длиннейший подотрезок без повторов.
13.3. Пример решения задачи. Подотрезки со всеми числами.
13.4. Пример решения задачи. Трехцветный забор.
Глава 14. Двоичный поиск.
14.1. Базовая задача: поиск в упорядоченном массиве.
14.2. Алгоритм двоичного поиска.
14.3. Реализация алгоритма двоичного поиска.
14.4. Библиотечные реализации.
14.5. Пример решения задачи. Подсчет меньших чисел.
14.6. Пример решения задачи. Грузовой лифт в отеле.
14.7. Пример решения задачи. Дисплеи для смартфонов.
14.8. Пример решения задачи. Прыжки лягушки.
14.9. Пример решения задачи. Корень уравнения.
14.10. Прочие применения двоичного поиска.
Глава 15. Проверка на простоту и факторизация.
15.1. Определения.
15.2. Общие сведения о простых числах и о факторизации.
15.3. Проверка числа на простоту. Базовый алгоритм.
15.4. Факторизация числа. Базовый алгоритм.
15.5. Пример решения задачи. Подсчет числа делителей.
15.6. Пример решения задачи. Иррациональный портной.
15.7. Пример решения задачи. Произведения-квадраты.
15.8. Пример решения задачи. Запросы числа делителей.
Глава 16. Динамическое программирование. Основы.
16.1. Пример решения задачи. Сумма однообразных чисел.
16.2. Пример решения задачи. Наидлиннейшая возрастающая подпоследовательность.
16.3. Пример решения задачи. Подмножество с заданной суммой.
16.4. Пример решения задачи. Минимальное подмножество с заданной суммой.
16.5. Пример решения задачи. Получение суммы монетами заданных номиналов.
16.6. Пример решения задачи. Задача о рюкзаке.
16.7. Пример решения задачи. Кладоискатель.
16.8. Пример решения задачи. Путь в матрице.
16.9. Пример решения задачи. Расстояние редактирования.
Глава 17. Задачи для самостоятельного решения.
17.1. Примеры задач.
17.2. Задачи в онлайн-системах.
Итоги ступени II.
СТУПЕНЬ III. РАСШИРЕНИЕ БАЗОВОГО АРСЕНАЛА.
Глава 18. Техники предварительного подсчета на массивах.
18.1. Указатели до ближайших элементов.
18.2. Частичные суммы.
18.3. Указатели до ближайших меньших элементов.
18.4. Списки позиций.
18.5. Сжатие значений.
18.6. Пример решения задачи. Поиск начала слова.
18.7. Пример решения задачи. Два подотрезка заданной длины с максимальной суммой.
18.8. Пример решения задачи. Подсчет чисел в подотрезках.
18.9. Пример решения задачи. Подотрезок с максимальной суммой.
18.10. Пример решения задачи. Проекционная реклама.
18.11. Пример решения задачи. Подотрезок с максимальным средним арифметическим.
18.12. Пример решения задачи. Сумма в прямоугольнике.
Глава 19. Графы. Обход в глубину.
19.1. Что такое граф.
19.2. Ориентированные и неориентированные графы.
19.3. Способы представления графов в компьютере.
19.4. Алгоритм обхода в глубину.
19.5. Реализация обхода в глубину.
19.6. Пример решения задачи. Проверка наличия пути.
19.7. Пример решения задачи. Конная прогулка.
19.8. Пример решения задачи. Проверка связности.
19.9. Пример решения задачи. Проверка двудольного графа.
19.10. Пример решения задачи. Проверка орграфа на ацикличность.
19.11. Пример решения задачи. Топологическая сортировка.
19.12. Пример решения задачи. Диаметр дерева.
Глава 20. Графы. Обход в ширину.
20.1. Алгоритм обхода в ширину.
20.2. Свойства обхода в ширину.
20.3. Реализация обхода в ширину.
20.4. Пример решения задачи. Кластер компьютеров.
20.5. Пример решения задачи. Робот в лабиринте.
20.6. Пример решения задачи. Наводнение.
Глава 21. Решето Эратосфена.
21.1. Алгоритм решета Эратосфена.
21.2. Демонстрация работы алгоритма.
21.3. Доказательство корректности решета Эратосфена.
21.4. Время работы решета Эратосфена.
21.5. Базовые оптимизации решета Эратосфена.
21.6. Реализация решета Эратосфена.
21.7. Дальнейшие оптимизации решета Эратосфена.
21.8. Пример решения задачи. Подсчет простых чисел в отрезке.
Глава 22. Двоичное возведение в степень.
22.1. Ключевая идея.
22.2. Алгоритм двоичного возведения в степень.
22.3. Иллюстрация работы алгоритма.
22.4. Время работы двоичного возведения в степень.
22.5. Реализация двоичного возведения в степень.
22.6. Пример решения задачи. Последние цифры степени.
22.7. Пример решения задачи. Обратное по простому модулю. Малая теорема Ферма.
22.8. Пример решения задачи. Быстрое вычисление чисел Фибоначчи. Двоичное возведение матриц в степень.
22.9. Пример решения задачи. Физический движок.
22.10. Пример решения задачи. Подсчет путей фиксированной длины.
Глава 23. Структуры данных. Дерево отрезков.
23.1. Базовый вариант. Дерево для минимумов.
23.2. Дерево отрезков для максимумов.
23.3. Дерево отрезков с запросами модификации.
23.4. Дерево отрезков для сумм.
23.5. Прочие виды операций в дереве отрезков.
23.6. Запросы обновления на отрезке.
23.7. Дальнейшие обобщения дерева отрезков.
23.8. Пример решения задачи. Наидлиннейшая возрастающая подпоследовательность (быстрый вариант).
23.9. Пример решения задачи. Наименьший общий предок.
Глава 24. Задачи для самостоятельного решения.
24.1. Примеры задач.
24.2. Задачи в онлайн-системах.
СТУПЕНЬ IV. РАЗНОСТОРОННЯЯ ПОДГОТОВКА.
Глава 25. Производительность ввода-вывода.
25.1. Производительность ввода-вывода в Python.
25.2. Производительность ввода-вывода в C++.
Глава 26. Графы. Алгоритм Дейкстры.
26.1. Постановка задачи поиска кратчайших путей.
26.2. Пример.
26.3. Алгоритм Дейкстры.
26.4. Ограничения алгоритма Дейкстры.
26.5. Пример работы алгоритма Дейкстры.
26.6. Восстановление кратчайшего пути.
26.7. Доказательство алгоритма Дейкстры.
26.8. Квадратичная реализация алгоритма Дейкстры.
26.9. Алгоритм Дейкстры для разреженных графов.
26.10. Пример решения задачи. Оптимальный путь четной длины.
26.11. Пример решения задачи. Ребра кратчайших путей.
Глава 27. Графы. Компоненты сильной связности.
27.1. Определения.
27.2. Алгоритм поиска компонент сильной связности.
27.3. Доказательство алгоритма.
27.4. Демонстрация работы алгоритма.
27.5. Временная сложность алгоритма.
27.6. Реализация алгоритма.
27.7. Дополнительные свойства алгоритма.
27.8. Пример решения задачи. Железнодорожный вокзал.
27.9. Пример решения задачи. Задача умозаключенного.
27.10. Пример решения задачи. Сбор дани.
Глава 28. Работа с вещественными числами.
28.1. Формат чисел с плавающей запятой.
28.2. Проблемы чисел с плавающей запятой.
28.3. Приемы работы с числами с плавающей запятой.
Глава 29. Геометрия на плоскости. Основы.
29.1. Расстояние между точками.
29.2. Косое произведение векторов.
29.3. Скалярное произведение векторов.
29.4. Площадь треугольника.
29.5. Направление поворота. Ориентированная площадь треугольника.
29.6. Площадь многоугольника.
29.7. Проверка точки на принадлежность прямой.
29.8. Проверка точки на принадлежность отрезку.
29.9. Проверка двух отрезков на пересечение.
29.10. Расстояние от точки до прямой.
29.11. Расстояние от точки до отрезка.
29.12. Точка пересечения двух прямых.
29.13. Точка пересечения двух отрезков.
29.14. Матрица поворота.
29.15. Пример решения задачи. Проверка окружностей на пересечение.
29.16. Пример решения задачи. Пересечение окружности и прямой.
29.17. Пример решения задачи. Сортировка точек по углу.
Глава 30. Расширенный алгоритм Евклида.
30.1. Алгоритм.
30.2. Доказательство.
30.3. Реализация расширенного алгоритма Евклида.
30.4. Пример решения задачи. Прыжки вперед и назад.
30.5. Пример решения задачи. Линейное диофантово уравнение с двумя переменными.
30.6. Пример решения задачи. Обратное по составному модулю.
Глава 31. Задачи для самостоятельного решения.
31.1. Примеры задач.
ЗАКЛЮЧЕНИЕ.
Методики решения задач.
Благодарности.
Послесловие.
Приложение. Решения задач.
Задачи из главы 8.
Задачи из главы 10.
Задачи из главы 17.
Задачи из главы 24.
Задачи из главы 31.
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ.

Купить .





Теги: учебник по программированию :: программирование :: Иванов