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

Дискретна математика — галузь математики, що вивчає властивості будь-яких дискретних структур. Як синонім іноді вживається термін дискретний аналіз, що вивчає властивості структур скінченного характеру. До таких структур може бути віднесено скінченні групи, скінченні графи, а також деякі математичні моделі перетворювачів інформації. Розділ дискретної математики, що вивчає їх, називається скінченною математикою. Іноді саме це поняття розширюють до дискретної математики. Крім скінченних структур, дискретна математика вивчає деякі системи алгебри, нескінченні графи, обчислювальні схеми певного вигляду.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекурентні співвідношення

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

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

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

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

Тема 1. Основні означення. Означення графа. Способи задання графа. Різновиди графів.

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

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

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

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

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

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