Последовательности (множества и мультимножества)

Множества и мультимножества

Не существует формального определения множества ; считается что это понятие первичное и не определяется. Так, можно говорить, что множество есть объединение различных элементов, но при этом мы оставляем неопределяемыми понятия "объединение" и "элементы". Дадим следующее определение множеству: множество - это неупорядоченная совокупность различных объектов или структура данных, используемая для представления множества. Мультимножество есть объединение не обязательно различных элементов; его можно считать множеством, в котором каждому элементу поставлено в соответствие положительное целое число, называемое кратностью.

Конечное множество $$S$$ будем записывать в следующем виде:$$S = \{ s_1,s_2,\ldots,s_n \},$$ где $$s_1,s_2,\ldots,s_n$$ - элементы $$S$$, обязательно различные! Мощность множества $$S$$ обозначается как $$\left| S\right|$$, для выписанного выше множества мощность записывается так $$\left| S \right| = n$$. Если $$S$$ - конечное мультимножество, то будем записывать его в следующем виде:$$S=\{\uns{s_1,s_1,\ldots,s_1}{m_1\text{раз}},\uns{s_2,s_2,\ldots,s_2}{m_2\text{ раз}}, \uns{s_3,s_3,\ldots,s_3}{m_3\text{ раз}}\} = \{ m_1 ullet s_1, m_2 ullet s_2,\ldots,m_n ullet s_n \}.$$ Здесь все $$s_i$$ различны и $$m_i$$ - кратность элемента $$s_i$$. В этом случае мощность $$S$$ равна$$\left| S \right| = \sum\limits_{i = 1}^n {m_i }.$$ Наиболее общими операциями на множествах и мультимножествах являются операции объединения и пересечения. Для множеств эти операции будем обозначать $$\cup$$ и $$\cap$$, а для мультимножеств - $$\mathop \cup \limits^ +$$ и $$\mathop \cap \limits^ +$$. Последовательное и связанное представление последовательностей можно использовать для множеств и мультимножеств очевидным способом. Индуцируя искусственный порядок элементов множества или используя собственный порядок, если он существует, можно рассматривать множество как последовательность. Аналогично, как последовательность можно рассматривать и мультимножество, или, для того чтобы сэкономить место, его можно рассматривать как последовательность пар, каждая из которых состоит из элемента и его кратности.

Как и для последовательностей, наилучший метод представления множеств или мультимножеств существенно зависит от операций, которые выполняются над ними. Предположим, например, что имеем дело с непересекающимися подмножествами множества $$S = \{ s_1,s_2,\ldots,s_n \}$$ и что над ними необходимо выполнить две следующие операции: объединение двух множеств и отыскание подмножества, содержащего данное $$s_i$$. Таким образом, в любой момент времени имеем разбиение $$S$$ на непустые непересекающиеся подмножества. Рассмотрим эти операции в конце данной лекции.

С целью идентификации считаем, что каждое из непересекающихся подмножеств множества $$S$$ имеет имя. Имя - это просто один из элементов подмножества, или, иначе, - представитель подмножества. Когда мы будем ссылаться на имя подмножества, то будем под этим подразумевать его представителя. Рассмотрим, например, множество$$S = \{ 1,2,3,4,5,6,7,8,9,10,11\},$$ разбитое на четыре непересекающихся подмножества$$\begin{gathered} \{ 1,6,\langle 7\rangle,8,11\} \{ \langle 2\rangle \} \{ \langle 3\rangle,4,5\} \{ 9,\langle 10\rangle \} \end{gathered}$$ В каждом из подмножеств, взятый в скобки элемент является его именем. Если нам нужно найти подмножество, в котором содержится восьмерка, искомым ответом будет 7, то есть имя подмножества, содержащего восьмерку. Если нужно взять объединение подмножеств с именами 2 и 10, получим разбиение множества $$S$$ следующего вида:$$\begin{gathered} \{ 1,6,\langle 7\rangle,8,11\} \{ \langle 3\rangle,4,5\} \{ \langle 2\rangle \} \cup \{ 9,\langle 10\rangle \} \end{gathered}$$

Именем множества $$\{ \langle 2\rangle \}$$ $$\cup$$ $$\{ 9,\langle 10\rangle \}$$ может быть или 2, или 10.Предполагаем, что вначале имеется разбиение множества $$S = \{s_1,s_2,\ldots,s_n \}$$ на $$n$$ подмножеств, каждое из которых состоит из одного элемента$$\{ \langle s_1 \rangle \} \{ \langle s_2 \rangle \},...,\{ \langle s_n \rangle \}$$ и имя каждого из них есть просто этот единственный элемент. Это разбиение преобразуется путем применения операций объединения вперемешку с операциями отыскания. Такая кажущаяся на первый взгляд надуманной задача чрезвычайно полезна в определенных комбинаторных алгоритмах; пример ее полезности виден в "жадном" алгоритме (лекция 16).

Для реализации операций и объединения, и отыскания опишем процедуры (операции) $$UNION(x,y)$$ и $$FIND(x)$$. Процедура (операция) $$UNION(x,y)$$ по именам двух различных подмножеств $$x$$ и $$y$$ образует новое подмножество, содержащее все элементы множеств $$x$$ и $$y$$. Процедура (операция) $$FIND(x)$$ выдает имя множества, содержащего $$x$$. Например, если нужно множество,содержащее $$a$$, объединить с множеством, содержащим $$b$$, необходимо выполнить следующую последовательность операторов:$$x \leftarrow FIND(a)\\ y \leftarrow FIND(b)\\ \text{\it if $x \ne y$ then $UNION(x,y)$}. \end{gathered}$$

Предположим, что мы имеем $$u$$ операций объединения, перемешанных с $$f$$ операциями отыскания, и что начинаем алгоритм с множества $$S=\{s_1 ,s_2,\ldots,s_n \}$$, которое разбито на подмножества, состоящие из одного элемента (см. 6.2.). Найдем такую структуру данных для представления непересекающихся подмножеств множества $$S$$, чтобы последовательность операций можно было производить эффектно. Такой структурой данных является представление в виде леса с указателями отца, как показано на рис. 4.5 лекции 4. Каждый элемент $$s_i$$ множества будет узлом леса, а отцом его будет элемент из того же подмножества, что и $$s_i$$. Если элемент не имеет отца, то есть является корнем, то он будет именем своего подмножества. В соответствии с этим разбиение 6.1 может быть представлено так:

При таком представлении процедура (операция) $$FIND(x)$$ состоит в переходах по указателям отцов от $$x$$ до корня, то есть имени, его подмножества. Процедура (операция) $$UNION(x,y)$$ состоит в связывании вместе некоторым образом деревьев, имеющих корни $$x$$ и $$y$$. Например, такую связь можно осуществить, сделав $$y$$ отцом $$x$$.

После $$u$$ операций объединения наибольшее из возможных подмножеств, получающихся в результате разбиения $$S$$, будет содержать $$u + 1$$ элементов. Поскольку каждое объединение уменьшает число подмножеств на единицу, последовательность операций может содержать не более $$n-1$$ объединений, откуда $$u \leqslant n - 1$$. Так как каждая операция объединения изменяет имя подмножества, содержащего некоторые элементы, можно считать, что каждому объединению предшествует по крайней мере одно отыскание, в связи с чем естественно предположить, что $$f \geqslant u$$. Выясним, насколько эффективно можно выполнить последовательность из $$u \leqslant n - 1$$ операций объединения, перемешанных с $$f \geqslant u$$ операциями отыскания. Время, требуемое на операции объединения, очевидно, пропорционально $$u$$, потому что необходимая для каждой операции объединения переделка некоторых указателей требует фиксированного количества работы. Поэтому сосредоточим свое внимание на времени, требуемом для $$f$$ операций отыскания.

Если операция $$UNION(x,y)$$ выполняется путем назначения $$x$$ отцом $$y$$, то после $$u$$ операций объединения может получиться лес, показанный ниже.

В этом случае, если $$f$$ операций отыскания выполняются после всех операций объединения и каждый поиск начинается внизу цепи из $$u + 1$$ элементов множества, то ясно, что время, требуемое на операции отыскания, будет пропорционально $$f \cdot (u + 1)$$. Очевидно, оно не может быть больше, чем константа, умноженная на $$f \cdot (u + 1)$$. Можно существенно уменьшить эту оценку.

Формула включений и исключений

Пусть имеется $$N$$ предметов, некоторые из которых обладают свойствами $$\alpha _1,\alpha _2,\ldots \alpha _n$$. При этом каждый предмет может либо не обладать ни одним из этих свойств, либо обладать одним или несколькими свойствами. Обозначим через $$N(\alpha _i \alpha _j \ldots \alpha _k )$$ количество предметов, обладающих свойствами $$\alpha _i,\alpha _j ,\ldots,\alpha _k$$ (и быть может, еще некоторыми из других свойств). Если нужно взять предметы, не обладающие некоторым свойством, то эти свойства пишем со штрихом. Например, через $$N(\alpha _1 \alpha _2 \alpha _4'$$ ) обозначено количество предметов, обладающих свойствами $$\alpha _1,\alpha _2$$, но не обладающих свойством $$\alpha _4$$ (вопрос об остальных свойствах останется открытым). Число предметов, не обладающих ни одним из указанных свойств, обозначается по этому правилу через $$N(\alpha _1' \alpha _2' \ldots \alpha _n')$$. Общий закон состоит в том, что$$\begin{gathered} N(\alpha _1' \alpha _2' \ldots \alpha _n' ) = N - N(\alpha _1 ) - N(\alpha _2 ) - \ldots - N(\alpha _n ) + N(\alpha _1 \alpha _2 ) + \\ + N(\alpha _1 \alpha _3 ) + \ldots + N(\alpha _1 \alpha _n ) +\ldots+ N(\alpha _{n - 1} \alpha _n ) - N(\alpha _1 \alpha _2 \alpha _3 ) - \ldots - \\ -N(\alpha _{n - 2} \alpha _{n - 1} \alpha _n + \ldots + ( - 1)^n N(\alpha _1 \alpha _2 \ldots \alpha _n ). \end{gathered}$$ Здесь алгебраическая сумма распространена на все комбинации свойств $$\alpha _1,\alpha _2,\ldots,\alpha _n$$ (без учета их порядка), причем знак + ставится, если число учитываемых свойств четно, и знак $$-$$, если это число нечетно. Например, $$N(\alpha _1 \alpha _3 \alpha _6 \alpha _8 )$$ входит со знаком +, а $$N(\alpha _3 \alpha _4 \alpha _{10} )$$ со знаком $$-$$. Формулу 6.3 называют формулой включений и исключений - сначала исключаются все предметы, обладающие хотя бы одним из свойств $$\alpha _1,\alpha _2,\ldots,\alpha _n$$, потом включаются предметы, обладающие, по крайней мере, двумя из этих свойств, затем исключаются имеющие, по крайней мере, три и т.д.

Решето Эратосфена

Одной из самых больших загадок математики является расположение простых чисел в ряду всех натуральных чисел. Иногда два простых числа идут через одно, (например, 17 и 19, 29 и 31), а иногда подряд идет миллион составных чисел. Сейчас ученые знают уже довольно много о том, сколько простых чисел содержится среди $$N$$ первых натуральных чисел. В этих подсчетах весьма полезным оказался метод, восходящий еще к древнегреческому ученому Эратосфену. Он жил в третьем веке до новой эры в Александрии.

Эратосфен занимался самыми различными вопросами - ему принадлежат интересные исследования в области математики, астрономии и других наук. Впрочем, такая разносторонность привела его к некоторой поверхностности. Современники несколько иронически называли Эратосфена "во всем второй": второй математик после Евклида, второй астроном после Гиппарха и т.д.

В математике Эратосфена интересовал как раз вопрос о том, как найти все простые числа среди натуральных чисел от 1 до $$N$$. (Эратосфен считал 1 простым числом. Сейчас математики считают 1 числом особого вида, которое не относится ни к простым, ни к составным числам.) Он придумал для этого следующий способ. Сначала вычеркивают все числа, делящиеся на 2 (исключая само число 2). Потом берут первое из оставшихся чисел (а именно 3). Ясно, что это число - простое. Вычеркивают все идущие после него числа, делящиеся на 3. Первым оставшимся числом будет 5. Вычеркивают все идущие после него числа, делящиеся на 5, и т.д. Числа, которые уцелеют после всех вычеркиваний, и являются простыми. Так как во времена Эратосфена писали на восковых табличках и не вычеркивали, а "выкалывали" цифры, то табличка после описанного процесса напоминала решето. Поэтому метод Эратосфена для нахождения простых чисел получил название "решето Эратосфена".

Подсчитаем, сколько останется чисел в первой сотне, если мы вычеркнем по методу Эратосфена числа, делящиеся на 2, 3 и 5. Иными словами, поставим такой вопрос: сколько чисел в первой сотне не делится ни на одно из чисел 2, 3, 5? Эта задача решается по формуле включения и исключения.

Обозначим через $$\alpha _1$$ свойство числа делиться на 2, через $$\alpha _2$$ - свойство делимости на 3 и через $$\alpha _3$$ - свойство делимости на 5. Тогда $$\alpha _1 \alpha _2$$ означает, что число делится на 6, $$\alpha _1 \alpha _3$$ означает, что оно делится на 10, и $$\alpha _2 \alpha _3$$ - оно делится на 15. Наконец, $$\alpha _1 \alpha _2 \alpha _3$$ означает, что число делится на 30. Надо найти, сколько чисел от 1 до 100 не делится ни на 2, ни на 3, ни на 5, то есть не обладает ни одним из свойств $$\alpha _1$$, $$\alpha _2$$, $$\alpha _3$$. По формуле 6.3 имеем$$N(\alpha _1' \alpha _2' \alpha _3')=100-N(\alpha _1 ) - N(\alpha _2 ) - N(\alpha _3 ) + N(\alpha _1 \alpha _2 ) +\\+ N(\alpha _1 \alpha _3 ) + N(\alpha _2 \alpha _3 ) - N(\alpha _1 \alpha _2 \alpha _3 ).$$ Но чтобы найти, сколько чисел от 1 до $$N$$ делится на $$n$$, надо разделить $$N$$ на $$n$$ и взять целую часть получившегося частного. Поэтому$$N(\alpha_1)=50,N(\alpha_2)=33,N(\alpha_3)=20,$$ $$N(\alpha_1\alpha_2)=16,N(\alpha_1\alpha_3)=10,N(\alpha_2\alpha_3)= 6,N(\alpha _1 \alpha \alpha _3 ) = 3,$$ и значит,$$N(\alpha _1' \alpha _2' \alpha _3' ) = 32.$$ Таким образом, 26 числа от 1 до 100 не делятся ни на 2, ни на 3, ни на 5. Эти числа и уцелеют после первых трех шагов процесса Эратосфена. Кроме них останутся сами числа 2, 3 и 5. Всего останется 35 чисел.

А из первой тысячи после первых трех шагов процесса Эратосфена останется 335 чисел. Это следует из того, что в этом случае$$N(\alpha _1 ) = 500,N(\alpha _2 ) = 333,N(\alpha _3 ) = 200,$$ $$N(\alpha _1 \alpha _2 ) = 166,N(\alpha _1 \alpha _3 ) = 100,N(\alpha _2 \alpha _3 ) =66,N(\alpha _1 \alpha _2 \alpha _3 ) = 33.$$

Примеры программы

Программа 1. Решето Эратосфена.

{В примере, иллюстрирующем работу с множествами,  реализуется алгоритм
выделения из первой сотни натуральных чисел всех простых чисел. В основе
алгоритма лежит прием "решета Эратосфена".
Алгоритм  написан на языке программирования  Turbo-Pascal.}

Uses crt;
Const
    N=100; {количество элементов исходного множества}
Type
    SetN=set of 1..N;
var
    n1, next, I : word; {вспомогательные переменные }
    BeginSet,              {исходное множество }
    PrimerSet: SetN;   {множество простых чисел }
Begin
    Clrscr;   {почистить экран}
    BeginSet:=[2..N]; {создать исходное множество}
    PrimerSet:=[1];     {первое простое число}
    next:=2;                {следующее простое число}
while BeginSet <> [ ] do  {начало основного цикла}
    begin
        n1:=next; {n1-число, кратное очередному простому (next)}
        while n1<=N do
        {цикл удаления из исходного множества непростых чисел}
        begin
            BeginSet:=BeginSet-[n1];
            n1:=n1+next {следующее кратное}
            end;               {конец цикла удаления}
repeat    {получить следующее простое число, которое есть первое
           не вычеркнутое из исходного множества}
inc(next)
until(next  in  BeginSet) or (next > N)
end;  {конец основного цикла}
{вывод результата}
textcolor(15);  {задание цвета}
for I:=1 to N do
    if i in PrimerSet then write(I:8);
    readln;
end.

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

{Находит и пишет все простые числа в порядке убывания от 2 до 200.
Алгоритм  написан на языке программирования   Turbo-Pascal.}

Uses crt;
const
n=197;
var

i,q,w,e,r,t:integer;
prost:array[1..n] of integer;

begin
clrscr;
e:=1;
r:=0;
for q:=1 to n do begin
r:=0;
for w:=2 to n-1 do
if (q<>w) and (q mod w =  0) then r:=1;
{prost[e]:=q; e:=e+1;}

if r=0 then begin{begin write(q,' ');}

prost[e]:=q;
e:=e+1;
end;
end;

for i:=e downto 2 do  begin
write (prost[i],' ');
if wherex>70 then writeln;

end;
readln;
end.

Программа 3. Поиск литер в строке.

{Поиск числа вхождений в данную сроку литер a, c, e, h.
Алгоритм  написан на языке программирования  Turbo-Pascal.}

Uses crt;
type
liter_set = set of char;

var
c:integer;
let: liter_set;
a:char;

begin
 clrscr;
 let:=['a','c','e','h'];

repeat
  a:=readkey;
  write(a);
  if a in let then c:=c+1;
 until a = '.';
 writeln;
 writeln('Общее число вхожений литер a,c,e,h в вашу запись:',c);
readln;

end.