Структуры данных и модели вычислений

Амортизационный анализ работы двоичного счетчика

Рассмотрим работу -разрядного двоичного сбрасываемого счетчика, реализованного как массив битов , хранящий двоичную запись числа . Будем считать, что — младший разряд. Пусть первоначально . Единственной операцией в нашем примере будет операция Increment, увеличивающая на 1 по модулю .
Увеличение счетчика на единицу происходит следующим образом: все начальные единичные биты в массиве , если они есть, становятся нулями, а следующий непосредственно за ними нулевой бит, если он есть, устанавливается в единицу. Стоимость операции Increment линейно зависит от общего количества битов, подвергшихся изменению. Каждое такое изменение будем считать элементарной операцией.
Анализ работы двоичного счетчика методом группировки. Применим метод группировки для анализа сложности -кратного выполнения операции Increment. Поскольку в худшем случае, когда массив состоит из одних единиц, меняются все
битов, то -кратное выполнение операции Increment может быть оценено как элементарных операций. Но эта оценка слишком груба.
Чтобы получить более точную оценку, учтем, что не каждый раз значения всех битов меняются. В самом деле, младший бит меняется при каждом исполнении операции Increment. Следующий по старшинству бит меняется только через раз. При счете от нуля до этот бит меняется раз. Бит меняется только каждый четвертый раз, и так далее. Заметим, что если , то в процессе счета от до
разряд меняется раз, а если , то он вообще не меняется. Следовательно, общее количество операций зануления и записи 1 равно Тем самым, увеличение двоичного счетчика от до
требует не более операций, причем константа не зависит от и равна . Учетную стоимость операции Increment можно считать равной .
Анализ работы двоичного счетчика методом предоплаты. Применим метод предоплаты для анализа сложности -кратного выполнения операции Increment. Будем считать, что реальная стоимость изменения бита составляет рубль. Установим такие учетные стоимости: рубля за запись единицы, за очистку. При каждой установке бита в единицу одним из двух рублей учетной стоимости будем расплачиваться за реальные затраты на эту установку, а второй рубль, остающийся в резерве, будем "прикреплять" к рассматриваемому биту.
Поскольку первоначально все биты были нулевыми, в каждый момент к каждому ненулевому биту будет прикреплен резервный рубль. Стало быть, за очистку любого бита дополнительно платить нам не придется: мы расплатимся за нее рублем, прикрепленным к этому биту в момент его установки.

Теперь легко определить учетную стоимость операции Increment. Поскольку каждая такая операция требует не более одной установки бита, ее учетную стоимость можно считать равной рублям. Следовательно, фактическая стоимость последовательных операций Increment, начинающихся с нуля, есть , поскольку она не превосходит суммы учетных стоимостей .

Анализ работы двоичного счетчика методом потенциалов. Проанализируем теперь трудоемкость -кратного выполнения операции Increment с помощью метода потенциалов.

Пусть — содержимое счетчика в начальный момент, — содержимое счетчика после выполнения -й операции, — число единиц в записи , — число единиц, превращенных в нули при -й операции. Очевидно, что

Пусть далее — реальная стоимость -й операции Increment, — ее учетная стоимость. Очевидно, что . Тогда

Если счет начинается с нуля, то

и

для всех . Поскольку сумма учетных стоимостей оценивает сверху сумму реальных стоимостей, имеем

то есть получаем, что суммарная стоимость операций есть с константой (двойкой), не зависящей от .

Метод потенциалов позволяет разобраться и со случаем, когда счет начинается не с нуля. В этом случае имеем

откуда при достаточно больших значениях () получаем, что реальная стоимость оценивается как , причем константа в -записи не зависит ни от , ни от начального значения счетчика.

Амортизационный анализ

Наряду с получением верхних и нижних оценок и оценок в среднем, часто используются так называемые амортизационные оценки.
Амортизационный анализ применяется при оценке времени выполнения корректной последовательности, состоящей из однотипных или разнотипных операций с некоторой структурой данных. Если верхнюю оценку времени выполнения одной операции умножить на , получим верхнюю оценку выполнения всех операций. Часто такая оценка бывает сильно завышенной. Иногда длительное время выполнения очередной операции влечет за собой малое время выполнения следующих операций. Более того, такая ситуация может создаваться искусственно, то есть при выполнении очередной операции мы можем готовить почву для более эффективного выполнения следующей. Поэтому возникает задача изучения асимптотического поведения гарантированной оценки для среднего времени выполнения одной операции.
При амортизационном анализе определяется некоторая так называемая учетная (амортизационная) стоимость одной операции, которая может быть как больше, так и меньше реальной стоимости конкретной операции. Но при этом для любой корректной последовательности операций фактическая суммарная длительность всех операций не должна превосходить суммы их учетных стоимостей. Зная учетную стоимость одной операции, верхнюю оценку времени выполнения последовательности из операций можно получить, умножив ее на .
Ниже рассмотрим три часто используемых метода амортизационного анализа: метод группировки, метод предоплаты и метод потенциалов.
Метод группировки. Предположим, что мы оценили сверху время выполнения последовательности из операций, установив, что она не превосходит , тогда величину
объявим учетной стоимостью любой операции из рассматриваемой последовательности, независимо от ее длительности.
Метод предоплаты. В этом методе операции разных типов получают разные учетные стоимости, причем эти стоимости могут быть как больше, так и меньше фактических. Если учетная стоимость превосходит фактическую, то разность между ними рассматривается как резерв на оплату в будущем тех операций, у которых учетная стоимость ниже реальной.
Учетные стоимости должны выбираться так, чтобы в любой момент времени фактическая стоимость не превосходила суммы учетных стоимостей, то есть чтобы резерв оставался неотрицательным.

Метод потенциалов. Этот метод является обобщением метода предоплаты. Здесь резерв определяется функцией состояния структуры данных в целом. Эта функция называется потенциалом.

Общая схема метода такова. Пусть над структурой данных предстоит произвести операций, и пусть — состояние структуры данных после -й операции ( — исходное состояние). Потенциал представляет собой функцию

из множества возможных состояний структуры данных в множество действительных чисел.

Пусть — реальная стоимость -й операции. Учетной стоимостью -й операции объявим число , определяемое формулой как сумма реальной стоимости операции плюс приращение потенциала в результате выполнения этой операции. Тогда суммарная учетная стоимость всех операций равна

Если нам удалось придумать функцию , для которой то суммарная учетная стоимость даст верхнюю оценку для реальной стоимости последовательности из операций. Не ограничивая общности, можно считать, что

Говоря неформально, если разность потенциалов

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

Учетные стоимости и оценки реальной стоимости, рассчитанные с помощью метода потенциалов, зависят от выбора потенциальной функции, а сам этот выбор является делом творческим.

Ниже эти три метода будут проиллюстрированы на примере анализа работы двоичного счетчика с единственной операцией Increment (прибавление единицы).

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

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

Структуры данных и модели вычислений

Деревья и графы

Деревья находят широкое применение при проектировании алгоритмов и, в частности, структур данных. Отсылая читателя к литературе по теории графов, мы будем пользоваться такими понятиями, как узел, ребро, лист, потомок, сын, левый потомок, правый потомок, предок, отец, корень, ветвь и другие. Регулярным деревом назовем дерево, в котором фиксировано максимально возможное (как правило, небольшое) число потомков для каждого из его узлов. В частности, если число потомков для каждого узла не больше двух, то дерево называется бинарным, если не более трех — тернарным. Если это число может равняться только двум или трем, то дерево называется (—)-деревом.
Достаточно универсальным является способ представления регулярных деревьев, при котором каждый узел представляется записью, содержащей, кроме прикладной информации, позиции смежных с ним элементов, например позиции потомков или наряду с потомками позицию предка или еще каких-либо узлов, в зависимости от потребностей. Регулярность дерева позволяет фиксировать число полей, достаточное для представления любого узла.
Так, узлы бинарного корневого дерева можно представлять записями вида где представляет связанную с узлом прикладную информацию, — позицию его левого потомка, а — позицию правого потомка. Само дерево в таком случае можно представить позицией его корня. Если в алгоритме необходимо продвижение от узла к предку, то узлы бинарного корневого дерева можно представлять записями вида
где — позиция предка рассматриваемого узла.
Для представления нерегулярных деревьев (то есть деревьев, узлы которых могут иметь произвольное число потомков) применяют следующий способ: потомки каждого узла нумеруются и каждый узел представляется записью, включающей в себя позицию его первого (левого) потомка и позицию его "правого брата".
Для регулярных деревьев более экономным по памяти может оказаться представление с помощью массива. Рассмотрим этот прием на примере бинарного дерева. Значения индексов массива отождествляются с узлами дерева, пронумерованными так, что корень получает номер 1, а потомки узла c номером получают номера и .
При таком представлении предок узла с номером будет иметь номер

(частное от деления на 2). Аналогично можно представить тернарное и другие регулярные деревья.

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

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

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

Еще один способ, часто имеющий преимущества перед названными выше, — это представление графа массивом или списком списков (рис. 2.7).

Рис. 2.7.  Представление графа комбинацией списков: множество вершин представлено списком узлов, к каждому из которых справа подцеплен список смежных с ним вершин

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

вершины, смежные с -й, при этом

— первая позиция за пределами массива . В таком случае, если нам требуется с каждой вершиной из окрестности вершины выполнить оператор , то можно сделать это с помощью оператора цикла:

Заметим, что если граф не ориентирован, то каждое ребро (, ) будет представлено дважды: один раз в последовательности вершин, смежных с вершиной , а второй раз — в последовательности вершин, смежных с вершиной . Но эта избыточность часто бывает полезна с точки зрения времени выполнения операций над окрестностями вершин графа. Как недостаток такого представления графа, можно отметить неудобство при динамической модификации графа, например, добавление к графу ребра может потребовать большого количества пересылок в массиве . Этого недостатка лишен способ представления графа, показанный на рис. 2.7.

Моделирование списков с последовательным доступом при помощи массивов

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

Таблица 2.1. Моделирование одностороннего списка при помощи массива

Адрес	1	2	3	4	5	6	7	8	9	10	11	12
Inf	e		b			c			d		a
Next	0		6			9			1		3

Доступ к списку можно осуществить через его первый элемент, позиция которого в массиве задается значением переменной . Значение говорит о том, что в позиции
расположен элемент, у которого нет преемника, то есть последний элемент кортежа.
На табл. 2.2 показано возможное заполнение массивов , и для представления кортежа () двусторонним списком.

Таблица 2.2. Моделирование двустороннего списка при помощи массивов

Адрес	1	2	3	4	5	6	7	8	9	10	11	12
Inf	e		b			c			d		a
Next	0		6			9			1		3
Precede	9		11			3			6		0

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

Некоторые дополнительные операции со связными списками

Конкатенация. Эта операция предназначена для соединения двух списков в один результирующий. Она эффективна в тех случаях, когда обеспечен доступ к последнему элементу списка с трудоемкостью . При соединении двух списков и первый элемент списка становится преемником последнего элемента списка . При этом возникают вопросы — должен ли получившийся список иметь какое-то новое имя и должны ли сохраниться как таковые исходные списки
и ?
В рассмотренной ниже процедуре Concat, реализующей операцию "Соединить два списка", принято следующее решение. К списку
присоединяется список , список сохраняется, а результирующим является список . Следует, однако, понимать, что если в список
будут внесены изменения, они автоматически произойдут в новом списке. Трудоемкость этой операции — .
Из списка удалить элементы, удовлетворяющие некоторому условию. Предположим, что требуемое условие на элемент
проверяется предикатом condition().
Построить список,состоящий из элементов данного списка , удовлетворяющих некоторому условию. Предположим, что требуемое условие на элементпроверяется предикатом condition().
Получить списокреверсированием списка

Общие сведения о списках

Остановимся на наиболее часто используемых структурах данных, называемых списками. Списки лежат в основе многих более сложных структур данных. В простейшем случае списки используются для представления кортежей.
Кортеж — это конечная последовательность, возможно с повторениями, элементов некоторого множества . Элементами кортежа могут быть числа, символы некоторого алфавита, точки плоскости и т.д. В более сложных случаях элементами кортежа, в свою очередь, могут быть также кортежи. Элементы, не являющиеся кортежами, называются атомами. Количество элементов в кортеже называется его длиной. Удобно рассматривать кортежи, не содержащие ни одного элемента. Такие кортежи называются пустыми. Длина пустого кортежа считается равной .
Элемент кортежа характеризуется своим номером в последовательности (кортежным номером) и содержанием, то есть элементом множества . Если длина кортежа равна , , то кортеж
удобно рассматривать как отображение множества в множество . Таким образом, — это -й элемент кортежа .
Термин "список" используется как обобщающее название различных структур данных, используемых для представления кортежей в памяти компьютера. При представлении кортежа в памяти появляется еще одна характеристика элемента кортежа — его позиция в памяти. В некоторых случаях номер элемента в кортеже и его позиция в памяти связаны друг с другом арифметическими соотношениями таким образом, что по номеру легко вычисляется позиция и, наоборот, по позиции вычисляется номер. В других случаях связь между номерами и позициями задается "таблично" или осуществляется с помощью алгоритмических процедур. Множество позиций обозначим через . Иногда удобно считать, что в множестве имеется специальный элемент , указывающий на несуществующую область памяти. Таким образом, при рассмотрении того или иного списка мы имеем дело с тремя множествами , , и с отображениями на этих множествах.
Типичными при работе со списками являются следующие операции:

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

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

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

Удаление элемента, находящегося в заданной позиции.

Вставка в кортеж нового элемента перед элементом, расположенным в заданной позиции.

Определение длины кортежа.

При описании этих и других операций со списками будем использовать следующие отображения и константы, заданные на множествах , , :

: , где (pos) — элемент списка, находящийся в позиции pos памяти.

, где (pos) — позиция элемента, следующего за элементом из позиции pos.

: , где (pos) — позиция элемента, находящегося перед элементом из позиции pos.

: , где (pos) — кортежный номер элемента, находящегося в позиции pos.

: , где () — позиция элемента, имеющего кортежный номер .

— длина списка.

— позиция первого элемента списка.

— позиция последнего элемента списка.

Иногда для распознавания концевых элементов списка пользуются следующим соглашением: eсли pos является позицией последнего элемента списка, то полагают , а если началом, то . В случаях, когда позицией элемента, следующего за последним или предшествующего первому, является несуществующая позиция , будем считать, что принадлежит множеству . При изменении содержимого списка все введенные множества, отображения и константы могут изменяться.

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

Список, в который предполагается добавлять и удалять элементы лишь с одного его конца, называется стеком.


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

Списки, для которых не планируется выполнять операции вставки

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

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


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

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

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

Поля, относящиеся к конкретному списку , будем записывать в форме

В полях дескриптора будем указывать также имена процедур и функций, которые реализуют примитивные операции над списками при рассматриваемой их реализации.

Так, например, дескриптор списка может иметь форму

При таком дескрипторе

означает позицию первого элемента списка ,

— его длину.

Списки с последовательным доступом

Последовательный доступ к элементам списка, как правило, реализуется с использованием динамического выделения памяти во время исполнения программы. Поиск свободных участков памяти обычно возлагается на систему программирования. Мы будем называть такие списки связными. Преимущества связных списков перед списками с прямым доступом проявляются в тех случаях, когда часто используются вставки в списки и удаление элементов из списков. Еще одно преимущество динамического выделения памяти может проявиться, когда в алгоритме одновременно используется большое количество списков, каждый из которых в процессе работы может потребовать большой объем памяти, однако в совокупности эта память может быть ограничена приемлемой величиной.
Элементы связного списка, следующие друг за другом, не обязательно размещаются в последовательных ячейках памяти — доступ к следующему и предыдущему элементам осуществляется при помощи специальных ссылок (указателей). Чтобы обеспечить запоминание указателей на следующий и предыдущий элементы, каждый элемент списка "погружается" в узел, для которого в памяти компьютера формируется запись, состоящая из нескольких полей. В простейшем случае эта запись может состоять из двух полей. Одно из них — — предназначено для запоминания самого элемента, а другое — — для запоминания позиции следующего. Для обозначения такого узла будем использовать следующую форму: где — позиция (адрес) узла в памяти. Поскольку у последнего элемента нет следующего, его поле заполняют значением . Иногда вместо используют ссылку на сам этот элемент, что также может являться признаком конца списка. Мы часто будем пользоваться именно этим способом распознавания конца списка. Представление списка с помощью таких узлов обеспечивает сканирование списка от начала к его концу. Доступ к самому списку осуществляется через его голову с помощью переменной , содержащей позицию первого элемента. Такие списки называются односторонними.
При описании операций со списками через будем обозначать узел, расположенный в позиции .
Для доступа к полям узла

используем форму ,

и т.д. Оператор для создания нового узла будем записывать в виде

Для обеспечения сканирования как от начала к концу, так и от конца к началу используют узлы следующего вида:

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

На рис. 2.1—2.6 представлено несколько разновидностей списков. Узлы списков изображены прямоугольниками, разделенными на части по числу полей. Стрелки проведены в соответствии со значениями полей и .

Рис. 2.1.  Односторонний список: вход через первый элемент, сканирование от начала к концу, признак конца — Next(pos) = nil

Рис. 2.2.  Односторонний список: вход через первый элемент; сканирование от начала к концу, признак конца — Next(pos) = pos

Рис. 2.3.  Односторонний циклический список: вход через первый элемент; сканирование от начала к концу, признак конца — Next(pos) = first

Рис. 2.4.  Односторонний циклический список: вход через последний элемент с помощью ссылки Last^.next; сканирование от начала к концу, признак конца — pos = last

Рис. 2.5.  Двусторонний список: вход через первый элемент, сканирование от начала к концу и от конца к началу; признак начала — Procede(pos) = nil; признак конца — Next(pos) = nil

Рис. 2.6.  Двусторонний циклический список: вход через первый элемент; сканирование от начала к концу и от конца к началу, признак конца — Next(pos) = first


При ее использовании могут возникнуть проблемы, связанные с некорректным обращением, так как в процедуре не производится проверка, является ли позиция pos позицией какого-либо элемента списка . Ответственность за некорректное обращение несет вызывающая программа. Проверка этого условия с помощью сканирования списка могла бы оказаться слишком дорогой и свела бы на нет преимущества использования связных списков. Еще одна проблема, связанная с выполнением этой операции, заключается в том, что узел

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

Вставить в список элемент после элемента, находящегося в позиции

Следующие две операции рассмотрим на примере одностороннего циклического списка (см. рис. 2.4).

Добавить элемент к концу списка

Добавить элемент к началу списка

Следующие три процедуры рассмотрим на примере двустороннего циклического списка (см. рис. 2.6).

Удалить последний элемент списка

Удалить первый элемент списка

Удалить из списка элемент, находящийся в позиции

Списки с прямым доступом

Прямой доступ, как правило, реализуется при представлении списка массивом. Элементы кортежа размещаются в идущих подряд ячейках некоторого массива. Для локализации списка в массиве введем целочисленную переменную для хранения номера позиции массива, в которой расположен его первый элемент, и целочисленную переменную , означающую длину списка. Равенство служит признаком того, что массив содержит пустой список. Иногда для переменных, хранящих позицию элемента массива, удобно иметь какое-либо условное значение, выходящее за рамки индексации массива. Будем обозначать его .
Рассмотрим подробнее реализацию списка с прямым доступом, дающую возможность добавлять элементы к списку с любого его конца. Воспользуемся циклической "нумерацией" элементов массива, при которой следующим за последним элементом массива считается его первый элемент, а предыдущим для первого — последний (речь идет об элементах массива, а не об элементах списка). Если элементы массива пронумеровать числами от
до , то переход к следующему (предыдущему) элементу списка осуществляется с помощью прибавления (вычитания) единицы по модулю , где — длина массива. Дескриптор такого списка будет иметь форму
Добавление элемента к началу списка осуществляется его записью в позицию
с последующим присваиванием , а добавление в конец (записью элемента в позицию (
с последующим выполнением оператора . Заметим, что при таком способе начальный фрагмент кортежа может оказаться в конце массива, а конечный фрагмент — в начале. Заметим также, что добавление нового элемента возможно только при условии . Кроме того, нужно иметь в виду, что в системах программирования со статическим распределением памяти под массивы, которое происходит во время компиляции, длину массива следует выбирать достаточной для размещения списков, порождаемых разрабатываемым алгоритмом. Следует помнить, что максимальная длина списка зависит не только от алгоритма, но и от входных данных.
Основные отображения для списка с прямым доступом, имеющего дескриптор , определяются следующим образом:
Приведем несколько процедур для работы со списками с прямым доступом.
Создать пустой список

Добавить элемент к концу списка

Добавить элемент e к началу списка

Заменить элемент с кортежным номером
на элемент
Удалить последний элемент списка
Удалить первый элемент списка

Структуры данных и модели вычислений

Анализ трудоемкости

Для анализа трудоемкости выполнения операций нам потребуются две функции. Одна из них,, является суперэкспонентой и определяется следующим образом:
Вторая — суперлогарифм , по основанию 2, определяемая соотношением
Суперлогарифм является в некотором смысле обратной функцией к суперэкспоненте, . Значения функций и при нескольких значениях аргументов приведены в следующих таблицах:

…

Ребропри текущем состоянии коллекции назовем корневым, если— корень и (петля); назовем его прикорневым, если — корень и, в противном случае — внутренним.
Отметим следующие свойства коллекции на множестве из элементов. Прикорневое ребро может превратиться во внутреннее, а корневое — в прикорневое только при выполнении операции ОБЪЕДИНИТЬ.
Внутреннее ребропри первом же выполнении операции НАЙТИ, "проходящей через него", исчезает, но вместо него появляется прикорневое ребро, при этом, следовательно, внутреннее ребро "участвует в поиске" не более одного раза.
Если при выполнении очередной операции ОБЪЕДИНИТЬузел становится родителем узла , то после ее выполнения справедливо неравенство.
При выполнении операции НАЙТИ ранги узлов не изменяются, но узлы могут менять своих родителей, то есть меняется структура леса.
Если перед выполнением операции НАЙТИ узел был родителем узла , а после выполнения этой операции родителем узла стал узел , то выполняется неравенство. Следовательно, даже после изменения леса в результате выполнения операции НАЙТИ ранги вдоль любого пути от листа к корню будут строго возрастать.
При выполнении операции ОБЪЕДИНИТЬ ранг любого некорневого элемента не изменяется, а ранг корня либо сохраняется, либо увеличивается на 1.

Остается оценить суммарную трудоемкость операций НАЙТИ.

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

Поскольку ранг узла может увеличиваться лишь при выполнении операции ОБЪЕДИНИТЬ, причем не более чем на 1, после таких операций ранг никакого узла не может стать больше , следовательно, максимальный индекс , при котором может быть непустым, равен .

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

Еслии в данный момент не является корнем, то расходы относим на статью транзитных расходов. Еслии не является корнем, то на статьюместных расходов в-м диапазоне, если же— корень, то на статью корневых расходов.

Сумму местных расходов во всех диапазонах обозначим через

Имеем, так как при каждом выполнении операции НАЙТИ проходится одно корневое и, возможно, одно прикорневое ребро.

Для транзитных переходов имеем, так как при каждом выполнении операции НАЙТИ происходит не болеепереходов из одного диапазона в другой.

Для оценки величины введем потенциалузла после выполнения операции . Если к узлу еще не применялась операция СОЗДАТЬ, то.

Потенциалом группыпри текущем состоянии коллекции назовем величину

Очевидно, что в любой момент времени справедливо неравенство

(1)

Покажем, что для любого узлапри любом выполняется неравенство . Действительно, если — операция СОЗДАТЬ (), то то есть потенциал узла , так же, как, очевидно, и всех остальных, не изменяется.

Операции над разделенными множествами

Разделенные множества — это абстрактный тип данных, предназначенный для представления коллекции, состоящей из некоторого числа попарно непересекающихся подмножеств
заданного множества . Для простоты в качестве
будем рассматривать множество .
Этот тип данных применяется в таких задачах, как поиск минимального остовного дерева для заданного взвешенного неориентированного графа, построение компонент связности графа, минимизация конечного автомата, и многих других, требующих динамического поддержания некоторого отношения эквивалентности. Примеры таких задач будут рассмотрены ниже.
Как правило, в таких задачах вычисления начинаются с пустой коллекции подмножеств (). Затем по мере вычислений формируются новые подмножества, включаемые в коллекцию. Формирование новых подмножеств происходит либо путем создания одноэлементного подмножества, либо путем объединения уже существующих в коллекции подмножеств. Для осуществления таких действий используются имена включенных в коллекцию подмножеств. В качестве имени подмножества будем использовать один из его элементов (главный элемент), выбираемый по определенному правилу. Поскольку в коллекции всегда будут находиться попарно непересекающиеся подмножества множества , такое имя будет однозначно определять требуемое подмножество.
СОЗДАТЬ(). Эта операция предназначена для введения в коллекцию нового подмножества, состоящего из одного элемента , при этом предполагается, что не входит ни в одно из подмножеств коллекции, созданной к моменту выполнения этой операции. Элемент указывается в качестве параметра. Именем созданного подмножества будет считаться сам элемент .
ОБЪЕДИНИТЬ(). С помощью этой операции можно объединить два подмножества коллекции, имеющие, соответственно, имена и , в одно новое подмножество, при этом оба объединяемые подмножества удаляются из коллекции, а вновь построенное подмножество получает некоторое имя. Во всех рассматриваемых нами случаях именем нового полученного в результате этой операции подмножества будет одно из имен или .
Имена объединяемых подмножеств указываются в качестве параметров.

НАЙТИ(). Эта операция позволяет определить имя

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

Последовательность , составленную из операций типа СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ, назовем корректной, если перед выполнением каждой операции из последовательности соблюдены условия ее применения. Например, перед выполнением очередной операции вида ОБЪЕДИНИТЬ (, ) подмножества с именами и должны быть уже созданы. Перед выполнением операции СОЗДАТЬ() элемент не должен принадлежать ни одному из подмножеств коллекции. Операция НАЙТИ (, ) применима при любом значении аргумента . Следует только помнить, что если не принадлежит ни одному из подмножеств коллекции, то получим .

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

с помощью массива;

с помощью древовидной структуры;

с помощью древовидной структуры с использованием рангов вершин;

с помощью древовидной структуры с использованием рангов вершин и сжатия путей.

Последний из перечисленных способов является наиболее эффективным по времени выполнения произвольных корректных последовательностей операций типа СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ. Строго говоря, во всех перечисленных случаях будут использоваться массивы, но интерпретации их содержимого будут различными. Каждый раз при описании очередной реализации мы будем обсуждать оценки трудоемкости рассматриваемых операций.

Представление разделенных множеств древовидной структурой

Пусть, по-прежнему, — множество, из элементов которого будет строиться коллекция. Каждое подмножество коллекции представляется корневым деревом, узлы которого являются элементами этого подмножества, то есть отождествляются с номерами из множества . Корень дерева используется в качестве имени соответствующего подмножества (канонический элемент). Для каждого узла дерева определяется узел , являющийся его родителем в дереве; если — корень, то полагаем .
Фактически в памяти компьютера это дерево будем представлять массивом так, что будет предком узла , если не является корнем, и , если — корень. Если же не входит ни в одно из подмножеств коллекции, то .
Рассмотрим пример. Пусть и коллекция состоит из двух подмножеств и . Деревья, представляющие эти подмножества, могут быть такими, как на рис.3.1. Кружочки обозначают узлы дерева; указатели на родителей представлены при помощи стрелок. Именем одного из этих подмножеств является 3, другого — 6:

Рис. 3.1. 

Представление разделенных множеств с помощью массива

Пусть — множество, из элементов которого будет строиться коллекция разделенных подмножеств. Одним из очевидных способов представления коллекции является представление ее с помощью массива. При таком способе для каждого элемента
в соответствующей (-й) ячейке массива помещаем имя (канонический элемент) того подмножества, которому принадлежит элемент . Если элемент
не принадлежит ни одному из подмножеств коллекции, то в -ю ячейку записываем 0.

Представление разделенных множеств с использованием рангов вершин

Предыдущую реализацию разделенных множеств можно усовершенствовать следующим образом. Операцию ОБЪЕДИНИТЬ можно выполнить так, чтобы высота дерева, соответствующего объединению двух множеств, была как можно меньше. А именно, корень большего по высоте дерева сделать родителем корня другого дерева. Назовем такую реализацию операции ОБЪЕДИНИТЬ объединением по рангу. В качестве ранга в данном случае берется высота соответствующего дерева.

Примеры использования разделенных множеств

Пример 1.
Рассмотрим задачу выделения компонент связности неориентированного графа. Напомним, что компонентой связности называется максимальное по включению подмножество вершин графа такое, что любые две его вершины связаны цепью. Полагаем, что вершины графа пронумерованы числами и каждое ребро представлено парой () номеров вершин. Предполагаем также, что множество ребер не пусто.
Алгоритм выделения компонент связности неориентированного графа
Очевидно, построенные подмножества коллекции будут представлять искомые компоненты связности. Используя названия основных операций над коллекцией разделенных множеств, представленный выше алгоритм можно записать в следующем виде:
Пример 2.
Рассмотрим неориентированный связный граф без петель, ребрам которого приписаны в качестве весов положительные вещественные числа. Требуется построить остовное дерево, накрывающее все вершины графа и имеющее минимальный суммарный вес входящих в него ребер. Итак, пусть заданный граф имеет множество вершин, пронумерованных числами , и множество ребер. Каждому ребру из множества
поставлена в соответствие пара его концевых вершин и число — его вес. Для решения этой задачи были предложены различные алгоритмы. Мы рассмотрим алгоритм, который разработал Крускал.
Алгоритм Крускала
Заметим, что в процессе работы алгоритма в множестве будут находиться ребра, составляющие ациклический подграф исходного графа, являющийся лесом, состоящим из некоторого числа деревьев. Отсутствие циклов гарантируется проверкой "Если " в пункте 6 описанного алгоритма. Фактически при происходит объединение двух поддеревьев в одно дерево с помощью ребра , найденного на шаге 3.
Если исходный граф связен, как сказано в постановке задачи, то построенное с помощью такого алгоритма множество будет, очевидно, представлять дерево, накрывающее все вершины исходного графа. Доказательство того, что суммарный вес входящих в него ребер будет минимальным, можно найти в разделе "Графы".
В алгоритме естественным образом используется структура разделенных множеств. Обратим внимание на операцию поиска в множестве
ребра
с минимальным весом. Эффективность этой операции во многом зависит от выбора структуры данных для хранения множества . Приемы эффективного выполнения этой операции рассмотрены в разделе "Приоритетные очереди".

Реализация операций с использованием рангов вершин

Для такой реализации разделенных множеств необходимо хранить с каждым узлом дополнительно еще одну величину — высоту поддерева, корнем которого является узел . Будем называть ее высотой, или рангом, узла . Остальные операции нужно настроить на корректную работу с этим полем. Будем хранить высоту каждого узла в ячейке массива .
Операция СОЗДАТЬ () назначает в качестве родителя узлатот же самый, а высотой узласчитает 0. Таким образом, время выполнения данной операции есть. В результате выполнения операции СОЗДАТЬ () образуется новое дерево, изображенное на рис. 3.6. Число, расположенное рядом с узлом, обозначает его высоту. Описанные действия реализуются с помощью операторов

Рис. 3.6. 
Операция ОБЪЕДИНИТЬ
() назначает корень большего по высоте дерева родителем корня другого дерева. Если деревья имеют одинаковую высоту, то узел назначается родителем узла , после чего значение высоты узла увеличивается на единицу. Заметим, что и должны быть до выполнения операции корнями соответствующих деревьев. Именем вновь образованного подмножества будет имя того из объединяемых подмножеств, у которого корень имел большую высоту, а имя другого из объединяемых подмножеств перестанет быть именем какого-либо из подмножеств. Очевидно, время выполнения этой операции есть константа. Выполнить описанные действия можно с помощью следующей процедуры:
На рис. 3.7 и рис. 3.8 показано применение операции ОБЪЕДИНИТЬк коллекции, изображенной на рис. 3.3, с учетом высот объединяемых поддеревьев. Рядом с кружочками, изображающими узлы, показаны их высоты. Так как, то родителем узла 6 становится узел 3.
Операция НАЙТИ () осуществляется, как и в предыдущей реализации, продвижением по указателям на родителей от узла до корня дерева. В качестве берется найденный корень.

Рис. 3.7. 

Рис. 3.8. 
Очевидно, что время выполнения данной операции, как и ранее, пропорционально длине пути из узлав корень соответствующего дерева. Однако длина такого пути в данном случае может быть оценена иначе. Для оценки длины этого пути докажем следующие леммы:

Лемма 1.

В результате выполнения любой последовательности операций из набораСОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИнад пустой коллекцией разделенных множеств для любого узла выполняется неравенство, где — количество узлов в поддереве с корнем — высота узла .

Доказательство

Очевидно, перед первым применением операции ОБЪЕДИНИТЬ для любого узлаимели ,и, следовательно,. Операции СОЗДАТЬ и НАЙТИ не могут нарушить доказываемого неравенства, поэтому доказательство можно провести индукцией по количеству применений операции ОБЪЕДИНИТЬ.

Предположим, что перед очередным применением операции ОБЪЕДИНИТЬ () доказываемое неравенство все еще остается верным, тогда если высота узла меньше высоты узла , то дерево, полученное с помощью ОБЪЕДИНИТЬ (), имеет корень , а высоты узлов и не изменились. Количество узлов в дереве с корнем не изменилось, а количество узлов в дереве с корнем увеличилось. Таким образом, как для узлов,, так и для всех остальных неравенство сохраняется. Случай, когда высота узла больше высоты узла , аналогичен рассмотренному.

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

Лемма 2.

Если за время работы, начавшейся с пустой коллекции, операция СОЗДАТЬ применяласьраз, то для любогочисло узлов высоты удовлетворяет неравенству.

Доказательство

Пусть— все узлы высоты , тогда по лемме 1 присправедливы неравенства. Таким образом, откуда и следует требуемое неравенство.

Следствие 3.

В результате выполнения любой последовательности операций из набораСОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИнад пустой коллекцией разделенных множеств для любого узлаимеет место неравенство.

Доказательство

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

Следствие 4.

Время выполнения операции НАЙТИ есть.

Следствие 5.

При реализации разделенных множеств с использованием рангов время выполнения операций ОБЪЕДИНИТЬ иили НАЙТИ есть величина.

Замечание

При реализации операции объединения подмножеств в качестве ранга узла можно использовать количество узлов в поддереве с корнем в данном узле. Утверждение леммы 1 будет справедливым и в этом случае, следовательно, сохранятся и оценки времени выполнения операций.

Реализация операций с помощью древовидной структуры

Операция СОЗДАТЬ
() назначает в качестве родителя узла сам узел с помощью присваивания . Таким образом, время выполнения операции есть . В результате выполнения операции СОЗДАТЬ() образуется новое одновершинное дерево с петлей в корне, изображенное на рис. 3.2.

Рис. 3.2. 
Если к коллекции подмножеств, изображенных на рис. 3.1, применить операцию СОЗДАТЬ (5), то получим коллекцию, изображенную на рис. 3.3.

Рис. 3.3. 
Операция ОБЪЕДИНИТЬ
() назначает узел
родителем узла с помощью присваивания . Заметим, что и должны быть до выполнения рассматриваемой операции корнями соответствующих деревьев. Именем вновь образованного подмножества будет , а перестанет быть именем какого-либо множества. Время выполнения этой операции есть .

Рис. 3.4. 
Если применить операцию ОБЪЕДИНИТЬ к коллекции, представленной на рис. 3.3, то получим коллекцию, состоящую из двух подмножеств и , — изображенную на рис. 3.4. Именем первого из этих подмножеств будет 6, второго — 5.
Операция НАЙТИ() осуществляется продвижением по указателям на родителей от узла до корня дерева. В качестве берется этот корень. Описанные действия можно реализовать с помощью операторов
Очевидно, что время выполнения данной операции есть , где — длина пути из узла в корень соответствующего дерева. Но заметим, что при выполнении операций СОЗДАТЬ и ОБЪЕДИНИТЬ возможно образование дерева в виде линейной цепочки из узлов, изображенной на рис. 3.5.

Рис. 3.5. 
К такой цепочке может привести, например, следующая последовательность операций
СОЗДАТЬ ();
СОЗДАТЬ ();
… … …
СОЗДАТЬ ();
ОБЪЕДИНИТЬ ();
ОБЪЕДИНИТЬ ();
… … …
ОБЪЕДИНИТЬ ();
Как видим,может достигать величины, поэтому трудоемкость операции НАЙТИ является величиной.
Худший случай применения операции НАЙТИ в данной ситуации — это НАЙТИ (). В этом случае необходимо сделатьпереход по ссылкам на родителей, чтобы дойти от узла к корню дерева , и один переход, чтобы узнать, что родитель узла есть сам узел .
Если операция СОЗДАТЬ выполняетсяраз, то время выполнения последовательности, составленной изопераций ОБЪЕДИНИТЬ иили НАЙТИ, при рассматриваемой реализации разделенных множеств есть величина . Действительно, время выполнения операций ОБЪЕДИНИТЬ, очевидно, есть , так как время выполнения одной такой операции есть константа. Время выполнения операций НАЙТИ есть, так как время выполнения одной такой операции есть. Итак, время выполнения произвольных операций есть .

Реализация операций с помощью массива

Обозначим через массив длины , с помощью которого будем представлять коллекцию. Пустая коллекция представляется массивом, заполненным нулями.
Операция СОЗДАТЬ() осуществляется записью элемента
в ячейку с номером . Время выполнения операции — .
Операция ОБЪЕДИНИТЬ() осуществляется следующим образом. Просматриваются элементы массива , и в те ячейки, в которых было записано имя , заносится новое имя — . Следовательно, именем вновь образованного подмножества будет , а перестанет быть именем какого-либо подмножества. Очевидно, время выполнения этой операции — .
Операция НАЙТИ () выдает в качестве
содержимое элемента с номером в массиве . Время выполнения операции — .
При такой реализации разделенных множеств, очевидно, что время выполнения произвольных операций, среди которых операций ОБЪЕДИНИТЬ, есть величина .

Сводные данные о сложности операций с разделенными множествами

Реализация с помощью массива

СОЗДАТЬ
ОБЪЕДИНИТЬ
НАЙТИ
операций

Реализация с помощью древовидной cтруктуры

СОЗДАТЬ
ОБЪЕДИНИТЬ
НАЙТИ
операций

Реализация с использованием рангов вершин

СОЗДАТЬ
ОБЪЕДИНИТЬ
НАЙТИ
операций

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

СОЗДАТЬ
ОБЪЕДИНИТЬ
НАЙТИ
операций

Структуры данных и модели вычислений

Алгоритм Дейкстры

Заполнить массив нулями.

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

Организовать приоритетную очередь из вершин графа, взяв в качестве ключей величины , .

Заменить ключ вершины на 0.

Пока очередь не пуста, выполнять операции .

Выбрать (с удалением) из приоритетной очереди элемент с минимальным ключом.

Для каждой вершины , смежной с , выполнить операции .

Вычислить величину .

Если , то уменьшить ключ элемента
на величину и заменить старое значение величины на .

Упражнение
Напишите на каком-либо алгоритмическом языке реализацию алгоритма Дейкстры с использованием -кучи и испытайте ее на тестовых примерах при различных значениях .

Бесхитростная сортировка в памяти с прямым доступом.

Бесхитростный алгоритм сортировки может заключаться в выполнении следующих операторов:
Здесь — процедура, транспонирующая элементы . Заметим, что число сравнений при реализации такого алгоритма равно . В частности, это означает, что время работы алгоритма равно .

Нахождение кратчайших путей в графе

Входные данные:

Граф со взвешенными ребрами (под весами можно понимать длины ребер, если речь идет о геометрическом графе, или любые другие числовые характеристики ребер). Пусть — вес ребра ().

Стартовая вершина (вершина, от которой вычисляются расстояния до всех остальных вершин).

Выходные данные:

Массив , — кратчайшее расстояние от вершины до вершины ).

Массив , — предпоследняя вершина в кратчайшем пути из вершины
в вершину ).

Приводимый ниже алгоритм Дейкстры корректно решает задачу для графов с неотрицательными весами вершин. Если же в графе есть ребра с отрицательными весами, но нет циклов с отрицательным суммарным весом, то для решения задачи можно использовать алгоритм Форда, Беллмана.

Операции с d-кучей

При реализации основных операций над кучами используются две вспомогательные операции — ВСПЛЫТИЕ и ПОГРУЖЕНИЕ. При реализации этих операций введем еще одну вспомогательную операцию — транспонирование, с помощью которой будем менять местами элементы, расположенные в двух разных узлах дерева. Ее реализация может быть представлена следующим образом:
Замечание.
Если в кучу помещаются только ключи элементов, то процедура транспонирования модифицируется соответствующим образом.
Операция ВСПЛЫТИЕ.Эта операция применяется в тех случаях, когда в некотором узле, например в -м, расположен элемент , нарушающий кучеобразный порядок так, что его ключ меньше ключа его родителя .
Элементы и меняются местами. Если после этого элемент
снова не удовлетворяет условиям кучи, то еще раз проводится аналогичная перестановка. И так до тех пор, пока не встанет на свое место.
Рассмотрим 3-дерево на рис. 4.3. В этом дереве кучеобразный порядок нарушает узел с ключом , так как его родительскому узлу приписан элемент с ключом .

Рис. 4.3. 
Применим к узлу операцию ВСПЛЫТИЕ. Элементы с ключами и меняются местами. В результате получается дерево, представленное на рис. 4.4.

Рис. 4.4. 
Теперь нарушен кучеобразный порядок в узле (), меняем местами элементы c ключами и . В результате получаем кучу, изображенную на рис. 4.5. Кучеобразный порядок восстановлен, операция ВСПЛЫТИЕ завершена.

Рис. 4.5. 
Вычислительная сложность этой операции пропорциональна числу сравнений элементов и их обменов. Это число, очевидно, не более чем удвоенное число узлов в пути от узла до корня дерева. Длина такого пути в -куче с узлами не превосходит ее высоты, а именно , в соответствии с доказанным выше утверждением 1. Значит, время выполнения данной операции — .
Реализация операции ВСПЛЫТИЕ. Входным параметром этой операции является номер узла, в котором нарушен порядок:
Замечание.

Операцию ВСПЛЫТИЕ можно применять не только к -куче, но и к другим видам куч.

Для более эффективного выполнения операции ВСПЛЫТИЕ можно поступить следующим образом: запомнить элемент, находящийся в узле , переместить элемент из его родительского узла

в узел , затем из узла в узел

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

Операция ПОГРУЖЕНИЕ. Эта операция также применяется для восстановления свойства кучеобразности. Пусть, например, в -м узле расположен элемент , нарушающий кучеобразный порядок таким образом, что ключ элемента больше ключа элемента , приписанного потомку узла . В этом случае среди непосредственных потомков узла выбирается элемент с наименьшим ключом, и элементы и меняются местами. Если после этого элемент снова не удовлетворяет условиям кучи, то еще раз проводим аналогичную перестановку. И так до тех пор, пока не встанет на свое место.

Рассмотрим -дерево, представленное на рис. 4.6. В узле расположен элемент с ключом , и этот узел имеет двух потомков с меньшими ключами, а именно и . Применим к элементу

операцию ПОГРУЖЕНИЕ.

Рис. 4.6. 


Если у узла нет потомков, то .

Реализация операции ПОГРУЖЕНИЕ

Операция ВСТАВКА. Если перед выполнением этой операции куча содержала узлов (напомним, что они пронумерованы числами от

до ), то добавляем к дереву -й узел (его номер будет ) и приписываем ему элемент с именем и ключом . Вставка нового элемента производится посредством отведения для него места в -ых позициях массивов и соответственно, после чего к добавленному узлу применяется операция ВСПЛЫТИЕ для восстановления кучеобразного порядка.

Вставим в -кучу, изображенную на рис. 4.9, новый элемент с ключом .

Рис. 4.9. 

Сначала добавляем к дереву новый узел с номером и приписываем ему элемент с ключом . Получим дерево, представленное на рис. 4.10.

Рис. 4.10. 

Затем применяем к узлу операцию ВСПЛЫТИЕ. При описании этой операции использовался именно приведенный пример (см. рис. 4.3, 4.4, 4.5).

Вычислительная сложность данной операции равна константе плюс вычислительная сложность операции ВСПЛЫТИЕ, то есть .

Реализация операции ВСТАВКА

Операция УДАЛЕНИЕ.

Используется для удаления элемента, приписанного узлу с заданным номером . Сначала элемент, приписанный последнему узлу дерева, переносится на место удаляемого элемента, последний узел при этом становится ненужным и поэтому удаляется из дерева. Далее, если узел , в который помещен новый элемент, имеет родителя с большим ключом, то к узлу применяется операция ВСПЛЫТИЕ, в противном случае — ПОГРУЖЕНИЕ.

Таким образом, ориентируясь на худший случай, вычислительную сложность операции УДАЛЕНИЕ оцениваем величиной .

Реализация операции УДАЛЕНИЕ

Операция УДАЛЕНИЕ_МИНИМУМА. Эта операция предназначена для взятия из кучи элемента с минимальным ключом (он находится в корне дерева) и удаления его из кучи с помощью операции УДАЛЕНИЕ.

Реализация операции УДАЛЕНИЕ_МИНИМУМА

Функция MINKEY. Эта функция предназначена для определения минимального ключа без удаления соответствующего элемента.

Реализация функции MINKEY

Трудоемкость операции, очевидно, равна .

Операция УМЕНЬШЕНИЕ_КЛЮЧА. Предназначена для уменьшения ключа у элемента, приписанного узлу с заданным номером , на заданную величину .


Это действие может нарушить кучеобразный порядок лишь таким образом, что уменьшенный ключ элемента в узле станет меньше ключа элемента в родительском узле. Для восстановления порядка в куче используется операция ВСПЛЫТИЕ.

Вычислительная сложность данной операции определяется временем, затрачиваемым на уменьшение ключа (то есть константой), и временем выполнения операции ВСПЛЫТИЕ (то есть . В итоге вычислительная сложность операции УМЕНЬШИТЬ_КЛЮЧ равна .

Реализация операции УМЕНЬШЕНИЕ_КЛЮЧА

Операция ОКУЧИВАНИЕ.

Заметим, что если -куча создается путем -кратного применения операции ВСТАВКА, то суммарная трудоемкость ее создания будет равна . Если же все элементов сначала занимают в произвольном порядке массив и, соответственно, массив , то можно превратить их в -кучу, применяя операцию ПОГРУЖЕНИЕ по очереди к узлам .

Такой процесс будем называть окучиванием массива. Для доказательства того, что в результате действительно устанавливается кучеобразный порядок, достаточно заметить, что если поддеревья с корнями в узлах упорядочены по правилу кучи, то после применения процедуры ПОГРУЖЕНИЕ к узлу поддерево с корнем в этом узле также станет упорядоченным по правилу кучи. Итак, остановимся на следующей реализации.

Реализация операции ОКУЧИВАНИЕ

Утверждение 3.

Вычислительная сложность операции ОКУЧИВАНИЕ равна .

Доказательство

Заметим, что трудоемкость погружения с высоты

равна , а количество узлов высоты

не превосходит . Осталось оценить сумму где , и убедиться, что полученная сумма есть .

Для суммирования можно воспользоваться формулой

Предоставляем читателю возможность завершить доказательство.

Операция СОЗДАТЬ_СПИСОК_МИНИМАЛЬНЫХ.

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


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

Реализация операции СОЗДАТЬ_СПИСОК_МИНИМАЛЬНЫХ

Сводные данные о трудоемкости операций с d-кучами

ВСПЛЫТИЕ
ПОГРУЖЕНИЕ
ВСТАВКА
УДАЛЕНИЕ
УДАЛЕНИЕ_МИН
MINKEY
УМЕНЬШЕНИЕ_КЛЮЧА
ОБРАЗОВАTЬ_ОЧЕРЕДЬ
СПИСОК_МИН

Замечание.

Для -куч "неудобной" является операция слияния куч.

Основные определения

Приоритетная очередь — это абстрактный тип данных, предназначенный для представления взвешенных множеств. Множество называется взвешенным, если каждому его элементу однозначно соответствует число, называемое ключом или весом. Основными операциями над приоритетной очередью являются следующие операции:

ВСТАВИТЬ в множество новый элемент со своим ключом.

НАЙТИ в множестве элемент с минимальным ключом. Если элементов с минимальным ключом несколько, то находится один из них. Найденный элемент не удаляется из множества.

УДАЛИТЬ из множества элемент с минимальным ключом. Если элементов с минимальным ключом несколько, то удаляется один из них.

Дополнительные операции над приоритетными очередями:

ОБЪЕДИНИТЬ два множества в одно.

УМЕНЬШИТЬ ключ указанного элемента множества на заданное положительное число.

Приоритетная очередь естественным образом используется в таких задачах, как сортировка элементов массива, поиск во взвешенном неориентированном графе минимального остовного дерева, поиск кратчайших путей от заданной вершины взвешенного графа до его остальных вершин, и во многих других.
Приоритетную очередь можно представить с помощью массива или списка элементов, но такие реализации неэффективны по времени выполнения основных операций. Так, например, поиск элемента с минимальным ключом в неупорядоченном массиве или списке требует последовательного просмотра всех его элементов. Если поддерживать упорядоченность массива или списка по ключу, то "неудобной" окажется операция вставки нового элемента.
Чаще всего приоритетная очередь представляется с помощью корневого дерева или набора корневых деревьев с определенными свойствами. При этом узлам дерева ставятся во взаимно однозначное соответствие элементы рассматриваемого множества.
Соответствие между узлами дерева и элементами множества называется кучеобразным, если для каждого узла соблюдается следующее условие:
Ключ элемента, приписанного узлу , не превосходит ключей, приписанных его потомкам.
Такие представления взвешенных множеств называются кучами. Вид дерева и способ его представления в памяти компьютера подбирается в зависимости от тех операций, которые предполагается выполнять над множеством, и от того, насколько эти операции сказываются на суммарной трудоемкости алгоритма.

Представление приоритетной очереди с помощью d-кучи

Представление приоритетной очереди с помощью -кучи основано на использовании так называемых завершенных -арных деревьев ().
Завершенное -арное дерево — это корневое дерево со следующими свойствами:

Каждый внутренний узел (то есть узел, не являющийся листом дерева), за исключением, быть может, только одного, имеет ровно
потомков. Один узел-исключение может иметь от до
потомков.

Если — глубина дерева, то для любого
такое дерево имеет ровно узлов глубины .

Количество узлов глубины в дереве глубины
может варьироваться от до . Это свойство является следствием первых двух.

Узлы завершенного -арного дерева принято нумеровать следующим образом: корень получает номер 0, потомки узла с номером
получают номера: , , , . Такая нумерация удобна тем, что позволяет разместить узлы дерева в массиве в порядке возрастания их номеров, при этом позиции потомков любого узла в массиве легко вычисляются по позиции самого узла. Так же легко по позиции узла вычислить позицию его родителя. Так, для узла, расположенного в позиции , родительский узел располагается в позиции , где — операция деления нацело.
В изображении завершенного -арного дерева узлы одинаковой глубины удобно располагать на одном уровне, при этом потомки одного узла располагаются слева направо в порядке объявленных номеров. При таком рисовании нижний уровень заполняется, возможно, не полностью.
Отметим некоторые простые утверждения о завершенных -арных деревьях, которые будут полезны при анализе трудоемкости основных операций.
Утверждение 1.
Длина пути из корня завершенного -арного дерева с узлами в любой лист удовлетворяет неравенствам:
Доказательство
Минимальное количество узлов в -куче высоты
(), по свойствам 2 и 3 -арного дерева, очевидно, равно
(последний уровень содержит лишь один узел).
Максимальное количество узлов в такой -куче равно (последний уровень содержит узлов). Отсюда имеем неравенства:
Суммируя левую и правую части как геометрические прогрессии, получим и после некоторых очевидных оценок с помощью логарифмирования получаем требуемые неравенства:

Утверждение 2.

Количество узлов высоты не превосходит .

Под высотой узла понимается расстояние от него до наиболее далекого потомка. Кучу, содержащую элементов, будем представлять двумя массивами — и , — полагая что — имя элемента, приписанного узлу ; — его ключ. Иногда под

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

На рис. 4.1 приведен пример кучи для , . Кружочками изображены узлы дерева, в них записаны элементы массива, представляющие имена элементов кучи.

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

Рис. 4.1. 

Рис. 4.2. 

Применение приоритетных очередей в задаче сортировки

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

Сортировка методом "разделяй и властвуй".

Предположим, что в нашем распоряжении имеется процедура РАЗДЕЛЯЙ , которая по заданным значениям индексов , находит некоторое промежуточное значение и переставляет элементы сегмента так, чтобы для
выполнялось неравенство , а для — неравенство .
Тогда для сортировки сегмента
может быть использована рекурсивная процедура СОРТИРУЙ.
Для сортировки всего исходного массива достаточно выполнить оператор СОРТИРУЙ .
Заметим, что если бы процедура РАЗДЕЛЯЙ работала линейное от длины сегмента время и давала значение , близкое к середине между
и , то число обращений к ней приблизительно равнялось бы и сортировка всего массива проходила бы за время порядка . Однако можно доказать, что при естественной реализации эта оценка справедлива лишь в среднем.
Упражнения

Разработайте вариант процедуры СОРТИРУЙ без использования рекурсии. Сколько дополнительной памяти требуется для запоминания границ еще не отсортированных сегментов?

Охарактеризуйте работу процедуры СОРТИРУЙ на заранее отсортированном массиве.

Напишите на известном вам алгоритмическом языке программу сортировки числового массива с помощью процедуры СОРТИРУЙ и испытайте ее на массивах, сгенерированных с помощью датчика случайных чисел.

Составьте таблицу, отражающую время работы вашей программы на массивах разной длины. Каков максимальный размер массива, который можно отсортировать составленной программой на вашем компьютере?

Сортировка с помощью d-кучи.

Для представления сортируемой последовательности используем структуру -кучи. Сортировку можно провести в два этапа.

Окучить сортируемый массив, применяя последовательно операцию ПОГРУЖЕНИЕ по очереди к узлам
в предположении, что сначала все ключей занимают в произвольном порядке массив .

Осуществить окончательную сортировку следующим образом. Первый (минимальный) элемент кучи меняем местами с последним, уменьшаем размер кучи на 1 (минимальный элемент остается в последней позиции массива , не являясь уже элементом кучи) и применяем операцию ПОГРУЖЕНИЕ к корню, затем повторяем аналогичные действия, пока размер кучи не станет равным 1.

Эти два этапа реализуются с помощью процедуры SORT, которая сортирует массив по убыванию ключей:
Заметим, что процедура не требует дополнительной памяти, размер которой зависел бы от длины массива .
Упражнения

Докажите, что оператор
в процедуре можно заменить оператором

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

Сортировка "слиянием".

Этот метод является разновидностью метода "разделяй и властвуй"; впрочем, уместнее было бы назвать его "властвуй и объединяй".
Предположим, что у нас есть процедура СЛИВАЙ (, которая два уже отсортированных сегмента и
преобразует (сливает) в один сегмент , делая его полностью отсортированным. Тогда рекурсивная процедура
очевидно, сортирует сегмент , а для сортировки всего исходного массива достаточно выполнить оператор СОРТИРУЙ . Как видим, вопрос балансировки размера сегментов решается здесь просто. Число обращений к процедуре СЛИВАЙ
равно , а время ее выполнения легко сделать линейным от суммарной длины сливаемых сегментов.
Упражнения

Разработайте процедуру СЛИВАЙ и вариант процедуры СОРТИРУЙ без использования рекурсии. Сколько дополнительной памяти требуется для ее реализации?

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

Напишите на известном вам алгоритмическом языке программу сортировки числового массива методом слияния и испытайте ее на массивах, сгенерированных с помощью датчика случайных чисел.

Составьте таблицу, отражающую время работы вашей программы на массивах разной длины. Каков максимальный размер массива, который можно отсортировать составленной программой на вашем компьютере?

Структуры данных и модели вычислений

Левосторонние кучи

Левосторонняя куча — это представление приоритетной очереди с помощью так называемого левостороннего бинарного дерева. При реализации приоритетных очередей левосторонними кучами предусматривается возможность их объединения.
Бинарным деревом называется корневое дерево, у которого каждый узел имеет не более двух непосредственных потомков. Один из потомков называется левым, другой, если он есть, — правым. Узел называется неполным, если он имеет менее двух непосредственных потомков. В частности, листья дерева являются неполными узлами.
Рангом узла будем называть увеличенное на 1 расстояние (число ребер) от него до ближайшего неполного потомка.
Ранг узла также можно определить следующим образом. Расширить данное дерево до полного бинарного дерева, добавляя к каждому узлу, имеющему менее двух потомков, в том числе и к листьям исходного дерева, недостающее количество потомков. Затем приписать каждому из листьев полученного расширенного дерева ранг 0, а ранг каждого из остальных узлов определить как минимум из рангов его непосредственных потомков плюс 1. Очевидно, что ранги вершин исходного дерева совпадут с рангами соответствующих вершин расширенного дерева.
Левостороннее дерево — это бинарное дерево, для каждого узла которого ранг его левого непосредственного потомка в расширенном дереве не меньше ранга его правого потомка.
Ветвью бинарного дерева мы называем последовательность его узлов, начинающуюся с корня и заканчивающуюся листом, такую, что каждый следующий узел является непосредственным потомком предыдущего.
Правой ветвью дерева мы называем ветвь, заканчивающуюся в узле, не имеющем правого потомка, такую, что каждый следующий узел является непосредственным правым потомком предыдущего.
Пример левостороннего дерева (и его расширения) приведен на рис. 5.1. Ребра исходного дерева выделены жирными линиями, а ребра, добавленные при расширении, — пунктиром. Числа рядом с узлами — их ранги.

Рис. 5.1. 

Операции с левосторонними кучами

Операция СЛИЯНИЕ. Эта операция позволяет слить две левосторонние кучи и в одну кучу . Реализуется она посредством слияния правых путей двух исходных куч в один правый путь, упорядоченный по правилам кучи, а левые поддеревья узлов сливаемых правых путей остаются левыми поддеревьями соответствующих узлов в результирующем пути. В полученной куче необходимо восстановить свойство левизны каждого узла. Это свойство может быть нарушено только у узлов правого пути полученной кучи, так как левые поддеревья с корнями в узлах правых путей исходных куч не изменились. Восстанавливается свойство левизны при помощи прохода правого пути снизу вверх (от листа к корню) с попутным транспонированием в случае необходимости левых и правых поддеревьев и вычислением новых рангов проходимых узлов.
Рассмотрим процесс слияния двух левосторонних куч
и , изображенных на рис. 5.2.

Рис. 5.2. 
Числа внутри кружочков являются ключами элементов, приписанных к соответствующим узлам. Правые ветви куч показаны жирными линиями. Числа рядом с узлами — их ранги.
После объединения правых путей получим дерево, изображенное на рис. 5.3. Оно не является левосторонним. В скобках указаны ранги узлов, какими они были в исходных кучах до слияния.
Восстановление свойства левизны кучи начинаем с последнего узла правой ветви. Это узел с ключом . Очевидно, он должен иметь ранг , совпадающий с его старым значением и поэтому не требующий обновления.

Рис. 5.3. 
Следующий по направлению к корню узел правой ветви имеет ключ , ранг его левого сына не меньше ранга правого сына, следовательно, условие левизны выполняется и поэтому транспонирования его левого и правого поддеревьев не требуется. Однако ранг этого узла необходимо обновить, так как его старое значение не совпадает с увеличенным на
минимальным из рангов его потомков, то есть с числом 2. Обновив ранг, получим кучу, изображенную на рис. 5.4.

Рис. 5.4. 
Теперь рассмотрим узел с ключом . Он имеет левого сына с ключом
и рангом и правого сына с ключом и рангом . Для восстановления свойства левизны в этом узле необходимо поменять местами его левое и правое поддеревья и обновить ранг. Его новым значением будет минимум из рангов его потомков (это ранг нового правого сына) плюс , то есть . В результате получаем дерево, изображенное на рис. 5.5.

Рис. 5.5. 

Сводные данные о трудоемкости операций с левосторонними кучами

СЛИТЬ
ВСТАВИТЬ
УДАЛИТЬ_МИН
МИН
УДАЛИТЬ
УМЕНЬШИТЬ_КЛЮЧ
ОБРАЗОВАТЬ_ОЧЕРЕДЬ

Свойства левостороннего дерева

Правая ветвь из любого узла дерева имеет минимальную длину среди всех ветвей, исходящих из этого узла.

Длина правой ветви левостороннего дерева, имеющего узлов, ограничена величиной , .

Первое свойство непосредственно следует из определения левостороннего дерева. Для доказательства второго свойства рассмотрим левостороннее дерево , у которого длина правой ветви равна . Индукцией по числу докажем, что число узлов в таком дереве удовлетворяет неравенству . Действительно, при утверждение очевидно. При левое и правое поддеревья дерева будут левосторонними, а ранги их корней больше или равны . Следовательно, по предположению индукции число узлов в каждом из них больше или равно , а в дереве — больше или равно
Для реализации приоритетной очереди с помощью левосторонней кучи будем использовать узлы вида содержащие следующую информацию:

element — элемент приоритетной очереди или ссылка на него (используется прикладной программой);

key — его ключ (вес);

rank — ранг узла, которому приписан рассматриваемый элемент;

left, right — указатели на левое и правое поддеревья;

parent — указатель на родителя.

Куча представляется указателем на ее корень. Если — указатель на корень кучи, то через будем обозначать и саму кучу. Заметим, что указатель на родителя используется лишь в операциях УДАЛИТЬ и УМЕНЬШИТЬ_КЛЮЧ (см. ниже).

Структуры данных и модели вычислений

Ленивая левосторонняя куча

Ленивая левосторонняя куча — это представление приоритетной очереди левосторонним деревом, но при этом, в отличие от обычной левосторонней кучи, каждый узел может содержать, а может и не содержать в себе (быть пустым) элемент приоритетной очереди. Для реализации ленивой левосторонней кучи к каждому узлу добавляется еще одно поле, для хранения признака, содержит ли данный узел элемент или является пустым. Такие кучи носят название "ленивых" из-за способа выполнения операций УДАЛИТЬ и СЛИТЬ.
При выполнении операции УДАЛИТЬ узел не удаляется, а лишь помечается как пустой. Время "ленивого" выполнения этой операции равно .
Операция СЛИТЬ осуществляется следующим образом. Заводится пустой корневой узел, сыновьями которого становятся корневые узлы объединяемых куч. Время "ленивого" выполнения этой операций равно .
При операции НАЙТИ_ЭЛЕМЕНТ_С_МИНИМАЛЬНЫМ_КЛЮЧОМ происходит расплата за "лень", так как эта операция выполняется следующим образом. Сначала делается обход дерева сверху для составления списка, содержащего верхние непустые узлы, чьи родители помечены как пустые. Затем из построенного списка образуется приоритетная очередь с непустыми узлами, после чего берется элемент, содержащийся в корне дерева. Справедливо следующее
Утверждение.
Время выполнения операции НАЙТИ_ЭЛЕМЕНТ_С МИНИМАЛЬНЫМ_КЛЮЧОМ является величиной
где — количество верхних пустых элементов.
При операции УДАЛИТЬ_ЭЛЕМЕНТ_МИНИМАЛЬНЫМ_КЛЮЧОМ также происходит расплата за "лень". Она выполняется следующим образом. Сначала, как описано выше, делается обход дерева сверху для нахождения узла с минимальным ключом; найденный узел помечается как пустой. После этого, снова путем обхода дерева сверху, составляется список верхних непустых узлов. И, наконец, поддеревья с корнями в этих узлах сливаются в одну кучу .
Операция ВСТАВИТЬновый элемент в кучу
производится посредством слияния кучи с кучей, содержащей единственный элемент .
Операция ОБРАЗОВАТЬ_ОЧЕРЕДЬ в форме ленивой левосторонней кучи из элементов списка производится как в обычных левосторонних кучах, то есть с неленивыми слияниями.
Операция УМЕНЬШИТЬ_КЛЮЧ элемента на величину выполняется следующим образом. Ключ элемента уменьшается на , узел, его содержащий, помечается как пустой, из этого элемента
образуется новая одноэлементная куча, которая сливается с исходной кучей.

Самоорганизующаяся куча

Самоорганизующаяся куча — это представление приоритетной очереди корневым деревом, операции с которым производятся аналогично операциям с левосторонней кучей, но без использования рангов. Длина правого пути из корня такого дерева в лист может быть произвольной, поэтому время выполнения всех операций в худшем случае есть , где — число элементов в очереди. Однако среднее время выполнения произвольных операций есть , то есть время, приходящееся на одну операцию, как ни удивительно, является величиной . Для их реализации необходимо с каждым узлом дерева хранить элемент, его ключ, указатели на левое и правое поддеревья, то есть узлы представлять записями вида
Операция СЛИТЬ кучи и в одну кучу
выполняется следующим образом. Правые пути двух исходных куч
и сливаются в один путь, упорядоченный по правилам кучи, и этот путь становится левым путем результирующей кучи . Левые поддеревья узлов, попавших в результирующий левый путь, становятся правыми.
Операция ВСТАВИТЬ в кучу новый элемент производится посредством слияния кучи с кучей, содержащей единственный элемент . Таким образом, время выполнения этой операции равно времени выполнения операции СЛИТЬ.
Операция УДАЛИТЬ_ЭЛЕМЕНТ_С_МИНИМАЛЬНЫМ_КЛЮЧОМ производится посредством удаления корня кучи и слияния его левой и правой подкуч. Таким образом, вычислительная сложность этой операции равна вычислительной сложности операции СЛИТЬ.
ОперацияНАЙТИ_ЭЛЕМЕНТ_С_МИНИМАЛЬНЫМ_КЛЮЧОМ выполняется, очевидно, за время , так как этот элемент находится в корне.
Анализ времени выполнения операции СЛИТЬ. Поскольку время выполнения всех трудоемких операций определяется временем выполнения операции СЛИТЬ, остается проанализировать именно эту операцию. Очевидно, время ее выполнения пропорционально количеству узлов в правых путях исходных куч и . Длина такого пути в худшем случае может зависеть линейно от количества узлов в соответствующей куче. Таким образом, время выполнения операции СЛИТЬ есть величина , где , , — количества узлов в кучах , , , соответственно.
Нахождение суммарной оценки времени выполнения m операций СЛИТЬ. Введем определение. Узел назовем тяжелым, если количество узлов в его правом поддереве строго больше, чем в левом. Остальные узлы назовем легкими.
Определим потенциал коллекции куч как общее количество содержащихся в ней тяжелых узлов. Пусть — потенциал коллекции после выполнения -й операции.

Нахождение суммарной оценки времени выполнения m операций СЛИТЬ. Введем определение. Узел назовем тяжелым, если количество узлов в его правом поддереве строго больше, чем в левом. Остальные узлы назовем легкими.

Определим потенциал коллекции куч как общее количество содержащихся в ней тяжелых узлов. Пусть — потенциал коллекции после выполнения -й операции.

Утверждение.

Время выполнения операций СЛИТЬ, примененных к коллекции, состоящей из куч с нулевым потенциалом, является величиной , где

— общее количество узлов в коллекции.

Доказательство.

Пусть -я операция заключается в слиянии куч и в результирующую кучу . Пусть перед ее выполнением и — количества тяжелых узлов в правых путях куч и соответственно,

и — количества легких узлов в этих путях, ,

— количества тяжелых узлов в остальных частях куч.

Время выполнения этой операции с точностью до постоянного множителя оценивается сверху величиной .

Подсчитаем изменение потенциала при ее выполнении. Имеем

По завершении этой операции тяжелые узлы правых путей становятся легкими, их количество равно . Легкие узлы правых путей могут как стать тяжелыми, так и остаться легкими, их будет не более штук, а количества тяжелых узлов в остальной части обоих деревьев не изменились. Следовательно, количество

тяжелых узлов после выполнения операции удовлетворяет неравенству

Таким образом, получаем изменение потенциала

и, следовательно,

Из определения легкого узла следует, что количество легких узлов в куче не превосходит логарифма количества узлов в этой куче.

Следовательно, где , а — общее количество узлов в исходных кучах.

Суммируя левую и правую части последнего неравенства по , получаем, что величина

с точностью до постоянного множителя оценивается сверху величиной, пропорциональной , то есть принадлежит .

Величина является амортизационной оценкой времени выполнения операции СЛИТЬ, то есть величиной .

Замечание.

Вначале коллекция, состоящая из куч, к которым применяются операций СЛИТЬ, может иметь произвольное количество узлов, в сумме равное .Важно, чтобы потенциал каждой из них, следовательно, и суммарный потенциал был равен нулю, то есть кучи не должны первоначально иметь тяжелых узлов.

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

с максимальным количеством узлов, не имеющая тяжелых узлов. Остальные варианты являются промежуточными.

Особое значение имеет случай, когда каждая из начальных куч состоит из единственного узла.

Итак, для всех коллекций таких куч амортизационное время выполнения одной операции СЛИТЬ является величиной , где

— общее количество их узлов.

Сводные данные о трудоемкости операций с самоорганизующимися кучами

ОперацияВерхняя оценкаАмортизационная оценка

СЛИТЬ
ВСТАВИТЬ
УДАЛИТЬ_МИНИМУМ
НАЙТИ_МИНИМУМ

Сводные данные о трудоемкости операций с ленивыми левосторонними кучами

УДАЛИТЬ УЗЕЛ
НАЙТИ ЭЛЕМЕНТ С МИНИМАЛЬНЫМ КЛЮЧОМ
УДАЛИТЬ ЭЛЕМЕНТ С МИНИМАЛЬНЫМ КЛЮЧОМ
СЛИТЬ
ВСТАВИТЬ
ОБРАЗОВАТЬ ОЧЕРЕДЬ
УМЕНЬШИТЬ КЛЮЧ

Структуры данных и модели вычислений

Биномиальные кучи

Для каждого биномиальное дерево определяется следующим образом: — дерево, состоящее из одного узла высоты ; далее при
дерево
высоты формируется из двух деревьев , при этом корень одного из них становится потомком корня другого. На рис. 7.1
изображены биномиальные деревья .
Биномиальный лес — это набор биномиальных деревьев, в котором любые два дерева имеют разные высоты.

Рис. 7.1. 

Фибоначчиевы кучи

Название рассматриваемых куч связано с использованием чисел Фибоначчи при анализе трудоемкости выполнения операций. В отличие от биномиальных куч, в которых операции вставки, поиска элемента с минимальным ключом, удаления, уменьшения ключа и слияния выполняются за время , в фибоначчиевых кучах они выполняются более эффективно. Операции, не требующие удаления элементов, в этих кучах имеют учетную стоимость . Теоретически фибоначчиевы кучи особенно полезны, если число операций удаления мало по сравнению с остальными операциями. Такая ситуация возникает во многих приложениях.
Например, алгоритм, обрабатывающий граф, может вызывать процедуру уменьшения ключа для каждого ребра графа. Для плотных графов, имеющих много ребер, переход от к в оценке времени работы этой операции может привести к заметному уменьшению общего времени работы. Наиболее быстрые известные алгоритмы для задач построения минимального остовного дерева или поиска кратчайших путей из одной вершины используют фибоначчиевы кучи.
К сожалению, скрытые константы в асимптотических оценках трудоемкости велики и использование фибоначчиевых куч редко оказывается целесообразным: обычные двоичные (-ичные) кучи на практике эффективнее. С практической точки зрения желательно придумать структуру данных с теми же асимптотическими оценками, но с меньшими константами. Такие кучи будут рассмотрены в следующих разделах.
При отсутствии операций уменьшения ключа и удаления элемента фибоначчиевы кучи имели бы ту же структуру, что и биномиальные. Но в общем случае фибоначчиевы деревья обладают большей гибкостью, чем биномиальные. Из них можно удалять некоторые узлы, откладывая перестройку дерева до удобного случая.
Строение фибоначчиевой кучи. Каждая фибоначчиева куча состоит из нескольких деревьев. В отличие от биномиальных деревьев, здесь дети любого узла могут записываться в любом порядке. Они связываются в двусторонний циклический список. Каждый узел этого списка имеет поля и , указывающие на его соседей в списке. На рис. 7.2 показано схематическое строение фибоначчиевой кучи.

Рис. 7.2. 

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

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

истинно, если узел потерял ребенка после того, как он в последний раз сделался чьим-либо потомком. Позже будет ясно, как и когда это поле используется.

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

Доступ к куче производится ссылкой

на узел с минимальным ключом. Кроме того, общее число узлов задается атрибутом .

Потенциал. При анализе учетной стоимости операций используют метод потенциала. Пусть — число деревьев в корневом списке кучи , а — количество помеченных узлов. Потенциал определяется формулой

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

Максимальная степень Через обозначим верхнюю границу для степеней узлов в кучах, которые могут появиться при выполнении операций. Аргументом функции является общее число всех узлов в куче, обозначаемое через .

Мы не будем углубляться в анализ трудоемкости операций с фибоначчиевыми кучами, отсылая читателя к соответствующей литературе [7], [19]

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

Фибоначчиевы кучи ввел М.Фредман и Р.Тарьян [17].В их статье описаны также приложения фибоначчиевых куч к задачам о кратчайших путях из одной вершины, о кратчайших путях для всех пар вершин, о паросочетаниях с весами и о минимальном покрывающем дереве.

Впоследствии Д.Дрисколл и Р.Тарьян [16]

разработали структуру данных, называемую , как замену для фибоначчиевых куч. Есть две разновидности такой структуры данных. Одна из них дает те же оценки учетной стоимости, что и фибоначчиевы кучи. Другая — позволяет выполнять операцию за время в худшем случае, а операции и Delete — за время

в худшем случае. Эта структура данных имеет также некоторые преимущества по сравнению с фибоначчиевыми кучами при использовании в параллельных алгоритмах.

Свойства биномиальных деревьев

Дерево состоит из корня с присоединенными к нему корнями поддеревьев в указанном порядке.

Дерево имеет высоту .

Дерево имеет ровно узлов.

В дереве на глубине имеется ровно узлов.

В дереве корень имеет степень , остальные узлы имеют меньшую степень.

Для каждого натурального числа n существует биномиальный лес, в котором количество узлов равно .

Максимальная степень вершины в биномиальном лесе с
узлами равна .

Биномиальный лес содержит не более
биномиальных поддеревьев.

Чтобы убедиться в существовании биномиального леса из узлов, представим в двоичной системе счисления (разложим по степеням двойки) , где . Для каждого , такого, что , в искомый лес включаем дерево .
Биномиальная куча — это набор биномиальных деревьев, узлам которых приписаны элементы взвешенного множества в соответствии с кучеобразным порядком, при котором вес элемента, приписанного узлу, не превосходит весов элементов, приписанных его потомкам.
Поскольку количество детей у узлов варьируется в широких пределах, ссылка на детей осуществляется через левого ребенка, а остальные дети образуют односвязный список. Каждый узел в биномиальной куче представляется набором полей где — ключ (вес) элемента, приписанного узлу, — родитель узла,
— левый ребенок узла, — правый брат узла, — степень узла.
Доступ к куче осуществляется ссылкой на самое левое поддерево. Корни деревьев, из которых составлена куча, оказываются организованными с помощью поля в так называемый корневой односвязный список.
Поиск элемента с минимальным ключом. Поскольку искомый элемент находится в корне одного из деревьев кучи, элемент с минимальным ключом находится путем просмотра корневого списка за время .
Слияние двух очередей. Две очереди и объединяются в одну очередь следующим образом. Последовательно выбираются деревья из исходных очередей в порядке возрастания их высот и вставляются в результирующую очередь , вначале пустую.
Если дерево очередной высоты присутствует лишь в одной из исходных очередей, то перемещаем его в результирующую очередь. Если оно присутствует в одной из исходных очередей и уже есть в результирующей очереди, то объединяем эти деревья в одно , которое вставляем в . Если присутствует во всех трех очередях, то сливаем два из них в
и вставляем в , а третье дерево просто перемещаем в . Трудоемкость — .
Вставка нового элемента. Создается одноэлементная очередь из вставляемого элемента, которая объединяется с исходной очередью. Трудоемкость — .
Удаление минимального элемента. Сначала в исходной куче
производится поиск дерева , имеющего корень с минимальным ключом. Найденное дерево удаляется из , его прикорневые поддеревья включаются в новую очередь , которая объединяется с исходной очередью . Трудоемкость — .
Уменьшение ключа. Осуществляется с помощью всплытия. Трудоемкость — .
Удаление элемента. Уменьшается ключ удаляемого элемента до , применяется всплытие, всплывший элемент удаляется как минимальный. Трудоемкость — .

Структуры данных и модели вычислений

Основные определения

Рассматриваемые здесь тонкие и, в следующей лекции, толстые кучи предложены М.Фредманом и Х.Капланом как альтернатива фибоначчиевым кучам. Долгое время фибоначчиевы кучи считались рекордными по производительности. Оценки операций над фибоначчиевыми кучами имеют амортизационный характер, а скрытые в них константы велики настолько, что реальный выигрыш во времени работы с ними достигался только на данных "астрономических" размеров. Рассматриваемые здесь тонкие кучи имеют те же асимптотические оценки, что и фибоначчиевы, но гораздо практичнее их. Оценки для толстых куч "хуже" по операции слияния, выполняемой за O(\log n) времени. Достоинством этой структуры является то, что ее оценки рассчитаны на худший случай. Заметим, что на данный момент ни фибоначчиевы, ни толстые, ни тонкие кучи не являются рекордными, так как Г.Бродал предложил новую структуру, которую мы будем называть кучей Бродала. Кучи Бродала характеризуется такими же, как и фибоначчиевы кучи, оценками операций, но все оценки справедливы для худшего случая. К сожалению, структура, предложенная Г.Бродалом, сложна для реализации. Рассмотрим реализацию приоритетной очереди с помощью тонкой кучи.
Тонкие кучи, как и многие другие кучеобразные структуры, аналогичны биномиальным кучам.
Тонкое дерево
ранга — это дерево, которое может быть получено из биномиального дерева
удалением у нескольких внутренних, то есть не являющихся корнем или листом, узлов самого левого сына. Заметим, что у листьев детей нет, а если у корня удалить самого левого сына, то
превратится в . Ранг тонкого дерева равен количеству детей корня.
Для любого узла в дереве обозначим: — количество детей узла ; — ранг соответствующего узла в биномиальном дереве .
Тонкое дерево удовлетворяет следующим условиям:

Для любого узла либо , в этом случае говорим, что узел не помечен (полный); либо , в этом случае говорим, что узел помечен (неполный).

Корень не помечен (полный).

Для любого узла ранги его детей от самого правого к самому левому равны соответственно .

Узел помечен тогда и только тогда, если его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1 и он не имеет детей.

На рис. 8. 1 приведены примеры тонких деревьев; числа рядом с узлами обозначают их ранги. Вверху изображено биномиальное дерево , внизу — два полученных из тонких дерева ранга три. Стрелки указывают на помеченные узлы. Заметим, что биномиальное дерево является тонким деревом, у которого все узлы не помечены.

Тонкий лес — это набор тонких деревьев, ранги которых не обязательно попарно различны.

Рис. 8.1. 

Тонкая куча — это кучеобразно нагруженный тонкий лес.

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

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

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

Пусть — максимально возможный ранг узла в тонкой куче, содержащей элементов.

Теорема [22]

В тонкой куче из элементов , где — золотое сечение.

Доказательство. Сначала покажем, что узел ранга

в тонком дереве имеет не менее потомков, включая самого себя, где — -е число Фибоначчи, определяемое соотношениями , , для .

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

тонкого дерева получаем следующие соотношения:

Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что для любых . Неравенство

хорошо известно.

Теперь убедимся в том, что максимально возможный ранг

тонкого дерева в тонкой куче, содержащей элементов, не превосходит числа . Действительно, выберем в тонкой куче дерево максимального ранга. Пусть — количество вершин в этом дереве, тогда .

Отсюда следует, что .

Представление тонкой кучи в памяти компьютера.

Тонкие кучи формируют из узлов, представленных записями следующего вида: где — ключ элемента, приписанного узлу; — указатель на ближайшего левого брата, если такового нет, то на родителя, а если нет и родителя, то указатель заземлен; — указатель на ближайшего правого брата, если такового нет, то указатель заземлен; — указатель на самого левого сына, если такового нет, то указатель заземлен; — ранг узла.
Таким образом, узлы-братья связаны в двусвязный список при помощи указателей и . У самого левого брата в этом списке указатель указывает на общего родителя всех узлов в списке. У самого правого брата из списка указатель заземлен. Корни деревьев в тонкой куче связаны в односвязный циклический список. Этот список будем называть корневым списком. Корневой список реализуется при помощи поля . Поле у каждого узла корневого списка заземлено.
В случае необходимости в описании узла может присутствовать и другая прикладная информация. На рис. 8.2 приведен пример тонкой кучи.

Тонкая куча
Представление кучи со ссылками, в узлах указаны ранги

Рис. 8.2. 
Заметим, что принадлежность заданного узла корневому списку кучи осуществляется проверкой указателя на заземленность.
Введем еще одну запись , которая будет соответствовать отдельной куче и иметь вид где — указатель на начальный элемент корневого списка; — указатель на элемент корневого списка с минимальным ключом.
Очевидно, что узел с минимальным ключом обязательно находится в корневом списке.

Реализация основных операций и оценки трудоемкости

Сосредоточим внимание на амортизационных оценках трудоемкости. Будем получать их методом потенциалов. Потенциалом тонкой кучи будем считать величину , где — количество деревьев в куче, а — число помеченных вершин. Заметим, что потенциал кучи неотрицателен и в начальный момент равен .
Операция MakeHeap. Эта операция создает указатель на новую пустую кучу. Очевидно, фактическая стоимость операции есть , а потенциал созданной кучи равен .
Операция FindMin (H). Указатель на узел с минимальным ключом в куче определяется с помощью указателя . Если куча пуста, то результирующий указатель нулевой. Амортизационная оценка совпадает с фактической и равна , потенциал не изменяется.
Операция Insert(i,H). С помощью этой операции осуществляется вставка в кучу нового элемента с ключом . При ее реализации создается новое тонкое дерево ранга , которое вставляется в корневой список кучи , разрывая его в произвольном месте. При необходимости перевычисляется ссылка на минимальный элемент.
Операция увеличивает потенциал на , так как добавляется одно дерево в корневой список кучи, но это не влияет на амортизационную оценку, которая равна фактической .
Операция Meld(H1, H2). Результатом этой операции является указатель на кучу, полученную слиянием двух куч
и . Она осуществляется соединением корневых списков сливаемых куч. При таком способе выполнения операции, как и при реализации вставки элемента в кучу, можем получить в корневом списке результирующей кучи несколько деревьев одинакового ранга. При удобном случае, а именно при удалении минимального элемента, мы освободим корневой список от этой неоднозначности. Оценка совпадает с оценками для всех предыдущих операций. Суммарный потенциал не изменяется.

Структуры данных и модели вычислений

Избыточное представление чисел

Рассматриваемое в этой лекции представление приоритетной очереди основано на использовании так называемых избыточных счетчиков, позволяющих за время O(1) инкрементировать любой разряд. Заметим, что использованные здесь счетчики — лишь один из способов реализации толстых куч. На самом деле, для их реализации подойдет произвольный d-арный счетчик, при условии, что трудоемкость инкрементирования любого его разряда является константной.
Основные определения. Избыточным -арным представлением неотрицательного целого числа будем считать последовательность , , такую, что где , . Будем называть цифрой, стоящей в -м разряде. В примерах запятые между цифрами опускаем.
Заметим, что избыточное представление отличается от обычного -арного представления использованием "лишней" цифры , что приводит к неоднозначности представления чисел. Например, при число может быть представлено как и как .
В примерах, в которых , "цифру" 10 будем обозначать символом .
Назовем -арное избыточное представление числа регулярным, если в нем между любыми двумя цифрами, равными , найдется цифра, отличная от .
Пример.
Пусть , а число представляется в обычной десятичной системе последовательностью , тогда представления и не являются регулярными -арными избыточными представлениями числа , а представления и регулярны.
Пусть — номер разряда, отличного от и ближайшего слева от -го разряда в регулярном -арном избыточном представлении .
Определим следующим образом: , если ,
и ; — произвольное число , если
и ; — не определено, если .
Величину будем называть прямым указателем. Пусть — -арное регулярное представление некоторого числа.
Фиксацией цифры b, стоящей в i-м разряде представления d,
назовем операцию, заключающуюся в обнулении цифры
и инкрементировании цифры , при этом если , то полагаем . При каждом выполнении операции фиксации будем обновлять значение . Очевидно, при операцию можно выполнить с помощью следующих операторов.
Инкрементирование i-й цифры избыточного представления d можно выполнить с помощью операторов
Очевидно, что инкрементирование -го разряда регулярного -арного избыточного представления числа
производит представление числа .
Нетрудно доказать, что операции фиксации и инкрементирования, примененные к регулярному избыточному представлению, не нарушают регулярности и корректно вычисляют указатели с трудоемкостью .
Эта схема может быть расширена для выполнения за константное время декрементирования произвольной цифры добавлением дополнительного цифрового значения . Оставляем детали в качестве упражнения.

Основные операции

Операция make-heap заключается в инициализации счетчиков. Трудоемкость .
Операция FindMinвозвращает указатель на минимальный элемент. Трудоемкость .
Операция Insert(key). Чтобы выполнить эту операцию, делаем новый элемент отдельным деревом и выполняем процедуру вставки нового элемента ранга в корневой счетчик. После этого, если необходимо, корректируем значение указателя на минимальный элемент.
Операция уменьшения ключа DecreaseKey. Чтобы выполнить эту операцию, поступим следующим образом. Пусть— узел, на который указывает указатель . Вычитаемиз ключа узла . Если новый ключ меньше минимального ключа кучи , обмениваем ключ элементас ключом минимального элемента. Новых нарушений операция не создаст. Пусть — ранг. Если — нарушаемый узел, добавляемкак новое-ранговое нарушение инкрементированием-й цифрысчетчика нарушений. Трудоемкость .
Операция DeleteMin выполняется следующим образом. Удаляем поддерево с корнем в минимальном узле из леса. Минимальность этого элемента гарантирует нам, что среди его детей нарушений порядка кучи не было. То есть нет необходимости работать со счетчиком нарушений. Затем вставляем в кучу все деревья с корнями, расположенными в детях удаляемого узла. Очевидно, что новый минимальный ключ — либо в корне дерева леса, либо в нарушенном узле. Выполняем поиск нового минимального элемента среди корней деревьев и нарушенных узлов.
Если минимальный элемент оказался в нарушенном узле, то обмениваем его с элементом, хранимым в корне этого дерева, корректируя корневой счетчик, если это необходимо. После замены новый минимум — в корне дерева леса. Этот корень будет новым минимальным узлом. Трудоемкость операции равна .
Операция удаления элемента. Выполняется с помощьюи затем. Трудоемкость операции .
Операция Meld(h1, h2). Выполняется следующим образом. Первый шаг — фиксируются все нарушения в куче с меньшим максимальным рангом (разрывая связь произвольно). Не уменьшая общности, считаем, что эта куча —. Пройти по счетчику нарушений от младшей цифры к старшей, пропуская цифры со значением .
Для - й цифрыделаем операцию фиксирования на каждой цифре, показываемой прямым указателем, если эта цифра имеет значение 2. Затем, если, фиксируем . Если, преобразуем это-ранговое нарушение в -ранговое нарушение, как при фиксировании, используя-рангового брата нарушенного узла вместо (несуществующего) другого-рангового нарушения.

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

Операция DeleteViolation. Для освобождения кучи от нарушений достаточно выполнить операторы

Основываясь на описанной выше реализации толстой кучи, получаем следующий результат. В толстых кучах операцииивыполняются за время , а и— за время .

Замечание.

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

Г.Бродал описывает кучевидную структуру, которая теоретически лучше, чем толстые кучи, так как их временная оценка для—в худшем случае. Структура Бродала, однако, намного сложнее толстых куч.

Толстая куча

Толстая куча — это почти кучеобразный нагруженный лес.
Представление толстой кучи. Каждый узел толстой кучи будем представлять записью следующего вида: где — ключ элемента, приписанного узлу дерева; — указатель на родителя; — указатель на ближайшего левого брата; — указатель на ближайшего правого брата; — указатель на самого левого сына; — ранг узла. Таким образом, "братья" связаны в двусвязный список при помощи указателей
и . У самого левого (правого) "брата" в этом списке указатель () заземлен.
На рис. 9.2 представлено толстое дерево
(внутри узлов указаны их ранги).

Рис. 9.2. 

Толстые деревья

Основные определения
Определяем толстое дерево ранга
следующим образом:

Толстое дерево ранга ноль состоит из единственного узла.

Толстое дерево ранга , для , состоит из трех деревьев
ранга , связанных так, что корни двух из них являются самыми левыми потомками корня третьего.

Ранг узла в толстом дереве определяется как ранг толстого поддерева с корнем в узле .
На рис. 9.1 приведены примеры толстых деревьев.

Рис. 9.1. 
Свойства толстых деревьев:

В толстом дереве ранга ровно узлов.

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

Толстый лес из узлов содержит деревьев.

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

Вспомогательные процедуры

Процедура обновления прямого указателя -го разряда счетчика нарушений аналогична процедуре
для корневого счетчика. Необходимо лишь учесть, что счетчик нарушений — двоичный.

Процедура корректировки списочной части -го разряда счетчика нарушений при появлении в куче нового -рангового нарушения — назовем ее
— вставляет новый нарушенный узел, обновляя, в зависимости от значения , либо первый , либо второй указатель. Причем перед тем как вставлять в счетчик новое нарушение, необходимо проверить, не присутствует ли оно там.

Процедура взаимной замены поддеревьев кучи с корнями в узлах и — назовем ее — подразумевает, что ранги обмениваемых деревьев одинаковы.

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

Функция, которая связывает три толстых дерева ранга в одно толстое дерево ранга , аналогична соответствующей функции для корневого счетчика.

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

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

Разобьем дальнейшее рассмотрение на два случая:

Ранг равен . Пусть и — это толстые деревья ранга с корнями в двух нарушаемых узлах, а дерево — толстое дерево ранга , полученное из поддерева с корнем в узле

удалением поддеревьев и .

Если узел не является корнем дерева , то удаляем из дерева

поддерево . Из трех толстых деревьев ) ранга образуем одно дерево ранга , чей корень является узлом с наименьшим ключом среди корней деревьев . Вставляем в дерево вновь полученное толстое дерево с корнем в узле вместо поддерева с корнем в узле . Если узел оказывается нарушенным, инкрементируем . Значение -го разряда делаем нулевым.

Если узел — корень дерева , то удаляем дерево из кучи. Из трех толстых деревьев

ранга образуем одно дерево ранга , чей корень является узлом с наименьшим ключом среди ключей корней деревьев . Вставляем вновь полученное толстое дерево с корнем в узле

в кучу. Значение -го разряда делаем нулевым.

Если ранг больше, чем , то, по условию регулярности счетчика нарушений, узел должен иметь хотя бы одного сына ранга , который не является -ранговым нарушением, и два -ранговых сына должны быть также ненарушенными. Тогда заменяем два нарушенных -ранговых сына узла на два хороших -ранговых сына узла . Тем самым мы свели задачу к случаю 1.

Можно доказать, что рассматриваемая операция не испортит регулярности счетчика.

Инкрементирование i-го разряда счетчика нарушений . Используя описанную выше операцию фиксации, можно осуществить инкрементирование -го разряда счетчика нарушений следующими операторами:

Трудоемкость операции .

Удаление нарушения из кучи. Заметим, что удаление нарушения из кучи подразумевает наличие в куче этого нарушения; пусть это нарушение ранга .Тогда значение -го разряда для счетчика нарушений не равно нулю. Следовательно, уменьшение этого значения на единицу не испортит регулярности и не потребует обновления каких-либо указателей. Необходимо лишь уменьшить на единицу значение переменной и обработать указатели и . Очевидно, что трудоемкость этой операции .

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

Вспомогательные структуры

Для представления толстой кучи введем новую структуру, которую назовем корневым счетчиком, а для того, чтобы быстро находить неправильные узлы, введем еще один избыточный счетчик, который назовем счетчиком нарушений. Таким образом, толстую кучу можно представить записью следующего вида: где — массив, соответствующий корневому счетчику; — массив, соответствующий счетчику нарушений; — указатель на элемент кучи, имеющий минимальный ключ; — наибольший ранг среди рангов деревьев, присутствующих в куче.
Корневой счетчик. Корневой счетчик состоит из избыточного троичного представления числа элементов в куче и набора списочных элементов.
Значение -го разряда избыточного корневого представления равно количеству деревьев ранга , присутствующих в куче. При таком определении избыточного корневого представления число, которое оно представляет, равно числу узлов в куче, так как толстое дерево ранга содержит ровно узлов. Заметим, что состояние избыточного корневого представления определяется неоднозначно. Отсюда следует, что толстая куча с одним и тем же набором элементов может быть представлена различными наборами толстых деревьев. Очевидно, что для любой толстой кучи, состоящей из элементов, существует регулярное избыточное представление корневого счетчика.
Списочный элемент, приписанный -му разряду избыточного корневого представления, — это указатель на список деревьев ранга , присутствующих в куче, образованный посредством указателей корневых узлов связываемых деревьев.
Определение корневого счетчика дает возможность сделать несколько утверждений:

Корневой счетчик позволяет иметь доступ к корню любого дерева ранга за время .

Вставка толстого дерева ранга соответствует операции инкрементирования -го разряда корневого счетчика.

Удаление толстого поддерева ранга соответствует операции декрементирования -го разряда корневого счетчика.

Операции инкрементирования и декрементирования -го разряда корневого счетчика осуществляются за время .

Представление корневого счетчика. Корневой счетчик представляем расширяющимся массивом , каждый элемент которого — запись с тремя полями:
которые интерпретируем следующим образом:

— - й разряд, равный количеству деревьев ранга ;

— прямой указатель -го разряда;

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

корневых узлов связываемых деревьев. Если в куче нет деревьев ранга , то указатель заземлен. Заметим, что если значение равно нулю, то нам неважно, каково значение указателя .

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

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

Обновление прямого указателя i-го разряда корневого счетчика заключается в выполнении операторов

Корректировка списочной части i-го разряда корневого счетчика при вставке в кучу нового дерева ранга i. Эта процедура вставляет новое дерево ранга

(на него указывает указатель ) в списочную часть -го разряда корневого счетчика и заключается в выполнении операторов

Корректировка списочной части i>-го разряда корневого счетчика при удалении из кучи дерева ранга i. Эта процедура удаляет дерево ранга (на него указывает указатель ) из списочной части -го разряда корневого счетчика . Будем считать, что указанное дерево присутствует в куче. Процедура заключается в выполнении операторов

Связывание (Fastening (p1, p2, p3)) трех толстых деревьев ранга i в одно толстое дерево ранга i +1.Эта функция принимает три указателя на три разных толстых дерева одного и того же ранга и возвращает указатель на вновь сформированное дерево ранга .


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

Процедура заключается в выполнении операторов

Функция GetKey (p) по указателю p на элемент определяет значение его ключа и реализуется оператором

Функция MinKeyNodeRoot(p), которая по указателю на списочную часть разряда корневого счетчика возвращает указатель на корневой узел с минимальным ключом, реализуется операторами

Очевидно, что трудоемкость всех приведенных выше операций оценивается величиной .

Операция фиксации ({\rm FixRootCount(i)}) Операция фиксации -го разряда корневого счетчика подразумевает, что его значение равно трем, а списочная часть содержит указатель на список деревьев ранга , состоящий ровно из трех деревьев. При выполнении этой операции значение в -м разряде — должно стать равным нулю, а значение в -м разряде увеличиться на единицу. То есть в куче не должно остаться деревьев ранга , а количество деревьев ранга должно увеличиться на единицу. Для этого следует удалить из кучи три присутствующих в ней дерева ранга , связать их в дерево ранга и вставить вновь полученное дерево в кучу.

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

Операция фиксации осуществляется с помощью операторов

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

Инкрементирование i-го разряда корневого счетчика ({\rm IncRootCount(i,p)}). По сравнению с описанным алгоритмом инкрементирования -го разряда избыточного представления здесь мы должны учесть работу со списочной частью и обновить прямые указатели. Процедура реализуется операторами

Очевидно, что, если корневой счетчик находится в корректном состоянии и , то операция инкрементирования -го разряда корневого счетчика переводит корневой счетчик в новое корректное состояние.


Трудоемкость этой операции равна .

Процедура удаления дерева из кучиподразумевает наличие в куче этого дерева. Пусть удаляемое дерево имеет ранг . Тогда значение -го разряда избыточного корневого представления не равно нулю. То есть уменьшение этого значения на единицу не испортит регулярности представления и не потребует обновления каких-либо указателей. Необходимо лишь соответствующим образом обработать списочную часть. Процедура реализуется операторами

Трудоемкость операции .

Нахождение дерева с минимальным ключом в корне реализуется операторами

Трудоемкость данной операции также .

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

Отличие заключается в том, что:

Нас теперь интересует не само число, а только значения разрядов.

Операция фиксации тесно связана с толстой кучей.

Значение -го разряда для счетчика нарушений интерпретируется как количество неправильных узлов ранга , а его списочная часть — это указатели на неправильные узлы ранга .

Такое определение счетчика нарушений дает возможность сделать несколько утверждений:

Наличие счетчика нарушений позволяет иметь доступ к любому неправильному узлу ранга за время .

Уменьшение ключа у элемента ранга

соответствует операции инкрементирования -го разряда счетчика нарушений (естественно, лишь в случае, когда новое значение ключа у изменяемого узла становится меньше значения ключа его родителя).

Операции инкрементирования и декрементирования -го разряда осуществляются за время .

Представление счетчика нарушений. Счетчик нарушений — это расширяющийся массив, элементы которого являются записями из четырех полей

со следующей интерпретацией:

— количество неправильных узлов ранга в куче, — прямой указатель -го разряда,

и — указатели на неправильные узлы ранга .

Заметим, что если значение

равно единице, то важно лишь значение первого указателя и не играет роли значение второго . Если равно нулю, то неинтересны оба указателя.

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

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

Структуры данных и модели вычислений

АВЛ-деревья

АВЛ-балансировка по определению требует, чтобы для каждого узла высота его правого поддерева отличалась от высоты левого не более чем на единицу.
Пусть— минимальное число узлов в АВЛ-дереве высоты . Тогда,,, при .
Теорема.
Для любоговыполняется неравенство, где — положительный корень уравнения .
Доказательство.
Непосредственно проверяется базис индукции,. Предположим теперь, что при выполняется неравенство , и докажем его при . Действительно, . Докажем последнее в этой цепочке неравенство.
Пусть, тогда и, следовательно,. Получили противоречие .
Следствие.
Для любого АВЛ-дерева высоты с узлами выполняется соотношение, что обеспечивает "логарифмическую трудоемкость" выполнения основных операций с АВЛ-деревом.
Идея балансировки двоичных деревьев поиска принадлежит\linebreak Г.М.Адельсону-Вельскому и Е.М.Ландису, предложившим в 1962 г. класс сбалансированных деревьев, называемых с тех пор АВЛ-деревьями. Баланс поддерживается с помощью процедуры вращения. Для его восстановления в дереве с узлами после добавления или удаления узла может потребоватьсявращений.
Еще один класс деревьев поиска, называемых--деревьями, был предложен Дж. Хопкрофтом в 1970 г. Здесь баланс поддерживается за счет изменения степеней узлов. Обобщение--деревьев предложили Д.Байер и Е.Мак-Крейт. Их деревья называются Б-деревьями, которые мы рассмотрим в следующем разделе.
Красно-черные деревья предложил Д.Байер, назвав их симметричными двоичными Б-деревьями. Л.Гибас подробно изучил их свойства и предложил использовать для наглядности красный и черный цвета Посмотрите [7].
Из многих других вариаций на тему сбалансированных деревьев наиболее интересны расширяющиеся деревья, которые придумали Д.Слеатор и Р.Тарьян. Эти деревья являются саморегулирующимися. Хорошее описание расширяющихся деревьев дал Тарьян. Расширяющиеся деревья поддерживают баланс без использования дополнительных полей (типа цвета). Вместо этого расширяющие операции, включающие вращения, выполняются при каждом обращении к дереву. Учетная стоимость в расчете на одну операцию с деревом для расширяющихся деревьев составляет.

Б-деревья

Б-деревья — это один из видов сбалансированных деревьев, обеспечивающих эффективное хранение информации на магнитных дисках и других устройствах с прямым доступом. Б-деревья похожи на красно-черные, разница в том, что в Б-дереве узел может иметь много детей, на практике до тысячи, в зависимости от характеристик используемого диска. Благодаря этому константа в оценке для высоты дерева существенно меньше, чем для красно-черных деревьев. Как и красно-черные деревья, Б-деревья позволяют реализовать многие операции с множествами размера за время .
Узел, хранящийключей, имеетдетей. Хранящиеся в ключи служат границами, разделяющими всех его потомков на групп; за каждую группу отвечает один из потомков . При поиске в Б-дереве мы сравниваем искомый ключ с ключами, хранящимися в , и по результатам сравнения выбираем одного из потомков.

Добавление элемента.

Процедурадобавляет заданный элемент в подходящее место дерева . Параметром процедуры является указатель на новую вершину, в которую помещены значения,и . В ходе работы процедура изменяет дерево и (возможно) некоторые поля вершины , после чего новая вершина с данным значением ключа оказывается вставленной в подходящее место дерева:
Подобно процедурами , процедурадвигается вниз по дереву, начав с его корня. При этом в вершине сохраняется указатель на родителя вершины . Сравниваяс , процедура решает куда идти — налево или направо. Процесс завершается, когда становится равным . Этот стоит как раз там, куда надо поместить , что и делается. Очевидно, добавление требует временидля дерева высоты .

Комбинаторные свойства красно-черных деревьев

Для произвольного узлаопределим черную высотукак количество черных узлов на пути из в некоторый лист, не считая сам узел . По свойству 4 эта сумма не зависит от выбранного листа. Черной высотой дерева будем считать черную высоту его корня.
Пусть— количество внутренних узлов в поддереве с корнем({\rm nil}-узлы не считаются).
Лемма 1.
Для произвольного узла красно-черного дерева выполняется неравенство .
Доказательство.
Если— лист, тои, следовательно, утверждение леммы выполнено. Далее, пусть для узлови утверждение леммы справедливо, то есть
тогда
Предпоследнее неравенство справедливо в силу соотношения
Лемма 2.
Красно-черное дерево свнутренними узлами-листья не считаютсяимеет высоту не больше .
Доказательство.
Обозначим высоту дерева через . Согласно свойству 3, по меньшей мере половину всех вершин на пути от корня к листу, не считая корень, составляют черные вершины. Следовательно, черная высота дерева не меньше . Тогда и, переходя к логарифмам, получаем или . Лемма доказана.
Полученная оценка высоты красно-черных деревьев гарантирует выполнение операций,,,и с красно-черными деревьями за время. Сложнее обстоит дело с процедурамии: проблема в том, что они могут испортить структуру красно-черного дерева, нарушив RB-свойства. Поэтому описанные процедуры придется модифицировать. Ниже увидим, как можно реализовать их за времяс сохранением RB-свойств.

Красно-черные деревья

Мы видели, что основные операции с двоичным поисковым деревом высоты могут быть выполнены за действий. Деревья эффективны, если их высота мала, но если не принимать специальные меры при выполнении операций, малая высота не гарантируется, и в этом случае деревья не более эффективны, чем списки.
Для повышения эффективности операций используют различные приемы перестройки деревьев, чтобы высота дерева была величиной. Такие приемы называются балансировкой деревьев. При этом используются разные критерии качества балансировки. Одним из видов сбалансированных деревьев поиска являются так называемые красно-черные деревья, для которых предусмотрены операции балансировки, гарантирующие оценку высоты величиной.
Частным случаем такой балансировки является АВЛ-балансировка, при которой у каждого узла высота его левого поддерева отличается от высоты правого не более чем на единицу. Заметим, что наихудшими в некотором смысле АВЛ-деревьями являются деревья Фибоначчи, определяемые следующим образом:— пустое дерево,— дерево, состоящее из одного узла. При деревосостоит из корня с левым поддеревоми правым —. Нетрудно видеть, что при заданной величине деревоимеет наименьшее число узлов среди всех АВЛ-деревьев высоты .
Для удобства поисковые деревья будем расширять, вводя дополнительный фиктивный узел (-узел) и считая его потомком каждого узла исходного дерева, у которого нет правого, левого или обоих потомков, его же считаем родителем корня.
Красно-черное дерево — это расширенное двоичное дерево поиска, вершины которого разделены на красные (red) и черные (black) так, что:

Каждый узел либо красный, либо черный.

Каждый лист (-узел) — черный.

Если узел красный, то оба его ребенка черные.

Все пути, идущие вниз от корня к листьям, содержат одинаковое количество черных узлов.

Свойства 1-4 называют RB-свойствами. Узлы красно-черного дерева будем представлять записями вида

Общие сведения

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

Search — поиск элемента с заданным ключом.

Minimum — поиск элемента с минимальным ключом.

Maximum — поиск элемента с максимальным ключом.

Predecessor — поиск элемента с предыдущим ключом.

Successor — поиск элемента со следующим ключом.

Insert — вставка элемента со своим ключом.

Delete — удаление указанного элемента.

Считается, что каждый элемент словаря имеет ключ (вес), принимающий значение из какого-либо линейно упорядоченного множества. Таким множеством может быть, например, числовое множество или множество слов в некотором алфавите. В последнем случае в качестве линейного порядка можно рассматривать лексикографический порядок. Таким образом, дерево поиска может быть использовано и как словарь, и как приоритетная очередь.
Время выполнения основных операций пропорционально высоте дерева. Если каждый внутренний узел двоичного дерева имеет ровно двух потомков, то его высота и время выполнения основных операций пропорциональны логарифму числа узлов. Напротив, если дерево представляет собой линейную цепочку из узлов, это время вырастает до . Известно, что высота случайного двоичного дерева поиска есть , так что в этом случае время выполнения основных операций есть .
Конечно, возникающие на практике двоичные деревья поиска могут быть далеки от случайных. Однако, приняв специальные меры по балансировке деревьев, мы можем гарантировать, что высота деревьев с узлами будет . Ниже рассмотрим один из подходов такого рода (красно-черные деревья и, как частный случай, АВЛ-деревья). Будут рассмотрены также Б-деревья, которые особенно удобны для данных, хранящихся во вторичной памяти с произвольным доступом (на диске).

Операции с двоичным поисковым деревом

Процедура обходит все узлы поддерева с корнем в узле и печатает их ключи в неубывающем порядке:
Свойство упорядоченности гарантирует правильность алгоритма. Время работы на дереве с вершинами есть , каждая вершина обрабатывается один раз. Операторнапечатает ключи всех элементов в неубывающем порядке.
Заметим, что порядок, при котором корень предшествует узлам обоих поддеревьев, называется preorder; порядок, в котором корень следует за ними, называется postorder.
Покажем, что двоичные поисковые деревья позволяют выполнять операции,,,иза время (, где— высота дерева.
Поиск ({\rm Search)}. Процедура поиска получает на вход искомый ключ и указатель на корень дерева и возвращает указатель на вершину с ключом (если такая есть) или (если такой вершины нет).

В процессе поиска мы двигаемся от корня, сравнивая ключ с ключом, хранящимся в текущей вершине . Если они равны, поиск завершается. Если, то поиск продолжается в левом поддереве , если же, то в правом. Длина пути поиска не превосходит высоты дерева, поэтому время поиска есть(где — высота дерева).
Итеративная версия процедуры Поиск

Минимум и Максимум. Элемент с минимальным ключом в дереве поиска можно найти, пройдя от корня по указателям, пока не упремся в . Процедуравозвращает указатель на найденный элемент поддерева с корнем .
Алгоритмсимметричен:

Оба алгоритма требуют времени, где — высота дерева.
Следующий и предыдущий элементы. Если— указатель на некоторый узел дерева, то процедуравозвращает указатель на узел со следующим за элементом или, если указанный элемент — последний в дереве:
Приведенная процедура отдельно рассматривает два случая. Если правое поддерево вершины не пусто, то следующий за элемент — минимальный элемент в этом поддереве и он равен. Если правое поддерево вершиныпусто, то идем от вверх, пока не найдем вершину, являющуюся левым сыном своего родителя. Этот родитель (если он есть) и будет искомым элементом. Время работы процедурына дереве высоты есть , так как мы двигаемся либо только вверх, либо только вниз. Процедурасимметрична.

Особенности работы с информацией, размещаемой на диске

Алгоритмы, работающие с Б-деревьями, хранят в оперативной памяти лишь небольшую часть всей информации (фиксированное число секторов).
Диск рассматривается как большой участок памяти, работа с которым происходит следующим образом: перед тем как работать с объектом , выполняется специальная операция-(чтение с диска). После внесения изменений в объект выполняется операция-(запись на диск).
Время работы программы в основном определяется количеством этих операций, так что имеет смысл читать/записывать как можно больше информации за один раз и сделать так, чтобы узел Б-дерева заполнял полностью один сектор диска. Таким образом, степень ветвления (число детей узла) определяется размером сектора.
Типичная степень ветвления Б-деревьев находится между и в зависимости от размера элемента. Увеличение степени ветвления резко сокращает высоту дерева, и тем самым число обращений к диску, при поиске. Например, Б-дерево степени и высоты может хранить более миллиарда ключей. Учитывая, что корень можно постоянно хранить в оперативной памяти, достаточно двух обращений к диску при поиске нужного ключа.
Считаем, что прикладная информация, связанная с ключом, хранится в том же узле дерева. На практике это не всегда удобно, и в реальном алгоритме узел может содержать лишь ссылку на сектор, где она хранится.
Определение Б-дерева. Б-деревом называют корневое дерево, устроенное следующим образом. Каждый узел содержит следующие поля:

— количество ключей, хранящихся в узле ;

,,,— сами ключи в неубывающем порядке;

— булевское значение, истинное, когда узел является листом.

Если— внутренний узел, то он содержит указатели на его детей в количестве.

У листьев детей нет, и эти поля для них не определены.

Все листья находятся на одной и той же глубине, равной высоте дерева.

Возможное число ключей, хранящихся в одном узле, определяется параметром, которое называется минимальной степенью Б-дерева.

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

Если дерево не пусто, то в корне должен храниться хотя бы один ключ. Узел, хранящий ровноключей, будет называться полным.

Ключислужат границами, разделяющими значения ключей в поддеревьях. Точнее,

ссылается на поддерево, ключи в котором меньше, чем ;

при ссылается на поддерево, ключи в котором находятся в пределах от до ;

ссылается на поддерево, ключи в котором больше, чем.

В случае, когда, у каждого внутреннего узла,или потомка, получается так называемое---дерево. Для эффективной работы с диском на практике выбирают достаточно большим. Число обращений к диску для большинства операций пропорционально высоте Б-дерева. Оценим сверху эту высоту.

Представление двоичных деревьев поиска

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

Случайные двоичные деревья поиска

Поскольку основные операции с двоичными деревьями поиска требуют времени , где — высота дерева, важно знать, какова высота "типичного" дерева. Для этого принимают какие-то статистические предположения о распределении ключей и последовательности выполняемых операций. К сожалению, в общем случае ситуация трудна для анализа. Если определить случайное двоичное дерево из различных ключей как дерево, получающееся из пустого дерева добавлением этих ключей в случайном порядке, считая все перестановок равновероятными, то можно доказать, что средняя высота случайного двоичного дерева поиска, построенного по различным ключам, равна.

Удаление элемента

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

черного дерева красный. Если мы

Предположим, что корень красно- черного дерева красный. Если мы покрасим его в черный цвет, останется ли дерево красно-черным?

Покажите, что самый длинный путь вниз от вершины к листу не более чем вдвое длиннее самого короткого такого пути.

Какое наибольшее и наименьшее количество внутренних узлов может быть в красно-черном дереве черной высоты?

Вращения — это манипуляции с красно-черными деревьями с целью восстановления RB-свойств в случае их нарушения. Их используют при реализации операцийи. Вращение представляет собой локальную операцию, при которой меняется несколько указателей, но свойство упорядоченности сохраняется.
На рис. 10.1 показаны два взаимно обратных вращения: левое и правое.

Рис. 10.1. 
Левое вращение возможно в любом узле, правый ребенок которого (назовем его ) не является листом (). После вращения оказывается корнем поддерева,— левым ребенком узла, а бывший левый ребенок— правым ребенком узла .

и правое вращения можно осуществить

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

Напишите процедурыи , реализующие левое и правое вращение в дереве относительно узла .

Пусть,и — произвольные узлы в поддеревьях,ина рис. 10.1 (справа). Как изменится глубина,и при выполнении левого вращения?

Покажите, что произвольное двоичное дерево поиска с узлами может быть преобразовано в любое другое дерево с тем же числом узлов (и теми же ключами) с помощью вращений. (Указание: сначала покажите, что правых вращений достаточно, чтобы преобразовать любое дерево в идущую вправо цепочку.)

Напишите процедуры Insert(T, x) и Delete(T, x), которые добавляют и удаляют элемент x из дерева T за время .

Разработайте алгоритм объединения двух красно-черных деревьев в одно красно-черное дерево за время .

Упражнения

Напишите процедурудля вставки элемента в АВЛ-дерево .

Напишите процедурудля удаления из АВЛ-дерева .

Напишите процедуру, удаляющую элемент из

Напишите рекурсивный вариант процедуры.

Напишите процедуру, удаляющую элемент из дерева .

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

Покажите, что если вершина двоичного дерева поиска имеет двоих детей, то следующая за ней вершина не имеет левого ребенка, а предшествующая — правого.

Структуры данных и модели вычислений

Алгебра тьюринговых программ

Для записи программ в виде формульных выражений введем обозначения для некоторых элементарных программ и операций, позволяющие строить из уже созданных программ более сложные.
Элементарными вычисляющими программами будем называть программы вида
Обозначать их будем, соответственно, символами
где .
Программы, у которых множество выходов разбито на два непустых подмножества: подмножество да-выходов и подмножество нет-выходов, назовем бинарными распознающими программами.
Элементарными распознающими программами будем считать программы вида
Обозначать такую программу будем через .
Правила композиции. Введем несколько правил, которые позволят нам из уже построенных программ создавать более сложные.

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

Если — бинарная распознающая программа, а — произвольная, то выражение
означает программу, полученную следующим образом. Все да-выходы программы соединяются с входом программы . Входом в полученную программу является вход в программу , а выходом — выходы программы и нет-выходы программы . Программы такого вида называются охраняемыми, и в таких случаях говорят, что программа охраняется программой .

Если дан набор охраняемых программ вида (если ) , то выражение вида
обозначает программу, полученную следующим образом. Да-выходы программы соединяются с входом ; нет-выходы программы
соединяются с входом . Входом в полученную программу является вход в программу , а выходом — выходы программ
и нет-выходы программы .

Если — бинарная распознающая программа, а — любая, то выражение
обозначает программу, полученную следующим образом. Да-выходы программы соединяются с входом программы . Все выходы программы соединены с входом в . Входом в полученную программу является вход в , а выходом — нет-выходы программы .

Если — бинарная распознающая программа, а — любая, то выражение
обозначает программу, полученную соединением нет-выходов программы с входом в , а выходов
— с входом в . Входом в полученную программу является вход в , а выходами — да-выходы программы .

Сокращения. Программы вида
будем сокращенно записывать в виде
а программы вида
в случае, когда — в виде .
В контексте со словами "если", "пока", "до" угловые скобки в записи элементарного распознающего оператора
будем опускать.

Частично-рекурсивные функции

Пытаясь выяснить содержание интуитивного понятия вычислимой функции, А.Черч в 1936 году рассмотрел класс так называемых рекурсивных функций, а Клини расширил его до класса частично-рекурсивных функций. В то же время впервые была высказана естественно-научная гипотеза о том, что интуитивное понятие вычислимой частичной функции совпадает с понятием частично рекурсивной функции. Эту гипотезу называют тезисом Черча. Здесь мы напомним понятие частично-рекурсивной функции и покажем, что любая частично-рекурсивная функция вычислима по Тьюрингу. Набор аргументов
обозначим через .
Функция называется суперпозицией -местных функций , и -местной функции , если
Говорят, что -местная функция
получена примитивной рекурсией из -местной функции
и -местной функции , если
Говорят, что -местная функция
получена минимизацией из -местной функции , если
Часто обозначают через .
Заметим, что суперпозиция и примитивная рекурсия, примененные к всюду определенным функциям, дают всюду определенные функции, тогда как минимизация, примененная к всюду определенной функции, может дать частичную функцию.
Числовая функция называется частично рекурсивной, если она является одной из базисных функций:
а) (при всех ),
б) (при всех ),
в)
или получена из них с помощью конечного числа применений суперпозиции, примитивной рекурсии и минимизации.
Теорема.
Любая частично-рекурсивная функция вычислима по Тьюрингу.
Доказательство теоремы заключено в следующих четырех леммах, с использованием унарного кодирования чисел.
Лемма 1 (о базисных функциях).
Базисные функции , , вычислимы по Тьюрингу.
Действительно, функцию вычисляет программа , функцию — программа , функцию — программа .
Лемма 2 (о суперпозиции).
Если функции и
вычислимы, соответственно, программами , и , то функцию
вычисляет программа:
Доказательство.
Чтобы убедиться в справедливости этого утверждения, достаточно выписать псевдослова, которые появляются на ленте после выполнения отдельных частей программы. Сначала на ленте находится псевдослово

после выполнения на ленте будет

после —

после —

и т.д.

После — после —

и, наконец, после выполнения всей программы получим

Лемма 3 (о примитивной рекурсии).

Если функции , и вычислимы соответственно программами и , то функция , полученная по схеме примитивной рекурсии, вычислима программой

Доказательство.

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

Пунктирными стрелками показаны контрольные дуги, для которых будут сформированы соответствующие индуктивные утверждения .

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

Напомним, что основное требование, предъявляемое к утверждениям , заключается в том, чтобы была возможность доказательства индуктивных шагов:

Пусть , — исходные значения аргументов из множества , тогда требуемые утверждения можно сформулировать следующим образом:

P_1 — содержимое ленты равно

— существует

такие, что содержимое ленты равно

— содержимое ленты равно

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

Лемма 4 (о минимизации).

Если функция вычислима программой , то функция , полученная из нее по схеме минимизации, вычисляется программой

Доказательство.

Представим программу, предлагаемую для вычисления функции , блок-схемой c указанными контрольными точками , , .

Пусть — исходные значения аргументов, тогда для доказательства частичной корректности предлагаемой программы можно воспользоваться следующими индуктивными утверждениями:

— содержимое ленты равно

— существуют , такие, что содержимое ленты равно

— содержимое ленты равно Требуется доказать следующие индуктивные шаги.

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

Заметим, что в доказательствах лемм 3 и 4 при рисовании блок-схемы мы несущественно отступили от текстов программ, данных в их формулировках, а при доказательстве леммы 2 не выписывали индуктивных утверждений, так как в представлении программы блок-схемой нет циклов. Обращаем внимание на то, что правильность блоков, из которых составлены программы, мы не подвергаем сомнению.

Исторические сведения

К концу XIX - началу XX века в математике накопилось некоторое количество вычислительных задач, для которых ученые, несмотря на упорные попытки, не могли предложить методов решения. Одной из таких задач является задача о разрешимости диофантова уравнения. В докладе Д.Гильберта, прочитанном на II Международном конгрессе математиков в августе 1900 года, она звучит следующим образом:
"Пусть задано диофантово уравнение с произвольными неизвестными и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах".
Неудачные попытки математиков решить эту и другие подобные задачи привели к мысли о том, что метода их решения может и не существовать. Но, чтобы доказывать подобного рода утверждения, необходимо иметь математическое определение метода, то есть для интуитивных понятий разрешимости и вычислимости необходимо иметь их формальные эквиваленты. Одним из важнейших достижений математики XX века является формирование математических понятий, которые раскрывают сущность интуитивных представлений о том, что такое метод (алгоритм) решения той или иной задачи, что такое вычислимая функция.
Важность этих понятий вытекает не только из общенаучных проблем развития математики, но также из практических задач общества, использующего вычислительную технику в производстве, экономике, инженерных расчетах и нуждающегося в адекватном представлении о возможностях вычислительных автоматов. Приведем краткие исторические сведения о возникновении теории алгоритмов.
В 1932-1935 годах А.Черч и С.К.Клини ввели понятие -определимой функции, которое сыграло важную роль в определении объема интуитивного понятия вычислимой функции.
В 1934 году К.Гедель, на основе идей Дж.Эрбрана, рассмотрел класс функций, названных общерекурсивными, а в 1936 году А.Черч и С.К.Клини доказали, что этот класс совпадает с классом -определимых функций.
В 1936 году А.Тьюринг ввел свое понятие вычислимой функции, а в 1937 году доказал, что оно совпадает с понятием -определимой функции.

В 1943 году Э.Пост, основываясь на своей неопубликованной работе 1920-1922 годов, выдвинул еще один формальный эквивалент понятия вычислимой функции.

Еще одну формулировку дает теория алгоритмов Маркова (1951 г.).

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

Еще один подход к моделированию вычислений развивается в рамках так называемого логического программирования. При таком подходе условия решаемой задачи и ее цель формулируются с помощью предложений формального логического языка. Затем осуществляется автоматический поиск доказательства цели, сопровождаемый вычислением неизвестных в задаче величин.

Заметим, что разрабатываемые в настоящее время алгоритмические языки, составляющие математическое обеспечение современных вычислительных устройств, также можно использовать для определения понятия вычислимости. Более того, можно проследить тесную связь между упомянутыми здесь теоретическими моделями вычислений и реальным программированием. Так, -исчисление Черча является прообразом функционального программирования, реализованного в известном программистам языке ЛИСП, разработанном в 1961 году Дж.Маккарти, а модель Поста содержит идеи, реализованные в операторных языках типа Фортран, Алгол. Методы логического программирования реализованы в настоящее время в нескольких версиях языка Пролог.

Однако реальные языки программирования из-за своей громоздкости и избыточности выразительных средств малопригодны для теоретического анализа понятия вычислимости. Отметим также модели вычислительных устройств, получившие название РАМ (Равнодоступная Адресная Машина) и РАСП (Равнодоступная Адресная Машина С хранимой Программой).Эти модели в большей степени, чем, например, модель Тьюринга, отражают структуру современных вычислительных устройств.

Методика доказательства правильности программ

Рассматриваемая методика предназначена для доказательства правильности алгоритмов, представленных в виде графов, вершинам которых поставлены в соответствие операторы над памятью, а дугам — переходы от оператора к оператору. Одну из вершин назовем входной, ей соответствует оператор, с которого начинается выполнение алгоритма, а выходных вершин может быть несколько. Считаем, что входная и выходная вершины помечены, соответственно, входящей и выходящей стрелками. Такие представления алгоритмов называют блок-схемами. Доказать правильность алгоритма — это значит доказать следующее утверждение:

Если входные данные удовлетворяют входному условию, то алгоритм через конечное число шагов завершает работу и выходные данные удовлетворяют требуемому выходному условию.

На практике такое утверждение часто разбивают на два.

Если входные данные удовлетворяют входному условию и алгоритм через конечное число шагов завершает работу, то выходные данные удовлетворяют требуемому выходному условию.

Если входные данные удовлетворяют входному условию, то алгоритм через конечное число шагов завершает работу.

Алгоритм, для которого доказано утверждение 1, называется частично правильным или частично корректным. Если же доказаны утверждения 1 и 2, то алгоритм называется правильным или корректным.
Заметим, что когда доказательство утверждения 2 представляет непреодолимые трудности, то ограничиваются доказательством утверждения 1. Таковы, например, итерационные алгоритмы, для которых неизвестна область сходимости. В таком случае, если алгоритм в приемлемое время завершает свою работу, то правильность ответа гарантируется.
Остановимся на доказательстве частичной корректности. Методика заключается в следующем:

Для контроля над ходом вычислений выбираются так называемые контрольные дуги. К числу контрольных обязательно относят входную и все выходные дуги, а также некоторое количество других дуг, так, чтобы в граф-схеме алгоритма оказались "разрезанными" все циклы.

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

Для каждой пары , контрольных точек, для которых в блок-схеме имеется путь из в , минующий другие контрольные точки, выбираются все такие пути, и для каждого выбранного пути доказывается утверждение (индуктивный шаг): "Если при очередном проходе через точку выполнялось индуктивное предположение и если реализуется рассматриваемый путь, то при достижении точки
будет выполняться условие ".

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

Начальное математическое обеспечение

Приведем несколько программ, для которых введем обозначения, и в дальнейшем будем использовать их для построения более сложных программ. Они будут составлять начальное математическое обеспечение программирования.
В таблице приведены их схемы в предположении, что алфавит
состоит из символов ; а символ
обозначен через .
Кроме того, считаем, что и — произвольные псевдослова над алфавитом ; , — слова в алфавите ; — произвольный символ из ; — слово, полученное из слова путем изменения порядка символов на противоположный; .
Программы и , описанные в начале таблицы, используются в последующих программах.
Сдвиг головки влево до ближайшего пробела.Обозначение

Вход
Выход
Программа

Сдвиг головки вправо до ближайшего пробела.Обозначение

Вход
Выход
Программа

Копирование -го слова.Обозначение

Вход
Выход
Программа

Удаление буквы со сдвигом. Обозначение

Вход
Выход
Программа

Циклический сдвиг слов. Обозначение

Вход
Выход
Программа

Удаление -го слова. Обозначение

Вход
Выход
Программа

Об измерении алгоритмической сложности задач

При практическом решении многих интересных задач с помощью вычислительных автоматов существенную роль играет время работы и объем памяти, которые требуются для их решения соответствующими алгоритмами. Упомянутые характеристики называются, соответственно, временной и пространственной сложностью алгоритма.
Временной и пространственной сложностью задачи в классе алгоритмов (или автоматов) называется время и объем памяти, необходимые "лучшему" в данном классе алгоритму (автомату) для решения рассматриваемой задачи.
Вопрос о нахождении сложностных характеристик задач весьма труден. Трудности, как правило, связаны с логической сложностью рассматриваемых задач и обилием алгоритмов в любом универсальном классе.
Рассмотрим некоторые подробности на примере тьюринговых программ. Будем считать, что задача представлена двухместным словарным предикатом над некоторым алфавитом и заключается в нахождении по заданному слову
слова такого, что истинно.
Слово будем считать решением задачи при входном слове . Чтобы пустоту слова трактовать как отсутствие решения, наложим на следующие ограничения:

Результат работы тьюринговой программы на входном слове
обозначим , считая равным выходному слову.
Будем говорить, что тьюрингова программа решает задачу , если на любом входном слове она останавливается через конечное число шагов и .
Через обозначим число элементарных тьюринговых команд, которые будут выполнены программой от начального момента до момента остановки при работе на входном слове . Если при входном слове программа выполняет бесконечное число шагов, то считаем .
Величину будем называть временем работы программы на слове . В большинстве случаев эта величина существенно зависит от длины слова , поэтому представляет интерес функция , где максимум вычисляется по всем словам длины .
Заметим, что эта ситуация не является общей; в некоторых случаях величина не зависит от длины слова . Например, пусть требуется определить четность числа, представленного в двоичном коде. Для этого достаточно посмотреть на его младший разряд.

Важным и интересным для практики является вопрос о верхних и нижних оценочных функциях для времени работы конкретных алгоритмов.

Заметим, что получение нижних нетривиальных оценок каждый раз представляет собой сложную математическую задачу. Известно, например, что временная сложность задачи распознавания симметрии слова тьюринговыми программами оценивается снизу функцией , где — длина слова, а — некоторая константа.

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

Если для задачи имеется полиномиальная от

верхняя оценочная функция, то говорят, что разрешима в полиномиальное время.

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

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

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

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

Тьюрингова модель переработки информации

Описанная ниже модель несущественно отличается от модели, предложенной Тьюрингом.
Представление информации (модель памяти). Будем считать, что информация представляется словами, то есть конечными последовательностями, составленными из букв конечного алфавита, и записывается на неограниченной в обе стороны ленте, разделенной на ячейки. Слово записывается в идущих подряд ячейках по одной букве в ячейке.
В ячейку может быть ничего не записано, в этом случае говорим, что ячейка содержит пробел. Для обозначения пробела используем символ . Конечную последовательность, составленную из символов алфавита и символа пробела, называем псевдословом. Считаем, что слева от первой буквы псевдослова и справа от последней записаны пробелы, кроме того, один из символов псевдослова будем помечать стрелкой. Множество всех конечных последовательностей символов из алфавита обозначается через .
Если псевдослово имеет вид , где , , то называем его первым словом, — вторым и т.д. Слова могут быть и пустыми. Пустые слова не занимают места на ленте. При необходимости будем считать, что между двумя идущими подряд пробелами записано пустое слово.
Поскольку на ленте в каждый момент времени будет находиться не более чем конечное число символов, отличных от пробела, постольку для любого
в псевдослове будет определено его -е слово, возможно пустое.
Преобразователь информации. Преобразователь информации можно представить как некоторое устройство, снабженное головкой, обозревающей в каждый момент времени одну из ячеек ленты, которое по заранее намеченному плану (программе) может выполнять операции следующего вида:

напечатать один из символов алфавита в обозреваемой ячейке;

сдвинуть головку по ленте на одну ячейку влево;

сдвинуть головку по ленте на одну ячейку вправо;

ничего не делать до следующего такта времени.

Определение программы. Программу преобразования информации будем представлять в виде ориентированного графа, вершины которого помечены символами из множества , а дуги — символами из множества так, что разным дугам, выходящим из одной вершины, приписаны разные символы.
Одна вершина графа выделена в качестве входной, на рисунках будем отмечать ее входящей стрелкой. Предполагаем, что .

Действие программы осуществляется следующим образом. В начальный момент головка вычислительного устройства обозревает одну из ячеек ленты. Просматривается входная вершина программы. Если ей приписан символ , или , то головка вычислителя сдвигается по ленте на одну ячейку соответственно вправо, влево или остается на месте; если же ей приписан символ из алфавита или , то этот символ печатается в обозреваемой ячейке, а старое содержимое ячейки при этом стирается. После того как выполнено действие, соответствующее вершине , в графе отыскивается выходящая из дуга, помеченная той буквой, которая находится в данный момент в обозреваемой ячейке. Затем выполняется действие, соответствующее вершине, в которую ведет найденная дуга. Процесс продолжается до тех пор, пока не будет достигнута вершина, из которой не выходит дуга, помеченная буквой, обозреваемой в данный момент. Если такой момент не наступает, то программа работает бесконечно долго.

Вершину , для которой найдется хотя бы одна буква из , не используемая в качестве метки на дугах, выходящих из , будем называть выходной. Выходные вершины будем помечать выходящими "в никуда" стрелками, помеченными буквами, не использованными на других дугах.

Согласно данному описанию, программу можно задать как набор: в котором — множество вершин графа;

— алфавит символов, печатающихся на ленте; — входная вершина (); — отображение в ; — частичное отображение

в .

Чтобы не загромождать чертежи большим количеством стрелок и надписей при изображении программ, мы используем следующие соглашения. Если из вершины в вершину

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

Пример.

Пусть и на ленте записано псевдослово

, где , , а стрелка над символом показывает положение головки в начальный момент. Рассматривая слово

как двоичную запись натурального числа , требуется составить программу, которая на ленте оставляет псевдослово

, являющееся двоичной записью числа . Нетрудно увидеть, что поставленную задачу решает программа, представленная на рис. 11.1.

Рис. 11.1. 

Здесь входная и выходная вершины помечены, соответственно, входящей и выходящей стрелками.

Универсальная тьюрингова программа и пример невычислимой функции

В этом параграфе речь пойдет об универсальной тьюринговой программе , которая может имитировать любую программу, работающую над фиксированным алфавитом . Эта программа , получив на входе псевдослово, содержащее в определенном виде код произвольной программы и псевдослово , должна оставить на ленте код программы
и псевдослово — результат работы программы на псевдослове .
Читатель, построивший универсальную программу, может считать себя изобретателем компьютера.
Пусть — множество всех функций из в таких, что каждая из них определена в точке 0 и вычислима программой, состоящей не более чем из тьюринговых команд. Рассмотрим функцию , где максимум берется по всем функциям из . Очевидно, всюду определена и монотонна. Более того, справедлива
Теорема.
Для любой всюду определенной вычислимой функции существует такое, что при любом
выполняется неравенство .
Действительно, пусть — произвольная всюду определенная функция из в , тогда очевидно, что функция будет также всюду определенной и вычислимой. Пусть в унарном коде ее вычисляет программа , состоящая из команд. Рассмотрим программу , которая сначала записывает на ленте число , а затем работает как . Очевидно, что она состоит из команд и вычисляет некоторую функцию .
По определению и имеем . Используя монотонность функции , получим при всех , следовательно, , . Отсюда следует, что при
выполняется неравенство , что и требовалось доказать.
Следствие.
Функция невычислима, так как она растет быстрее, чем любая вычислимая функция.
Заметим, что при любом фиксированном
значение можно попытаться вычислить путем перебора всех программ длины и определения для каждой из них времени работы до момента остановки или доказательства ее незавершаемости. Но вопрос о завершаемости программ в общем виде алгоритмически неразрешим. Уточним основные моменты этого утверждения.
Пусть — тьюрингова программа, работающая в алфавите , и пусть — слово в алфавите , кодирующее программу (на деталях кодирования не останавливаемся).
Программа называется самоприменимой, если при подаче ей на вход ее собственного кода она через конечное число шагов остановится, в противном случае программа называется несамоприменимой. Пусть — множество кодов самоприменимых программ.
Теорема.
Множество алгоритмически неразрешимо.
Доказательство.
Пусть — алгоритмически разрешимо. Тогда существуют две программы и такие, что останавливается только на словах из , а — только на словах из .
Тогда, если на собственном коде остановится, то
по определению , но по определению .
Если же на своем коде не остановится, то по определению , а по определению
. Итак, в любом случае имеем противоречие.
Еще одним примером алгоритмически неразрешимого множества является множество кодов программ, которые останавливаются при пустом входе. Легко показать, что если бы было разрешимым, то множество
тоже было бы разрешимым.

Вычисление числовых функций

Чтобы вычислять значения числовых функций с помощью тьюринговых программ, необходимо выбрать способ кодирования на ленте аргументов и значений функции. Мы рассматриваем функции из в , где — множество натуральных чисел, включая , а .
Значения функции и ее аргументов будем записывать в бинарном, унарном или каком-либо ином коде, для чего нам потребуется, соответственно, алфавит , и т.д. Значения аргументов перед вычислением должны быть представлены на ленте в виде псевдослова где — код -го аргумента .
После вычисления содержимое ленты должно иметь вид где — код значения функции при заданных значениях аргумента.
Упражнения

Составить программу, перерабатывающую псевдослово
в псевдослово , где — бинарный, а — унарный код некоторого числа из .

Составить программу сложения и умножения чисел в унарном и бинарном кодах.

Составить программу для удвоения числа в бинарном и унарном кодах.

Составить программу деления нацело натуральных чисел в унарном коде.

Вычислимость и разрешимость

Упорядоченный набор из слов в алфавите
называется -местным набором над . Множество всех -местных наборов над обозначим через . Любое подмножество множества называется -местным словарным отношением.
Любое, возможно частичное, отображение
называется -местной словарной функцией. Область определения функции обозначается через .
Результатом работы программы на входном псевдослове называется псевдослово , которое появляется на ленте в момент остановки программы; если программа работает бесконечно, то результат не определен.
Программу, которая в процессе работы над любым псевдословом
не сдвигает головку левее пробела, расположенного слева от -го слова псевдослова , будем называть -программой.
Словарное -местное отношение называется полуразрешимым, если существует -программа , которая останавливается в точности на всех псевдословах, имеющих вид где .
Словарное -местное отношение называется разрешимым, если и полуразрешимы (под здесь понимается множество .
Словарная -местная функция называется вычислимой по Тьюрингу, если существует программа такая, что где и , в противном случае результат не определен.
Вычислимые по Тьюрингу функции уместно было бы назвать полувычислимыми, а полувычислимые с разрешимой областью определения — вычислимыми, но это противоречит установившимся традициям.

Структуры данных и модели вычислений

Абак

Абак наряду с машинами Тьюринга является одной из простейших универсальных моделей вычислений. Это числовая модель; элементами информации являются целые неотрицательные числа.
Память представляет собой потенциально бесконечный набор ячеек, каждая ячейка может содержать любое целое неотрицательное число. Считается, что ячейки пронумерованы числами .
Исполняющее устройство способно выполнять всего две операции (элементарные команды) над числами, это прибавление (increment) и вычитание (decrement) единицы из указанного в команде числа. Команды имеют вид и , где
— номер ячейки. Поскольку в каждом конкретном алгоритме может быть использовано лишь конечное число ячеек и с номерами ячеек никаких операций не производится, мы будем обозначать их в примерах для наглядности отдельными буквами, возможно, с использованием индексов.
Программа (алгоритм) — это ориентированный граф, вершинам которого приписаны элементарные команды указанного выше вида. Из каждой вершины, помеченной командой вида , выходит одна дуга в вершину со следующей командой. Из каждой вершины, помеченной командой вида , выходят две дуги. Одна из них помечается знаком "" и ведет в вершину, помеченную командой, которая должна выполняться следующей в случае, если перед ее выполнением в ячейке находилось число, отличное от нуля. Вторая дуга помечается знаком "" и ведет в вершину, помеченную командой, которая должна выполняться следующей в случае, если перед ее выполнением в ячейке находилось число нуль. Одна из вершин графа помечается как входная, в нее ведет дуга "из ниоткуда", выходных вершин может быть несколько.
Несмотря на простоту этой модели вычислений, она "эквивалентна по силе" любой из изучавшихся универсальных моделей вычислений и относительно нее можно сформулировать тезис, аналогичный тезису Черча, который может выглядеть следующим образом. Любая интуитивно вычислимая функция может быть вычислена на абаке. При этом, конечно, надо условиться о том, где располагаются входные аргументы и куда следует поместить результат (значение вычисляемой функции).
Примеры программ. В рассмотренных ниже примерах операция обозначается для краткости через , а операция — через . Основные операции изображены кружками. Прямоугольниками изображены операции, для которых в предыдущих примерах построены алгоритмы. Знак "" на соответствующих дугах опущен. Сформулируйте инварианты циклов во всех рассмотренных ниже примерах.

Программа
В языках программирования эта операция обычно является элементарной. На абаке это действие можно выполнить следующей программой:

Программа

Программа

Программа

Программа

Программа

Программа

Алгорифмы Маркова

Термин "алгорифм" является устаревшим вариантом современного термина "алгоритм", однако по отношению к алгоритмам Маркова принято использовать авторский вариант.
Информация, обрабатываемая алгорифмом Маркова, представляется словом в некотором фиксированном алфавите .
Алгорифм (программа) представляется последовательностью пар слов в алфавите . Пары, составляющие алгорифм, называются также подстановками и записываются в виде где , — слова в алфавите , причем может быть пустым (обозначаем ). Программа имеет вид
Некоторые подстановки помечаются восклицательным знаком и называются заключительными.
Функционирование. Во входном слове ищется фрагмент, совпадающий с левой частью первой подстановки. Если фрагмент находится, то самый левый такой фрагмент во входном слове заменяется на ее правую часть, в противном случае рассматривается вторая подстановка из алгорифма и так далее. Вычисления заканчиваются, когда ни одна из левых частей подстановок не является фрагментом обработанного к данному моменту слова или когда выполнена заключительная подстановка. Заметим, что описанный таким образом процесс может оказаться и бесконечным.
Замечание.
Алгорифмы Маркова составляют теоретическую основу системы программирования, использующую язык РЕФАЛ.
Пример.
Алфавит . Здесь запятая не является символом алфавита.
Рассмотрим программу Убедитесь в том, что она входное слово вида переработает в слово , в котором число символов "1" — такое же, как во входном слове. Можно считать, что программа выполняет сложение натуральных чисел, представленных в унарной системе счисления.
Пример.
Алфавит .
Программа
Рассмотрим протокол вычислений на входном слове . Справа указаны применяемые подстановки. Если считать, что во входном слове закодирована задача умножения в унарной системе счисления, то в выходном слове получен ответ 6.
Докажите, что программа дает верный ответ при любом корректном входном слове.

Примеры неразрешимости

Функцию назовем вычислимойна абаке, если существует программа , которая, получив в некоторой, заранее обусловленной ячейке значение аргумента , а в остальных ячейках — нули, через конечное число шагов остановится, и в ячейке будет находиться .
Проблема построения невычислимой функции известна как "проблема усердного бобра". Пусть — абак-программа и
— номер некоторой ячейки. Определим величину следующим образом. Если в начальный момент все ячейки содержат число 0 и программа через конечное число шагов останавливается, то равно числу в момент остановки. Если же программа работает бесконечно, то считаем . Величину назовем -продуктивностью программы .
Обозначим через множество всех абак-программ, состоящих из команд. Определим функцию как максимум по всем программам из и ячейкам . Очевидно, эта функция определена при всех натуральных значениях аргумента и строго монотонна.
Лемма.
Для любого натурального числа выполняется неравенство
Для доказательства достаточно рассмотреть программу, которая сначала запишет в ячейку , затем прибавит к ней раз 1, скопирует содержимое ячейки в ячейку и добавит к ней содержимое ячейки . Очевидно, после выполнения такой программы в ячейке будет число , а подсчет числа команд показывает, что их будет . Наличие такой программы (рис. 12.1) доказывает требуемое неравенство.

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

Итак, предположение о вычислимости функции привело к противоречию.

Рис. 12.2. 
На рис. 12. 2 команда повторяется раз, общее количество команд в программе , в ячейке
вычисляется .
Рассмотрим произвольную инъективную нумерацию программ, то есть нумерацию, ставящую в соответствие каждой программе ее номер , причем разным программам ставятся в соответствие разные номера. Программу назовем самоприменимой относительно ячейки , если она, получив в ячейке свой номер, а в остальных ячейках — нули, через конечное число шагов завершает вычисления.
Рассмотрим функцию , определяемую следующим образом:

, если является номером некоторой самоприменимой относительно ячейки программы,

, в противном случае.

Докажем, что функция не вычислима никакой программой. Предположим, что вычисляется программой , которая, получив в ячейке число , остановится через конечное число шагов и в ячейке оставит . Рассмотрим программу , изображенную на рис. 12.3.

Рис. 12.3. 
Если самоприменима относительно ячейки , то , поэтому, когда проработает программа , в ячейке
будет записана 1 и остальная часть программы — будет работать без остановки. Следовательно, — не самоприменима относительно .
Если же не самоприменима относительно ячейки , то , следовательно, когда проработает программа , в ячейке будет записан 0 и тогда остальная часть программы — сразу же завершит работу. Следовательно, — самоприменима относительно .
Итак, предположение о вычислимости функции в любом случае приводит к противоречию.

Равнодоступная адресная машина

Равнодоступная адресная машина (РАМ) — это числовая модель вычислительного устройства. Эта модель является наиболее близкой из рассмотренных к реальным вычислительным машинам и позволяет наиболее реалистично применять теоретические оценки сложности алгоритмов к реальным вычислениям.
Память машины состоит из регистров (ячеек). Каждый регистр имеет адрес и может содержать произвольное число. Регистр с номером 0 называется сумматором.
Программа — последовательность пронумерованных команд. Команда имеет вид
Коды операций
Операнд может быть одного из трех видов
где — натуральное число.
Содержимое регистра с номером обозначим через . Значение операнда определяется в зависимости от его вида следующим образом.
При оценке сложности алгоритмов используют в зависимости от обстоятельств разные веса команд. При работе с малыми числами и малым числом регистров реалистичным оказывается так называемый равномерный вес, при котором каждая команда требует единицу времени. При работе с большими числами и большим количеством регистров используется так называемый логарифмический вес команды, при котором время выполнения команды зависит как от значения операнда, так и от значения его адреса.
При определении веса команды используется функция , выражающая длину записи числа
Основание логарифма при получении асимптотических оценок не имеет существенного значения.
Вес операнда определяется в зависимости от его вида следующим образом:
Таблица 12.1. КомандаДействиеЛогарифмический вес

	очередное число
	очередное число
	печать
	переход на команду с номером	1
	переход на команду с номером , если
	переход на команду с номером , если
	конец вычислений	1

Например, команда имеет логарифмический вес
Временная сложность программы определяется как сумма весов всех выполненных команд с учетом их многократного выполнения.
Емкостная сложность программы определяется как сумма по всем регистрам длин максимальных чисел, побывавших в этих регистрах.
Пример.
Рассмотрим вычисление :
Этот псевдокод легко может быть заменен РАМ-программой, представленной в таблице 12.2.

Таблица 12.2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

Емкостная сложность программы при равномерном критерии равна , при логарифмическом — .

Структуры данных и модели вычислений

Автоматное задание языков

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

Диаграмма автомата изображена на рис. 13.1

Рис. 13.1. 
Недетерминированные конечные автоматы без
-переходов. Недетерминированным конечным автоматом без -переходов над алфавитом называется набор
где — множество состояний, — алфавит, — начальное состояние , — множество финальных состояний и
— переходная функция. Такой автомат также можно представить нагруженным ориентированным мультиграфом (диаграммой). Отличие в том, что дуги теперь могут быть помечены только символами алфавита .
Язык , порождаемый таким автоматом , состоит из всех слов, которые можно прочитать, двигаясь, начиная со стартового состояния , по ребрам и читая приписанные им символы. Чтение заканчивается в любом из финальных состояний множества не обязательно при первом попадании туда.
Детерминированные конечные автоматы. Детерминированным конечным автоматом над алфавитом называется набор где — множество состояний, — алфавит, — начальное состояние , — множество финальных состояний и — переходная функция.
Такой автомат также можно представить нагруженным ориентированным мультиграфом (диаграммой). Отличие от недетерминированного автомата состоит в том, что из каждого состояния выходит ровно одна дуга, помеченная конкретной буквой алфавита .

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

Теорема.

Классы языков, задаваемые детерминированными конечными автоматами, недетерминированными конечными автоматами с -переходами, недетерминированными конечными автоматами без -переходов, регулярными выражениями совпадают.

Доказательство.

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

Синтез. Регулярное выражение представляется автоматом где , алфавит — произволен, — начальное состояние, — множество финальных состояний и переходная функция задается соотношениями

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

задается соотношениями и , .

Регулярное выражение представляется автоматом , где , — начальное состояние, — множество финальных состояний и переходная функция

задается соотношениями

и .

Для регулярного выражения , где

и — регулярные выражения, можно построить задающий автомат следующим образом. Пусть автомат

задает , а автомат задает . Не уменьшая общности, можно считать, что и — одноэлементные и что , . Положим , где , — новые состояния, и поясним построение автомата на языке диаграмм. Состояние соединим дугами со стартовыми состояниями , автоматов , и пометим их символом . Состояния и автоматов , соединим дугами с новым состоянием и также пометим их символом . Начальным состоянием построенного автомата объявим , а финальным — .


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

автомата .

Для регулярного выражения , где — регулярное выражение, можно построить задающий автомат следующим образом. Пусть автомат

задает . Опять не уменьшая общности, считаем, что — одноэлементное и что . Добавляем к множеству два новых состояния — и . Соединяем -переходами пары состояний , , и .

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

Таким образом, задача синтеза решена.

Избавление от -переходов. Покажем, как по недетерминированному автомату

с -переходами построить недетерминированный автомат ) без -переходов, такой, что . Назовем -путем путь в диаграмме автомата , возможно пустой, порождающий пустое слово. Обозначим через

множество состояний, достижимых из с помощью некоторого -пути.

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

Детерминизация.Покажем, как по недетерминированному автомату без -переходов построить детерминированный автомат , такой, что . Положим , , , а

определим следующим образом: Нетрудно видеть, что построенный таким образом автомат

удовлетворяет условию .

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

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


где , если , , если . Решив систему, берем в качестве ответа значение переменной .

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

Рис. 13.2. 

Решение. Запишем систему уравнений Заметим, что при записи системы мы упростили обозначения переменных, используя индексы.

Из четвертого уравнения получаем . Подставляя полученное выражение во все остальные уравнения, получим систему из трех уравнений: Перепишем ее в стандартном виде:

Из третьего уравнения получаем и подставляем в остальные уравнения:

Преобразуем второе уравнение к стандартному виду

и получаем из него

Наконец, получаем ответ

Основные понятия и обозначения

Алфавит — конечное множество абстрактных символов, как правило, упорядоченное в так называемом алфавитном порядке.
Слово (в алфавите ) — конечная последовательность символов (алфавита).
Длина слова— количество вхождений символов в слово. Длина слова , обычно обозначается .
Пустое слово — пустая последовательность, то есть последовательность, не содержащая ни одного символа. Пустое слово, соблюдая традиции, часто обозначают греческой буквой , полагая при этом, что она не является символом рассматриваемого алфавита.
Слово длины () можно отождествить с элементом декартова произведения (, в котором
сомножителей, обозначаемого . При
имеем , состоящее из одного пустого слова; не путать с пустым множеством, обозначаемым знаком .
Замечание.
При отождествлении элемента декартова произведения со словом полагаем, что слово составлено из входящих в него символов в соответствующем порядке.
Множество всех слов в алфавите обозначают

Множество всех непустых слов в алфавите обозначают
Сверхслово (в алфавите ) — бесконечная последовательность символов (алфавита ).
Формальный язык (в алфавите ) — множество слов (в алфавите ).
Конкатенация слов— двухместная операция над словами, заключающаяся в приписывании второго слова к первому. Результат конкатенации слов и обозначается .
Начальный фрагмент слова , имеющий длину , называется префиксом длины
слова , обозначается .
Конечный фрагмент слова , имеющий длину , называется суффиксом длины слова , обозначается .
Если , то префикс и суффикс называются собственными. Заметим, что при нашем определении пустое слово
будет и собственным префиксом, и собственным суффиксом любого слова .
Операции над формальными языками. Поскольку формальные языки являются множествами, то к ним применяются обычные теоретико-множественные операции: объединение, пересечение, дополнение (до множества всех слов в рассматриваемом алфавите). Кроме перечисленных, применяются специфические операции — это конкатенация двух языков и итерация языка.
Результатом конкатенации языков и
является язык , обозначаемый также . Результат конкатенации
экземпляров языка обозначим через .
Результатом итерации языка является язык . Заметим, что
и поэтому при любом .
Замечание. При работе с формальными языками операцию объединения часто обозначают знаком "". В следующих тождествах используется именно это соглашение.
Основные тождества. Пусть , , — произвольные формальные языки над некоторым фиксированным алфавитом, тогда справедливы следующие тождества:

Применение конечных автоматов в программировании

Задача. По заданному регулярному выражению над алфавитом найти в тексте
наименьший префикс, содержащий слово из .
Решение. Строится регулярное выражение и для него — недетерминированный конечный автомат с -переходами. Пусть это будет автомат . Если при чтении текста построенным автоматом мы приходим в финальное состояние, то это означает, что мы прочитали префикс текста , содержащий слово из языка .
Алгоритм, моделирующий работу недетерминированного конечного автомата с -переходами на входном слове .
Оценим трудоемкость приведенного алгоритма. Пусть , тогда тело цикла
оценивается как , а тело цикла " " как и весь алгоритм имеет трудоемкость .
Анализируя алгоритм построения автомата с -переходами по регулярному выражению , легко установить следующие свойства:

, где — длина выражения
с учетом скобок и символов операций;

;

;

.

Учитывая приведенные свойства, можем теперь оценить алгоритм, моделирующий работу автомата , величиной .
Рассмотрим теперь задачу, частную по отношению к рассмотренной выше, полагая, что вместо регулярного выражения задано одно слово-образец .
Задача. Требуется найти вхождение заданного слова-образца
в слово-текст
или установить, что такого вхождения нет.
Определение.
По данному образцу определим функцию
следующим образом: — наибольший префикс слова , являющийся суффиксом слова .
Очевидно, что .
Утверждение 4.
Для любой строки и любого символа
.
Действительно, предположим, что
и , тогда , а будет префиксом и суффиксом строки , причем , что противоречит определению .
Утверждение 5.
Пусть , тогда для любого символа
.
Действительно, по предыдущему утверждению, , поэтому значение не изменится, если от строки оставить последние символов, а именно . Построим по слову-образцу конечный автомат где , , , а переходную функцию определим следующим образом:
Для построенного автомата, очевидно, будет справедливо следующее утверждение.
Утверждение 6.
Прочитав текст , автомат
будет находиться в состоянии .
Алгоритм вычисления функции переходов:

Время работы этого алгоритма .

Пример.

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

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

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

Рис. 13.3. 


Время работы этого алгоритма .

Пример.

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

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

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

Рис. 13.3. 

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

Слова являются собственными префиксами и суффиксами слова .

Последовательность

обрывается на пустом слове.

Любой префикс слова , являющийся его суффиксом, находится в последовательности

Пример.

Пусть . Тогда

Определение.

Функцией откатов для слова называют функцию , определяемую соотношением , где — префикс длины слова .

В нашем примере функция задается следующей таблицей:

Алгоритм Кнута-Морриса-Пратта построения функции откатов для слова :

Для разъяснения работы алгоритма рассмотрим ситуацию, возникшую при обработке слова на шаге . К этому моменту вычислены значения при :

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

Регулярные выражения

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

— регулярное выражение;

— регулярное выражение;

— регулярное выражение, если ;

— регулярное выражение, если
и — регулярные выражения;

— регулярное выражение, если и — регулярные выражения;

— регулярное выражение, если — регулярное выражение.

Регулярное выражение задает язык в соответствии со следующими правилами:

— пустой язык;

— язык, состоящий из одного пустого слова;

— язык, состоящий из одного однобуквенного слова ;

;

;

.

Пример.
Рассмотрим регулярное выражение
над алфавитом . Язык состоит из слов, в которых на нечетных местах стоит символ , а на четных или .
Замечание 1.
В регулярных выражениях вместо знака "" часто используют знак "".
Замечание 2.
Если дополнить правила построения регулярных выражений еще двумя правилами

— регулярное выражение, если
и — регулярные выражения,

— регулярное выражение, если — регулярное выражение, и , а ,

то получим так называемые расширенные регулярные выражения. Здесь дополнение берется до множества всех слов в алфавите . Если не использовать дополнение, то получим полурасширенное регулярное выражение.
Как увидим в дальнейшем, использование расширенных регулярных выражений не расширяет класса регулярных языков.
Замечание 3.
Используя описанную выше интерпретацию регулярных выражений, мы будем вместо соотношения
писать .

Решение уравнений в словах

Рассмотрим уравнение вида , где и — формальные языки над некоторым алфавитом .
Теорема.
Если , то уравнение
имеет единственное решение . Если , то
будет решением уравнения при любом .
Доказательство.
Пусть и — решение, тогда, подставляя его в уравнение, получим
Продолжая выполнять подстановки, видим, что при любом
выполняется равенство

(1)

Покажем сначала, что . Действительно, пусть , тогда при некотором значении получим и из (1) при таком значении
получаем .
Осталось показать, что . Действительно, пусть , тогда при любом
Но так как , то при достаточно больших значениях
каждое слово в множестве будет длиннее слова
и, следовательно, , но тогда при таких
Следовательно, . Итак, мы показали, что если — решение, то оно задается формулой , то есть является единственным. Тот факт, что
на самом деле — решение, проверяется простой подстановкой. Второе утверждение теоремы предоставляем доказать читателю.
Замечание.
Если в уравнении под и
понимать регулярные выражения, то в случае
его единственным решением будет регулярное выражение .
В случае, когда содержит , уравнение имеет бесконечно много решений вида , но здесь под можно понимать не только регулярные выражения, но и выражения в каком-либо формализме, задающие произвольный язык. Часто в таком случае интересуются наименьшим по включению решением, так называемой "наименьшей неподвижной точкой".
Системы линейных уравнений с регулярными коэффициентми.
Под стандартной системой понимают систему вида
где , — регулярные выражения, — переменные ().
Решением системы называется набор формальных языков, которые при подстановке вместо соответствующих переменных в уравнения обращают их в равенства. Удобно на решение смотреть как на отображение , которое каждой переменной ставит в соответствие язык . Решение называется наименьшей неподвижной точкой системы, если для любого другого решения выполняются соотношения при .
Теорема.
Каждая стандартная система уравнений имеет единственную неподвижную точку.
Доказательство.
Действительно, нетрудно видеть, что отображение , определяемое по формулам , где пересечение берется по всем решениям (, является искомой неподвижной точкой системы.
Решаются такие системы уравнений методом исключения неизвестных. Если, например, , то первое уравнение можно представить в виде , где , записать его решение описанным выше способом в виде и подставить в остальные уравнения. Получим систему с меньшим числом неизвестных и так далее.

Способы задания формальных языков

Прежде всего, для задания формального языка может подойти любое математически корректное определение множества слов в заданном алфавите. Однако если иметь в виду задание, при котором возможно алгоритмическое решение вопроса о принадлежности слова языку, то нужны средства более ограниченные. Наиболее общим из конструктивных способов задания языков является способ, использующий так называемые формальные грамматики.
Формальной грамматикой для порождения формального языка в алфавите называется набор где — алфавит терминальных (основных) символов; — алфавит нетерминальных (вспомогательных) символов, ; — стартовый символ, ; — конечный набор правил вывода. Каждое правило вывода имеет вид , где , — слова в объединенном алфавите , причем содержит хотя бы один символ из алфавита .
Правило применимо к слову , если
является фрагментом слова . Результатом применения этого правила к слову называется слово , полученное заменой любого фрагмента
в слове
на слово .
Если — результат применения некоторого правила к слову , то пишем .
Если , то пишем .
Язык , порождаемый грамматикой , определяется следующим образом: Другими словами, — множество слов в основном алфавите, которые могут быть получены из стартового символа путем конечного числа применений правил грамматики.
Классификация Хомского:

Грамматики типа — это грамматики, не имеющие ограничений на вид правил.

Грамматики типа — это грамматики, в которых правила имеют вид , где — нетерминальный символ, а , , — слова в объединенном алфавите. Слова , называются контекстом правила. Эти грамматики (и языки, порождаемые ими) называются контекстными, так как в описанном правиле символ заменяется словом , если находится в контексте , .

Грамматики типа — это грамматики, в которых правила имеют вид , где — нетерминальный символ, а — непустое слово в объединенном алфавите. Эти грамматики (и языки, порождаемые ими) называются контекстно-свободными.

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

Известно, что класс языков, задаваемых грамматиками типа , является классом рекурсивно перечислимых языков, не совпадающим с классом рекурсивных языков. На языке теории алгоритмов это означает, что не существует алгоритма, который по любой грамматике типа 0 и любому слову отвечает на вопрос "". С другой стороны, существует алгоритм, который, получив на входе грамматику
и слово , ответит "да", если , в противном случае он либо ответит "нет", либо будет работать бесконечно.
Классы языков, задаваемых грамматиками типа , , , являются классами рекурсивных языков.
Альтернативный способ задания формальных языков — их описание с помощью различных видов автоматов. Одним из простейших классов языков, имеющих большое прикладное значение, является класс регулярных языков, допускающих описание и с помощью конечных автоматов, и с помощью аналитических выражений.

Структуры данных и модели вычислений

Язык предикатов

Теоретические исследования математических моделей вычислений играют важную роль в формировании технологии использования компьютерной техники. Каждая такая модель вносит свой вклад в реальную технологию. Развитие технологии в обход теоретических исследований часто приводит к неуклюжим, трудным для восприятия и, в конечном счете, малопроизводительным видам деятельности.
Исследования универсальных методов доказательства в рамках логики предикатов дают повод для разработки на их основе новых языков программирования. Опыты, проведенные в 70-х годах прошлого века, показали перспективность использования этих методов в реальных технологиях автоматической переработки информации.
В настоящее время в рамках так называемого логического программирования ведутся исследования по использованию различных стратегий поиска доказательств утверждений, сформулированных в языке предикатов, и, в частности, известного в математической логике метода резолюций. Эти стратегии реализованы в настоящее время в нескольких версиях языка Пролог (Эрити Пролог, Турбо Пролог и др.).
Формулы языка предикатов строятся из предикатных и функциональных символов с помощью логических связок, кванторов и некоторых вспомогательных символов. Набор предикатных и функциональных символов заранее не фиксируется, а выбирается из содержательных соображений, связанных с желанием строить высказывания о тех или иных объектах или их свойствах и отношениях между ними. С каждым предикатным символом связывается натуральное число, его арность (число аргументов).
"Строительные материалы", из которых конструируются формулы и предложения языка предикатов:

Логические связки и кванторы:

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

Вспомогательные символы: прямые и круглые скобки и запятая.

Предикатные и функциональные символы.

Замечания

Предикатные символы используются для обозначения предложений, в которых некоторые слова заменены переменными, так что при замене переменных именами конкретных объектов получаются высказывания об этих объектах, которые можно оценить при определенных обстоятельствах как истинные или ложные. Каждое такое предложение называется высказывательной формой, а количество различных переменных, входящих в такое предложение, — ее арностью или местностью. Например, предложение "Река

является притоком реки " — двухместная форма, которая при замене переменной на собственное имя "Волга" превращается в одноместную форму. "Река является притоком реки Волга". А если еще и переменную

заменить именем "Ока", то получим истинное высказывание. Если же переменную заменить именем "Енисей", то — ложное.

При имеем дело с конкретным высказыванием.

Функциональные символы используются для обозначения отображений (функций).

Нульместные функции называются также константами.

Основными конструкциями языка предикатов являются термы и формулы.

Правила образования термов

Любая переменная или константа является термом.

Если — функциональный -местный символ, а — термы, то выражение

является термом.

Замечания

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

Если в терме нет переменных, то он интерпретируется как имя некоторого объекта, если же переменные есть, то терм удобно рассматривать как схему для образования имени. Например, — терм, который при замене переменной константой превращается в терм , являющийся именем вполне конкретного числа, хотя и нетрадиционным. Под выражением мы понимаем здесь функциональный символ, хотя и состоящий из трех латинских букв.

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

Аналогичное замечание справедливо и для двухместных предикатов.

Правила образования формул

Если — -местный предикатный символ, а — термы, то выражение является формулой (атомарной).

Если и — формулы, то выражения , , и являются формулами.

Если — формула, а — переменная, то выражения , являются формулами.

Замечания

В правиле формула называется областью действия соответствующего квантора, а все вхождения переменной

в атомарные подформулы формулы называются связанными.

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

Формула, не имеющая переменных со свободными вхождениями, называется предложением.

Формулы, в которых имеются свободные вхождения переменных, трактуются как высказывательные формы, а предложения — как высказывания, истинностная оценка которых зависит от интерпретации входящих в них предикатных и функциональных символов в соответствии со смыслом логических связок и кванторов.

Пример.

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

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

— точка, являющаяся серединой отрезка ,

— точка, симметричная точке

относительно некоторой точки,

— предикат, означающий равенство точек и .

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

Очевидно, что это утверждение истинно.

Рис. 14.1. 

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

— произведение чисел ,

— число, обратное числу ,

— "".

Рассматриваемая нами формула является теперь утверждением о том, что для любых двух чисел из нашего универсума выполняется равенство

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

Примеры. Пусть и — одноместные предикатные символы.

— тождественно истинная формула.

— тождественно ложная формула.

— истинность этой формулы зависит от интерпретации предикатных символов и .

Если в формуле есть свободные переменные, то она получает конкретное истинностное значение при означивании этих переменных.

Формула называется выполнимой, если она истинна хотя бы при одной интерпретации.

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

Например, формулы

не являются логически равносильными, а формулы

логически равносильны.

Логическую равносильность формул будем обозначать знаком , например,

Заметим, что в этом выражении фигурирует не одна формула, а две, соединенные знаком логической равносильности.

Элементы языка Пролог

Основным элементом языка Пролог является терм. Термы строятся из переменных, атомов, чисел и функторов с использованием круглых скобок.
Переменная — это цепочка (слово), составленная из букв, цифр и символа подчеркивания, начинающаяся с большой буквы или символа подчеркивания. Если переменная используется однажды, то вместо нее можно использовать так называемую анонимную переменную, состоящую из одного символа подчеркивания.
Атом — это цепочка, составленная из букв, цифр и символа подчеркивания, начинающаяся с маленькой буквы или с большой буквы, но тогда в одинарных кавычках. Последний способ удобен, если атом является собственным именем. Иногда атомы строятся и из специальных знаков, но мы не будем их использовать при первоначальном знакомстве.
Числазаписываются традиционным образом. Числа с плавающей запятой в обычных применениях Пролога используются редко из-за ошибок округления.
Функтор синтаксически совпадает с атомом.
Терм— это либо переменная, либо атом, либо число, либо выражение вида где — функтор, а — термы.
Для некоторых специальных функторов, например знаков арифметических операций, отношений сравнения и других, в Прологе, как в традиционной математике, используется инфиксная форма записи. Например, выражение рассматривается как терм с функтором и двумя аргументами и .
Среди термов ввиду особой важности выделяются термы для представления списков. Канонически список представляется двухместным термом, первым аргументом которого является головной элемент списка, а вторым — его хвост, то есть список, полученный из исходного удалением головного элемента. Функтором в такой записи часто используется символ точка. Альтернативным представлением списка является выражение вида или , где — головной элемент, а — хвост списка. Допустимо также выражение вида .
Важным инструментом в языке Пролог является унификация термов с помощью подстановок. Такую унификацию мы применяли выше в примерах на доказательство методом резолюций. Сейчас более подробно рассмотрим понятие унификации.

Подстановкой называется набор пар , где — переменные, а — термы.

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

Пусть — еще одна подстановка. Композиция двух подстановок и

определяется следующим образом: Подстановка может быть вычислена следующим образом. Составим из подстановок и последовательность

и проведем следующие две операции:

Если некоторое совпадает с некоторым , то вычеркиваем пару .

Если , то вычеркиваем пару .

Пример.

Пусть . Рассмотрим последовательность и по первому правилу вычеркиваем пары и , затем по второму правилу — пару . В результате получим

Подстановка называется унификатором термов , , если .

Наиболее общим унификатором термов ,

называется подстановка , такая, что любой другой их унификатор представляется в виде .

Пример.

Для термов , унификатором будет подстановка Будет ли она наиболее общим унификатором?

Пример.

Для термов и

наиболее общим унификатором будет подстановка . Результатом унификации будет терм

Некоторые сведения из математической логики

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

(1)

где — предикатные символы соответствующей арности; , — индивидные переменные.
Известно, что по любому предложению в предваренной нормальной форме можно построить так называемое сколемовское предложение . Для этого избавляются от кванторов существования следующим образом. Пусть ( — самое левое вхождение квантора существования в рассматриваемую формулу и перед ним расположены кванторов общности с переменными . Выбираем новый -местный функциональный символ , вхождение удаляем из формулы, а каждое вхождение переменной заменяем термом . Аналогичным образом избавляемся и от других кванторов существования. В результате получим сколемовскую формулу для исходной формулы .
Так, для формулы (1) соответствующая сколемовская формула будет иметь вид

(2)

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

Равносильность по выполнимости формулы и соответствующей ей сколемовской формулы может быть использована следующим образом. Предположим, мы хотим доказать, что формула является логическим следствием формул и . Это сводится к доказательству невыполнимости формулы или соответствующей ей сколемовской формулы, что технически осуществить оказывается проще.

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

(3)

Упомянутый выше метод резолюций основывается на единственном правиле вывода, называемом правилом резолюции, которое заключается в следующем. Из двух формул вида

и

в соответствии с правилом резолюции выводится формула

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

Из математической логики известно, что не существует алгоритма, который по любому множеству формул-гипотез логики предикатов и еще одной формуле отвечал бы на вопрос, является ли

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

Различные версии языка Пролог базируются на использовании так называемых хорновских клаузальных формул. Хорновскими называются формулы, являющиеся дизъюнкциями атомарных формул и/или их отрицаний, причем атомарная часть без отрицания может быть в такой формуле не более чем одна. Рассмотрим пример такой формулы:

(4)

Ее можно представить в виде

(5)

Эта формула воспринимается Прологом так, как если бы все ее переменные были связаны квантором общности. Восстанавливая кванторы, имеем

(6)

Учитывая, что не входит в правую часть импликации, формулу (6) можно переписать в виде

изменив область действия квантора .

В Прологе принято формулы, аналогичные формуле (5), записывать в виде

(7)

меняя местами левую и правую части импликации и вместо знака конъюнкции ставя запятую.

Формулу (7) Пролог воспримет как указание на то, что для доказательства истинности надо найти некоторое значение

и доказать, что истинны , , . Такие формулы принято называть правилами.

Если в хорновской клаузальной формуле отсутствуют атомарные части с отрицанием, то такая формула называется фактом. Если в хорновской клаузальной формуле отсутствует атомарная часть без отрицания, то такая формула называется запросом. Программой в Прологе называется набор фактов и правил.

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


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

(3)

Упомянутый выше метод резолюций основывается на единственном правиле вывода, называемом правилом резолюции, которое заключается в следующем. Из двух формул вида

и

в соответствии с правилом резолюции выводится формула

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

Из математической логики известно, что не существует алгоритма, который по любому множеству формул-гипотез логики предикатов и еще одной формуле отвечал бы на вопрос, является ли

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

Различные версии языка Пролог базируются на использовании так называемых хорновских клаузальных формул. Хорновскими называются формулы, являющиеся дизъюнкциями атомарных формул и/или их отрицаний, причем атомарная часть без отрицания может быть в такой формуле не более чем одна. Рассмотрим пример такой формулы:

(4)

Ее можно представить в виде

(5)

Эта формула воспринимается Прологом так, как если бы все ее переменные были связаны квантором общности. Восстанавливая кванторы, имеем

(6)

Учитывая, что не входит в правую часть импликации, формулу (6) можно переписать в виде

изменив область действия квантора .

В Прологе принято формулы, аналогичные формуле (5), записывать в виде

(7)

меняя местами левую и правую части импликации и вместо знака конъюнкции ставя запятую.

Формулу (7) Пролог воспримет как указание на то, что для доказательства истинности надо найти некоторое значение



    Программирование: Языки - Технологии - Разработка

• Программирование
  
• Технологии программирования
  
• Разработка программ
  
• Работа с данными
  
• Методы программирования
  
  
• IDE интерфейс
  
• Графический интерфейс
  
• Программирование интерфейсов
  
• Отладка программ
  
• Тестирование программ
  
  
• Программирование на Delphi
  
• Программирование в ActionScript
  
• Assembler
  
• Basic
  
• Pascal
  
  
• Perl
  
• VBA
  
• VRML
  
• XML
  
• Ada
  
  
• Lisp
  
• Python
  
• UML
  
• Форт
  
• Языки программирования
  

---

---