Главная Учебники - Разные Лекции (разные) - часть 51
Содержание Введение Задание 1 Представить с помощью кругов Эйлера множественное выражение Используя законы и свойства алгебры множеств, упростить заданное выражение Задание 2 Заданы множества кортежей Показать, что эти множества представляют собой соответствия между множествами N1
и N2
, если N1
= N2
= Задание 3 Частично упорядоченное множество М задано множеством упорядоченных пар Построить диаграмму и определить, является ли данное множество решеткой. Если заданное множество является решеткой, то определить, является ли решетка дедекиндовой , дистрибутивной … Задание 4 Является ли полной система булевых функций Задание 5 Минимизировать булеву функцию Задание 6 Для неориентированного графа а) вычислить числа б) определить хроматическое число Задание 7 Для заданной сети а) найти величину минимального пути и сам путь от вершины б) используя алгоритм Форда-Фалкерсона, определить максимальный поток Литература Введение Проблемы, связанные с понятиями бесконечности, дискретности и непрерывности, рассматривались в математике, как и в философии, древнегреческими мыслителями, начиная с 6 века до нашей эры. Под влиянием сочинений Аристотеля они широко обсуждались средневековыми учеными и философами в странах Европы и Азии. Через всю историю математики проходит идея преодоления между актуальной и потенциальной бесконечностью, с одной стороны, между дискретным характером числа и непрерывной природой геометрических величин – с другой. Впервые проблема математической бесконечности и связанных с нею понятий была широко поставлена в наиболее общем виде в теории множеств, основы которой были разработаны в последней четверти 19 века Георгом Кантором. Цель контрольной работы – ознакомится с основными понятиями и методами решения по дискретной математике, уметь применить полученные знания при решении практического задания. Задание 1 Представить с помощью кругов Эйлера множественное выражение Используя законы и свойства алгебры множеств, упростить заданное выражение. Решение:
Используя круги Эйлера и, учитывая, что операция пересечения выполняется раньше операции объединения, получим следующие рисунки: Объединяя заштрихованные области, получим искомое множество: Упростим заданное выражение: Задание 2 Заданы множества кортежей: Показать, что эти множества представляют собой соответствия между множествами N1
и N2
, если N1
= N2
= Решение:
Найдем декартово произведение: Видно, что заданные множества являются подмножествами этого пря-мого произведения. Следовательно, данные множества есть соответствия. а) Область определения: Область значений: Образом элемента б) Область определения: Область значений: Образом любого элемента из в) Область определения: Область значений: Образом любого элемента из г) Область определения: Область значений: Образом любого элемента из N1
является единственный элемент из N2
. Следовательно, соответствие является функциональным, функцией. Так как соответствие всюду определено, сюръективно, функционально и прообразом любого элемента из Так как функция полностью определена и соответствие сюръективно, то имеем отображение N1
на N2
. Так как для любых двух различных элементов из N1
их образы из N2
также различны, то отображение является инъективным. Так как отображение является одновременно сюръективным и инъективным, то имеем биективное отображение (взаимно однозначное отображение). Задание 3 Частично упорядоченное множество М задано множеством упорядоченных пар Построить диаграмму и определить, является ли данное множество решеткой. Если заданное множество является решеткой, то определить, является ли решетка дедекиндовой , дистрибутивной. Решение:
Построим диаграмму: Построим таблицу: Пары элементов Так как любая пара элементов имеет единственную наибольшую нижнюю грань и единственную наименьшую верхнюю грань, то заданное частично упорядоченное множество М является решеткой. Решетка М является дедекиндовой, когда выполняется равенство: для таких Решетка М не является дедекиндовой, т.к. указанное равенство не вы-полняется, например, для элементов 2, 3, 4: Одним из условий дистрибутивности решетки является ее дедекиндо-вость. Так как решетка М не является дедекиндовой, то она не является дистрибутивной решеткой. Задание 4 Является ли полной система булевых функций Решение:
Рассмотрим функцию 1. Принадлежность функции к классу Следовательно, 2. Принадлежность функции к классу Следовательно, 3. Принадлежность функции к классу Предположим, что функция линейная и, следовательно, представима в виде полинома Жегалкина первой степени: Найдем коэффициенты Фиксируем набор 000: Следовательно, Фиксируем набор 100: Следовательно, Фиксируем набор 010: Следовательно, Фиксируем набор 001: Следовательно, функция (по нашему предположению) может быть представлена полиномом вида: Если функция линейная, то на всех остальных наборах ее значение должно равняться 1. Но на наборе 111 4. Принадлежность функции к классу Функция самодвойственная, если на любой паре противоположных наборов (наборов, сумма десятичных эквивалентов которых равна Вычисляем Строим таблицу: (000) 0 (001) 1 (010) 2 (011) 3 (100) 4 (101) 5 (110) 6 (111) 7 На наборах 1 и 6, 2 и 5, 3 и 4 функция принимает одинаковые значения. Следовательно, 5. Принадлежность функции к классу Из таблицы видно: 000 < 111 , но Рассмотрим функцию 1. Принадлежность функции к классу Следовательно, 2. Принадлежность функции к классу Следовательно, 3. Принадлежность функции к классу Предполагаем, что Фиксируем набор 000: Фиксируем набор 100: Фиксируем набор 010: Фиксируем набор 001: Окончательно получаем Это равенство не соблюдается на наборе 011: Следовательно, 4. Принадлежность функции к классу Вычислим значения функции на оставшихся наборах: Строим таблицу : (000) 0 (001) 1 (010) 2 (011) 3 (100) 4 (101) 5 (110) 6 (111) 7 Из таблицы видно, что на наборах 3 и 4 функция принимает одинаковые значения. Следовательно, 5. Принадлежность функции к классу Из таблицы видно, что 111 > 000 , но Строим критериальную таблицу: В таблице в каждом столбце стоят минусы. Следовательно, система булевых функций является полной . Найдем все возможные базисы. По критериальной таблице составим КНФ : Приведем КНФ к ДНФ : По полученной ДНФ выписываем искомые базисы: Задание 5 Минимизировать булеву функцию Решение:
1 этап. Определение сокращенной ДНФ. По десятичным эквивалентам запишем 0-кубы : Выполним разбиение на подгруппы: Строим Выполняем разбиение всех Выполняем сравнение кубов внутри каждой подгруппы с целью построения Выполняем сравнение кубов внутри каждой подгруппы с целью построения Так как они одинаковы, то Запишем сокращенную ДНФ, в которую должны быть включены им-пликанта из К 3
и импликанты, не участвовавшие в склеивании (в нашем случае таких импликант нет) : 2 этап. Определение тупиковой ДНФ. Так как все импликанты участвовали в склеивании, и сокращенная ДНФ состоит из одной простой импликанты, то строить таблицу покрытий нет необходимости, т.е. Задание 6 Для неориентированного графа а) вычислить числа б) определить хроматическое число Решение:
Построим граф: а) Вычислим числа 1) Используя алгоритм выделения пустых подграфов, построим дерево: Согласно определению 2) Используя алгоритм выделения полных подграфов, построим дерево: Здесь 3) Построим модифицированную матрицу смежности 1 2 3 4 5 6 Находим минимальное число строк, покрывающих все столбцы модифи-цированной матрицы . Таких строк – одна. Следовательно, б) Определим хроматическое число Согласно алгоритму минимальной раскраски вершин графа, выделим все пустые подграфы графа G , т.е. построим дерево (оно построено в пункте а) ): Построим таблицу: 1 2 3 4 5 6 1. {1,4,6} 1 1 1 2. {1,5} 1 1 3. {2,5} 1 1 4. {2,6} 1 1 5. {3} 1 Определяем минимальное число строк, покрывающих все столбцы таблицы. Такими строками могут быть строки 1, 3, 5. Значит, Зададимся красками: для множества вершин Раскрасим вершины графа G : Задание 7 Для заданной сети а) найти величину минимального пути и сам путь от вершины б) используя алгоритм Форда-Фалкерсона, определить максимальный поток если задана матрица весов (длин, пропускных способностей) Р : v1
v2
v3
v4
v5
v6
Решение:
Построим сеть: а) Найдем величину минимального пути и сам путь сети G . Используем для этого алгоритм Дейкстры. Этап 1. Нахождение длины кратчайшего пути. Шаг 1. Полагаем 1-я итерация. Шаг 2. Составим множество вершин, непосредственно следующих за Шаг 3. Одна из временных меток превращается в постоянную: Шаг 4. 2-я итерация. Шаг 2. Шаг 3. Шаг 4. 3-я итерация. Шаг 2. Шаг 3. Шаг 4. 4-я итерация. Шаг 2. Шаг 3. Шаг 4. 5-я итерация. Шаг 2. Шаг 3. Шаг 4. Следовательно, длина кратчайшего пути равна Этап 2. Построение кратчайшего пути. 1-я итерация. Шаг 5. Составим множество вершин, непосредственно предшествующих для этих вершин: Включаем дугу Шаг 6. 2-я итерация. Шаг 5. Включаем дугу Шаг 6. Следовательно, кратчайший путь построен. Его образует последовательность дуг: Окончательно, кратчайший путь от вершины б) Определим максимальный поток Выбираем произвольно путь из вершины v1
в вершину v6
. Пусть это будет путь Путь Других маршрутов нет (другие маршруты проходят через насыщенные дуги). Поток максимален. Делаем разрез вокруг вершины v1
по насыщенным дугам и получаем его величину 8. Используя алгоритм Краскала, построить остов с наименьшим весом для неориентированного взвешенного графа □ Построим граф G : 1. Упорядочим ребра в порядке неубывания веса (длины): 2. Возьмем ребро u1
и поместим его в строящийся остов. Возьмем ребро u2
и поместим его в строящийся остов (т.к. оно не образует с предыдущим ребром цикла). Берем ребро u3
и помещаем его в строящийся остов (т.к. оно не образует с предыдущими ребрами цикла). Берем ребро u4
и помещаем его в строящийся остов (т.к. оно не образует с предыдущими ребрами цикла). Берем ребро u5
и помещаем его в строящийся остов (т.к. оно не образует цикла с предыдущими ребрами). Ребра Проверим окончание алгоритма. Число входящих в остов ребер равно 5. Заданный граф имеет п = 6 вершин и Вес (длина) построенного остова равен Литература 1. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986. – 311 с. 2. Коршунов Ю.М. Математические основы кибернетики. – М.: Энерго атомиздат, 1987. – 496 с. 3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988. – 480 с. 4. Шапорев С.Д. Дискретная математика. – СПб.: БХВ-Петербург, 2006. - 400 с. 5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. – М.: ФИЗМАТЛИТ, 2005. – 416 с. 6. Хаханов В.И., Чумаченко С.В. Дискретная математика ( конспект теоретического материала). – Харьков: ХНУРЭ, 2003. – 246 с. 7. Богданов А.Е. Курс лекций по дискретной математике.–Северодонецк: СТИ, 2006. – 190 с.
|