1. Варианты индивидуального задания (контрольной работы)

1. Представить с помощью кругов Эйлера множественное выражение. Используя законы и свойства алгебры множеств, упростить заданное выражение.

2. Заданы множества кортежей. Показать, что эти множества представляют собой соответствия между множествами N₁ и N₂ , если N₁ = N₂ = . Дать полную характеристику этих соответствий.

3. Частично упорядоченное множество М задано множеством упорядо-ченных пар. Построить диаграмму и определить является ли данное множество решеткой. Если заданное множество является решеткой, то определить является ли решетка дедекиндовой , дистрибутивной.

4. Из колоды, содержащей 52 карты, вынули 10 карт. В скольких случаях среди этих карт окажется указанное количество указанных карт?

5. После обследования читательских вкусов оказалось, что 60% студентов читает журнал А, 65% − журнал В, 60% − журнал С, 55% − журнал Д, 40% − журналы А и В, 35% − журналы А и С, 30% − журналы А и Д, 40% − журналы В и С, 35% − журналы В и Д, 30% − журналы С и Д, 25% − журналы А, В и С, 20% − журналы А, В и Д, 20% − журналы А, С и Д, 15% − журналы В, С и Д, 10% − журналы А, В, С и Д. Сколько процентов студентов читает указанные журналы?

6. Решить рекуррентное соотношение.

7. Для неориентированного графа , у которого :

а) вычислить числа ;

б) определить хроматическое число .

8. Для заданной сети :

а) найти величину минимального пути и сам путь от вершины до вершины по алгоритму Дейкстры ;

б) используя алгоритм Форда-Фалкерсона, определить максималь-ный поток ( v₁ – вход , v₇ – выход сети ) и указать ми-нимальный разрез, отделяющий v₁ от v₇ ,

если задана матрица весов (длин, пропускных способностей) Р.

9. Используя алгоритм Краскала, построить остов с наименьшим весом для неориентированного взвешенного графа , у ко-торого , если заданы веса (длины) ребер.

ВАРИАНТ № 1

1.

2.

3. .

4. Хотя бы один «туз».

5. Не читает ни одного журнала.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 2

1.

2.

3. .

4. Ровно два «короля».

5. Читает только журнал А.

6.

7. .

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 3

1.

2.

3. .

4. Не менее трех «дам».

5. Читает только журналы А и В.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 4

1.

2.

3. .

4. Не более двух «валетов».

5. Читает только журналы А, В и С.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 5

1.

2.

3. .

4. Ни одного «короля».

5. Читает только один журнал.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 6

1.

2.

3. .

4. Хотя бы два «туза».

5. Читает менее четырех журналов.

6.

7. .

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 7

1.

2.

3. .

4. Ровно четыре «туза».

5. Читает не менее двух журналов.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 8

1.

2.

3. .

4. Не менее одного «валета».

5. Читает не более одного журнала.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 9

1.

2.

3. .

4. Не более трех «дам».

5. Читает только журнал В.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 10

1.

2.

3. .

4. Ни одного «туза».

5. Читает только журналы А и С.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 11

1.

2.

3. .

4. Хотя бы три «туза».

5. Читает только журналы А, В и Д.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 12

1.

2.

3. .

4. Ровно один «валет».

5. Читает только два журнала.

6.

7. .

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 13

1.

2.

3. .

4. Не менее двух «дам».

5. Читает менее трех журналов.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 14

1.

2.

3. .

4. Не более трех «королей».

5. Читает не менее трех журналов.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 15

1.

2.

3. .

4. Ни одного «валета».

5. Читает не более двух журналов.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 16

1.

2.

3. .

4. Хотя бы один «король».

5. Читает только журнал С.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 17

1.

2.

3. .

4. Ровно три «дамы».

5. Читает только журналы А и Д.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 18

1.

2.

3. .

4. Не менее двух «королей».

5. Читает только журналы А, С и Д.

6.

7. .

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 19

1.

2.

3. .

4. Не более двух «королей».

5. Читает только три журнала.

6.

7. .

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 20

1.

2.

3. .

4. Ни одной «дамы».

5. Читает менее двух журналов.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 21

1.

2.

3. .

4. Хотя бы два «короля».

5. Читает не менее одного журнала.

6.

7. .

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 22

1.

2.

3. .

4. Ровно два «валета».

5. Читает не более трех журналов.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 23

1.

2.

3. .

4. Не менее трех «валетов».

5. Читает только журнал Д.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 24

1.

2.

3. .

4. Не более двух «дам».

5. Читает только журналы В и С.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 25

1.

2.

3. .

4. Хотя бы три «короля».

5. Читает только журналы В, С и Д.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 26

1.

2.

3. .

4. Ровно одна «дама».

5. Читает только журналы В и Д.

6.

7. .

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 27

1.

2.

3. .

4. Не менее трех «тузов».

5. Читает только один журнал.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 28

1.

2.

3. .

4. Не более двух «тузов».

5. Читает менее четырех журналов.

6.

7. .

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 29

1.

2.

3. .

4. Ровно две «дамы».

5. Читает не менее двух журналов.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 30

1.

2.

3. .

4. Не менее трех «королей».

5. Читает не более одного журнала.

6.

7. .

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 31

1.

2.

3. .

4. Ровно три «валета».

5. Читает только журналы С и Д.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 32

1.

2.

3. .

4. Не менее двух «тузов».

5. Читает не более трех журналов.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 33

1.

2.

3. .

4. Не более трех «тузов».

5. Читает только два журнала.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 34

1.

2.

3. .

4. Хотя бы две «дамы».

5. Читает менее трех журналов.

6.

7.

.

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

ВАРИАНТ № 35

1.

2.

3. .

4. Ровно три «короля».

5. Читает не менее трех журналов.

6.

7. .

v₁ v₂ v₃ v₄ v₅ v₆ v₇

8. Р = .

9.

2. ОБРАЗЕЦ ВЫПОЛНЕНИЯ ИНДИВИДУАЛЬНОГО ЗАДАНИЯ (КОНТРОЛЬНОЙ РАБОТЫ)

1. Представить с помощью кругов Эйлера множественное

выражение

.

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

□ Используя круги Эйлера и, учитывая, что операция пересечения выполняется раньше операции объединения, получим следующие рисунки:

Объединяя заштрихованные области, получим искомое множество:

Упростим заданное выражение:

=

.

■

2. Заданы множества кортежей:

.

Показать, что эти множества представляют собой соответствия между множествами N₁ и N₂ , если N₁ = N₂ = . Дать полную характеристику этих соответствий.

□ Найдем декартово произведение:

Видно, что заданные множества являются подмножествами этого прямого произведения. Следовательно, данные множества есть соответствия.

а) .

Область определения: . Следовательно, соответствие является частично определенным.

Область значений: . Следовательно, соответствие является сюръективным.

Образом элемента являются два элемента . Значит, соответствие не является функциональным. Из этого следует, что соответствие не является функцией, отображением.

б) .

Область определения: . Следовательно, соответствие является частично определенным.

Область значений: . Следовательно, соответствие не является сюръективным.

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

в) .

Область определения: . Следовательно, соответствие всюду определено.

Область значений: . Следовательно, соответствие не является сюръективным.

Образом любого элемента из является единственный элемент из . Следовательно, соответствие является функциональным, функцией. Так как соответствие всюду определено, то имеем полностью определенную функцию, т.е. имеем отображение N₁ в N₂ .

г) .

Область определения: . Значит, соответствие полностью определено.

Область значений: . Значит, соответствие сюръективно.

Образом любого элемента из N₁ является единственный элемент из N₂ . Следовательно, соответствие является функциональным, функцией.

Так как соответствие всюду определено, сюръективно, функционально и прообразом любого элемента из является единственный элемент из , то соответствие является взаимно однозначным.

Так как функция полностью определена и соответствие сюръективно, то имеем отображение N₁ на N₂ .

Так как для любых двух различных элементов из N₁ их образы из N₂ также различны, то отображение является инъективным.

Так как отображение является одновременно сюръективным и инъективным, то имеем биективное отображение (взаимно однозначное отображение).

■

3. Частично упорядоченное множество М задано множеством

упорядоченных пар

.

Построить диаграмму и определить, является ли данное множество решеткой. Если заданное множество является решеткой, то определить, является ли решетка дедекиндовой , дистрибутивной.

□ Построим диаграмму:

Построим таблицу:

Пары элементов	Н.Г.	В.Г.	Н.Н.Г.	Н.В.Г.
1,2	1	2,5	1	2
1,3	1	3,4,5	1	3
1,4	1	4,5	1	4
1,5	1	5	1	5
1,6	1	6,2,5	1	6
2,3	1	5	1	5
2,4	1	5	1	5
2,5	2,6,1	5	2	5
2,6	6,1	2,5	6	2
3,4	3,1	4,5	3	4
3,5	3,1	5	3	5
3,6	1	5	1	5
4,5	4,3,1	5	4	5
4,6	1	5	1	5
5,6	6,1	5	6	5

Так как любая пара элементов имеет единственную наибольшую ниж-нюю грань и единственную наименьшую верхнюю грань, то заданное частично упорядоченное множество М является решеткой.

Решетка М является дедекиндовой, когда выполняется равенство:

для таких , что .

Решетка М не является дедекиндовой, т.к. указанное равенство не выполняется, например, для элементов 2, 3, 4:

Одним из условий дистрибутивности решетки является ее дедекиндо-вость. Так как решетка М не является дедекиндовой, то она не является дистрибутивной решеткой.

■

4. Из колоды, содержащей 52 карты, вынули 10 карт. В скольких

случаях среди этих карт окажется не более одной «шестерки»?

□ Не более одной «шестерки» означает, что среди извлеченных 10 карт может быть: либо ни одной «шестерки», либо одна «шестерка». Всего в колоде 4 «шестерки».

По правилу произведения:

− ровно нуль «шестерок» ( − нуль «шестерок» из четырех и − десять не «шестерок» из 48 карт, не содержащих «шестерок»);

− ровно одна «шестерка» ( − одна «шестерка» из четырех и − девять не «шестерок» из 48 карт, не содержащих «шестерок»).

Число не более одной «шестерки» среди выбранных 10 карт по правилу суммы будет равно

+ = =

=

=

= 47·46·44·43·41·39 + 16·47·46·22·43·41·5 = 6 540 715 896 + 6 708 426 560 =

= 13 249 142 456

■

5. При опросе сотрудников некоторого учреждения оказалось, что 60% сотрудников знают английский язык, 50% − французский, 50% − немецкий, 30% − английский и французский, 20% − французский и немецкий, 40% − английский и немецкий, 10% − английский, французский и немецкий. Сколько процентов сотрудников знают не менее двух языков.

□ Знать не менее двух языков – это знать два или три языка. Пусть − количество сотрудников, знающих не менее r языков из k языков. Тогда = + , где − количество сотрудников, знающих два языка; − количество сотрудников, знающих три языка. Количество сотрудников, знающих два языка, можно определить по формуле

,

т.е.

= + ,

где − количество сотрудников, знающих хотя бы два языка; − количество сотрудников, знающих три языка.

Пусть общее число сотрудников равно 1 или 100%. Тогда

= 0,3 + 0,2 + 0,4 = 0,9 и = 0,1 (по условию).

Следовательно,

1·0,9 − 3·0,1 = 0,6 или 60%.

По условию задачи = 0,1. Следовательно, количество сотрудников, знающих не менее 2 языков из 3 языков:

= 0,6 + 0,1 = 0,7 или 70%.

Для подсчета числа сотрудников, знающих не менее 2 языков, можно также воспользоваться формуле

= = = − =

= 1·0,9 − 2·0,1 = 0,2 или 70%.

■

6. Решить рекуррентное соотношение

□ Решить рекуррентное соотношение – это значит найти общий член последовательности , удовлетворяющей указанному рекуррентному соотношению.

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

или

,

или

.

Так как = , то

, , .

Тогда

) ) − ,

+ 9 t + 2t − 8t² = .

Отсюда

= = .

Методом неопределенных коэффициентов находим А, В и С:

,

пусть : , А = 1;

пусть : , В = −3;

пусть : , С = 2.

Тогда

= =

= = .

Следовательно, общий член последовательности имеет вид

= .

■

7. Для неориентированного графа , у которого ,

а) вычислить числа ;

б) определить хроматическое число .

□ Построим граф:

а) Вычислим числа .

1) :

Используя алгоритм выделения пустых подграфов, построим дерево:

Согласно определению :

.

2) :

Используя алгоритм выделения полных подграфов, построим дерево:

Здесь - полные подграфы. Видно, что мощность носителей всех под-графов равна трем, т.е.

.

3) :

Построим модифицированную матрицу смежности заданного графа G :

1 2 3 4 5 6

.

Находим минимальное число строк, покрывающих все столбцы модифи-цированной матрицы . Таких строк – одна. Следовательно,

.

б) Определим хроматическое число .

Согласно алгоритму минимальной раскраски вершин графа, выделим все пустые подграфы графа G , т.е. построим дерево (оно построено в пункте а) ):

Построим таблицу:

1 2 3 4 5 6

1. {1,4,6} 1 1 1

2. {1,5} 1 1

3. {2,5} 1 1

4. {2,6} 1 1

5. {3} 1

Определяем минимальное число строк, покрывающих все столбцы табли-цы. Такими строками могут быть строки 1, 3, 5. Значит,

.

Зададимся красками: для множества вершин - краска синяя (С ), для множества вершин - краска красная ( К ), для множества вер-шин - краска зеленая ( З ).

Раскрасим вершины графа G :

■

8. Для заданной сети :

а) найти величину минимального пути и сам путь от вершины до вершины по алгоритму Дейкстры ;

б) используя алгоритм Форда-Фалкерсона, определить максималь-ный поток ( v₁ – вход , v₆ – выход сети ) и указать ми-нимальный разрез, отделяющий v₁ от v₆ ,

если задана матрица весов (длин, пропускных способностей) Р :

v₁ v₂ v₃ v₄ v₅ v₆

□ Построим сеть:

а) Найдем величину минимального пути и сам путь сети G . Использу-ем для этого алгоритм Дейкстры.

Этап 1. Нахождение длины кратчайшего пути.

.

Шаг 1. Полагаем

1-я итерация.

Шаг 2. Составим множество вершин, непосредственно следующих за с временными метками: . Пересчитываем вре-менные метки этих вершин: ,

.

Шаг 3. Одна из временных меток превращается в постоянную:

Шаг 4. Следовательно, возвращаемся на второй шаг.

2-я итерация.

Шаг 2.

Шаг 3.

Шаг 4. Переход на второй шаг.

3-я итерация.

Шаг 2.

Шаг 3.

Шаг 4. Переход на второй шаг.

4-я итерация.

Шаг 2.

Шаг 3.

Шаг 4. Переход на второй шаг.

5-я итерация.

Шаг 2.

Шаг 3.

Шаг 4. Конец первого этапа.

Следовательно, длина кратчайшего пути равна .

Этап 2. Построение кратчайшего пути.

1-я итерация.

Шаг 5. Составим множество вершин, непосредственно предшеству-ющих с постоянными метками : Проверим равенство

для этих вершин:

т.е.

т.е.

Включаем дугу в кратчайший путь,

Шаг 6. Возвращаемся на пятый шаг.

2-я итерация.

Шаг 5.

Включаем дугу в кратчайший путь, .

Шаг 6. . Завершение второго этапа.

Следовательно, кратчайший путь построен. Его образует последователь- ность дуг: .

Окончательно, кратчайший путь от вершины до вершины v₆ пост-роен. Его длина (вес) равна . Сам путь образует последова-тельность дуг:

б) Определим максимальный поток через сеть G. Для этого используем алгоритм Форда – Фалкерсона.

Выбираем произвольно путь из вершины v₁ в вершину v₆ . Пусть это будет путь . Минимальную пропускную способность на этом пути, равную 10, имеет дуга , т.е. Увеличим на этом пути поток до 10 единиц. Дуга становится насыщенной. Дуга имеет на данный момент пропускную способность, равную 10.

Путь Следовательно, поток на этом пути можно увеличить на 9 единиц. Дуги становятся насыщенными.

Других маршрутов нет (другие маршруты проходят через насыщенные дуги). Поток максимален. Делаем разрез вокруг вершины v₁ по насыщенным дугам

и получаем его величину единиц.

■

9. Используя алгоритм Краскала, построить остов с наименьшим

весом для неориентированного взвешенного графа , у ко-торого , если заданы веса (длины) ребер:

□ Построим граф G :

1. Упорядочим ребра в порядке неубывания веса (длины):

2. Возьмем ребро u₁ и поместим его в строящийся остов.

Возьмем ребро u₂ и поместим его в строящийся остов (т.к. оно не обра-зует с предыдущим ребром цикла).

Берем ребро u₃ и помещаеи его в строящийся остов (т.к. оно не образу-ет с предыдущими ребрами цикла).

Берем ребро u₄ и помещаем его в строящийся остов (т.к. оно не образу-ет с предыдущими ребрами цикла).

Берем ребро u₅ и помещаем его в строящийся остов (т.к. оно не образу-ет цикла с предыдущими ребрами).

Проверим окончание алгоритма. Число входящих в остов ребер равно 5. Заданный граф имеет п = 6 вершин и . Таким образом, остов содержит все вершины заданного графа G .

Вес (длина) построенного остова

равен .

■