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. Найти общее решение рекуррентного соотношения при заданных начальных членах

Решение:

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

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

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

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

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

Ответ:

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

 

 

Решение: