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

Зміст

  • Теорія множин
    • Вступ
    • 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. Контрольні запитання
    • Перелік посилань
    • Тест