Контрольная - Дискретная математика - файл n2.doc
Контрольная - Дискретная математикаскачать (48 kb.)
Доступные файлы (1):
| n2.doc | 165kb. | 20.03.2011 22:13 | скачать |
- Смотрите также:
- Чудинов К.М. (состав.) Дискретная математика (Документ)
- Галкина М.Ю. Дискретная математика (Документ)
- Гусева А.И., Тихомирова А.Н. Дискретная математика для информатиков и экономистов (Документ)
- Контрольная работа - Дискретная математика вариант 1 (Лабораторная работа)
- Довгий П.С., Поляков В.И. Арифметические основы ЭВМ (Документ)
- Новиков Ф.А. Дискретная математика для программистов (Документ)
- Контрольная - Дискретная математика (Лабораторная работа)
- Эвнин А.Ю. Дискретная математика. Конспект лекций (Документ)
- Алексеев В.В. Элементы теории множеств и теории графов. Сборник задач и упражнений по курсу Дискретная математика (Документ)
- Эвнин А.Ю. Задачник по дискретной математике (Документ)
- Чудесенко. Учебник по высшей математике (Документ)
- Белоусов А.И., Ткачев С.Б. Дискретная математика (Документ)
n2.doc
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 228. Используя метод Магу, определить максимально внутренне устойчивые, а также минимально внешне устойчивые множества вершин орграфов и найти их ядра.
v1 v2
v
3 v41.Найдем множества внутренней устойчивости:
-
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Л |
Ответ: М2=11000000q01
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. Комбинаторика