yandex rtb 1
ГоловнаЗворотній зв'язок
yande share

Алгоритмы и структуры данных

4.1. Введения в множества

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

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

1.    Для любых элементов а и b из множества S может быть справедливым только одно из следующих утверждений: а < b, а = b или b < а.

2.   Для любых элементов а, b и с из множества S таких, что а < b и b < с, следует а < с (свойство транзитивности).

Множества целых и действительных чисел, символов и символьных строк обладают естественным линейным порядком, для проверки которого можно использовать оператор отношения < языка Pascal. Понятие линейного порядка можно определить для объектов, состоящих из множеств упорядоченных объектов. Формулировку такого определения мы оставляем читателю в качестве упражнения. (Прежде чем приступать к общей формулировке, рассмотрите пример двух множеств целых чисел, одно из которых состоит из чисел 1 и 4, а второе — из чисел 2 и 3, и сформулируйте условия, в соответствии с которыми первое множество будет больше или меньше второго.)

Система обозначений для множеств

Множество обычно изображается в виде последовательности его элементов, заключенной в фигурные скобки, например {1, 4} обозначает множество, состоящее из двух элементов, — чисел 1 и 4. Порядок, в котором записаны элементы множества, не существен, поэтому мы можем писать {4, 1} так же, как и {1, 4}, при записи одного и того же множества. Отметим (и будем это иметь в виду в дальнейшем), что множество не является списком (хотя бы по признаку произвольного порядка записи элементов), но для представления множеств мы будем использовать списки. Повторим также еще раз, что мы предполагаем отсутствие повторяющихся элементов в множестве, поэтому набор элементов {1,4,1} не будем воспринимать как множество.

 Иногда мы будем представлять множества с помощью шаблонов, т.е. выражений вида {х | :утверждение относительно х”, где "утверждение относительно х" является формальным утверждением, точно описывающим условия, при выполнении которых объект х может быть элементом множества. Например, шаблон | х — положительное целое число и х ≤1000} представляет множество {1, 2, ...,1000}, а запись | для произвольного целого у, х = у2} определяет множество точных квадратов целых чисел. Отметим, что множество точных квадратов бесконечно и его нельзя представить перечислением всех его элементов.

Фундаментальным понятием теории множеств является понятие отношения принадлежности к множеству, обозначаемое символом . Таким образом, запись х  А обозначает, что х принадлежит множеству А, т.е. является элементом этого множества; элемент х может быть атомом или другим множеством, но А не может быть атомом. Запись х  А означает, что не принадлежит множеству А", т.е. х не является элементом множества А. Существует специальное множество, обозначаемое символом 0, которое называется пустым множеством и которое не имеет элементов. Отметим, что 0 является именно множеством, а не атомом, хотя и не содержит никаких элементов. Утверждение х  Ø является ложным для любого элемента х, в то же время запись х  у (если х и у атомы) просто не имеет смысла: здесь синтаксическая ошибка, а не ложное утверждение.

Говорят, что множество А содержится в множестве В (или включается в множество В), пишется А С В или В  А, если любой элемент множества А является также элементом множества В. В случае A  В также говорят, что множество А является подмножеством множества В. Например, {1, 2}  {1, 2, 3}, но множество {1, 2, 3} не может быть подмножеством множества {1, 2}, поскольку множество {1, 2, 3} содержит элемент 3, которого не имеет множество {1, 2}. Каждое множество включается в самого себя, пустое множество содержится в любом множестве. Два множества равны, если каждое из них содержится в другом, т.е. они имеют одни и те же элементы. Если А ≠ В и А  В, то множество А называют собственным, истинным или строгим подмножеством множества В.

Основными операциями, выполняемыми над множествами, являются операции объединения, пересечения и разности. Объединением множеств А и В (обозначается А и В) называется множество, состоящее из элементов, принадлежащих хотя бы одному из множеств А и В. Пересечением множеств А и В (обозначается А  В) называется множество, состоящее только из тех элементов, которые принадлежат и множеству А, и множеству В. Разностью множеств А и В (обозначается А  В) называется множество, состоящее только из тех элементов множества А, которые не принадлежат множеству В. Например, если А = {а, b, с} и В = {b, d}, то А  В = {а, b, с, d}, A  В = {b} и А\ В = {а, с}.

 

Операторы АТД, основанные на множествах

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

1-3. Первые три процедуры UNION(A, В, С), INTERSECTION^, Б, С) и DIFFERENCE^, В, С) имеют "входными" аргументами множества А и В, а в качестве результата — "выходное" множество С, равное соответственно А  В, AВ и А\ В.

4.    Иногда мы будем использовать оператор, который называется слияние (merge), или объединение непересекающихся множеств. Этот оператор (обозначается MERGE) не отличается от оператора объединения двух множеств, но здесь предполагается, что множества-операнды не пересекаются (т.е. не имеют общих элементов). Процедура MERGE(A, В, С) присваивает множеству С значение А  В, но результат будет не определен, если А  В = 0, т.е. в случае, когда множества А к В имеют общие элементы.

5.    Функция MEMBER(x, А) имеет аргументами множество А и объект ж того зке типа, что и элементы множества А, и возвращает булево значение true (истина), если x  А, и значение false (ложь), если х  А.

6.    Процедура MAKENULL(A) присваивает множеству А значение пустого множества.

7.    Процедура INSERTCr, А), где объект х имеет тот же тип данных, что и элементы множества А, делает х элементом множества А. Другими словами, новым значением множества А будет А  {х}. Отметим, что в случае, когда элемент х уже присутствует в множестве А, это множество не изменяется в результате выполнения данной процедуры.

8.    Процедура DELETE(x, А) удаляет элемент х из множества А, т.е. заменяет множество А множеством А \ {х}. Если элемента х нет в множестве А, то это множество не изменяется. ;

9.    Процедура ASSIGN(A, В) присваивает множеству А в качестве значения множество В.

10. Функция MIN(A) возвращает наименьший элемент множества А. Для применения этой функции необходимо, чтобы множество А было параметризировано и его элементы были линейно упорядочены. Например, МШ({2, 3, 1}) = 1 и MIN({'а', 'Ь', 'с'}) = 'а'. Подобным образом определяется функция МАХ.

11. Функция EQUAL(A, В) возвращает значение true тогда и только тогда, когда множества А и В состоят из одних и тех же элементов.

12. Функция FIND(x) оперирует в среде, где есть набор непересекающихся множеств. Она возвращает имя (единственное) множества, в котором есть элемент х.

4.2. АТД с операторами множеств

Мы начнем с определения АТД для математической модели "множество" с определенными тремя основными теоретико-множественными операторами объединения, пересечения и разности. Сначала приведем пример такого АТД и покажем, как его можно использовать, а затем обсудим некоторые простые реализации этого АТД.

Пример 4.1. Напишем программу, выполняющую простой "анализ потока данных" по блок-схемам представленных процедур. Программа будет использовать переменные абстрактного типа данных SET (Множество), для этого АТД операторы UNION, INTERSECTION, DIFFERENCE, EQUAL, ASSIGN и MAKENULL определены в предыдущем разделе.

В блок-схеме на рис. 4.1 блоки-прямоугольники помечены B1, ..., В8, а операторы определения данных (операторы объявления данных и операторы присваивания) пронумерованы от 1 до 9. Эта блок-схема соответствует алгоритму Евклида (вычисление наибольшего общего делителя двух чисел), но в данном примере детали этого алгоритма нас не интересуют.

В общем случае анализ потока данных относится к той части компилятора, которая проверяет блоковую структуру исходной программы (подобную рис. 4.1) и собирает информацию о выполнении операторов каждого прямоугольника блок-схемы. Влеки (прямоугольники) блок-схемы представляют совокупность операторов, через которые последовательно "проходит" поток данных. Информация, полученная в результате анализа потока данных, помогает повысить качество генерируемого компилятором кода программы. Бели, например, в процессе анализа потока данных обнаружено, что при каждом прохождении блока В переменная х принимает значение 27, то можно подставить 27 для всех вхождений х в блоке В вместо выполнения оператора присваивания этой переменной. Если доступ к константам осуществляется быстрее, чем к значениям переменных, то описанная замена приводит к более эффективному коду программы, полученному в процессе компиляции.

В нашем примере мы хотим определить, где переменная последний раз принимала новое значение. Другими словами, мы хотим для каждого блока В, вычислить множество DEFIN[i] определений d таких, которые сделаны в блоках от В1, до Bi, но в последующих блоках нет других определений для той же переменной, которая определялась в определении d.

Чтобы проиллюстрировать необходимость такой информации, рассмотрим блок-схему на рис. 4.1. Первый блок В1 являясь "холостым" блоком, содержит три определения, присваивающих переменным t, p и q "неопределенные" значения. Если, например, множество DEFIN[7] включает в себя опр萵деление 3, которое присваивает переменной q "неопределенное" значение, значит, программа содержит ошибку, поскольку будет предпринята печать этой переменной без присваивания ей "настоящего" значения. К счастью, в данной блок-схеме нетрудно проверить, что невозможно достигнуть блока В7, минуя операторы присвоения значений этой переменной, поэтому множество DEFIN[7] не будет содержать определение 3.

При вычислении множества DEFIN[i] будем придерживаться нескольких правил. Сначала для каждого блока Вi предварительно вычислим два множества GEN[i] и KILL[i]. GEN[i] — это множество определений, сделанных в блоке Вi. Если в этом блоке есть несколько определений одной переменной, то только последнее из них заносится в множество GEN[i]. Другими словами, GEN[i] является множеством определений, "генерируемых" блоком Вi.

Множество KILL[i] содержит определения (из всех блоков, кроме Д) тех же переменных, которые определены в блоке Д. Например, на рис. 4.1 GEN[4] = {6}, поскольку в блоке В4 содержится определение 6 (переменной t). В свою очередь KILL[4] = {1, 9}, так как существуют определения 1 и 9 той же переменной t и которые не входят в блок В4.

Кроме множеств DEFIN[i], для каждого блока В, также будем вычислять множества DEFOUT[i]. Так же, как DEFIN[i] является множеством определений, действие которых достигает блока Вi, так и DEFOUT[i] — это множество определений, действие которых распространяется за блок Вi. Существует простая формула, связывающая множества DEFIN[i] и DEFOUT[i]:

DEFOUT[i] = (DEFIN[i]-KILL[i])GEN[i] (4.1)

Таким образом, определение d распространяет свое действие за блок Вi только в двух случаях: если его действие начато до блока Вi и не "убито" в этом блоке или если оно генерировано в блоке Вi. Вторая формула, связывающая множества DEFIN[i] и DEFOUT[i], показывает, что DEFIN[i] можно вычислить как объединение тех множеств DEFOUT[p], для которых определяющие их блоки Вp, предшествуют блоку Вi.

(4.2)

Из формулы (4.2) следует очевидный вывод, что определения данных регистрируются в блоке Д тогда и только тогда, когда их действие начинается в одном из предшествующих блоков. В особых случаях, когда Д не имеет предшественников (как блок B1 на рис. 4.1), множество DEFIN[i] считается равным пустому множеству. Хотя в этом примере введено много новых понятий, мы не будем обобщать этот материал для написания общих алгоритмов вычисления областей действия определений в произвольных блок-схемах. Вместо этого мы напишем часть программы вычисления множеств DEFIN[i] и DEFOUT[i] (i = 1, .... 8) для блок-схемы рис. 4.1, предполагая, что множества GEN[i] и KILL[i] определены заранее. Отметим, что предлагаемый фрагмент программы предполагает существование АТД SET (Множество) с операторами UNION, INTERSECTION, DIFFERENCE, EQUAL, ASSIGN и MAKENULL, позднее мы покажем, как реализовать этот АТД.

В создаваемом программном фрагменте (листинг 4.1) процедура propagate(GEN, KILL, DEFIN, DEFOUT) использует формулу (4.1) для вычисления множества DEFOUT указанного блока. Если программа свободна от циклов и повторяющихся структур, то в этом случае множества DEFOUT можно вычислить непосредственно. При наличии в программе циклов или повторяющихся структур для вычисления DEFOUT применяются итерационные процедуры. Сначала для всех і положим DEFIN[i] = 0 и DEFOUT[i] = GEN[i], затем последовательно применим формулы (4.1) и (4.2) несколько раз, пока не "стабилизируются" (не перестанут изменяться) множества DEFIN и DEFOUT. Поскольку каждое новое значение множеств DEFIN[i] и DEFOUT[i] содержит свои предыдущие значения, а количество всех определений в программе ограничено, то процесс должен сходиться к решению уравнений (4.1) и (4.2).

Последовательные значения множеств DEFIN[i] после каждой итерации цикла показаны в табл. 4.1. Заметим, что операторы 1, 2 и 3 присваивания переменным "неопределенных" значений не распространяются на блоки, где эти переменные используются. Отметим также, что в листинге 4.2 сначала выполняются вычисления по формуле (4.2), а затем по формуле (4.1); в общем случае это обеспечивает сходимость процесса вычисления DEFIN[i] всего за несколько итераций.

 

23