Основы дискретной математики Лекции 8-11

Логика предикатов и базы данных.
Содержание.
Реляционные базы данных.
Реляционная алгебра.
Теоретико-множественные операции.
Специальные реляционные операторы.
Запросы.
Ограничения целостности.
Задачи.
Графы: представления, достижимость и связность.
Содержание.
Основные понятия.
Представления графов.
Матрица (таблица) смежности.
Матрица (таблица) инцидентности.
Списки смежности.
Граф достижимости.
Взаимная достижимость, компоненты сильной связности и базы графа.
Задачи.
Деревья.
Содержание.
Неориентированные и ориентированные деревья.
Деревья и формулы (выражения).
Обходы деревьев.
Задачи.
Три алгоритма на графах.
Содержание.
Построение минимального остова.
Поиск в глубину и задача о лабиринте.
Задача о кратчайших путях из одного источника.
Задачи.