1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 33
Текст из файла (страница 33)
Наконец, полагаем счетчик числа узлов объединенного дерева равным сумме счетчиков для Т„и Т,. Случай 2. СЧЕТ(Т,)(СЧЕТ(Т„), Здесь вычисляется ГЛУБИНА(о), преобразуется узел о' в сына узла г' и ВЕС [г'1 — ВЕС [г']+ ГЛУБИНА(и) + 1; ВЕС [о'] -ВЕС [о') — ВЕС [г']; СЧЕТ(Т,) — СЧЕТ(Т,) + СЧЕТ(Т,). Итак, 0(п) операций СВЯЗАТЬ и НАЙТИ ГЛУБИНУ можно выполнить за время 0(пб(п)). Приложение 3. Эквивалентность конечных автоматов Детерминированным конечным автоматом называется машина, распознающая цепочки символов.
Она имеет входную ленту, раз- битую на клетки, головку на входной ленте (входную головку) и управляющее устройство с конечным числом состояний (рис. 4.24). Конечный автомат М можно представить в виде пятерки (5, 1, 6, в„г), где 1) 5 — множество состояний управляющего устройства, 2) 1 — входной алфавит (каждая клетка входной ленты содержит символ из 1), гл. с ствнктнгы данных для задач с множвствлми аиэатиая .мила эивяялягм /юаелээ Рнс. 4.24.
Конечный автомат. 3) 6 — отображение из Як( в 5 (если 6(з, а)=з', то всякий раз, когда М находится в состоянии з, а входная головка обозревает символ а, М сдвигает входную головку вправо и переходит в состояние э'), 4) э, — выделенное состояние в 5, называемое начальным, 5) Р— подмножество в о, называемое множеством допускаю- и4их (или заключительных) октояний.
Пусть 1а — множество цепочек (слов) конечной длины, состоящих из символов алфавита 1. В 1а включается и пустая цепочка з. Продолжим 6 до отображения из Ях1а в Я: 1) 6(з, е)=з, 2) 6(з, ха)=6(6(э, х), а) для всех хЕ1а и аЕ1. Входная цепочка х допускаетея автоматом М, если 6(э„х) Е Р. ,Чзыком 1, (М), допускаемым автоматом М, называется множество всех цепочек, допускаемых М. Более подробное введение в теорию конечных автоматов изложено в равд. 9.1.
Два состояния з, и з, считаются экзивалентныии, если для каждого х Е Ра состояние 6 (э„х) будет допускающим тогда и только тогда, когда 6(э„х) — допускающее состояние. Два конечных автомата М, и М, считаются эквивалентными, если 1, (М,)=1, (М,). Мы покажем здесь, что с помощью алгоритма ОБЪЕДИНИТЬ вЂ” НАЙТИ можно распознать эквивалентность двух конечных автоматов М,= (5„1, 6„з„Р,) и М,= (5„1, 6„ э„Р,) за 0(пб(п)) шагов, где п=Щ1+Щ(. Отношение эквивалентности двух состояний обладает важным свойством: если два состояния з и э' эквивалентны, то для всех входных символов а состояния 6 (э, а) и 6 (э', а) также эквивалентны. Кроме того, благодаря наличию пустой цепочки, никакое допускающее состояние не может оказаться эквивалентным недопускающему.
Таким образом, если допустить, что начальные состояния з, и э, автоматов М, и М, эквивалентны, то можно вывести другие пары эквивалентных состояний. Если в одну нз таких пар попадет допускающее состояние вместе с недопускающим, то з, н з, были неэквивалентными.
Если же это не произойдет, то верно обратное ка. ппиложкиия и овожцнния алгопитма овъндинить — плати Ьеп)п СПИСОК вЂ” (з„з,); НАБОР— 8; 1ог зб5т()5, до добавить (з) в НАБОР; сопппеп1 Мы только что образовали исходные множества для каждого состояния из 5,05,; тнЬ11е есть пара (з, а'), входящая в СПИСОК бо Ьей(п удалить (з, з') из множества СПИСОК; пусть А и А' обозначают НАЙТИ(з) и НАЙТИ(з') соответственно; И А ФА' 1Ьеп Ьея)п ОБЪЕДИНИТЬ (А, А', А); 1ог а Е! бо добавить (6(з, а), 6(з', а)) в СПИСОК епп епд епд Рис. 4.25. Алгоритм для нахождения множеств вквивалентиык состояний в пред. положении, что аг и аа эквивалентны.
Чтобы узнать, эквивалентны ли два конечных автомата М,= = (5ь 7, 6о зь гг) и М,=(5„1, б„з„ра), мы поступаем так: 1. С помощью программы иа рис. 4.26 находим все множества состояний, которые должны быть эквивалеитиыми, если эквивалеитиы з, и з,. СПИСОК содержит такие пары состояний (з, з'), что з и з' оказались эквивалентными, а следующие за ними состояиия (6(з, а), 6(з', а)) еще не рассматривались.
Вначале СПИСОК содержит только пару (зь з,). Чтобы найти множества эквивалентиых состояний, программа применяет алгоритм объединения иепересекающихся множеств. НАБОР представляет некоторое семейство множеств. Вначале каждое состояние из 5, В 5, образует одно- элементное множество. (Без потери общиости можно считать, что множества 5, и 5, ие пересекаются.) Затем всякий раз, когда з и з' оказываются эквивалентными, содержащие их множества А и А', входящие в НАБОР, сливаются, и новое множество получает имя А.
2. После выполнения этой программы множества, входящие в НАБОР, представляют разбиение множества 5,()5, иа блоки гл. з. ствгктувы двнных для злдлч с множествами состояний, которые должны быть эквивалентными. М, и М, эквивалентны тогда и только тогда, когда никакой блок ие содержит допускающего состояния вместе с недопускающим. Время работы этого алгоритма (как функция от числа состояний л=Щ~+115,11) определяется в основном работой алгоритма объединения множеств.
Операций ОБЪЕДИНИТЬ может быть не более и — 1, поскольку каждая такая операция уменьшает на единицу число множеств, входящих в НАБОР, а вначале было только п множеств. Число операций НАЙТИ пропорционально числу пар, помещенных в СПИСОК. Это число не больше и~~1~~, так как всякая пара, кроме начальной (зь з,), попадает в СПИСОК только после операции ОБЪЕДИНИТЬ. Таким образом, при постоянном размере входного алфавита на распознавание эквивалентности конечных автоматов М, и М, тратится время 0(п0(л)). 4.9.
СХЕМЫ СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ При решении ряда важных классов задач, аналогичных задаче ОБЪЕДИНИТЬ вЂ” НАЙТИ, мы, по-видимому, вынуждены вернуться к способам, при которых последовательность из и операций выполняется за время 0(л 1ойп) (в худшем случае). В один такой класс входят задачи, в которых последовательность из операций ПРИНАДЛЕЖАТЬ, ВСТАВИТЬ и УДАЛИТЬ выполняется в случае, когда допускается гораздо больше элем итон, чем используется на самом деле. В этом случае нельзя выбрать элемент, обращаясь прямо в массив указателей.
Надо применять расстановку или дерево двоичного поиска. Если а элементов уже вставлены, то в методе расстановки один выбор осуществляется за постоянное время в среднем и 0(п) в худшем случае. Дерево двоичного поиска дает среднее время 0 (1ой и) на один выбор, но в худшем случае может тоже дать плохое время выбора, если множество имен изменяется. Если же просто добавлять имена к дереву, не имея никакого механизма для поддержания его сбалансированности, то можно в результате придти к дереву с а узлами, глубина которого близка к и.
Поэтому в худшем случае производительность дерева двоичного поиска будет 0(а) шагов на операцию. Методом, изложенным в этом разделе, можно уменьшить сложность в худшем случае до 0(1ойп) шагов на операцию. Другой класс задач, требующих 0(п!ода) времени, образуют задачи выполнения последовательности из и операций, включакхцих ВСТАВИТЬ, УДАЛИТЬ и М1Н, в префиксном режиме. Еще один, третий, класс задач возникает, когда нужно представлять упорядоченные списки и уметь сцеплять и расцеплять их. В настоящем разделе мы познакомимся с техникой, позволяющей выполнять в префиксном режиме последовательности, содер- ° Фз Св.
СХЕМЫ СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ жащие важные подмножества семи основных операций иа множествах, введенных в равд. 4.1. Структурой данных, лежащей в основе метода, является сбалансированное дерево, под которым мы понимаем дерево с высотой, приблизительно равной логарифму числа его узлов. Вначале сбалансированное дерево строится легко. Трудно не дать ему в процессе выполнения последовательности операций ВСТАВИТЬ и УДАЛИТЬ превратиться в несбалансированное.
Например, если периодически не делать перебалансировку, то при выполнении последовательности операций УДАЛИТЬ, которые удаляют узлы только из левой части дерева, получается дерево, смещенное вправо. Известно много способов перебалансировки дерева в случае необходимости. Некоторые из них оставляют структуру дерева достаточно гибкой, так что число узлов в дереве высоты й может изменяться от 2" до 2"+' или 3". В них позволяется по меньшей мере удвоить число узлов в поддереве, прежде чем что-то менять выше его корня. й4ы обсудим два метода этого рода, называемые методами 2-3- деревьев и АВЛ-деревьев. Алгоритмы, работающие с 2-3-деревьями, понять легче, и сейчас мы обсудим их.
Алгоритмы с АВЛ- деревьями похожи на них, и потому вынесены в упражнения. Определение. 2-3-деревом называется дерево, в котором каждый узел, не являющийся листом, имеет двух или трех сыновей, а длины всех путей из корня в листья одинаковы. Заметим, что дерево, состоящее из единственного узла, является 2-3-деревом. На рис. 4.26 приведены два 2-3-дерева с шестью листьями.
В следукицей лемме показана связь числа узлов и числа листьев в 2-3-дереве с его высотой. Лемма 4.6. Пусть Т будет 2-3-деревом высоты й. Число узлов дерева Т заключено между 2"+' — 1 и (ЗА+4 — Ц!2, а число листьев— между 2" и 3". Д о к а з а те л ь а т в о, Элементарная индукция по й.
С! Ряс. 4.26. 2-3.деревья, гл 4. стгуитуьы длнных для задач с множествами Линейно упорядоченное множество 5 можно представить 2-3- деревом, приписав его элементы листьям дерева. Обозначим элемент, приписанный листу 1, через Е(1). Существуют два основных метода приписывания элементов листьям; какой из них применить, зависит от рассматриваемой задачи. Если допускается элементов гораздо больше, чем на самом деле используется, и дереву предстоит быть словарем, то, вероятно, лучше приписывать элементы в порядке возрастания слева направо. В каждом узле и, не являющемся листом, нам потребуется еще два данных: Е (в) и М (о).
Е )и) — это наибольший элемент множества 5 в поддереве, корнем которого служит самый левый сын узла гл М(п) — это наибольший элемент множества 5 в поддереве, корнем которого служит второй сын узла и (см. рис. 4.26). Значения Е и М, приписанные узлам, позволяют искать элемент, начиная с корня, способом, аналогичным двоичному поиску. Время обнаружения произвольного элемента пропорционально высоте дерева. Поэтому операцию ПРИНАДЛЕЖАТЬ можно выполнить на множестве из и элементов за время 0(1ояа), если представить его в виде 2-3-дерева такого рода. Во втором методе приписывания элементов листьям на порядок, в котором приписываются эти элементы, не налагается никаких ограничений. Метод особенно полезен для реализации операции ОБЪЕДИНИТЬ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
