Опис дисципліни

Програму навчальної дисципліни «Дискретна математика» складено відповідно до освітньо-професійної програми підготовки бакалаврів за спеціальністю 113 Прикладна математика.

Навчальна дисципліна належить до циклу навчальних дисциплін природничонаукової підготовки.

Предмет навчальної дисципліни – дискретні математичні структури та їх властивості.

Міждисциплінарні зв’язки:

• дисципліна «Дискретна математика» забезпечує вивчення дисциплін «Математична логіка та теорія алгоритмів», «Обчислювальна геометрія та комп’ютерна графіка», «Методи оптимізації», «Забезпечення якості ПЗ», «Дослідження операцій» , «Бази даних та інформаційні системи», «Методи штучного інтелекту» навчального плану підготовки бакалаврів за спеціальністю 113 Прикладна математика, а також дисциплін «Нечітка математика», «Еволюційні обчислення» та «Інтелектуальний аналіз даних» навчального плану підготовки магістрів за спеціальністю 113 Прикладна математика.

1. Мета та завдання навчальної дисципліни

1.1. Мета навчальної дисципліни

Метою навчальної дисципліни є формування у студентів здатностей:

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

 1.2. Основні завдання навчальної дисципліни

Згідно з вимогами освітньо-професійної програми, студенти після засвоєння дисципліни «Дискретна математика» мають продемонструвати такі результати навчання:

знання:

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

уміння:

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

досвід:

• визначення властивості дискретних математичних об’єктів;
• розв’язання задач булевої алгебри;
• синтезу та аналізу абстрактних автоматів та мереж Петрі.

2. Структура навчальної дисципліни

На вивчення дисципліни «Дискретна математика» відводиться 225 годин / 7,5 кредитів ECTS. Навчальна дисципліна містить кредитні модулі:

1) «Дискретна математика 1. Теорія множин»

2) «Дискретна математика 2. Комбінаторика»

Рекомендований розподіл навчального часу

Форма навчання

Кредитні модулі

Всього

Розподіл навчального часу за видами занять

Семестрова атестація

Розподіл аудиторних годин на тиждень

за курсами і семестрами

кредитів

годин

Лекції

Практичні

заняття

СРС

І

I
ІІ

Денна

Всього

6,5

195

72

72

51

1

3

90

36

36

18

Екзамен

4
 

2

3,5

105

36

36

33

Екзамен

 
4

3. Зміст навчальної дисципліни

Кредитний модуль 2. ДИСКРЕТНА МАТЕМАТИКА-2. КОМБІНАТОРИКА

РОЗДІЛ 1. ЕЛЕМЕНТИ КОМБІНАТОРИКИ. АЛГЕБРА БУЛЕВИХ ФУНКЦІЙ.

Тема 1.1. Елементи комбінаторики. Абстрактна алгебра Буля.

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

РОЗДІЛ 2. ЗМІСТОВНІ ТА АБСТРАКТНІ ТЕОРІЇ.

Тема 2.1. Алгебра висловлювань як модель булевої алгебри.

Тема 2.2. Числення висловлювань.

РОЗДІЛ 3. ОСНОВИ ТЕОРІЇ АВТОМАТІВ.

Тема 3.1. Абстрактні автомати.

Тема 3.2. Мережі Петрі. 

4. Рекомендований перелік практичних занять

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

Кредитний модуль 2. ДИСКРЕТНА МАТЕМАТИКА-2. КОМБІНАТОРИКА

• Дослідження булевих формул і функцій.
• Дослідження повноти систем булевих функцій.
• Мінімізація булевих функцій.
• Дослідження тавтологій логіки висловлювань.
• Доведення і застосування похідних правил виводу.
• Побудова найпростіших кінцевих автоматів.
• Моделювання процесів мережами Петрі.

5. Рекомендована література 

5.1. Базова література

1. Таран Т. А. Основы дискретной математики. Учебное пособие. К.: Просвіта. – 2003. – 287c.

2. Таран Т. А. Основы математической логики. К.: КПИ. – 1996. –с. 64.

3. Бардачов Ю.М., Соколова Н.А., Ходаков В.Є. Дискретна математика. – К.: Вища школа. 2002. - 287с.

4. Нікольський Ю.В., Пасічник В.В., Щербина Ю.М. Дискретна математика. К.: Видавнича група BHV. 2007.- 368 с.

5. Темнікова О.Л. Дискретна математика: методичні вказівки до практичних занять з дисципліни «Дискретна математика» для студентів напряму підготовки 6.040301 «Прикладна математика» [Електронне видання] / О.Л.Темнікова – К. : НТУУ «КПІ», 2013. – 56 с.

6. Новиков Ф.А. Дискретная математика для программистов. 2ое издание. Учебник для ВУЗов. СПб.: Питер. – 2006. – 368c.

7. Мендельсон Э. Введение в математическую логику. –- М.: Наука, 1976.

8. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М. : Наука, 1975.

9. Шапорев С.Д. Дискретная математика. Курс лекций и практических занятий. СПб.: “БХВ – Петербург”. – 2006.- 396c.

5.2. Допоміжна література

1. Берж К. Теория графов и ее приложения. – М.: Изд. Иностр. Лит., 1962.

2. Биркгоф Г. Теория решеток. – М.: Наука. 1984. 568 с.

3. Гильберт Д., Бернайс П. Основания математики. Логические исчисления и формализация арифметики. –- М.: Наука. 1979.

4. Гиндикин С. Г. Алгебра логики в задачах. – М.: Наука. 1972.

5. Горбатов В. А. Основы дискретной математики. М.:Высш.шк,1986-311 с.

6. Ершов Ю.А., Палютин Е.А. Математическая логика.–М.: Наука, 1979.

7. Клини С. К. Введение в метаматематику. М.: Мир. 1957.

8. Клини С. К. Математическая логика. - М.: Мир, 1973.

9. Коэн П. Дж. Теория множеств и континуум-гипотеза. – М.: Мир. 1973.

10. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. –- М.: Энергия. 1980.

11. Куратовский К., Мостовский А. Теория множеств. – М.: Мир. 1970.

12. Нефедов В. Н., Осипова В. А. Курс дискретной математики. –- М.: МАИ. 1992.

13. Оре О. Теория графов. – М.: Наука, 1968.

14. Столл Р. Множество, логика, аксиоматические теории. – М.: Просвещение, 1968.

15. Харари Ф. Теория графов. – М.: Мир, 1973.

16. Хаусдорф Ф. Теория множеств. – М.: ОНТИ, 1937.

17. Черч А. Введение в математическую логику - М.: ИЛ. т.1. 1961.