з дисципліни

МЕТОДИЧНІ ВКАЗІВКИ

Для виконання практичних робіт

з дисципліни

„Дискретна математика”

для спеціальності

5.05010201 „Обслуговування комп’ютерних систем і мереж”

Розглянуто та схвалено

на засіданні циклової комісії

інформатики та

комп’ютерних дисциплін

Голова циклової комісії

__________ Р. В. Твердохліб

Протокол № _____

від „___” __________ 2010 р.

Розробив викладач НРПК

____________ І. Я. Кулик

2010 р.

Зміст

ВСТУП ........................................................................................................... 3 ст.

ПРАКТИЧНА РОБОТА №1

Виконання операцій над множинами ......................................................... 4 ст.

ПРАКТИЧНА РОБОТА №2

Визначення типу алгебр .............................................................................. 10 ст.

ПРАКТИЧНА РОБОТА №3

Застосування основних комбінаторних схем для розв’язання задач ...... 17 ст.

ПРАКТИЧНА РОБОТА №4

Знаходження мінімальних шляхів у зважених графах ............................. 23 ст.

ПРАКТИЧНА РОБОТА №5

Побудова та використання бінарних дерев пошуку ................................. 31 ст.

ПРАКТИЧНА РОБОТА №6

Побудова граматики мови програмування Pascal ..................................... 39 ст.

СПИСОК

ВИКОРИСТАНОЇ ЛІТЕРАТУРИ ................................................................ 49 ст.

Вступ

Вивчення дисципліни „Дискретна математика” передбачає виконання 6 практичних робіт, на виконання яких відводиться 12 навчальних годин.

Метою виконання практичних робіт є формування у студентів сис­тем­ного підходу при вивченні дискретних об’єктів, процесів та явищ; здо­бут­тя необ­хід­них їм мате­ма­тич­них знань (про способи створення, аналізу і опти­мі­зації диск­рет­них об’єктів); підготовка сту­ден­тів до розробки алгоритмів для розв’язування приклад­них задач, а також побудови комп’ютерних мереж.

В ході виконання практичних робіт студенти повинні

знати:

- математичний апарат дискретної математики
(множини, графи, елементи теорії загальної алгебри);

- основні формули та методи комбінаторики;

- алгоритми і засоби пошуку оптимальних розв’язків
типових задач дискретної математики;

вміти:

- виконувати постановку і розв’язання задач
синтезу та аналізу дискретних об’єктів;

- знаходити найбільш ефективний для розв’язання
конкретної задачі математичний апарат.

Теоретичною базою для виконання практичних робіт є не тільки матеріали, які розглядались на лекційних заняттях, а і матеріали, які виносились на самостій­не опрацювання студентами.

Практична робота №1

Виконання операцій над множинами.

Мета: Навчитися задавати множини та виконувати над ними операції; ефективно використовувати для тотожного перетворення формул алгебри
множин її основні закони та властивості.

Теоретичні відомості:

Множина є настільки загальним і водночас початковим поняттям, що її стро­ге визначення через більш прості поняття дати важко. Тому вслід за Георгом Кан­тором (німецький математик, засновник теорії множин) ми приймаємо інту­ї­ти­вне уявлення про множину як сукупність деяких елементів, цілком визначених у випадку кожної конкретної множини. Множини позначають великими, а елементи множин – малими латинськими буквами (можуть бути індекси).

Множина називається скінченою, якщо вона містить скінчене число еле­мен­тів (тобто для неї існує натуральне число, що дорівнює кількості її елементів), і нескінченою, якщо вона містить необмежене число елементів. Кількість еле­мен­тів скінченої множини А позначають як ½А½ і називають потужністю множи­ни.

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

Кортеж – це впорядкований набір елементів. Елементи, що утворюють кор­теж, називають його компонентами. Компоненти нумерують, кількість компонент на­зивають довжиною (розмірністю) кортежу. На відміну від елементів множини, ком­поненти кортежу можуть повторюватись.

Дві множини рівні, якщо вони містять одинаковий набір елементів. Мно­жи­на А, всі елементи якої належать множині В, називається підмножиною множини В. Нестроге включення позначається А Í В, означає, що А – підмножина мно­жи­ни В, що, можливо, співпадає з В. Строге включення позначається А Ì В і озна­чає, що А – підмножина множини В, що не співпадає з В.

Порожньою називається така множина, яка не містить ніяких елементів. Така множина позначається спеціальним символом Æ. Універсальною називається мно­жина, яка містить всі можливі елементи , що зустрічаються в даній задачі. Уні­версальна множина (універсум) позначається символом U. Множиною-степе­нем або булеаном множини А називають множину всіх її підмножин, зокрема по­рож­ню множину і саму множину А. Цю множину позна­чають 2^А чи Р(А).

Множини А та В називаються еквівалентними або рівнопотужними (А ~ В), якщо між ними можна встановити взаємно однозначну відповідність. Взаємно од­но­­значною називається така відповідність між множинами А та В, при якій ко­ж­но­му елементу множини А відповідає один і тільки один елемент множини В, і кожному елементу множини В відповідає один і тільки один елемент множини В. Функція, що визначає взаємно однозначну відповідність, називається бієктив­ною функцією або бієкцією.

Є декілька способів подання множин:

¾ вербальний (словесний) – за допомогою опису характеристичних властивостей, які повинні мати елементи множини;

¾ список (перелік) усіх елементів множини у фігурних дужках;

¾ предикатний (висловлювальний) – за допомогою предиката, тобто мно­жина подається у вигляді {х : Р(х)} або {х│Р(х)}, де Р(х) – пре­ди­кат, що набуває значення „істина” для елементів цієї множини;

¾ за допомогою породжувальної процедури (алгоритму), що описує спосіб отримання елементів множини із уже існуючих елементів або інших об’єктів, якщо такий спосіб існує.

Для наочного зображення співвідношень між підмножинами універсальної мно­жини використовуються діаграми Венна та круги Ейлера. Побудова діаграми Венна полягає в розбитті площини на 2ⁿ областей за допомогою n фігур. Кожна фі­гура на діаграмі зображує окрему множину. При цьому кожна наступна фігура по­винна мати одну і тільки одну загальну область-перетин з кожною з раніше по­бу­дованих фігур. Діаграми Венна не відображають реальні відношення вклю­чен­ня, що встановлені між множинами, а розглядають їх у загальному випадку. Інди­ві­ду­альні відношення між заданими множинами зображують за допомогою кругів Ей­лера. Для зображення множини на площині креслять замкнену лінію із за­штри­хо­ваною внутрішньою областю (найчастіше – це коло, але для зображення уні­вер­са­льної множини – прямокутник). У цьому випадку множини, що не мають спі­ль­них елементів, зображують не­перетинними фігурами. Відношення включення на мно­жинах зображують, роз­та­шовуючи одну фігуру вкладеною в іншу.

Основні операції над множинами та результати їх виконання:

¾ об’єднання (А È В) – множина, що складається з усіх елементів мно­жи­н А та В і не містить жодних інших елемен­тів;

¾ перетин (А Ç В) – множина, що складається з тих і тільки тих еле­мен­тів, які належать одночасно множині А та множині В;

¾ різниця (А \ В) – множина, що складається з тих і тільки тих еле­мен­тів, які належать множині А й не належать В;

¾ симетрична різниця (А Å В) – множина, що складається з усіх еле­ментів А, які не належать множині В, й усіх елементів В, які не на­ле­жать множині А, та яка не містить ніяких інших елементів;

¾ доповнення (Ā) – множина, що містить усі елементи універсальної множини (універсуму), за винятком елементів А.

Прямим або декартовим добутком множин А та В називають множину всіх упо­рядкованих пар елементів (a, b), з яких перший належить множині А, а другий – множині В. Порядок входження пар може бути будь-яким, але розміщення еле­мен­тів у кожній парі визначається порядком множин, що перемножуються.

Множина 2^U всіх підмножин універсальної множини U із заданими на ній чотирма операціями (об’єднання, перетин, різниця, доповнення) складає алгебру мно­жин. Алгебра множин широко застосовується у програмуванні, зокрема, при ро­боті з різноманітними базами даних і становить основу для побудови багатьох ма­те­матичних структур; вона дуже проста і близька до реального життя.

Черговість виконання операцій у виразах називається пріоритетом. Поря­док ви­­конання операцій над множинами відповідно до їх пріоритету: Ā; АÇВ; АÈВ; А\В. Порядок виконання операцій над множинами можна змінити, якщо взяти окре­мі фрагменти виразу в круглі дужки. Якщо у ви­ра­зі є декілька операцій з одна­ковим пріоритетом, то вони будуть виконуватися злі­ва направо. Треба па­м’я­та­ти, що фрагмент у дужках перед обчисленням всього ви­разу сприймається як окремий операнд.

Основні тотожності алгебри множин:

1. комутативні закони

2. асоціативні закони

3. дистрибутивні закони

4. властивості порожньої та універсальної множин

5. закони ідемпотентності

6. закони поглинання

7. закони де Моргана

8. інші властивості алгебри множин

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

Порядок виконання роботи:

1. Занотуйте номер свого варіанту для звіту.

2. Виберіть згідно номеру свого варіанту дані для завдання
та перепишіть у звіт формулювання цього завдання.

3. Задайте множини А та В.

4. Виконайте над множинами А та В операції об’єднання,
перетину, різниці та симетричної різниці.

5. Знайдіть декартовий добуток множин А та В.

6. Зобразіть основні операції над множинами
за допомогою кругів Ейлера.

7. Спростіть вираз за допомогою основних тотожностей алгебри множин.

8. Занотуйте для звіту основні закони і властивості алгебри множин.

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

1. Що називається множиною?

2. Яке практичне застосування має теорія множин?

3. Яку множину називають скінченою?

4. Яку множину називають впорядкованою?

5. Що представляє собою універсальна множина?

6. Що представляє собою порожня множина?

7. Коли можна вважати, що множини рівні?

8. Які є способи задання множин?

9. Яку множину називають булеаном або множиною-степенем?

10. Які засоби використовують для геометричної інтерпретації множин?

11. Які основні операції можна виконувати над множинами?

12. Що представляє собою об’єднання множин?

13. Що представляє собою перетин множин?

14. Що представляє собою різниця множин?

15. Що представляє собою симетрична різниця множин?

16. Що представляє собою доповнення множини?

17. Які є основні закони та властивості алгебри множин?

18. Що представляє собою алгебра множин?

19. Що представляє собою декартовий добуток множин?

20. Яку множину називають нечіткою?

21. Які множини називають еквівалентними?

22. Що представляє собою лінгвістична змінна?

Студенти повинні знати:

1. основні поняття теорії множин;

2. способи задання множин та їх геометричну інтерпретацію;

3. основні операції над множинами;

4. загальну характеристику нескінченних та нечітких множин;

5. основні тотожності алгебри множин та методи їх доведення.

Студенти повинні вміти:

1. використовувати спеціальні позначення введені у теорії множин;

2. задавати множини;

3. виконувати основні операції над множинами;

4. ефективно використовувати основні закони та властивості
алгебри множин для тотожного перетворення формул.

Порядок оформлення звіту:

Звіт повинен складатися з наступних частин:

1. Тема роботи.

2. Мета роботи.

3. Хід роботи.

4. Висновки до роботи.

Зразок виконання практичної роботи №1

Завдання

Задати списком (переліком) елементів та предикатним (висловлювальним) спосо­бом множини А та В:

Виконати над множинами А та В операції об’єднання, перетину, різниці, симет­ри­чної різниці. Знайти декартовий добуток множин А та В. Наочно зобразити осно­вні операції над множинами (об’єд­нан­ня, пе­ретин, різниця, доповнення та симет­ри­чна різниця) за допомогою кругів Ей­ле­ра. Спростити вираз за допомогою основних законів і властивостей алгеб­ри множин:

№	вираз

Розв’язок

3. Задання множин списком (переліком) елементів:

А={1, 2, 3, 4, 5, ..., 22, 23};

В={11, 22, 33, 44, 55, 66, 77, 88, 99};

задання множин предикатним способом:

А={a│aÎN, a £ 23}; B={b│bÎZ, 10£b£99, b mod 11=0}.

4. А È В={1, 2, 3, 4, 5, ..., 22, 23, 33, 44, 55, 66, 77, 88, 99};

А Ç В={11, 22};

А \ В={1, 2, 3, …, 10, 12, 13, …, 20, 21, 23};

А Å В={1, 2, 3, …, 10, 12, 13, …, 20, 21, 23, 33, 44, 55, 66, 77, 88, 99}.

5. Декартовий добуток множин:

A ´ B={(1, 11), (1, 22), …, (1, 99), (2, 11), (2, 22), …, (2, 99), …, (23, 99)}.

7.

Завдання

Задати списком (переліком) елементів та предикатним (висловлювальним) спосо­бом множини А та В:

Виконати над множинами А та В операції об’єднання, перетину, різниці, симет­ри­чної різниці. Знайти декартовий добуток множин А та В. Наочно зобразити осно­вні операції над множинами (об’єд­нан­ня, пе­ретин, різниця, доповнення та симет­ри­чна різниця) за допомогою кругів Ей­ле­ра. Спростити вираз за допомогою основних законів і властивостей алгеб­ри множин:

№	вираз

Практична робота №2

Визначення типу алгебр.

Мета: Навчитися працювати з алгебраїчними структурами,
досліджувати їх властивості та визначати тип алгебр.

Теоретичні відомості:

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

Операцією на множині Х називається функція F, яка є відображенням виду Хⁿ ® X, n ÎN, де Хⁿ – декартовий добуток Х ´ Х ´...´ Х, в який Х входить n разів. У цьому визначенні є два важливих моменти. По-перше, оскільки операція є фун­к­­цією, то результат застосування операції визначено однозначно. Тому даний упо­ряд­кований набір з n елементів множини Х функція F переводить тільки в один еле­мент із Х. По-друге, операція замкнена на Х у тому розумінні, що область ви­зна­чення та область значень операції лежать у Хⁿ і X відповідно.

Стверджують, що операція Хⁿ ® X має порядок n або є n-арною операцією. Частіше зустрічаються ситуації, коли порядок дорівнює 1 або 2. Операції виду Х ® X називають унарними, а операції Х² ® X називають бінарними. Елементи упо­­рядкованого набору з n елементів в області визначення Хⁿ називають операн­да­ми. Операції звичайно позначають символами, що називають операторами. У ви­­падку унарних операцій символ оператора ставлять перед або над операндом. Бі­нарні операції записують одним з трьох способів. У першому випадку оператор ста­виться між операндами (infix), у другому – перед операндами (prefix) і у тре­тьо­му – після операндів (postfix). Відповідно до більшості математичних текстів ми будемо використовувати позначення infix. Форми запису postfix і prefix мають ту перевагу, що не потребують дужок при визначенні порядку обчислень склад­них виразів, і це робить їх особливо зручними для автоматичної обробки. Вони час­то використовуються для представлення виразів у пам’яті комп’ютера.

Крім стандартних відомих нам операцій ( + , – , * ) існує багато інших. Ми бу­демо використовувати символи Å і Ä для позначення абстрактних бінарних опе­рацій. Бінарні операції, визначені на скінченних множинах, зручніше задавати за допомогою таблиць. Таблиця, що задає деяку бінарну операцію Ä на деякій мно­жині А, називається таблицею Келі, її рядки та стовпці нумеруються еле­мен­та­ми множини А, а елементом таблиці, що стоїть на перетині рядку a_i і стовпця a_j, є елемент a_k = a_i Ä a_j .

Властивості, які можуть мати операції:

1. нехай дано множину А, на якій визначено деяку бінарну операцію Ä; якщо a Ä b = b Ä a для всіх a, b Î A, то стверджують, що бінарна опера­ція Ä на множині А має властивість – комутативність;

2. якщо (a Ä b) Ä c = a Ä (b Ä c) для всіх a, b, c ÎA, то стверджують, що бі­нар­на операція Ä на множині А має властивість – асоціативність;

3. нехай на множині А визначено дві бінарні операції Ä і Å; якщо для всіх a, b, c ÎA виконується a Ä (b Å c) = (a Ä b) Å (a Ä c), то стверджують, що опе­ра­ція Ä має властивість – дистрибутивність відносно операції Å.

Якщо для бінарної операції Ä на множині А існує елемент е Î А такий, що для всіх а Î А: е Ä а = а Ä е = а, тоді е називається нейтральним елементом (оди­ни­цею або нулем) відносно операції Ä.

Нехай Ä – операція на А з нейтральним елементом е і елементи х, у Î А за­до­вольняють рівності: х Ä у = е = у Ä х. Тоді у називається оберненим елементом до х відносно операції Ä, і х називається оберненим елементом до у відносно опе­ра­ції Ä. Обернений елемент ще називають симетричним або протилежним.

Іноді розрізняють ліві та праві одиниці і ліві та праві обернені елементи, однак у більшості випадків вони є двосторонніми.

Нехай n – довільне натуральне число. Додаванням за модулем n цілих чисел a і b називається алгебраїчна операція, результатом якої є решта (остача) від ді­лен­ня суми a + b на n. Множенням за модулем n цілих чисел a і b називається ал­ге­б­раїчна операція, результатом якої є решта (остача) від ділення добутку a * b на n. Ці операції ( Å_n, Ä_n ) визначені на множині цілих невід’ємних чисел Z₊ .

Алгебраїчною структурою (алгеброю) називається множина разом із за­да­ни­ми операціями, визначеними і замкненими на цій множині. Ця множина нази­ва­є­ть­ся носієм алгебраїчної структури.

Алгебраїчна структура S¢ – ( А¢, Å¢ ) є підструктурою алгебраїчної структури S – ( А, Å ), якщо: А¢ Ì А; Å¢ і Å операції одного порядку і звуження операції Å на підмножині А¢ співпадає з операцією Å¢. Очевидно, що найбільшою підструк­ту­­рою структури S є сама структура S. У деяких випадках інших підструктур мо­же не бути. Відношення між алгебраїчними структурами можуть бути не тільки такі, що включають (структура – підструктура). Можливі й інші відношення, що до­зволяють здійснювати перехід від структури до структури, з втратою деякої ін­фор­­мації або без втрати інформації.

Нехай задано дві структури (А, Ä), (С, Å) з операціями Ä, Å одного порядку n. Відображення j : А ® С називається гомоморфізмом із структури (А, Ä) у стру­­ктуру (С, Å), якщо воно представлене операціями у такому вигляді:

j × Ä = Å × j¢, де відображення j¢ : Аⁿ ® Сⁿ діє за правилом

j¢(а₁, а₂, ... , а_n) = ( j(а₁), j(а₂), ... , j(а_n) ), " а_і Î А. Для бінарних операцій, зокрема, j (х Ä у) = j (х) Å j (у) для будь-яких х, у Î А.

Гомоморфізм, який є бієкцією, називають ізоморфізмом. Якщо існує ізо­мор­фізм між двома алгебраїчними структурами, то говорять, що вони ізоморфні одна одній. Відношення ізоморфізму – це відношення еквівалентності на множині ал­геб­­раїчних структур, тому ізоморфізм розбиває множину всіх алгебраїчних стру­к­тур на класи еквівалентності. Використовуючи ізоморфізм, можна здійснювати екві­­валентні перетворення алгебраїчних структур.

Півгрупою називається алгебраїчна структура з множиною-носієм А і бінар­ною операцією Ä: А² ® А, яка задовольняє властивості асоціативності.

Якщо бінарна операція півгрупи – комутативна, то півгрупу називають ко­му­та­тивною, або абелевою. Півгрупа з одиницею є моноїдом.

Групою називають множину G з бінарною операцією Ä, що замкнена в G, та­кою, що: Ä – асоціативна; існує нейтральний елемент е Î G (одиниця) відносно Ä; кожному елементу х Î G відповідає обернений (симетричний, проти­леж­ний) елемент х¢ Î G відносно Ä. Чис­ло елементів групи називають її порядком.

Група, в якій бінарна операція комутативна, є комутативною, або абелевою. Групу, всі елементи якої є степенями одного елемента а , називають циклічною.

Кільцем (R, Å, Ä) називається множина R з визначеними на ній бінарними опе­раціями Å і Ä, такими, що: Å – асоціативна і комутативна та має одиницю, яка на­зивається нулем; існує обернений (симетричний) елемент відносно Å для кожно­го х Î R; Ä – асоціативна і дистрибутивна відносно Å зліва і справа.

Будемо вважати, що кільце комутативне, якщо бінарна операція Ä – кому­та­тив­на і є кільцем з одиницею, якщо існує одиниця відносно Ä. Кільце з одиницею часто називають алгеброю.

Поле (R, Å, Ä) – це комутативне кільце з одиницею (відносно Ä, що від­різ­ня­ється від нуля (нейтрального елемента відносно Å)), в якому кожний елемент а (що відрізняється від нуля) обернений за Ä. Поле можна визначити як об’єднання двох абелевих груп, пов’язаних одним законом дистрибутивності.

Алгебри – це множини, на яких задані операції. Множини, де крім операцій за­дані відношення, називають алгебраїчними системами. Тобто, алгебраїчні стру­к­­­тури можна вважати окремим випадком алгебраїчних систем (в яких мно­жи­на від­ношень – порожня). Прикладом алгебраїчної системи, що найчастіше трап­ля­­ється в теоретичній алгебрі та її застосуваннях є гратка.

Граткою називають частково впорядковану множину, в якій для будь-яких двох елементів a і b існують: a Ù b = с – така нижня грань a та b, що будь-яка інша ниж­ня грань a і b менша за с; a Ú b = d – така верхня грань a та b, що будь-яка інша верхня грань a і b більша за d.

Отже, гратка – це алгебраїчна система (М; £; Ù; Ú) з одним бінарним відно­шен­ням часткового порядку та двома бінарними операціями (Ù і Ú), які є абст­ра­к­т­ними операціями алгебраїчної системи.

Порядок виконання роботи:

1. Занотуйте номер свого варіанту для звіту.

2. Виберіть згідно номеру свого варіанту дані для завдання
та перепишіть у звіт формулювання цього завдання.

3. Визначте, чи замкнені дані операції відносно заданих множин.

4. Визначте, чи мають зазначені операції наведені властивості.

5. Зобразіть у вигляді таблиці основні типи алгебр і вкажіть
властивості та відповідні елементи першого (адитивного)
і другого (мультиплікативного) законів алгебри.

6. Визначте тип заданих алгебраїчних структур (алгебр).

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

1. Що називають операцією на множині?

2. Які операції називають бінарними?

3. Які існують способи запису операцій?

4. Що представляє собою наступна властивість операцій: комутативність?

5. Що представляє собою наступна властивість операцій: асоціативність?

6. Що представляє собою наступна властивість операцій: дистрибутивність?

7. Що називають алгебраїчною структурою?

8. Що називають гомоморфізмом алгебр?

9. Що називають ізоморфізмом алгебр?

10. Коли вважають, що операція є замкненою відносно множини?

11. Який елемент множини називають нейтральним (одиницею або нулем)?

12. Який елемент множини називають
симетричним (оберненим або протилежним)?

13. Що називають півгрупою?

14. Що називають групою?

15. Що представляє собою кільце?

16. Що називають тілом?

17. Що представляє собою поле?

18. Що називають алгебраїчною системою?

19. Що представляє собою гратка?

20. Яке практичне застосування мають алгебраїчні структури та системи?

Студенти повинні знати:

1. основні поняття, означення та властивості алгебраїчних структур;

2. способи задання множин та операцій на них;

3. типи алгебр та їх особливості;

4. алгебраїчні операції та їх властивості;

5. загальну характеристику алгебраїчних систем.

Студенти повинні вміти:

1. використовувати спеціальні позначення
введені для алгебраїчних структур і систем;

2. задавати множини та операції на них;

3. працювати з алгебраїчними структурами;

4. досліджувати властивості алгебраїчних структур і систем;

5. визначати тип алгебр.

Порядок оформлення звіту:

Звіт повинен складатися з наступних частин:

1. Тема роботи.

2. Мета роботи.

3. Хід роботи.

4. Висновки до роботи.

Зразок виконання практичної роботи №2

Завдання

Визначити, чи замкнені дані операції відносно заданих множин:

Визначити, чи мають зазначені операції наведені властивості:

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

Визначити тип алгебр:

Розв’язок

3. Визначаю, чи замкнені дані операції відносно заданих множин:

4. Визначаю, чи мають зазначені операції наведені властивості:

5. Зображаю у вигляді таблиці основні типи алгебр і вказую
властивості та відповідні елементи першого (адитивного)
і другого (мультиплікативного) законів алгебри:

6. Визначаю тип заданих алгебраїчних структур (алгебр):

( R, + ) – множина дійсних чисел разом з операцією додавання є абе­ле­вою гру­пою; ( N, + ) – множина натуральних чисел разом з операцією додавання є абе­­ле­вою півгрупою; ( R, * ) – множина дійсних чисел разом з операцією мно­жен­ня є абе­ле­вою півгрупою з одиницею; ( N, * ) – множина натуральних чисел разом з операцією множення є абе­ле­­вою півгрупою з одиницею;

( R₊, * ) – додатна підмножина множини дійсних чисел разом з операцією множення є абелевою групою;

( R, +, * ) – множина дійсних чисел із стандартними операціями додавання і множення є полем і складається з абелевих груп ( R, + ), ( R \ {0}, * ), операції в яких зв’язані відповідним законом дистрибутивності;

( Z_n, Å_n, Ä_n ) – множина цілих невід’ємних чисел, менших за n, із стан­дар­т­ни­ми операціями додавання за модулем n та множення за модулем n є кому­та­тив­ним кільцем з одиницею при будь-якому n Î N. Якщо n – просте число, то алгебра ( Z_n, Å_n, Ä_n ) є полем.

Завдання

Визначити, чи замкнені дані операції відносно заданих множин:

Визначити, чи мають зазначені операції наведені властивості:

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

Визначити тип алгебр:

Практична робота №3

Застосування основних комбінаторних схем
для розв’язання задач.

Мета: Навчитися застосовувати основні комбінаторні схеми для

розв’язування типових задач комбінаторики.

Теоретичні відомості:

Комбінаторика або комбінаторний аналіз – розділ дискретної математики, що вивчає комбінації і перестановку предметів, взаємне розташування частин скінчених множин предметів довільного походження, а також нескінченних мно­жин, які задовольняють деякі умови підпорядкованості. Виникла комбінаторика у XVII столітті, але у самостійну наукову дисципліну комбінаторний аналіз сфор­му­вався лише у ХХ столітті. Комбінаторні методи застосовуються в теорії ймо­вір­нос­тей, випадкових процесах, статистиці, мате­ма­тичному програмуванні, пла­ну­ван­ні експериментів. Розглядаються задачі, в яких до­во­диться обирати ті чи інші предмети, розташовувати їх у певному порядку і знаходити серед різно­манітних комбінацій найкращі. Комбінаторика тісно зв’язана з теоріями чисел, графів, скін­чен­­них автоматів. Її досягнення використовуються під час планування та ана­лі­зу наукових експериментів, у лінійному та динамічному програмуванні, у ма­те­ма­тич­ній економіці, у системах проектування та керування, у комп’ютерних нау­ках та інших галузях науки і техніки.

Виділяють такі проблеми (основні типи за­дач) комбінатор­но­го аналізу: зада­чі на пере­лічення, задачі про існування та побудо­­ву, задачі про вибір. У задачах на перелічення необхідно визначити кількість розміщень елемен­тів скінченної мно­­­жи­ни, що задовольняють певні умови. Для розв’язку задач пе­ре­лічення роз­роб­лено різно­ма­нітні методи, серед яких метод продуктивних фун­к­цій і метод перелічення Поя. У за­да­чах про існування та побудову розглядаються питан­ня: чи має місце визначена кон­фі­гу­рація частин скінченної множини з дея­ки­ми влас­ти­востями; якщо така конфігурація існує, то як її побудувати. При цьому важливу роль відіграють чисельні та алгебраїчні ме­то­ди. За­­дачі про вибір досліджують умо­ви, за яких можна здійснити вибір підмножини або дея­кої су­ку­п­ності частин множини так, щоб задовольнити певні вимоги. Для розв’язку задач про вибір, крім комбінаторних методів, треба застосовувати алгебраїчний апарат.

Правило добутку комбінаторного аналізу: нехай предмет а₁ можна обрати m₁ способами, предмет а₂ – m₂ способами, ... , предмет а_k – m_k способами і нехай ви­бір предмета а₁ не впливає на кількість способів вибору предметів а₂, ... , а_k; вибір предмета а₂ не впливає на кількість способів вибору предметів а₁, а₃, ... , а_k і т. д. Тоді вибір упорядкованої множини предметів (а₁, а₂, ... , а_k) у вказаному поряд­ку можна здійснити m₁ * m₂ * … * m_k способами.

Правило суми комбінаторного аналізу: нехай предмет а₁ можна обрати m₁ способами, предмет а₂ – m₂ способами, ... , предмет а_k – m_k способами. Тоді вибір предмета а₁, або а₂, ... , або а_k може бути зроблений m₁ + m₂ + … + m_k способами.

Нехай M={а₁, а₂, ... , а_n} – фіксована множина. Упорядковані підмножини з k елементів множини М називаються перестановками k елементів. Можна сказати, що k-перестановки – це розміщення у визначеному порядку k елементів з мно­жини М. k-перестановки множини з n елементів називаються розміщеннями з n по k елементів. Якщо у перестановці беруть участь всі елементи множини (n-пере­ста­новка), то використовують термін перестановка, а кількість всіх n-перестановок позначають через . Два розміщення з n по k різні, якщо вони складаються з різних елементів або з однакових елементів, але розміщених у різному порядку. Кіль­кість розміщень з n по k елементів: . Кількість всіх перестановок з n елементів: . Розміщення і перестановки обов’язково враховують порядок елементів. Розміщенням з повтореннями з n елементів по k називається кортеж (вибірка з повторенням) довжини k з n елементів. Кількість k-розміщень з повтореннями з n елементів обчислюється за формулою: .

Кількість n-пере­ста­­новок з повтореннями, які містять n₁ елементів першого типу, n₂ елементів дру­го­го типу, ... , n_k елементів k-го типу (n₁+n₂+... +n_k =n): .

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

Біноміальна формула: .

Композиції числа – це його розкладання у суму натуральних доданків, де вра­­хо­­ву­ють­ся як величини доданків, так і порядок їх розташування у сумі. Роз­би­т­тям числа називається його розкладання у суму натуральних доданків, де вра­хо­­вуються величини до­дан­ків, але не враховується порядок їх розташування у сумі.

Досить часто у комбінаториці використовують рекурентні співвідношення. Метод реку­рен­тних співвідношень полягає у тому, що розв’язок комбінаторної задачі з n предметами ви­ра­жається через розв’язок аналогічної задачі з меншою кількістю предметів за допо­мо­гою деякого співвідношення, яке називається рекурентним (зворотним). Користуючись цим спів­відношенням, шукану величину можна обчислити, виходячи з того, що для невеликої кіль­кості предметів розв’я­зок задачі легко знаходиться.

Порядок виконання роботи:

1. Занотуйте номер свого варіанту для звіту.

2. Виберіть згідно номеру свого варіанту дані для завдання 1
та перепишіть у звіт формулювання цього завдання.

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

4. Виберіть згідно номеру свого варіанту дані для завдання 2
та перепишіть у звіт формулювання цього завдання.

5. Знайдіть кількість способів розміщення Nрізних
предметів у M урнах (з урахуванням і без урахування
порядку розміщення предметів в урнах).

6. Виберіть згідно номеру свого варіанту дані для завдання 3
та перепишіть у звіт формулювання цього завдання.

7. Визначте кількість невід’ємних цілих розв’язків
заданого рівняння при вказаних умовах.

8. Виберіть згідно номеру свого варіанту дані для завдання 4
та перепишіть у звіт формулювання цього завдання.

9. Вкажіть порядок розкладу заданого виразу
за допомогою біноміальної формули.

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

1. Для розв’язку яких задач використовують комбінаторику?

2. Що представляє собою правило добутку комбінаторного аналізу?

3. Що представляє собою правило суми комбінаторного аналізу?

4. Що представляє собою множина?

5. Що представляє собою кортеж?

6. Що представляє собою вибірка?

7. Яку вибірку називають розміщенням?

8. Яку вибірку називають сполученням?

9. Яку вибірку називають перестановкою?

10. Яким чином можна обчислити кількість перестановок?

11. Як можна обчислити кількість перестановок із повтореннями?

12. Яким чином можна обчислити кількість сполучень?

13. Як можна обчислити кількість сполучень із повтореннями?

14. Яким чином можна обчислити кількість розміщень?

15. Як можна обчислити кількість розміщень із повтореннями?

16. Які позначення використовують у комбінаторному аналізі?

17. Які властивості характерні для сполучень?

18. Що представляють собою композиції та розбиття чисел7

19. Як можна обчислити кількість композицій числа?

20. Як можна обчислити кількість розбиттів числа?

21. Що представляє собою метод рекурентних співвідношень?

22. Що представляє собою формула включень та виключень?

23. Що представляє собою біноміальна формула?

24. Для чого використовують продуктивні функції?

Студенти повинні знати:

1. загальну характеристику та історію розвитку комбінаторики;

2. основні поняття, означення та правила комбінаторного аналізу;

3. загальну характеристику розміщень, сполучень та перестановок;

4. основні типи комбінаторних задач та методи їх розв’язку.

Студенти повинні вміти:

1. використовувати спеціальні позначення
введені для комбінаторного аналізу;

2. знаходити кількість розміщень, сполучень та
перестановок (з повтореннями і без них);

3. застосовувати основні комбінаторні схеми для розв’язування задач.

Порядок оформлення звіту:

Звіт повинен складатися з наступних частин:

1. Тема роботи.

2. Мета роботи.

3. Хід роботи.

4. Висновки до роботи.

Зразок виконання практичної роботи №3

Завдання

1. Знайти кількість слів (рядків), які можна утворити, переставляючи букви

наступного слова: PERSPECTIVE.

2. Скількома способами можна розмістити Nрізних предметів у M урнах
(з урахуванням і без урахування порядку розміщення предметів в урнах) ?

N=21, M=6.

3. Визначити кількість невід’ємних цілих розв’язків рівняння при заданих умовах:

4. Знайти розклад виразу (х + у)^k для k = 4 (за допомогою біноміальної формули).

Розв’язок

1. Знаходжу кількість слів, які можна утворити, переставляючи букви слова PERSPECTIVE (11 букв). У цьому слові є повторні входження букв, тому
треба використати формулу для знаходження кількості перестановок із повтореннями:

2. Знаходжу кількість способів розміщення 21 різних предметів у 6 урнах (з ура­ху­­ванням і без урахування порядку розміщення предметів в урнах). Кіль­кість роз­поділів різних предметів без урахування порядку предметів в урнах: кож­ний предмет можна покласти у будь-яку з 6 урн, тому за правилом добутку пре­д­мети можна розмістити mⁿ = 6²¹ способами.

Кіль­кість розподілів різних пре­д­метів з урахуванням їх порядку в урнах: якщо не обмежува­ти кількість пре­дметів в урнах і якщо предмети не розрізняти між собою, то кількість таких роз­­поділів дорівнює . Кожному способу розпо­ді­лу однакових предметів між урнами відповідає n! способів розподілу різних предметів з урахуванням їх порядку. За пра­ви­лом добутку одержуємо шукану кількість розміщень пред­ме­тів:

3. Визначаю кількість невід’ємних цілих розв’язків рівняння х₁+х₂+х₃+х₄+х₅ = 25 за умов: х₁ ≥ 1, х₂ ≥ 2, х₃ ≥ 3, х₄ ≥ 4, х₅ ≥ 5. Дана задача еквівалентна рівнянню х₁+х₂+х₃+х₄+х₅ = 10 без обмежень; оскільки потрібно взяти щонайменше 1 еле­мент першого типу, 2 – другого, 3 – третього, 4 – четвертого і 5 елементів п’я­то­го типу – разом 1+2+3+4+5 =15 елементів; отже, 25 – 15 = 10 елементів зали­шається для довільного вибору.

4. Знаходжу розклад виразу (х + у)^k для k = 4 (за допомогою біноміальної формули). Скориставшись біноміальною формулою можна записати:

Завдання

1. Знайти кількість слів (рядків), які можна утворити, переставляючи букви

наступного слова:

2. Скількома способами можна розмістити Nрізних предметів у M урнах
(з урахуванням і без урахування порядку розміщення предметів в урнах) ?

3. Визначити кількість невід’ємних цілих розв’язків рівняння при заданих умовах:

4. Знайти розклад виразу (х + у)^k для k = 7 (за допомогою біноміальної формули).

Практична робота №4

Знаходження мінімальних шляхів у зважених графах.

Мета: Навчитися задавати графи та працювати з ними; застосовувати основні алгоритми пошуку оптимальних маршрутів теорії графів для знаходження мінімальних шляхів у зважених графах.

Теоретичні відомості:

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

Задачі відшукання оптимальних маршрутів у графах час­то зустрічаються на прак­тиці. У реальних задачах на графах, як правило, потрібно брати до уваги додат­ко­ву інфор­­ма­цію – фактичну віддаль між окремими пунктами, вартість проїзду, час проїз­ду. Для цьо­го використовують поняття зваженого графа. Зваженим називають про­с­тий граф, кожному ребру e якого приписано дійсне число w(e). Це число на­зи­вають ва­гою ребра e. Аналогічно означають зважений орієнтований граф: це та­кий орієн­­то­ва­ний граф, кожній дузі e якого приписано дійсне число w(e), яке нази­ва­ють вагою дуги. Існують такі основні способи задання (зберігання) зважених графів: по­дан­ня графа матрицею ваг W, яка являє собою аналог матриці су­міжності; подання графа списком ребер доповненим відповідними вагами; подання графа списками суміжності. Довжиною шляху в зваженому графі називають суму ваг ребер (дуг), які утво­­рюють цей шлях. Якщо граф не зважений, то вагу кожного ребра (кожної дуги) вва­жають рівною 1 й отримують раніше введене поняття довжини шляху як кількос­ті ребер (дуг) у ньому.

Задача про найкоротший шлях полягає в знаходженні мінімального (найкорот­шо­го) шляху від заданої початкової вершини а до заданої вершини z. Наступні дві задачі – без­посередні узагальнення сформульованої задачі про найкоротший шлях: для заданої початкової вершини а знайти найкоротші шляхи від а до всіх інших вер­шин (задача 1); знайти найкоротші шляхи між усіма парами вершин графа (за­да­ча 2). Вияв­ляється, що майже всі методи розв'язання задачі про найкоротший шлях від зада­ної початкової вершини а до заданої вершини z також дають змогу знайти й най­коротші шляхи від вершини а до всіх інших вершин графа. Отже, за їх допо­мо­гою можна розв'язати задачу 1 із невеликими додатковими обчис­лювальними ви­тра­­тами. З іншого боку, задачу 2 можна розв'язати або n разів застосувавши алго­ритм за­да­чі 1 із різними початковими вершинами, або один раз застосувавши спе­ціа­ль­ний алгоритм. Розглянемо два алгоритми: перший алгоритм призначений для роз­в'язування задачі 1, другий – для задачі 2.

Найефективніший алгоритм визначення довжини найкоротшого шляху від фік­со­ваної вершини до будь-якої іншої запропонував у 1959 році датський математик Е. Дейкстра (Е. Dijkstra). Цей алгоритм застосовний лише тоді, коли вага кож­ного реб­ра (дуги) додатна.

Нехай G = (V, Е) – зважений орієнтований граф, w(v_i, v_j) – вага дуги (v_i, v_j). По­чав­ши з вершини а, знаходимо віддаль від а до кожної із суміжних із нею вершин. Вибираємо вершину, віддаль від якої до вершини а найменша; нехай це буде вер­ши­на v*. Далі знаходимо віддалі від вершини а до кожної вершини, суміжної з v* вздовж шляху, який проходить через вершину v*. Якщо для якоїсь із таких вершин ця віддаль менша від поточної, то замінюємо нею поточну від­даль. Знову вибираємо вер­шину, найближчу до а й не вибрану раніше; повто­рюємо процес.

Описаний процес зручно виконувати за допомогою присвоювання вершинам мі­ток. Є мітки двох типів — тимчасові та постійні. Вершини з постійними мітками гру­пу­ють у множину М, яку називають множиною позначених вершин. Решта вер­шин має тимчасові мітки, і множину таких вершин позначимо як Т, Т = V \ M. Позначати­ме­мо мітку (тимчасову чи постійну) вершини v як l(v). Значення постійної мітки l(v) до­рівнює довжині найкоротшого шляху від вершини а до вершини v, тимчасової – до­в­жині найкоротшого шляху, який проходить лише через вершини з постійними міт­ками. Фіксованою початковою вершиною вважаємо вершину а; довжину найкорот­шо­го(мінімального) шляху шукаємо до вершини z (або до всіх вершин графа). Тепер формально опишемо алгоритм Дейкстри (наведемо кроки алгоритму).

Алгоритм Дейкстри:

Крок 1. Присвоювання початкових значень. Виконати l(a) : = 0 та вважати цю мі