Контрольная работа по дискретной математике. Вариант №20

Контрольная работа должна выполняться после изучения всего теоретического материала. Решения задач следует сопровождать пояснениями. Контрольная работа может выполняться в электронном виде или быть решена в обычной ученической тетради и прислана по почте.

Первые четыре задачи относятся к первой главе – теории множеств.

В первой задаче необходимо аналитически доказать равенство в пункте (а), используя свойства операций над множествами (по материалам п. 1.2.5), а также проиллюстрировать его диаграммами Эйлера-Венна (по материалам п. 1.2.2).

Например: Пусть нужно доказать равенство A\(A\B)=AÇ B. Преобразуем левую часть: (по свойству разности No 10) = (по двойственности No 9) = (по дистрибутивности No 4) = Æ È (A Ç B) (по свойству дополнения No 7) = A Ç B (по свойству нуля No 5) Þ получена правая часть, т.е. равенство доказано.

В пункте (б) следует использовать определение операции декартова произведения, например: (AÈ B) ́ C = {(a,c) | a Î AÈ B, c Î C} = {(a,c) | (a Î A или a Î B), c Î C} = {(a,c) | (a Î A, c Î C) или (a Î B, c Î C} = ... (далее аналогично).

Во второй задаче необходимо построить в декартовой системе координат каждое из заданных отношений (по материалам п. 1.3.2, рекомендуется первый способ графического представления – см. пример 1.13), построить обратное к композиции отношение. Найти области определения и множества значений всех трех отношений. Проверить по матрице свойства заданного отношения (по материалам п. 1.3.4), при этом сначала необходимо давать определение, а затем применять его к конкретной задаче.

Например: Пусть на некотором этапе решения задачи получена матрица отношения . Отношение рефлексивно, если на главной диагонали матрицы нет нулей, следовательно, данное отношение рефлексивно. Отношение симметрично, если исходная и транспонированная матрицы совпадают. В нашем случае это не так (выписать транспонированную матрицу), значит, отношение не является симметричным. И так далее – для всех свойств.

В третьей задаче необходимо проверить свойства заданного отношения согласно определениям (по материалам п. 1.3.3) – т.е. либо показать, что определение справедливо для всех элементов из области определения отношения, либо (если это не так) привести контрпример, т.е. показать, что для некоторой пары элементов – и указать эту пару – определение не выполняется.

Например, рассмотрим отношение P = {(x,y) | x,y Î Z и x+y > 7}. Отношение определено на всем множестве Z, т.к. для любого целого x можно найти такое yÎ Z, что x+y > 7. В силу коммутативности операции сложения, данное отношение является симметричным (т.е. (x,y)Î P Þ (y,x)Î P). Очевидно, что рефлексивным (т.е. (x,x)Î P) оно не является – например, (1,1) Ï P. Что касается транзитивности, согласно определению должно выполняться (x,y)Î P и (y,z)Î P Þ (x,z)Î P. 1+7>7, 7+2>7, но не 1+2>7, Þ отношение не транзитивно.

В четвертой задаче дано утверждение, которое следует доказать, используя принцип математической индукции (по материалам п. 1.4.3). Для этого сначала утверждение проверяется для начального значения параметра n (это может быть или 0, или 1, или 2 – в зависимости от задания) – это так называемая база индукции. Затем предполагается, что утверждение справедливо для n. Если в этом предположении удастся показать, что оно справедливо и для n+1, то доказательство считается законченным.

Например: Доказать, что " n Î Z, n > 0 выражение n3 – n кратно трем. База индукции n = 1 (т.к. по заданию n > 0): 13–1 = 0, т.е. кратно трем. Предположим, что n3–n = 3k и покажем, что в таком случае (n+1)3 – (n+1) = 3m. (n+1)3 – (n+1) = n3+3n2+3n+1–n–1 = (n3–n)+3(n2+n); т.к. первое слагаемое делится на 3 по индукционному предположению, а у второго коэффициент 3, значит, и все выражение кратно 3.

Задачи NoNo 5–8 относятся к главе No 2 – элементам комбинаторики.

В пятой задаче задание сводится к определению числа разбиений множества на заданное количество подмножеств (по материалам п. 2.4.2). В первом вопросе задачи группы, на которые следует разбить исходное множество, принципиально различны, следовательно, речь идет об упорядоченных разбиениях (т.е. о тех, когда порядок блоков имеет значение). Значит, следует использовать формулу (2.5). Во втором вопросе блоки абсолютно одинаковы, значит, их порядок значения не имеет и речь идет о разбиениях неупорядоченных. Можно для вычисления использовать числа Стирлинга 2 рода (если нет какого-либо ограничивающего условия на минимальное число элементов в блоке) или упорядоченные разбиения, устранив из их формулы порядок.

Например: Пусть дано множество {a,b,c,d}. Определить количество упорядоченных и неупорядоченных разбиений его на 2 подмножества.

Разбиения на 2 подмножества возможны на 1+3 элемента и 2+2. Для неупорядоченных: R(4;1,3)+R(4;2,2)/2 – т.к. формула предназначена для подсчета числа упорядоченных разбиений, а поскольку во втором случае элементов в блоках одинаковое количество (2 и 2), то будет автоматически учтен порядок, что нужно исключить. Значит, каждое из выражений, где есть блоки одинакового размера, нужно разделить на число перестановок этих блоков (с одинаковым количеством элементов) – в нашем случае это 2!. Следовательно, в итоге количество неупорядоченных разбиений 4!/(1!·3!)+4!/(2!·2!)/2! = 4+3 = 7. Если считать через числа Стирлинга 2 рода: S(4,2) = S(3,1) + 2·S(3,2) = 1 + 2·(S(2,1) + 2·S(2,2)) = 1 + 2·(1 + 2·1) = 7. Если выписать эти разбиения явно, получим: {{a},{b,c,d}}, {{b},{a,c,d}}, {{c},{a,b,d}}, {{d},{a,b,c}}, {{a,b},{c,d}}, {{a,c},{b,d}}, {{a,d},{b,c}}. Если бы, например, в задаче требовалось найти разбиения множества из 7 элементов с помощью формулы для R(7;2,2,1,1,1), то для исключения порядка ее бы следовало разделить на (2! 3!).

Для упорядоченных разбиений при выписывании добавятся варианты с обратным расположением блоков, т.е. еще 7, следовательно, всего 14. При подсчете вариантов: R(4,2) = R(4;1,3) + R(4;2,2) + R(4;3,1) = 2·R(4;1,3) + R(4;2,2) = 2·4!/(3!·1!) + 4!/(2!·2!) = 8+6 = 14. Т.е. при наличии в формуле блоков разных размеров следует для сокращения расчетов умножать ее на число перестановок этих блоков (определяемое согласно комбинаторной формуле).

Для определения того же R(7;2,2,1,1,1) в результате перестановок блоков с 1 и 2 элементами: 2+2+1+1+1 = 2+1+1+1+2 = 2+1+2+1+1+1=... – появится коэффициент 5!/(2!·3!) = C(5,2) = 10 (согласно п. 2.4.1, формула 2.3), т.е. количество различных перестановок таких блоков равно 10. Значит, в результирующем выражении при подсчете числа упорядоченных разбиений в состав общей суммы войдет 10·R(7;2,2,1,1,1).

Шестая задача решается на основании принципа включения и исключения (по материалам п. 2.5) с применением формулы 2.8 (см. пример 2.24 в лекциях).

В седьмой задаче следует использовать полиномиальную теорему (по материалам п. 2.4.2, формула 2.6). При определении ni в формуле 2.6 нужно обратить внимание на степени переменных в исходном выражении, а при вычислении числового коэффициента – на коэффициенты при переменных в исходном выражении.

Например: Пусть надо определить, чему равен коэффициент при x2·y2·z4 в выражении (2x2+3y+2z2)5. Для x2·y2·z4: (2x2)1·(3y)2·(2z2)2 . Значит, степени соответственно равны 1, 2 и 2, а числовой коэффициент имеет вид R(5;1,2,2)·21·32·22 = 5!/(1!·2!·2!)·21·32·22 = 2 160.

В восьмой задаче нужно найти частное решение рекуррентного уравнения с заданными начальными условиями (по материалам 2-й главы лекций, п. 2.6). Для этого требуется построить характеристический многочлен (формула 2.10) и найти его корни. Затем на основании теоремы 2.11 выписывается общее решение an рекуррентного соотношения, в котором присутствуют неизвестные константы c1, c2 (см. пример 2.29). После этого на основании заданных начальных условий составляется система уравнений и из нее определяются эти константы.

Задачи NoNo 9, 10 относятся к главе No 3 – элементам теории графов.

В девятой задаче нужно построить ориентированный граф по заданной матрице смежности и определить его компоненты сильной связности, т.е. такие группы вершин, что каждая из них составляет максимальный сильно связный подграф (по материалам главы 3, п. 3.2.3, 3.4.2, 3.5.1). Затем следует заменить все дуги ребрами и в полученном неориентированном графе найти эйлеров цикл или цепь (по материалам главы 3 п. 3.5.4). При этом в случае соединения двух вершин a и b дугами (a,b) и (b,a) в неориентированном графе появятся кратные ребра. Для выяснения возможности построения эйлерова цикла или цепи (согласно определению, это соответственно цикл или цепь, проходящий по всем ребрам графа ровно по одному разу) необходимо определить степени всех вершин (см. лекции, п. 3.2.1). Условие наличия эйлерова цикла – четность степеней всех вершин. Для существования эйлеровой цепи в графе должно быть ровно две вершины с нечетными степенями.

В десятой задаче для построения остовного подграфа минимального веса следует использовать алгоритм Краскала (согласно п. 3.5.3 лекций) – нужно построить само дерево и вычислить его вес. Что касается второй части задачи, для ее решения необходимо применять алгоритм Дейкстры (согласно п. 3.5.3 лекций). При этом нужно обратить внимение на то, что пометки вершин (см. пример 3.32 из п. 3.5.3) изменяются только в случае, когда найдено более короткое расстояние. При этом поиск минимального расстояния выполняется по всем временным вершинам, а не только по тем, которые входили в множество смежности на последнем шаге.

Вариант 20

ОТЛИЧНО!!!