Файл: Дискретная математика.pdf

11

Вариант 3.

A (B (C X )) A (B (C X ))

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

A = {1, 5, 7}

B = {2, 4, 6, 10}

C = {1, 3, 5, 6, 8, 10}

X — ?

Вариант 4.

A (B (C X )) B (C ( A X ))

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

A = {1, 5, 7}

B = {2, 4, 6, 10}

C = {1, 3, 5, 6, 8, 10}

X — ?

Вариант 5.

A X ( X B) X B C

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

A = {2, 3, 4, 7, 10}

B = {1, 2, 6, 9}

C = {3, 5, 7, 9}

X — ?

Вариант 6.

A ( X B) (C X ) ( X A) ( X B) C

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

A = {4, 8, 9}

B = {1, 2, 4, 6, 8, 9}

C = {4, 5, 7, 9}

X — ?

Вариант 7.

( X A) ( X B) C A X (C X )

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

A = {2, 9, 10}

B = {1, 2, 8, 9, 10}

C = {1, 3, 6, 7}

X — ?

12

Вариант 8.

X A X B C X A B

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

A = {3, 4, 5, 6, 10}

B = {1, 2, 3, 7, 9}

C = {3, 4, 5, 8, 10}

X — ?

Вариант 9.

( A X ) (B X ) C A X (C X )

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

A = {1, 3, 5, 6, 8}

B = {2, 4, 6, 9}

C = {2, 6, 7, 10}

X — ?

Вариант 10.

A (B X ) C A (B X ) C X

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {4, 5, 7, 8, 9, 10}

B = {2, 3, 4, 5, 6, 10} C = {4, 5, 7, 8, 10}

X — ?

Вариант 11.

B ( X C) A ( A X ) B X

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

A = {1, 3, 6, 7, 8, 10}

B = {1, 3, 4, 5, 9}

C = {1, 3, 6, 7, 10}

X — ?

Вариант 12.

A B C X A B (C X )

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

A = {1, 4, 10}

B = {3, 5, 6, 7}

C = {3, 6, 7, 10}

X — ?

13

Вариант 13.

A B X X C A B (C X )

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {2, 3, 9, 10}

B = {1, 5, 8}

C = {4, 5, 7}

X — ?

Вариант 14.

( A X ) B X C C X ( A X )

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {1, 4, 8}

B = {1, 5, 7, 10}

C = {3, 6, 7, 10}

X — ?

Вариант 15.

( A X B) (C X ) X ( A X ) C

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

A = {1, 2, 5, 8, 9}

B = {1, 2, 6, 7, 9, 10}

C = {2, 4, 6, 9, 10}

X — ?

Вариант 16.

B X C A B X ( A X )

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

A = {1, 3, 6, 7, 8, 10}

B = {1, 3, 4, 5, 9}

C = {1, 3, 6, 7, 10}

X — ?

Вариант 17.

(C X ) A X ( A X ) B X

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = {3, 7, 9, 10}

B = {1, 3, 8, 9, 10}

C = {2, 4, 5, 6, 7}

X — ?

14

Контрольные вопросы

1.Дать определение понятиям:

—множество, элемент множества;

—конечное множество, мощность множества;

—бесконечное, счетное и несчетное множество;

—пустое множество, универсум;

—подмножество, собственное подмножество;

—булеан, операции над множествами, алгебра подмножеств.

2.Привести примеры задания множества различными способами.

3.Проиллюстрировать операции над множествами и свойства операций диаграммами Эйлера.

4.Вычислить значение выражения в алгебре подмножеств.

5.Определить количество подмножеств заданного множества.

6.Дать определение понятиям:

—первичный терм;

—элементарное пересечение;

—нормальная форма кантора;

—конституента;

—совершенная НФК;

—простая импликанта;

—сокращенная, тупиковая и минимальная НФК.

7.Как получить сокращенную НФК?

8.Что такое импликантная матрица Квайна? Для чего она используется?

9.Доказать теоретико-множественное тождество различными методами.

10.Дать определение теоретико-множественному уравнению.

11.Что такое частное и общее решение теоретико-множественного уравнения?

12.Что является условием существования решения теоретикомножественного уравнения?

13.Как определить мощность общего решение теоретико-множест- венного уравнения?

14.Сравнить способы представления множества в памяти ЭВМ (объем памяти, время выполнения операций).

15.Программно реализовать заданную операцию над множествами при заданном способе представления множества в памяти ЭВМ.

16.Изменить алгоритмы 1.19 и 1.20, используя логические операции вместо операций сравнения.

15

2. КОМБИНАТОРНЫЕ ОБЪЕКТЫ

Л а б о р а т о р н а я р а б о т а № 2.1

Алгоритмы порождения комбинаторных объектов

Цель занятия: изучить основные комбинаторные объекты, алгоритмы их порождения, программно реализовать и оценить временную сложность алгоритмов.

Задания

1.Реализовать алгоритм порождения подмножеств.

2.Построить график зависимости количества всех подмножеств от мощности множества.

3.Построить графики зависимости времени выполнения алгоритмов п.1 на вашей ЭВМ от мощности множества.

4.Определить максимальную мощность множества, для которого можно получить все подмножества не более чем за час, сутки, месяц, год на вашей ЭВМ.

5.Определить максимальную мощность множества, для которого можно получить все подмножества не более чем за час, сутки, месяц, год на ЭВМ, в 10 и в 100 раз быстрее вашей.

6.Реализовать алгоритм порождения сочетаний.

7.Построить графики зависимости количества всех сочетаний из n по k от k при n = (5, 7, 9).

8.Реализовать алгоритм порождения перестановок.

9.Построить график зависимости количества всех перестановок от мощности множества.

10.Построить графики зависимости времени выполнения алгоритма п.8 на вашей ЭВМ от мощности множества.

11.Определить максимальную мощность множества, для которого можно получить все перестановки не более чем за час, сутки, месяц, год на вашей ЭВМ.

12.Определить максимальную мощность множества, для которого можно получить все перестановки не более чем за час, сутки, месяц, год на ЭВМ, в 10 и в 100 раз быстрее вашей.

13.Реализовать алгоритм порождения размещений.

14.Построить графики зависимости количества всех размещений из n по k от k при n = (5, 7, 9).

17

3. Определить, существуют ли решения в заданном k-элементном множестве X целых чисел следующего уравнения:

4.На прямой расположены n равноотстоящих друг от друга узлов. Можно ли в узлах разместить n предметов из n-элементного множества так, чтобы центр тяжести находился в одном из узлов. Вес каждого предмета задан.

5.Задана точка с натуральными координатами (x,y) на целочисленной решетке. Найти “монотонную” траекторию минимальной стоимости, ведущую из начала координат в заданную точку. На каждом шаге “монотонной” траектории можно двигаться только вправо или вверх к соседней точке. Стоимость возможных шагов из каждой точки решетки задана.

6.Есть n станков. Каждый из станков делает различные операции (какие заданы). При обработке детали необходимо выполнить k заданных операций. Найти минимальное множество станков, требуемых для обработки детали.

7.Заданы n2 попарно различных целых чисел. Разместить их, если

можно, в матрице n n так, чтобы суммы строк, столбцов и диагоналей были одинаковыми. Определить количество таких размещений.

8.Найти все решения уравнения x1 + x2 + … + xn = b в натуральных числах, n и b — заданы.

9.Имеется n исполнителей, каждый из которых может выполнять некоторые из n работ. Для каждого исполнителя задано множество работ, которые он может выполнять, и стоимость выполнения каждой работы. Нужно распределить исполнителей по работам, т.е. назначить по одному исполнителю на каждую работу, так, чтобы выполнить все работы, минимизируя затраты.

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

11.Необходимо перевести n тонн груза. Имеется k самолетов гру-

зоподъемностью s1, s2, …, sk тонн, s1 + s2 + … + sk > n. Стоимость рейса c1, c2, …, ck руб. не зависит от массы груза, перевозимого самолетом. Найти оптимальное множество самолетов для перевозки груза.

12.Задано множество предметов. Для каждого предмета известен его вес. Можно ли разделить предметы на две равные по весу части.

13.В матрице n m целых чисел встречаются нули. Можно ли перестановкой строк добиться того, чтобы нули в каждом столбце занимали только самые нижние позиции? Получить все такие матрицы.