Контрольная - Дискретная математика - файл n2.doc
Контрольная - Дискретная математикаскачать (48 kb.)
Доступные файлы (1):
n2.doc
1. Комбинаторика 2.2 Бросают три игральные кости (с шесть гранями каждая). Сколькими способами они могут упасть так, что либо все оказавшиеся вверху грани одинаковы, либо все попарно различны? 6 вариантов, когда все одинаковы и 6*5*4=120, когда все попарно различны
Итого: 126 вариантов
6.5. Предложить алгоритм бесповторного перечисления всех (n,n) перестановок чисел 1,2,…,n. Может быть n вариантов первой цифры, n-1 второй и т.д. Следовательно число вариантов равно
1*2*3*…*n=n!
2. Графы 3. Записать следующие графы матрицами инцидентности и смежности.(Рис.3.).
Х3
а) б) в)
| Х1 | Х2 | Х3 | Х4 | Х5 |
Х1 | 0 | 1 | 0 | 0 | 0 |
Х2 | 1 | 0 | 1 | 0 | 0 |
Х3 | 0 | 1 | 0 | 1 | 0 |
Х4 | 0 | 0 | 1 | 0 | 1 |
Х5 | 0 | 0 | 0 | 1 | 0 |
а)матрица инцидентности матрица смежности
| Е1 | Е2 | Е3 | Е4 |
Х1 | 1 | 0 | 0 | 0 |
Х2 | 1 | 0 | 0 | 1 |
Х3 | 0 | 0 | 1 | 1 |
Х4 | 0 | 1 | 1 | 0 |
Х5 | 0 | 1 | 0 | 0 |
б)матрица инцидентности матрица смежности
| Х1 | Х2 | Х3 | Х4 | Х5 |
Х1 | 0 | 1 | 0 | 0 | 0 |
Х2 | 1 | 0 | 1 | 0 | 0 |
Х3 | 0 | 1 | 0 | 1 | 0 |
Х4 | 0 | 0 | 1 | 0 | 1 |
Х5 | 0 | 0 | 0 | 1 | 0 |
| Е1 | Е2 | Е3 | Е4 |
Х1 | 1 | 0 | 0 | 0 |
Х2 | 1 | 1 | 0 | 0 |
Х3 | 0 | 1 | 1 | 0 |
Х4 | 0 | 0 | 1 | 1 |
Х5 | 0 | 0 | 0 | 1 |
в)матрица инцидентности матрица смежности
| Х1 | Х2 | Х3 | Х4 | Х5 |
Х1 | 0 | 1 | 0 | 0 | 0 |
Х2 | 0 | 0 | 0 | 0 | 0 |
Х3 | 0 | 1 | 0 | 0 | 0 |
Х4 | 0 | 0 | 1 | 0 | 0 |
Х5 | 0 | 0 | 0 | 1 | 0 |
| Е1 | Е2 | Е3 | Е4 |
Х1 | -1 | 0 | 0 | 0 |
Х2 | +1 | +1 | 0 | 0 |
Х3 | 0 | -1 | +1 | 0 |
Х4 | 0 | 0 | -1 | +1 |
Х5 | 0 | 0 | 0 | -1 |
8. Даны графы типа дерева на рис.7. Для каждого графа выполнить следующее задание. Сколько вершин максимального типа имеется в данном графе? Какое цикломатическое число графа? Чему равно цикломатическое число графа G', являющегося лесом и представленного двумя одинаковыми деревьями рассматриваемого типа графа? Построить ориентированное дерево с корнем 0, являющимся вершиной максимального типа.
Рис. 7
Цикломатическое число v(G)= m-n+1
m- кол-во ребер
n- кол-во вершин
G1)v(G)=20-20+1 =1
G2)v(G)=18-19+1 =0 => G2 уже дерево
G3)v(G)=18-19+1 =0 => G3 уже дерево
Кол-во вершин максимального типа:
G1)7
G2)4
G3)2
Цикломатическое число леса:
G1)1*2=2
G2)0*2=0
G3)0*2=0
Ориентированные деревья:
20. Найти ядро графа с помощью алгоритмов Магу (рис. 4.12).
1.Найдем множества внутренней устойчивости:
-
| 1 | 2 | 3 | 4 | 5 |
1 |
|
| 1 |
|
|
2 |
|
|
| 1 |
|
3 |
|
|
|
| 1 |
4 | 1 |
|
|
|
|
5 |
| 1 |
|
|
|
(1v3)(1v4)(2v4)(2v5)(3v5)
Перейдем к ДНФ
123v125v145v234v345
Для каждой конъюнкции выписываем недостающие вершины, образующие множества внутренней устойчивости.
{4,5},{3,4},{2,3},{1,5},{1,2}
2.Найдем множества внешней устойчивости:
-
| 1 | 2 | 3 | 4 | 5 |
1 | 1 |
| 1 |
|
|
2 |
| 1 |
| 1 |
|
3 |
|
| 1 |
| 1 |
4 | 1 |
|
| 1 |
|
5 |
| 1 |
|
| 1 |
(1v3)(2v4)(3v5)(1v4)(2v5)
Перейдем к ДНФ
123v125v145v234v345
{1,2,3}{1,2,5},{1,4,5},{2,3,4},{3,4,5}
Совпадающих множеств нет.
21. Привести граф к яруcно-параллельной форме (рис. 4.13).
| 1 | 2 | 3 | 4 | 5 | 6 |
1 |
|
|
|
|
|
|
2 |
|
|
|
|
|
|
3 |
| 1 |
|
|
|
|
4 | 1 |
| 1 |
| 1 |
|
5 |
|
|
|
|
|
|
6 | 1 |
| 1 | 1 | 1 |
|

6
4





1 5 5

2
28. Используя метод Магу, определить максимально внутренне устойчивые, а также минимально внешне устойчивые множества вершин орграфов и найти их ядра. v1 v2






v

3 v4
1.Найдем множества внутренней устойчивости:
-
| 1 | 2 | 3 | 4 |
1 |
| 1 | 1 |
|
2 |
|
|
|
|
3 |
| 1 |
| 1 |
4 |
|
| 1 |
|
(1v2)(1v3)(2v3)(3v4)
Перейдем к ДНФ
13v23v124
Для каждой конъюнкции выписываем недостающие вершины, образующие множества внутренней устойчивости.
{2,4},{1,4},{3}
2.Найдем множества внешней устойчивости:
-
| 1 | 2 | 3 | 4 |
1 | 1 | 1 | 1 |
|
2 |
| 1 |
|
|
3 |
| 1 | 1 | 1 |
4 |
|
| 1 | 1 |
(1v2v3)(2)(2v3v4)(3v4)
Перейдем к ДНФ
23v24
{2,3},{2,4}
{2,4} ядро графа
3. Резолюции 1. Необходимо ответить, являются ли следующие конструкции термами max (x,y,z), (x,y), (xy),
. Все конструкции – термы, т.к. являются функциями
2. Необходимо ответить, являются ли следующие конструкции формулами
P(x); х P(x) Все конструкции являются формулами, т.к
P(x)это атом.
3. Являются ли выполнимыми следующие формулы? P(a) P(a);Формула является выполнимой т.к. результат 1.
31. Получить множество дизъюнктов.
x, y, z (P(x)&Q(x, y)R(z))
Приведем к конъюктивной нормальной форме
x, y, z ((P(x) R(z))&(Q(x, y)R(z)))
Кванторов существования нет, а кванторы общности можно отбросить
(P(x) R(z)),(Q(x, y)R(z))
x, y, z (P(x)Q(x, y)R(z)M(y))
Избавимся от импликации:
x, y, z ((P(x)Q(x, y))R(z)M(y))
Приведем к конъюктивной нормальной форме
x, y, z ((P(x)&Q(x, y))R(z)M(y))
Т.к. есть квантор существования, и левее нет кванторов общности, то заменяем х
i на константу k.
(P(k)&Q(k, y))R(z)M(y)
4. Машины Тьюринга 3. Построить машину Т, сдвигающую головку вправо на следующий массив единиц, который будет обнаружен на ленте: 1q1x1y 1x1y-1q01 (машина находит следующий справа массив единиц и останавливается, воспринимая самую правую заполненную ячейку).
| q1 | q2 |
1 | Q21П | Q21П |
| Q1П | Q0Л |
8. По заданной машине Т и начальной конфигурации М1 найти заключительную конфигурацию . 8.1. T:
| q1 | q2 |
0 | q01C | q10П |
1 | q20П | q21Л |
а) M
1 = 1
2q11
301;
Ответ: М
2=11000000q
01
9. Построить в алфавите {0,1} машину Т, переводящую конфигурацию M0 в конфигурацию М1. 3) М0 = 1nq10, М1 = q012n, (n1);
| q1 | q2 | q3 | q4 | q5 | q6 | q7 |
1 | - | Q21Л | Q40П | Q41П | Q51П | - | Q71Л |
0 | q20Л | Q30П | Q00С | Q50П | Q61П | Q71Л | Q1,0С |
5. Рекурсивные функции 1. Применить операцию примитивной рекурсии к функциям g(x1) и h(x1, x2, x3) 3) g(x1)= 1 и h(x1, x2, x3) = x3(1+sgx1+2-2x3);3. Доказать примитивную рекурсивность следующих функций 3)
(усеченная разность) 6. Применить операцию минимизации к функции f по переменной xi. Результирующую функцию представить в аналитической форме. 3)
f(
x1,
x2) =
I12(
x1,
x2),
i=2;
1. Комбинаторика