чисел, то

t=l 1=1

означают соответственно сумму и произведение всех элементов V.

7. VVi~\ Наименьшее целое число, большее или равное Vi.

w,.J Наибольшее целое число, меньшее или равное Vi.

8. V=c» V - бесконечное множество, т. е. оно содержит

бесконечное счетное число элементов. V<co V - конечное множество.

9. Если I, k - положительные целые числа, то i!=iX (i-1)Х. . .X

Х2х1 читается «i-факториал» (см. разд. 4.5).

(j) читается «число сочетаний из i по /» и означает

число способов выбора / разных объектов из i разных

объектов.

10. Гармонический ряд - это бесконечный ряд рациональных чисел

I 11

называется iV-й частной суммой гармонического ряда.

Б.2. Применение множеств и операции на множествах

Как узнать, является ли данный элемент и элементом множества V? Глядя на F и проверяя, находится ли и там, ие правда ли? Проблема, однако, состоит в следующем: как может ЭВМ «смотреть» на V и проверять наличие ы? Это задача представления множества в машине. Здесь будет дан один очень простой ответ. Возможны и другие ответы.

Особенно простое представление возможно, если мы предполагаем, что все рассматриваемые множества являются подмножествами некоторого конечного универсального множества V. Пусть U содержит п различных элементов, помеченных как 1, 2, . . ., п (каждый элемент помечен определенным целым числом). Мы можем представить любое подмножество V множества U цепочкой, или последовательностью, нулей и единиц. Если i-я позиция, или бит, этой цепочки есть 1, тогда элемент под номером i и обозначаемый Vi находится в V; если же там О, то Vt; например, если в U шесть элементов, то

1/-(0,0,1,0,1,1)

представляет множество V, состоящее из элементов Ьз, и v, и

0= (0,0,0,0,0,0)

представляет пустое множество (всегда обозначаемое 0), не содержащее ни одного элемента, в то время как t/= (1,1,1,1,1,1). Любая такая последовательность, представляющая множество V, известна как характеристический вектор V (по отношению к U).

Если и содержит п элементов, сколько имеется различных подмножеств и?

Заметим, что если \ U\ меньше, чем число битов в слове вашей ЭВМ, то можно представить любое Vsf/ одним словом памяти.

Как тогда мы проверяем справедливость принадлежности у g V? В представлении характеристическим вектором мы смотрим, какая целочисленная метка была поставлена в соответствие v. Предположим, что это i. Тогда мы проверяем t-й бит в последовательности, представляющей V. Если там стоит О, то v0, в противном случае v£V.

Операция объединения множеств легко реализуется с помощью характеристических векторов. Все, что надо сделать, чтобы получить А и В, это «сложить» характеристический вектор, представляющий А, с вектором, представляющим В. .Мы проделываем это «сложение» покомпонентно при условии, что «сумма» двух единиц есть единица. Такое модифицированное сложение называется операцией двоичного ИЛИ и обозначается символом V- Основные правила этой операции сведены в четыре формулы:

ivi=i

1V0=1

ovi=i

ovo=o

Для примера пусть \U\=7; рассмотрим два характеристических вектора

Л= (1,0,1,0,1,1,0) £=(1,1,0,0,1,0,0)

Тогда

А и В= (1,1,1,0,1,1,0)

На многих ЭВМ эта реализация операции объединения может быть выполнена одной операцией, если \U\ размера основного машинного слова. В противном случае нам может понадобиться \U\ операций.

Мы можем также определить операцию двоичного И /\ vl воспользоваться ею, чтобы сформулировать алгоритм для представления АГ\В характеристическим векторомиз представлений для А и В.

Аналогично операция .NOT. (не) может быть определена для представления дополнения множества.

Каковы другие операции на множествах, которые никогда не

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

По поводу операции исключения элемента v из множества V, обозначаемой V-{и}, можно сказать следующее: она требует одного шага, если использовать представление характеристическими векторами.

Далее, существует проблема отыскания элемента v. Какое из нашего текущего набора множеств содержит v (если какое-нибудь содержит)? Это пример задачи поиска. Более общие задачи поиска требуют отыскания всех элементов, обладающих некоторыми свойствами.

Часто бывает, что рассматриваемые элементы множеств все являются действительными или целыми числами и могут быть упорядочены естественным образом, т. е. с использованием отношения между действительными числами «равно» и «больше, чем». Другие множества элементов также могут быть упорядочены некоторым естественным или хорошо определенным способом. Можете ли вы придумать несколько примеров?