Прикладне вживання методів дискретної математики

МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ

Бердичівський політехнічний коледж





























Контрольна робота

Прикладне вживання методів дискретної математики



















м. Бердичів 2007 р.


Зміст



			Задача 1

			Задача 2

			Задача 3

			Задача 4

			Список використаної літератури


1. Задача 1

	

		Задана універсальна множина U={a,b,c,d,e,f,g,h,i} і дві множини S={b,c,e,i}, T={c,e,f,i}. Знайти:

		об’єднання, перетин, різницю і симетричну різницю множин S i T;

		доповнення множини S і доповнення множини T;

		прямий добуток множин S i T;

		задати функцію із S в T: ін’єктивну, сюр’єктивну і бієктивну.

		Дані відображення h1 і h2, що представляють множину сумісних кортежів. Знайти:

	h3=(h1h2);

	h4=(h1h2);

	h5=(h1\h2);

	

h1

у

x1

x2

x3



h2

у

x1

x2

x3



2

b

e

6





3

с

e

6



3

с

e

5





5

с

b

2



5

с

b

2





4

а

c

5



4

а

e

5





2

b

e

6

	

	

	

	

	

	h6=(h1h2).

		Хай дані відношення r1 і r2. Знайти:

		

r3=(r1r2);

		r4=(r1r2);

		r5=(r1\r2).

		r6=(r1r2).

r1

x1

x2

x3

x4



r2

x1

x2

x3

x4

x1

1

1

0

1



x1

1

1

0

1

x2

0

1

0

1



x2

1

1

0

0

x3

1

0

1

0



x3

0

1

0

0

x4

0

1

1

1



x4

0

0

1

1

	













Відповідь:



1. 

а)	А = ST = {b, c, e, f, i};

А = ST = {c, e, i};

A = S\T = {b};	B = T\S = {f}:

A = ST = {b, f}.

b)	A = S = {a, d, f, g, h};

	B = T = {a, b, d, g, h}.

c)	ST = {{b, c}, {b, e}, {b, f}, {b, i}, {c, c}, {c, e}, {c, f}, {c, i}, {e, c}, {e, e}, {e, f}, {e, i}, {i, c}, {i, e}, {i, f}, {i, i}}.

2.

a)	h3 = 



у

x1

x2

x3

2

b

e

6

3

с

e

5

5

с

b

2

4

а

e

5

3

с

e

6

4

а

c

5











b) 	h4 = 



c)	h5 = 

у

x1

x2

x3

3

с

e

5

4

а

e

5

d)	h6 = 



у

x1

x2

x3

2

b

e

6

5

с

b

2







3.

a)

r3

x1

x2

x3

x4

x1

1

1

0

1

x2

1

1

0

1

x3

1

1

1

0

x4

0

1

1

1











b)



r4

x1

x2

x3

x4

x1

1

1

0

1

x2

0

1

0

0

x3

0

0

0

0

x4

0

0

1

1









c)

r3

x1

x2

x3

x4

x1

0

0

0

0

x2

0

0

0

1

x3

1

0

1

0

x4

0

1

0

0









d)

r3

x1

x2

x3

x4

x1

0

0

0

0

x2

1

0

0

1

x3

1

1

1

0

x4

0

1

0

0











2. Задача 2



У колоді 52 карти. У скількох випадках при виборі з колоди 10 карт серед них виявляться: а) рівно один туз; б) хоча б один туз; в) не менше двох тузів; г) рівно два тузи?

Відповідь:

а) Всього у колоді 4 тузи. Отже за правилом добутку перемножимо ймовірність вибору з чотирьох тузів одного туза та ймовірність вибору інших карт, тобто 9 з 48:



.



б) Хоча б один туз – це означає може бути і 4, і 3, і 2, і 1. Отже для розв'язку необхідно від ймовірності вибору 10 карт з 52 відняти ймовірність вибору 10 карт з 48:



.



в) Не менше двох тузів – означає, що з 10 карт буде 4, 3 або 2 тузи. Рішенням буде попередня відповідь від якої відняти ймовірність вибору 1 туза (першої відповіді):

.



г) Аналогічно розв'язку першого завдання отримаєм:








3. Задача 3



Граф заданий матрицею вагів. Побудувати для нього остов мінімальної ваги використовуючи алгоритми Пріма та Краскала, за алгоритмом Флойда обчислити найкоротші шляхи графа.







Відповідь:

Будова графа:





х1

х2

х4

х3

х5



Побудова остову мінімальної ваги по алгоритму Краскала:

Встановлюємо частковий порядок по вазі ребер графа:

L13

L15

L14

L12

L23

L45

L34

L35

L24

L25

8

8

9

11

12

12

14

15

18

20



Будуємо остов мінімальної ваги:




х1

х2

х4

х3

х5



Крок

Ребра остову

Вершини остову



L13

L15

L14

L12

x1

x2

x3

x4

x5

1

1

0

0

0

1

1

0

0

0

2

1

1

0

0

1

1

1

0

0

3

1

1

1

0

1

1

1

1

0

4

1

1

1

1

1

1

1

1

1

Lij

8

8

9

11

L=8+8+9+11=36



Обчислення найкоротших шляхів за алгоритмом Флойда:

Будуємо матрицю вагів та матрицю переходів:



А0 = 			Р0 = 



Елементи матриці вагів будемо знаходити за формулою:



Ak [i; j] = min (Ak-1 [i; j], Ak-1 [i; k] + Ak-1 [k; j])



Перша ітерація:	k=1


А1 = 			Р1 = 



Друга ітерація:		k=2



А2 = 			Р2 = 



Третя ітерація:		k=3



А3 = 			Р3 = 



Четверта ітерація:	k=4



А4 = 			Р4 = 



П’ята ітерація:		k=5

А5 = 			Р5 = 



4. Задача 4



Знайти мінімальну ДНФ логічної функції F = F (хг, х2, х3, х4), яка дорівнює одиниці на наборах 2, 3, 4, 11, 14, 15 і нулю на решті наборів.

Відповідь:

Спочатку необхідно подати функцію у ДДНФ.



ДДНФ =x1x2x3x4  x1x2x3x4  x1x2x3x4  x1x2x3x4  x1x2x3x4  x1x2x3x4



Виконуємо склеювання:



1-2		x1x2x3

1-4		x2x3x4

2-4		x2x3x4

4-6		x1x3x4

5-6		x1x2x3

ДДНФ = x1x2x3  x2x3x4  x2x3x4  x1x3x4  x1x2x3  x1x2x3x4

1-2		x2x3 

1-3		x2x3 

2-3		x2x3 

3-4		x3x4 

4-5		x1x3 

ДДНФ = x2x3  x3x4  x1x3  x1x2x3x4 



ДДНФ

x1x2x3x4

x1x2x3x4

x1x2x3x4

x1x2x3x4

x1x2x3x4

x1x2x3x4

x2x3

+

+

-

+

-

-

x3x4

-

+

-

+

-

+

x1x3

-

-

-

+

+

+

x1x2x3x4

-

-

+

-

-

-



Отже, 



min ДНФ = x1x3  x2x3  x1x2x3x4 


Список використаної літератури



	«Дискретна математика» С.Лук’яненко. К-2000

	«Комбінаторика» Д.Сафонов. М-1992

	«Комбінаторика для програмістів» В.Липський. М-1988

	Конспект лекцій

	Комп’ютерна мережа Інтернет