Построение полного потока в транспортной сети.
Нахождение корней уравнения

Тип работы:
Контрольная
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Министерство образования Российской Федерации Международный институт «ИНФО-Рутения»

РГГРУ

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

Дискретная математика

Минина Н.В.

г. Старая Русса

Контрольное задание № 1

Задача № 1. Дано одношаговое рекуррентное соотношение с начальным условием. Найти 7-й член последовательности

Решение. Чтобы найти 7-й член последовательности по рекуррентному соотношению, нужно найти все предыдущие. Нулевой член последовательности задан. Чтобы найти первый элемент, поставим в правую часть рекуррентного соотношения. Такая подстановка соответствует присваиванию и можно найти и т. д. Следовательно:. Поставив, получим..

.

.

.

.

.

Ответ:.

Задача № 2. Вычислить

Решение.

.

Задача № 3. Решить уравнение

истинность логический карта карно

Решение.

.

После сокращения получаем. Найдем корни полученного уравнения:.

Ответ:.

Задача № 4. Сколькими способами можно выбрать трех дежурных из группы в 20 человек

Решение. Поскольку порядок в выборке из трех дежурных является не существенным, такая выборка будет неупорядоченной. Поэтому, количество способов, которыми можно выбрать трех дежурных из группы в 20 человек определится сочетанием из 20 человек по 3 дежурным. В результате получим.

Ответ: 1140 способов.

Задача № 5. Даны 2 множества:. Найти их

a) Объединение. Ответ:;

b) Пересечение. Ответ:;

c) Разность. Ответ: ;

d) Симметричную разность. Ответ:.

Контрольное задание № 2

Задача № 1. Построить полный поток в транспортной сети G, приведенной на рисунке (цифрами даны пропускные способности дуг)

Решение. Начинаем с нулевого потока, пологая.

При нулевом потоке отсутствуют насыщенные дуги. Выделим в G простую цепь и увеличим потоки по дугам на 3 до насыщения дуги (). В результате получим поток, содержащий одну насыщенную дугу. Пометим ее крестиком и удалим из орграфа, который снова обозначим.

Выделим в простую цепь и увеличим потоки по дугам этой цепи на 3 до насыщения дуги (). В результате получим поток, величина которого равна и который содержит насыщенную дугу. Удалим эту насыщенную дугу из и оставшийся орграф обозначим.

Выделим в простую цепь и увеличим потоки по дугам этой цепи на 2 до насыщения дуги (). В результате получим поток, величина которого равна и который содержит насыщенную дугу. Удалим эту насыщенную дугу из и оставшийся орграф обозначим.

Выделим в простую цепь и увеличим потоки по дугам этой цепи на 3 до насыщения дуги (). В результате получим поток, величина которого равна и который содержит насыщенную дугу. Удалим эту насыщенную дугу из и оставшийся орграф обозначим.

Выделим в простую цепь и увеличим потоки по дугам этой цепи на 2 до насыщения дуги (). В результате получим поток, величина которого равна и который содержит насыщенную дугу. Удалим эту насыщенную дугу из и оставшийся орграф обозначим.

В оставшемся не существует пути их, который не содержал бы насыщенных дуг, т. е. поток является полным и его величина равна 13.

Задача № 2. По данному логическому выражению построить таблицу истинности без предварительного упрощения функции

.

Построим таблицу истинности по частям, предварительно построив таблицу истинности для каждой конъюнкции, а затем в последнем столбце запишем логическую сумму (дизъюнкцию) соответствующих значений трех конъюнкций.

А

В

С

F

0

0

0

1

0

0

0

0

0

0

1

1

0

0

0

0

0

1

0

0

0

0

0

0

0

1

1

0

0

0

0

0

1

0

0

1

0

0

0

0

1

0

1

1

0

1

0

1

1

1

0

0

0

0

0

0

1

1

1

0

1

0

1

1

Логические переменные А, В и С принимают всего значений, причем в таком порядке, что если перевести приведенные триады из двоичной системы в десятичную то получим числа от 0 до 7. В столбцах 5, 6 и 7 приведены элементарные конъюнкции, значения которых определяются перемножение соответствующих логических переменных. Значения дизъюнкций, приведенное в 8 столбце таблицы, определяется суммой соответствующих конъюнкций.

Задача № 3. Функция задана десятичными эквивалентами единичных значений. Представить эту функцию в виде СДНФ или в виде СКНФ.

.

Поскольку в списке 14 чисел, т. е. 14 эквивалентов единичных значений, следовательно нулевых значений два (16−14=2). Поэтому по таблице истинности целесообразней строить СКНФ.

Построим таблицу истинности. В первом столбце укажем десятичные эквиваленты соответствующих наборов.

N

F

1

0

0

0

1

0

2

0

0

1

0

0

3

0

0

1

1

0

4

0

1

0

0

0

5

0

1

0

1

0

6

0

1

1

0

0

7

0

1

1

1

0

8

1

0

0

0

0

9

1

0

0

1

1

10

1

0

1

0

1

11

1

0

1

1

0

*

12

1

1

0

0

0

*

13

1

1

0

1

0

14

1

1

1

0

1

15

1

1

1

1

1

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

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

.

Задача № 4. Упростить логические выражения с помощью карты Карно

.

Известно, что конъюнкции соответствует пересечение областей карты Карно, соответствующих сомножителям, а дизъюнкции соответствует объединение областей, соответствующих слагаемым. Конъюнкции второго ранга на карте Карно соответствует 4 клеточки. Затененная область на рис. 1,2,3 соответствует конъюнкциям соответственно. На рис. 4 показано пересечение областей, соответствующих множителям. В соответствующих клетках пересечения областей стоят единицы и штриховкой показана область клеток для переменной.

В

В

А

А

С

С

D

D

Рис. 1. Область Рис. 2. Область

Клетки имеющие затенение и штриховку одновременно соответствуют исходной функции. Объединив эти три единицы в две пары, получим представление исходной функции в виде дизъюнкции двух конъюнкций третьего ранга.

В

В

А

А

С

1

1

С

1

D

D

Рис. 3. Область Рис. 4. Заполнение карты Карно

ПоказатьСвернуть
Заполнить форму текущей работой