Рубрики

Структуры данных и алгоритмы | Комплект 20

Следующие вопросы задали на экзамене GATE CS 2006.

1. Пусть S — NP-полная задача, а Q и R — две другие проблемы, о которых неизвестно, что они есть в NP. Q сводится за S за полиномиальное время, а S сводится к R. за полиномиальное время. Какое из следующих утверждений верно?
(A) R является NP-полным
(B) R является NP-сложным
(C) Q является NP-полным
(D) Q — NP-сложный

Ответ (Б)
(A) Неправильно, потому что R не в NP. NP Полная задача должна быть как в NP, так и в NP-сложности.
(B) Верно, потому что NP Полная задача S полиномиально обучаема R.
(C) Неправильно, потому что Q не в NP.
(D) Неправильно, потому что не существует NP-полной задачи с полиномиальным временем, сводимой по Тьюрингу к Q.

2) Множество X может быть представлено массивом x [n] следующим образом:

Рассмотрим следующий алгоритм, в котором x, y и z являются логическими массивами размера n:

algorithm zzz(x[] , y[], z [])
{

   int i;

   for (i=O; i<n; ++i)

     z[i] = (x[i] ^ ~y[i]) V (~x[i] ^ y[i])

}

Множество Z, вычисленное по алгоритму:
(A) (X пересечение Y)
(B) (X Союз Y)
(C) (XY) Пересечение (YX)
(D) (XY) Союз (YX)

Ответ (D)
Выражение x [i] ^ ~ y [i]) возвращает только 1 с в x, где соответствующая запись в y равна 0. Массив с этими установленными битами представляет собой набор X — Y
Выражение ~ x [i] ^ y [i]) дает только 1 с в y, где соответствующая запись в x равна 0. Массив с этими установленными битами представляет собой набор Y — X.
Оператор «V» приводит к объединению двух вышеуказанных множеств.

3. Рассмотрим следующее повторение:

Что из следующего верно?
(A) T (n) = Θ (логлогиния)
(B) T (n) = Θ (logn)
(C) T (n) = Θ (sqrt (n))
(D) T (n) = Θ (n)

Ответ (Б)

  Let n = 2^m
  T(2^m) = T(2^(m/2)) + 1
  Let T(2^m) =  S(m)
  S(m)  = 2S(m/2) + 1  

Выше выражением является рекурсия обхода двоичного дерева, временная сложность которой составляет Θ (m). Вы также можете доказать, используя теорему мастера .

S(m)  = Θ(m)  
      = Θ(logn)  /* Since n = 2^m */

Теперь вернемся к исходной рекурсивной функции T (n).

  T(n)  = T(2^m) = S(m)
                 = Θ(Logn)

Обратите внимание, что решение T (n) = T (√n) + 1 — это Θ (Log Log n), выше повторяемость отличается, это T (n) = 2T (√n) + 1

Пожалуйста, пишите комментарии, если вы найдете какие-либо неправильные ответы / объяснения, или вы хотите поделиться дополнительной информацией по темам, обсужденным выше.

Рекомендуемые посты:

Структуры данных и алгоритмы | Комплект 20

0.00 (0%) 0 votes