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

Зміст

Теорія множин
- Вступ
- 1. Основні поняття теорії множин
  - 1.1. Відношення приналежності й включення
  - 1.2. Способи завдання множин
  - 1.3. Алгебра множин Кантора
  - 1.4. Закони й тотожності алгебри множин
  - 1.5. Контрольні питання
- 2. Відповідності. Функції. Відображення
  - 2.1. Поняття впорядкованої пари й вектора
  - 2.2. Декартів (прямий) добуток множин
  - 2.3. Відповідності
  - 2.4. Функції. Відображення
  - 2.5. Контрольні питання
- 3. Відношення. Алгебра відношень
  - 3.1. Поняття відношення
  - 3.2. Операції над відношеннями
  - 3.3. Алгебра відношень
  - 3.4. Контрольні питання
- 4. Бінарні відношення
  - 4.1 Способи завдання бінарних відношень
  - 4.2 Властивості бінарних відношень
  - 4.3 Бінарне відношення еквівалентності
  - 4.4 Контрольні питання
- 5. Бінарне відношення порядку
  - 5.1. Упорядковані множини й бінарне відношення порядку
  - 5.2. Типи порядку (лінійний, частковий, передпорядок)
  - 5.3. Контрольні питання
- 6. Структури (рашітки). Алгебраїчні системи. Ізоморфізм
  - 6.1. Структури
  - 6.2. Дедекіндові (модулярні) структури
  - 6.3. Дистрибутивні структури
  - 6.4. Ізоморфізм множин
  - 6.5. Контрольні питання
- 7. Висновки до розділу «Теорія множин»
- 8. Позначення до розділу «Теорія множин»
- Перелік посилань
- Тест
Булева алгебра
- 9. Основні поняття булевої алгебри
  - 9.1. Логічні операції й логічні функції
  - 9.2. Закони й тотожності булевої алгебри
  - 9.3. Доведення законів булевої алгебри
  - 9.4. Контрольні запитання
- 10. Диз’юнктивні й кон’юнктивні нормальні форми (ДНФ і КНФ). Досконалі ДНФ і КНФ (ДДНФ і ДКНФ)
  - 10.1. ДНФ і КНФ
  - 10.2. ДДНФ і ДКНФ
  - 10.3. Складність зображення булевих функцій
  - 10.4. Теорема Шенона про розкладання булевих функцій
  - 10.5. Контрольні запитання
- 11. Елементи логічних схем. Булеві функції від двох змінних
  - 11.1. Фізичний зміст логічних функцій І, АБО, НІ та їх схемотехнічне зображення
  - 11.2. Таблиця аналітичного й схемотехнічного зображення булевих функцій від двох змінних
  - 11.3. Властивості й аналітичні зображення елементарних булевих функцій від двох змінних
  - 11.4. Приклади розв’язання практичних завдань
  - 11.5. Контрольні запитання й завдання
- 12. Способи зображення булевих функцій
  - 12.1. Табличний спосіб зображення булевих функцій
  - 12.2. Числовий спосіб зображення булевих функцій
  - 12.3. Аналітична форма запису булевих функцій
  - 12.4. Геометрична інтерпретація булевих функцій
  - 12.5. Кубічна форма зображення булевих функцій
  - 12.6. Схемотехнічне зображення
  - 12.7. Контрольні запитання й завдання
- 13. Системи функцій алгебри логіки. Функціональна повнота
  - 13.1. Класи булевих функцій
  - 13.2. Повнота функцій алгебри логіки
  - 13.3. Контрольні запитання й завдання
- 14. Булеві похідні
  - 14.1. Булеві похідні першого порядку
  - 14.2. Фізичний зміст булевої похідної першого порядку
  - 14.3. Змішана похідна k-го порядку
  - 14.4. Булеві похідні k-го порядку
  - 14.5. Контрольні запитання
- 15. Мінімізація булевих функцій. Методи Квайна й Квайна-Мак-Класки
  - 15.1. Основні положення методу Квайна
  - 15.2. Мінімізація булевих функцій за методом Квайна-Мак-Класки
  - 15.3. Контрольні запитання
- 16. Мінімізація булевих функцій: метод невизначених коефіцієнтів
  - 16.1. Основні припущення
  - 16.2. Алгоритм знаходження невизначених коефіцієнтів
  - 16.3. Контрольні питання
- 17. Мінімізація булевих функцій: метод карт Карно
  - 17.1. Основні положення
  - 17.2. Спрощений стандарт карт Карно
  - 17.3. Мінімізація за картами Карно
  - 17.4. Контрольні запитання
- 18. Висновки до розділу «Булева алгебра»
- 19. Позначення до розділу «Булева алгебра»
- Перелік посилань
- Тест Булева алгебра
Комбінаторний аналіз
- 20. Основні поняття комбінаторного аналізу. Правила суми та добутку
  - 20.1. Правило суми
  - 20.2. Правило добутку
  - 20.3. Перестановки та підстановки
  - 20.4. Добуток підстановок
  - 20.5. Група підстановок n елементів
  - 20.6. Інверсії. Парність підстановки
  - 20.7. Підстановки із заданим числом циклів
  - 20.8. Контрольні запитання й завдання
- 21. Формула бінома Ньютона
  - 21.1. Біноміальні коефіцієнти
  - 21.2.Властивості біноміальних коефіцієнтів
  - 21.3.Формула бінома Ньютона
  - 21.4.Контрольні запитання та завдання
- 22. Поліноміальна формула
  - 22.1. Поліноміальні коефіцієнти
  - 22.2.Формула полінома
  - 22.3.Контрольні запитання та завдання
- 23. Сполучення. Розміщення
  - 23.1. Поняття сполучення
  - 23.2.Геометрична інтерпретація чисел
  - 23.3.Кількість підмножин даної множини
  - 23.4.Поняття розміщення
  - 23.5.Контрольні запитання та завдання
- 24. Комбінаторні конфігурації з повтореннями
  - 24.1. Перестановки з повтореннями
  - 24.2. Розміщення з повтореннями
  - 24.3. Сполучення з повтореннями
  - 24.4. Контрольні запитання
- 25. Вибірки. Узагальнення комбінаторних конфігурацій
  - 25.1. Поняття вибірки
  - 25.2. Визначення перестановок, сполучень, розміщень у термінах вибірок
  - 25.3. Комбінаторна міра інформації
  - 25.4. Імовірність спотворення інформації
  - 25.5. Контрольні запитання й завдання
- 26. Позначення до розділу «Комбінаторний аналіз»
- Перелік посилань
- Тест "Комбінаторний аналіз"
Теорія графів
- 27. Основні поняття теорії графів
  - 27.1. Інцидентність та суміжність
  - 27.2. Маршрути на графах
  - 27.3. Типи графів
  - 27.4. Зв’язність та дерева
  - 27.5. Підграфи графів
  - 27.6. Ізоморфізм графів
  - 27.7. Операції над графами
  - 27.8. Контрольні запитання і завдання
- 28. Способи зображення графів
  - 28.1. Актуальність і практична спрямованість
  - 28.2. Подання графа матрицею суміжності
  - 28.3. Матриця інциденцій
  - 28.4. Матриця циклів
  - 28.5. Порівняння і складність матричних способів зображення графів
  - 28.6. Контрольні запитання та завдання для самоконтролю
- 29. Алгебраїчна форма подання графів
  - 29.1. Основні положення АФПГ
  - 29.2. Аксіоми і тотожності АФПГ
  - 29.3. Контрольні запитання
- 30. Кубічна форма подання графів
  - 30.1. Основні поняття КФПГ
  - 30.2. Процедура проектування КФПГ
  - 30.3. Оцінка якості кодування
  - 30.4. Формалізація процедури проектування КФПГ
  - 30.5. Контрольні запитання
- 31. Ейлерові графи
  - 31.1. Основні поняття
  - 31.2. Приклади розв’язання практичних задач
  - 31.3. Застосування ейлерових графів
  - 31.4. Контрольні запитання
- 32. Гамільтонові графи
  - 32.1. Основні поняття
  - 32.2. Метод перебору Робертса та Флореса для визначення гамільтонових циклів
  - 32.3. Алгебраїчний метод визначення гамільтонова циклу в орієнтованому графі
  - 32.4. Застосування гамільтонових графів
  - 32.5. Порівняльний аналіз ейлерових та гамільтонових графів
  - 32.6. Контрольні запитання та завдання
- 33. Метод гілок та границь розв’язання задачі комівояжера
  - 33.1. Основні поняття. Постановка задачі
  - 33.2. Опис методу гілок і границь
  - 33.3. Загальна модель задачі пошуку
  - 33.4. Розв’язання практичних задач
  - 33.5. Контрольні запитання й завдання
- 34. Метод динамічного програмування розв’язання задачі комівояжера
  - 34.1. Основні положення та принципи методу динамічного програмування
  - 34.2. Приклад застосування методу
  - 34.3. Контрольні запитання та завдання
- 35. Алгоритм Гільберта-Мура побудови оптимального дерева бінарного пошуку
  - 35.1. Основні положення
  - 35.2. Постановка задачі та опис алгоритму
  - 35.3. Застосування орієнтованих дерев
  - 35.4. Приклади розв’язання практичних задач
  - 35.5. Контрольні запитання
- 36. Побудова остову найменшої довжини. Алгоритм Краскала
  - 36.1. Основні поняття й постановка задачі
  - 36.2. Алгоритм побудови остову найменшої довжини (алгоритм Краскала)
  - 36.3. Приклади розв’язання практичних задач
  - 36.4. Контрольні запитання
- 37. Побудова найкоротших ланцюгів із заданої вершини. Алгоритм Дейкстри
  - 37.1. Основні визначення
  - 37.2. Найкоротші шляхи з даної вершини s до всіх інших вершин графа
  - 37.3. Процедура розстановки міток
  - 37.4. Опис алгоритму Дейкстри
  - 37.5. Оцінка складності алгоритму
  - 37.6. Контрольні запитання
- 38. Складність задач теорії графів. Задача синтезу керуючих систем
  - 38.1. Складність задач теорії графів
  - 38.2. Задача синтезу керуючих систем
  - 38.3. NP-повнота
  - 38.4. Приклади розв’язання практичних задач
  - 38.5. Контрольні запитання
- Перелік посилань
- Тест