Багатофазне сортування

При використанні розглянутого вище методу збалансованого багатошляхового зовнішнього сортування на кожному кроці приблизно половина допоміжних файлів використовується для введення даних і приблизно стільки ж для виведення злитих серій. Ідея багатофазного сортування полягає у тому, що з наявних m допоміжних файлів (m-1) файл служить для введення злитих послідовностей, а один – для виведення утворених серій. Як тільки один з файлів введення стає порожнім, його починають використовувати для виведення серій, одержуваних при злитті серій нового набору (m-1) файлів. Отже є перший крок, при якому серії початкового файлу розподіляються по m-1 допоміжному файлу, а потім виконується багатошляхове злиття серій з (m-1) файлу, поки в одному з них не утвориться одна серія.

Очевидно, що при довільному початковому розподілі серій по допоміжним файлам алгоритм може не зійтися, оскільки в одному непорожньому файлі існуватиме більше, ніж одна серія. Припустимо, наприклад, що використовується три файли В1, В2 і В3, і при початковому розподілі у файл В1 вміщені 10 серій, а у файл В2 – 6. При злитті В1 і В2 до моменту, коли ми дійдемо до кінця В2, в В1 залишаться 4 серії, а у В3 потраплять 6 серій. Продовжиться злиття В1 і В3, і при завершенні перегляду В1 у В2 містимуться 4 серії, а у В3 залишаться 2 серії. Після злиття В2 і В3 в кожному із файлів В1 і В2 міститиметься по 2 серії, які зіллються і утворять 2 серії в В3 при тому, що В1 і В2 – порожні. Отже, алгоритм не зійшовся (таблиця 11).

Таблиця 11 – Приклад початкового розподілу серій, при якому трифазне зовнішнє сортування не приводить до потребного результату

К-ть серій у файлі В1	К-ть серій у файлі В2	К-ть серій у файлі В3

Оскільки кількість серій у початковому файлі може не забезпечувати можливість такого розподілу серій, застосовується метод додавання порожніх серій, які надалі якомога рівномірніше розподіляються між проміжними файлами і пізнаються при подальшому злитті. Зрозуміло, що чим менше таких порожніх серій, тобто чим ближча кількість початкових серій за вимогами Фібоначчі, тим ефективніше працює алгоритм.

Контрольні запитання

1. Поясніть особливості внутрішніх та зовнішніх методів сортування.

2. Назвіть методи внутрішнього сортування

3. Назвіть методи зовнішнього сортування.

4. Визначте алгоритмічну складність сортування методом Хоара.

5. Визначте алгоритмічну складінсть пірамідального сортування.

Тести для закріплення матеріалу

1. Назвати складові частини алгоритмів сортування

а) порівняння, що визначає впорядкованість пари елементів;

б) перестановка, що змінює місцями пари елементів;

в) пошук, який ставить найбільший елемент на початок;

г) власне алгоритм сортування, що здійснює порівняння і перестановку елементів доти, поки всі елементи множини не будуть впорядковані.

2. Перерахуйте методи внутрішнього сортування

а) включенням;

б) Шелла;

в) обмінне;

г) природне злиття;

д) багатофазне злиття;

е) пірамідальне;

є) вибором;

ж) поділом;

з) сортування деревом.

3. Перерахуйте методи зовнішнього сортування

а) включенням;

б) Шелла;

в) обмінне;

г) природне злиття;

д) багатофазне злиття;

е) пірамідальне;

є) вибором;

ж) поділом;

з) сортування деревом.

4. За фраґментом програми визначте метод сортування

for(i=1,i<=n-1;i++)

for(j=i+1;<=n;j++)

if(a[i]<a[j])

{

b=a[i];

a[i]=a[j];

a[j]=b;

}

а) бульбашки;

б) включення;

в) Шелла:

г) поділу.

5. За фраґментом програми визначте метод сортування

for(i=1,i<=n;i++)

for(j=i;<=n-1;j++)

if(a[i]<a[i+1])

{

b=a[i];

a[i]=a[i+1];

a[i+1]=b;

}

а) бульбашки;

б) включення:

в) Шелла;

г) поділу.

6. За фраґментом програми визначте її призначення

Type tree=^tr;

Tr=record;

k:integer; s:string; l,r:tree; end;

function mmm(k:integer;var d,res:tree):boolean;

var p,q:tree; b:boolean;

begin b:=false; p:=d;

if d<>nil then repeat q:=p; if р^.k=k then b:=true

else begin q:=p; if k<р^.k then р:=р^.l else p:=p^.r

end

until b or (p=nil); mmm:=b; res:=q;end;

а) видалення елемента з списку;

б) видалення елемента в дереві;

в) пошук елемента в списку;

г) пошук елемента в дереві.'

7. За фраґментом програми визначте метод сортування:

for(i=0;i<n;i++)

if(i<(int)n/2)

а1[і]=а[і];

else

a2[i-(int)n/2]=a[i];

for(i=0;i<(int)n/2;i++)

for(j=0;j<(int)n/2-1;j++)

if(a1[j]<a1[j+1])

{

tmp=a1[j];a1[j]=a1[j+1];a1[j+1]=tmp;

}

for(i=0;i<(int)n/2+n%2;i++)

for(j=0;j<(int)n/2+n%2-1;j++)

if(a2[j]<a2[j+1])

{

tmp=a2[j]; a[j]=a2[j+1]; a2[j+1]=tmp;

}

i=0;

while(i<n)

{

if ((k==(int)n/2)&&(l!=t))

{a[i]=a2[l]; i++;l++;continue;}

if ((k!=(int)n/2)&&(l==t))

{a[i]=a1[k]; i++;k++;continue;}

if(a2[j]<a1[k])

{a[i]=a1[k]; i++;k++;continue;}

if(a1[k]<a2[l])

{a[i]=a2[l]; i++;l++;continue;}

if(a2[l]==a1[k])

{a[i]=a1[k]; i++;k++; a[i]=a2[l]; i++; l++; continue;}

}

а) бінарний;

б) включення;

в) Шелла;

г) пірамідальний.

8. За фраґментом програми визначте метод сортування:

while (j<znach-1)

{

for (i=0;i<znach-1;i++)

if (strcmp(mas[i],mas[i+1])>0)

{

pidmin=mas[i];

mas[i]=mas[i+1];

mas[i+1]=pidmin;

}

j++;

}

а) бінарний;

б) включення;

в) Шелла;

г) поділу.

9. За фраґмєнтом програми визначте метод сортування:

for(i=0; i<rowArr; i++)

k[i]=0;

for(i=0; i<rowArr-1; i++)

{

for (j=i+1; j<rowArr; j++)

{

if (ar_s[i]<ar_s[j])

{

k[i]++;

}

else k[j]++;

}

}

for (i=0; i<rowArr; i++)

ar_s1[k[i]]=ar_s[i];

for (i=0; i<rowArr; i++)

ar_s[i]=ar_s1[i];

а) включення;

б) Шелла;

в) поділу;

г) підрахунку.

Контрольні питання

ЛЕКЦІЯ № 9

Тема: Класичні задачі комбінаторіки

Ціль: розглянути класичні задачі комбінаторіки та їх властивості

План

1 Комбінаторика як наука.

2 Задачі з комбінаторики.

3 Задачі на класичне означення ймовірності.

5 Задачі на застосування аксіом теорії ймовірностей

4 Задачі на операції з множинами

6 Задачі на умовні ймовірності і незалежні події

7 Випробування Бернуллі. Наближені формули для .

1 Комбінаторика як наука.

Комбінаторика – розділ математики, присвячений розв’язанню задач вибору і розміщення елементів деякої, зазвичай скінченної множини у відповідності з деякими правилами. Кожне таке правило визначає спосіб побудови деякої конструкції з елементів вихідної множини, яка називається комбінаторною конфігурацією. Тому можна сказати, що основними задачами комбінаторики є вивчення комбінаторних конфігурацій, питання про їх існування, алгоритми побудови, розв’язання задач на перелік. Прикладами комбінаторних конфігурацій є перестановки, розміщення та комбінації; блок-схеми та латинські квадрати.

Комбінаторика - один із традиційних розділів дискретної математики. Як розділ математики комбінаторика вивчає питання про те, скільки сполук, пов’язаних з тими або іншими умовами, можна утворити з даних об’єктів.

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

У XVI столітті в житті привілейованих людей тодішнього суспільства велике місце посідали азартні ігри. У карти й кості вигравалося і програвалося золото і діаманти, палаци й маєтки, породисті коні і дорогі прикраси. Були поширені всілякі лотереї. Спочатку комбінаторні задачі стосувалися, в основному, азартних ігор, наприклад, питань, скількома способами можна викинути дане число очок, кидаючи дві чи три кості, скількома способами можна одержати двох королів у картковій грі. Ці та інші проблеми азартних ігор були рушійною силою в розвитку комбінаторики і теорії ймовірностей.

Теоретичні дослідження з питань комбінаторики почали в XVII столітті французькі вчені Б. Паскаль (1623-1662) і П. Ферма (1601-1665). Вихідним пунктом їхніх досліджень також були проблеми азартних ігор.

Термін "комбінаторика" був уведений у математику німецьким вченим Г. Лейбніцем. У 1666 році Лейбніц опублікував роботу "Міркування про комбінаторне мистецтво". Комбінаторику він розумів дуже широко, як складову будь-якого дослідження, будь-якого творчого акту, що припускає спочатку аналіз (розчленовування цілого на частини), а потім синтез (з’єднання частин у ціле).

У 1713 році опубліковано роботу Я. Бернуллі (1654-1720) "Мистецтво припущень", у якій досить повно були викладені відомі на той час комбінаторні факти. Робота складалася із 4-х частин; комбінаториці була присвячена друга частина, у якій містяться формули: для числа перестановок з n елементів, для числа сполучень (названого Я. Бернуллі класовим числом), без повторень і з повторенням, для числа розміщень з повтореннями і без повторень.

У XX столітті завдяки роботам Дж.К. Рота (1964), а потім Р. Стенлі відбувається стрімкий процес алгебраїзації комбінаторики. Вивчення ними частково упорядкованих множин, властивостей функції Мебіуса, абстрактних властивостей лінійної залежності, виявлення їхньої ролі під час розв’язування комбінаторних задач сприяли збагаченню комбінаторних методів дослідження і подальшої інтеграції комбінаторики в сучасну математику.

Проблема вивчення комбінаторики в школі активно досліджувалась в період 1970-1980 рр. Розглядалися різні методичні моделі, але напрямок більшості досліджень характеризується тим, що комбінаториці в них відводиться допоміжна роль: вивчення її підпорядковано меті вивчення початків теорії ймовірностей. Однак, оскільки сьогодні комбінаторика має дуже широку сферу застосувань, то цей розділ сучасної математики набуває самостійного значення. Отже, існує потреба в дослідженнях та пошуках більш досконалих підходів до вивчення комбінаторики з урахуванням досвіду, зокрема й досвіду вивчення комбінаторики у вищій школі.

На жаль, у 80-90 роки комбінаторика до програми основного курсу математики не ввійшла і була винесена на факультативні заняття. Але розвиток дискретної математики, її багатогранні зв’язки з іншими галузями науки і безпосередньо з виробництвом вплинули і на нові підходи до відбору змісту шкільної математичної освіти. Цій проблемі велику увагу приділяють провідні математики та методисти: А. Блох, Н. Віленкін, Б. Гнєденко, О. Дубинчук, А. Колмогоров, А. Маркушевич, З. Слєпкань, О.Хінчін, М. Ядренко та інші. Більш того, як зазначав І.Яглом, “...нова математика, в силу свого скінченого характеру, значно доступніша для початківців, ніж класичний математичний аналіз; вона скоріше може зацікавити тих, хто навчається, викличе менше труднощів і тому більше підходить для викладання навіть на ранніх стадіях навчання”.

Отже, сьогодні розділи математики, в яких не використовуються уявлення про нескінченні множини, границі й неперервність, стали тепер більш змістовними і важливими, ніж це думали математики ХІХ століття або першої половини ХХ століття. Якщо, починаючи з ХVІІ століття, панівне положення у математиці займало вивчення неперервних функцій, що було основою всіх застосувань математики у фізиці і техніці, то з середини ХХ століття почалося відродження інтересу до так званої “до-ньютонівської” або скінченної математики, яка оперує лише скінченними множинами і функціями, які визначені на таких множинах.

2 Задачі з комбінаторики.

В подальшому вам часто знадобиться вміння підраховувати кількість способів, варіантів (ще можна сказати - різних наслідків, результатів) настання певної події або виконання деякої дії. Наприклад: скільки є різних початкових положень при грі в преферанс? Скільки є різних способів освітлення кімнати, якщо в ній розміщені 5 світильників, кожний з яких можна ввімкнути та вимкнути незалежно від інших?

Найголовніше правило, яке "працює" при розв’язанні подібних задач - це так зване правило добутку; ще його називають основним принципом комбінаторики. Сформулюємо та пояснимо його спочатку в більш простому вигляді, одночасно з правилом суми; потім - у більш загальному.

Правила суми та добутку. Якщо вибрати елемент A можна m способами, а В - n способами, то вибір "А або В" можна здійснити m+n способами, а "А і В" - mn способами.

Приклад. Якщо ви бачите в аудиторії 3 дівчини та 5 юнаків, то вибрати дівчину (одну) можна, звичайно, трьома способами, а юнака - п’ятьма. Вибір "дівчину або юнака", тобто довільну особу з присутніх, можна здійснити 3+5=8 способами, бо цих присутніх саме стільки. Вибрати ж дівчину та юнака можливо саме 3´5=15 різними способами. Справді. для кожної з трьох різних дівчат може бути вибраний ще будь-який з п’яти юнаків. Отже, способів 5+5+5= 5´3=15.

Основний принцип комбінаторики. (загальне формулювання). Нехай певну дію (наприклад, вибір) можна виконати за k послідовних кроків, і два способи виконання є різними, якщо хоч на одному кроці вони відрізняються. Якщо кількості способів, якими можна виконати перший, другий, …, k-й етапи відповідно дорівнюють n₁, n₂, …, n_k і не залежать від того, як виконувались попередні етапи, то кількість різних способів виконання всієї дії дорівнює добутку n₁´ n₂´ … ´ n_k.

Проілюструємо дію основного принципу комбінаторики (далі - ОПК) на кількох важливих прикладах.

Приклад 2. Підрахуйте кількість різних результатів, які можна отримати, підкинувши монету три рази (з точки зору того, яким боком вона падала).

éСпосіб 1. Ці результати можна просто виписати: ГГГ, ГГР (цей результат означає, що спочатку монета двічі впала гербом, а потім - решкою), ГРГ, ГРР, РГГ, РГР, РРГ, РРР. Всього 8 різних.

Спосіб 2. Одержати певний результат трикратного кидання монети, можна, послідовно розглядаючи можливості при першому, другому та третьому киданні. На мові вище розглянутих послідовностей з трьох літер це означає: записати таку послідовність (і повністю визначити цим один окремий результат) можна, вибравши спочатку першу літеру, потім другу, потім третю. Для кожного кроку маємо 2 можливості, тобто 2 способи - Г або Р. Всього за ОПК способів 2´2´2=8.

Зауваження 1. Хоч у задачі цього явно не сказано, ми враховували послідовність випадання гербів та решок. Інакше результатів було б всього чотири: три герби, два герби і одна решка, один герб і дві решки, три решки. Таких способів підрахунку ми будемо уникати з-за того, що тут різні результати не є рівноможливими: порівнявши з попередніми міркуваннями, бачимо, що "два герби і одна решка" втричі можливіше за "три герби".

Зауваження 2. Міркуючи аналогічно до способу 2, приходимо до формули для кількості так званих розміщень з повтореннями, тобто впорядкованих послідовностей з k елементів, кожний з яких може бути будь-яким з даної множини, в якій n різних елементів:

Згідно з назвою, тут елементи в послідовності можуть повторюватись. Якщо ж поставити вимогу, щоб цього не було, тобто щоб усі k елементів були різні, то вийде формула для розміщень без повторень з n елементів по k:

Справді, для першого елемента послідовності маємо n способів вибору, для другого n-1 (якщо вже вибраний перший, то другий не може з ним співпадати) і т.д. У випадку, коли розміщуємо в деякому порядку k різних елементів, маємо розміщення без повторень з k елементів по k, або, простіше перестановку з k елементів. Кількість таких перестановок рахується аналогічно з застосуванням ОПК.

Одержані нами формули дуже корисні, тому що в багатьох задачах вибір способу дії фактично зводиться до вибору розміщення, або перестановки, або так званої комбінації з n елементів по k. Це будь-яка підмножина з k елементів даної n - елементної множини. Формула для кількості таких комбінацій:

.

Вона виведена в курсі лекцій, як і формула для кількості перестановок з повтореннями (коли переставляють n елементів, з яких деякі однакові, а саме n₁ однакових одного типу, n₂ - другого, …, n_л - k - го, де n₁+ n₂+…+ n_л=n)

.

Розглянемо застосування даних понять в прикладах.

Приклад 3. На станції є п’ять світлофорів,кожний з яких може показувати червоне, жовте або зелене світло (не горіти вони не можуть). Скільки є різних варіантів подання сигналів цими світлофорами?

é Спосіб 1. Перенумеруємо світлофори і кожний варіант задаватимемо послідовністю з п’яти символів, кожний з яких Ч, Ж, З. Маємо розміщення (з повтореннями) з трьох елементів по п’ять. Їх кількість

Спосіб 2. Для першого світлофора 3 варіанти сигналу, для другого, третього і т.д. - теж. Оскільки нам треба вибрати і сигнал першого, і другого,…, і п’ятого, то діє правило добутку: 3´3´3´3´3=243. û

Приклад 4. Три рази кидають гральний кубик. Скільки може бути різних наслідків при цьому? В скількох з них є хоч одна "шістка"? Рівно одна шістка, а два інші результати однакові?

éЗа правилом добутку або за формулою кількість всіх способів 6´6´6=216. Щоб знайти відповідь на наступне питання, застосуємо так званий прийом "знаходження доповнення". Запитаємо себе, що собою уявляє "решта" варіантів? Це варіанти, де нема жодної шісткі, тобто могли випадати тільки грані 1, 2, 3, 4, 5. Але ж їх тоді легко порахувати: за тим же правилом добутку їх кількість 5´5´5=125. Тоді тих наслідків, де є хоч одна "шістка", 216-125=91.

Щоб відповісти на останнє запитання, уявимо собі, що ми вибираємо, тобто визначаємо потрібний нам варіант, за такі кроки: 1) вибираємо, яка ще грань буде випадати, крім шістки;

2) розставляємо у певному порядку три відомі грані, з яких дві однакові. На першому кроці способів, очевидно, 5, на другому 3 (це можна встановити багатьма способами: наприклад, взагалі за формулою P₃(2,1)).

Оскільки цим варіант визначається однозначно, то маємо відповідь за ОПК 5´3=15. û

Зауваження. Як правило, як тільки в умові задачі зустрічається зворот "хоча б одна", треба відразу застосовувати прийом "знаходження доповнення".

Приклад 5. Тринадцять осіб сідають в поїзд метро з чотирьох вагонів. В два вагони повинно сісти по 4 пасажири, ще в один - три і ще в один - решта двоє. Скільки є різних способів такого їх розташування?

é Не так просто вибрати спосіб міркування для цієї задачі. "Розкручувати" її будемо поступово, за кілька послідовних кроків:

1) вибираємо, в які саме вагони сядуть по 4 пасажири (, а не , бо порядок вибору не має значення);

2) з решти двох вагонів вибираємо ще, наприклад, той куди сядуть троє (способів 2= ). Тепер нам відомо, в який вагон скільки пасажирів сяде. Починаємо їх розміщувати:

3) вибираємо 4 пасажири для одного з вагонів, де їх буде саме стільки: способів .

4), 5), 6) аналогічно: способів , .

За основним принципом комбінаторики відповідь: .

Зауваження. В цій задачі не можна було б міркувати так: 1) виберемо, куди сяде перший пасажир - 4 способи; 2) …. Основний принцип комбінаторики тут не спрацював би, бо кількість способів для наступних етапів була б різною в залежності від того, як виконано попередні.

3 Задачі на класичне означення ймовірності.

Якщо в умові задачі є слово "ймовірність", це вже не комбінаторна задача; але швидше за все комбінаторика знадобиться. Перше, що потрібно зробити - з’ясувати для себе, в чому полягає так званий стохастичний експеримент задачі. Як правило, він описаний на початку умови і результат його неможливо взнати заздалегідь. Після цього потрібно визначити, якими можуть бути результати експерименту і як їх можна задати (наприклад, у вигляді розміщень або комбінацій символів, щоб зручно було застосовувати комбінаторику), причому вони всі повинні бути однаково можливими. Тепер треба визначити загальну можливу кількість N результатів, або наслідків, а також скільки з них (K) є спиятливими для даної події А. Тут і буде корисною комбінаторика. Залишається поділити друге число на перше: .

Приклад 6. В групі 10 білявих та 15 чорнявих студентів. Навгад за списком вибирають двох. Яка ймовірність того, що з вибраних студентів один білявий та один чорнявий?

é Експеримент - відбір двох студентів з 25, кількість рівноможливих результатів . Сприятливих буде , тому що потрібно вибрати для цього одного білявого й одного чорнявого.

Відповідь: . û

Приклад 7. В групі k студентів. Знайдіть ймовірність того, що якісь дні народження збігаються.

é Стохастичний експеримент задачі доводиться будувати самим, наприклад, як з’ясування днів народження першого, другого, …, k -го студента за списком. Способів маємо (29 лютого не враховується для спрощення). Кількість способів, коли якісь дні народження збігаються, безпосередньо порахувати важко; наприклад, правило добутку тут застосувати неможливо (переконайтесь у цьому). Застосуємо прийом "доповнення": решта варіантів - це ті, в яких всі дні народження різні, і їх . Тому відповідь .

Цікаво, що вже при k=23 , в що важко повірити недосвідченій людині. Спробуйте перевірити, що у випадковій аудиторії більше ніж з 23 осіб ймовірність співпадання днів народження досить велика, більша за 50%.

4 Задачі на операції з множинами

З кожним стохастичним експериментом пов’язують простір елементарних подій W - сукупність можливих наслідків експерименту. Всі випадкові події, пов’язані з даним стохастичним експериментом - підмножини в W (тобто деякі набори можливих результатів). Тому теорія ймовірностей і теорія множин мають багато спільного: втім, вони говорять одне і те ж різними словами, що видно з такої таблиці:

Теорія множин	Теорія ймовірностей
W - універсальна множина	W - простір елементарних подій
W	W є достовірна подія, тобто така, що відбувається при кожному здійсненні експерименту
Æ (порожня множина)	Æ - неможлива подія, тобто така, яка не відбувається при будь якому здійсненні експерименту
АÌ В	З події А випливає подія В
АÈ В, або А+В	АÈ В, або А+В - подія, яка полягає в тому, що відбувається принаймі одна з подій А або В
АÇ В, або А×В	АÇ В, або А×В – подія, яка полягає в здійсненні і А, і В
(доповнення до )	- протилежна подія до - подія, яка полягає в тому, що не відбувається
АÇ В=Æ (А і В - множини, що не перетинаються)	АÇ В=Æ - події А і В несумісні
А\ В (різниця множин А і В)	А\ В -різниця множин А і В - подія, яка полягає в тому, що відбудеться А і не відбудеться В.

Приклад 8. Нехай А, В і С - довільні події. Що означають наступні події:

?

é Перша подія, очевидно, означає, що в результаті проведення стохастичного експерименту подія А не відбулася, а В і С - відбулись. Друга подія означає, що і А, і В, і С не відбулись, іншими словами - жодна. Третя подія означає, що хоча б одна з подій А, В і С не відбулась, інакше кажучи – не всі відбулись; четверта - що відбулась рівно одна з подій А, В, С, а дві інші не відбулись; п’яту подію можна виразити так: не відбулось не менше двох подій з А, В і С, або, що те ж саме, відбулось не більше однієї з цих подій. û

Приклад 9. Гральний кубик підкидають двічі. Описати простір елементарних подій. Описати події: А - сума очок, які з’явились, дорівнює 8; В - принаймі один раз з’явилось 6 очок. Що собою являє подія А Ç В?

é Простір елементарних подій, або сукупність можливих наслідків експерименту, очевидно, можемо записати як набір усіх можливих впорядкованих пар чисел від 1 до 6 (перше число в парі - те, що випало при першому киданні кубика, друге - при другому). Отже,

W={ (1;1); (1;2); (1;3); …; (6;5); (6;6) }. Всього, очевидно, 36 різних елементів. Подію А задаємо перерахуванням елементів, які її складають:

А={сума очок дорівнює 8}={ (2,6); (3,5); (4,4); (5,3); (6,2) }.

Аналогічно В={ (6,1); (6,2); (6,3); (6,4); (6,5); (6,6); (1,6); (2,6); (3,6); (4,6); (5,6) }.

Подія АВ складається з двох елементів, які входять і в А, і в В: АВ={(2,6); (6,2)}.

Це можна було б з’ясувати і безпосередньо з умови задачі: якщо здійснилась і подія А, і подія В, то на одному кубику повинно бути 6 очок, а на іншому, відповідно, 8-6=2.

5 Задачі на застосування аксіом теорії ймовірностей

Коли виникла необхідність втиснути в рамки логічної і стрункої схеми теорію ймовірностей (до того вона базувалась більше на інтуітивних міркуваннях), А.Н. Колмогоровим було введено систему з 6 аксіом. Їх повинні були задовольняти такі об’єкти: Ω (простір елементарних наслідків), Р (ймовірність). Оскільки виявилось, що не можна усяку підмножину з Ω вважати випадковою подією, було введено окремо набір випадкових подій F. Тобто, "Ає F " еквівалентно "А-випадкова подія".

Пояснити суть аксіом можна так. Перші три аксіоми означають, що набір F повинен задовольняти елементарні вимоги:1) все Ω є випадковою подією; 2) якщо якась підмножина з Ω входить в F, тобто А- випадкова подія, то "А не здійснилась" теж випадкова подія, тобто ; 3) якщо А₁, А₂, … - випадкові події, то є випадковою подія " здійснилась хоча б одна з подій А₁, А₂, …".

Друга група з трьох аксіом відноситься до поняття ймовірності: вони повністю узгоджуються з класичним та частотним означеннями ймовірності. Якщо вважати, що ймовірність події А –це число, що дорівнює її середній частоті за багато повторень експерименту, то аксіоми говорять: 1) це число невід’ємне і визначене для кожної випадкової події А (тобто Ає F); 2) середня частота Ω (достовірної події) дорівнює 1; 3) якщо події А₁, А₂, … є несумісними, то середня частота їх об’єднання дорівнює сумі середніх частот. Дійсно, оскільки несумісні події можуть відбуватися тільки по одній, то відповідні кількості треба просумувати.

Шість аксіом теорії ймовірностей становлять її міцну базу. Їх застосовують при розв’язанні багатьох задач.

Приклад 10 Довести, що якщо А і В – випадкові події, то і - випадкова подія і Р()=Р(А)+Р(В)-Р().

Переформулюємо перше наше завдання так: якщо Ає F і ВєF, то є F. В аксіомах цього прямо не записано, але це не важко довести. Справді, , тобто . Оскільки Ає F і ВєF, то і (аксіома 2), тоді (аксіома 3), і звідси (знову аксіома 2), що й потрібно було довести.

Далі, подію можна подати як об’єднання трьох несумісних подій: “ А відбувається, В ні “, “ В відбувається, А ні “, “відбуваються і А, і В “, тобто

, і аналогічно

, .

Застосовуємо аксіому 6:

,

,

.

З цих рівностей неважко одержати потрібну формулу.

Приклад 11. Нехай А і В – випадкові події, Р₀ – ймовірність того, що не відбудеться жодна з них, Р₁ – що відбудеться рівно одна, Р₂ –що відбудуться обидві. Виразити Р₀, Р₁, Р₂ через Р(А), Р(В), .

Очевидно, Р₂= . Далі, доповненням до події є подія , ймовірність якої є шукана Р₀, тобто 1-Р()=Р₀ і з попередньої задачі Р()=Р(А)+Р(В)-Р(); отже, Р₀=1-Р(А)-Р(В)+ .

Знаючи тепер Р₀ і Р₂, можна легко знайти Р₁; справді, сума Р₀+Р₁+Р₂ повинна дорівнювати одиниці як сума ймовірностей трьох несумісних подій, об’єднання яких є W; отже, .

6 Задачі на умовні ймовірності і незалежні події

Умовною ймовірністю події А відносно події В називають число

, при Р(В)¹0.

Щоб знайти його, отже, треба з’ясувати, що являє собою подія , знайти ймовірності її та події В і поділити.

Умовну ймовірність можна розуміти так: є інформація про те, що в результаті експерименту подія В відбулась. Яка за цієї умови ймовірність події А? Це і є Р(А/В).

В задачах часто застосовують очевидну формулу

та її узагальнення .

Далі, якщо ймовірність події А залишається незмінною, чи береться вона при умові В, чи без такої умови, то природно називати А незалежною від В. Так буде, якщо виконуватиметься рівність ;

Видно, що й В тоді незалежна від А; коротко кажуть, що А і В незалежні. Аналогічно визначається незалежність кількох подій, а саме: події А₁,А₂, …, А_n називаються незалежними в сукупності, якщо ймовірність перетину будь-якого числа з них дорівнює добутку відповідних ймовірностей: . Зауважимо, що для такої незалежності недостатньо попарної незалежності подій.

Приклад 12. Підкидають два гральні кубики. Знайти ймовірність того, що випаде хоч раз 6 очок, якщо відомо, що сума очок, що випали, не менша за 9.

Конструкція "ймовірність…якщо відомо…", або інакше: "ймовірність … за умови, що…" ясно вказує на умовну ймовірність. Очевидно, потрібно знайти Р(А/В), де А – подія "випаде хоч раз 6 очок", В – "сума не менша за 9".

В прикладі 9 ми вже з’ясували, який стохастичний експеримент, і знайшли кількість (36) рівноможливих наслідків, що складають Ω. З цих результатів подія А є об’єднання рівно одинадцяти: (6,1); (6,2); …; (6,6); (1,6);…; (5,6), а подія В – восьми: (4,5); (5,4); (4,6); (5,5); (6,4); (5,6); (6,5); (6,6).

Подія складається з п’яти випадків, що входять і в А, і в В: (4,6); (6,4); (5,6); (6,5); (6,6). Отже, .

Приклад 13. З урни, що містить білих та чорних куль, послідовно виймають дві кулі (без повернення). Знайти ймовірність того, що друга куля біла, якщо відомо, що перша куля біла.

Нам потрібно знайти Р(А/В), де А є подія "друга куля біла", В – подія "перша куля біла".

7 Випробування Бернуллі. Наближені формули для .

На практиці часто зустрічаються ситуації, які можна розглядати як проведення певної кількості n окремих експериментів (випробувань), які є незалежними і в результаті кожного з яких певна подія (“успіх”) може статись з однією і тією ж ймовірністю p. Такі випробування прийнято називати випробуваннями Бернуллі.

Приклад: Сподіваючись на приз від компанії “Кока-кола”, ви протягом року кожного тижня купуєте по пляшці цього напою. В середньому кожна двохсота пляшка має кришечку зі знаком призу.

В даному випадку n =?, p =?

В лекціях виведено формулу для ймовірності того, що в даній серії з n випробувань Бернуллі відбудеться рівно k успіхів:

Якщо n та k великі, можна використовувати наближені формули:

локальну Муавра-Лапласа

, - щільність стандартного нормального розподілу, а - ймовірність “неуспіху”;

інтегральну Муавра-Лапласа

,

де , для формула аналогічна, а значення функції Лапласа беруться з таблиць;

формулу Пуассона (для малих p)

, де .

Вправа: Які з цих формул можна застосувати до попереднього прикладу, щоб обчислити ймовірність того, що вам жодного разу не пощастить? Зробіть це і порівняйте результати.

Контрольні питання

1 Комбінаторика.

2 Задачі з комбінаторики.

3 Задачі на класичне означення ймовірності.

5 Задачі на застосування аксіом теорії ймовірностей

4 Задачі на операції з множинами

6 Задачі на умовні ймовірності і незалежні події

7 Випробування Бернуллі.

8 Наближені формули для .

ПЕРЕЛІК ЛІТЕРАТУРИ

1. Котов В.М., Пилипчук Л.А., Соболевская Е.П. Теория алгоритмов. Ч.1. - Мн.: БГУ. 2001. - 192 с.

2. Котов В.М., Соболевская Е.П. Структуры данных и алгоритмы: теория и практика. - Мн.: БГУ. 2004. - 252 с.

3. Окулов С. М. Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2004. — 341 с: ил.

4. Шаховська Н.Б., Р.О. Голощук «Алгоритми і структури даних», посібник, під редакцією д.т.н., професора В.В. Пасічника. «Магнолія 2006», Львів, 2010. – 215 с.

5. Ахо Альфред В., Хопкрофт Джон Э., Ульман Джеффри Д. Построение и анализ вычислительных алгоритмов. - М.: Мир,1979. - 536 c.

6. Ахо Альфред В., Хопкрофт Джон Э., Ульман Джеффри Д. Структуры данных и алгоритмы. - М.: Издательский дом “Вильямс”, 2000. - 384 c.

7. Ковалев М.Я., Котов В.М.,Лепин В.В. Теория алгоритмов. Часть 2. Приближенные алгоритмы. – Мн.: БГУ, 2003. – 147 с.

8. Кормен Т., Лейзерсон Ч., Ривест Р.. Алгоритмы: построение и анализ. - М.: МЦНМО, 1999. - 960 с., 263 ил.