Навчальний курс "Дискретна математика 2"

Назва курсу

Дискретна математика

---

Галузь знань: 12 Інформаційні технології

Напрям підготовки:122 Комп'ютерні науки та інформаційні технології

Освітньо-кваліфікаційний рівень: бакалавр

Мета та завдання навчального курсу

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

Завдання: навчити студентів використовувати апарат дискретної математики для розв’язування практичних задач, що пов’язані з розробкою програмних комплексів для ЕОМ та створенням алгоритмів вирішення прикладних проблем.

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

знати:

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

вміти:

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

Робоча програма курсу

Автори курсу

Болілий Василь Олександрович

Ганенко Людмила Дмитрівна

---

Графік консультацій

Понеділок	Середа	Четвер
1400-1520	1240-1400	1400-1520

Учасники

Сторінка координування курсу "Дискретна математика 2"

---

Графік навчання

Змістовий модуль 1

Теорія множин

Тема 1. Множини і операції над ними. Вступ. Мета і завдання курсу. Поняття множини. Способи задання множини. Операції над множинами. Діаграми Ейлера-Венна. Властивості операцій над множинами. Булеан множини.

Тема 2. Відношення. Декартовий добуток множин. Поняття відношення. Способи задання бінарних відношень. Операції над відношеннями. Властивості бінарних відношень. Відношення еквівалентності. Відношення порядку. Реляційна модель даних.

Тема 3. Функціональні відношення. Означення функціонального відношення. Типи функціональних відношень

Тема 4. Потужність множини. Потужність множини. Потужність N. Потужність Z. Потужність Q. Потужність R. Незліченість множини дійсних чисел. Кардинальні числа.

Тема 5. Аксіоматика множини натуральних чисел. Аксіоми Пеано. Принципи математичної та трансфінітної індукції. Застосування методу математичної індукції до розв’язання основних типів задач.

Змістовий модуль 2

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

Тема 1. Булеві функції. Елементарні булеві функції. Булеві вектори. Число булевих векторів. Булеві функції. Табличне задання функцій. Булеві функції і формули. Суперпозиція булевих функцій. Рівносильні формули. Закони булевої алгебри. Фіктивні і суттєві змінні в булевих функціях. Двоїсті функції і двоїсті формули.

Тема 2. Нормальні (канонічні) форми булевих функцій. Нормальні форми. Досконалі нормальні форми. Способи побудови нормальних форм.

Тема 3. Поліноми Жегалкіна. Алгебра Жегалкіна. Поліноми Жегалкіна. Представлення булевих функцій поліномами Жегалкіна.

Тема 4. Повнота та замкненість булевих функцій. Повнота системи булевих функцій. Приклади повних систем. Замкнені класи булевих функцій. Критерій повноти Поста.

Тема 5. Мінімізація булевих функцій. Основні поняття. Мінімізація булевих функцій методом карт Карно.

Змістовий модуль 3

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

Тема 1. Суми та добутки. Позначення сум. Перетворення сум. Загальні методи сумування. Позначення добутків. Факторіал. Перетворення добутків.

Тема 2. Найпростіші комбінаторні об’єкти. Правила суми і добутку. Основні комбінаторні схеми. Розміщення без повторень. Перестановки без повторень. Комбінації без повторень. Розміщення з повтореннями. Перестановки з повтореннями. Комбінації з повтореннями.

Тема 3. Комбінаторні тотожності. Тотожності для біноміальних коефіцієнтів. Трикутник Паскаля. Біном Ньютона. Поліноміальна формула. Формула включень та виключень.

Тема 4. Подільність чисел. Відношення подільності. Прості числа. Взаємнопрості числа. Відношення конгруенції. Лишки.

Тема 5. Спеціальні функції та числа. Цілочисельні функції. Числа Стірлінга. Числа Ейлера. Числа Бернуллі. Числа Фібоначчі.

Тема 6. Рекурентні співвідношення. Задачі, що приводять до рекурентних співвідношень. Лінійні рекурентні співвідношення та їх розв’язання. Нелінійні рекурентні співвідношення.

Тема 7. Твірні функції. Означення твірних функцій. Таблиця елементарних твірних. Операції над твірними функціями. Обчислення твірних функцій. Застосування твірних функцій.

Змістовий модуль 4

Теорія графів

Тема 1. Основні означення. Означення графа. Способи задання графа. Різновиди графів. Матриці суміжностей і досяжності. Матриця інцидентності. Ізоморфізм графів. Операції над графами. Ототожнення (злиття) вершин, стягування ребра, роздвоєння (розщеплення) вершини. З’єднання графів, доповнення графа. Властивості графів. Властивості регулярних графів. Властивості двочастинних (дводольних) графів.

Тема 2. Зв’язні графи. Маршрути, цикли, зв’язність. Властивості зв’язних графів.

Тема 3. Ейлерові графи. Теорема Ейлера. Властивості ейлерових графів.

Тема 4. Планарність і укладання графів. Плоскі та планарні графи. Укладання графів. Критерій Понтрягіна-Куратовського планарності графа.

Тема 5. Дерева. Дерева та їх властивості. Перелічення дерев. Остови (каркаси) графа. Основні поняття орграфів. Бінарні відношення і орграфи. Орієнтовані дерева та їх властивості.

Тема 6. Найкоротші відстані та шляхи у графах. Початкові поняття. Гамільтонові цикли і шляхи. Задача комівояжера.

Змістовий модуль 5

Теорія скінченних автоматів

Тема 1. Представлення подій в автоматах. Події та їх представлення в автоматах. Композиція автоматів. Означення автомата з однією стрічкою. Проблеми пустоти та нескінченності. Означення магазинного автомата.

Тема 2. Алгоритми сортування. Пірамідальне сортування.

Зміст курсу

Змістовий модуль 3. Комбінаторика

Тема 1. Суми та добутки. Позначення сум. Перетворення сум. Загальні методи сумування. Позначення добутків. Факторіал. Перетворення добутків.

Теоретичний матеріал

Лекція №1

Тема 2. Найпростіші комбінаторні об’єкти. Правила суми і добутку. Основні комбінаторні схеми. Розміщення без повторень. Перестановки без повторень. Комбінації без повторень. Розміщення з повтореннями. Перестановки з повтореннями. Комбінації з повтореннями.

Теоретичний матеріал

Лекція №1

Самостійна робота

Самостійна робота №1

Тема 3. Комбінаторні тотожності. Тотожності для біноміальних коефіцієнтів. Трикутник Паскаля. Біном Ньютона. Поліноміальна формула. Формула включень та виключень.

Теоретичний матеріал

Лекція №1

Практичні завдання

Практична робота №1

Тема 6. Рекурентні співвідношення. Задачі, що приводять до рекурентних співвідношень. Лінійні рекурентні співвідношення та їх розв’язання. Нелінійні рекурентні співвідношення.

Практичні завдання

Практична робота №1

Тема 7. Твірні функції. Означення твірних функцій. Таблиця елементарних твірних. Операції над твірними функціями. Обчислення твірних функцій. Застосування твірних функцій.

Практичні завдання

Практична робота №1

Практична робота №2

Самостійна робота

Самостійна робота №1

Змістовий модуль 4. Теорія графів

Тема 1. Основні означення. Означення графа. Способи задання графа. Різновиди графів. Матриці суміжностей і досяжності. Матриця інцидентності. Ізоморфізм графів. Операції над графами. Ототожнення (злиття) вершин, стягування ребра, роздвоєння (розщеплення) вершини. З’єднання графів, доповнення графа. Властивості графів. Властивості регулярних графів. Властивості двочастинних (дводольних) графів.

Практичні завдання

Практична робота №1

Тема 2. Зв’язні графи. Маршрути, цикли, зв’язність. Властивості зв’язних графів.

Практичні завдання

Практична робота №1

Тема 3. Ейлерові графи. Теорема Ейлера. Властивості ейлерових графів.

Практичні завдання

Практична робота №1

Тема 6. Найкоротші відстані та шляхи у графах. Початкові поняття. Гамільтонові цикли і шляхи. Задача комівояжера.

Самостійна робота

Самостійна робота №1

Ресурси

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

• 

  Айгнер М.

• 

  Ахо А.

• 

  Бардачов Ю.

• 

  Белоусов А.

Базова

1. Айгнер М. Комбинаторная теория: пер. с англ. – М. Мир, 1982 – 558 с.
2. Ахо А., Хопкрофт В., Ульман Дж. Структуры данных и алгоритмы. – М.: Издательский дом «Вильямс», 2003. – 384 с.
3. Бардачов Ю. М. Дискретна математика : підруч. для студ. ВНЗ / Ю. М. Бардачов, Н. А. Соколова. В. Є. Ходаков ;за ред. В. Є. Ходакова. - 2-е вид., перероб. і доп. - К. : Вища шк., 2007. – 383 с.
4. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. для вузов / Под. ред. В.С. Зарубина, А.П. Крищенко. – 3-е изд., стереотип. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. – 744 с. (Сер. Математика в техническом университете; Вып. ХІХ).
5. Бордачков Ю.М. та ін. Дискретна математика: Підручник/ Ю.М. Бардачков, Н.А.Соколова, В.Є. Ходаков; За ред. В.Є. Ходакова. – К.: Вища шк., 2002. – 287 с.
6. Глибовець М.М. Основи комп’ютерних алгоритмів. – К.: Вид. дім «КМ Академія», 2003. – 452 с.
7. Глушков В.М. Введение в кибернетику. – К.: Изд-во АН УССР, 1964.
8. Грэхэм Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики - М.: Мир, 1998. – 703 с.
9. Донской В.И. Дискретная математика. – Симферополь: Издательство «СОНАТ», 2000. – 360 с.
10. Ежов И.И., Скороход А.В., Ядренко М.И. Элементы комбинаторики. М.: Главная редакция физико-математической литературы издательства «Наука», 1977 – 80 с.
11. Ерош И.Л. Дискретная математика. Булева алгебра, комбинационные схеми, преобразования двоичных последовательностей: Учеб пособие / СПбГУАП. СПб., 2001. – 30 с.
12. Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцький Г.М., Печурін М.К. Основи дискретної математики: Підручник. – К.: «Наукова думка», 2002. – 579 с.
13. Колмогоров А.М., Фомін С.В. Елементи теорії функцій і функціонального аналізу. – К.: Вища школа,1974. – 456 с.
14. Комп’ютерна дискретна математика: Підручник/ М.Ф.Бондаренко, Н.В.Білоус, А.Г.Руткас. – Харків: «Компанія СМІТ», 2004. – 480 с.
15. Кривий С. Л. Збірник задач з дискретної математики : навч. посіб. для студ. ВНЗ / С. Л. Кривий , О. М. Ходзінський. - К. : Бізнесполіграф, 2008. - 360 с
16. Шоломов Л.А. Основи теории дискретных логических и вычислительных устройств.– М.: Наука. Главная редакция физико-математической литературы, 1980. – 400 с.
17. Ядренко М. Й. Дискретна математика : навч. посіб. для студ. ВНЗ / М. Й. Ядренко. - К. : ТВіМС, 2004. - 245 с. Примірників всього: 9
18. Ядренко М.Й. Дискретна математика: навчальний посібник. – К.: МП «ТВіМС», 2004. – 245 с.

Допоміжна

1. Акимов О.Е. Дискретная математика: логика, группы, графы. 2-е изд., дополн. – М.: Лаборатория Базовых Знаний, 2001 – 376 с.
2. Белов В.В. и др. Теория графов. – М.: «Высшая школа», 1976. – 392 с.
3. Виленкин Н.Я. Комбинаторика. – М.: Наука, 1969. – 328 с.
4. Глушков В.М. Синтез цифровых автоматов. – М.: Физматгиз, 1962. – 476 с.
5. Горбатов В.А. Основы дискретной математики: Учеб. Пособие для студентов вузов. – М.: Высш. шк., 1986. – 311 с.
6. Емеличев В.А. и др. Лекции по теории графов. – М.: Наука, 1990. – 384 с.
7. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. Пособие. – М.: Лаборатория Базовых Знаний, 2002. – 288 с.
8. Калужнин Л.А. Введение в общую алгебру. М.: Наука, 1973. – 448 с.
9. Кормен Т., Лейзерсон Ч. Ривест Р. Алгоритмы: построение и анализ. М: МЦНМО, 2001 – 960с.
10. Кофман А. Введение в прикладную комбинаторику. – М.: Наука, 1975. – 480 с.
11. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергия, 1980 – 344 с.
12. Кулаков Ю.В., Шамкин В.Н. Дискретная математика: Учебное пособие. Тамбов: Изд-во Тамб. Гос. Техн. Ун-та, 2004. – 80 с.
13. Липский В. Комбинаторика для программистов. – М.: Мир, 1988. – 213 с.
14. Мендельсон Э. Введение в математическую логику. М: Наука, 1984. – 320с
15. Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2001. – 304 с.
16. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – М.: Мир,1980. – 476 с.
17. Сачков В.Н. Введение в комбинаторные методы дискретной математики. – М.: Наука, 1982. – 384 с.
18. Трахтенброт Б.А., Бардзинь Я.М. Конечные автоматы (поведение и синтез). – М.: Наука, 1970. – 400 с.
19. Ядренко М.Й., Оленко А.Я. Дискретная математика. Навчально-методичний посібник. – К., 1995. – 83 с.

Інформаційні ресурси

Вікі-портал КДПУ

Вікіпедія

---