ДМ_МУ_САМ РАБ

Вцих виданнях можна знайти роз’яснення з основних постановок комбінаторних задач та приклади їх використання.

Література [16] являє собою сучасний підручник з дискретної математики. Окрім таких розділів, як математична логіка, теорія множин, комбінаторика, теорія графів, теорія алгоритмів і обчислень, що традиційно складають курс дискретної математики, у підручнику є відомості про теорію ймовірностей, алгебру і теорію чисел. Особливу увагу в ньому приділено теорії доведень. Вивчення матеріалів літератури [16] потребує деякої математичної культури, хоча для вивчання основних глав достатньо знань з математики у обсязі середньої школи. Матеріал підручника супроводжується багато численними прикладами, в кінці кожного розділу наводиться велика кількість вправ.

Достатньо повно в літературі [1-4, 10, 14, 16] представлено питання з теорії графів: основні положення; операції над графами; властивості графів; способи задання графів; дерева; транспортні мережі і течії.

Влітературі [1, 2, 16] розглядаються питання з теорії скінченних автоматів.

Література [13, 18] може використовуватися для самостійної перевірки знань з основ дискретної математики на базі тестових завдань (та відповідей на них).

Згідно з робочою програмою для вивчення дисципліни «Дискретна математика» надаються [20-23]: конспект лекцій, методичні вказівки з практичних занять, методичні вказівки до самостійної роботи, матеріали дистанційного навчання.

21

4 МЕТОДИЧНІ ВКАЗІВКИ З ВИВЧЕННЯ ЗМІСТОВИХ МОДУЛІВ ДИСЦИПЛІНИ «ДИСКРЕТНА МАТЕМАТИКА»

4.1 Змістовий модуль 1 «Введення в дисципліну. Основи теорії множин.

Алгебра множин» 4.1.1 Перелік тем змістовного модуля 1

Під час вивчення змістового модуля 1 розглядаються такі теми:

тема 1 «Історія зародження, розвитку і становлення дискретної математики. Внесок вчених у її розвиток. Мета і задачі дисципліни, її місце в системі підготовки фахівців з комп'ютерних наук»;

тема 2 «Основні поняття і позначення теорії множин»;

тема 3 «Алгебра множин».

4.1.2 Тема 1 «Історія зародження, розвитку і становлення дискретної математики. Внесок вчених у її розвиток. Мета і задачі дисципліни, її місце в системі підготовки фахівців з комп'ютерних наук»

Дискретність – поняття, протилежне безперервності. Дискретна математика – галузь математики, що вивчає властивості дискретних структур.

У широкому сенсі дискретна математика включає в себе теорію чисел,

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

Комп’ютерні науки викладається на I курсі. У зв'язку з цим зростає його роль як важливої ланки математичної освіти.

З основними питаннями історії зародження, розвитку і становлення дискретної математики, з внеском вчених у її розвиток, з її місцем в системі підготовки фахівців з комп'ютерних наук можна ознайомитись, використовуючи електронні джерела (наприклад, http://uk.wikipedia.org/wiki).

Мета і задачі дисципліни «Дискретна математика»надаються в розділі 2 методичних вказівок.

Матеріал дисципліни «Дискретна математика», що викладається для студентів напряму 6.050101 – Комп’ютерні науки, згрупований у такі змістові модулі:

22

змістовий модуль 1 «Введення в дисципліну. Основи теорії множин. Алгебра множин»;

змістовий модуль 2 «Відношення та їх властивості»;

змістовий модуль 3 «Алгебри (алгебраїчні структури)»;

змістовий модуль 4 «Основи математичної логіки. Двійкова логіка.

Булеві функції та перетворення»;

змістовий модуль 5 «Логіка висловлень і логіка предикатів»;

змістовий модуль 6 «Основи комбінаторного аналізу»;

змістовий модуль 7 «Основи теорії кодування»;

змістовий модуль 8 «Основні поняття теорії графів» ;

змістовий модуль 9 «Елементи теорії формальних граматик»;

змістовий модуль 10 «Елементи теорії скінчених автоматів».

4.1.3 Тема 2 «Основні поняття і позначення теорії множин»

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

«об'єднання в одне ціле об'єктів, добре помітних нашою інтуїцією й думкою». Математичне поняття «множина» пов'язане з абстракцією. Сутність цієї

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

Вивчення теми «Основні поняття і позначення теорії множин» пов’язане із розглядом таких питань [1-9, 13-16, 20-23]: інтуїтивне поняття множини (кантеровська теорія множин, її парадокси); скінченні й нескінченні множини;

універсальна і порожня множини; способи задання множин; множина і підмножини, булеан множини.

Основними поняттями і визначеннями теорії множин, які надаються в [1- 4, 16, 20-23], є: множина, елемент множини, клас (сімейство), мультимножина,

23

упорядкована множина, кортеж, довжина (розмірність) кортежу, скінченні,

нескінченні, зчисленні множини, порожня множина, універсальна множина (універсум), способи задання множин, потужність множини, рівнопотужні множини, рекурсивно задана множина, підмножина, відношення приналежності і включення, властива і невластива підмножини, булеан множини, (множина-

степень).

4.1.4 Тема 3 «Алгебра множин»

Вивчення теми «Алгебра множин» пов’язане із розглядом таких питань [1-5, 7, 13, 14-16, 20-23]: геометрична інтерпретація множин (круги Ейлера і діаграми Венна); операції на множинах; загальне визначення алгебри, поняття алгебри множин; аксіоми алгебри множин; тотожні перетворення формул алгебри множин.

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

[1-5, 7, 14-16, 20, 22], є: теоретико-множинні операції (об’єднання множин, перетин множин, розбиття множини, різниця множин, доповнення

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

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

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

1.Що таке множина? Наведіть приклади різних множин.

2.Які способи задання множин Ви знаєте?

3.Що таке порожня множина? Обґрунтуйте необхідність використання порожньої множини.

4.Що таке універсальна множина? Наведіть приклади універсальних

множин.

5.Дайте визначення скінченної і нескінченної множини.

6.Дайте визначення зчисленної множини.

7.Що таке потужність множини?

8.Дайте визначення підмножини. Наведіть приклади підмножин.

9.Яке відношення між множинами називають строгим включенням, а

яке нестрогим включенням?

24

10.Чим відрізняється поняття включення ( або ) від поняття приналежності ( )?

11.У яких випадках можна говорити, що множини A, B і C рівні?

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

13.Яка пріоритетність виконання операцій над множинами?

14.Які способи графічної ілюстрації операцій над множинами Ви

знаєте?

15.Поясніть узагальнене поняття алгебри. Наведіть приклади алгебр.

16.Що таке алгебра множин?

17.Яка операція над множинами називається бінарною?

18.Яка операція над множинами називається унарною?

19.Назвіть основні аксіоми (закони) алгебри множин.

20.Які властивості має порожня множина та універсальна множина?

21.Опишіть принцип двоїстості в алгебрі множин, наведіть приклади двоїстих символів.

22.Поясніть способи перетворення формул алгебри множин.

4.2 Змістовий модуль 2 «Відношення та їх властивості»

4.2.1 Перелік тем змістовного модуля 2

Під час вивчення змістового модуля 2 розглядаються такі теми:

тема 1 «Відношення та операції над ними»;

тема 2 «Властивості бінарних відношень»;

тема 3 «Функціональні відношення»;

тема 4 «Елементи реляційної алгебри».

Розглядаючи в попередньому модулі «Введення в дисципліну. Основи теорії множин. Алгебра множин» основні положення про множину та її елементи, було використано наступне визначення, пропоноване групою видатних математиків, що виступають під псевдонімом Н. Бурбаки: «Множини утворюються з елементів, що мають деякими властивості й перебувають у деяких відносинах між собою або з елементами інших множин».

У даному змістовому модулі 2 «Відношення та їх властивості» пропонується формальний підхід для опису таких відношень.

25

У загальному значенні відношення означає який-небудь зв'язок між предметами або поняттями.

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

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

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

Уданому модулі дисципліни основна увага приділена опису властивостей

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

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

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

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

4.2.2 Тема «Відношення та операції над ними»

Вивчення теми «Відношення та операції над ними» пов’язане із розглядом таких питань [1-5, 7, 13, 16, 20-23]: декартів добуток множин; бінарні

26

та n-арні відношення; область визначення та область значень відношень;

способи задання відношень; операції над відношеннями.

Основними поняттями і визначеннями відношень та операцій над ними,

які надаються в [1-5, 7, 16, 20-23], є: декартів (прямий) добуток множин; декартова степінь; декартів квадрат, декартів куб множин; n-арне відношення;

унарне, бінарне відношення; область визначення відношення; область значень відношення; відповідність; повне, тотожне, порожнє відношення; матричний спосіб задання відношень; переріз відношень; фактор-множина; об’єднання, перетин, різниця, доповнення відношень; симетричне (обернене) відношення;

композиція відношень.

4.2.2 Тема «Властивості бінарних відношень»

Вивчення теми «Властивості бінарних відношень» пов’язане із розглядом таких питань [1-5, 7, 16, 20-23]: властивості бінарних відношень; класи бінарних відношень (відношення еквівалентності, порядку і толерантності).

Основними поняттями, пов’язаними з властивостями і класами бінарних відношень, які надаються в [1-5, 7, 16, 20, 22], є: рефлексивність, антирефлексивність, симетричність, антисиметричність, асиметричність,

транзитивність, антитранзитивність відношення; відношення еквівалентності; клас еквівалентності; система представників; відношення часткового порядку;

частково впорядкована множина; порівнянні та непорівнянні елементи відношень; лінійний порядок; лінійно впорядкована множина (ланцюг);

відношення нестрогого і строгого порядку; відношення толерантності.

4.2.3 Тема «Функціональні відношення»

Вивчення теми «Функціональні відношення» пов’язане із розглядом таких питань [1-5, 13, 16, 20-23]: поняття функціонального відношення;

способи задання функціональних відношень; поняття відображення (функції); область визначення та область значень функціональних відношень; основні типи відображень (функцій).

Основними поняттями, пов’язаними з функціональними відношеннями,

які надаються в [1-5, 16, 20, 22], є: функціональне відношення; функція; відображення; часткова функція; образ; прообраз; сюр’єктивна функція

(сюр’єктивне відображення); ін’єктивна функція (ін’єктивне відображення);

27

бієктивна функція (бієктивне відображення); взаємно однозначне відображення.

4.2.4 Тема «Елементи реляційної алгебри»

Вивчення теми «Елементи реляційної алгебри» пов’язане із розглядом таких питань [1, 20, 22]: зображення інформації у вигляді двовимірних таблиць

(реляційне зображення даних); реляційна модель даних; основні поняття реляційної алгебри; основна ідея реляційної алгебри; традиційні теоретико-

множинні операції реляційної алгебри; спеціальні операції реляційної алгебри. Основними поняттями, пов’язаними з основами реляційної алгебри, які надаються в [1, 20, 22], є: кортеж, домен, атрибут, реляційна алгебра, операція об’єднання, операція перетин, операція різниця, операція прямий добуток,

операція обмеження, операція проекція, операція натуральне з’єднання, операція ділення.

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

1.Як зв’язані між собою теорія множин і теорія відношень?

2.Поясніть поняття кортежу. Наведіть приклади кортежів.

3.Що таке «прямий» («декартів») добуток множин?

4.Як визначається потужність декартова добутку?

5.Що таке відношення множин?

6.Яке відношення називається n-арним, унарним, бінарним?

7.Що таке тотожне, повне і порожнє відношення?

8.Нехай A деяка множина. Що буде означати запис A1, A2 , A3 , An ?

9.Що є областю визначення та областю значення відношення R?

10.Наведіть характеристику способів задання відношень.

11.Які зі способів задання відношень використовуються для n-арних відношень, якщо n 2?

12.Перелічить операції над відношеннями.

13.Дайте визначення перерізу відношення R за елементом xi .

14.Що таке фактор-множина множини Y за відношенням R?

15.Назвіть специфічні операції над відношеннями.

16.Що таке композиція відношень? Наведіть приклади.

17.Що таке симетризація відношення?

28

18.Яке відношення називається оберненим?

19.Перелічить основні властивості відношень.

20.Що таке рефлексивність відношень? Наведіть приклади.

21.Яке відношення є антирефлексивним? Наведіть приклади.

22.Яке відношення є симетричним, а яке відношення є асиметричним?

23.Яке відношення є антисиметричним?

24.Яке відношення є транзитивним, а яке антитранзитивним?

25.Яке відношення в множині X називається відношенням еквівалентності?

26.Яке відношення в множині X називається відношенням нестрогого порядку, а яке називається відношенням строгого порядку?

27.Яке відношення називається функціональним?

28.Яке функціональне відношення називається всюди визначеним?

29.Як виглядає матриця функціонального відношення?

30.Яке функціональне відношення називають відображенням множини

Xв Y ?

31.Що таке сюр’єкція?

32.Яке відображення називається ін’єктивним?

33.Що таке бієкція?

34.Яке відображення називається взаємно однозначним?

35.Що називається образом елемента?

36.Що таке прообраз елемента?

37.Чим характеризується граф і матриця сюр’єктивного, ін’єктивного,

бієктивного відображення?

38.Перелічить основні властивості відображень.

39.Що являє собою реляційний метод побудови баз даних?

40.Що називається кортежем, атрибутом, доменом? Наведіть приклади.

41.Наведіть теоретико-множинні операції, що застосовуються при роботі з реляційними базами даних. Поясніть принцип їх виконання.

42.Назвіть спеціальні реляційні операції, які вам відомі. Поясніть принцип виконання кожної з них.

29

4.3 Змістовий модуль 3 «Алгебри (алгебраїчні структури)» 4.3.1 Перелік тем змістовного модуля 3

Під час вивчення змістового модуля 3 розглядаються такі теми:

тема 1 «Алгебраїчні операції та їх властивості»;

тема 2 «Поняття алгебраїчної структури»;

4.3.2 Тема 1 «Алгебраїчні операції та їх властивості»

Вивчення теми «Алгебраїчні операції та їх властивості» пов’язане із розглядом таких питань [1, 2, 4, 5, 16, 20]: види операцій; способи записів операцій; основні властивості операцій; операції додавання та множення за модулем.

Основними поняттями і визначеннями теми «Алгебраїчні операції та їх властивості», які надаються в [1, 2, 4, 5, 16, 20], є: операція, унарна операція, бінарна операція, n-арна операція, операнд, записи infix, prefix, postfix,

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

4.3.3 Тема 2 «Поняття алгебраїчної структури»

Вивчення теми 2 «Поняття алгебраїчної структури» пов’язане із розглядом таких питань [1, 2, 4, 5, 16, 20]: визначення алгебраїчної структури;

відношення між алгебраїчними структурами; визначення підструктура; морфізми (гомоморфізм, ізоморфізм); графічне визначення гомоморфізму;

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

Основними поняттями і визначеннями теми «Алгебраїчні операції та їх властивості», які надаються в [1, 2, 4, 5, 16, 20], є: алгебраїчна структура, носій алгебраїчної структури, підструктура, гомоморфізм, ізоморфізм, півгрупа, моноїд, група, абелева група, кільце, поле, гратка.

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

1. Дайте визначення операції і наведіть приклади операцій, що задані на різних множинах.

30