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

выполнения цикла до строки 14, то по предположению индукции найдется такой список qu . q, что (4.6) было справедливо для / на предыдущем этапе. Кроме того, в строке 4 обязательно

Случай 1. i нет в L={qx, q, . . ., q. В строках 9, 10 могло произойти разбиение нескольких блоков. Для каждого такого блока B[qj], lrk (т. е. j=qr), добавим в L индекс блока, образованного в строке 8. Благодаря строке 11 список L по-прежнему будет состоять только из индексов, входящих в ОЖИДАНИЕ. Если сам блок В[1] не разбит, то ВЦ] и множество блоков с индексами из L все еще образуют множество, безопасное для текущего разбиения, так что (4.6) удовлетворяется. Если же блок В[1] разбит, надо также добавить в L индекс q, выбранный в строке 8, когда /=/. Следовательно, множество В[/] U U Blr] будет безопасно для текущего разбиения.

Случай 2. i находится в L={qi, q2.....q}. Без потери общности будем считать, что i=qi. Рассуждение проводится почти так же, как в случае 1, но в конце рассматриваемой итерации строк 4-14 может не входить в ОЖИДАНИЕ. Мы знаем, что каждый блок В текущего разбиения будет либо подмножеством множества f-{B[qi]), либо не будет с ним пересекаться. Пусть Т= =В{1] и и В[г], где список L модифицирован, как в случае 1. Если

Bf-iBlqi]), то, разумеется, В П/-ЧЛ=0- Если В п f{Blqi])= = 0, то аналогично случаю 1 можно доказать, что В f]f~ (Т)=0 или Bf-ЦТ).

Наконец, когда алгоритм 4.5 заканчивает работу, множество ОЖИДАНИЕ должно быть пусто. Следовательно, из (4.6) вытекает, что для каждого / блок ВЦ] безопасен для окончательного разбиения. □

Теорема 4.8. Алгоритм 4.5 правильно вычисляет грубейшее разбиение множества S, совместимое с п и f.

Доказательство. Лемма 4.7 показывает, что выход л алгоритма 4.5 совместим с я и /. Надо доказать, что разбиение я грубо, насколько возможно. Простая индукция по числу блоков, разбиваемых в строках 9, 10, показывает, что каждое такое разбиение, сделанное алгоритмом, необходимо для совместимости. Оставляем эту индукцию в качестве упражнения. □

Теперь мы должны детально исследовать реализацию алгоритма 4.5, чтобы показать, что время его работы составляет О (п logn), где я=5. Основным при оценке времени работы будет демонстрация того, что цикл в строках 6-14 можно выполнить за время, пропорциональное ЦОБРАЩЕНИЕЦ. Наша первая задача - эффективно найти подходящее множество чисел / в строке 6. Нам понадобится такой массив БЛОК, что БЛОК[/] - индекс блока, содержащего /. Начальное состояние массива БЛОК можно по-



строить за О (п) шагов, после строки 9 скорректировать его за время, не большее того, что тратится на формирование списка B[q] в этой строке. Следовательно, поскольку нас интересует только порядок временной сложности, можно не учитывать время, затрачиваемое на работу с массивом БЛОК.

С помощью массива БЛОК легко построить список ЛСПИСОК чисел /, необходимых в строке 6, за 0(ОБРАЩЕНИЕ) шагов. Для каждого элемента а, входящего в ОБРАЩЕНИЕ, индекс блока, содержащего а, добавляем в ЛСПИСОК, если его там еще нет. Для каждого / хранится счетчик числа элементов, входящих в ОБРАЩЕНИЕ, которые входят также и в Blj]. Если этот счетчик достигнет величины то В[/] ОБРАЩЕНИЕ и / удаляется

из списка ЛСПИСОК.

Используя БЛОК, можно для каждого /, входящего в ЛСПИСОК, построить также список ПЕРЕСЕЧЕНИЕ[/1, в который войдут все целые числа, принадлежащие обоим множествам B[j] и ОБРАЩЕНИЕ.Чтобы быстро удалить элементы списка ПЕРЕСЕЧЕНИЕ!;] из Blj] и добавить их в Blq], надо поддерживать списки ВЦ], в дважды связанном виде, т. е. с указателями как к следующей, так и к предыдущей компонентам.

Строки 9 и 10 требуют OdlBllH) шагов. Для данного выполнения for-цикла суммарное время, затрачиваемое на нахождение подходящих чисел / и на выполнение строк 7-10, составляет 0(ОБРАЩЕНИЕ1). Кроме того, легко видеть, что тест в строках 12-14, если его выполнять должным образом, занимает OdlBflH) времени, так что общее время есть 0(ОБРАЩЕНИЕ).

Осталось рассмотреть строку 11. Чтобы быстро сказать, входит ли / в ОЖИДАНИЕ, образуем другой массив В ОЖИДАНИИ[/]. Начальное состояние В .ОЖИДАНИИ можно построить за О (п.) шагов и без труда корректировать его в строках 11-14. Таким образом, мы доказали следующую лемму.

Лемма 4.8. ior-цикл в строках 6-14 на рис. 4.35 можно реализовать за 0(ОБРАЩЕНИЕ) ишов.

Доказательство. В силу изложенного выше. □ Теорема 4.9. Алгоритм 4.5 можно реализовать за время О (пlogn).

Доказательство. Рассмотрим условия, при которых блок, содержащий целое число s и не представленный в множестве ОЖИДАНИЕ, может попасть туда. В строке 1 это может случиться лишь один раз. В строке И это произойти не может; даже если sBlq], поскольку тогда s было бы в Blj] еще раньше, а индекс / уже входил в ОЖИДАНИЕ. Если это случилось в строках 13 и 14, то число S находится в блоке, размер которого не больше половины размера того блока, куда оно входило в тот предыдущий момент, когда индекс множества, содержащего s, попал в ОЖИДА-



НИЕ. Отсюда можно заключить, что индекс множества, содержащего S, попадает в ОЖИДАНИЕ не больше l+log« раз. Следовательно, S не может быть в блоке i, который выбирался в строке 4 более чем l+logn раз.

Допустим, что на каждый элемент s из B[i] каждый раз налагается штраф, пропорциональный /~i(s), так что сумма всех штрафов равна сложности выполнения цикла в строках 6-14. Тогда существует такая постоянная с, что за одно выполнение цикла элемент S штрафуется не более чем на c\\f- (s). Как мы уже показали, элемент s не может попасть в выбираемый список BU] более чем 0(log«) раз, так что суммарный штраф, налагаемый на него, составляет О (/~ (s) log«). Так как сумма 2,11/" должна равняться

п, то общая сложность всех выполнений for-цикла есть 0(«logn). Легко видеть, что сложность остальной части алгоритма 4.5 есть О (п); теорема доказана. □

Алгоритм 4.5 имеет несколько приложений. Одно из важных приложений - минимизация числа состояний конечного автомата. Дан конечный автомат M-(S, I, б, So, F) и требуется найти эквивалентный ему автомат М с наименьшим числом состояний. Для каждого состояния s и входного символа а обозначим через б (s, а) очередное состояние автомата. Вначале все состояния автомата М можно разбить на множество F допускающих состояний и множество S - F недопускающих состояний. Задача минимизации числа состояний автомата М эквивалентна нахождению грубейшего разбиения я множества S, совместимого с начальным разбиением {f, S - f} и такого, что если состояния s и / находятся в одном блоке разбиения я, то состояния 6(s, а) и б(/, а) также находятся в одном блоке автомата М для каждого входного символа а.

Единственное отличие этой задачи от задачи, решаемой алгоритмом 4.5, состоит в том, что б - отображение из Sx / в S, а не из S в S. Однако можно трактовать б как множество {бд, ба,, . . . . . ., ба„} функций на S, где б„ - сужение функции б на а.

Алгоритм 4.5 легко модифицировать так, что он справится с этой более общей задачей, помещая в множество ОЖИДАНИЕ пары (г, б„). Каждая пара (i, б„) состоит из индекса i некоторого блока разбиения и функции б, по которой проводится разбиение. Вначале 0ЖИДАНИЕ = {(1, б„)г = 1 или 2 и ag/}, поскольку начальное разбиение {F, S - jF} состоит из двух блоков. Всякий раз, когда блок В[]] разбивается на ВЦ] и B[q], каждая допустимая функция ба спаривается с j п q. Остальные детали оставляем в качестве упражнения.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 [58] 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0044