М.: МЦНМО, 2009. — 256 с.
В книге излагаются основные (начальные) разделы теории сложности
алгоритмов. Различаются алгебраическая и битовая сложности, каждая
из которых рассматривается в худшем случае и в среднем. Ряд
основных понятий теории сложности, как-то: оценки снизу и сверху,
нижняя граница сложности алгоритмов некоторого класса, оптимальный
алгоритм и т. д., рассматривается не только в обычном
функциональном, но и в асимптотическом смысле: асимптотические
оценки, асимптотическая нижняя граница, оптимальность по порядку
сложности и т. д. Показывается, что при исследовании существования
алгоритма решения задачи, имеющего «не очень высокую» сложность,
важную роль может играть сводимость одной задачи к другой.
Изложение сопровождается анализом сложности большого числа алгоритмов арифметики, сортировки и поиска, вычислительной геометрии, теории графов и др.
Для студентов, специализирующихся в области математики и информатики. Содержание:
Сложности алгоритмов как функции числовых аргументов. Сложность в худшем случае.
Затраты алгоритма для данного входа, алгебраическая сложность.
Асимптотические оценки (формализм).
Асимптотические оценки (два примера).
Длина числа как возможный размер входа.
Сложность в среднем.
Понятие сложности в среднем.
Сортировка и конечные вероятностные пространства.
Применение формулы полного математического ожидания
Пример медленного роста сложности в среднем в срав-
нении со сложностью в худшем случае.
Функция затрат рандомизированного алгоритма.
Оценивание числа шагов (итераций) алгоритма.
Функции, убывающие по ходу выполнения алгоритма.
Качество оценок.
Завершимость работы алгоритма.
Вложенные циклы (дополнительные примеры).
Нецелые размеры входа и непрерывные оценочные функции.
Нижняя граница сложности алгоритмов некоторого класса. Оптимальные алгоритмы.
Понятие нижней границы сложности.
Оптимальные алгоритмы.
Асимптотические нижние границы. Алгоритм, оптимальный по порядку сложности.
Нижняя граница сложности в среднем.
Нижние границы сложности рандомизированных алгоритмов. Принцип Яо.
Битовая сложность.
Битовые операции.
Наивная арифметика: умножение.
Наивная арифметика: деление с остатком.
Модулярная арифметика.
Булева арифметика.
Рекуррентные соотношения как средство анализа сложности алгоритмов.
Простейшие рекуррентные уравнения.
Об одном классе нелинейных рекуррентных соотношений.
Асимптотические оценки решений рекуррентных неравенств.
Добавление нулей.
Сводимость
Линейная сводимость.
Линейная сводимость и нижние границы сложности.
Классы P и NP.
Существование задач распознавания, не принадлежащих P. Связь моделей МТ и РАМ.
Полиномиальная сводимость. NP-полные задачи.
Приложения.
Изложение сопровождается анализом сложности большого числа алгоритмов арифметики, сортировки и поиска, вычислительной геометрии, теории графов и др.
Для студентов, специализирующихся в области математики и информатики. Содержание:
Сложности алгоритмов как функции числовых аргументов. Сложность в худшем случае.
Затраты алгоритма для данного входа, алгебраическая сложность.
Асимптотические оценки (формализм).
Асимптотические оценки (два примера).
Длина числа как возможный размер входа.
Сложность в среднем.
Понятие сложности в среднем.
Сортировка и конечные вероятностные пространства.
Применение формулы полного математического ожидания
Пример медленного роста сложности в среднем в срав-
нении со сложностью в худшем случае.
Функция затрат рандомизированного алгоритма.
Оценивание числа шагов (итераций) алгоритма.
Функции, убывающие по ходу выполнения алгоритма.
Качество оценок.
Завершимость работы алгоритма.
Вложенные циклы (дополнительные примеры).
Нецелые размеры входа и непрерывные оценочные функции.
Нижняя граница сложности алгоритмов некоторого класса. Оптимальные алгоритмы.
Понятие нижней границы сложности.
Оптимальные алгоритмы.
Асимптотические нижние границы. Алгоритм, оптимальный по порядку сложности.
Нижняя граница сложности в среднем.
Нижние границы сложности рандомизированных алгоритмов. Принцип Яо.
Битовая сложность.
Битовые операции.
Наивная арифметика: умножение.
Наивная арифметика: деление с остатком.
Модулярная арифметика.
Булева арифметика.
Рекуррентные соотношения как средство анализа сложности алгоритмов.
Простейшие рекуррентные уравнения.
Об одном классе нелинейных рекуррентных соотношений.
Асимптотические оценки решений рекуррентных неравенств.
Добавление нулей.
Сводимость
Линейная сводимость.
Линейная сводимость и нижние границы сложности.
Классы P и NP.
Существование задач распознавания, не принадлежащих P. Связь моделей МТ и РАМ.
Полиномиальная сводимость. NP-полные задачи.
Приложения.