Размещено на http://www.allbest.ru

Контрольная работа № 1

1. Даны множества А, В, С. Количество элементов: |A|=15; |B|=15; |C|=20; |A?B|=8; |A?C|=10; |B?C|=9; |A?B?C|=5. Всего элементов в U 47. Найти количество элементов в дополнении к объединению всех трех множеств.

Решение

Используем формулу включений и исключений для определения мощности объединения множеств А, В, С.

=|A|+|B|+|C| -|A?B|-|A?C|-|B?C|+|A?B?C|=15+15+20-8-10-9+5=28

2. Упростить выражение и нарисовать диаграмму Эйлера-Венна для множества множество граф неориентированный булевой

Решение

= применим правило де Моргана

=(применим свойство дистрибутивности

=((C)= (

3. Перевести 506, В13₁₆ в 13-ю систему счисления с креном

на 2 в «-».

Решение

Переведем целую часть в систему счисления с основанием 10:

Затем переведем в систему счисления с основанием 13:

=

Переведем дробную часть в систему счисления с основанием 10:

0,=++=

=0+0,6875+0,00390625+0,000732421875=

Затем переведем в систему счисления с основанием 13:

506,=

Контрольная работа № 2

1. Найти Эйлерову цепь в неориентированном графе

Эйлерова цепь - путь в графе, который проходит по всем ребрам графа, причем по каждому - только один раз. При наличии в графе ровно двух вершин нечетной степени, эйлерова цепь существует, если началом и концом ее выбраны вершины нечетной степени. Построим ее:

-

2. Найти минимальное остовное дерево в неориентированном нагруженном графе:

1) вручную

2) матричным способом

1) Алгоритм Краскала: добавляем ребра в остов в порядке возрастания их веса, исключая образования циклов.

(v6,v8), (v4,v6), (v5,v7), (v2,v8), (v5,v6), (v6,v1), (v3,v4)

Вес остова равен 22.

2) В матрице смежности А размером n*n выбираем минимальный элемент , строим подграф включающий вершины i и j и ребро (i,j). k=2 -количество вершин. l()=.

Если n()=n, алгоритм заканчивает работу. Иначе, строим граф , добавив к ребро, соответствующее минимальному элементу среди оставшихся, инцидентное какой-либо вершине из и одновременно вершине, не принадлежащей . Повторяем действия, пока k не станет равно n.

={(v6,v8), v6, v8}

={(v6,v8), v6, v8, (v6,v4),v4}

={(v6,v8), v6, v8, (v6,v4),v4, (v2,v8),v2}

={(v6,v8), v6, v8, (v6,v4),v4, (v2,v8),v2, (v5,v6),v5}

={(v6,v8), v6, v8, (v6,v4),v4, (v2,v8),v2, (v5,v6),v5, (v5,v7),v7}

={(v6,v8), v6, v8, (v6,v4),v4, (v2,v8),v2, (v5,v6),v5, (v5,v7),v7, (v6,v1), v1}

={(v6,v8), v6, v8, (v6,v4),v4,(v2,v8),v2, (v5,v6),v5, (v5,v7),v7, (v6,v1), v1, (v4,v3),v3}

Вес остова равен 22.

3. Найти расстояния в ориентированном графе D: диаметр, радиус и центры

1. Определим расстояние между парами вершин:

d(v1,v2)=1 d(v1,v3)=2 d(v1,v4)=3 d(v1,v5)=1d(v1,v6)=1 d(v1,v7)=2

d(v2,v1)=2 d(v2,v3)=1 d(v2,v4)=2 d(v2,v5)=1 d(v2,v6)=3 d(v2,v7)=3

d(v3,v1)=3 d(v3,v2)=4 d(v3,v4)=1 d(v3,v5)=2 d(v3,v6)=2 d(v3,v7)=2

d(v4,v1)=3 d(v4,v2)=3 d(v4,v3)=2 d(v4,v5)=1 d(v4,v6)=1 d(v4,v7)=1

d(v5,v1)=1 d(v5,v2)=2 d(v5,v3)=1 d(v5,v4)=2 d(v5,v6)=2 d(v5,v7)=3

d(v6,v1)=3 d(v6,v2)=4 d(v6,v3)=3 d(v6,v4)=2 d(v6,v5)=2 d(v6,v7)=1

d(v7,v1)=2 d(v7,v2)=3 d(v7,v3)=2 d(v7,v4)=1 d(v7,v5)=1 d(v7,v6)=2

2. Определим диаметр как =

3. Определим эксцентриситет каждой вершины:

4. Определим радиус графа как ): =3

5. Определим центральные вершины:v1,v2, v4, v5, v7.

4. Найти минимальный путь в нагруженном графе с помощью алгоритма Дейкстры. Из вершины до всех остальных.

Решение

Рассмотрим отдельные шаги решения.

1. Вершина получает постоянную метку 0, остальные -- метку ?:

2. Вычисляем расстояния от вершины 1 с постоянной меткой 0.Вершины 2, 5 и 7 меняют свои временные метки на 9, 4 и 4.Остальные имеют прежние метки -- ?. Очевидно, наименьшей меткой является 4 для вершины 5. Она и становится постоянной:

3. Вычисляем расстояния от вершины 5 с постоянной меткой 4. Вершины 4 и 6меняют свои временные метки на 13 и 11. Для вершины 7 прежнее значение, 4, было меньше нового значения 5. Следовательно, значение метки7 не меняем; оно остается равным 4. Из трех временных меток-- 13, 11 и 4 -- наименьшая принадлежит вершине 7. Эта метка становится постоянной:

4. Вычисляем расстояния от вершины 7 с постоянной меткой 4. Для вершины 6 прежнее значение, 11,было больше нового значения 10. Меняем на временную 10. Из трех временных меток-- 9, 13 и 11 -- наименьшая, принадлежит вершине 2. Эта метка становится постоянной:

5. Вычисляем расстояния от вершины 2 с постоянной меткой 9. Для вершины 6 прежнее значение, 10,было меньше нового значения 21.Не меняем. Для вершины 3 меняем на 16. Из трех временных меток-- 16, 13 и 10 -- наименьшая, принадлежит вершине 6. Эта метка становится постоянной:

6. Вычисляем расстояния от вершины 6 с постоянной меткой 10. Для вершины 4 прежнее значение, 13,было меньше нового значения 18. Не меняем. Для вершины 3 меняем на 11. Из двух временных меток-- 11 и 13 -- наименьшая, принадлежит вершине 3. Эта метка становится постоянной:

Метку у вершины 4 не меняем. Все расстояния найдены.

Контрольная работа № 3

1. Минимизировать представление булевой функции методом Квайна - Мак-Класки и изобразить схему И-НЕ для нее

Булевой функцией называют функцию , у которой все независимые аргументы  и сама функция являются логическими переменными, принимающими только два значения: 0 и 1. Эти функции могут быть заданы аналитически в виде пропозициональной формулы (ПФ) геометрически или с помощью таблиц истинности.

Построим таблицу истинности

= =

(выполняем склеивание элементарных конъюнкций)

= =

(используем тождество =

=

Построим импликантную таблицу:

Сокращенная ДНФ является минимальной так как ни один импликант нельзя удалить.

Чтобы перейти к базису И - НЕ воспользуемся правилом де Моргана

=

Схема, реализующая данную функцию:

2. Минимизировать представление слабо определенной булевой функции методом Квайна

Задача до определения сводится к тому, чтобы из возможных вариантов выбрать тот, который позволит получить минимальную форму записи функции.

МДНФ не полностью определенной логической функции получается как дизъюнкция наиболее коротких по числу букв импликант функции, принимающих значение единицы на всех кортежах частичной функции, которые в совокупности покрывают все импликанты СДНФ для частичной функции, принимающей значение нуля на всех кортежах, где она не определена.

=

Все элементарные конъюнкции ДНФ принимают значение 0 на заданных нулевых наборах. Для минимизации ДНФ доопределим функцию.

В первом единичном наборе положим =0, в третьем - =1. =>

= =

поглощение первой элементарной конъюнкции

=

Литература

1. Алексеев В.Е. Графы и алгоритмы. Структуры данных. Модели вычислений : учебник / В. Е. Алексеев, В. А. Таланов. - М. : Интернет-Ун-т Информ. Технологий ; М. : БИНОМ. Лаборатория базовых знаний, 2006. - 319 с. - (Основы информационных технологий).

2. Сагадеева М.А. Теория графов : учеб. пособие / М. А. Сагадеева ; Южно-Уральский институт управления и экономики. - Челябинск: Полиграф-Мастер, 2010. - 138 с.

3. Триумфгородских, М. В. Дискретная математика и математическая логика для информатиков, экономистов и менеджеров [Электронный ресурс]: учебное пособие / М. В. Триумфгородских. - М.: Диалог-МИФИ, 2011. - 180 с. - 978-5-86404-238-0.

Размещено на Allbest.ru