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

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

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

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

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

Операция фиксации. Фиксация -й цифры

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

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

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

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

Инкрементирование 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)

(7)