Контрольная работа № 1 По дисциплине: Дискретная математика

Федеральное агентство связи

Сибирский Государственный Университет Телекоммуникаций и Информатики

Межрегиональный центр переподготовки специалистов

Контрольная работа № 1

По дисциплине: Дискретная математика

Выполнил:

Группа: _______________

Вариант:___2___________

Проверил: ___________________

Новосибирск, 2012 г

№1 Доказать равенства, используя свойства операций над множествами и определения операций. Проиллюстрировать при помощи диаграмм Эйлера-Венна. А) (AÇ B) \ (AÇ C) = (AÇ B) \C б) (A È B)x C=(Ax C) È (Bx C) .

Доказательство.

А) Проведем двустороннее доказательство. Сначала докажем, что из того, что элемент принадлежит левой части, вытекает его принадлежность к правой части.

Рассмотрим произвольный элемент ає(AÇ B) \ (AÇ C). По определнию разноси, это означает, что он принадлежит (AÇ B) и не принадлежит (AÇ C), первое означает, что он находится и в А и в В, а второе, что находится в A и в С, следовательно, он находится в той части пересечения А и B, которая не пересекается с С, что и т. д.

Теперь докажем, что из того, что элемент принадлежит правой части, вытекает его принадлежность к левой части.

Рассмотрим произвольный элемент ає(AÇ B) \C, это значит, что он принадлежит AÇ B, но не принадлежит С. Если он не принадлежит С, то естественно не принадлежит той части С, которая пересекается с А, то есть не принадлежит AÇ C, что и т. д.

У Вас все операции над множествами выглядят квадратиками (или треугольничками). В таком виде я не могу проверить работу. Исправьте.

Диаграммы:

AÇB AÇB

AÇC AÇB\C

(AÇB)\(AÇC)

B) (AÈ B)x C=(AÈ C)x (BÈ C).

Рассмотрим произвольный элемент ає(AÈ B)x C – это пара таких элементов, что первый принадлежит (AÈ B), а второй принадлежит С. Это означает, что первый элемент принадлежит либо А либо В, тогда эта пара принадлежит или множеству AxC или множеству BxC, а следовательно и (AxC) È (Bx C).

Все операции при доказательстве носят двусторонний характер, поэтому доказывать в обратную сторону не требуется.

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

AUB AxC BxC

(AUB)xC

(AxC) È (Bx C)

№2 Даны два конечных множества: А={a, b,c}, B={1,2,3,4}; бинарные отношения P1  Í Aх B, P2  Í B2. Изобразить P1, P2 графически. Найти P = (P2◦P1)–1. Выписать области определения и области значений всех трех отношений: P1, P2, Р. Построить матрицу [P2], проверить с ее помощью, является ли отношение P2 рефлексивным, симметричным, антисимметричным, транзитивным. P1 = {(a,1),(a,2),(a,3),(a,4),(b,3),(c,2)}; P2 = {(1,1),(1,4),(2,2),(2,3),(3,3),(3,2),(4,1),(4,4)}.

Решение.

Обозначим элементы множества А точками оси ОХ, а элементы множества В – точками оси OY. Тогда элементы P1 – точки плоскости:

Обозначим элементы множества B точками оси ОХ и оси OY. Тогда элементы P2 – точки плоскости:

Композиция отношений  и :

.

В нашем случае R=P2ÍB2=BxB; S=P1Í Aх B.

P2◦P1={(a,1);(a,4);(a,2);(a,3);(b,3);(b,2);(c,2);(c,3)}

Обратное отношение: ;

P = (P2◦P1)–1={(1,a);(2,a);(2,b);(2,c);(3,a);(3,b);(3,c);(4,a)}

Область определения :  ;

Область значений: ;

Dom(P1)=A.

Dom(P2)=B.

Dom(P)=B.

Im(P1)=B

Im(P2)=B

Im(P)=A.

Матрица отношения P2=

1	0	0	1
0	1	1	0
0	1	1	0
1	0	0	1

Отношение P2 рефлексивно, так как на главной диагонали все единицы. Симметрично, так как если на пересечении i-той строки и j-того столбца стоит 1, то и на пересечении j-той строки и i-того столбца тоже 1. Транзитивно. Неантисимметрично, так как есть обратныке пары с различными элементами.

Транзитивность следует проверить.

Транзитивность подразумевает, что при наличии во множестве пары (a, b) и (b, c), пара (a, c) тоже ему принадлежит. Это выполняется простым перебором пар.

Это не выполняется перебором пар. Есть алгоритм проверки по матрице, матрица умножается сама на себя и проверяется, что результат есть подмножество исходной матрицы.

№3 Задано бинарное отношение P; найти его область определения и область значений. Проверить по определению, является ли отношение P рефлексивным, симметричным, антисимметричным, транзитивным. P  Í R2,, P = {(x, y) | x·y > 1}.

Dom(P)={x≠0}.

Im(P)={y≠0}.

Не рефлексивно, т. к. например существует точка (0,5;0,5) не принадлежащая P.

Симметрично, в силу коммутативности умножения.

Не антисимметрично, так как симметрично. Может быть то и другое вместе. Так что не основание.

Не антисимметрично, так как есть обратные пары с различными элементами, например (2,1) и (1,2).

Нетранзитивно, так как существуют пары (0,5; 8) и (8; 0,2) принадлежащие Р, но пара (0,5; 0,2) не принадлежит Р.

Остальное верно. Только исправьте квадратики!!!

верно

№4 Доказать утверждение методом математической индукции:
(n3 + 11·n) кратно 6 для всех целых n   0.

Доказательство.

1) Проверим для n=0 и n=1. База – ОДНО значение n.

1) Проверим для n=0.

Если n=0, то n3 + 11·n=0+11*0=0, что кратно 6.

Если n=1, то n3 + 11·n=1+11*1=12. 12/6=2, то есть тоже выполняется. !!!

2) Пусть выполняется при n=k, то есть k3 + 11·k делится на 6 без остатка.

3) Докажем, что при n=k+1, утверждение тоже выполняется. Подставим n=k+1 в исходное выражение.

(k+1)3+11*(k+1)=k3+3k2+3k+1+11k+11= (k3+11k)+(3k2+3k+12) =(k3+11k)+3(k2+k+4)

(k3+11k) кратно k по индуктивному предположению.

3(k2+k+4) делится на 3, следовательно, чтобы оно делилось на 6 достаточно, чтобы k2+k+4 делилось на 2.

Если k – четное, то его квадрат – четный, а сумма трех четных четная, следовательно, k2+k+4 делится на 2.

Если k – нечетное, то его квадрат нечетный, а сумма двух нечетных и одного четного – четная, следовательно, k2+k+4 делится на 2, при любых k, следовательно, 3(k2+k+4) делится 6.

То есть в сумме (k3+11k)+3(k2+k+4) оба слагаемых кратны 6, следовательно и сама сумма кратна 6, что и т. д..

Остальное верно.

№5 Бригада из одиннадцати взломщиков одновременно выходит на грабеж трех разных магазинов. Сколькими способами они могут разделиться, если в каждой группе должно быть не менее двух человек? Сколькими способами их после задержания могут рассадить по четырем одинаковым камерам (не менее чем по одному в каждую)?

Решение.

А)Взломщиков индивидуальными не считаем, так как про них (в отличии от магазинов) это не сказано. 11 человек на 3 группы не менее чем по 2 человека в каждой можно разделить соедующимии способами:

2,2,7

2,3,6

2,4,5

3,4,4

При этом первая и четвертые группы предполагают только по 3 варианта разделния по 3 разным магазинам, а 2 и 4 – по 6. Итого получаем 3+6+6+3=18 способов.

Решать следует в соответствии с формулой РАЗБИЕНИЙ множества. Все элементы множества, как известно, различны.

Решение.

А) Их количество находим как число Стирлинга 2 рода. Их находим из треугольника Стирлинга по рекуррентной формуле:

В этом вопросе следует использовать формулу для УПОРЯДОЧЕННЫХ разбиений. Числа Стирлинга пригодны для неупорядоченных

= + k * , n > 0

n
0	1
1	0	1
2	0	1	1
3	0	1	3	1
4	0	1	7	6	1
5	0	1	15	25	10	1
6	0	1	31	90	65	15	1
7	0	1	63	301	350	140	21	1
8	0	1	127	966	1701	1050	266	28	1
9	0	1	255	3025	7770	6951	2646	462	36	1
10	0	1	511	9330	34105
11	0	1	1023	28501	145750

Б) Преступников по камерам можно распределить всего 8 способами

{1,1,1,8}; {1,1,2,7}; {1,1,3,6};{1,1,4,5};{1,2,2,6};{1,2,3,5};{1,2,4,4};{1,3,3,4}. Так как камеры одинаковы, то перестановки по количеству учитывать не нужно.

Аналогично, только здесь разбиения НЕУПОРЯДОЧЕННЫЕ. Ответы неверные.

Ответ: 18; 8.

Так как камеры одинаковы, то перестановки по количеству учитывать не нужно, то есть разбиения упорядоченные.

Их количество находим Сn-1k-1=10!/(7!3!)=120.

Ответ: 28501; 120.

Ответы неверные. Во втором случае возьмите формулу упорядоченных разбиений и исключите порядок. Или по числам Стирлинга…

№6 Сколько существует положительных трехзначных чисел: а) делящихся на числа 6, 8 или 21? б) делящихся ровно на одно из этих трех чисел?

Трехзначные числа от 100 до 999.

Если число делится на 6, то имеет вид 6k. Посчитаем их количество.

100<6k<999

16<k<167. То есть всего их 150.

Если число делится на 8, то имеет вид 8k. Посчитаем их количество.

100<8k<999

12<k<125. То есть всего их 112.

Если число делится на 21, то имеет вид 21k. Посчитаем их количество.

100<21k<999

4<k<48. То есть всего их 43.

Если число делится на 6 и на 8, то делится на их наименьшее общее кратное = 24 и имеет вид 24k. Посчитаем их количество.

100<24k<999

4<k<42. То есть всего их 37.

Если число делится на 6 и на 21, то делится на их наименьшее общее кратное = 42 и имеет вид 42k. Посчитаем их количество.

100<42k<999

2<k<24. То есть всего их 21.

Если число делится на 8 и на 21, то делится на их наименьшее общее кратное = 168 и имеет вид 168k. Посчитаем их количество.

100<168k<999

0<k<6. То есть всего их 5.

Если число делится на 6 и на 8, и на 21, то делится на их наименьшее общее кратное = 168 и имеет вид 168k. Посчитаем их количество.

100<168k<999

0<k<6. То есть всего их 5.

По кругам Эйлера общее число чисел составит n=150+112++5=247.

- делящихся только на 6: +5=97

- делящихся только на 8: +5=75

- делящихся только на 21:43-21-5+5=22.

Всего таких чисел 97+75+22=194.

Ответ: 247; 194.

верно.

№7 Найти коэффициенты при a=x3·y2·z2, b=x2·y2·z2, c=x4·z4 в разложении (2·x+3·y+5·z2)6.

Решение

Воспользуемся обобщением Бином Ньютона до полинома Ньютона - возведения в степень суммы произвольного числа слагаемых:

где

это мультиномиальные коэффициенты. Сумма берется по всем неотрицательным целым индексам , сумма которых равна n.

1) b=x2·y2·z2 В нашем случае последнее слагаемое имеет вторую степень, что означает, что при возведении сумма степеней в слагаемых содержащих его должна быть не меньше 7, следовательно слагаемого b не существует – коэффициент перед ним = 0.

2) a=x3·y2·z2 . Здесь k1=3; k2=2; k3=1, тогда коэффициент равен:

6!/(3!*2!*1!)*(2x)3*(3y)2*(5z2)1=720/(6*2)*8*9*5* x3·y2·z2=21600 x3·y2·z2

3) c=x4·z4 . Здесь k1=4; k2=0; k3=2, тогда коэффициент равен:

6!/(4!*0!*2!)*(2x)4*(3y)0*(5z2)2=720/(24*2)*16*1*25* x4·z4 =6000 x4·z4

верно

№8 Найти последовательность {an}, удовлетворяющую рекуррентному соотношению an+2 – 3·an+1 + 2·an = 0· и начальным условиям a1=3, a2=7.

Решение.

Подставим известные в соотношение, чтобы найти a3=3·an+1 - 2·an=3*7-2*3=15

Аналогично a4=3·a3 - 2·a2=3*15-2*7=31.

Исходя из полученных данных, делаем предположение, что последовательность имеет вид an=2n+1-1, для всех целых n>0. Тогда an+1=2n+2-1, an+2=2n+3-1.

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

Подставим их в соотношение для проверки.

an+2 – 3·an+1 + 2·an= 2n+3-1– 3·2n+2+3 + 2*2n+1-2=8*2n-12*2n+4*2n=0*2n=0, что и т. д.

Ответ: an=2n+1-1, для всех целых n>0.

Решение.

Составим уравнение по рекуррентному соотношению:

λ2-3λ+2=0

λ1=1; λ2=2

Тогда общий вид последовательности

С1λn1+ С2λn2= С1*1n+ С2*2n

Подставим начальные условия:

С1+2С2=3

С1+4С2=7

Вычтя уравнения получаем С2=2; С1=-1

Ответ: an=2n+1-1, для всех целых n>0.

верно

№9 Орграф задан матрицей смежности. Необходимо:
а) нарисовать граф;
б) выделить компоненты сильной связности;
в) заменить все дуги ребрами и в полученном неориентированном графе найти эйлерову цепь (или цикл).

0 1 0 0 0 0

1 1 0 0 0 1

0 0 0 1 0 1

0 0 1 0 1 0

0 0 1 1 0 1

0 0 0 0 0 1

Решение

А)

Б) По определению компонентами сильной связности можно считать {1,2}; {3,4,5}; {6}.

В) Нечетных степеней вершин в графе 2, следовательно существует Эйлерова цепь, начинающаяся в вершине 2 и заканчивающаяся в вершине 6. Она изображена на рисунке красным.

верно

№10 Взвешенный граф задан матрицей длин дуг. Нарисовать граф.

Найти: а) остовное дерево минимального веса;

б) кратчайшее расстояние от вершины v2 до остальных вершин графа, используя алгоритм Дейкстры.

Решение

Алгоритм Крускала (или алгоритм Краскала) — алгоритм построения минимального остовного дерева взвешенного связногонеориентированного графа. Алгоритм впервые описан Джозефом Крускалом в 1956 году.

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

1) Начинаем с ребра 1-3. Вес остовного 2.

2) Добавляем ребро 1-4. Вес остновго 2+2=4.

3) Добавляем ребро 5-6. Вес остовного 4+2=6

4) Добавляем ребро 2-4. Вес остовного 6+3=9

5) Добавляем ребро 1-6. Вес остовного 9+3=12.

Остовное – жирное на рисунке.

2) Алгоритм Дейкстры

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем смежными этой вершины. Вообще-то такие вершины называются смежными с вершиной u, или ее окружением. Зачем придумывать какие-то другие термины, если они уже существуют? Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.

Все расчеты будем проводить на таблице меток.

Верш.	Метка
1	Беск.
2	0
3	Беск.
4	Беск.
5	Беск.
6	Беск.

Расстояние от 2 – до 4 – 3, до 5 – 4, до 1 – 5 . Эти числа – новые метки вершин. Вершина 2 – посещенная. (закрашиваем посещенные).

Верш.	Метка
1	5
2	0
3	Беск.
4	3
5	4
6	Беск.

Далее берем вершину 4, как ближайшую к 2.

Расставлем от нее метки:

- к вершине 1 – 3+2=5, но и стоит 5 – ничего не меняем.

- к вершине 5 – 3+5=8, больше 4 – ничего не меняем.

- к вершине 3 – 3+6=9 – меньше бесконенчости, меняем метку 3 – на 9.

Вершина 4 – посещенная.

Верш.	Метка	Путь
1	5	2-1
2	0	2
3	9	-
4	3	2-4
5	4	2-5
6	Беск.	-

Далее берем вершину 5, как ближайшую к 2.

Расставлем от нее метки:

- к вершине 6 – 4+2=6 - меньше бесконенчости, меняем метку 6 – на 6.

Вершина 5 – посещенная.

Верш.	Метка	Путь
1	5	2-1
2	0	2
3	9	2-4-3
4	3	2-4
5	4	2-5
6	6	-

Далее берем вершину 1, как ближайшую к 2.

Расставлем от нее метки:

- к вершине 3 – 5+2=7 - меньше 9, меняем метку 3 – на 7.

- к вершине 6 – 5+3=8 - больше 6, не меняем метку 6.

Вершина 1 – посещенная.

Верш.	Метка	Путь
1	5	2-1
2	0	2
3	7	2-4-3
4	3	2-4
5	4	2-5
6	6	2-5-6

Далее берем вершину 6, как ближайшую к 2.

Расставлем от нее метки:

- к вершине 3 – 6+4=10 - больше 7, ничего не меняем.

Вершина 6 – посещенная.

У вершины 3 – нет не помеченных соседей.

Алгоритм законечн.

Ответ: 5;7;3;4;6.

Алгоритм должен находить не только расстояния, но и пути. У Вас информация о путях потерялась. Добавьте ее.

верно