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

Конспект лекций  

назад вперед
 

Конспект лекций в формате Microsoft Word

Введение

Глава 1 Элементы теории множеств
1.1 Множества и их спецификация
 1.1.1 Элементы и множества
 1.1.2 Задание множеств. Парадокс Рассела
 1.1.3 Контрольные вопросы
1.2 Операции над множествами
 1.2.1 Сравнение множеств
 1.2.2 Операции над множествами. Диаграммы Венна
 1.2.3 Представление множеств в ЭВМ
 1.2.4 Разбиения и покрытия
 1.2.5 Свойства операций над множествами
 1.2.6 Контрольные вопросы
1.3 Отношения на множествах
 1.3.1 Прямое произведение множеств
 1.3.2 Отношения
 1.3.3 Свойства отношений
 1.3.4 Представление отношений в ЭВМ
 1.3.5 Отношение эквивалентности
 1.3.6 Отношение порядка
 1.3.7 Контрольные вопросы
1.4 Функции
 1.4.1 Определение функции
 1.4.2 Классификация функций
 1.4.3 Некоторые специальные функции
 1.4.4 Контрольные вопросы

Глава 2 Элементы комбинаторики
2.1 Комбинаторные задачи и основные принципы
 2.1.1 Комбинаторные задачи
 2.1.2 Основные комбинаторные принципы
 2.1.3 Контрольные вопросы
2.2 Комбинаторные конфигурации
 2.2.1 Перестановки и подстановки
 2.2.2 Понятие выборки
 2.2.3 Размещения и сочетания без повторений
 2.2.4 Размещения и сочетания с повторениями
 2.2.5 Контрольные вопросы
2.3 Биномиальные коэффициенты
 2.3.1 Свойства биномиальных коэффициентов
 2.3.2 Треугольник Паскаля
 2.3.3 Контрольные вопросы
2.4 Обобщенные перестановки и разбиения
 2.4.1 Перестановки с повторениями
 2.4.2 Разбиения и числа Стирлинга
 2.4.3 Контрольные вопросы
2.5 Принцип включения и исключения
2.6 Рекуррентные функции
 2.6.1 Понятие рекуррентного соотношения
 2.6.2 Решение рекуррентного уравнения
 2.6.3 Контрольные вопросы

Глава 3 Элементы теории графов
3.1 Определения графов
 3.1.1 История теории графов
 3.1.2 Основные понятия
 3.1.3 Другие определения графов и бинарные отношения
 3.1.4 Изоморфизм графов
 3.1.5 Контрольные вопросы
3.2 Элементы графов
 3.2.1 Валентность
 3.2.2 Маршруты, цепи, циклы
 3.2.3 Связность
 3.2.4 Подграфы
 3.2.5 Контрольные вопросы
3.3 Виды графов и операции над ними
 3.3.1 Тривиальные и полные графы
 3.3.2 Двудольные графы
 3.3.3 Плоский (планарный) граф
 3.3.4 Направленные орграфы и сети
 3.3.5 Операции над графами
 3.3.6 Деревья
 3.3.7 Контрольные вопросы
3.4 Представление графов в ЭВМ
 3.4.1 Требования к представлению графов
 3.4.2 Способы представления графа
 3.4.3 Обходы графов
 3.4.4 Контрольные вопросы
3.5 Алгоритмы на графах
 3.5.1 Выделение компонент связности в орграфах
 3.5.2 Кратчайшие пути
 3.5.3 Минимальный остов
 3.5.4 Эйлеровы графы
 3.5.5 Гамильтоновы графы
 3.5.6 Контрольные вопросы

Глава 4 Алгебра логики
4.1 Формулы и функции алгебры логики
 4.1.1 Высказывания и операции над ними
 4.1.2 Построение формул
 4.1.3 Булевы функции и формулы
 4.1.4 Булевы функции и булева алгебра
 4.1.5 Принцип двойственности
 4.1.6 Алгебра Жегалкина
 4.1.7 Контрольные вопросы
4.2 Способы представления булевых функций
 4.2.1 Нормальные формы
 4.2.2 Построение совершенных нормальных форм
 4.2.3 Карты Карно
 4.2.4 Контрольные вопросы
4.3 Контактные схемы
 4.3.1 Контрольные вопросы
4.4 Минимизация булевых функций
 4.4.1 Применение карт Карно
 4.4.2 Метод Квайна-Мак-Класки
 4.4.3 Минимизация частично определенных функций
 4.4.4 Контрольные вопросы

Список литературы


назад вперед