Программа курса «Дискретная математика»

1. Множества

Фундаментальные понятия. Пустое, универсальное множества. Задание множеств: перечислением, условием, процедурой. Аксиомы и определения. Операции над множествами. Диаграммы Эйлера-Венна. Мощность множеств.

2. Отношения и графы

Понятие отношений. Классификация отношений. Отношения и графы. Диаграмма графа. Матрицы смежности, инциденций, структура смежности, список ребер. Ациклические графы. Специальные виды отношений. Частичный, слабый и линейный порядки. Отношения предпочтения. Маршруты в графах. Эйлеровы и гамильтоновы циклы. Расстояние в графах. Метрические характеристики графа (эксцентриситет, радиус и диаметр, центр и периферия). Минимальный остов графа.

3. Некоторые вопросы комбинаторики

Правило умножения. Элементарные задачи комбинаторики (числа перестановок, сочетаний, размещений). Разбиения множества. Числа Стирлинга 2-го рода. Числа Белла.

4. Методы дискретной математики в области принятия решений

Парето-множество. Граф Парето. Методы принятия решений в случае дискретного множества альтернатив (агрегирование критериев, иерархия критериев, идеальная точка). Паросочетания. Условие Холла. Метод чередующихся цепей. Обобщенные паросочетания. Коллективные решения.

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

Понятие функции. Функции алгебры логики. Функции одной и двух переменных. Представление булевых функций через базовые. Дизъюнктивные и конъюнктивные нормальные формы. СДНФ. Минимизация ДНФ. Представление булевых функций через штрих Шеффера.

6. Элементы теории автоматов.

Понятие конечного автомата. Задание автомата. Входной и выходной алфавиты. Построение автоматов.

7. Основные принципы кодирования информации.

Двоичное кодирование информации. Объем информации. Префиксное и постфиксное кодирование. Алгоритм Шеннона-Фано. Минимальное кодирование. Алгоритм Хаффмана.

8. Клеточные автоматы.

Понятие клеточного автомата. Классы клеточных автоматов. Использование клеточных автоматов для математического моделирования динамических процессов.

Вопросы к экзамену по дискретной математике

Основные понятия теории множеств и операции над множествами. Диаграммы Эйлера-Венна.

Понятие и классификация бинарных отношений. Операции над отношениями.

Специальные виды отношений (порядки).

Бинарные отношения и графы. Способы задания графов.

Маршруты в графах. Эйлеровы и гамильтоновы циклы.

Расстояние в графах. Метрические характеристики графа.

Элементарные задачи комбинаторики (перестановки, сочетания, размещения).

Разбиения множества. Числа Стирлинга 2-го рода. Числа Белла.

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

Дизъюнктивные и конъюнктивные нормальные формы. СДНФ. Минимизация ДНФ.

Методы принятия решений при наличии множества критериев.

Процедуры принятия коллективных решений.

Паросочетания. Условие Холла. Метод чередующихся цепей.

Обобщенные паросочетания. Алгоритм построения устойчивого паросочетания.

Конечные автоматы, их задание и построение.

Двоичное кодирование информации. Объем информации. Префиксное и постфиксное кодирование. Алгоритм Шеннона-Фано.

Минимальное кодирование. Алгоритм Хаффмана.

Клеточные автоматы. Основные понятия и классификация.

Задачи, прилагаемые к билетам по дискретной математике (общие формулировки)

Постройте диаграмму Эйлера-Венна для множества заданного операциями над несколькими исходными множествами и выразите это множество через исходные указанным способом.

Постройте СДНФ для заданной функции булевых переменных и, если возможно, минимизируйте ее.

Решите элементарную комбинаторную задачу.

Граф задан одним из способов. Задайте его другими способами (диаграмма, матрицы смежности, инцидентности, список ребер).

Найдите метрические характеристики взвешенного графа (расстояния между вершинами, центральное и периферийное множества, радиус, диаметр) и постройте его минимальный остов.

Для данного двудольного графа проверьте выполнение условия Холла и постройте методом чередующихся цепей максимальное паросочетание.

По таблице с критериальными оценками альтернатив постройте граф Парето, укажите множество Парето и выберите оптимальное решение двумя способами: проведя агрегирование критериев и методом идеальной точки.