Математика	Физика	Химия	Биология	Техника и технологии
	Методы упорядочения информации в цифровых системах. Папернов А. А., П о д ы-м о в В. Я. Главная редакция физико-математической литературы изд-ва «Наука», М., 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 Цена книги: 150руб.
Назад	Заказ	На главную страницу