Ответы к экзамену 2010 (1133259), страница 3
Текст из файла (страница 3)
МТ(НМТ) распознает язык L за полиномиальное время, если онараспознает L и ∃p : ∀ω ∈ L∃ принимающее вычисление длины, не превышающейp(kωk)Опр. P - класс языков, распознаваемых МТ за полиномиальное времяП - мн-во отображений вида f : Aω → Aω , вычислимых МТ за полиномиальное11времяОпр.L и K - языки. Тогда L полиномиально сводится к К (L ≺ K), еслисуществует f ∈ Π : f (ω) ∈ K ⇔ ω ∈ LОпр.Языки L и K полиномиально эквивалентны, если L ≺ K и K ≺ LОпр.NP - класс языков, распознаваемых НМТ за полиномиальное времяОпр.Язык L - NP-полный, если L ∈ N P K ≺ L ⇒ K ∈ N PОпр.Язык выполнимости (ВЫП) состоит из слов в алфавите A = {(, ), &, ∨, 6, xi , i = 1, 2...}, представляющий собой выполнимые КНФ (т.е.
КНФ не равныетождественно 0)Опр.Пусть буква - произвольная булева переменная или ее отрицание; скобка формула вида (y1 ∨...∨yr , где yi - буква, r>1. К-КНФ - конъюнкция скобок, каждая изкоторых есть дизъюнкция не более к букв. Задача k-выполнимости - распознаваниевыполнимости k-КНФТеорема Задача 2-ВЫП распознается детерминированной МТ за полиномиальноевремя11Билет 10. Теорема С.КукаТеорема.
Если язык L ∈ N P , то L сводится к задаче выполнимостиД-воТ.к. L ∈ N P , существует НМТ, распознающая язык L за полиномиальное время.Пусть p(x) - полином и НМТ М такова, что М разпознает L и tM (ω) ≤ p(kωk) длялюбого слова ω ∈ LПостроим по произвольному слову ω КНФ A(ω) = A(ω, H, p) выполнимой тогдаи только тогда, когда ω ∈ L.Пусть A = {a1 , ..., al } - алфавит, a1 - пустой символQ = {q1 , ..., qr } - множество состояний.
q1 - начальное состояние, qr принимающее.Введем переменные, от которых будет зависеть строящаяся КНФ A(ω):i; 1 ≤ i ≤ l; 1 ≤ s, t ≤ T• Ps,ti= 1 ⇔ ячейка с номером s на шаге t содержит символ aiPs,t• Qjt ; 1 ≤ j ≤ r; 1 ≤ t ≤ TQjt = 1 ⇔ на шаге t МТ находится в состоянии qj• Ss,t ; 1 ≤ s, t ≤ TSs,t = 1 ⇔ на шаге t головка обозревает s-ю ячейку.Строим КНФ A(ω) = B&C&D&E&F &G, гдеB=T\Btt=1Bt - на шаге t обозревается одна и только одна ячейка:tol0 ko odnaobozrevaetsia{}|{ z \ }|z(Si,t ∨ Sj,t )Bt = (S1,t ∨ ...
∨ ST,t ) &1≤i<j≤T12C=T \T\Cs,ts=1 t=1, где Cs,t - на шаге t в ячейке s находится один и только один символD=t\Dtt=1, где Dt - в момент времени Т МТ находится в одном и только одном состоянии.i2i1in1&Pn+1,1 &...&PT,1&...&Pn,1&P2,1E = Q11 &S1,1 &P1,1Примечание - ω = ai1 , ..., ain |{z}. Всего T символов, т.к. дальше не уйдем за T| {z }T −nnшаговF =T \T\Fs,ts=1 t=1, где Fs,t а) если ячейка с номером s не обозревается на шаге t, то символ в ней неменяется; б) если ячейка с номером s обозревается на шаге t, то изменение символав ней происходит в соответствии с программой.Пусть Rs,t,i,j = 1 ⇔ на шаге t обозревается ячейка s и из того, что в ячейкенаходится символ ai и М находится в состоянии qj следует, что М действует всоответствии хотя бы с одной из команд, начинающихся с пары ai qj .Пример (в программе НМТ две команды)ai qj → ai1 qj1 Lai qj → ai2 qj2 Ri1i212i∨ Qjt ∨ Ps,t+1&Qjt+1&Ss−1,t+1 ∨ Ps,t+1&Qjt+1Тогда Rs,t,i,j = Ps,t&Ss+1,t+1Fs,t = Ss,t &(l\ii(Ps,t∨ Ps,t+1)) ∨ Ss,t &(i=1l _r_Rs,t,i,j )i=1 j=1G - МТ обязательно придет в принимающее состояниеG = Qr1 ∨ ...
∨ QrTПредставим каждый множитель B, C, D, E, F, G в виде КНФ, тогда A(ω) = 1 ⇔ω∈LСледствие Язык ВЫП - NP-полный.12Вопрос 11. NP-трудная задача 3-ВЫП, (0,1)целочисленное программированиеТеорема 3-ВЫП является NP-полнойОпр.Задача называется NP-трудной, если любой язык из NP сводится к этойзадаче.Опр.Задача называется NP-полной, если она NP-трудная и принадлежитклассу NP13Рис.
4: Схема сведения задачСхема сведения задач - Рис.5Задача ВЫП:Вход: КНФСв-во: выполнимостьЗадача 0-1 ЦЛП:Вход: м-ца A ∈ Rp×n , целочисленный вектор b = (b1 , ..., bp )Св-во: существует (0,1)-вектор x = (x1 , ..., xn ) : AxT ≥ bTТеорема Задача ВЫП сводится к 0-1 ЦЛП13Билет 12.
NP-трудные задачи: Клика, Вершинноепокрытие, Покрытие множестваЗадача КликаВход: граф G = (V, E), число kСвойство: в G существует полный подграф с k-вершинамиТеорема ВЫП сводима к КликаЗадача вершинное покрытиеВход: граф G0 = (V 0 , E 0 ), число l.Свойство: существует множество вершин R такое, что |R| ≤ l и при этом каждоеребро графа G инцидентно некоторой вершине из R.Теорема Задача Клика сводима к задаче вершинное покрытиеПокрытие множествВход: Семейство F = S1 , ..., Sm подмножеств множества S такое, что[Sj = SSj ∈F, число hСвойство: существует подсемейство T ⊂ F : |T | ≤ h и при этом[Sj = SSj ∈TТеорема Вершинное покрытие сводимо к покрытию множеств1414Билет 13.
NP-трудная задача РаскраскаЗадача РаскраскаВход: граф G = (V, E), число kСвойство: существует функция φ : V → Zk : φ(u) 6= φ(v) для всех (u, v) ∈ EТеорема Задача 3-ВЫП сводится к задаче РаскраскаД-воПусть К - 3-КНФ c n переменными и t скобками. Построим за время,ограниченное полиномом от max(n, t) граф G = (V, E) с 3n + t вершинами, которыйможно раскрасить в n + 1 цветов тогда и только тогда, когда К выполнима.Пусть x1 , ..., xn - переменные; C1 , ..., Ct - сомножители КНФ К.Пусть v1 , ..., vn - новые символы. n ≥ 4.Вершины графа G:• xi , xi , vi для 1 ≤ i ≤ n• ci для 1 ≤ i ≤ tРебра графа G:• Все (vi , vj ), i 6= j• Все (vi , xj ) и (vi , xj ), i 6= j• (xi , xi ), 1 ≤ i ≤ n• (xi , cj ), если xi не входит в cj и (xi ), cj ), если xi не входит в скобку cjВершины v1 , ..., vn образуют полный граф с n вершинами, значит, для ихраскраски требуется n цветов.
Каждая из вершин xj , xj соединена с каждой вершинойvi , i 6= j, значит, xj , xj не могут быть одного цвета с vi . Т.к. xj и xj смежны, они немогут быть раскрашены в один цвет. Значит, весь граф нельзя раскрасить меньше,чем в n+1 цвет. Граф G можно раскрасить ровно в n+1 цвет тогда и только тогда,когда одна из вершин xj , xj имеет тот же цвет, что и vj , а другая имеет новый цвет(специальный).Пусть той из вершин xj , xj , которая раскрашена в специальный цвет, приписанозначение 0.Рассмотрим цвет, приписанный вершине cj . Вершина cj смежна по краней мерес 2n − 3 из 2n вершин x1 , ..., xn , x1 , ..., xn .
Т.к. n ≥ 4, для каждой j найдется тако i,что cj смежна как с xi , так и с xi . Поскольку одна из этих вершин раскрашена вспециальный цвет, то cj не может быть раскрашена в специальный цвет.Если скобка cj содержит такой символ g, что вершине g приписан специальныйцвет, то вершина cj не смежна ни с какой вершиной, раскрашенной так же, как и g,значит, ей можно приписать тот же цвет, что и g.
Иначе нужен новый цвет, а запасауже нет=)Таким образом, все вершины ci можно раскрасить тогда и только тогда, когдасимволам можно так приписать специальный цвет, чтобы каждый сомножительсодержали такой символ g, чтобы символ g был раскрашен в специальный цвет, т.е.когда переменным можно так присвоить значения, чтобы в каждом сомножителеоказался g со значением 1, то есть когда КНФ выполнима1515Билет 14. Моделирование МТ схемами. ТеоремаСевиджа о моделировании вычисления (n,m)операторовРассмотрим детерминированную МТ с односторонней бесконечной лентой вправо.A = {a1 , ..., am } - алфавит лентыQ = {q0 , ..., qk } - алфавит состояний, q0 - начальное, qk - заключительноеΛ - пустой символ.В начальный момент времени на ленте записано слово x1 , ..., xn .Для моделирования будем применять обобщение СФЭ.На входе: А - ленточный алфавитe = Q ∪ {eНа выходе: Qq }, qe - холостое состояниеПереход от обобщенных схем к обычным (двоичным) связан с увеличениемсложности в константу раз (после предварительного кодирования букв алфавитовА и Q конечными двоичными последовательностями).Пусть МТ М работает на каждом слове длины n не более Т тактов.Построим обобщенную схему, к-рая моделирует работу М на словах длины n.Схема состоит из преобразующих элементов U и фильтрующих элементов Φ.Элемент U: 2 входа (ai ∈ A, qj ∈ Q), 4 выхода (a0i , qiL , qiR , qiS ), производиттождественное преобразование.• Если qj = qe, то a0i = ai ; qjR = qjL = qjS = qe• Если qj 6= qe, М отыскивает команду с левой частью ai qj (пусть правая частьal , qm , L).
Тогда a0i = al ; qjL = qm , qjR = qjS = qeeЭлемент Φ: входы (3 шт.(?)) и выход - символы алфавита Q• Если на одном из входов появляется символ, отличный от qe, он проходит навыход• Если на всех входах qe, то выход qeСлучай, когда несколько входов отличны от qe невозможен.Время работы МТ над словом x1 , ..., xn не превосходит Т, то есть головка можетуйти вправо от начального положения не более, чем на Т ячеек. Значит, достаточнодержать в поле зрения зону ленты в Т ячеек, пронумерованных числами от 1 до Т.Схема имеет прямоугольный вид: Т двухъярусных строк и Т столбцов. При этом i-ястрока выходами своих Т элементов представляет i-ю конфигурацию МТ.Теорема (Дж. Сэвидж).
Пусть МТ М работает на словах длины n не более2TM (n) тактов. Тогда ее можно моделировать СФЭ сложности O(TM(n))16Билет 15. Самокоррекция КС. Тривиальная самокоррекция.Примеры нетривиальной самокоррекции КСПусть U - класс управляющих систем. Н - источник неисправностей. Возьмемуправляющую систему U ∈ U, где U = (Σ, f ). f1 , ..., fr (f1 = f ) - функциинеисправностей, вызываемые источником Н16Рис. 5: часть СФЭ для МТОпр.Схема Σ называется самокорректирующейся (относительно источникаН), если для всех i fi = fВ качестве источника неисправностей возьмем Ha,b , вызывающий не более аразрывов и b замыканий в контактной схеме.ПримерТривиальная самокоррекция КС: f=x, a обрывов, b замыканий: Рис.6Рис.
6: тривиальная самокоррекцияПримерНетривиальная самокоррекция КС: h(x1 , x2 , x3 ) = x1 x2 ∨ x1 x3 ∨ x2 x3 : Рис.7*сюда же добавить то, что было на семинарах*17Рис. 7: нетривиальная самокоррекция17Билет 16. Асимптотика функции Шеннона дляКС, корректирующих одно замыкание (или одинобрыв) контактаПусть La,b (f ) - сложность минимальной самокорректирующейся схемы относительноHa,b , реализующей ф-ю f. La,b (n) - соответствующая функция Шеннона.Теорема (Потапов, Яблонский) Существует метод синтеза, позволяющийдля каждой булевой ф-и f (x1 , ..., xn ) строить самокорректирующуюся относительноnH0,1 схему Σcf такую, что L(Σcf (x1 ,...,xn ) ) . 2n*Как-то тут мало букв, может, что еще стоит написать*18Билет 17.
Тесты. Алгоритмы построения всехтупиковых тестов. Нижние оценки длины тестовдля таблиц. Верхняя оценка длины теста дляпочти всех таблицОпр.Тест - множество наборов значений переменных, которое позволяет установить,какая неисправность произошла или определить, исправна ли схемаОпр.Тупиковый тест - тест, который перестает быть тестом при удалениилюбого набораОпр.Минимальный тест - тест, который имеет минимальную мощностьОпр.Проверяющий тест - множество наборов, позволяющее отличить исходнуюфункцию от неисправныхОпр. Диагностический тест - множество наборов, различающих все неисправностиЗадача сводится к тестам для таблицы А (таблица m x n, из нулей и единиц).Диагностический тест для таблицы А - такое множество строк, что вподматрице A0T , образованной этими строками все столбцы различны между собой.Проверяющий тест для таблицы А - такое множество строк, что вподматрице A0T все столбцы, начиная со 2го отличаются от 1го.Найдем таблицу с максимальным размером минимального теста.
При m=nрассмотрим диагональную таблицу. Размер ее диагностического теста будет n-1.Тривиальная оценка размера теста - nТеорема (нижняя оценка длины тестов (каких?))A - матрица m x n. Все столбцы A попарно различны. Пусть l(A) - длинаминимального теста. Тогда l(A) ≥ log2 n.18Оценим сверху длину минимального теста для почти всех таблицОпр. Почти все таблицы А размера m x n обладают свойством q, если доля техА, к-рые обладают этим св-вом стремится 1 при n → ∞ТеоремаПусть K0 (n) = 2 log2 n + φ(n), где φ(n) → ∞ при n → ∞Пусть m ≥ K0 (n)Тогда почти все таблицы А размена m x n обладают тестом длины K0 (n)18.1Алгоритм построения всех тупиковых тестов для таблицЗадана А размера m x n.По ней строим матрицу A(2) , состоящую из сумм по модулю 2 всех пар столбцовматрицы АУтв.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
