Глава 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

Оглавление

251

§ 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

252

Оглавление

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

Литература 243

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

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

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

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

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