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

êUú < n

U = {U₁, U₂, U₃,…}

Число элементов в универсуме не превосходит разрешающимися сети компьютера.

 

Подмножество А универсума U представляется двоичным кодом(машинным кодом, битовой шкалой)

C_i= 1, U_iÎA

0, U_iÏA

Пересечение А и В являются поразрядным логическим произведением кодом множеств А и В.

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

Код дополнения множества А является инверсией кода множества А.

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

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

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

В памяти ЭВМ целые числа представляются кодами в двоичной системе счисления, при чем 2^k – 1 задается последовательностью из 1111111…11(k-раз)

Двоичное представление целых чисел дает возможность сгенерировать все подмножества универсума.

Алгоритм генерации всех подмножеств данного множества.

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

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

for i from 0 to 2ⁿ – 1 do

yield i

end

Алгоритм выдает 2ⁿ различных целых чисел, т.е. 2ⁿ различных двоичных кодов.

С увеличением числа n, увеличивается количество двоичных разрядов необходимых для представления этого числа.

Недостаток этого алгоритма заключается в том, что порядок генерации подмножеств никак не связан с их составом.

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

Алгоритм построения бинарного кода Грея.

Алгоритм генерирует все подмножества n – элементного множества, при чем каждое следующее подмножество получается из предыдущего путем добавления или удаления одного элемента.

 

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

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

В:array [1..n] of 0..1

for i from 1 to n o

B[i]=0

end for

yield B

for i from 1 to 2ⁿ – 1 do

p=Q(i)

B[p]=1-B[p]

yield B

end for/

 

proc Q(i)

q:=1 i:=i

while j=четное do

j=j/2; q:=q+1

endwhile

return q

endproc.

 

Тестирование алгоритма

n=3

i	P	B

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

Представление множеств в виде битовых шкал не является эффективным с точки зрения экономии памяти.

Во избежание трудностей множество удобно представлять в виде списков элементов.

Поэтому для представления множеств можно использовать списки элементов.

Список элементов задается записью с 2 полями: одно из которых является информационным, а второе – поле указателей.

elem = record

i:=info

n:=­elem

info	­
Петров	¯
Иванов	¯
nil

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

Эффект реализации операций над множествами, представленными упорядоченными списками, основан на алгоритме слияния.

Алгоритм слияния просматривает параллельно 2 множества. На каждом шаге продвижение происходит на том множестве, в котором элемент оказываются меньшими.

Алгоритм проверки включения.

Вход: А и В – представлены упорядоченные списки

Выход: 1, если АÌВ, иначе 0.

 

while pa¹nil and pb¹nil do

if pa.i<pb.i then

return 0

else if pa.i>pb.i then

pb:=pb.n

else pa:=pa.n

pb:=pb.n

endif

endwhile

return pa=nil.

//pa.i=элемент списка

pa.n=ссылка