В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов, А.А. Сапоженко, С.Н. Селезнева - Задачи по курсу Основы кибернетики, страница 2

Алфавиты A и Q конечны. Символом q1 обозначаетсяначальное состояние, символом a1 — пустой символ, присутствующий поопределению в алфавите A. Считается, что в начальный момент слово w = b1 b2 . . . bn , обрабатываемое МТ, записано в первых n ячейкахленты, а все остальные ячейки ленты содержат символ a1 . Детерминированность МТ означает, что для каждой пары вида (a, q), где a —символ входного алфавита, а q — символ состояния, в программе МТприсутствует не более одной команды вида: aq → a0 q 0 d, начинающейся сaq.Пусть в процессе работы МТ на некотором такте t оказалось, что наленте записано слово w = b1 b2 .

. . bm . Это означает, что в первых m ячей-ках ленты содержатся символы b1 , . . . , bm , а ячейки, начиная с (m + 1)-й,содержат символ a1 . Пусть далее на такте t МТ находится в состоянии qj ,а головка обозревает ячейку с номером k. Конфигурацией (мгновеннымописанием), соответствующей этому такту t, называется слово Ct видаb1 b2 . .

. bk−1 qj bk . . . bm . Конфигурация, соответствующая первому такту,называется начальной, а последнему (если МТ останавливается), — заключительной. Вычислением МТ M на входе w называется последовательность конфигураций C1 , C2 , ..., Ct , ..., возникающая при работе надсловом w. Подразумевается, что конфигурация Ct+1 однозначно определяется конфигурацией Ct и командой МТ M , начинающейся с пары(bk , qj ), где bk — символ, обозреваемый МТ в момент t, а qj — состояниеМТ в момент t.

Время работы или число шагов tM (w) МТ M на входеw определяется как число конфигураций в вычислении МТ M на входе w. Если вычисление бесконечно, полагаем tM (w) = ∞. Пусть средисостояний МТ имеются выделенные заключительные состояния — принимающее и отвергающее. Тогда вычисление называется принимающим(отвергающим), если оно заканчивается в принимающем (отвергающем)состоянии.Недетерминированные машины Тьюринга. Отличие недетерминированной МТ (сокращенно, НМТ) от детерминированной состоит втом, что в программе НМТ для пары (a, q), где a — символ из алфавита МТ, а q — символ состояния, в ее программе может присутствоватьнесколько команд, начинающихся с aq. Без потери общности можно ограничиться случаем, когда паре aq может соответствовать не более двухкоманд c началом aq.

Пусть в программе НМТ имеется пара командaq → a0 q 0 L и aq → a00 q 00 R. Тогда, находясь в состоянии q и обозреваясимвол a на ленте, НМТ может выбрать любую из двух возможностей:записать в обозреваемую ячейку символ a0 , перейти в состояние q 0 и сдвинуть головку влево, либо записать в обозреваемую ячейку символ a00 , перейти в состояние q 00 и сдвинуть головку вправо. При этом считается, чтоНМТ как бы создает две копии самой себя и прослеживает последовательность вычислений обоих способов действия. Понятие конфигурациидля НМТ не отличается от того, что определено выше для обычной МТ.Вычислением НМТ на входе w называется последовательность конфигураций C1 , C2 , ..., Ct , ..., в которой C1 = q1 w, а Ct+1 получается из Ctс помощью одной из команд, соответствующих паре a(t)q(t), где q(t) —символ состояния, входящий в Ct , а a(t) — буква из Ct , стоящая справаот q(t).

Всякое вычисление можно изобразить ориентированной цепью,вершинами которой являются конфигурации, а каждая дуга соединяетдве последовательные вершины. В случае детерминированных МТ вычисление однозначно определяется входом. В случае НМТ объединениецепей, соответствующих вычислениям на входе w, представляет собойориентированное (от корня) дерево с корнем C1 = q1 w.Распознавание языков. Пусть A — конечный алфавит. Через Aωобозначим множество всех слов (конечных последовательностей) в алфавите A.

Через ||w|| обозначим длину слова w, определяемую как число букв в w. Произвольное подмножество L ⊆ Aω называется языкомв алфавите A. Говорят, что МТ (НМТ) M с двумя заключительнымисостояниями (принимающим и отвергающим) распознает язык L, если для всякого слова w ∈ Aω принимающее вычисление M на входе wсуществует тогда и только тогда, когда w ∈ L.

В случае, когда w 6∈ L,каждое вычисление либо бесконечно, либо является отвергающим. Говорят, что МТ (НМТ) M распознает язык L за полиномиальное время,если она распознает L и существует полином p такой, что для каждогослова w ∈ L существует принимающее вычисление длины, не превышающей p(||w||).Через P обозначим класс языков, распознаваемых МТ за полиномиальное время. Через Π обозначим множество отображений вида f :Aω → Aω , вычисляемых МТ за полиномиальное время. Пусть L1 и L2— языки. Говорят, что L1 (полиномиально) сводится к L2 (обозначениеL1 ≺ L2 ), если существует функция f ∈ такая, что w ∈ L1 ⇔ f (w) ∈ L2 .Языки L1 и L2 (полиномиально) эквивалентны, если L1 ≺ L2 и L2 ≺L1 .Определение 2.1.

Класс NP есть множество языков, распознаваемых НМТ за полиномиальное время.Пусть P2 — множество пар (L, M ) языков из P. Говорят, что язык Kвыводим из пары (L, M ), путем навешивания p-ограниченного кванторасуществования, если существует такой полином p, чтоK = {x : ∃y(x, y) ∈ (L, M ) & ||y|| ≤ p(||x||)},где ||z|| — длина слова z.Определение 2.2. Класс NP есть множество языков, выводимых изэлементов P2 путем навешивания p-ограниченного квантора существования.Язык L называется N P -полным, если1) L ∈ NP.2) для любого языка L0 из NPL0 ≺ L.Справедливы следующие простые утверждения.Утверждение 2.1.

Если L1 ≺ L2 и L2 ≺ L3 , то L1 ≺ L3 .Утверждение 2.2. Если L1 ∈ P и L2 ≺ L1 , то L2 ∈ P.Утверждение 2.3. P ⊆ NP.Утверждение 2.4. Либо все N P -полные языки принадлежат P, либони один из них не принадлежит P. Первая ситуация имеет местотогда и только тогда, когда P=NP.Конъюнктивная нормальная форма (КНФ) называется выполнимой,если найдется набор значений ее переменных, на котором эта КНФ обращается в единицу. Пусть K — множество всех выполнимых КНФ, A —некоторый конечный алфавит, а ψ — взаимно однозначное отображениеK во множество слов в алфавите A. Для определенности рассмотрималфавит A = {(, ), &, ∨, ¬, x, 0, 1}, а отображение ψ определим следующим образом: буква вида xσi преобразуется в слово xστ1 .

. . τl , где τ1 . . . τlдвоичное представление числа i; остальные символы не изменяются. Например, если K = x1 &(x̄2 ∨ x5 ), то ψ(K) = x11&(x010 ∨ x1101). ЯзыкВЫПОЛНИМОСТЬ (сокращенно ВЫП) представляет собой образ ψ(K)множества K при отображении ψ. Язык К-ВЫП есть образ множестватех выполнимых КНФ, у которых каждая скобка содержит не более kбукв.Теорема 2.5. (S. A. Cook [4] – [3], [7]) Если L ∈ NP, то L ≺ ВЫП.Существует достаточно большой класс задач, заключающийся в распознавании тех или иных свойств графов, целых чисел, массивов целыхчисел, конечных множеств, булевых формул и т.

д. Подходящей кодировкой такие задачи могут быть сведены к распознаванию языков. Поэтомув дальнейшем мы будем взаимозаменять термины “язык” и “задача”. Задачи из класса P будем называть полиномиально решаемыми.Ниже приведены некоторые N P -полные задачи.1. Задача 0-1 Целочисленное линейное программирование (0-1 ЦЛП).Вход: Матрица A = (aij ) размера p × n и целочисленный вектор b =(b1 , . . .

, bp ).Свойство: Существует вектор x = (x1 , . . . , xn ) из нулей и единиц такой,чтоAxT ≥ bT .2. Задача КЛИКА.Вход: Граф (G, E), число k.Свойство: В графе G существует полный подграф на k вершинах (графназывается полным, если любые две его различные вершины соединеныребром).3. Задача ВЕРШИННОЕ ПОКРЫТИЕ.Вход: Граф G = (V, E), число l.Свойство: Существует такое подмножество вершин R, что |R| ≤ l икаждое ребро графа G инцидентно некоторой вершине из R.4. Задача ПОКРЫТИЕ МНОЖЕСТВА.S Вход: Семейство F = {S1 , . . .

, Sm } подмножеств множества S, причемSj ∈F = S, число h.S Свойство: Существует такое подсемейство T ⊆ F , что |T | ≤ h иSj ∈T = S.5. Задача РАСКРАСКА.Вход: Граф G = (V, E), число k.Свойство: Существует такая функция χ : V → {1, 2, . . . , k}, чтоχ(u) 6= χ(v) для всех (u, v) ∈ E.2.1. Пусть A — алфавит символов ленты МТ, A = {0, 1, Λ}, входноеслово записано в алфавите {0, 1}, Λ — пустой символ.Положим t(n, L) = min max t(w), где минимум берется по всемw∈L,||w||=nМТ, распознающим язык L.Показать, что t(n, L) = O(f (n)), если:1) L — множество всех слов, содержащих подслово вида 111, f (n) = n;2) L — множество всех слов, в которых нет подслов вида 11, f (n) = n;3) L — множество всех слов, в которых нечетное число единиц, f (n) =n;4) L — множество всех слов, в которых число символов кратно 3,f (n) = n;5) L — множество всех слов, которые не являются числами — степенями двойки, записанными в двоичной системе счисления, f (n) = n;6) L — множество всех слов, в которых после каждой единицы естьхотя бы один ноль, f (n) = n;7) L — множество всех слов, в которых нет трех нулей подряд, f (n) =n;8) L — множество всех симметричных слов, f (n) = n2 .2.2.

Пусть A — алфавит символов ленты МТ, A = {0, 1, Λ}, входноеслово записано в алфавите {0, 1}, Λ — пустой символ.Оценить сверху время работы МТ, выясняющей1) делится ли число единиц в слове на 3;2) равно ли число единиц в слове числу нулей;3) в любом начальном отрезке слова число единиц не меньше числанулей;4) слово периодично, т.

е. найдется такое слово u в алфавите {0, 1} итакое число n ≥ 2, что входное слово имеет вид uu. . . u};| {zn раз5) по двум словам u и v, разделенным символом Λ, является ли словоu подсловом слова v.2.3. Пусть A — алфавит символов ленты МТ, A = {0, 1, Λ}, Λ — пустойсимвол. Оценив сверху время работы МТ, осуществляющей следующеепреобразование, доказать что оно лежит в Π:1) сложение двух целых чисел в двоичной записи;2) умножение двух целых чисел в двоичной записи;3) нахождение остатка от деления одного целого числа в двоичнойзаписи на другое;4) нахождение определителя квадратной матрицы из нулей и единицв поле E2 из двух элементов с операциями ⊕ и &;5) умножение двух квадратных матриц из нулей и единиц в поле E2из двух элементов с операциями ⊕ и ·;6) решение системы линейных уравнений в поле E2 из двух элементовс операциями ⊕ и ·;7) нахождение значения булевой функции по формуле над базисом{&, ∨, ¬} на наборе (α1 , .

. . , αn ) значений переменных;8) нахождение корня полинома Жегалкина, т. е. набора, на которомполином обращается в ноль;9) нахождение кратчайшего расстояния между данной парой вершинв графе;10) построение остовного дерева графа.2.4. Раскрасить граф G в k цветов:1) G - граф на рис. 1, k = 4;2) G - граф на рис. 3, k = 3;3) G - граф на рис. 5, k = 2;4) G - граф на рис. 7, k = 3.2.5.