Дроздов Сергей Николаевич

Комбинаторные задачи

и элементы теории вычислительной сложности

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

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

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

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

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

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

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

Усл.п.л. – 5.8 Уч.-изд. л. – 5.6

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

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

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

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

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

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

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

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

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

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