Методы упорядочения информации в цифровых системах. Папернов А. А., П о д ы-м о в В. Я. Главная редакция физико-математической литературы изд-ва «Наука», М., 1973, 384 стр. Книга посвящена вопросу организации в памяти цифровых систем информации, предназначенной для поиска. Приводятся алгоритмы формирования информации в упорядоченные массивы и деревья. Рассмотрению конкретных алгоритмов предшествует общая теория упорядочения, позволяющая изложить все конкретные алгоритмы с единой точки зрения, выявить критерии их количественной оценки и сравнения друг с другом, предложить методы анализа и синтеза таких алгоритмов. Приводятся и обосновываются рекомендации по использованию алгоритмов упорядочения в зависимости от характеристик информации, подлежащей упорядочению, ограничений, накладываемых на используемые ресурсы, т. е. на объемы памяти \и быстродействие, характеристик временных потоков обновления и устаревания информации, а также потоков запросов на поиск.
Книга предназначена для инженеров и математиков, занятых разработкой информационно-поисковых систем и программированием информационно-логических задач в цифровых системах.
Табл. 11. Илл. 1. Библ. 86 назв.
ОГЛАВЛЕНИЕ
Предисловие
ГЛАВА I
ПОИСК ИНФОРМАЦИИ В ЗУ ЦИФРОВЫХ МАШИН
§ 1.1. Определение процедуры поиска. Обзор характерных условий поиска .....
§ 1.2. Способы организации информации об одном
объекте..........13
§ 1.3. Структура информации о множестве объектов ...........15
§ 1.4. Основные методы поиска формуляров в
списках..........18
§ 1.5. Алгоритмы дихотомического поиска в массивах ...........30
• 1.6. Примеры поисковых систем. Словари . . 39
§ 1.7. Примеры поисковых систем. Таблицы функций ...........43
ГЛАВА2
ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ УПОРЯДОЧЕНИЯ
§ 2.1. Определение и основные характеристики
процедуры упорядочения ..... 49
§ 2.2. Характеристики состояния информации в
массиве..........60
§ 2.3. Характеристики операторов упорядочения 80
§ 2.4. Некоторые способы частичной оптимизации
процедур упорядочения ...... 82
ГЛАВА 3
МЕТОДЫ СЛИЯНИЯ
§ 3.1. Предпосылки метода.......88
§ 3.2. Оператор слияния двух упорядоченных под-массивов в один........91
§ 3.3 Оператор слияния нескольких упорядоченных подмассивов в один......102
§ 34 Упорядочение случайного массива при использовании процедуры слияния .... 109
§ 3.5. Процедуры . упорядочения слиянием при
ограничении резерва памяти.....118
§ 3.6. Способы аппаратной реализации метода
слияния..........133
ГЛАВА 4
ПРОЦЕДУРЫ УПОРЯДОЧЕНИЯ
С ПРЕДЕЛЬНОЙ ЭКОНОМИЕЙ ПАМЯТИ
§ 4.1. Предпосылки метода......149
§ 4.2. Характеристики оператора упорядочения
последовательностей методом вставки . . 152
§ 4.3. Особенности процедуры упорядочения при чередовании кратных и чередовании некратных шагов.........170
§ 4.4. Изменение степени неупорядоченности в процессе выполнения процедуры .... 174
§ 4.5. Сложность выполнения процедуры упорядочения ...........
§ 4.6. Блок-схема алгоритма упорядочения . . 183
ГЛАВА 5
УПОРЯДОЧЕНИЕ ДЕЛЕНИЕМ МАССИВА
§ 5.1. Предпосылки метода....... 187
§ 5.2. Оператор разделения массива .... 190
§ 5.3. Основные характеристики оператора . . 193
§ 5.4. Разделение по первому элементу массива 197
§ 5.5. Организация процедуры упорядочения . . 203
§ 5.6. Выбор из массива элемента для разделения 208
§ 5.7. Упорядочение с использованием элементов
эквивалентного массива ...... 229
/ Л А В А 6
ПОРАЗРЯДНОЕ УПОРЯДОЧЕНИЕ
§ 6.1. Характеристики процедуры поразрядного
упорядочения ........ 233
§ 6.2. Организация процедуры поразрядного упорядочения ....... . . 239
§ 6.3. Упорядочение по группе разрядов . . . 244
ГЛАВА 7
МЕТОДЫ УПОРЯДОЧЕНИЯ ИНФОРМАЦИИ ВО ВНЕШНИХ ЗУ
§ 7.1. Специфические особенности внешнего упорядочения ..........257
§ 7.2. Основные операторы процедуры внешнего
упорядочения слиянием ...... 259
§ 7.3. Метод упорядочения с несколькими выходными лентами.......268
§ 7.4. Метод упорядочения с чередованием операторов формирования и слияния . . . +.
§ 7.5. Метод упорядочения с одной выходной лен-
тпй
ТОЙ
271 274
§ 7.6. Оценка сложности процедуры упорядочения с одной выходной лентой ....
284 § 7.7. Упорядочение на одной ленте .... 287
ГЛА В А 8
ОРГАНИЗАЦИЯ ИНФОРМАЦИИ В ВИДЕ ДВОИЧНЫХ ДЕРЕВЬЕВ
§ 8.1. Определение двоичного дерева и основная
терминология.........291
§ 8.2. Свойства упорядоченных двоичных дег
ревьев...........296
§ 8.3. Алгоритмы поиска и формирования в
двоичном дереве..... , . 302
§ 8.4. Некоторые статистические характеристики
нелерестраиваемых деревьев . . . . 311
Г Л А В А 9
МЕТОДЫ ПЕРЕСТРОЙКИ ДВОИЧНЫХ ДЕРЕВЬЕВ
§ 9.1. Постановка вопроса о перестройке деревьев
в процессе их формирования .... 320
§ 9.2. Метод перестройки неполных узлов дерева 324
§ 9.4. Метод преобразования внутренних цепочек
дерева..........342
ГЛАВА 10
ВОПРОСЫ СОВМЕСТНОЙ ОПТИМИЗАЦИИ ПРОЦЕССОВ ПОИСКА И УПОРЯДОЧЕНИЯ
§ 10.1. Организация поиска и упорядочения в
статическом массиве......363
§ 10.2. Поиск и упорядочение в динамическом
массиве..........373
Приложение, Сравнительные характеристики
основных методов упорядочения . . . 376
Литература...........380