Генерация всех подмножеств универсума

 

Во многих переборных алгоритмах требуется последовательно рассмотреть все подмножества заданного множества. В большинстве компьютеров целые числа представляются кодами в двоичной системе счисления, причём число 2^k – 1 представляется кодом, содержащим k единиц. Таким образом, число 0 является представлением пустого множества Æ, число 1 является представлением подмножества, состоящего из первого элемента, и т.д. Следующий тривиальный алгоритм перечисляет все подмножества n-элементного множества.

Алгоритм генерации всех подмножеств n-элементного множества:

Вход: n ³ 0 – мощность множества;

Выход: последовательность кодов подмножеств i;

for i from 0 to 2ⁿ – 1;

yield i;

end for;

 

Алгоритм выдаёт 2ⁿ различных целых чисел, следовательно, 2ⁿ различных кодов. С увеличением числа увеличивается количество двоичных разрядов, необходимых для его представления. Самое большое (из генерируемых) число 2ⁿ – 1 требует своего представления ровно n разрядов. Таким образом, все подмножества генерируются, причём ровно по одному разу. Недостаток этого алгоритма состоит в том, что порядок генерации подмножеств никак не связан с их составом. Например, вслед за подмножеством с кодом 0111 будет перечислено подмножество с кодом 1000.

 

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

 

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

elem = record;

i: info; {информационное поле};

n: ­ n {указатель на следующий элемент};

end record;

 

При таком представлении трудоёмкость операции Î составит О(n), а трудоёмкость операций Ì, Ç, È составит О(n×m), где n и m – мощности участвующих в операции множеств.

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

Заключение

 

Курсовой проект выполнен на тему «Элементы теории множеств». В нём рассмотрены вопросы:

§ Множества: элементы и множества, способы задания множеств, количество элементов в множестве;

§ Операции над множествами: сравнение множеств, основные операции над множествами, свойства операций над множествами;

§ Аксиоматическая теория множеств: наивная теория множеств, аксиомы теории множеств;

§ Представление множеств в ЭВМ: Реализация операций над подмножествами заданного универсума U, Генерация всех подмножеств универсума, Представление множеств упорядоченными списками;

На основании найденной информации (учебная литература, Internet), я выделил основные пункты, которые наиболее полно и точно дают представление о теории множеств. При выполнении работы были приведены примеры множеств, а также и те примеры, которые приводят к противоречиям при различном способе их задания. При исследовании свойств операций над множествами я доказал одно из свойств (дистрибутивность) с помощью диаграмм Эйлера-Венна. И я считаю, что в последней главе необходимо было указать на связь между множествами и их представлением на ЭВМ, особенно это важно, на мой взгляд, для специальности математика-программиста.

После проделанной работы можно сделать следующий вывод:

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

Список использованной литературы

 

1. Дискретная математика для программистов / Ф.А.Новиков. – СПб.: Питер, 2002. – 304 с.

2. Жолков С.Ю. Математика и информатика для гуманитариев: Учебник. – М.: Гардарики, 2002. – 531 с.

3. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002. – 280 с. – (Серия «Высшее образование»)

4. Шипачёв В.С. Высшая математика. Учеб. Для вузов. – 4-е изд., стер. – М.: Высшая школа. 1998. – 479 с.

5. Материал из Википедии — свободной энциклопедии. Георг Кантор (http://www.peoples.ru/science/mathematics/kantor/)