Лекции ДМ
Контрольные вопросы
Какой маршрут называется минимальным?
Алгоритм выделения минимального маршрута в ненагруженном неорграфе.
Алгоритм выделения минимального маршрута в нагруженном графе.
Какой граф называется ациклическим? Какой подграф называется остовом? Алгоритм его построения.
Что называется цикловым рангом графа? Что такое цикломатическое число, цикловой базис графа? Алгоритм построения циклового базиса графа.
Содержание
- Лекция 2
- Лекция 3
- Лекция 4
- Лекция 5
- Лекция 13
- Лекция 14
- Лекция 16
- Основные понятия
- Понятие множества. Способы задания множеств.
- Понятие множества. Способы задания множеств.
- Отношения между множествами.
- 3, Операции над множествами.
- Алгебра множеств.
- Теорема о количестве подмножеств конечного множества.
- Формула включений и исключений.
- Лекция 2
- 1.Понятие вектора. Прямое произведение множеств.
- 2.Теорема о количестве элементов прямого произведения.
- Понятие вектора. Прямое произведение множеств.
- Теорема о количестве элементов прямого произведения.
- Лекция 3
- 2. Понятие высказывания.
- 3. Логические операции над высказываниями
- 4.Формулы алгебры логики.
- Лекция 4
- 2. Важнейшие равносильности алгебры логики.
- 3.Равносильные преобразования формул.
- Задачи для самостоятельного решения
- Лекция 5
- Дизъюнктивная нормальная форма.
- Конъюнктивная нормальная форма.
- Проблема разрешимости.
- Лекция 6
- Функции алгебры логики.
- 3. Представление произвольной функции алгебры логики в виде формулы алгебры логики.
- 4.Приложения алгебры логики в технике (релейно-контактные схемы).
- Контрольные вопросы
- Лекция 7
- Совершенная дизъюнктивная нормальная форма.
- Совершенная конъюнктивная нормальная форма.
- Совершенная дизъюнктивная нормальная форма.
- 2.Совершенная конъюнктивная нормальная форма.
- Лекция 8
- 2.Понятие минимальной днф. Метод минимизирующих карт.
- 3.Метод Квайна.
- 4.Метод Карно.
- 5.Постановка задачи минимизации в геометрической форме.
- 6.Сокращенная днф.
- 7.Тупиковая днф. Днф Квайна.
- Лекция 9
- Некоторые логические операции. Двоичное сложение.
- Полином Жегалкина.
- Некоторые логические операции. Двоичное сложение.
- Полином Жегалкина.
- Лекция 10
- Полная система . Достаточное условие полноты.
- Критерий полноты системы булевых функций.
- Независимые системы. Базис замкнутого класса.
- Полная система. Достаточное условие полноты.
- Критерий полноты системы булевых функций.
- 3. Независимые системы. Базис замкнутого класса.
- Лекция 11
- Понятие предиката.
- Логические операции над предикатами.
- 1. Понятие предиката
- 2. Логические операции над предикатами
- Лекция 12
- 2. Формулы логики предикатов.
- Значение формулы логики предикатов.
- 4. Равносильные формулы логики предикатов.
- Лекция 13
- Построение противоположных утверждений.
- 3. Прямая, обратная и противоположная теоремы.
- 4. Необходимые и достаточные условия.
- 5. Доказательство методом от противного.
- Задачи для самостоятельного решения
- Лекция 14
- 2. Использование метода математической индукции для нахождения сумм конечного числа слагаемых
- 3. Использование метода математической индукции для доказательства неравенств и делимости выражений, зависящих от n на некоторое число
- 4. Обобщение метода математической индукции
- Контрольные вопросы
- Лекция 15
- Операции над бинарными отношениями.
- 3. Свойства бинарных отношений.
- 4. Специальные бинарные отношения.
- Контрольные вопросы
- Лекция 16
- Функция
- 1. 4. Отображение
- Обратная функция
- 2. Свойства отображений и функций
- 3.Операции над функциями. Свойства операций
- Контрольные вопросы
- Лекция 17
- Основные понятия .
- 2. Смежность, инцидентность, степени вершин.
- 3. Способы задания графов
- Маршруты в неориентированном графе
- Операции над графами.
- Связность. Компоненты связности
- Контрольные вопросы
- Лекция 18
- 2. Метрические характеристики неориентированного графа
- Минимальные маршруты в нагруженных графах
- Задачи на деревьях
- Цикловой ранг графа. Цикломатическое число
- Контрольные вопросы
- Лекция 19
- Эйлеровы цепи и циклы
- Гамильтоновы циклы и цепи
- Эйлеровы цепи и циклы
- Гамильтоновы циклы и цепи.
- Контрольные вопросы
- Лекция 20
- Двудольный граф. Условие существования двудольного графа
- Паросочетания . Реберные покрытия
- Двудольный граф. Условие существования двудольного графа
- Паросочетания. Реберные покрытия
- Контрольные вопросы
- Лекция 21
- Основные определения
- Алгоритм плоской укладки графа
- Контрольные вопросы
- Лекция 22
- Способы задания ориентированного графа
- Путь в ориентированном графе
- 4. Связность. Компоненты связности в орграфе
- Контрольные вопросы
- Лекция 23
- 2. Минимальные пути в нагруженных орграфах
- 3. Порядковая функция орграфа без контуров
- Контрольные вопросы