Код: 316152

Назва:

Додаткові розділи дискретної математики

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

Тип дисципліни: вибіркова (професійно-орієнтована)

Рік навчання: 1

Семестр: 2

Кількість кредитів: 5

Форма контролю: залік

Викладач(і): ст. в., к.н. Тимошкевич Л.М.

Результати навчання: у результаті вивчення дисципліни студент повинен
знати:
- способи опису множини та її елементів, операцій над множинами;
- властивості відношень, способи задання відношень, бінарні відношення еквівалентності, часткового порядку, функціональні відношення;
- поняття потужності множини, основні кардинальні числа;
- типи та композиції відображень;
- способи задання графів, операцій над графами;
- властивості різних типів графів (зв'язані графи, дводольні графи, дерева, ейлерові графи, гамільтонові графи);
- теореми Куратовського, Ейлера;
- основні типи задач комбінаторного аналізу;
- визначення понять: перестановки, розміщення, комбінації елементів;
- метод твірних функцій;
- основи теорії автоматів, властивості автоматів, типи автоматів (скінчені автомати, автомати з магазинною пам'яттю);
вміти:
- виконувати дії над елементами множини;
- використовувати діаграми Вена або кола Ейлера;
- описувати типи відношень;
- визначити області значення та області визначення відношень;
- використовувати аксіоми порядку для визначення властивостей відношень;
- використовувати графи для моделювання різних об'єктів;
- виконувати операції над графами;
- використовувати теореми Ейлера, Куратовського, для розв'язування прикладних задач;
- розраховувати перестановки, розміщення, комбінації та використовувати їх в конкретних задачах;
- застосовувати елементи комбінаторного аналізу до комбінаторних систем з оптимальним розподілом елементів;
- використовувати біномінальні коефіцієнти для генерування к-елементних підмножин;
- використовувати приклади скінчених автоматів для моделювання реальних об'єктів.




Спосіб навчання: аудиторний

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

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


Рекомендована література: 1.Боднарчук Ю. В., Олійник Б. В. Основи дискретної математики: Навч. посіб. - К.: Вид. дім "Києво-Могилянська академія", 2009. - 159 с.
2.Виленкин Н. Я. Индукция. Комбинаторика. - М.: Просвещение, 1976.
3.Грэхем З., Кнут Д., Паташник О. Конкретная математика. Основание ин-форматики. - М.: Мир, 1998. - 703 с.
4.Новиков Ф. А. Дискретная математика для программистов. - СПб: Питер, 2000. - 304 с.
5.Оленко А. Я., Ядренко М. Й. Дискретна математика: Навч.-метод. посіб. - К.: НаУКМА, 1996. - 83 с.
6.Дяченко С. М., Морозов Д. І. p-адичні числа і групи автоморфізмів кореневих дерев: навч. посіб./ С. М. Дяченко. - К.: НаУКМА, 2016. - 60 с.

Форми та методи навчання: лекції, семінари, самостійне виконання індивідуальних завдань

Методи й критерії оцінювання: Знання з курсу оцінюються за 100-бальною рейтинговою системою шляхом оцінювання виконання видів роботи протягом семестру: контрольна робота самостійна робота колоквіум та складання заліку

Мова навчання: українська