1)Понятие множества и его элементов. Способы задания множеств. Подмножества.

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

• Множества обычно обозначают прописными буквами (А, В, С и т.д.), а их элементы – строчными (например: x, y, z).

Если элемент x принадлежит множеству А, то пишут x  A. Запись x  A означает, что элемент x не принадлежит множеству А.

1. Рассмотрим несколько множеств:

1. А = {2, 4, 6}; 2) B = {1, 3, 5}; 3) C = {A, B}; 4) D = {x R | x>0}; 5) E = {2·y | y=1, 2, …, n}; {мн-во четных чисел} 6) F = {x | x=1 или x=2·y, yF } {степени двойки: 1, 2, 2², 2³, 2⁴, …}

В первом и втором пунктах примера множества заданы путем перечисления их элементов. В третьем пункте – тоже, но здесь элементами множества C являются множества. Заметим, что множество C имеет только два элемента и, в частности, 1 C, хотя 1 A  и A C . Действительно: 1A и 1B,  1 C, т.к. только A и B являются элементами C.

В 4-м примере множество D задано путем его описания, т.е. задания неких свойств его элементов.

Множества E, F строятся согласно указанному способу порождения множества, т.е. с помощью задания некой процедуры построения, причем множество F определяется через его же элементы. Правило задания F является рекурсивным.

Итак, множества могут быть заданы тремя основными способами:

1. Перечислением элементов множества (множества A, B, C) {1,2,3}.

Этот способ применим только для конечных множеств.

2. Указанием свойств элементов множества, или заданием т.н. характеристического предиката: D = {x | P(x)} (Другими словами – задание разрешающей процедуры).

Здесь P(x) обозначает некоторое условие, выраженное в форме логического утверждения; это условие может быть проверено для любого элемента.

3. Порождающей процедурой: E = {y | y:=f(x)}.

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

2. Операции над множествами (объединение, пересечение, дополнение, разность, симметрическая разность), их графическое представление

Объединением (или суммой) множеств А и В называется множество, состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множеств А или В: A  B = {x | x  A или x  B}.

Пересечением (или произведением) множеств А и В называется множество, состоящее из тех и только тех элементов, которые принадлежат каждому из множеств А и В: A  B = {x | x  A и x  B}.

Если A  B = , то множества А и В называются непересекающимися.

Разностью множеств А и В называется множество A \ B , состоящее из тех и только тех элементов, которые принадлежат А, но не принадлежат В: A \ B = {x | x  A и x  B}.

Симметрической разностью множеств А и В называется множество A Δ B = (A  B) \ (A  B) = {x | (x  A и x  B) или (x  B и x  A)}.

Дополнением множества А называется множество всех элементов универсального множества, не входящих в A: A = U \ A = {x |  x  A}.

3) Способы представления множеств в ЭВМ.

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

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

Для конечного универсума, мощность которого не превосходит разрядности машинного слова, подмножества универсума могут представляться битовой шкалой (аналог характеристической функции – 0 или 1 для каждого элемента). Битовая шкала имеет размерность универсума, и для каждого подмножества число единиц в соответствующей ему битовой шкале определяется мощностью этого подмножества. Если элемент входит в подмножество, то ему соответствует 1, иначе 0. Тогда операции над подмножествами осуществляются посредством поразрядных логических операций.

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

Если универсум велик, а подмножества имеют сравнительно небольшую мощность, то использование характеристических функций невыгодно, т.к. в них будет много нулей. Для представления таких множеств обычно используют списки элементов. Элемент множества тогда может быть представлен записью с двумя полями: информационным и указателем на следующий элемент. Трудоемкость операций включения, пересечения и объединения определяется как O(mn), где m и n – мощности множеств; операции  – как O(n).

4)Алгоритм типа слияния для различных операций над множествами.

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

1. Проверка включения AB

Вход: Два упорядоченных множества A и B (массивы).

Выход: да или нет (1 или 0, true или false).

i:=1; j:=1; // указатели на начало множеств

пока i|A|+1 и j|B|+1 цикл

если A[i] < B[j] то вернуть 0 и выход // элемент A отсутствует в B

иначе если A[i] > B[j] то j:=j+1 // переход к след. элементу B

иначе // элементы совпали – перейти к следующим

i:=i+1; j:=j+1;

конец если

конец цикла

если i=|A|+1 то вернуть 1 иначе вернуть 0.

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

Для определения объединения в результирующее множество заносятся каждый из меньших элементов и один, если они равны. Если конец одного из множеств достигнут раньше, все оставшиеся элементы другого дописываются в конец итогового множества.

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

5)Разбиения и покрытия.

Пусть Ě ={E_i} для i I – некоторое семейство непустых подмножеств множества M, E_i  M. Тогда семейство Ě называется покрытием множества M, если каждый элемент множества M принадлежит хотя бы одному из E_i: M    x M  i I |  x E_i.

Семейство Ě называется дизъюнктным, если элементы этого семейства попарно не пересекаются, т.е. каждый элемент множества M принадлежит не более чем одному из множеств E_i: i,j I, ij  E_i   E_j=. (илл. на д. Венна)

Дизъюнктное покрытие Ě называется разбиением множества M.

2. Пусть имеется множество M={1,2,3}. Тогда семейство {{1,2}, {2,3}, {3,1}} является покрытием, но не разбиением; семейство {{1},{2},{3}} – покрытием и разбиением, а семейство {{1},{2}} является дизъюнктным, но в то же время не является ни покрытием, ни разбиением.

Совокупность всех подмножеств множества M называется булеаном и обозначается P (M), или 2^M: 2^M = {A | A  M}.

3. Пусть имеется множество M = {1,2,3}. Тогда булеаном для него будет являться семейство {,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}