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

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

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

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

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

М. Бердичів 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}. Знайти:

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

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

C) прямий добуток множин SiT;

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

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

A) h3 =(h1 Èh2 );

B) h4 =(h1 Çh2 );

C) h5 =(h1 \h2 );

H1УX1X2X 3H2УX1X2X 3
2BE63СE6
3СE55СB2
5СB24АC5
4АE52BE6

D) h6 =(h1 Dh2 ).

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

A) R3 =(r1 Èr2 );

B) r4 =(r1 Çr2 );

C) r5 =(r1 \r2 ).

D) r6 =(r1 Dr2 ).

R1X1X2X3X4R2X1X2X3X4
X11101X11101
X20101X21100
X31010X30100
X40111X40011

Відповідь:

1.

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

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

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

A = SDT = {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) h3 =

УX1X2X 3
2BE6
3СE5
5СB2
4АE5
3СE6
4АC5

B) h4 =

c) h5 =

УX1X2X 3
3СE5
4АE5

D) h6 =

УX1X2X 3
2BE6
5СB2

3.

A)

R 3X1X2X3X4
X11101
X21101
X31110
X40111

B)

R 4X1X2X3X4
X11101
X20100
X30000
X40011

C)

R 3X1X2X3X4
X10000
X20001
X31010
X40100

D)

R 3X1X2X3X4
X10000
X21001
X31110
X40100

2. Задача 2

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

Відповідь:

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

.

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

.

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

.

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

3. Задача 3

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

Відповідь:

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

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

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

L13L15L14L12L23L45L34L35L24L25
88911121214151820

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

КрокРебра остовуВершини остову
L13L15L14L12X1X2X3X4X5
1100011000
2110011100
3111011110
4111111111
Lij88911L=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 і нулю на решті наборів.

Відповідь:

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

ДДНФ =x1 x2 x3 x4 Úx1 x2 x3 x4 Úx1 x2 x3 x4 Úx1 x2 x3 x4 Úx1 x2 x3 x4 Úx1 x2 x3 x4

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

1-2 x1 x2 x3

1-4 x2 x3 x4

2-4 x2 x3 x4

4-6 x1 x3 x4

5-6 x1 x2 x3

ДДНФ = x1 x2 x3 Úx2 x3 x4 Úx2 x3 x4 Úx1 x3 x4 Úx1 x2 x3 Úx1 x2 x3 x4

1-2 x2 x3

1-3 x2 x3

2-3 x2 x3

3-4 x3 x4

4-5 x1 x3

ДДНФ = x2 x3 Úx3 x4 Úx1 x3 Úx1 x2 x3 x4

ДДНФX1 x2 x3 x4X1 x2 x3 x4X1 x2 x3 x4X1 x2 x3 x4X1 x2 x3 x4X1 x2 x3 x4
X2 x3+++
X3 x4+++
X1 x3+++
X1 x2 x3 x4+

Отже,

MinДНФ = x1 x3 Úx2 x3 Úx1 x2 x3 x4

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

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

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

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

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

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


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