ПРЕДМЕТ ДИСКРЕТНОЙ МАТЕМАТИКИ

1.  НАЧАЛЬНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ

1.1. Элементы и множества

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

1.3. Основные тождества алгебры множеств

1.4. Прямое произведение множеств. Отношения и функции

1.5. Свойства бинарных отношений. Специальные бинарные отношения

1.6. Операции над бинарными отношениями

1.7. Алгебраические операции

2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

2.1. Логика высказываний

2.1.1. Высказывания. Логические связки

2.1.2. Формулы логики высказываний

2.1.3. Равносильность формул логики высказываний

2.1.4. Нормальные формы

2.1.5. Совершенные нормальные формы

2.2. Булевы функции

2.2.1. Представление булевой функции формулой логики высказываний

2.2.2. Минимизация нормальных форм

2.2.3. Полные системы булевых функций

2.2.4. Существенные и несущественные переменные. Производная булевой функции первого порядка. Вес переменной

2.3. Исчисление высказываний

2.3.1. Основные схемы логически правильных рассуждений

2.3.2. Метод Вонга

2.3.3. Метод резолюций

2.4. Логика предикатов

2.4.1. Основные понятия, связанные с предикатами

2.4.2. Классификация предикатов

2.4.3. Логические операции над предикатами

2.4.4. Кванторные операции над предикатами

2.4.5. Численные кванторы

2.4.6. Формулы логики предикатов

2.4.7. Интерпретация формул логики предикатов

2.4.8. Классификация формул логики предикатов

2.4.9. Равносильность формул логики предикатов

3. ТЕОРИЯ ГРАФОВ

3.1. Основные определения

3.1.1. Смежность, инцидентность, степени

3.1.2. Изоморфизм, гомеоморфизм

3.1.3. Матричное задание графов. Матрицы смежности, инцидентности

3.1.4. Примеры графов. Операции над графами

3.1.5. Маршруты, цепи, циклы

3.1.6. Связность. Компоненты связности

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.4. Транспортные сети

3.4.1. Поток в транспортной сети

3.4.2. Орграф приращений