2.1. Перелік питань з дисципліни "Основи дискретної математики"

Тема 1. Елементарні логічні Функції

Виказування. Операції: кон’юнкція, диз’юнкція, заперечення. Таблиці істинності. Складне виказування. Основні закони алгебри виказувань. Атомарне виказування. Булєва функція (функція алгебри логіки - ФАЛ) від нуля змінних, від однією змінній, від двох змінних. Класи ФАЛ. Теорема Пост-Яблонського о повноті системи ФАЛ. Базис. Метод Петрика що до пошуку базисів ФАЛ.

Тема 2. Математичне представлення графів

Геометричний граф. Вершини. Ребра. Граф: неорієнтований, вироджений, кінцевий, орієнтований, звичайний, повний. Суміжні вершини, ребра. Інцидентність. Шлях, контур, ланцюг, цикл. Розріз. Зв’язність графів. Ізоморфізм графів. Таблиця, фактор-множина, матриця інциденцій, матриця суміжності вершин, матриця циклів, матриця розрізів, матриця шляхів.

Тема 3. Мінімізація логічних функцій

Досконала диз’юнктивна нормальна форма (ДНФ). Досконала кон’юнктивна нормальна форма (КНФ). Елементарні кон’юнкція, диз’юнкція. Розкладання Шеннону. Первинний терм. Операції поглинання та склеювання. Тупикова ДНФ, мінімальні ДНФ і КНФ. Методи мінімізації ФАЛ: метод невизначених коефіцієнтів, гарвардський метод, метод Квайна-МакКласкі, за допомогою карт Карно (Вейча).

Тема 4. Алгоритми пошуку найкоротшого шляху в графах

Задача про найкоротший шлях. Метод індексів для графів з ребрами одиничної довгі. Алгоритм Флойда для зваженого графа.