Название: Дискретная математика
Автор: Лелонд О.В., Тренина М.А.
Издательство: Тольятти: Тольяттинский государственный университет
Год: 2018
Формат: pdf/djvu
Страниц: 93
Для сайта: litgu.ru
Размер: 12 mb
Язык: русский
В учебном пособии дается первоначальное представление о множествах и операциях над ними, соответствиях и отношениях; рассматриваются основные комбинаторные схемы, на примерах демонстрируются принципы решения комбинаторных задач. Также значительное внимание в пособии уделено другим вопросам дискретной математики.
Предназначено для студентов, обучающихся по направлению подготовки 01.03.02 «Прикладная математика и информатика», 02.03.03 «Математическое обеспечение и администрирование информационных систем», 09.03.03 «Прикладная информатика» всех форм обучения высшего профессионального образования.
Содержание
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, T и 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. Алгоритм нахождения максимального потока на сети
Контрольные вопросы
Библиографический список