Графический метод минимизации булевых функций:


Типовые примеры на применение функции Патрика для отыскания всех тупиковых и минимальных ДНФ для заданной булевой функции:


Пример А.
Найти все тупиковые и минимальные ДНФ для булевой функции четырёх переменных, заданной вектором:
  1. (0100 1100 1101 1011)
  2. (1101 0111 1111 0001)
  3. (1110 0111 1011 0001)
  4. (1100 0101 1010 1011)
Пример Б.
Найти все тупиковые и минимальные ДНФ для булевой функции трёх переменных, заданной вектором:
  1. (0111 1110)
  2. (1111 0101)
  3. (1101 1011)

Пример построения функции Патрика для отыскания всех тупиковых и минимальных ДНФ:


Пример решения задачи минимизации методом Квайна—Макласки


Использование функции Патрика для отыскания всех тупиковых и минимальных ДНФ (Пример 2)


Использование функции Патрика для отыскания всех тупиковых и минимальных ДНФ (Пример 3)


Пример решения задачи минимизации методом Карно


Демонстрационные варианты контрольной работы


Типовые задачи



Потоковая контрольная работа 28 апреля 2017 года

Задача 1. Найти ДНФ сокращенную, ядровую, минимальные и тупиковые для функций f(x,y,z) и g(x,y,z), используя графический метод.

Задача 2. Найти ДНФ сокращенную, ядровую, минимальные и тупиковые для функции f(x_1,x_2,x_3,x_4) и g(x,y,z), используя метод Карно либо метод Квайна -- Макласки.
 
Задача 3. Доказать по теореме Поста полноту системы булевых функций; выразить формулами над этой системой следующие функции: 1, 0, отрицание, конъюнкцию, дизъюнкцию.
 
Задача 4. Доказать по теореме Поста полноту системы булевых функций; выразить формулами над этой системой следующие функции: 1, 0, отрицание, конъюнкцию, дизъюнкцию.

Сами варианты представлены на фото доски (ниже).


К решению задачи об оптимальном назначении (с максимальной суммарной эффективностью)

Ниже разобран пример решения задачи об оптимальном назначении с матрицей эффективностей размера 4x4

Пример построения максимального потока в транспортной сети

На приведённом ниже снимке слева представлено поэтапное построение максимального потока f_max за счет нагружения 6 цепей, соединяющих источник со стоком (цепи показаны схематично под изображением сети).
Справа приведён заключительный граф перестройки, который позволяет найти минимальный разрез \Sigma в сети. Этот разрез есть объединение 5 рёбер, перечисленных непосредственно. На самом чертеже сети разрез выделен дугой.
 
Заметьте!
Величина максимального потока f_max совпадает с пропускной способностью разреза \Sigma (и равна 14).


Пример решения задачи на построение максимального потока и отыскание минимального разреза в транспортной сети

Замечания:
  1. графы перестройки строим, начиная с 5-го этапа (см. G_1 на фото);
  2. на 5-м этапе находим цепь с реверсным ребром;
  3. заключительный граф перестройки G_2 позволяет найти минимальный разрез.

Пример (2) решения задачи на построение максимального потока и отыскание минимального разреза в транспортной сети

Замечания:
  1. графы перестройки строим, начиная с 6-го этапа (см. G_1 на фото);
  2. на 6-м этапе находим цепь с реверсным ребром;
  3. заключительный граф перестройки G_2 позволяет найти минимальный разрез.


Пример решения задачи на оптимальное назначение

Замечания:
  1. находим совершенное паросочетание на 3-ем шаге;
  2. на первом и втором шаге имеем один и тот же подграф G_1=G_2, соответствующий выделенным элементам матрицы эффективностей, выбираем на нём одно и то же множество вершин S, выделенное кружками (всё множество вершин левой доли подграфа G_1=G_2), в соответствии с теоремой Холла;
  3. существует два решения (см. фото)


Пример решения задачи на отыскание кратчайшего пути на графе между начальной и конечной вершинами (метод Дейкстры)

Алгоритм включает прямой и обратный проходы между выделенными вершинами, в данном случае v_0 и v_8.
1) Прямой проход
Шаг за шагом, начиная с вершины v_0, присваиваем метки всем вершинам. При этом заполняется протокол. Временные метки постепенно меняются на постоянные (по протоколу видно это изменение).
Когда метки у всех вершин становятся "постоянными", метка вершины v_8 указывает на длину искомого кратчайшего пути.
2) Обратный проход
Находим кратчайший путь, строя его с конца от вершины v_8.
На каждом ребре, входящем в этот путь, выполнено условие: разность меток в концах равна длине ребра.


Пример решения задачи на отыскание минимального остова для заданного взвешенного графа (алгоритм Краскала)

Алгоритм начинается с сортировки ребер по длине (весу): составляется список ребер по возрастанию длины.
На фото выделены сначала ребра длины 1, затем длины 2, затем длины 3...
 
Далее последовательно в остов включаются ребра из списка (выделяются жирно на чертеже графа), при этом отбраковываются те ребра, которые приводят к образованию циклов (на фото они зачеркнуты в списке).
 
Алгоритм заканчивается, когда набирается ребер на единицу меньше, чем вершин в графе, или когда остовом захвачены все вершины графа.
 
Напоминание:
Остов графа - подграф со всеми вершинами графа, являющийся деревом.
Дерево - это связный граф без циклов.