Электронная книга – цифровая версия продукта

Название: Практический алгоритм

Автор: Пётр Станьчик

Формат файла: pdf

Издательство: Wydawnictwo Naukowe PWN

Количество страниц: 312

Издания: 1Год выпуска: 2009

ISBN: 978-83-01-15821-7

язык: польский

Описание:

Эта книга отличается от книг, посвященных алгоритмам, известных на польском рынке, тем, что касается ее практической стороны. Такой подход к этой отрасли информатики обусловлен растущим интересом как студентов, так и студентов к участию в различного рода соревнованиях по программированию.

Читатель найдет обзор реализации основных алгоритмов и структур данных, которые можно использовать напрямую или легко адаптировать при решении соревновательных задач. Основой книги является алгоритмическая библиотека, которая была создана и расширена в ходе подготовки команды Варшавских хищников Варшавского университета к представлению этого университета на международных соревнованиях.

Уникальность книги состоит из следующих элементов:

- изложение всех наиболее важных разделов алгоритмики с точки зрения соревнований,

>- интуитивный подход к представленным алгоритмическим вопросам,

- лаконичная, эффективная реализация обсуждаемых алгоритмов на C++,

- многочисленные примеры конкурсных задач с подсказками, постепенно ведущими к правильному решению задачи, а также адрес сайта, на котором можно найти программы, составляющие решения этих задач,

- тематические списки задач со всего мира с возможностью тестирования их решения на сайтах соревнований,

— ссылки на литературу, позволяющую детально ознакомиться с описываемыми вопросами с теоретической точки зрения,

— ценные советы по стратегии участия в соревнованиях.

Эту работу должен прочитать каждый, кто хочет улучшить свои навыки в области алгоритмов и программирования.

Дополнительные материалы доступны по адресу:

Оглавление:

Предисловие9

Предисловие11

1. Графовые алгоритмы15

1.1. Графическое представление 16

1.2. Поиск по графу в ширину 20

1.3. Поиск по графу в глубину 25

1.4. Сильно связанные компоненты 31

1.5. Топологическая сортировка 38

1.6. Ацикличность 41

1.7. Мосты, точки артикуляции и двухкогерентные компоненты 44

1.8. Путь и цикл Эйлера 51

1.9. Минимальное связующее дерево 57

1.10. Алгоритм Дейкстры 60

1.11. Алгоритм Беллмана-Форда 65

1.12. Максимальный расход 67

1.12.1. Максимальный расход определяется по методу Dinica 68

1.12.2. максимальный поток для ребер блока 72

1.12.3. Самый дешевый максимальный расход для ребер блока 74

1.13. Максимальное совпадение в двудольном графе 77

1.13.1. Двуразделение графа 78

1.13.2. Максимальное совпадение в двудольном графе за время O (n(n+m)) 81

1.13.3. Максимальное совпадение в двудольном графе за время O((n+m)n1/2) 83

1.13.4. Самое дорогое совпадение в двудольном графе 86

2. Вычислительная геометрия на плоскости91

2.1. Расстояние точки от прямой 95

2.2. Площадь многоугольника 96

2.3. Укажите принадлежность к рисунку 98

2.4. Точки пересечения 105

2.5. Три точки – круг 114

2.6. Угловая сортировка 116

2.7. Выпуклое гало 120

2.8. Ближайшая пара очков 123

3. Комбинаторика128

3.1. Перестановки в антилексикографическом порядке 128

3.2. Перестановки - минимальное количество транспозиций 130

3.3. Перестановки - минимальное количество соседних транспозиций 132

3.4. Все подмножества множества 135

3.5. Подмножества K-элементов в лексикографическом порядке 137

3.6. Разделение набора с использованием минимального количества изменений 138

3.7. Деление числа в антилексикографическом порядке 140

4. Теория чисел142

4.1. Биномиальный коэффициент 142

4.2. Наибольший общий делитель 144

4.3. Модульный обратный 147

4.4. Сравнения 149

4.5. Быстрое модульное возведение в степень 152

4.6. Решето Эратосфена 154

4.7. Список простых чисел 155

4.8. Тест на примитивность 157

4.9. Арифметика больших чисел 160

5. Структуры данных178

5.1. Структура данных для представления непересекающихся множеств 178

5.2. Двоичные деревья поиска 182

5.2.1. Максимум деревьев 185

5.2.2. Деревья счетчиков 187

5.2.3. Деревья позиций 189

5.2.4. Покровные деревья 192

5.3. Динамически выделяемые двоичные статические деревья 195

5.4. Обогащенные бинарные деревья 200

6. Текстовые алгоритмы212

6.1. Алгоритм КМП 212

6.2. Минимальный период слова 216

6.3. KMP для множественных шаблонов (алгоритм Ахо-Корасика) 217

6.4. Радиусы палиндрома в слове 223

6,5. Суффиксные деревья 226

6.5.1. Количество вхождений шаблона в текст 230

6.5.2. Количество различных подслов слова 232

6.5.3. Самое длинное подслово, встречающееся nраз 233

6.6. Лексикографически максимальный суффикс 234

6.7. Циклическая эквивалентность 235

6.8. Минимальная лексикографическая цикличность слова 237

7. Линейная алгебра240

7.1. Метод исключения Гаусса 240

7.1.1. Исключение по Гауссу в Z2 241

7.1.2. Метод исключения Гаусса в Zp 244

7.2. Линейное программирование 248

8. Элементы стратегии во время соревнований253

8.1. Оценка ожидаемой временной сложности 253

8.2. Стратегия командной работы 255

8.3. Шаблон 258

8.4. Пли

----

Важная информация о продукте:

ЭЛЕКТРОННАЯ КНИГА — ЦИФРОВОЙ ПРОДУКТ

Вы можете скачать файл в своей учетной записи Allegro на вкладке «Моя полка».

Для покупки электронной книги у вас должна быть учетная запись на Allegro.

Электронная книга будет защищена водяным знаком и не имеет DRM.