анти. Guide to Competitive
 Скачать 2.39 Mb.
|
|
322 Библиография 19. J. Kärkkäinen and P. Sanders. Simple linear work suffix array construction. International Colloquium on Automata, Languages, and Programming, 943–955, 2003. 20. R. M. Karp, R. E. Miller, and A. L. Rosenberg. Rapid identification of repeated patterns in strings, trees and arrays. Annual ACM Symposium on Theory of Computing, 125–135, 1972. 21. T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park. Linear-time longest- common-prefix computation in suffix arrays and its applications. Annual Symposium on Combinatorial Pattern Matching, 181–192, 2001. 22. J. Kleinberg and É. Tardos. Algorithm Design, Pearson, 2005. 23. D. E. Knuth. Optimum binary search trees. Acta Informatica 1 (1): 14–25, 1971. 24. D. E. Knuth, J. H. Morris Jr., V. R. Pratt, Fast pattern matching in strings. SIAM J. Comput. 6 (2), 323–350 (1977). 25. S. Kopeliovich. Offline solution of connectivity and 2-edge-connectivity problems for fully dynamic graphs. MSc thesis, Saint Petersburg State University, 2012. 26. M. G. Main and R. J. Lorentz. An O(n log n) algorithm for finding all repetitions in a string. Journal of Algorithms, 5 (3): 422–432, 1984. 27. J. Pachocki and J. Radoszewski. Where to use and how not to use polynomial string hashing. Olympiads in Informatics, 7 (1): 90–100, 2013. 28. D. Pearson.Apolynomial-time algorithm for the change-making problem. Operations Research Letters, 33 (3): 231–234, 2005. 29. 27-Queens Puzzle: Massively Parallel Enumeration and Solution Counting. https://github.com/preusser/q27 30. M. I. Shamos and D. Hoey. Closest-point problems. Annual Symposium on Foundations of Computer Science, 151–162, 1975. 31. S. S. Skiena. The Algorithm Design Manual, Springer, 2008 (2nd edition). 32. S. S. Skiena andM. A. Revilla. Programming Challenges: The Programming Contest Training Manual, Springer, 2003. 33. D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26 (3): 362–391, 1983. 34. P. Stańczyk. Algorytmika praktyczna w konkursach Informatycznych. MSc thesis, University of Warsaw, 2006. 35. V. Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13 (4): 354–356, 1969. 36. F. F. Yao. Efficient dynamic programming using quadrangle inequalities. Annual ACM Symposium on Theory of Computing, 429–435, 1980. Предметный указатель Символы 2SAT задача 221 2SUM задача 137 3SAT задача 223 H heavy-light декомпозиция 170 I IDA* алгоритм 306 L LCP-массив 271 M mex функция 211 N NP-трудная задача 47 S SPFA алгоритм 113 Z Z-алгоритм 266 Z-массив 266 А автомат 272 алгоритм заметающей прямой 66 , 256 алгоритм масштабирования пропускной способности 231 алгоритм разреженной таблицы 146 алгоритм с параллельным просмотром разрядов 132 алгоритм с постоянным временем 46 алгоритм типа Лас-Вегас 205 алгоритм типа Монте-Карло 205 алгоритмы сортировки 59 амортизационный анализ 136 антицепь 237 арифметика по модулю 29 арифметическая прогрессия 315 Б Беллмана–Форда алгоритм 112 Бёрнсайда лемма 188 беспорядок 187 Бине формула 319 биномиальное распределение 203 биномиальный коэффициент 181 битовая маска 39 битовое множество 41 ближайшая пара точек 257 ближайший меньший элемент 138 быстрое преобразование Фурье (БПФ) 215 В Варнсдорфа правило 227 ввод и вывод 27 вектор 74 , 190 , 247 векторное произведение 249 вероятность 199 вершина 102 вершинное покрытие 234 взаимно простые числа 178 взвешенный граф 103 включение-исключение 186 внутренний порядок 159 возведение в степень по модулю 178 возведение матрицы в степень 192 временная сложность 43 встреча в середине 308 выигрышное состояние 207 выпуклая оболочка 258 выпуклая функция 142 вычисление обратной величины по модулю 179 Г гамильтонов путь 226 гамильтонов цикл 226 гармонический ряд 175 , 316 324 Предметный указатель геометрическая прогрессия 316 геометрическое распределение 203 геометрия 247 Гранди число 210 граница 268 граф 102 граф компонент 220 граф преемников 122 Д двоичное дерево поиска 78 двоичное индексное дерево 147 двоичное представление 36 двоичный поиск 69 двудольный граф 104 двумерное дерево отрезков 293 двусвязность 238 двусвязный граф 238 двусторонняя очередь 77 де Брёйна последовательность 226 Дейкстры алгоритм 114 делимость 172 дерево 103 , 157 дерево отрезков 150 , 286 дерево поиска в глубину 237 Джонсона алгоритм 244 диаметр 159 диапазон 76 дизъюнкция 318 Дилуорса теорема 237 динамическая связность 312 динамический массив 74 динамическое дерево отрезков 290 динамическое программирование 86 диофантово уравнение 180 дополнение 317 достижимость 135 дочерняя вершина 158 дуча 294 Е Евклида алгоритм 176 евклидово расстояние 254 единичная матрица 191 Ж жадный алгоритм 67 З задача 2-выполнимости 221 задача о 3-выполнимости 223 задача о размене монет 86 задача о сумме двух элементов 137 задача о ферзях 34 , 51 замощение 98 запоминание 89 запросы к деревьям 162 запросы по диапазону 144 И игра 15 306 игра Гранди 212 ИЛИ операция 38 импликация 318 инверсия 61 И операция 38 ИСКЛЮЧАЮЩЕЕ ИЛИ операция 38 итератор 75 К Каталана число 184 квадратичный алгоритм 46 квадратная матрица 190 квадратный корень в алгоритмах 279 квантор 318 Кёнига теорема 234 китайская теорема об остатках 180 Кнута оптимизация 302 Коллатца гипотеза 23 коллизия 264 комбинаторика 181 комплексное число 247 компонента связности 102 компонента сильной связности 219 конъюнкция 318 корень 157 корневое дерево 157 Косарайю алгоритм 220 Краскала алгоритм 126 кратчайший путь 111 Предметный указатель 325 кубический алгоритм 46 Кэли теорема 189 Л Левенштейна расстояние 262 ленивое дерево отрезков 287 ленивое распространение 287 линейное рекуррентное соотношение 192 линейный алгоритм 46 лист 157 логарифм 319 логарифмический алгоритм 46 М макрос 31 максимальная сумма подмассивов 49 максимальное независимое множество 235 максимальное остовное дерево 125 максимальное паросочетание 233 максимальный поток 228 манхэттенское расстояние 254 марковская цепь 203 маршрут шахматного коня 227 массив граней 275 массив обхода дерева 163 массив префиксных сумм 144 математическая логика 318 математическое ожидание 201 матрица смежности 106 метод двух указателей 136 метод удвоения префикса 269 метрика 254 мизер игра 210 минимальная циклическая перестановка 264 минимальное вершинное покрытие 234 минимальное остовное дерево 125 минимальный разрез 228 , 231 минимум в скользящем окне 139 множество 78 , 317 множество, основанное на политике 82 множитель 172 Мо алгоритм 285 мост 238 мультимножество 80 мультиномиальный коэффициент 183 Н наибольшая возрастающая подпоследовательность 92 наибольшая общая подпоследовательность 261 наибольший общий делитель 176 наибольший общий префикс 271 наименьшее общее кратное 176 наименьший общий предок 165 натуральный логарифм 319 независимое множество 235 независимость 201 НЕ операция 38 непересекающиеся пути 232 неравенство четырехугольника 301 ним игра 209 ним-сумма 209 О обнаружение циклов 110 , 119 , 124 обновление диапазона 155 обратный порядок 159 объединение 317 оператор сравнения 64 оптимизация динамического программирования 298 Оптимизация методом «разделяй и властвуй» 301 ориентированный ациклический граф (DAG) 118 ориентированный граф 103 остаток 29 остовное дерево 125 отображение 80 отрицание 318 отрицательный цикл 113 очередь 77 очередь с приоритетом 81 П парадокс дней рождения 265 параллельный двоичный поиск 310 паросочетание 233 Паскаля треугольник 182 перебор с возвратом 34 , 303 пересечение 317 326 Предметный указатель пересечение отрезков 250 перестановка 33 персистентное дерево отрезков 291 Пика теорема 253 пирамида 81 площадь многоугольника 252 поворот системы координат 255 подалгоритм 281 поддерево 158 подмножество 32 , 317 подпоследовательность 260 подстрока 260 поиск в глубину (DFS) 107 поиск в ширину (BFS) 109 полиномиальное хеширование 263 полиномиальный алгоритм 47 полный граф 104 положение точки относительно прямой 250 полустепень захода 104 полустепень исхода 104 поразрядный сдвиг 38 порядковая статистика 205 постоянный множитель 47 поток 228 поток минимальной стоимости 240 предикат 318 предок 162 преемник 122 префикс 260 префиксное дерево 261 Прима алгоритм 130 проверка на двудольность 111 проверка на простоту 173 проверка связности 110 проигрышное состояние 207 простое число 173 Прюфера код 189 прямой порядок 159 пузырьковая сортировка 60 путь 102 Р равномерное распределение 203 разложение на простые множители 173 разностный массив 155 разность 317 разреженное дерево отрезков 291 разрез 228 рандомизированный алгоритм 205 раскраска графа 206 распределение 202 расстановка скобок 184 расстояние от точки до прямой 251 расширенный алгоритм Евклида 177 ребро 102 регулярное выражение 273 регулярный граф 104 регулярный язык 273 редакторское расстояние 262 рекурсия 32 родитель 158 рюкзак 95 , 284 С свертка 217 связный граф 102 сжатие координат 154 сжатие путей 130 сильно связный граф 219 система непересекающихся множеств 128 скользящее окно 139 сложение матриц 190 случайная величина 201 смежные вершины 103 событие 200 совершенное паросочетание 234 сопоставление с образцом 264 , 268 , 274 сортировка 59 сортировка подсчетом 63 сортировка слиянием 61 соседние вершины 103 состояние игры 207 список ребер 106 список смежности 105 стек 77 степень 103 структура данных 74 суффикс 260 суффиксный автомат 276 суффиксный массив 269 Предметный указатель 327 Т теория игр 207 теория игры ним 207 теория чисел 172 топологическая сортировка 119 точка 247 точка внутри многоугольника 251 точка пересечения 256 точка сочленения 238 транспонированная матрица 190 тернарный поиск 141 трюк с выпуклой оболочкой 299 У умножение матриц 191 , 206 универсальное множество 317 условная вероятность 201 Ф факториал 319 Фаульхабера формула 315 Фенвика дерево 147 Ферма малая теорема 179 Фибоначчи числа 193 , 319 Флойда алгоритм 124 Флойда–Уоршелла алгоритм 116 Форда–Фалкерсона алгоритм 229 формула шнурования 252 функции сравнения 65 функциональный граф 122 функция Эйлера 178 Х Хирхольцера алгоритм 224 Холла теорема 234 Хэмминга расстояние 132 хеширование строк 263 хеш-код 263 хеш-таблица 78 Ц целое разбиение 283 целое число 28 центроид 170 центроидная декомпозиция 170 цикл 102 циклическая перестановка 264 Ч число без знака 37 число со знаком 37 число с плавающей точкой 30 Ш Шпрага–Гранди теорема 210 Штрассена алгоритм 191 Э эвристическая функция 306 Эдмондса–Карпа алгоритм 230 эйлеровым обходом дерева 166 Эйлера теорема 179 эйлеров подграф 239 эйлеров путь 223 эйлеров цикл 223 эквиваленция 318 Эндрю алгоритм 259 Эратосфена решето 175 Антти Лааксонен Олимпиадное программирование Изучение и улучшение алгоритмов на соревнованиях 2-е издание, обновленное и дополненное Главный редактор Мовчан Д. А. dmkpress@gmail.com Перевод с английского Слинкин А. А. Корректор Синяева Г. И. Верстка Паранская Н. В. Дизайн обложки Мовчан А. Г. Формат 70×100 1 / 16 . Печать цифровая. Усл. печ. л. 24,38. Тираж 400 экз. Веб-сайт издательства: www.dmkpress.com Книги издательства «ДМК Пресс» можно заказать в торгово-издательском хол- динге «Планета Альянс» наложенным платежом, выслав открытку или письмо по почтовому адресу: 115487, г. Москва, 2-й Нагатинский пр-д, д. 6А. При оформлении заказа следует указать адрес (полностью), по которому должны быть высланы книги; фамилию, имя и отчество получателя. Желательно также ука- зать свой телефон и электронный адрес. Эти книги вы можете заказать и в интернет-магазине: www.alians-kniga.ru. Оптовые закупки: тел. +7(499) 782-38-89 Электронный адрес: books@alians-kniga.ru. |