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



Скачать 148.96 Kb.
Дата04.07.2013
Размер148.96 Kb.
ТипКонтрольная работа
Федеральное агентство связи

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

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

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

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


Выполнил: Никитин А.В

Группа: _______________

Вариант:___???___________

Проверил: ___________________

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

1 Доказать равенства, используя свойства операций над множествами и определения операций. Проиллюстрировать при помощи диаграмм Эйлера-Венна. а)  (A B) \ (A C) = (A B) \C б)  (A B) C=(A C) (B 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) C=(A C) (B C) .

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

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

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


AUB AxC BxC

(AUB)xC

(A C) (B C)

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

Решение.

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



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



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

.

В нашем случае R=P2B2=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. Транзитивно. Неантисимметрично, так как есть обратныке пары с различными элементами.

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

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

Dom(P)={x≠0}.

Im(P)={y≠0}.

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

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

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

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

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

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

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

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

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

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

2) Пусть выполняется при n=k, то есть k+ 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 способов.

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

Б) Преступников по камерам можно распределить всего 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.

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

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

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

100<6k<999

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

100<8k<999

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

100<21k<999

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

100<24k<999

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

100<42k<999

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

100<168k<999

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

100<168k<999

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

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

- делящихся только на 8: 112-37-5+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.

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

0

3

9

4

3

5

4

6

Беск.

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

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

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

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

Верш.

Метка

1

5

2

0

3

9

4

3

5

4

6

6

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

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

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

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

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

Верш.

Метка

1

5

2

0

3

7

4

3

5

4

6

6

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

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

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

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

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

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

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

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

Похожие:

Контрольная работа №1 По дисциплине: Дискретная математика iconМетодические указания по подготовке к контрольным работам по дисциплине «Дискретная математика»
Теория графов. Методические указания по подготовке к контрольным работам по дисциплине «Дискретная математика». /Уфимск гос авиац...
Контрольная работа №1 По дисциплине: Дискретная математика iconКонтрольная работа по дисциплине «математика»

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

Контрольная работа №1 По дисциплине: Дискретная математика iconДискретная математика Контрольная работа
Доказать равенства, используя свойства операций над множествами и определения операций. Проиллюстрировать при помощи диаграмм Эйлера-Венна...
Контрольная работа №1 По дисциплине: Дискретная математика iconРабочая учебная программа по дисциплине «Дискретная математика» для ооп «010400 Прикладная математика и информатика»

Контрольная работа №1 По дисциплине: Дискретная математика iconКнига позволит быстро получить основные знания по предмету, повторить пройденный материал, а также качественно подготовиться и успешно сдать зачет и экзамен. Рекомендуется всем изучающим и сдающим дисциплину «Дискретная математика»
В шпаргалке в краткой и удобной форме приведены ответы на все основные вопросы, предусмотренные государственным образовательным стандартом...
Контрольная работа №1 По дисциплине: Дискретная математика iconДискретная математика
Ф50 Дискретная математика: сборник задач / Сост. И. В. Тимофеев. Красноярск: ипц кгту, 2003. 35 с
Контрольная работа №1 По дисциплине: Дискретная математика iconРабочая программа по дисциплине «Дискретная математика»

Контрольная работа №1 По дисциплине: Дискретная математика iconКонтрольная работа по Дисциплине «Экономическая математика, методы и модели»
Метод ветвей и границ. Рассмотрим задачу, состоящую в определении максимального значения функции
Контрольная работа №1 По дисциплине: Дискретная математика iconУчебная программа для специальности: (рабочий вариант) 1-310301-02 Математика
Рабочая программа составлена на основе учебной программы по дисциплине “Дискретная математика”, утверждённой 05. 09. 2008
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org