- •1.Множества и подмножества. Операции над ними.
- •2. Основные равносильности алгебры множеств.
- •3. Определение кортежа. Декартово (прямое) произведение множеств.
- •4. Определение отношения и теоретико-множественные операции над ними
- •5. Операции над отношениями.
- •6. Образ и прообраз множества в отношении.
- •7.Соответствия. Свойства соответствий.
- •8.Отношения. Свойства отношений.
- •9.Разбиение множеств.
- •10.Отношение эквивалентности.
- •11.Отношение порядка.
- •12. Табличный способ задания данных. Домены и атрибуты.
- •13. Ключи и нормализованное отношение. Реляционная модель базы данных.
- •14. Реляционная алгебра. Традиционные теоретико-множественные операции.
- •15. Реляционная алгебра. Специальные операции.
- •16. Реляционная алгебра как язык запросов.
- •17. Первая и вторая нормальные формы отношений
- •17. Первая и вторая нормальные формы отношений
- •20. Локальные степени графа.Части графа и подграфы.
- •21. Эйлеровы графы.
- •22. Гамельтоновы цепи и циклы.
- •23. Алгоритм Райяна решения задачи коммиваяжёра.
- •24. Деревья. Основные понятия и определения.
- •25. Задача о минимальном соединении (построение дерева-остова).
- •Алгоритм:
- •26. Деревья. Задача о минимальном пути.
- •Алгоритм:
- •Алгоритм Дейкстры:
- •27. Транспортные сети. Задача о максимальном потоке.
- •28. Теорема и алгоритм Форда-Фалкерсона.
- •Алгоритм построения полного потока:
- •Алгоритм Форда-Фалкерсона:
- •29. Деревья. Циклический ранг графа.
- •30. Задача раскраски графов. Хроматическое число.
- •32. Основные равносильности алгебры логики.
- •33.Функции логических переменных
- •X 0 1 Прим.
- •X1 x2 x3
- •X1&x2, x1’&x2, x1&x1& x2’.
- •36.Приведение к сндф по таблицам истинности
- •37. Аналитическое приведение формулы к сндф.
- •31. Высказывание. Основные логические операции.
- •18. Третья нормальная форма отношений.
- •19. Графы. Основные определения и способы задания.
Алгоритм Дейкстры:
x2 [1,x1] x6 = xn [6,x2]
5
1 5
[0,x1] 7 x4 [3,x2] 2
x1
10 2
1
x3 [5,x4] x5 [5,x4]
Разметки делятся на временные и постоянные.
Всем вершинам приписываем временную разметку .
В первой вершине ставим постоянную разметку .
2. Пусть - последняя из вершин, получивших постоянную разметку.
Для всех соседних вершин с временными разметкамипроверяется неравенство:
Если оно выполняется, то у вершины разметка меняется на
, если не выполняется, то разметка остается прежней.
3. Среди временных вершин выбирается вершина с минимальным расстоянием и она объявляется постоянной вершиной.
Возможны два исхода:
- вершина не имеет постоянной разметки, тогда возвращаемся к пункту 2.
- вершина имеет постоянную разметку.4. Построим искомый путь: Начинаем с вершины , вторая компонента разметки вершины- вторая вершина () и т.д.
27. Транспортные сети. Задача о максимальном потоке.
Задача о максимальном потоке – одна из оптимизационных задач.
Транспортные сети – граф, ориентированный в одном общем направлении от вершин, называемых входами, к вершинам, называемым выходами сети.
.
ориентация неизменна ориентация неизменна
В большинстве случаев рассматривается сеть с одним входом и одним выходом.
Транспортная сеть – граф с нагруженными ребрами. Каждому ребру приписывается число, равное пропускной способности этого ребра. Транспортная сеть имеет функцию пропускной способности (определена на множестве ребер) - .
Функция потока – целочисленная неотрицательная функция, определена на множестве ребер и удовлетворяет условиям:
1) - ребро,- неотрицательная функция.
2) Поток через каждое ребро не может превышать пропускной способности этого ребра:
3) Для каждой промежуточной вершин (узла) сумма потоков, входящих в узел, равна сумме потоков, выходящих из этого узла:
,
Ф =
Величина потока одинакова через любой разрез сети.
Разбить на два подмножества вершин А и В, не пустых, не пересекающихся, ,.
Множество ребер, заходящих в множество В, называется разрезом сети.
Величина разреза равна сумме пропускных способностей всех ребер, входящих в него:
=
Величина потока через разрез - сумма величин потоков по всем ребрам, входящим в него:
=
Задача о максимальном потоке:
Найти такое распределение потока по ребрам, чтобы суммарный поток через сеть принимал максимальное значение:
28. Теорема и алгоритм Форда-Фалкерсона.
x1 (4) x3
5 (4)
(4) 10 4
x0 1 7 10
(2) xn = x5
2 (1) (1) 20
10 (3)
x2 (3) x4
Начиная с любого начального распределения потока алгоритм строит максимальный поток. Алгоритм носит циклический характер.
В каждом шаге происходит увеличение потока на 1 или сигнализация о том, что максимальный поток построен.
Лучше начинать алгоритм с полного потока.
Полный поток через транспортную сеть - поток, насыщающий все пути из начальной вершины в конечную.
Путь называется насыщенным, если он содержит хотя бы одно насыщенное ребро.
Ребро называется насыщенным, если поток через него равен его пропускной способности.