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

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

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

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

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

Зміст

Задача 1

Задача 2

Задача 3

Задача 4

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

1. Задача 1

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

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

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

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

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

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

1. h³=(h¹h²);

2. h⁴=(h¹h²);

3. h⁵=(h¹\h²);

h¹

у

x₁

x₂

x₃

h²

у

x₁

x₂

x₃

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

4. h⁶=(h¹h²).

3. Хай дані відношення r¹ і r². Знайти:

r³=(r¹r²);

1. r⁴=(r¹r²);

2. r⁵=(r¹\r²).

3. r⁶=(r¹r²).

r¹

x₁

x₂

x₃

x₄

r²

x₁

x₂

x₃

x₄

x₁

1

1

0

1

x₁

1

1

0

1

x₂

0

1

0

1

x₂

1

1

0

0

x₃

1

0

1

0

x₃

0

1

0

0

x₄

0

1

1

1

x₄

0

0

1

1

Відповідь:

1.

а) А = ST = {b, c, e, f, i};

А = ST = {c, e, i};

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

A = ST = {b, f}.

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

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

c) ST = {{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) h³ =

у

x₁

x₂

x₃

2

b

e

6

3

с

e

5

5

с

b

2

4

а

e

5

3

с

e

6

4

а

c

5

b) h⁴ =

c) h⁵ =

у

x₁

x₂

x₃

3

с

e

5

4

а

e

5

d) h⁶ =

у

x₁

x₂

x₃

2

b

e

6

5

с

b

2

3.

a)

r³

x₁

x₂

x₃

x₄

x₁

1

1

0

1

x₂

1

1

0

1

x₃

1

1

1

0

x₄

0

1

1

1

b)

r⁴

x₁

x₂

x₃

x₄

x₁

1

1

0

1

x₂

0

1

0

0

x₃

0

0

0

0

x₄

0

0

1

1

c)

r³

x₁

x₂

x₃

x₄

x₁

0

0

0

0

x₂

0

0

0

1

x₃

1

0

1

0

x₄

0

1

0

0

d)

r³

x₁

x₂

x₃

x₄

x₁

0

0

0

0

x₂

1

0

0

1

x₃

1

1

1

0

x₄

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

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

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

L₁₃

L₁₅

L₁₄

L₁₂

L₂₃

L₄₅

L₃₄

L₃₅

L₂₄

L₂₅

8

8

9

11

12

12

14

15

18

20

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

х1

х2

х4

х3

х5

Крок

Ребра остову

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

L₁₃

L₁₅

L₁₄

L₁₂

x₁

x₂

x₃

x₄

x₅

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

L_ij

8

8

9

11

L=8+8+9+11=36

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

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

А₀ = Р₀ =

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

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

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

А₁ = Р₁ =

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

А₂ = Р₂ =

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

А₃ = Р₃ =

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

А₄ = Р₄ =

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

А₅ = Р₅ =

4. Задача 4

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

Відповідь:

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

ДДНФ =x₁x₂x₃x₄  x₁x₂x₃x₄  x₁x₂x₃x₄  x₁x₂x₃x₄  x₁x₂x₃x₄  x₁x₂x₃x₄

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

1-2 x₁x₂x₃

1-4 x₂x₃x₄

2-4 x₂x₃x₄

4-6 x₁x₃x₄

5-6 x₁x₂x₃

ДДНФ = x₁x₂x₃  x₂x₃x₄  x₂x₃x₄  x₁x₃x₄  x₁x₂x₃  x₁x₂x₃x₄

1-2 x₂x₃

1-3 x₂x₃

2-3 x₂x₃

3-4 x₃x₄

4-5 x₁x₃

ДДНФ = x₂x₃  x₃x₄  x₁x₃  x₁x₂x₃x₄

ДДНФ

x₁x₂x₃x₄

x₁x₂x₃x₄

x₁x₂x₃x₄

x₁x₂x₃x₄

x₁x₂x₃x₄

x₁x₂x₃x₄

x₂x₃

+

+

-

+

-

-

x₃x₄

-

+

-

+

-

+

x₁x₃

-

-

-

+

+

+

x₁x₂x₃x₄

-

-

+

-

-

-

Отже,

min ДНФ = x₁x₃  x₂x₃  x₁x₂x₃x₄

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

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

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

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

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

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