Контрольная - Дискретная математика - файл n2.doc

Контрольная - Дискретная математика
скачать (48 kb.)
Доступные файлы (1):
n2.doc165kb.20.03.2011 22:13скачать

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





v3 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. Получить множество дизъюнктов.

  1. 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))

  1. 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

Q2

Q2



Q1П

Q0Л


8. По заданной машине Т и начальной конфигурации М1 найти заключительную конфигурацию .

8.1. T:





q1

q2

0

q01C

q1

1

q2

q2
а) M1 = 12q11301;

Ответ: М2=11000000q01


9. Построить в алфавите {0,1} машину Т, переводящую конфигурацию M0 в конфигурацию М1.

3) М0 = 1nq10, М1 = q012n, (n1);





q1

q2

q3

q4

q5

q6

q7

1

-

Q2

Q4

Q4

Q5

-

Q7

0

q2

Q3

Q0

Q5

Q6

Q7

Q1,


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. Комбинаторика
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации