Особенность дискретной математики
Суть основного правила комбинаторики. Анализ булевой алгебры характеристических векторов и высказываний. Особенность дизъюнктивных и конъюнктивных нормальных форм. Функционально-полные системы функций. Главные параметры поиска многочлена Жегалкина.
| Рубрика | Математика |
| Вид | курс лекций |
| Язык | русский |
| Дата добавления | 08.02.2015 |
| Размер файла | 62,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Алгоритм нахождения максимального потока (Алгоритм Форда - Фалькерсона).
Берем любой поток в транспортной сети.
Строим граф перестроек g* по следующему правилу:
В него входят все вершины исходного графа g.
Те ребра, на которых значение функции потока в исходном графе g были равны 0, входят в новый граф без изменений со своими пропускными способностями.
Все ребра, на которых ф(x) > 0 в новом графе g* заменяются двумя ребрами x* и x**. Ребро x* направлено в ту же сторону, что и x, и пропускная способность c(x*) = c(x) - ф(x).
Ребро x** направлено в противоположную сторону ребру x, и пропускная способность c(x**) = ф(x).
Ребра с нулевой пропускной способностью можно не рисовать.
В графе g* ищем путь из А в В по ребрам с ненулевой пропускной способностью. Если его нет, то имеющийся поток является максимальным и алгоритм закончен. Иначе переходим к пункту 4.
(Этот путь называется увеличенной цепью. ????min(c(x)) - минимальное значение пропускной способности этой цепи).
Меняем значение функции потока в графе g для тех ребер, которые соответствуют найденному пути в графе перестроек по следующему правилу:
Если направление ребра x в графе g совпадает с направлением пути, то новое ф(x) = ф(x) + ?
Если же направление противоположно направлению пути, то ф(x) = ф(x) - ?
5. Переходим на шаг 2 с новым потоком.
Размещено на Allbest.ru
Подобные документы
Полнота и замкнутость системы булевых функций. Алгоритм построения таблицы истинности двойственной функции. Класс L линейных функций, сущность полинома Жегалкина. Распознавание монотонной функции по вектору ее значений. Доказательство теоремы Поста.
учебное пособие [1,3 M], добавлен 20.08.2014Основная функционально полная система логических функций. Законы алгебры логики в основной функционально полной системе и их следствия. Переместительный и распределительный законы. Закон инверсии (правило Де Моргана). Системы логических функций.
реферат [40,5 K], добавлен 17.11.2008Сокращенные, тупиковые дизъюнктивные нормальные формы. Полные системы булевых функций. Алгоритм Квайна, Мак-Класки минимизации булевой функции. Геометрическое представление логических функций. Геометрический метод минимизации булевых функций. Карты Карно.
курсовая работа [278,1 K], добавлен 21.02.2009Решения задач дискретной математики: диаграммы Эйлера-Венна; высказывание в виде формулы логики высказываний и формулы логики предикатов; СДНФ и СКНФ булевой функции. При помощи алгоритма Вонга и метода резолюции выяснить является ли клауза теоремой.
контрольная работа [133,5 K], добавлен 08.06.2010Минимизация заданного выражения алгебры множеств на основании известных свойств. Анализ заданного бинарного отношения в общем виде. Вывод формул булевых функций для каждого элемента и схемы в целом. Преобразование формулы булевой функции логической схемы.
контрольная работа [286,7 K], добавлен 28.02.2009Логический синтез устройства с использованием соотношений булевой алгебры. Составление таблицы истинности. Основные соотношения булевой алгебры. Логическая функция в смысловой, словесной, вербальной, табличной и аналитической математической формах.
лабораторная работа [83,6 K], добавлен 26.11.2011Изучение булевых функций. Алгоритм представления булевых функций в виде полинома Жегалкина. Система функций множества. Алгебраические преобразования, метод неопределенных коэффициентов. Таблица истинности для определенного количества переменных.
курсовая работа [701,9 K], добавлен 27.04.2011Нахождение собственных значений и собственных векторов матриц. Нетривиальное решение однородной системы линейных алгебраических уравнений. Метод нахождения характеристического многочлена, предложенный А.М. Данилевским. Получение формы Жордано: form.exe.
курсовая работа [53,4 K], добавлен 29.08.2010История возникновения булевой алгебры, разработка системы исчисления высказываний. Методы установления истинности или ложности сложных логических высказываний с помощью алгебраических методов. Дизъюнкция, конъюнкция и отрицание, таблицы истинности.
презентация [1,9 M], добавлен 22.02.2014Представление с помощью кругов Эйлера множественного выражения. Законы и свойства алгебры множеств, упрощение выражений. Система функций, ее возможные базисы. Минимизирование булевой функции. Метод Квайна – Мак-Класки. Определение хроматического числа.
контрольная работа [375,6 K], добавлен 17.01.2011