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

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

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

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

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

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

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

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

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

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

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

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

знання:

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

уміння:

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

досвід:

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

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

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

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

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

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

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

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

РОЗДІЛ 1. МОВА МАТЕМАТИЧНИХ ТВЕРДЖЕНЬ. ТЕОPІЯ МНОЖИН, ВІДНОШЕНЬ І ВІДОБРАЖЕНЬ.

Тема 1.1. Мова математичних тверджень. Теорія множин.

Тема 1.2. Теорія відношень.

Тема 1.3. Відображення і функції.

Тема 1.4. Потужність множин. Кардинальна арифметика.

РОЗДІЛ 2. ТЕОРІЯ РЕШІТОК.

Тема 2.1. Відношення порядку.

Тема 2.2. Решітки та їх властивості.

Тема 2.3. Будова і теорія представлення.

РОЗДІЛ 3. ТЕОРІЯ ГРАФІВ.

Тема 3.1. Основні поняття теорії графів і їх властивостей.

Тема 3.2. Матричні методи дослідження графів.

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

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

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

• Змістовна теорія множин. Алгебра множин.
• Дослідження властивостей відношень.
• Дослідження відображень.
• Визначення потужності. Кардинальні числа.
• Дослідження властивостей відношення порядку. Відображення впорядкованих множин.
• Побудова функціональних відображень множин і решіток.
• Представлення графів. Дослідження зв’язності графів.
• Дослідження планарності графів, збалансованості дерев.
• Знаходження відстаней та дослідження зв’язності матричними методами. 

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.