Главная Промышленная автоматика.

*3.21. Пусть Г - дерево Хаффмана и пусть лист, помеченный символом а, имеет большую глубину, чем лист, помеченный символом Ь. Докажите, что вероятность символа Ь не меньше, чем вероятность символа а.

*3.22. Докажите, что в результате выполнения алгоритма Хаффмана для заданных вероятностей получается оптимальный код. Совет: используйте упражнение 3.21.

Библиографические замечания

в работах [11] и [47] рассматриваются математические свойства деревьев. В [65] и [81] приведена дополнительная информация о деревьях двоичного поиска. Многие работы, приведенные в главе 6 и относяшиеся к графам и их применению, содержат также материал о деревьях.

Алгоритм поиска оптимального кода, описанный в разделе 3.4, взят из работы [54]. В [83] дано современное исследование этого алгоритма.



ГЛАВА 4

Основные операторы множеств

Множество является той базовой структурой, которая лежит в основании всей математики. При разработке алгоритмов множества используются как основа многих важных абстрактных типов данных, и многие технические приемы и методы разработаны для реализации абстрактных типов данных, основанных именно на множествах. В этой главе мы рассмотрим основные операторы, выполняемые над множествами, и опишем некоторые простые реализации множеств. Мы представим "словарь" и "очередь с приоритетами" - два абстрактных типа данных, основанных на модели множеств. Реализации для этих АТД приведены в этой и следующей главах.

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

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

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

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

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

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

Классическое определение отношения линейного строгого порядка требует выполнения свойств антирефлексивности, антисимметричности и транзитивности. Здесь выполнение свойства антирефлексивности обеспечивает требование различности элементов любого множества, а сформулированное свойство 1 является парафразом "стандартного" определения свойства антисимметричности. - Прим. ред.



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

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

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

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

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

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

множества с повторениями иногда используется термин мультимножество. Мультимножеством будет набор элементов {1, 4, 1). Мультимножество также не является списком и даже в большей степени, чем простое множество, поскольку для мультимножества можно писать {4, 1, 1} и {1, 1, 4).





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 [30] 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0049