Тема 11. Частичные булевы функций
Тема 11. Частичные булевы функций Краткая теория Булева функция называется частичной, если она определена не на всем множестве , а лишь на некотором его подмножестве. Частичные функции можно задавать аналогично общим функциям одномерными и двумерными таблицами с учетом того, что соответствующие наборы не пишутся, либо на соответствующих наборах значение функции игнорируется. Особый интерес вызывает задача доопределения частичных булевых функций с целью возможности записи их аналитическими выражениями, а в частности минимизации. Основная идея состоит в том, чтобы так доопределить частичную булеву функцию, чтобы ее МДНФ была самой короткой из всех возможных доопределения.
Примеры решения задач Задача. Минимизировать частичную булеву функцию Решение: Графический метод.
Анализируя полученный результата очевидно, что функцию необходимо доопределить следующим образом:
МДНФ: . Аналогично можно проводить рассуждения и для метода Квайна и для метода карт Карно. В общем случае необходим полный перебор всех возможных дополнений.
Упражнения 1. Минимизировать различными методами частичную булеву функцию: a) b) c)
Дополнительные упражнения 2. Минимизировать методом карт Карно частичную булеву функцию:
a) b)
Тема 12. Различные способы задания графов. Операции над графами Краткая теория Граф ( ) определяется двумя множествами: V – множество вершин, Е – множество ребер (дуг). Элементы из Е представляют собой неупорядоченные (упорядоченные) пары из V. Граф содержащий только ребра называется неориентированным графом (неограф), а граф содержащий только дуги – ориентированным графом (орграф). Операция над графами (без кратных ребер и петель): 1. Дополнением графа (обозначается ) называется граф множество вершин которого совпадает с множеством вершин исходного графа, а множество ребер (дуг) состоит из всех тех ребер (дуг) которые дополняют данный граф до полного графа. 2. Объединением графов и (обозначается ) называется граф такой, что , . 3. Пересечением графов и (обозначается ) называется граф такой, что . 4. Соединением (сложением) графов и (обозначается ), при условии и называется граф такой, что , . 5. Удаление вершины из графа (обозначается ) дает граф такой, что , . 6. Удаление ребра из графа (обозначается ) дает граф , где .
Примеры решения задач Задача. Для графически заданного графа найти матрицы смежности и инцидентности.
Решение: Матрица смежности графа
Матрица инцидентности графа
Упражнения 1. Для графа заданного матрицей смежности найти графическое задание и матрицу инцидентности:
2. Для графа заданного матрицей смежности найти графическое задание и матрицу инцидентности:
3. Выполните действия и найдите соответствующую матрицу смежности для графа : a) = ;
b) = ; c) = ; d) = ; e) = ; f) = ( ) – ; g) = ( ) – (1, 3); где , , матрицы смежности для графов , и соответственно.
Тема 13. Минимальные деревья Краткая теория Деревом называется связный граф без циклов. Матрицей весов графа называется матрица смежности в ячейках которой стоят веса соответствующих ребер (дуг) и знак бесконечности в случае отсутствия соответствующего ребра. Минимальным деревом называется остовное дерево графа с минимальным суммарным весом ребер. Жадный алгоритм построения минимального дерева: На каждом шаге алгоритма берется ребро с минимальным весом, не образовывающее циклов в строящемся графе. Алгоритм ближайшего соседа построения минимального дерева: В качестве исходной берется любая вершина графа. После этого, среди всех ребер инцидентных данной вершине берется ребро с наименьшим весом и включается в строящееся дерево. В дальнейшем к строящемуся дереву добавляются ребра, не образовывающие цикла, инцидентные какой-либо его вершине. Алгоритм удаления максимальных циклических ребер: На каждом шаге алгоритма удаляется ребро с максимальным весом образующее цикл в модифицируемом графе.
Воспользуйтесь поиском по сайту: ©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|