Дисципліна: Дискретні структури

Кількість годин (кредитів ЄКТС): 120 (4)

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

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

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

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

Результат вивчення навчальної дисципліни:

- засвоїти основні поняття дискретної математики;

- вивчити теоретичні методи аналізу і синтезу дискретних об’єктів, що застосовуються при проектуванні сучасних засобів обчислюваної техніки;

- набути практичних навичок щодо їх використання.

Дисципліна базується на знаннях, отриманих у середній школі та початкових розділів із дисципліни «Вища математика».

Дисципліна є базовою для вивчення курсів «Комп’ютерна схемотехніка», «Комп’ютерні системи», «Прикладна теорія цифрових автоматів», «Надійність, діагностика та контроль КС».

Місце навчальної дисципліни в системі професійних знань.

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

Зміст дисципліни (тематика):

Модуль 1

Елементи теорії множин

Поняття множини , підмножина, порожня множина, універсальна множина, способи завдання множин, операції над множинами, діаграми Ейлера-Венна, тотожності алгебри множин, способи доказів тотожностей, рівняння алгебри множин, булеан, покриття і розбиття множин, потужність множин, теорема Кантора про існування незліченної множини, розмиті множини.

Елементи теорії відношень

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

Елементи алгебраїчних систем

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

Модуль 2

Елементи алгебри логіки

Булеві функції, булеві функції двох змінних, основні тотожності алгебри логіки, ДНФ і КНФ, ДДНФ і ДКНФ, скорочена ДНФ і КНФ, тупікова і мінімальна ДНФ і КНФ, поняття суперпозиції, принцип подвійності булевих функцій, поліном Жегалкіна, класи Поста, теорема Поста про функціональну повноту.

Елементи математичної логіки

Формальна теорія, поняття логічного виведення, числення висловлень, аксіоми, правило виведення, теорема дедукції, методи доказу в численні висловлень: конструктивний, аксіоматичний, метод резолюцій, логіка предикатів, квантор загальності, квантор існування, поняття формули, інтерпретація, основні тотожності логіки предикатів, сколемовська нормальна форма, аксіоми і правила виведення, виведення, метод резолюцій.

Модуль 3

Елементи комбінаторики

Комбінаторні конфігурації, біном Ньютона, розбивка множин, числа Стирлінга, поліноміальна формула, метод включень / виключень, рекурентні співвідношення, рішення лінійних рекурентних співвідношень, твірні функції, операції над твірними функціями.

Елементи теорії графів

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

Види робіт: лекційні заняття, практичні роботи, самостійна робота студентів.