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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Задачи с экзаменов по дискретной математикеКафедра дискретной математики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.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов ответов (шпаргалок)