Олимпиадное программирование: изучение и улучшение алгоритмов на соревнованиях
Покупка
Тематика:
Программирование и алгоритмизация
Издательство:
ДМК Пресс
Автор:
Лааксонен Антти
Год издания: 2020
Кол-во страниц: 328
Дополнительно
Вид издания:
Практическое пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-97060-878-4
Артикул: 746441.02.99
К покупке доступен более свежий выпуск
Перейти
Перед вами второе, обновленное издание книги, которая уже успела полюбиться читателям. Автор подробно описывает, как проходят олимпиады по программированию и как к ним готовиться, разбирает базовые темы, трюки и алгоритмы. В новых разделах рассматриваются темы повышенного уровня: вычисление преобразования Фурье, нахождение потоков минимальной стоимости в графах и использование конечных автоматов в задачах о строках.
Спортивное программирование - самый перспективный интеллектуальный вид спорта; уже сейчас им увлекаются лучшие умы планеты, и число участников растет год от года. Рост популярности олимпиадного программирования положительно влияет на другие сферы жизнедеятельности человека. Навыки быстрого решения сложнейших задач помогут сегодняшним студентам в будущем эффективно справляться с реальными проблемами человечества.
Издание будет полезно студентам факультетов информационных технологий и участникам олимпиад по программированию.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 09.03.01: Информатика и вычислительная техника
- 09.03.02: Информационные системы и технологии
- 09.03.03: Прикладная информатика
- 09.03.04: Программная инженерия
- ВО - Магистратура
- 09.04.01: Информатика и вычислительная техника
- 09.04.02: Информационные системы и технологии
- 09.04.03: Прикладная информатика
- 09.04.04: Программная инженерия
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Интернетмагазин:
www.dmkpress.com
Оптовая продажа:
КТК «Галактика»
books@alians-kniga.ru
www.дмк.рф
Антти Лааксонен
Перед вами новое, дополненное издание замечательной книги, которая
уже выдержала проверку временем. Автор всесторонне освещает темы,
актуальные для современного спортивного программирования. Олимпиадное программирование – прекрасный способ изучить алгоритмы, усовершенствовать навыки кодирования и отладки и сформировать особый
тип мышления, необходимый для решения задач в условиях соревнования.
9 785970 608784
ISBN 978-5-97060-878-4
Д-р Антти Лааксонен (Antti Laaksonen) работает преподавателем и исследователем в Хельсинкском университете и университете Аалто в Финляндии. С
2008 года один из организаторов Финляндской олимпиады по информатике; в
2016 году был научным руководителем Балтийской олимпиады по информатике.
Выступал в качестве тренера и руководителя команды Финляндии на нескольких
международных соревнованиях по программированию, в том числе на Международных олимпиадах по информатике 2009 и 2016 года. Имеет обширный опыт
преподавания программирования и алгоритмов.
Рассматриваемые темы:
• краткий обзор языка программирования C++;
• математические вопросы, существенные для олимпиадного
программирования;
• создание эффективных алгоритмов, способных быстро обрабатывать
большие наборы данных;
• введение в динамическое программирование;
• алгоритмы на графах, геометрические алгоритмы, методы работы
со строками;
• алгоритмы, в которых используется идея квадратного корня;
• оптимизация динамического программирования;
• вычисление преобразования Фурье;
• нахождение потоков минимальной стоимости в графах;
• использование конечных автоматов в задачах о строках.
Предполагается, что читатель знаком с основами программирования,
однако опыт проектирования алгоритмов или участия в олимпиадах необязателен.
Издание станет идеальным справочным пособием для всех читателей,
интересующихся алгоритмами и желающих набраться опыта перед участием в соревнованиях по программированию. Благодаря широкому кругу
освещаемых тем разного уровня сложности книга будет интересна как
начинающим, так и более опытным читателям.
Олимпиадное
программирование
Олимпиадное программирование
Издание второе,
обновленное и дополненное
Второе
издание
Антти Лааксонен Олимпиадное программирование Изучение и улучшение алгоритмов на соревнованиях 2-е издание, обновленное и дополненное
Guide to Competitive Programming Learning and Improving Algorithms Through Contests Second Edition Antti Laaksonen
Москва, 2020 Олимпиадное программирование Изучение и улучшение алгоритмов на соревнованиях 2-е издание, обновленное и дополненное Антти Лааксонен
УДК 004.02: 004.424
ББК 22.18
Л12
Л12 Антти Лааксонен
Олимпиадное программирование. 2-е изд., обновленное и дополненное / пер. с англ. А. А. Слинкин – М.: ДМК Пресс, 2020. – 328 с.: ил.
ISBN 978-5-97060-878-4
Перед вами второе, обновленное издание книги, которая уже успела полюбиться читателям. Автор подробно описывает, как проходят олимпиады по
программированию и как к ним готовиться, разбирает базовые темы, трюки и
алгоритмы. В новых разделах рассматриваются темы повышенного уровня: вычисление преобразования Фурье, нахождение потоков минимальной стоимости
в графах и использование конечных автоматов в задачах о строках.
Спортивное программирование – самый перспективный интеллектуальный
вид спорта; уже сейчас им увлекаются лучшие умы планеты, и число участников растет год от года. Рост популярности олимпиадного программирования
положительно влияет на другие сферы жизнедеятельности человека. Навыки
быстрого решения сложнейших задач помогут сегодняшним студентам в будущем эффективно справляться с реальными проблемами человечества.
Издание будет полезно студентам факультетов информационных технологий
и участникам олимпиад по программированию.
УДК 004.02: 004.424
ББК 22.18
Original English language edition published by Springer International Publishing
AG. Copyright ©Springer International Publishing AG, part of Springer Nature 2020. All
rights reserved. This edition has been translated and published under licence from Springer
International Publishing AG. Russian-language edition copyright © 2020 by DMK Press. All
rights reserved.
Все права защищены. Любая часть этой книги не может быть воспроизведена в
какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероятность технических ошибок все равно существует, издательство не может гарантировать
абсолютную точность и правильность приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги.
ISBN 978-3-030-39357-1 (англ.) © Springer Nature Switzerland AG, 2020
ISBN 978-5-97060-878-4 (рус.) © Оформление, перевод на русский язык,
издание, ДМК Пресс, 2020
Оглавление От автора .......................................................................................................................11 Вступительное слово Алексея Малеева, основателя Moscow Workshops ............. 11 Отзыв Дмитрия Гришина, основателя Mail.Ru Group .............................................13 Благодарность от редакции .......................................................................................13 Отзыв Нияза Нигматуллина, двукратного чемпиона мира ACM ICPC 2012 и 2013 годов .....................................................................................14 Предисловие ко второму изданию ...........................................................................15 Предисловие к первому изданию .............................................................................16 Глава 1. Введение .........................................................................................................18 1.1. Что такое олимпиадное программирование? .................................................... 18 1.1.1. Соревнования по программированию .....................................................................19 1.1.2. Рекомендации желающим поучаствовать ...............................................................20 1.2. Об этой книге ................................................................................................................... 20 1.3. Сборник задач CSES ...................................................................................................... 22 1.4. Другие ресурсы ............................................................................................................... 24 Глава 2. Техника программирования ........................................................................26 2.1. Языковые средства ........................................................................................................ 26 2.1.1. Ввод и вывод .......................................................................................................................27 2.1.2. Работа с числами ...............................................................................................................28 2.1.3. Сокращение кода ..............................................................................................................31 2.2. Рекурсивные алгоритмы .............................................................................................. 32 2.2.1. Порождение подмножеств ............................................................................................32 2.2.2. Порождение перестановок ...........................................................................................33 2.2.3. Перебор с возвратом .......................................................................................................34 2.3. Поразрядные операции ............................................................................................... 36 2.3.1. Поразрядные операции ..................................................................................................38 2.3.2. Представление множеств ..............................................................................................40 Глава 3. Эффективность ..............................................................................................43 3.1. Временная сложность ................................................................................................... 43 3.1.1. Правила вычисления .......................................................................................................43 3.1.2. Часто встречающиеся оценки временной сложности .......................................46 3.1.3. Оценка эффективности ...................................................................................................47 3.1.4. Формальные определения ............................................................................................48 3.2. Примеры проектирования алгоритмов ................................................................. 49 3.2.1. Максимальная сумма подмассивов ...........................................................................49 3.2.2. Задача о двух ферзях ......................................................................................................51 3.3. Оптимизация кода .......................................................................................................... 53 3.3.1. Результат работы компилятора....................................................................................54
Оглавление 3.3.2. Особенности процессора ...............................................................................................56 Глава 4. Сортировка и поиск.......................................................................................59 4.1. Алгоритмы сортировки ................................................................................................. 59 4.1.1. Пузырьковая сортировка ...............................................................................................60 4.1.2. Сортировка слиянием ......................................................................................................61 4.1.3. Нижняя граница временной сложности сортировки .........................................62 4.1.4. Сортировка подсчетом ....................................................................................................63 4.1.5. Сортировка на практике .................................................................................................63 4.2. Решение задач с применением сортировки ....................................................... 66 4.2.1. Алгоритмы заметающей прямой .................................................................................66 4.2.2. Составление расписания ................................................................................................67 4.2.3. Работы и сроки исполнения .........................................................................................68 4.3. Двоичный поиск .............................................................................................................. 69 4.3.1. Реализация поиска ...........................................................................................................69 4.3.2. Двоичный поиск по ответу ............................................................................................71 Глава 5. Структуры данных .........................................................................................74 5.1. Динамические массивы ............................................................................................... 74 5.1.1. Векторы .................................................................................................................................74 5.1.2. Итераторы и диапазоны .................................................................................................75 5.1.3. Другие структуры данных ..............................................................................................77 5.2. Множества ......................................................................................................................... 78 5.2.1. Множества и мультимножества ...................................................................................78 5.2.2. Отображения .......................................................................................................................80 5.2.3. Очереди с приоритетом .................................................................................................81 5.2.4. Множества, основанные на политиках .....................................................................82 5.3. Эксперименты .................................................................................................................. 83 5.3.1. Сравнение множества и сортировки.........................................................................83 5.3.2. Сравнение отображения и массива...........................................................................84 5.3.3. Сравнение очереди с приоритетом и мультимножества ..................................84 Глава 6. Динамическое программирование ............................................................86 6.1. Основные понятия ......................................................................................................... 86 6.1.1. Когда жадный алгоритм не работает ........................................................................86 6.1.2. Нахождение оптимального решения ........................................................................87 6.1.3. Подсчет решений ..............................................................................................................91 6.2. Другие примеры .............................................................................................................. 92 6.2.1. Наибольшая возрастающая подпоследовательность .........................................92 6.2.2. Пути на сетке .......................................................................................................................93 6.2.3. Задачи о рюкзаке ..............................................................................................................95 6.2.4. От перестановок к подмножествам ...........................................................................97 6.2.5. Подсчет количества замощений .................................................................................98 Глава 7. Алгоритмы на графах ..................................................................................101 7.1. Основы теории графов ...............................................................................................101 7.1.1.Терминология .................................................................................................................... 102
Оглавление 7 7.1.2. Представление графа.................................................................................................... 104 7.2. Обход графа ....................................................................................................................107 7.2.1. Поиск в глубину ................................................................................................................107 7.2.2. Поиск в ширину ............................................................................................................... 109 7.2.3. Применения ...................................................................................................................... 110 7.3. Кратчайшие пути ...........................................................................................................111 7.3.1. Алгоритм Беллмана–Форда ....................................................................................... 112 7.3.2. Алгоритм Дейкстры ........................................................................................................ 114 7.3.3. Алгоритм Флойда–Уоршелла ..................................................................................... 116 7.4. Ориентированные ациклические графы .............................................................118 7.4.1. Топологическая сортировка ....................................................................................... 119 7.4.2. Динамическое программирование ......................................................................... 120 7.5. Графы преемников........................................................................................................122 7.5.1. Нахождение преемников ............................................................................................ 123 7.5.2. Обнаружение циклов .................................................................................................... 124 7.6. Минимальные остовные деревья ...........................................................................125 7.6.1. Алгоритм Краскала ......................................................................................................... 126 7.6.2. Система непересекающихся множеств.................................................................. 128 7.6.3. Алгоритм Прима .............................................................................................................. 130 Глава 8. Избранные вопросы проектирования алгоритмов ...............................132 8.1. Алгоритмы с параллельным просмотром разрядов .......................................132 8.1.1. Расстояние Хэмминга ................................................................................................... 132 8.1.2. Подсчет подсеток ........................................................................................................... 134 8.1.3. Достижимость в графах ............................................................................................... 135 8.2. Амортизационный анализ .........................................................................................136 8.2.1. Метод двух указателей ................................................................................................ 136 8.2.2. Ближайшие меньшие элементы ............................................................................... 138 8.2.3. Минимум в скользящем окне .................................................................................... 139 8.3. Нахождение минимальных значений ..................................................................140 8.3.1. Тернарный поиск ............................................................................................................ 141 8.3.2. Выпуклые функции ........................................................................................................ 142 8.3.3. Минимизация сумм ....................................................................................................... 142 Глава 9. Запросы по диапазону................................................................................144 9.1. Запросы к статическим массивам .........................................................................144 9.1.1. Запросы о сумме ............................................................................................................ 144 9.1.2. Запросы о минимуме .................................................................................................... 146 9.2. Древовидные структуры ............................................................................................147 9.2.1. Двоичные индексные деревья...................................................................................147 9.2.2. Деревья отрезков ........................................................................................................... 150 9.2.3. Дополнительные приемы ............................................................................................ 154 Глава 10. Алгоритмы на деревьях ...........................................................................157 10.1. Базовые понятия ........................................................................................................157 10.1.1. Обход дерева ................................................................................................................ 158
Оглавление 10.1.2. Вычисление диаметра ............................................................................................... 159 10.1.3. Все максимальные пути ............................................................................................ 161 10.2. Запросы к деревьям .................................................................................................162 10.2.1. Нахождение предков ................................................................................................. 162 10.2.2. Поддеревья и пути ...................................................................................................... 163 10.2.3. Наименьшие общие предки .................................................................................... 165 10.2.4. Объединение структур данных .............................................................................. 168 10.3. Более сложные приемы ...........................................................................................169 10.3.1. Центроидная декомпозиция ................................................................................... 170 10.3.2. Heavy-light декомпозиция ....................................................................................... 170 Глава 11. Математика ................................................................................................172 11.1. Теория чисел.................................................................................................................172 11.1.1. Простые числа и разложение на простые множители ................................. 172 11.1.2. Решето Эратосфена ................................................................................................... 175 11.1.3. Алгоритм Евклида ........................................................................................................ 176 11.1.4. Возведение в степень по модулю ......................................................................... 178 11.1.5. Теорема Эйлера ............................................................................................................ 178 11.1.6. Решение уравнений в целых числах ................................................................... 180 11.2. Комбинаторика ...........................................................................................................181 11.2.1. Биномиальные коэффициенты .............................................................................. 181 11.2.2. Числа Каталана ............................................................................................................. 184 11.2.3. Включение-исключение ........................................................................................... 186 11.2.4. Лемма Бёрнсайда ........................................................................................................ 188 11.2.5. Теорема Кэли ................................................................................................................. 189 11.3. Матрицы .........................................................................................................................190 11.3.1. Операции над матрицами ........................................................................................ 190 11.3.2. Линейные рекуррентные соотношения.............................................................. 192 11.3.3. Графы и матрицы ......................................................................................................... 194 11.3.4. Метод Гаусса .................................................................................................................. 196 11.4. Вероятность ..................................................................................................................199 11.4.1. Операции с событиями ............................................................................................. 200 11.4.2. Случайные величины.................................................................................................. 201 11.4.3. Марковские цепи ......................................................................................................... 203 11.4.4. Рандомизированные алгоритмы ........................................................................... 205 11.5. Теория игр .....................................................................................................................207 11.5.1. Состояния игры ..............................................................................................................207 11.5.2. Игра ним .......................................................................................................................... 209 11.5.3. Теорема Шпрага–Гранди .......................................................................................... 210 11.6. Преобразование Фурье ...........................................................................................213 11.6.1. Работа с полиномами ................................................................................................. 213 11.6.2. Алгоритм БПФ ............................................................................................................... 214 11.6.3. Вычисление свертки ....................................................................................................217 Глава 12. Дополнительные алгоритмы на графах ................................................219 12.1. Сильная связность......................................................................................................219
Оглавление 9 12.1.1. Алгоритм Косарайю .................................................................................................... 220 12.1.2. Задача 2-выполнимости ........................................................................................... 221 12.2. Полные пути .................................................................................................................223 12.2.1. Эйлеровы пути .............................................................................................................. 223 12.2.2. Гамильтоновы пути ...................................................................................................... 226 12.2.3. Применения ................................................................................................................... 226 12.3. Максимальные потоки .............................................................................................228 12.3.1. Алгоритм Форда–Фалкерсона .............................................................................. 229 12.3.2. Непересекающиеся пути .......................................................................................... 232 12.3.3. Максимальные паросочетания .............................................................................. 233 12.3.4. Покрытие путями ......................................................................................................... 235 12.4. Деревья поиска в глубину ......................................................................................237 12.4.1. Двусвязность .................................................................................................................. 238 12.4.2. Эйлеровы подграфы ................................................................................................... 239 12.5. Потоки минимальной стоимости .........................................................................240 12.5.1. Алгоритм путей минимальной стоимости .......................................................... 241 12.5.2. Паросочетания минимального веса ..................................................................... 243 12.5.3. Улучшение алгоритма ................................................................................................ 244 Глава 13. Геометрия ...................................................................................................247 13.1. Технические средства в геометрии ....................................................................247 13.1.1. Комплексные числа .....................................................................................................247 13.1.2. Точки и прямые ............................................................................................................. 249 13.1.3. Площадь многоугольника ......................................................................................... 252 13.1.4. Метрики ........................................................................................................................... 254 13.2. Алгоритмы на основе заметающей прямой ....................................................256 13.2.1. Точки пересечения ...................................................................................................... 256 13.2.2. Задача о ближайшей паре точек ............................................................................257 13.2.3. Задача о выпуклой оболочке ................................................................................. 258 Глава 14. Алгоритмы работы со строками .............................................................260 14.1. Базовые методы .........................................................................................................260 14.1.1. Префиксное дерево .................................................................................................... 261 14.1.2. Динамическое программирование ...................................................................... 261 14.2. Хеширование строк ...................................................................................................263 14.2.1. Полиномиальное хеширование ............................................................................. 263 14.2.2. Применения ................................................................................................................... 263 14.2.3. Коллизии и параметры .............................................................................................. 264 14.3. Z-алгоритм .....................................................................................................................266 14.3.1. Построение Z-массива ............................................................................................... 266 14.3.2. Применения ................................................................................................................... 268 14.4. Суффиксные массивы ...............................................................................................269 14.4.1. Метод удвоения префикса ....................................................................................... 269 14.4.2. Поиск образцов ............................................................................................................ 270 14.4.3. LCP-массивы .................................................................................................................. 271
Похожие Показать весь список
К покупке доступен более свежий выпуск
Перейти