Масові задачі

ЛЕКЦІЯ 7. Складність обчислень

Масова задача G визначається списком параметрів і формулюванням властивостей відповіді.

Приклад. 1). Задача про комівояжера (на повному зваженому графі).

Параметри: набір міст C = { c₁,..., c_m) і відстаней d (c_i, c_j) між ними.

Вид відповіді: упорядкований набір міст < c_g(1),..., c_g (m)>, що мінімізує величину шляху

d (c_g (i), c_g (i +1) + d (c_g (m), c_g (1)) £ B.

2). Перебування максимального елемента в масиві. Параметри: масив x(1), x(2), …< x(n)... Вид відповіді: числа m, j, такі, що m – max_1£k£nx(k) = x(j), причому j – максимальне з усіх можливих.

3). Выполнимость конъюнктивной нормальної форми (КНФ). Параметри: кількість перемінних, від яких залежить КНФ, і довжина формули. Вид відповіді: знайти хоча б один набір значень перемінних, при якому КНФ дорівнює 1, або довести, що дана КНФ дорівнює нулеві.

Індивідуальна задача I виходить з G, якщо всім параметрам G привласнені конкретні значення.

Алгоритм A вирішує задачу G, якщо він вирішує будь-яку задачу I з G.

Дата добавления: 2014-01-07