В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (скан) (1132786), страница 2
Текст из файла (страница 2)
Понятие конфигурации для НМТ не отличается от того, что определено выше для обычной МТ, Вычислением НМТ на входе ю называется последовательность конфигУРацнй С«Сг, -, Сь ..., в которой С« = д«ю, а С«»«получается из С« с помощью одной из команд, соответствующих паре а(г)ч(г), где ч(е)— символ состояния, входящий в С„а а(т) — буква из С«, стоящая справа от о(г). Всякое вычисление можно изобразить ориентированной цепью, вершинами которой являются конфигурации, а кзждая дуга соединяет две последовательные вершины. В случае детерминированных МТ вычисление однозначно определяется входом, В случае НМТ объединение цепей, соответствующих вычислениям на входе ю, представляет собой ориентированное (от корня) дерево с корнем С« = й«ю.
Распознавание языков. Пусть А — конечный алфавит. Через А" обозначим множество всех слов (конечных последовательностей) в алфавите А. Через ЦюЦ обозначим длину слова ю, определяемую как число букв в ю, Произвольное подмножество В С А называется языкам в алфавите А. Говорят, что МТ (НМТ) М с двумя заключительными состояниями (принимакпцим и о«пеергающим) распознает язык Ь, если для всякого слова ю й А' принимающее вычисление М на входе ю существует тогда и только тогда, когда ю Е Ь, В случае, когда ю й Ь, каждое вычисление либо бесконечно, либо является отвергающим. Говорят, что МТ (НМТ) М распознае«п язык Ь за полиномиальное время, если она распознает Ь и существует полипом р такой, что для каждого слова ю й Ь существует принимающее вычисление длины, не превышающей р(Ци Ц).
Через Р обозначим класс языков, распознаваемых МТ за полиномиальное время. Через П обозначим множество отображений вида Г: А -«А', вычисляемых МТ за полиномигльное время, Пусть В«и Вг — языки. Говорят, что В«(полиномиально) своей««пся к Вг (обозначение б« -с Ьг), сели существует функция з й такая, что ю й Ь«гь Дю) й Ьг.
Языки Ь«и Вг (полинами«ь«ьно) зквиеалгн«пнм, если Ь«ч Вг и г г -е В«, Определение 2.1. Класс ХР есть множество языков, распознаваемь«х НЫТ за полиномиельное время. Пусть Рг — множество нар (Ь, М) языков из Р. Говорят, что язык К выводим из пары (Ь, М), пу«пем навек«иеания р-ограниченного кван«пера сущгсп«зевания, если существует такой поливом р, что К = (х: Зу(х, у) й (ь, М) Ле ЦуЦ < р(ЦхЦ)), где ЦгЦ вЂ” длина слова г.
Определение 2.2. Класс ХР есть множество языков, выводимых из элементов Рг путем навешивания р-ограниченного квантора существования. Язык Ь называется ХР-полным, если 1)7 АКР. 2) для любого языка Е' из ХРЪ' -< Е. Справедливы следующие простые утверждения, Утверждение 2.1.
Если Ь! -с бг и Ег -с Ег, то Е| -< Ег. Утверждение 2.2. Если 71 б Р и Ег -с Ьм то Ег б Р. Утверждение 2.3. Р С ХР. Утверждение 2.4. г7ибо все ХР-полные языки принадлежат Р, либо ни один из них не принадлежит Р. Первая ситуация имеет месгпо тогда и только тогда, когда Р=ХР. Конъюнктнвная нормальная форма (КНФ) называется выполнимой, если найдется набор значений ее переменных, на котором эта КНФ об- ращается в единицу. Пусть К вЂ” множество всех выполнимых КНФ, А— некоторый коночный влфавит, а Р— взаимно однозначное отображение а. во множество слов в алфавите А.
Для определенности рассмотрим алфавит А = ((, ), й, У„, х, О, 1), а отображение Ф определим следую- щим образом: буква вида х," преобразуется в слово хсгт1... ти где т1... тс двоичное представление числа г; остальные символы не изменяются. На- пример, если А = х~бс(хг ~г хь), то г'(К) = х118с(х010 Ч х1101). Язык ВЫПОЛНИМОСТЬ (сокращенно ВЫП) представляет собой образ ф(К) множества 1С при отображении Ф. Язык К-ВЫП есть образ множества тех выполнимых КНФ, у которых каждая скобка содержит не более к букв.
Теорема 2.3. (Б. А. Соой [4[ — [3[,[7[) Если Е й ХР, то Ь.с ВЫП. Существует достаточно большой класс задач, заключающийся в рас- познавании тех или иных свойств графов, целых чисел, массивов целых чисел, конечных множеств, булевых формул и т. д. Подходящей кодиров- кой такие задачи могут быть сведены к распознаванию языков. Поэтому в дальнейшем мы будем взаимозаменять термины "язык" и "задача", За- дачи из класса Р будем называть полиномиально решаемыми.
Ниже пркведены некоторые )с'Р-полные задачи. 1. Задача 0-1 Целочисленное линейное программирование (0-1 ЦЛП). Вход: Матрица А = (а; ) рвзмера р х и и целочисленный вектор Ь = (Ьь...,б„'). Свойство; Существует вектор х = (х„..., х„) из нулей и единиц такой, что А т>Ьт 2. Задача КЛИКА. Вход: Граф (С, Е), число /с. Свойство: В графе С существуег полный подграф на 1с вершинах (граф называется полным, если любые две его различные вершины соединены ребром). 3. Задача ВЕРШИННОЕ ПОКРЫТИЕ.
Вход: Граф С = (У, Е), число 1. Свойство: Существует такое подмножество вершин В, что [В[ < 1 и каждое ребро графа С инцидентно некоторой вершине из В. 4, Задача ПОКРЫТИЕ МНОЖЕСТВА. Вход: Семейство Р = (ом..., о',„) подмножеств множества о', причем ()з г —— 5, число Л. Свойство: Существует такое подсемейство Т С Р, что [Т[ < И и [.)з,ет 5.
Задача РАСКРАСКА, Вход: Граф С = (У, Е), число lс. Свойство: Существует такая функция Х: У -+ (1,2,...,к), что 1С(и) ф ~(и) для всех (и, и) й Е. 2.1. Пусть А — алфавит символов ленты МТ, А = (О, 1, Л), входное слово записано в алфавите (О, 1), Л вЂ” пустой символ. Положим 1(п, Е) = ппп шах 1(и), где мииимулс берегся по всем ведймй в МТ, распознающим язык Е. Показать, что г(п, б) = 0(г(п)), если: 1) б — множество всех слов, содержащих подслово вида 111, Дп) = и ) 2) Š— лсножество всех слов, в которых нет подолов вида 11, Дп) = и 3) Š— множество всех слов, в которых нечетное число единиц, 1(п) = 4) Ь вЂ” множество всех слов, в которых число символов кратно 3, 7'(и) = п; о) Š— множество всех слов, которые не являются числами — степенями двойки, записанными в двоичной системе счисления, 1(п) = и; 6) Б — множество всех слов, в которых после каждой единицы есть хотя бы один ноль, Дп) = и; 7) Š— множество всех слов, и которых нет трех нулей подряд, Дп) = и; 8) Š— множество всех симметричных слов, Дп) = пг.
ш м 2.2. П1тгь А — алфавит символов ленты МТ„А = (О, 1, Л), вход„ елово записано в алфавите (О, Ц, Л вЂ” пустой символ. Оценить сверху время работы МТ, выясняющей 1) делится лк число единиц в слове на 3; 2) равно лн число единкц в слове числу нулей; 3) в любом начальном отрезке слова число единиц не меньше числа нулей; 4) слово периодично, т. е, найдется такое слово и в алфавите (О, 1) и такое число и > 2, что входное слово имеет вид ми., д и раз 5) по двум словам и и и, разделенным символом Л, являегся ли слово и подсловом слова и. 2.3.
Пусть А — алфавит символов ленты МТ, А = (О, 1, Л), Л вЂ” пустой символ. Оценпв сверху время работы МТ, осуществляющей следующее преобразование, доказать что оно лежит в ПО 1) сложение двух целых чисел в двоичной записи; (~ умножение двух целых чисел в двоичной записи; 3) нахождение остатка ог деления одного целого числа в двоичной записи на другое; ® нахождение определителя квапратной матрицы из нулей и единиц в поле Еа из двух элементов с операциями Ю н Й; ~5) умножение двух квадратных матриц из нулей и единиц в поле Ез из двух элементов с операциями ® и; ",6) решение системы линейных уравнений в поле Ез из двух элементов с операциями 61 и ", .3 нахождение значения булевой функции по формуле над базисом (бб, ч, ) на набоРе (аь..., а„) значений пеРеменных; (9 нахождекие корня полннома Жегалкина, т.
е. набора, на котором полипом обращается в ноль; 9) нахождение кратчайшего расстояния между данной парой вершин в графе; 10) построение остовного дерева графа. 2.4. Раскрасить граф С в и цветов: 1) С- граф парис. 1, и = 4; 2) С- граф парис. 3, и =3; 3) С - граф иа рнс. 5, и = 2; 4) С - граф на рис. 7, )б = 3, 12 Рма л бх - ье~.~ я б ~~2ф Найти размер максиб~альной клики графа С: 1) С - граф на рис. 2; 2) С - граф на рис. 5; 3) С - граф на рис, 8; 4) С- граф парис. 9.
2.6. Найти минимальное всршиняое покрытие графа С: 1) С- граф на рис. 1; 2) С - граф на рнс. 2; 3) С- граф на рис. 3; 4) С- граф парис. 6. 2.7. 1. Доказать полнномиальную рсшаемость задачи 2-ВЫП. 2. Продемонстрировать работу полнномиального алгоритма для задачи 2-ВЫП на примере входа К, если 1) л = (х1 чхе)(х2 ч хз)(х2 ч хднф ч хб)хб(хб ч хбПх1 ч хб)(хб чх1]1 2) К = (х1 ч хб)х1(хб ч хб)(хб ч хб)(ххя ч хб)хб(хз ч хб)(хз'ч хб). 2.8, Продемонстрировать работу жадного алгоритма дчя задачи поиска минимального сотенного дерева на примере входа С: С: 2.9.
Доказать, что следующие задачи принадлежат классу МР. 1) Задача И: Вход: граф С = (К Е), число к. Вопрос есть ли в графе С простой цикл длины Й? Доказать, что И 6 ХР. 2) Задача 52: Вход: граф С = (К Е), число и. Вопрос: есть ли в графе С вершина степени )б? Доказать, что 52 6 ХР. бб 3) Задача ХЗ: Вход: матрица М из 0 и 1 размера и х т, число к. Вопрос: есть ли покрытие матрицы М мощности (г (множество строк матрицы М называется ее покрытием, если в образованной ими подматрице нет нулевых столбцов)1 Доказать, что ХЗ 6 (ч(Р. 4) Задача ХА: Вход: матрица М из 0 н 1 размера и х гл без совпедвющих столбцов, число (г Вопрос; есть ли тест лля матрицы М длины (г (множество строк матрицы М называется тестом, если в образованной ими подматрице все столбцы различны; длиной теста называется число строк в нем)? Доказать, что ХА 6 й!Р.
2.10. ПостРоить пРсобРазование входа задачи Хч во вход задачи Хг, доказывающее полипомиальпую сводимосгь языка Х,! к языку Х.г, 1) Ь! есть ВЫП, Хг есп 0-1 ЦЛП; 2) Х ! есть ВЫП, Х,г есть 3-ВЫП; 3) Х,1 есть КЛИКА, Хг есть ВЕРШИННОЕ ПОКРЫТИЕ; 4) Х! есть ВЕРШИННОЕ ПОКРЫТИЕ, Хг есть ПОКРЫТИЕ МНО- ЖЕСТВ. 2.11. Даиный вход К задачи ВЫП преобразовать во вход К' задачи 3-ВЫП: 1) К = (х1 ч х2 ч хзчх4)(х1 ч х2 ч УЗ ч 24НУЗ ч хз ч х4) 2) К = (хзчх!чхгчхзчх4)хз(хгчхгчхзчхзНхзчх4НХ!чхзчх4чхз) 2.12. По КНФ К построить 0-1 матрицу А и вектор 5, являкнциеся входом задачи 0-1 ЦЛП, соответствующим КНФ К: 1) К (х! ч Уг)(х! ч хз) 2) К = (Х1 Ч Хг Ч ХЗ) (Х1 Ч ХЗ); 3) К =- (х! ч хг ч хз)(х! ч Уг ч У !); 4) К = (Х1 Ч Уг Ч хз)(21 Ч хг Ч хз); 5) К = (Х1 ч хг ч хз ч хз)(хг ч хг)(хг ч хз); 6) К = (х1 ч хг ч хз)(х! ч хг)(Х1 ч хз):, !) Хг = (х1 Ч х2 Чхз)(х1 Ч хз)(х2 Ч х4); 8) К = (Х1 Ч хг Ч х4)(У! ЧхЗ)(йг Ч х4).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
