Лекция 16

ТЕМА: СООТВЕТСТВИЯ И ОТОБРАЖЕНИЯ

ПЛАН:

1. Соответствие

2. Функция

3. Отображение

4. n –местная функция

5. Обратная функция

6. Свойства отображений

ЛЕКЦИЯ 17

ТЕМА: НЕОРИЕНТИРОВАННЫЙ ГРАФ.

ПЛАН:

1. Основные понятия

2. Смежность, инцидентность. Степени вершин

3. Способы задания графов

4. Маршруты в неориентированном графе

5. Операции над графами

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

ЛЕКЦИЯ 18

ТЕМА: ЗАДАЧИ НА НЕОРИЕНТИРОВАННЫЕ ГРАФЫ

ПЛАН:

1. Поиск маршрута с минимальным числом ребер

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

3. Минимальные маршруты в нагруженных графах

4. Задачи на деревьях

5. Цикловой ранг графа. Цикломатическое число

ЛЕКЦИЯ 19

ТЕМА: ЭЙЛЕРОВЫ И ГАМИЛЬТОНОВЫ ЦЕПИ И ЦИКЛЫ

ПЛАН:

1. Эйлеровы цепи и циклы

2. Гамильтоновы циклы и цепи

ЛЕКЦИЯ 20

ТЕМА: ДВУДОЛЬНЫЕ ГРАФЫ

ПЛАН:

1. Двудольный граф. Условие существования двудольного графа

2. Паросочетания . Реберные покрытия

ЛЕКЦИЯ 21

ТЕМА: ПЛОСКИЕ ГРАФЫ

ПЛАН:

1. Задача о плоской укладке графа

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

3. Алгоритм плоской укладки графа

ЛЕКЦИЯ 22

ТЕМА: ОРИЕНТИРОВАННЫЙ ГРАФ

ПЛАН:

7. Содержание

   • Лекция 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. Порядковая функция орграфа без контуров
   • Контрольные вопросы