235

11.Задачи из NP класса.

12.NP-трудные и NP-полные задачи, в чем их различие?

13.Примеры NP-полных задач.

14.Класс Е.

15.Емкостная (ленточная) сложность алгоритма, оценка ленточной сложности через временную сложность алгоритма.

§ 9. Упражнения

Рассмотрим известную задачу коммивояжера. Имеется n городов С={c1,c2,…,cn} и известны расстояния d(ci,cj) между каждой парой городов ci,cj из С. Нужно найти обход городов чтобы побывать в каждом городе из С один и только один раз, и вернуться в исходный город, т. е. найти

упорядоченный набор ck1,ck2,…,ckn и этот набор должен минимизировать суммарное расстояние обхода:

n−1	d(cki,ck(I+1))+d(ckn,ck1).	(7.3)
S = ∑
i =1

Эта задача, очевидно, алгоритмически разрешима, ибо можно перебрать все возможные варианты обходов и выбрать тот, для которого указанное суммарное расстояние минимально. Число обходов n городов равно M=(n-1)! / 2.

Легко найти, что число обходов n городов равно M=(n-1)! / 2. Известно [26], что число 50! имеет около 65 десятичных знаков. Пусть для выбора одного варианта обхода городов и вычисления величины S по формуле (7.3) требуется t0 = 0,001 секунд.

1.Оценить какое должно быть быстродействие ЭВМ которая переберет все варианты обхода городов задачи коммивояжера для n = 51 за миллиард лет непрерывной работы.

2.Оценить время непрерывной работы ЭВМ с современными вычислительными возможностями для перебора всех указанных в задаче 1 вариантов.

3.Построить алгоритм нахождения наибольшего элемента множества S, содержащего n действительных чисел, где n – степень числа 2, на базе стратегии дублирования. Оценить временную сложность построенного алгоритма.

4.Построить алгоритм нахождения наименьшего элемента множества S, содержащего n действительных неотрицательных чисел, на базе стратегии дублирования. Оценить временную сложность построенного алгоритма.

5.Пусть А массив размера n, состоящий из целых чисел

(положительных и отрицательных), причём А1<A2<…<An. Построить алгоритм нахождения числа i, для которого Аi=i (если такое i существует). Каков порядок времени работы алгоритма.

236

6.Построить алгоритм умножения двух полиномов степени n, где n=2k, k {1,2,3,…}, по стратегии дублирования и определить вычислительную сложность.

7.Доказать, что сложности умножения, деления, обращения и возведения в квадрат (M(n), D(n), R(n) и S(n)) целых двоичных чисел размера n совпадают с точностью до постоянных множителей и имеют порядок 0(nlog2n), если n – степень числа 2.

8.Доказать, что сложности умножения, деления, обращения и возведения в квадрат (M(n), D(n), R(n) и S(n)) полиномов степени n совпадают

сточностью до постоянных множителей и имеют порядок 0(nlog2n), если n – степень числа 2.