7.1

Упражнения

[12/17%]
Показать
LaTeX
Задача 7.1

Ответьте ВЕРНО или НЕВЕРНО для каждого пункта.

?
(a)

2n=O(n)2 n=O(n).

(b)

n2=O(n)n^{2}=O(n).

(c)

n2=O(nlog⁡2n)n^{2}=O\left(n \log^{2} n\right).

(d)

nlog⁡n=O(n2)n \log n=O\left(n^{2}\right).

(e)

3n=2O(n)3^{n}=2^{O(n)}.

(f)

22n=O(22n)2^{2^{n}}=O\left(2^{2^{n}}\right).

Задача 7.2

Ответьте ВЕРНО или НЕВЕРНО для каждого пункта.

?
(a)

n=o(2n)n=o(2 n).

(b)

2n=o(n2)2 n=o\left(n^{2}\right).

(c)

2n=o(3n)2^{n}=o\left(3^{n}\right).

(d)

1=o(n)1=o(n).

(e)

n=o(log⁡n)n=o(\log n).

(f)

1=o(1/n)1=o(1 / n).

Задача 7.3

Какие из следующих пар чисел взаимно просты? Приведите вычисления, обосновывающие ваш ответ.

?
(a)

1274 и 10505

(b)

7289 и 8029

Задача 7.4

Заполните таблицу, описанную в алгоритме распознавания контекстно-свободных языков за полиномиальное время из теоремы 7.16, для строки w=w= baba и КС-грамматики GG:

S→RTR→TR∣aT→TR∣b \begin{aligned} & S \rightarrow R T \\ & R \rightarrow T R \mid \mathrm{a} \\ & T \rightarrow T R \mid \mathrm{b} \end{aligned}
?
Задача 7.5

Выполнима ли следующая формула?

(x∨y)∧(x∨yˉ)∧(xˉ∨y)∧(xˉ∨yˉ) (x \vee y) \wedge (x \vee \bar{y}) \wedge (\bar{x} \vee y) \wedge (\bar{x} \vee \bar{y})
?
Задача 7.6

Покажите, что P замкнут относительно объединения, конкатенации и дополнения.

?
Задача 7.7

Покажите, что NP замкнут относительно объединения и конкатенации.

?
Задача 7.8

Пусть CONNECTED={⟨G⟩∣G — связный неориентированный граф}C O N N E C T E D=\left\{ \langle G\rangle \mid G\text{ — связный неориентированный граф}\right\}. Проанализируйте алгоритм, приведённый на стр. 185, чтобы показать, что этот язык принадлежит P.

?
Задача 7.9

Треугольником в неориентированном графе называется 3-клика. Покажите, что TRIANGLE ∈P\in \mathrm{P}, где TRIANGLE ={⟨G⟩∣G содержит треугольник}=\left\{ \langle G\rangle \mid G\text{ содержит треугольник}\right\}.

?
Задача 7.10

Покажите, что ALLDFA A L L_{\text{DFA }} принадлежит P.

?
Задача 7.11

В обоих пунктах приведите анализ временной сложности вашего алгоритма.

?
(a)

Покажите, что EQDFA∈PE Q_{\mathrm{DFA}} \in \mathrm{P}.

(b)

Будем говорить, что язык AA замкнут относительно звезды, если A=A∗A=A^{*}. Приведите полиномиальный алгоритм проверки того, распознаёт ли ДКА язык, замкнутый относительно звезды. (Заметим, что про EQNFA E Q_{\text{NFA }} неизвестно, принадлежит ли он P.)

Задача 7.12

Назовём графы GG и HH изоморфными, если вершины GG можно так переупорядочить, чтобы граф стал идентичен HH. Пусть ISO={⟨G,H⟩∣G и H — изоморфные графы}I S O=\left\{ \langle G, H\rangle \mid G\text{ и }H\text{ — изоморфные графы}\right\}. Покажите, что ISO∈NPI S O \in \mathrm{NP}.

?