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

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

ХАРКIВСЬКИЙ НАЦІОНАЛЬНИЙ УНIВЕРСИТЕТ РАДIОЕЛЕКТРОНIКИ

МЕТОДИЧНІ ВКАЗІВКИ до самостійної роботи з дисципліни

«ДИСКРЕТНА МАТЕМАТИКА»

для студентів усіх форм навчання напряму 6.050101 Комп’ютерні науки

Електронне видання

ЗАТВЕРДЖЕНО кафедрою «ІУС».

Протокол № 1 від 29.08.2013 р.

Харків 2013

Методичні вказівки до самостійної роботи з дисципліни «Дискретна математика» для студентів усіх форм навчання напряму 6.050101 – Комп’ютерні науки [Електронне видання] / Упоряд.: Н.В. Васильцова, Л.Е. Чала. – Харків: ХНУРЕ, 2014. – 66 с.

Упорядники: Н.В. Васильцова, Л.Е. Чала

ЗМІСТ

Вступ…………………………………………………………………………. 4 1 Мета і задачі дисципліни ………………………………………………… 5

1.1Мета викладання дисципліни ………………………………………….. 5

1.2Програма знань та умінь ……………………………………………….. 5 2 Робоча програма дисципліни …………………………………………….. 6

2.1Лекційні заняття ………………………………………………………… 6

2.2Практичні заняття………………………………………………...……... 15

2.3Розділи програми для самостійного вивчення ……………………….. 16

2.4Навчально-методичні матеріали з дисципліни ……………………….. 17

3	Характеристика підручників і навчальних посібників …………………	19
4	Методичні вказівки з вивчення змістових модулів
дисципліни «Дискретна математика»……………………………………...		22

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

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

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

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

Двійкова логіка. Булеві функції та перетворення»..………………………. 31

4.5Змістовий модуль 5 «Логіка висловлень і логіка предикатів»……….. 38

4.6Змістовий модуль 6 «Основи комбінаторного аналізу»………………. 43

4.7 Змістовий модуль 7 «Основи теорії кодування»……………………… 49

4.8Змістовий модуль 8 «Основні поняття теорії графів»..……………...... 50

4.9Змістовий модуль 9 «Елементи теорії формальних граматик»..……... 62

4.10Змістовий модуль 10 «Елементи теорії скінченних автоматів»………. 63 5 Основні рекомендації з організації самостійної роботи ……………….. 65

3

ВСТУП

Дисципліна «Дискретна математика» входить до складу дисциплін циклу природничо-наукової підготовки бакалаврів з напряму 6.050101 – «Комп’ютерні науки» і є однією з базових математичних дисциплін цього циклу.

Матеріал, який пропонується для вивчення дисципліни, складається з таких розділів: «Основи теорії множин. Алгебра множин»; «Відношення та їх властивості»; «Алгебри (алгебраїчні структури)»; «Основи математичної логіки. Двійкова логіка. Булеві функції та перетворення»; «Логіка висловлень і логіка предикатів»; «Основи комбінаторного аналізу»; «Основи теорії кодування»; «Основні поняття теорії графів»; «Елементи теорії формальних граматик»; «Елементи теорії скінченних автоматів».

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

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

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

управляючих систем і систем штучного інтелекту.

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

Для вивчення дисципліни «Дискретна математика» студент повинен мати знання математики в обсязі середньої школи і деякі основні поняття з розділів дисципліни з вищої математики.

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

4

1 МЕТА І ЗАДАЧІ ДИСЦИПЛІНИ

1.1 Мета викладання дисципліни

Метою викладання дисципліни є:

ознайомлення студентів з основними базовими поняттями, ідеями і методами подання та обробки дискретної інформації;

надання положень дискретної математики як інструментарію при обробці інформації з використанням сучасної комп’ютерної техніки;

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

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

1.2Програма знань та умінь

Завдання: за результатом вивчення дисципліни студенти повинні:

Знати:

історію розвитку математичного апарату, орієнтованого на формалізацію дискретних процесів;

методи та засоби дискретної математики в галузі опису та формалізації дискретних процесів (мову теорії множин, відношень,

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

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

Вміти:

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

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

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

5

використовувати мову графів для опису програмних моделей в інформаційних системах та інформаційних технологіях;

виконувати синтез та аналіз графових структур та алгоритмів на них;

вирішувати типові задачі теорії множин і теорії відношень,

комбінаторного аналізу, теорії графів, булевої алгебри та математичної логіки. Володіти (перелік компетенцій): базовими знаннями в області дискретної математики, уміннями застосовувати ці знання в науково-дослідній і професійній діяльності; здатністю аналізувати та синтезувати науково-

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

2 РОБОЧА ПРОГРАМА ДИСЦИПЛІНИ

2.1 Лекційні заняття

Кількість годин

Назви змістових

денна форма

Заочна форма

Усь-

у тому числі

Усь-

у тому числі

модулів і тем

го

л

п

лб

конс

с.р.

ого

л

п

лб

конс

с.р

.

1

2

3

4

5

6

7

8

9

10

11

12

13

Модуль 1

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

Тема 1.

Мета і задачі

8

2

1

3

6

1

4

дисципліни, її місце в

системі

підготовки

фа-

хівців з комп'ютерних

наук. Основні поняття і

4

2

позначення

теорії

мно-

жин. Інтуїтивне поняття

множини. Елементи мно-

жини.

Скінченні

та

нескінченні

множини.

Універсальна

і порожня

6

множини.

Способи

задання

множин.

Потужність

множин.

Множина і підмножини.

Тема

2.

Алгебра

7

2

3

6

5

множин.

Геометрична

інтерпретація

множин:

кола Ейлера та діаграми

Венна.

Операції

на

множинах. Загальне ви-

значення алгебри. Понят-

тя

алгебри

множин.

Аксіоми

алгебри

мно-

жин. Принцип двоїстості.

Тотожні

перетворення

формул алгебри множин.

Тема 3. Історія зарод-

0,5

0,5

3

3

ження,

розвитку

і

становлення дискретної

математики.

Внесок

вчених

у

її

розвиток.

(сам. роб)

Разом за зміст. модулем 1

15,5

4

4

1

6,5

15

1

2

12

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

Тема 1.

Відношення та

8

2

1

3

7

1

5

операції

над

ними.

Декартів

добуток

мно-

жин. Поняття відношень-

ня. Бінарні та n-арні

відношення.

Область

визначення

та

область

значень

відношення.

Способи

задання

відношень.

Операції над

відношеннями.

Тема

2.

Властивості

7

2

4

3

5

2

4

бінарних

відношень.

Рефлексивність,

антире-

флексивність,

симетри-

чність,

антисиметрич-

ність,

асиметричність,

транзитивність,

анти-

транзитивність

відно-

шень.

Класи

бінарних

відношень.

Відношення

еквівалентності.

Класи

еквівалентності.

Відно-

шення порядку. Відно-

шення толерантності.

Тема 3.

Функціональні

5,5

1

2

2,5

3

3

відношення.

Області

7

визначення

і

значень.

Функції

і

відображення.

Типи

відображень:

сюр'єкція,

ін'єкція,

бієкція.

Тема

4.

Елементи

1,5

1

0,5

3

3

реляційної

алгебри.

Реляційна модель даних.

Поняття

реляційної

алгебри.

Операції

реляційної алгебри.

Разом за зміст. модулем 2

22

6

6

1

9

18

1

2

15

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

Тема

1.

Алгебраїчні

1,5

1

0,5

3

3

операції та їх власти-

вості. Унарна, бінарна, n-

арна

операція.

Способи

записів операцій. Основ-

ні властивості

операцій.

Операції

додавання

та

множення

за

модулем.

(сам. роб.)

Тема 2. Поняття алгебра-

1

1

3

3

їчної структури Підстру-

ктура. Морфізми (гомо-

морфізм,

ізоморфізм).

Найпростіші алгебраїчні

структури. Кільці і поля.

Гратки. (сам. роб.)

Разом за зміст. модулем 3

2,5

1

1,5

6

6

Усього годин за мод. 1

40

10

10

3

17

39

2

4

33

Модуль 2

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

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

Тема 1.

Булеві функції

8

2

2

1

3

9

1

2

6

(основні

поняття).

Булева

алгебра.

Булеві

змінні і функції. Область

визначення

та

область

значень булевий функій.

Способи

задання

буле-

вих

функцій. Реалізація

булевих функцій форму-

лами. Елементарні функ-

ції

алгебри

логіки.

Двоїстість.

Двоїсті

та

самодвоїсті

булеві

функції.

Принцип

двоїстості.

Закони

і

тотожності

булевої

алгебри.

Еквівалентні

8

перетворення

формул

булевої алгебри.

Тема

2.

Нормальні

7

2

2

3

3

3

форми

булевих

функ-

цій. Основні поняття.

Нормальні

форми:

диз'юнктивна нормальна

форма (ДНФ), кон’юн-

ктивна нормальна форма

(КНФ).

Досконалі

нормальні форми (ДДНФ,

ДКНФ). Диз’юнктивні та

кон’юнктивні розкладан-

ня булевих

функцій.

Перехід

від

таблиці

булевої

функції

до

формули алгебри логіки і

навпаки.

Тема

3.

Мінімізація

7

2

2

3

3

3

булевих

функцій.

Основні поняття. Кри-

терії мінімізації. Основні

методи мінімізації буле-

вих

функцій.

Метод

мінімізуючих

карт

(діаграми Карно-Вейча).

Тема

4.

Алгебра

3,5

1

2

1,5

3

3

Жегалкіна.

Структура і

тотожністі

алгебри

Жегалкіна.

Поліном

Жегалкіна

та

правило

його

побудови.

Лінійні

булеві функції.

Тема 5. Функціональна

3,5

1

1,5

3

3

повнота

наборів

буле-

вих

функцій.

Типи

булевих функцій. Замк-

нені

класи

булевих

функцій. Поняття повно-

ти набору булевих функ-

цій. Теореми Поста про

функціональну

повноту

набору булевих функцій.

Тема 6. Логічні схеми.

0,5

-

0,5

3

3

Синтез

комбінаційних

схем. Перемикальні лан-

цюги; двох- і багато-

ступінчасті

комбіна-

ційні схеми. (сам. роб.)

Тема

7. Багатозначна

0,5

-

0,5

3

3

логіка. Основні поняття і

функції k-значної логіки.

9

(сам. роб.)

Разом за зміст. модулем 4

30

8

8

1

13

27

1

2

24

Змістовий модуль 5. Логіка висловлень і логіка предикатів.

Тема

1.

Висловлення.

4,5

1

2

1

1,5

9

1

2

6

Алгебра

висловлень.

Висловлення

(основні

поняття). Логічні зв'язки

і формули логіки вісло-

влень. Побудова склад-

них

формул.

Алгебра

логіки і логіка вислов-

лень. Інтерпретація фор-

мул логіки

висловлень.

Правильні

міркування.

Логічна еквівалентність і

логічний наслідок.

Тема

2.

Обчислення

5

2

2

3

3

висловлень. Аксіоми та

повнота

обчислення

логіки висловлень. Вис-

новки

в

обчисленні

висловлень.

Дедуктивні

висновки

у

логіці

висловлень.

Несупереч-

ність, незалежність.

Різні

аксіоматизації

обчислення висловлень.

Тема

3.

Предикати.

6

2

2

1

2

3

3

Алгебра

предикатів.

Основні

поняття

логіки

предикатів.

Операції

логіки

предикатів.

Кванторні

операції.

Формули

та

їх

інтерпретація

у

логіці

преди-катів. Закони і

тотожності

логіки

предикатів.

Виперед-

жені нормальні форми.

Тема

4.

Обчислення

3,5

1

1,5

3

3

предикатів.

Логічний

висновок

у

логіці

предикатів.

Разом за зміст. модулем 5

19

6

4

2

7

18

1

2

15

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

Тема 1. Історія розвит-

1,5

-

1

0,5

4

1

3

ку

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

Класичні

задачі

комбінаторного

аналізу.

Сучасні

задачі,

які

10