Дроздов Сергей Николаевич Комбинаторные задачи и элементы теории вычислительной сложности

Учебное пособие

Ответственный за выпуск Дроздов С.Н.

Редактор Монахова Е.Л.

Корректор Надточий З.И.

ЛР №020565 от 23 июня 1997 г.

Формат 6084 ¹/₁₆ Подписано к печати 21.12.00

Печать офсетная Бумага офсетная

Усл.п.л. – 4.0 Уч.-изд. л. – 3.8

Тираж 300 экз Заказ №

И здательство Таганрогского государственного радиотехнического университета ГСП-17А, Таганрог, 28, Некрасовский, 44

Типография Таганрогского государственного радиотехнического университета ГСП-17А, Таганрог, 28, Энгельса, 1

1 В некоторых книгах используется несколько иное определение понятия «O-большое», а именно, требуется, чтобы верхний предел отношения |f(n)/g(n)| был больше нуля, но меньше бесконечности. Все оценки, приводимые в данном пособии, одинаково справедливы для обоих определений.

1 Чтобы избежать двусмысленности, более привычное слово «решение» используется только в смысле «процесс решения», а слово «план» – в смысле «результат решения».

1 Речь идет о задаче минимизации. Если поставлена задача на отыскание максимума целевой функции, то следует соответственно использовать оценки сверху.

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

1 Не пытайтесь найти глубокий смысл в названии метода. Его нет. В 50-е годы слово «программирование» означало не то, что сейчас.

1 Говоря «числовые», мы фактически имеем в виду «целочисленные». Если задача имеет вещественные параметры, то с учетом ограниченной точности представления чисел в ЭВМ всегда можно заменить их целочисленными (например, задавать вещественное число его мантиссой и порядком).

2 Если только не окажется верной гипотеза «P = NP». В этом случае окажется, что для любой NP–полной задачи имеется полиномиальный алгоритм, а он, как было сказано, может также считаться псевдополиномиальным.