Задачи с экзаменов по дискретной математике

Задачи с экзаменов по дискретной математикеКафедра дискретной математики7 семестр, 2005 г.Это задачи, собранные с экзаменов по дискретной математике в 2005–2006 году. Естественно, на полнотуданный список не претендует. За сбор задач и набор решений спасибо Сергею Гладких, Стасу Куприянову, ИреШитовой, Мите Копьёву, Юре Притыкину, Мише Левину и Пете Митричеву.Последняя компиляция: 14 мая 2006 г.Обновления документа — на сайте http://dmvn.mexmat.net.Об опечатках и неточностях пишите на dmvn@mccme.ru.Далее очень часто будет использоваться обозначение B := {0, 1}.Задача 1. Пусть f (x) : Bn −→ B — булева функция, такая чтоXf (x) = n2 .x∈{0,1}nДоказать, что L(f ) = On3log2 n.Решение. Для начала представляем нашу функцию в виде_f (x) =xσ1 1 .

. . xσnn ,(1)где дизъюнкция берется только по тем n2 наборам, на которых функция равна единице. Такоепредставление дает нам сложность порядка n3 , а мы хотим меньше.1◦ . Заметим, что, фактически, мы хотим реализовать n2 функций вида xσ1 1 . . . xσnn . Разобьем это множество функций на два: xi1 . . . xik и xj1 ∨ . .

. ∨ xjl , то есть каждая конъюнкцияразбивается на конъюнкцию «положительных» степеней и конъюнкцию отрицаний. Их потомеще нужно будет склеивать, но асимптотики нам это не испортит. Далее мы ограничиваемсяреализация 1-го множества — со вторым все аналогично.2◦ . Рассмотрим наше множество функций как матрицу n2 × n. Если xi входит в j-ю конъюнкцию, ставимна ij-е место 1, иначе 0. Итак, задача сведена к реализации такой вот матрицыn3за O log n операций. 3й нетривиальный шаг.

Разбиваем матрицу на блоки по ⌈log2 n⌉ строк.2И замечаем, что это — проверочные матрицы двоичного кода Хемминга! А их мы умеем реализовывать за ∼ n операций (подробнее см. записки семинаров А. В. Чашкина). А таких блоков2у нас как раз logn n . Умножаем и получаем то, что требовалось. 2Задача 2. Найти минимальное число элементов единичной задержки, необходимых дляреализации автомата без входов, генерирующего периодическую последовательность с периодом (10000111), и оценить сложность порождающей этот автомат СФЭ.Задача 3.

Построить проверочную матрицу троичного кода Хемминга, содержащую тристроки.Задача 4. Дано поле из m := pn элементов (α1 , . . . αm ). Найти суммуXαi1 αi2 αi3 .i1 <i2 <i31(2)Решение. Здесь написан просто-напросто (с точностью до знака) элементарный симметрический многочлен третьего порядка. А мы знаем, что все элементы поля удовлетворяют уравнению xm − x = 0.

По теореме Виета, все элементарные симметрические многочлены, кромеодного (σm ), равны нулю, значит, в частности, наша сумма тоже равна нулю. Задача 5. Найти функцию Эйлера ϕ(n) через формулу включений-исключений.∗ Задача 6. Дано регулярное событие A = 0 (1111)∗00(00)∗ . Построить автомат, распознающий это событие.Задача 7. Найти вес ограниченно-детерминированной функции, которая равна 1 тогда итолько тогда, когда x ∈ A, а A = {1((00)∗(1111)∗ )∗ }.Задача 8.

Дан автомат без входов. Найти минимальное число элементов единичной задержки и функциональных элементов в базисе всех двуместных булевых функций для реализации (1110)∗.Задача 9. A := {f ∈ P2 (n) : f (x) = f (x)}, x = (x1 , . . . , xn ) ∈ Bn . Найти max L(f ).f ∈AЗадача 10. Пусть m(n, d) — максимальная мощность двоичного кода длины n с кодовымрасстоянием d. Доказать неравенство m(n, d) 6 2m(n − 1, d).Решение.

Решается по индукции. Рассмотрим самый мощный код длины n, разобьём слована две группы: с последним битом 0 и с последним битом 1. В каждой группе слов не больше,чем m(n − 1, d). Задача 11. Пусть f : B∗ → B∗ — детерминированная функция, гдеt1, P x = 2047;if (x1 , . . . , xt ) =i=10, иначе.(3)Найти вес функции f , построить для неё диаграмму Мура и написать канонические уравнения.Решение. Построим дерево для нашей функции и рассмотрим вершину на уровне t. Еслизначение функции на входящем в неё ребре равно 0, то дальше будет либо нулевое поддерево,либо по единичной ветви мы придём в вершину со значением 1.

Из начала это произойдёт за2047 шагов, из вершины 1-го уровня — за 2046, . . . , из вершины 2046-го уровня — за 1 шаг,из вершины 2047-го уровня — за 0 шагов. Таким образом, всего получаем 2048 состояний плюснулевое дерево — всего 2049. Это и есть вес функции f .Канонические уравненияy(t) = F (x(t), q(t))q(t + 1) = G(x(t), q(t))q(1) = 0находятся из таблицы:2x0101...010101qF00001010... ...2046 02046 12047 12047 02048 02048 0G0112...204620472047204820482048Задача 12.

Найти мощность 6-разрядного двоичного кода, если любой шар в B6 содержит1 или 2 элемента кода.Задача 13. Известно, что a1 = 2, a2 = 2, иan = −2an−2 + cosπn.2Найти an в явном виде.Задача 14. ПустьA=( nXi=1Найти асимптотику L(A).) nXai xi ai = 2 (mod 3) .i=1Задача 15.

Дан [n, k]-код. Найти максимальное n, при котором этот код исправляет однуошибку.Задача 16. Найти L {x ⊕ y, x ↓ y} .Задача 17. При каких r и q существует однозначное кодирование r-буквенного алфавитав q-буквенном, такое что для него в неравенстве Крафта – Макмиллана выполняется строгоеравенство?Задача 18. Сколько существует монотонных функций от n переменных, принимающихзначение 1 ровно на 7 наборах?nPЗадача 19. Пусть x = (x1 , x2 , . . . , xn ), где xi — булевы. Пусть |x| =2i−1 xi . Пусть A —1 √ множество булевых функций, таких что f (x) = f (y), если |x| ≡ |y| (mod 2 n ). Найти L(A)(оценить порядок).Ответ: Ответ:√2√ n.n√Решение.

Оценка снизу. Таких функций хотя бы 2 n−1 . С другой стороны, если применить лемму о количестве графов с p вершинами и q ребрами и оценить количество схем с неnболее, чем h элементами так же, как когда мы доказывали оценку снизу 2n , то получится какраз нужная оценка.√Оценка сверху. Если мы сможем находить остаток от |x| по модулю 2[ n] , то далее по теоре√ме Лупанова мы достроим схему из порядка 2[ n] , которая реализует нашу функцию. Отлично,осталось построить схему из полиномиального числа элементов, реализующую нахождение |x|3(mod a). Числа 2i (mod a) для i = 0, 1, . . . , n − 1 мы можем предвычислить в двоичном виде.Останется в таком случае решить следующую задачу: на входы схемы подаются числа нольили один. Тогда нужно сложить все из наших чисел 2i (mod a), для которых на i + 1 входеподали единицу.

То есть реально нужно построить схему, складывающую два двоичных числа.Ну, а так как ⊕ реализуется через конъюнкцию, дизъюнкцию и отрицание, то можно считатьего элементом. А из ⊕ уже можно с помощью стандартной техники сложения двоичных чисел на компьютере построить такую схему, складывая числа побитово, и имея дополнительныеэлементы для битов переполнения. Последняя компиляция: 14 мая 2006 г.Обновления документа — на сайте http://dmvn.mexmat.net.Об опечатках и неточностях пишите на dmvn@mccme.ru.4.