В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (2011), страница 3
Описание файла
PDF-файл из архива "В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (2011)", который расположен в категории "". Всё это находится в предмете "основы кибернетики" из 6 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 3 страницы из PDF
. . , α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. Найти размер максимальной клики графа G:1) G - граф на рис. 2;2) G - граф на рис. 5;3) G - граф на рис. 8;4) G - граф на рис. 9.2.6. Найти минимальное вершинное покрытие графа G:1) G - граф на рис. 1;2) G - граф на рис. 2;3) G - граф на рис. 3;4) G - граф на рис. 6.2.7. 1. Доказать полиномиальную решаемость задачи 2-ВЫП.2. Продемонстрировать работу полиномиального алгоритма для задачи 2-ВЫП на примере входа K, если:1) K = (x1 ∨ x2 )(x̄2 ∨ x3 )(x̄2 ∨ x1 )(x̄1 ∨ x̄3 )x4 (x4 ∨ x5 )(x1 ∨ x3 )(x3 ∨ x̄1 );2) K = (x̄1 ∨ x4 )x1 (x2 ∨ x̄3 )(x5 ∨ x̄2 )(x̄2 ∨ x3 )x4 (x̄2 ∨ x̄5 )(x2 ∨ x̄6 ).2.8. Продемонстрировать работу жадного алгоритма для задачи поиска минимального остовного дерева на примере входа G:G:2.9.
Доказать, что следующие задачи принадлежат классу NP.1) Задача L1:Вход: граф G = (V, E), число k.Вопрос: есть ли в графе G простой цикл длины k?Доказать, что L1 ∈ NP.2) Задача L2:Вход: граф G = (V, E), число k.Вопрос: есть ли в графе G вершина степени k?Доказать, что L2 ∈ NP.3) Задача L3:Вход: матрица M из 0 и 1 размера n × m, число k.Вопрос: есть ли покрытие матрицы M мощности k (множество строкматрицы M называется ее покрытием, если в образованной ими подматрице нет нулевых столбцов)?Доказать, что L3 ∈ NP.4) Задача L4:Вход: матрица M из 0 и 1 размера n × m без совпадающих столбцов,число k.Вопрос: есть ли тест для матрицы M длины k (множество строк матрицы M называется тестом, если в образованной ими подматрице всестолбцы различны; длиной теста называется число строк в нем)?Доказать, что L4 ∈ NP.2.10.
Построить преобразование входа задачи L1 во вход задачи L2 ,доказывающее полиномиальную сводимость языка L1 к языку L2 :1) L1 есть ВЫП, L2 есть 0-1 ЦЛП;2) L1 есть ВЫП, L2 есть 3-ВЫП;3) L1 есть КЛИКА, L2 есть ВЕРШИННОЕ ПОКРЫТИЕ;4) L1 есть ВЕРШИННОЕ ПОКРЫТИЕ, L2 есть ПОКРЫТИЕ МНОЖЕСТВ.2.11. Данный вход K задачи ВЫП преобразовать во вход K 0 задачи3-ВЫП:1) K = (x1 ∨ x2 ∨ x3 ∨ x4 )(x̄1 ∨ x2 ∨ x̄3 ∨ x̄4 )(x̄2 ∨ x̄3 ∨ x4 );2) K = (x3 ∨ x̄1 ∨x2 ∨ x̄5 ∨ x̄4 )x̄2 (x̄2 ∨x1 ∨x5 ∨ x̄3 )(x3 ∨x4 )(x1 ∨ x̄3 ∨x4 ∨x5 ).2.12.
По КНФ K построить 0-1 матрицу A и вектор b, являющиесявходом задачи 0-1 ЦЛП, соответствующим КНФ K:1) K = (x̄1 ∨ x̄2 )(x̄1 ∨ x̄3 );2) K = (x̄1 ∨ x̄2 ∨ x3 )(x1 ∨ x̄3 );3) K = (x̄1 ∨ x2 ∨ x̄3 )(x1 ∨ x̄2 ∨ x̄4 );4) K = (x1 ∨ x̄2 ∨ x3 )(x̄1 ∨ x2 ∨ x̄3 );5) K = (x̄1 ∨ x2 ∨ x̄3 ∨ x3 )(x1 ∨ x̄2 )(x̄2 ∨ x3 );6) K = (x1 ∨ x̄2 ∨ x3 )(x̄1 ∨ x̄2 )(x1 ∨ x̄3 );7) K = (x̄1 ∨ x2 ∨ x3 )(x̄1 ∨ x3 )(x̄2 ∨ x4 );8) K = (x1 ∨ x2 ∨ x̄4 )(x̄1 ∨ x3 )(x̄2 ∨ x̄4 ).2.13. По КНФ K, являющейся входом для языка ВЫП, построитьграф G и число k, являющиеся входом для задачи КЛИКА:1) K = (x1 ∨ x2 ∨ x3 )(x2 ∨ x3 )(x1 ∨ x3 );2) K = x1 (x2 ∨ x3 )(x1 ∨ x3 ∨ x4 )x2 ;3) K = (x1 ∨ x2 ∨ x3 )(x2 ∨ x3 )(x1 ∨ x3 );4) K = x3 (x1 ∨ x4 )(x1 ∨ x2 )(x4 ∨ x2 );5) K = (x1 ∨ x2 ∨ x4 )(x3 ∨ x4 )(x1 ∨ x2 ∨ x4 );6) K = (x1 ∨ x3 )(x2 ∨ x3 ∨ x4 )(x2 ∨ x4 )(x1 ∨ x4 );7) K = (x1 ∨ x2 ∨ x3 )(x2 ∨ x3 ∨ x4 )(x1 ∨ x4 )(x2 ∨ x3 );8) K = (x1 ∨ x2 ∨ x3 )(x2 ∨ x4 )(x1 ∨ x4 )x5 .2.14.
По КНФ K, являющейся входом для задачи ВЫП, построитьграф G и число l, являющиеся входом задачи ВЕРШИННОЕ ПОКРЫТИЕ:1) K = (x1 ∨ x2 ∨ x3 )(x1 ∨ x2 )(x1 ∨ x2 );2) K = (x1 ∨ x2 ∨ x3 )(x1 ∨ x2 ∨ x3 )(x1 ∨ x3 );3) K = (x1 ∨ x2 ∨ x3 )(x2 ∨ x3 ∨ x4 )(x1 ∨ x4 );4) K = (x1 ∨ x4 ∨ x2 )(x1 ∨ x3 )(x4 ∨ x2 ∨ x3 );5) K = (x2 ∨ x3 )(x1 ∨ x3 ∨ x4 )x4 (x1 ∨ x2 );6) K = (x1 ∨ x2 )(x3 ∨ x5 )(x1 ∨ x2 ∨ x4 );7) K = (x1 ∨ x2 ∨ x3 )(x1 ∨ x4 ∨ x5 )(x1 ∨ x3 ∨ x5 );8) K = (x2 ∨ x3 )(x1 ∨ x2 ∨ x4 )(x1 ∨ x2 ∨ x4 ).2.15. Граф G и число l являются входом задачи ВЕРШИННОЕ ПОКРЫТИЕ. Построить вход задачи ПОКРЫТИЕ МНОЖЕСТВ, соответствующий паре (G, l):1) l = 2, G:2) l = 3, G:3) l = 3, G:4) l = 3, G:2.16.
Данный вход задачи КЛИКА преобразовать во входы задачВЕРШИННОЕ ПОКРЫТИЕ и ПОКРЫТИЕ МНОЖЕСТВАМИ:1) k = 4, G:2) k = 4, G:2.17. Доказать NP-полноту задач 1 – 8 из введения к параграфу.2.18. Доказать, что следующие задачи являются NP-полными:1) существование набора, обращающего ДНФ в ноль;2) существование набора, обращающего ДНФ в ноль при условии, чтокаждое слагаемое этой ДНФ содержит не более 4 букв.2.19. Выделить среди перечисленных задач полиномиально решаемыеи NP-полные (при условии P 6= NP):1) существование двух противоположных наборов, на которых ДНФобращается в единицу;2) существование двух противоположных наборов, на которых ДНФобращается в ноль;3) существование набора, на котором полином Жегалкина обращаетсяв ноль;4) существование набора, на котором заданные полиномы Жегалкина(количество которых заранее неизвестно) одновременно обращаются вноль;5) существование эйлерова цикла в графе (эйлеровым циклом называется цикл, проходящий по всем ребрам графа, причем по каждому вточности один раз);6) существование гамильтонова цикла в графе (гамильтоновым циклом называется простой цикл, проходящий через все вершины графа);7) раскраска вершин графа в два цвета (граф можно раскрасить в двацвета, если каждой его вершине можно приписать цвет таким образом,что смежным вершинам приписаны разные цвета);8) раскраска вершин гиперграфа в два цвета (гиперграфом называется пара < V, E >, где V — конечное множество вершин, E, E ⊆ 2V —множество ребер; гиперграф можно раскрасить в два цвета, если каждой его вершине можно приписать цвет таким образом, что любое ребробудет содержать по меньшей мере две вершины, окрашенные в разныецвета).2.20.
Выяснить, какие из перечисленных задач являются полиномиально решаемыми, какие — NP-полными:1) распознавание нелинейности булевой функции, еслиа) функция задана таблицей своих значений,б) функция задана формулой,в) функция задана в виде ДНФ,г) функция задана в виде сокращенной ДНФ,д) функция задана в виде полинома Жегалкина;2) распознавание немонотонности булевой функции, еслиа) функция задана таблицей своих значений,б) функция задана формулой,в) функция задана в виде ДНФ,г) функция задана в виде сокращенной ДНФ,д) функция задана в виде полинома Жегалкина;3) распознавание несамодвойственности функции, еслиа) функция задана таблицей своих значений,б) функция задана формулой,в) функция задана в виде ДНФ,г) функция задана в виде совершенной ДНФ,д) функция задана в виде полинома Жегалкина;4) существовование в графе k-клики (k-кликой называется подграф,являющийся полным графом с k вершинами), еслиа) число k заранее известно,б) число k подается на вход МТ вместе с графом;2.21.
Доказать полиномиальную эквивалентность задач L1 и L2 , если1) L1 = ВЫП, L2 = 4-ВЫП;2) L1 = РАСКРАСКА ГРАФА В 2 ЦВЕТА; L2 = УМНОЖЕНИЕ ДВОИЧНЫХ ЧИСЕЛ.••••••••••••••••••••••••••Рис. 1.Рис. 2.••••••••••••••Рис. 4.••••••Рис. 3.•••••••Рис. 6.Рис. 5.••••• • • • •• • • • •Рис. 9.•Рис. 8.••••Рис. 7.•••Часть 2. Эквивалентные преобразования§ 3. Эквивалентные преобразовния формулДве формулы алгебры логики называются эквивалентными, если ониреализуют равные функции алгебры логики.Тождеством в алгебре логики называется равенство, в левой и правойчастях которого стоят эквивалентные функции.Справедливы, в частности, следующие тождества:(1) x1 ∨ x2 = x̄1 &x̄2(2) x1 &x2 = x̄1 ∨ x̄2¯=x(3) x̄(4) (x1 ∨ x2 )&x3 = (x1 &x3 ) ∨ (x2 &x3 )(5) x1 &x2 = x2 &x1(6) (x1 &x2 )&x3 = x1 &(x2 &x3 )(7) x&x = x(8) (x1 &x̄1 )&x2 = x1 &x̄1(9) (x1 &x̄1 ) ∨ x2 = x2(10) x1 ∨ x2 = x2 ∨ x1(11) (x1 ∨ x̄1 )&x2 = x2(12) (x1 ∨ x2 ) ∨ x3 = x1 ∨ (x2 ∨ x3 )(13) x ∨ x = x(14) x1 &x̄1 = x2 &x̄2 .Если в тождество A = B вместо одинаковых переменных всюду подставить произвольные одинаковые формулы, то снова получится тождество A0 = B 0 .
Применить тождество A = B к формуле C — это значитвыделить в формуле C подформулу, полностью совпадающую с A0 (илиB 0 ) и заменить в C эту подформулу на B 0 (соответственно, на A0 ).Вместо & мы обычно будем использовать · или вообще этот знак будемопускать.3.1. Используя только тождество (6), вывести тождества1)(x1 · x2 ) · (x3 · x4 ) = ((x1 · x2 ) · x3 ) · x4 ;2) x1 · ((x2 · x3 ) · x4 ) = ((x1 · x2 ) · x3 ) · x4 ;3) x1 · (x2 · (x3 · x4 )) = ((x1 · x2 ) · x3 ) · x4 ;4) (x1 · (x2 · x3 )) · (x4 · x5 ) = (((x1 · x2 ) · x3 ) · x4 ) · x5 ;5) x1 · ((x2 · x3 ) · (x4 · x5 )) = (((x1 · x2 ) · x3 ) · x4 ) · x5 .3.2. Пусть формулы F1 и F2 получены из выражения x1 · x2 · .
. . · xnлюбыми правильными расстановками скобок. Доказать, что, используятождество (6), можно вывести тождество F1 = F2 .Замечание. Результат задачи 3.2 для конъюнкции и аналогичныйрезультат для дизъюнкции (см. тождество (12)) позволяет записыватьдлинные конъюнкции и дизъюнкции без скобок.
В следующих задачахпорядок действий определяется либо скобками, либо соглашением о том,что конъюнкция выполняется раньше дизъюнкции, а отрицание применяется к той формуле, над которой оно стоит.3.3. С помощью тождеств (1)-(14) преобразовать в совершенную дизъюнктивную нормальную форму от переменных x, y, z или в формулу x&x̄следующие формулы:1) xȳ;2) x ∨ y · (xz̄ ∨ y);3) x̄;4) xy ∨ ȳz ∨ x̄ ∨ z̄;5) xy ∨ yz;6) xyz ∨ x ∨ y ∨ z;7) x̄y ∨ ȳz ∨ z̄x;8) xȳ ∨ yz̄x;9) (x ∨ ȳ)(y ∨ z̄)(z ∨ x);10) x ∨ y ∨ y ∨ z ∨ z ∨ x;11) x̄ · yz ∨ x · y ∨ z.3.4. Доказать, что с помощью тождеств (1)-(14) любую формулу алгебры логики в базисе {∨, &, −}, содержащую любое подмножество изпеременных x1 , x2 , . . . , xn , можно преобразовать в совершенную дизъюнктивную нормальную форму от всех переменных x1 , x2 , .