Читайте также:
|
«Дискретная математика»
Решение контрольных заданий оформляется в обычных ученических 12 листовых тетрадях. На обложке тетради записывается название факультета, название кафедры, уч.группа ФИО студента, номер варианта задания.
Ниже представлен пример выполнения контрольного задания.
Вариант №
1.Построить таблицу истинности формулы x 1 ÙØ x 2®(x 1 Ú x 2) ÙØ x 3.
2.Преобразовать формулу так, чтобы она содержала только булевы операции, упростить (x 1 Ú x 3) ÙØ x 2 ~ x 3
3.Из урны, содержащей 6 белых и 4 черных шара, вынимают 4 шара. Найти число неупорядоченных наборов таких, что: 1- все четыре шара черные; 2 – два белых шара и два черных шара. Решить задачу для схемы выбора: а) с возвращением; б) без возвращения.
4. Задана матрица инцидентности графа (цифрами обозначены вершины, буквами – ребра графа). а) восстановить граф по матрице инцидентности; б) выяснить, является ли граф связным; в) построить для данного графа матрицу смежности.
| e1 | e2 | e3 | e4 | e5 | e6 | e7 | e8 | e9 | |
5. A, B, C, D, E, F – населенные пункты, линии –проектируемые участки дорог, цифры – их стоимость. Найти, какие дороги надо построить, чтобы схема дорог позволяла попасть из любого города в любой другой и из всех возможных схем имела наименьшую стоимость.
В 6 C
|
А Е
Решение задачи1.
В начале покажем полный перебор значений переменных. В таблице истинности они дадут заполненные восемь строк трех самых левых столбцов. Будем строить таблицу истинности постепенно, согласно заданного выражения: x 1 ÙØ x 2®(x 1 Ú x 2) ÙØ x 3. Пропуская объяснения промежуточных этапов, получим таблицу истинности (табл. 1).
| x 1 | x 2 | x 3 | Ø x 2 | x 1 ÙØ x 2 | x 1 Ú x 2 | Ø x 3 | (x 1 Ú x 2) ÙØ x 3 | x 1 ÙØ x 2®(x 1 Ú x 2) ÙØ x 3 |
Решение задачи 2.
(x 1 Ú x 3) ÙØ x 2 ~ x 3 = (x 1ÙØ x 2 Ú x 3Ù x 2 ) ~ x 3 =
= (Ø (x 1ÙØ x 2 Ú x 3Ù x 2 ) ÙØ x 3 ) Ú((x 1ÙØ x 2 Ú x 3Ù x 2 ) Ù x 3 )=
= (Ø (x 1ÙØ x 2) ÙØ(Ø x 2Ù x 3)) ÙØ x 3Ú(x 1ÙØ x 2Ù x 3) ÚØ x 2Ù x 3 =
=(Ø x 1Ú x 2) Ù(x 2ÙØ x 3) ÙØ x 3 Ú x 1ÙØ x 2Ù x 3 Ú Ø x 2Ù x 3 =
= (Ø x 1ÙØ x 3 Ú x 2ÙØ x 3) Ù(x 2Ú Ø x 3) Ú x 1ÙØ x 2Ù x 3 Ú Ø x 2Ù x 3 =
= Ø x 1ÙØ x 3 Ú x 2ÙØ x 3 Ú Ø x 1Ù x 2ÙØ x 3 Ú x 2ÙØ x 3 Ú x 1ÙØ x 2Ù x 3 Ú Ø x 2Ù x 3 =
= Ø x 1ÙØ x 3 Ú x 2ÙØ x 3 Ú Ø x 2Ù x 3.
Решение задачи 3.
Случай с возвращением:
По теореме 1 из комбинаторики, число выборок, где все 4 шара черные, равно 44.
способами. Два черных шара выбираем 42=16 способами. Для каждой фиксированной пары белых шаров можем брать любую пару черных, поэтому число выборок, содержащих два белых и два черных, равно 36∙16.
Случай без возвращения:
1. Из 4 черных шаров при выборе без возвращения можно единственным образом
выбрать 4 черных шара. То есть выборка, где все 4 шара черные, одна.
2. Из белых шаров два можно выбрать С26 способами (по теореме 2), аналогично два черных шара из четырех выбираем С24 способами. Число выборок, состоящих из двух черных и двух белых шаров, равно
6! 4! 6!
С26 С24 = = = 90.
2!(6-2)! 2!(4-2)! 8
Решение задачи 4
a) Рассмотрим первый столбец матрицы инцидентности. В ней элементы (A(G))11 и (A(G))21 равны единице. По определению матрицы инцидентности получим, что ребро e1 соединяет вершину 1 с вершиной 2.
Рассматривая аналогично все остальные столбцы, получим:
ребро e2 соединяет вершину 1 с вершиной 2,
ребро e3 соединяет вершину 3 с вершиной 4,
ребро e4 соединяет вершину 1 с вершиной 4,
ребро e5 соединяет вершину 2 с вершиной 4,
ребро e6 соединяет вершину 5 с вершиной 7,
ребро e7 соединяет вершину 5 с вершиной 6,
ребро e8 соединяет вершину 6 с вершиной 7,
ребро e9 соединяет вершину 6 с вершиной 7.
Чертеж графа имеет следующий вид:
4
e6
e4 e3
e9 e8
1 e5 3
e7
e1 e2
a) Данный граф не является связным, так как, например, невозможно по ребрам попасть из вершины 1 в вершину 5
b) Построим для графа матрицу смежности B(G):
По определению матрицы смежности её элемент (B(G))ij равен числу ребер, соединяющих i-ю и j-ю вершины. Рассмотрим поочередно все ребра графа. Ребро e1 соединяет вершину 1 с вершиной 2, поэтому в матрице смежности элементы (B(G))12 и (B(G))21 равны единице. Аналогично получим, что равны единице элементы
(B(G))23 (B(G))32
(B(G))34 (B(G))43
(B(G))14 (B(G))41
(B(G))25 (B(G))42
(B(G))57 (B(G))75
(B(G))56 (B(G))65
Рассмотрим теперь ребро e8 . Оно соединяет вершины 6 и 7. Ребро e9 также соединяет вершины 6 и 7 и других ребер, соединяющих вершины 6 и 7 нет, то есть вершины 6 и 7 соединяют два ребра, поэтому элементы (B(G))67 и (B(G))67 равны двум.
Остальные элементы матрицы смежности равны нулю, так как мы рассмотрели все ребра и все вершины, соединенные этими ребрами.
Окончательно получим:
Критерий для проверки: полученная матрица смежности должна быть симметрична, поскольку ребер, соединяющих вершины i и j, столько же, сколько ребер, соединяющих вершины i и j.
Решение задачи 5.
Решение осуществляем по алгоритму Краскала.
Дата добавления: 2015-08-13; просмотров: 44 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Расчет холодопроизводительности | | | Зарождение и развитие ПВО в годы Первой мировой и Гражданской войн |