ЛЕКЦИИ по курсу "Дискретная математика" (лектор к.ф-м.н., доцент В.А.Щербакова)

Последнее изменение: 05/04/2022 18:33:41

Глава I. Множества, бинарные отношения, мощность множеств

Множества, булевы операции, свойства булевых операций
Операции над бинарными отношениями
Отношение частичного порядка
Индуктивность. Вполне упорядоченные множества
Отображения (функции)
Мощность множеств, кардинальные числа

Глава II. Комбинаторика

Основные комбинаторные конфигурации и формулы
Конфигурации с повторениями
Принцип Дирихле. Числа Стирлинга 2-го рода
Числа Стирлинга 1-го рода
Пути в квадратной решетке. Числа Каталана
Принцип включения-исключения. Задача о количестве перемещений (беспорядков). Функция Эйлера.
Порядок роста функций. Асимптотические оценки

Глава III. Графы

Основные определения
Деревья
Двудольные графы
Плоские и планарные графы. Теорема Эйлера о многогранниках
Раскраска графа. Хроматическое число
Ориентированные графы: основные определения

Глава IV. Алгебраические системы

Алгебраические операции
Примеры основных алгебраических структур
Подсистемы и изоморфизм
Примеры основных алгебраических структур

Глава V. Алгебра логики. Булевы функции

Высказывания, формулы. Булевы функции: основные определения.
Замкнутые классы. Полные классы
Класс монотонных функций
Теорема Поста (критерий полноты)
Решение типовых задач по булевым функциям