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

Рефераты по математике » Прикладне вживання методів дискретної математики

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

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

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

м. Бердичів 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=(h1h2);

h4=(h1h2);

h5=(h1h2);

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=(h1h2).

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

r
3=(r1r2);

r4=(r1r2);

r5=(r1r2).

r6=(r1r2).

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

Відповідь:

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

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

A = ST = {b}; B = TS = {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}}.

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

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

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

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

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

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

Відповідь:

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

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

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

L13	L15	L14	L12	L23	L45	L34	L35	L24	L25
8	8	9	11	12	12	14	15	18	20

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

Крок	Ребра остову				Вершини остову
Крок	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

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

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

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

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

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