1.8 Представление множеств в эвм

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

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

Следует подчеркнуть, что, как правило, один и тот же объект может быть представлен многими разными способами, причем нельзя указать способ, который является наилучшим для всех возможных случаев.

Выбор представления зависит от целого ряда факторов: особенностей представляемого объекта, состава и относительной частоты использования операций в конкретной задаче и т. д. Умение выбрать наиболее подходящее представление для данного случая является основой для практического программирования.

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

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

Пусть универсум U – конечный и число элементов в нём не превосходит разрядность ЭВМ: . Элементы универсума нумерованы: Подмножество А универсума U представляется кодом (машинным словом) С, в котором:

где - это i-й разряд кода С.

Код пересечения множеств А и В есть поразрядное логическое произведение кода множества А и кода множества В. Код объединения множеств А и В есть поразрядная логическая сумма кода множества А и кода множества В. Код дополнения множества А есть инверсия кода множества В.

В большинстве ЭВМ для этих операций есть соответствующие машинные команды. Таким образом, операции над небольшими множествами выполняются весьма эффективно.

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

Если универсум очень велик (или бесконечен), а рассматриваемые подмножества не очень велики, то множества обычно представляются списками элементов.

Элемент списка при этом представляется записью с двумя полями: информационным и указателем на следующий элемент. Если элементы в списках упорядочить, например, по возрастанию значения информационного поля, то трудоёмкость всех операций составит О(n). Существует весьма общий алгоритм, известный как алгоритм типа слияния для эффективной реализации операций над множествами, представленными в виде упорядоченных списков.

Задачи для самостоятельного решения

1. Доказать, что {}  .

2. Доказать, что существует лишь одно множество, не имеющее элементов

3. Доказать, что {{0, 1}, {0, 2}}{0, 1, 2}.

4. Осуществить операции над множествами:

A={2, 4, 6, 8}, B={3, 6, 9}, если U={1, 2, 3, …, 10}.

5. Осуществить операции над множествами А, В  U, если A={a, b, d}; B={b, d, e, h}, U={a, b, c, d, e, f, g, h}.

6. Пусть A={1, 2}, B={2, 3}, C={1, 3}. Найти:

а) ; б) ; в) ;

г) ; д) .

7. Указать, какие из следующих выражений справедливы:

а) 0; б)  = {0}; в) |{}| = 0; г) || = 0?

8. Пусть U={a, b, c, d}, X={a, c}, Y={a, b, d}, Z={b, c}.

Найти множества: а) ; б) ;

в); ; г); ; д) ;

е) ; ж) ; з) ;

и) ; к) ; л) .

8. Найти множества: а) ; б) ; в) ;

г) ; д) ; е) ; ж),

если U={1, 2, 3, 4, 5, 6}; A={1, 2, 3}; B={1, 3, 5, 6};

C={4, 5, 6}.

9. Даны два произвольных множества А и В такие, что . Что представляет собой и ?

10. Даны два произвольных множества C и D такие, что .Что можно сказать о и ?

11. Дано произвольное множество Х. найти множества:

а) ; б) ; в) .

12. Пусть [0, 1], [0, 2] – отрезки на числовой прямой. Дать геометрическую интерпретацию множеств: [0, 1][0, 2], [0, 1]², [0, 2]³.

13. Какие утверждения верны для всех X, Y, Z?

а) Если XY и YZ, то XZ, б) Если XY и YZ, то XZ,

в) Если и , то,

г) Если XY и YZ, то XZ.

12. Существуют ли такие множества X, Y, Z, что ; ; ?

13. Доказать, что .

14. Построить диаграммы Венна для задачи 8.

15. Пусть A, B, С  U. С помощью диаграмм Венна доказать:

а);

б) ;

в) ; г) ;

д) ; е) ;

ж) ; з). .

12. Доказать следующие тождества:

а);

б) ;

в) ; г) ;

д)

е) ; ж). .

12. Доказать, что

а) ;

б) ; в) ;

г) ;

д) ;

е) ;

ж) .

12. Определить операции ; - через операции :

а) ; б) ; в) .

12. Доказать, что характеристическая функция множеств удовлетворяет следующим условиям:

;

;

;

12. Найти все подмножества множеств

, {}, {x}, {1, 2}

12. Доказать, что:

а); ;

б) любое уравнение относительно множества Х, в правой части которого стоит , равносильно уравнению , где А и В – некоторые множества, в записи которых не содержится символ Х

в) система уравнений имеет решение тогда и только тогда, когда. При этом условии решением системы является любое множество Х такое, что .

Описать метод решения системы уравнений с одним неизвестным.

12. Решить систему уравнений ,

где А, В и С – данные множества, причем .

12. Пусть X={0, 1, 2, 3}, Y={a, b, c}. Найти XY, YX.

13. Доказать, что

а) ;

б) ;

в) ; г) .