Предметный указатель

Алгоритм

— Агравала—Кайала—Саксены (AKS) 148

— бинарный возведения в сте­пень (RS) 34, 109

— Грэхема (G) 23, 195

— Евклида (E) 74, 142, 143 расширенный (EE) 77, 144,

— Карацубы (KM) 174

— кратных карт 92

— наивного деления с остатком
(ND) 140

------ умножения (NM) 137

— оптимальный 110

------ по порядку сложности 114

— пробных делений (TD) 10, 32

— рандомизированный 58, 65, 128

— сложения (Add) 135

— Тоома (TM) 178

— Уоршелла 152, 189

— Шенхаге—Штрассена 180

— Шеймоса—Хоя (SH) 39

— Штрассена умножения матриц (St) 176

Асимптотики символ

— о 20, 22

— О 19, 22

— О 149

— в 18, 22

— U 19, 22

— ~ 22

Задача NP-полная 205 Затраты алгоритма (функции за­трат) 9

Класс

— P 196

— Р 196

— NP 198

Модель вычислений 17, 133, 203

Нижняя граница сложности 106

— асимптотическая 114

Оценка точная 20, 22

Поиск 216

— бинарный места элемента (BS) 78, 216

— наименьшего элемента 106,110, 216

— наименьшего и наибольшего элементов 112, 121, 216

— m -го наименьшего элемента 216

Полиномиальная ограниченность

46 Принцип Яо 128 Проблема Р = NP 196, 207

Размер входа 10

Сегмент массива 78 Сертификат 198 Сводимость

— линейная 185

— полиномиальная 204 Сложность 11

— аддитивная 15

Предметный указатель

Сложность алгебраическая 13

— битовая 134

— в среднем 42

— в худшем случае 11

— временная 11

— мультипликативная 14

— пространственная 11

— словесная 137 Сортировка 214

— быстрая (QS) 38, 215 рандомизированная 59

— вставками

------ бинарными (B) 82, 215

------ простыми (1_1; 1₂) 10, 214

— выбором 17, 214

— оптимальная (opt) 236

— пузырьковая 18, 52, 214

— слияниями и вставками (F) 237

— слияниями рекурсивная (MS) 163, 167, 215

— фон Неймана (vN) 80, 215
Стратегия «разделяй и властвуй»

163 Схемы Горнера оптимальность 227

Теорема

— Кука 205

— о рекуррентном неравенстве 169

— Фишера—Рабина 202

Оглавление

Наиболее часто используемые обозначения............................................... 8

Глава 1. Сложности алгоритмов как функции числовых аргумен­тов. Сложность в худшем случае

§ 1. Затраты алгоритма для данного входа, алгебраическая

§ 2. Асимптотические оценки (формализм).............................................. 18

§ 3. Асимптотические оценки (два примера)............................................ 23

§ 4. Длина числа как возможный размер входа....................................... 31

Глава 2. Сложность в среднем

§ 5. Понятие сложности в среднем............................................................. 42

§ 6. Сортировка и конечные вероятностные пространства.

Применение формулы полного математического ожидания46

§ 7. Пример медленного роста сложности в среднем в срав­
нении со сложностью в худшем случае............................................. 53

§ 8. Функция затрат рандомизированного алгоритма........................... 58

Глава 3. Оценивание числа шагов (итераций) алгоритма

§ 9. Функции, убывающие по ходу выполнения алгоритма.. 74

§ 10. Качество оценок........................................................................................ 83

§ 11. Завершимость работы алгоритма....................................................... 89

§ 12. Вложенные циклы (дополнительные примеры)........................... 95

§ 13. Нецелые размеры входа и непрерывные оценочные

Глава 4. Нижняя граница сложности алгоритмов некоторого клас­са. Оптимальные алгоритмы

§ 14. Понятие нижней границы сложности.............................................. 106

§ 15. Оптимальные алгоритмы................................................................. 109

Оглавление

§ 16. Асимптотические нижние границы. Алгоритм, опти­
мальный по порядку сложности........................................................ 114

§ 17. Нижняя граница сложности в среднем............................................ 118

§ 18. Нижние границы сложности рандомизированных алго­
ритмов. Принцип Яо.......................................................................... 126

Глава 5. Битовая сложность

§ 19. Битовые операции................................................................................ 133

§ 20. Наивная арифметика: умножение................................................. 137

§ 21. Наивная арифметика: деление с остатком.................................... 140

§ 22. Модулярная арифметика.................................................................... 145

§ 23. Булева арифметика........................................................................... 150

Глава 6. Рекуррентные соотношения как средство анализа слож­ности алгоритмов

§ 24. Простейшие рекуррентные уравнения........................................... 158

§ 25. Об одном классе нелинейных рекуррентных соотношений!63 § 26. Асимптотические оценки решений рекуррентных нера-

§ 27. Добавление нулей................................................................................. 172

Глава 7. Сводимость

§ 28. Линейная сводимость........................................................................... 185

§ 29. Линейная сводимость и нижние границы сложности.. 190

§ 30. Классы Р и NP......................................................................................... 195

§ 31. Существование задач распознавания, не принадлежа­
щих Р. Связь моделей МТ и РАМ...................................................... 201

§ 32. Полиномиальная сводимость. NP-полные задачи...................... 204

Приложение А. Основные алгоритмы сортировки и поиска... 214 Приложение В. Оценивание сумм значений монотонных функций 218

Приложение С. Проблема орбит....................................................................... 221

Приложение D. Оптимальность схемы Горнера........................................... 227

Приложение Е. Об одном свойстве сумм неотрицательных случай­
ных величин.................................................................................................... 233

Приложение F. О сортировке, оптимальной по числу сравнений
в худшем случае............................................................................................... 236

Оглавление

Приложение G. Метод построения общего решения линейного ре­куррентного уравнения с постоянными коэффициентами... 238 Приложение H. Об одном семействе алгебраических уравнений 240

Литература................................................................................. 243

Предметный указатель................................................................ 248

Сергей Александрович Абрамов

Лекции о сложности алгоритмов

Издательство Московского центра

непрерывного математического образования

119002, Москва, Большой Власьевский пер., 11. Тел. [phone]

Подписано в печать 01.11.2008 г. Формат 60x90Vi6. Бумага офсетная. Печать офсетная. Печ. л. 16. Тираж 1000. Заказ

Отпечатано с готовых диапозитивов в ППП «Типография „Наука“». 121099, Москва, Шубинский пер., д. 6.

Книги издательства МЦНМО можно приобрести в магазине «Математическая книга», Большой Власьевский пер., д. 11. Тел. [phone]. E-mail: [email protected]

Дата добавления: 2014-01-11