Файл: Зубов В.С. Математическое обеспечение цифровых вычислительных машин и систем учеб. пособие.pdf

- w -

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

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

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

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

Значения управляющих полей двух сопоставляемых записей обоз­

начим через УШ/Уи УП2 //7 ,т .е . как элементы вектора-управляю­

щего слова; L - номер ранга сравниваемых полей. Тогда обычная

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

УП2 Щ th en lifUilihen ynift] >УП2 & 1 else y n ifik УП2 /т1)e lse ify a iM t УП2[2khea(if B&]then ш М > т 2 Щ еЫ т -\р ]< . тп

... УП2[Ь) thenl if BlHiihen ynipij >УР2Melse УШ/hj<ffl2[til)e/se tru e

Докажем, что при конечной длине последовательности запи­ сей её можно преобразовать в правильную последовательность

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

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

Утверждение I . Если для двух записей последовательности

3 [i] к 31J] существует инверсия, то на отрезке последователь-

- 4 f -

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

Доказательство проведём от противного: воли между всеми

смежными записями указанного отрезка выполняется отношение

порядка, то в силу транзитивности отношения порядка оно вы­ полнится и между 3/</ и 3 [j] , что противоречит нашему условии.

Утверждение 2. Перестановка в последовательности (перену­

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

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

Из утверждений I и 2 вытекает, что многократное осуществ­ ление проверки правильности следования лишь смежных записей

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

и их перенумераций в случае инверсий приводит к правильной по­ следовательности после конечного числа таких актов, поскольку число инверсий в конечной последовательности - конечно.

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

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

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

ределёняости. Сокращение множества неопределённости в резуль­ тате сопоставления отражает уменьшение неопределённости сис­

темы. В конечном итоге, после сокращения множества неопределен­

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

Итак, при сопоставительном упорядочении происходит снятие

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

Оценим максимальную величину средней информационной цен­

ности, а черезS * - полученвого. Обозначим мощность подмножес­ тву, совместимого с результатом сравнения, т .е . содержащего текущую последовательность, черезS j , а мощность подмножества,

- 4 3 -

её не содержащего, через«?2 " В силу равновозможносш всех со ­ стояний обобщённой последовательности правильная последовате­

среднего числа сопоставлений, в процессе трансформации последо­

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

tygfcb

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

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

ментов, поэтому условимся использовать треугольную матрицу ,

состоящую из элементов, лежащих выше главной диагонали, со­

хранив за ней прежнее название матрицы инверсий. В этой мат­

рице L- я строка отражает выполнение отношения порядка [ -й

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

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

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

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

Матрица инверсий содержит избыточную информацию, так как содержание еб отдельных элементов взаимосвязано (эта взаимо­

связь проистекает из транзитивности отношения порядка). Пол-

2

ный объём информации матрицы равен (Л - П ) / 2 , где /7 - чис­

ло записей в последовательности (её длина). Математическое

ожидание (МО) числа единиц в матрице для случайной последо­ вательности равно (Л 2 - л )/4 (наличие и отсутствие инверсий

равновероятно). Эта же величина является оценкой МО числа перенумераций, если производится перенумерация лишь смежных записей, что свойственно примитивным сопоставительным алго­ ритмам. МО числа сопоставлений в-них не может иметь меньшей оценки , чем для перенумераций, и в большинстве простейших алгоритмов соответствует объёму информации матрицы (сопос­ тавьте с ранее полученной нижней грань» среднего их числа).

Прежде, чем рассмотреть основы построения более произ­

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

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

- 4 5 -

жуточныш между ними I элементами, мы можем ожидать устране­

Назовём перенумерацию, связанную с взаимным обменом мес­ тами в последовательности двух её элементов, обменом. Опре­

делим как вставку -исключение перенумерацию путём перестанов­ ки одного элемента в последовательности с одного её места на другое с соответствующим изменением позиций элементов, лежа­

щих в промежутке между ними. Обмен просто реализуется в опис­ ках типа А и Б и затруднительно - в списках типа В и Г. Нап­

ротив, вставка-исключение проще реализуется в списке типа В.

венно.

Действительно, нулевое содержимое элементов некоторого

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

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

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

- 4 7 -

оодержимым которых может бить либо 0 , либо I : для исходной последовательности наличие и отсутствие инверсии между за­ писями равновероятно, а упорядочение сегментов могло приве­ сти лишь к перестановке элементов, показанных завком X,Обо­ значим 1~к через р , а к -1 через 1 . Если некоторым образом осуществить полное упорядочение записей, входящих в оба се ­ гмента ("объединение" сегментов), то все символы X окажутся нулями, т .е . тем самым в среднем будет устранено ещё Р '%J2

инверсий. Объединение сегментов наиболее экономично реали­ зуется по методу 3 магазинов; два магазина содержат записи исходных, сегментов, третий - результирующего. В верхушках исходных магазинов находятся начальные записи ещё не рассмо­ тренной’ части сегмеишрв (в первый момент - начальные записи сегментов). В верхушку результирующего магазина в правильней последовательности загружаются записи результирующего сег­ мента. Определение очередной загружг емой записи осуществля­ ется сравнением записей в верхушках исходных магазинов, в

результате чего выясняется, что одна из,.них ( "выигравшая"

запись) должна следовать раньше. Применяя свойство транзи­ тивности, заключаем, что все не рассмотренные записл^долх-

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

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

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