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

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

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

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

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

м.Бердичів 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. Дані відображення h¹ і h² , що представляють множину сумісних кортежів. Знайти:

a) h³ =(h¹ Èh² );

b) h⁴ =(h¹ Çh² );

c) h⁵ =(h¹ \h² );

d) h⁶ =(h¹ Dh² ).

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

a) r³ =(r¹ Èr² );

b) r⁴ =(r¹ Çr² );

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

d) r⁶ =(r¹ Dr² ).

Відповідь:

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) h³ =

b) h⁴ =

d) h⁶ =

3.

a)

b)

c)

d)

2. Задача 2

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

Відповідь:

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

.

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

.

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

.

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

3. Задача 3

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

Відповідь:

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

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

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

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

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

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

А₀ = Р₀ =

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

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₄

Отже,

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

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

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

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

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

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

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