
Зміст
- Теорія множин
- Вступ
- 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. Позначення до розділу «Булева алгебра»
- Перелік посилань
- Тест Булева алгебра
- 9. Основні поняття булевої алгебри
- Комбінаторний аналіз
- 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. Позначення до розділу «Комбінаторний аналіз»
- Перелік посилань
- Тест "Комбінаторний аналіз"
- 20. Основні поняття комбінаторного аналізу. Правила суми та добутку
- Теорія графів
- 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. Контрольні запитання
- Перелік посилань
- Тест
- 27. Основні поняття теорії графів