Задачі для самостійної роботи студентів
Задача 1. Програти алгоритм генерації всіх підмножин для n=4.
Задача 2. Довести:
( A + B ) A = ( A B ) +A = A
A - ( B + C ) = ( A - B ) ( A - C )
A - ( B C ) = ( A - B ) + ( A - C )
A - ( A - B ) = A B
(A - B) - C = (A - C) - (B - C)
А ∆ ( А ∆ В ) = В
Задача
3. Спростити:
Задача
4. Дано:
,
Знайти:
а)
б)
Задача 5. Для множини А=(1,2,......10), з властивостями:
р1: аА
р2: аА, а>0
p2: aA, 2<a<8
визначити число елементів А, відповідаючих р1р2р3.
Контрольні питання
Дати визначення декартового множення.
Які множини називають еквівалентними?
Дати визначення симетричної різниці.
Лабораторна робота №3
Тема роботи: Комбінаторика.
Мета роботи: Вивчення основних способів рішення комбінаторних задач.
Теоретичні відомості
Комбінаторика — розділ математики, присвячений розв’язанню задач вибору та розташування елементів деякої, зазвичай скінченої множини відповідно до заданих правил. Кожне таке правило визначає спосіб побудови деякої конструкції із елементів вихідної множини, що зветься комбінаторною конфігурацією. Тому метою комбінаторики є дослідження комбінаторних комбінацій, алгоритмів їх побудови, оптимізація таких алгоритмів, а також розв’язання задач переліку. Найпростішими прикладами комбінаторних конфігурацій є перестановки, розміщення та сполучення.
В основі розв’язування багатьох комбінаторних задач лежать два основних правила – правило суми і правило добутку.
|
|
|
При рішенні комбінаторних задач часто необхідно виконати кілька етапів складного вибору, коли використовується як правило суми, так і правило добутку. Наприклад: Нехай мається чотири (HDD, FDD, CDROM, FLASH) різних носії для завантаження операційної системи. Необхідно забезпечити завантаження з не менш чим 2-х носіїв. Скільки різних способів можна застосувати, якщо порядок завантаження враховується? Варіант завантаження може складатися або з 2-х носіїв, або з 3-х, або з 4-х носіїв. Нехай N – загальне число способів, що складаються не менш ніж з 2 носіїв; N2 – число варіантів, що складаються рівно з 2 носіїв; N3 – рівно з 3 носіїв, N4 – рівно з 4 носіїв. За правилом суми маємо:
N= N2 +N3 +N4.
N2, N3 , N4 знаходимо за правилом добутку :
N2=3*2=6;
N3=3*2*1=6.
N4=4*3*2*1=24
У підсумку : N=36.
Перестановка - упорядкована вибірка n елементів кінцевої множини, у якій всі елементи різні. Кожному елементу перестановки поставлено у відповідність визначене натуральне число - номер елемента. У загальному випадку перестановка n-елементної множини позначається таким чином: S=(S1,..., Si,...,Sn), де Si - елемент вихідної множини, розташований у i-й позиції перестановки. Кінцеву множину з n елементів можна упорядкувати n! різними способами, одержавши n! перестановок, які відрізняються тільки порядком елементів.
Наприклад:
Для множини з 3-х елементів: {a, b, c}можна побудувати 3!(= 6) перестановок: (a, b, c); (a, c, b); (b, a, c); (b, c, a); (c, a, b); (c, b, a).
Приведемо алгоритми генерації перестановок. Перестановка n-елементної множині X з іншого погляду — взаємно однозначна функція f: X→X. Якщо прийняти X = {1, …, n}, тоді перестановка - упорядкований набір з n різних чисел, що лежать у проміжку від 1 до n. Позначимо множину усіх перестановок множини X через Sn. |Sn| = n!. Нехай кожне Mi буде являти собою множину чисел від 0 до i−1. Позначимо через Tn добуток n таких множин. Тоді якщо буде існувати взаімнооднозначна відповідність між Sn і Tn, можна перенумерувати всі перестановки Sn. Визначимо механізм переходу від перестановки r1, …, rn Sn до елемента t1, …, tn Tn... Для будь-якого i 1:n знайдемо номер позиції s значення i у перестановці (rs = i), і приймемо в якості ti кількість елементів менших i серед r1, …, rs−1... А при зворотному переході від елемента до перестановки, використовувати те, що місце будь-якого елемента i (починаючи з найбільшого) на одиницю більше, ніж число елементів, що перед i, а саме це число дорівнює сумі ti і числа елементів, більших i.
Елементи перестановки будемо запам'ятовувати у виді елементів масиву P[1], …, P[n]... Обмін значеннями перемінних будемо позначати через P[i] <-> P[j]. Ми розглядаємо тільки перестановки, задані на множині X = {1, …, n}.
На множині Sn задамо лексикографічний порядок:
(x1, …, xn) < (y1, …, yn) якщо існує k ≥ 1, таке що xk ≤ yk і xl = yl для кожного l < k.
Аналогічно задається антілексiкографічний порядок:
(x1, …, xn) < (y1, …, yn) якщо існує k ≤ n, таке що xk > yk і xl = yl для кожного l > k.
Рекурсивний алгоритм генерації всіх перестановок в анти лексикографічному порядку.
procedure REVERSE(m);
begin i := 1; j := m;
while i < j do
begin
P[i] :=: P[j];
i := i + 1;
j := j - 1;
end
end
procedure ANTYLEX(m);
begin
if m = 1 then
write(P[1], …, P[n])
else
for i := 1 to m do
begin ANTYLEX(m − 1);
if i < m m then
begin
P[i] :=: P[m];
REVERSE(m − 1)
end
end
end;
begin
for i := 1 to n do P[i] :=: i;
ANTYLEX(n)
end
Більш швидкий алгоритм, у якому кожна наступна перестановка утвориться з попередньої за допомогою тільки однієї транспозиції має вигляд:
procedure B(m, i);
begin
if (m mod 2 = 0) and (m > 2) then
if i < m − 1 then B := i
else B := m − 2
else B := m − 1
end;
procedure PERM(m);
begin
if m = 1 then
write(P[1], …, P[n])
else
for i := 1 to m do
begin PERM(m − 1);
if i < m then P[B(m, i)] :=: P[m]
end
end;
begin
for i := 1 to n do P[i] :=: i;
PERM(n)
end
Останній алгоритм генерування перестановок, будує послідовність перестановок, у якій кожна наступна утворюється з попередньої за допомогою однократної транспозиції сусідніх елементів. Позначимо через PR[i] булеву змінну, визначаючу інформацію про те, переноситься елемент i вперед (PR[i] = true) чи назад. Змінна C[i] буде показувати, яку з можливих n−i+1 позицій елемент i займає щодо елементів i+1, …, n на своєму шляху вперед та назад. Нижче наведений код цього алгоритму:
begin
for i := 1 to n do
begin P[i] := i; C[i] := 1; PR[i] := true;
end;
C[n] := 0;
write(P[1], …, P[n]);
i := 1;
while i < n do
begin i := 1; x := 0;
while C[i] = n − i + 1 do
begin PR[i] := not PR[i]; C[i] := 1;
if PR[i] then x := x + 1;
i := i + 1;
end;
if i < n then
begin
if PR[i] then k := C[i] + x;
else k := n − i + 1 − C[i] + x;
P[k] :=: P[k + 1];
write(P[1], …, P[n]);
C[i] := C[i] + 1
end
end
end
Якщо множина А, складається з n елементів, і n1 елементів належить першому типу; n2 елементів належить другому типу, nk - k-тому типу елементів. Елементи одного и того ж типу однакові між собою. Тоді кількість перестановок з повтореннями визначається:
,
де
.
Розміщення
з n
елементів по m —
це упорядкований ( ! порядок) набір з m
різних чисел, що лежать у проміжку від
1 до n
( X).
Різні розміщення відрізняються складом
або порядком елементів. Позначимо число
його елементів через An,m
.
При m = n,
.
Наприклад:
1) Нехай A={а,в,с}. Згенеруємо усі розміщення з 3 по 2: {ав, ва, ас, са, вс, св}.
2) Компілятор
з мови програмування GPSS розпізнає чотири
перших символи у операторі. Скільки
можна получити операторів в алфавіті
{A,B,C,D,E}. З урахуванням того, що порядок
символів у операторі має значення,
.
Розміщення з повторенням. Якщо А = {a1, a2,…, an} , де a1, a2,…, an - “представники” 1-го, 2-го, … n-го типу елементів. Елементів кажного типу необмежена кількість і елементи одного типу однакові. Вибираемо елемент на 1 місто, це можна зробити n варіантами. Після цього елемент повертається і може бути выбраним ще, т.ч. на 2-е місто є n кандидатів и т.д. На m - е місто також є n кандидатів. Число різних разміщень з повтореннями із n по m дорівнює:
.
Наприклад:
Скільки різних сигналів можуть дати 4
розряди одночасно? Кількість різних
сигналів у одному розряді дорівнює 2.
Різні розряди можуть давати однакові
сигнали. Тоді, Х - кількість різних
сигналів, дорівнює числу розміщень з
повтореннями з 2 по 4:
.
Сполучення з n елементів по m - це неупорядкований набір (множина) з m різних елементів, що належать множині X. Позначимо число елементів множини сполучень через Cn,m. Оскільки сполучення є неупорядкований набір, то кожному такому набору відповідає m! розміщень (тобто упорядкованих наборів тих же елементів). Тоді одержимо, що
.
Приклад:
Нехай A={а,в,с}. Генеруємо усі сполучення із 3 по 2: {ав, ас, вс}.
Деякі властивості сполучень:
Cn,m = Cn,n−m
Cn,m + Cn,m+1 = Cn+1,m+1
Cn,m * Cm,k = Cn,k * Cn−k,m−k
;
;
Ці властивості випливають із самих визначень і перевіряються безпосередньо.
Приведемо алгоритм генерації сполучень у лексикографічному порядку:
begin
for i := 1 to k do A[i] := i;
p := k;
while p ≤ 1 do
begin write(A[1], …, A[k]);
if A[k] = n then p := p − 1 else p := k;
if p ≥ 1 then
for i := k downto p do A[i] := A[p] + i − p + 1
end
end
Нумерацію сполучень можна організувати, використовуючи властивість 2 сполучення. Для цього з кожним сполученням з n по m зв'яжемо вектор з n нулів і одиниць. У цьому векторі буде m одиниць, а числа сполучення будуть задавати номери цих одиниць. Тоді такому вектору можна зіставити траєкторію, у якій одиницям відповідають горизонтальні кроки, а нулям — вертикальні. Тоді формула для номера буде мати вид:
num(b[1:n], m) = { якщо b[n] = 0, то num(b[1:n−1], m);
якщо b[n] = 1, то n−1,m + num(b[1:n−1], m−1)},
де b[1:n] — 0-1 вектор з n елементів.
Сполучення з повтореннями. Якщо А = {a1, a2,…, an} , де a1, a2,…, an - “представники” 1-го, 2-го, … n-го типу елементів. Елементів кожного типу необмежена кількість і елементи одного типу однакові. Сполучення с повтореннями відрізняються составом елементів, включених у вибрану множину. Порядок елементів не має значення. Має значення, скільки елементів кожного типу у сполученні.
