Контрольные по математике | Контрольная по дискретной математике | Matematiku5
Вузы по математике Готовые работы по математике Как писать работы по математике Примеры решения задач по математике Решить задачу по математике online

Контрольная по дискретной математике


К О Н Т Р О Л Ь Н А Я Р А Б О Т А

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

1. Дано универсальное множество U и X, Y,Z, U.

U={a, b,c, d}, X={a, c}, Y={a, b,d}, Z={b, c}

Найти: а)

b)

c)

Решение:

a) Согласно закона дистрибутивности

Ответ:

b) Согласно закона Даламбера

Ответ:

с)

Ответ:

2. Пусть A, B,C. Проиллюстрировать с помощью диаграмм Венна:

Решение:

а) Проиллюстрируем с помощью диаграмм Венна равенство :

 

б) Проиллюстрируем с помощью диаграмм Венна равенство :

 

3. Доказать справедливость (не используя диаграммы Венна):

Решение:

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

Докажем, что и . Пусть , тогда . Это значит, что либо , либо , т. е. либо , либо . Следовательно, . Это справедливо для всех элементов из , поэтому .

Обратно:

Пусть , тогда либо , либо . Это означает, что либо , либо , т. е. как А, так и В. Поэтому . Следовательно, . Это справедливо для всех элементов из множества . Поэтому .

4. Сколько наборов из 7 пирожных можно составить, если в продаже имеются 4 сорта.

Решение:

Для решения этой задачи воспользуемся формулой для расчета комбинаций с повторениями:

Ответ: 120 наборов.

5) В партии из 18 изделий 5 бракованных. Наудачу выбирают 4 изделия. Сколько существует таких вариантов выбора изделий, что среди них окажутся бракованными 3?

Решение:

Всего исходов (выбор 4-х деталей из 18) равно:

Благоприятный исход (выбор 3-х бракованных деталей из 5-ти):

Число вариантов, что в каждой выборке окажутся 3 бракованные детали, равно:

Ответ: 306 вариантов.

6. Сколько различных вариантов хоккейных команд можно составить из 9 нападающих, 5 защитников и 3 вратарей, если в состав команды должно войти 3 нападающих, 2 защитника и 1 вратарь?

Решение:

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

Ответ: 2520 вариантов.

7. Найти общее решение рекуррентного соотношения при заданных начальных членах

Решение:

Характеристический многочлен будет иметь вид:

Найдем его корни:

Тогда по теореме общее решение имеет вид:

Используем начальные условия для нахождения :

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

Ответ:

2

1

4

5

2

2

3

2

1

4

1

3

5

6

4

4

2

5

2

1

5

1

6

2

6

2

4

4

1

6

8. Граф задан матрицей весов. Используя алгоритм Прима, построить минимальный покрывающий остов.

Решение:

Используя данную матрицу, построим граф:

1) За первую вершину примем вершину , т. к. она имеет минимальный индекс.

2) Определим минимальное значение веса ребра, выходящего из вершины .Это ребро (v1, v3) и оно имеет вес = 1.

3) Определим вершину , как помеченную. Следующая вершина становится .

4) Ребро с минимальным весом, выходящим из этой вершины, это ребро (v3, v2), имеющее вес = 3.

5) Определим вершину , как помеченную. Следующая вершина становится .

6) Ребро с минимальным весом, выходящим из этой вершины, это ребро (v2, v5), имеющее вес = 1.

7) Определим вершину , как помеченную. Следующая вершина становится .

8) Ребро с минимальным весом, выходящим из этой вершины, это ребро (v5, v4), имеющее вес = 2.

9) Определим вершину , как помеченную. Следующая вершина становится .

10) Ребро с минимальным весом, выходящим из этой вершины, это ребро (v4, v6), имеющее вес = 1.

На этом работу алгоритма можно считать завершенной и мы можем построить минимальный покрывающий остов.

 

 

Ответ: Минимальный покрывающий остов:

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

1

 

V5

 

V4

 

1

 

2

 

4

 

V3

 

V0

 

1

 

2

 

2

 

3

 

1

 

V2

 

1

 

Решение:

Дано: не пустой взвешенный граф с неотрицательными весами дуг. Требуется построить дерево кратчайших расстояний из 1-й вершины.

Применим алгоритм Дейкстры.

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

1) Первой будем считать вершину с меткой , т. к. она имеет минимальный индекс.

2) Первой соседней вершиной для является вершина, с меткой , т. к. имеет минимальное расстояние до вершины . Длина пути в нее равна кратчайшему расстоянию до вершины + длина ребра, идущего из к , т. е. 0 + 1 = 1.

Итак, построим дерево кратчайших расстояний:

Минимальное расстояние между вершиной и другими вершинами составляет:

 

V0

 

 

Ответ:

 

V3

 

1

 

V4

 

V1

 

V5

 

10. Найти величину максимального потока в данной сети (алгоритм Форда-Фалкерсона).

2

 

 

Блок-схема: узел:

 

 

Решение:

 

Наташа

Автор

Наташа — контент-маркетолог и блогер, но все это не мешает ей оставаться адекватным человеком. Верит во все цвета радуги и не верит в теорию всемирного заговора. Увлекается «нефрохиромантией» и тайно мечтает воссоздать дома Александрийскую библиотеку.

Распродажа дипломных

 Скидка 30% по промокоду Diplom2020

А ты боишься COVID-19?

 Пройди опрос и получи промокод