- •6 Отношения. Унарные, бинарные, тернарные отношения.
- •13 Способы задания нечетких множеств. Операции над нечеткими множествами.
- •Операции над нечеткими множествами
- •15 Логика высказываний.
- •16 Логические операции. Формулы логики высказываний. Логические операции.
- •Формулы логики высказываний
- •17 Равносильность формул.
- •18 Нормальные формы формул, приведение к днф, кнф.
- •19 Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы.
- •Алгоритм получения сднф по таблице истинности.
- •Алгоритм получения скнф по таблице истинности.
- •20 Булева алгебра. Логические функции одной или нескольких переменных.
- •21 Суперпозиции функций. Полные системы логических функций.
- •22 Минимизация в классе дизъюнктивных нормальных форм.
- •23 Исчисление высказываний и исчисление предикатов.
- •Исчисление предикатов
- •24 Аксиоматические теории. Выводимость формул в исчислении высказываний.
- •25. Теорема дедукции. Предикаты, кванторы.
- •26. Формулы логики предикатов, их равносильность, выполнимость и общезначимость.
- •27. Аксиомы исчисления предикатов.
- •28. Алгебраические структуры. Группы.
- •29. Циклические группы. Группы подстановок. Кольца и поля
- •30. Элементы теории кодирования. Представление о кодировании.
- •31. Расстояние Хемминга.
- •32. Теорема о корректирующей способности кодов.
- •33. Матричное кодирование. Групповые коды.
- •34. Коды Хемминга.
- •35. Элементы комбинаторики. Размещения и сочетания.
- •36 Перестановки и подстановки.
- •37 Разбиения Формула включений и исключений.
- •38 Теория графов. Основные понятия и определения.
- •39 Понятие графа. Виды графов.
- •40 Способы задания графов.
- •41 Смежность, инцидентность.
- •42.Операции над графами. Части графов.
- •43 Связность, компоненты связности.
- •44 Числа графов: цикломатическое, хроматическое, внешней и внутренней устойчивости.
- •45 Поиск маршрутов в графе. Задача о минимальном соединении.
- •46 Задача о кратчайшем пути.
- •47 Эйлеровы цепи и циклы. Гамильтоновы цепи и циклы.
- •48 Транспортные сети. Понятие транспортной сети.
- •49 Поток в транспортной сети. Разрез, пропускная способность разреза.
- •50 Алгоритмы построения максимального потока.
- •1) Процедура помечивания вершин.
- •2) Процедура изменения потока.
1) Процедура помечивания вершин.
Обработка i-й вершины с пометкой (x,e) заключается в том, что из вершины i помечаются смежные непомеченные вершины по следующему правилу:
- если дуга направлена из i в j и поток по этой дуге (fij) меньше пропускной способности дуги (cij), то вершине j присваивается метка (i+,min(e,cij-fij))
- если дуга направлена из j в i и поток по этой дуге (fji) больше нуля, то вершине j присваивается метка (i-,min(e,fji))
Эта процедура всегда начинается с помечивания и обработки истока. Он помечается особой меткой (-,). Затем обрабатываются другие помеченные вершины (после обработки истока пометятся вершины, смежные с ним) и т.д.
Процесс помечивания заканчивается в двух случаях:
1) Ни одну вершину больше нельзя пометить, но сток не помечен. Это значит, что найденный поток - максимальный и алгоритм останавливается.
2) Помечается сток. В этом случае производится изменение потока.
2) Процедура изменения потока.
Если сток получил метку (k+,d), то потоки будут изменяться на величину d следующим образом:
- если мы находимся в вершине j с меткой (i+,x), то прибавляем d к fij и переходим в вершину i.
- если мы находимся в вершине j с меткой (i-,x), то вычитаем d из fij и переходим в вершину i.
Изменение потока начинается от стока и продолжается до достижения истока. После этого все метки стираются и заново выполняется процедура помечивания вершин.
Этот процесс продолжается до тех пор, пока не будет найден максимальный поток (ни одну вершину больше нельзя пометить, но сток не помечен).