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

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

Автор: Piotr Stańczyk

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

Видавництво: Wydawnictwo Naukowe PWN

Кількість сторінок: 312

Видання: 1Рік випуску: 2009

ISBN: 978-83-01-15821-7

мова: польська

Опис:

Ця книга відрізняється від книжок, присвячених алгоритмам, відомих на польському ринку, оскільки вона стосується її практичної сторони. Таке ставлення до цієї галузі інформатики є результатом зростаючого інтересу як учнів, так і студентів до участі в різних видах олімпіад з програмування.

Читач знайде огляд реалізації основних алгоритмів і структур даних, які можна використовувати безпосередньо або легко адаптувати під час розв’язування конкурсних завдань. Основою книги є алгоритмічна бібліотека, яка була створена та розширена під час підготовки команди Warsaw Predators з Варшавського університету до представлення цього університету на міжнародних змаганнях.

Унікальність книги полягає в наступних елементах:

- виклад усіх найважливіших розділів алгоритміки з точки зору змагань,

- інтуїтивно зрозумілий підхід до представлених алгоритмічних проблем,

- лаконічна, ефективна реалізація обговорюваних алгоритмів у 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. Алгоритм KMP 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