Контрольные задания по курсу "Дискретная математика".
1. Раздел «Множества»
Вариант № 8
В группе переводчиков 15 человек владеет английским языком, 19 – французским, 8 – немецким. 9 переводчиков владеют английским и французским языком, 7 – английским и немецким, 6 – французским и немецким. 4 переводчика владеют всеми тремя языками. Сколько переводчиков в группе?
2. Пользуясь равносильными преобразованиями, установить, верно или неверно равенство: А \ (В ∪ С) = (А \ В) ∪ С?
3. В каком случае А
А∩В?
4. Нарисовать диаграмму Эйлера-Венна для множества (
∪
) \ (A ∪ B).
5. Эквивалентны ли множества A = {x: x2 –3x + 2 = 0} и B = {1, 3}?
2. Раздел «Отношения. Функции»
Вариант № 8
1. Задано бинарное отношение ρ = {<2, 2>, <2, 3>, <3, 2>, <3, 4>, <4, 2>}.
Найти D(ρ), R(ρ), ρ
ρ, ρ -1. Проверить, будет ли отношение ρ рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения транзитивного, рефлексивного и антисимметричного.
3. Дана функция f(x) = x +
, отображающая множество действительных чисел R во множество действительных чисел, R→ R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
3. Раздел «Графы»
1. Описать граф, заданный матрицей смежности, используя как можно больше характеристик. Составить матрицу инцидентности и связности (сильной связности).
2. Пользуясь алгоритмом Форда-Беллмана, найти минимальный путь из x1 в x7 в ориентированном графе, заданном матрицей весов.
3. Пользуясь алгоритмом Краскала, найти минимальное остовное дерево для графа, заданного матрицей длин ребер.
1.
0 1 1 0 1 1 2. ∞ 2 5 8 9 ∞ ∞ 3.
∞ 1 3 4 5
1 0 1 1 0 1 ∞ ∞ ∞ 10 4 ∞ ∞ 1 ∞ 2 9 1
1 1 0 0 1 1 5 3 ∞ 2 1 ∞ ∞ 3 2 ∞ 1 1
0 1 0 0 0 1 ∞ ∞ ∞ ∞ 7 6 ∞ 4 9 1 ∞ 3
1 0 1 0 0 0 ∞ ∞ ∞ ∞ ∞ ∞ 5 5 1 1 3 ∞
1 1 1 1 0 0 ∞ ∞ ∞ ∞ ∞ ∞ 9
∞ ∞ ∞ ∞ ∞ ∞ ∞
4. Раздел «Булевы функции»
Для данной формулы булевой функции
а) найти ДНФ, КНФ, СДНФ, СКНФ методом равносильных преобразований;
б) найти СДНФ, СКНФ табличным способом (сравнить с СДНФ, СКНФ, полученными в пункте “а”);
в) указать минимальную ДНФ и соответствующую ей переключательную схему.
(x&¬y) ⊃ ((¬xVz) & y)
Комбинаторика
Вариант 8.
1. Тест содержит два вопроса и по три возможных ответа на каждый из них. Сколько вариантов ответа на тест у студента?
2. Предприятие может представить работу по одной специальности 4-м женщинам, по другой - 5 мужчинам и по 3-ей - 3-ем работникам любого пола. Сколькими способами можно заполнить эти места, если имеются 10 мужчин и 8 женщин?
3. Чему равен коэффициент разложения бинома (х+у)8 при слагаемом х3 у5 .
Список рекомендованной литературы
1. Акимов математика: логика, группы, графы. – М.: Лаборатория Базовых Знаний, 2001.
2. , Адельсон-Вельский математика для инженера. – М.: Энергоиздат, 1988.
3. омбинаторика для программистов. – М.: Мир, 1988.
4. , Осипова дискретной математики. – М.: Издательство МАИ, 1992.
5. Новиков математика для программистов. – СПб.: Питер, 2002.
6. , Овчинникова дискретной математики. – М.: ИНФРА – М, Новосибирск: Изд-во НГТУ, 2002.
