Дискретная математика: Электронное учебно-методическое пособие

Description

ДИСКРЕТНАЯ МАТЕМАТИКА Cодержание 1. МНОЖЕСТВА. СООТВЕТСТВИЯ. БИНАРНЫЕ ОТНОШЕНИЯ 1.1. Множества и операции над ними 1.2. Соответствия между множествами. Отображения 1.3. Эквивалентность множеств. Понятие мощности множества 1.4. Бинарные отношения Контрольные вопросы 2. КОМБИНАТОРИКА 2.1. Введение 2.2. Правила комбинаторики 2.3. Принцип включения и исключения 2.4. Комбинаторные схемы 2.5. Полиномиальная формула 2.6. Биномиальная формула Контрольные вопросы 3. БУЛЕВЫ ФУНКЦИИ 3.1. Элементарные булевы функции 3.2. Реализация функций формулами 3.3. Некоторые свойства элементарных функций 3.4. Принцип двойственности 3.5. Нормальные формы 3.6. Разложение булевой функции по переменным 3.7. Минимизация СДНФ 3.8. Полные системы. Примеры полных систем 3.9. Теорема Жегалкина о представимости функции алгебры логики полиномом 3.10. Понятие замкнутого класса. Замкнутость классов T0, T1 и L 3.11. Класс самодвойственных функций 3.12. Класс монотонных функций 3.13. Теорема Поста о полноте системы функций алгебры логики Контрольные вопросы 4. ГРАФЫ И СЕТИ 4.1. Понятие графа 4.2. Смежность, инцидентность, степени вершин 4.3. Маршруты, цепи, циклы 4.4. Изоморфизм графов 4.5. Способы представления графов 4.6. Полные и двудольные графы 4.7. Свойства степеней вершин графа 4.8. Операции над графами 4.9. Связность 4.10. Диаметр, радиус и центр графа 4.11. Деревья 4.12. Планарные графы 4.13. Эйлеровы и гамильтоновы графы 4.14. Раскраска графов 4.15. Алгоритмы раскраски графов 4.16. Циклы и коциклы 4.17. Независимые множества циклов и коциклов 4.18. Фундаментальные циклы 4.19. Фундаментальные разрезы 4.20. Сети и потоки 4.21. Разрез на сети 4.22. Алгоритм нахождения максимального потока на сети Контрольные вопросы Библиографический список