\input style
МЕСТАХ, ГДЕ НА КАРТЕ ОТПЕРФОРИРОВАНЫ ОТВЕРСТИЯ, ВХОДЯТ В КОНТАКТ С РТУТЬЮ 
НА НИЖНЕЙ ПАНЕЛИ.

т РЕЗУЛЬТАТЕ ЗАМЫКАНИЯ СООТВЕТСТВУЮЩЕЙ ЦЕПИ ПОКАЗАНИЕ СВЯЗАННОГО С 
НЕЙ ЦИФЕРБЛАТА ИЗМЕНЯЕТСЯ НА 1 И, КРОМЕ ТОГО, ОДНА ИЗ 26 КРЫШЕК 
СОРТИРОВАЛЬНОГО ЯЩИКА ОТКРЫВАЕТСЯ. т ЭТОТ МОМЕНТ ОПЕРАТОР ОТПУСКАЕТ 
ПРЕСС, КЛАДЕТ КАРТУ В ОТКРЫТОЕ ОТДЕЛЕНИЕ И ЗАКРЫВАЕТ КРЫШКУ. яО 
СООБЩЕНИЯМ, КАК-ТО ЧЕРЕЗ ЭТУ МАШИНУ ПРОПУСТИЛИ 19071 КАРТУ ЗА ОДИН 
6.5-ЧАСОВОЙ РАБОЧИЙ ДЕНЬ; В СРЕДНЕМ ПРИМЕРНО 49 КАРТ В МИНУТУ! (ёРЕДНИЙ 
ОПЕРАТОР РАБОТАЛ ПРИМЕРНО ВТРОЕ МЕДЛЕННЕЙ.) 

эАСЕЛЕНИЕ ПРОДОЛЖАЛО НЕУКЛОННО РАСТИ, И ПЕРВЫЕ 
ТАБУЛЯТОРЫ-СОРТИРОВЩИКИ ОКАЗАЛИСЬ НЕДОСТАТОЧНО БЫСТРЫМИ, ЧТОБЫ 
СПРАВИТЬСЯ С ОБРАБОТКОЙ ПЕРЕПИСИ 1900~Г., ПОЭТОМУ їОЛЛЕРИТ ИЗОБРЕЛ ЕЩЕ 
ОДНУ МАШИНУ, ЧТОБЫ ПРЕДОТВРАТИТЬ ЕЩЕ ОДИН КРИЗИС В ОБРАБОТКЕ ДАННЫХ. 
хГО НОВОЕ УСТРОЙСТВО (ЗАПАТЕНТОВАННОЕ В 1901 И 1904 ГГ.) ИМЕЛО 
АВТОМАТИЧЕСКУЮ ПОДАЧУ КАРТ И ВЫГЛЯДЕЛО, В СУЩНОСТИ, ПОЧТИ ТАК ЖЕ, КАК 
СОВРЕМЕННЫЕ КАРТОЧНЫЕ СОРТИРОВАЛЬНЫЕ МАШИНЫ. шСТОРИЯ РАННИХ МАШИН 
їОЛЛЕРИТА С ИНТЕРЕСНЫМИ ПОДРОБНОСТЯМИ ИЗЛОЖЕНА ыЕОНОМ ¤. ЄРУСДЕЛЛОМ 
В The Development of Punch Card Tabulation (Washington: U. S. Bureau of the 
Census, 1965); СМ. ТАКЖЕ СООБЩЕНИЯ СОВРЕМЕННИКОВ їОЛЛЕРИТА: 
{\sl Columbia College School of Mines Quarterly\/}, {\bf 10} (1889), 238--255; 
{\sl J. Franclin Inst.\/}, {\bf 129} (1890), 300-- 306;
{\sl The Electrical Engineer\/}, {\bf 12} (Nov. 11, 1891). 521--530; 
{\sl J. Amer. Statistical Assn.\/}, {\bf 2} (1891), 330--341;{\bf  4} (1895), 365; 
{\sl J. Royal Statistical Soc.\/}, {\bf 55} (1892), 326--327; 
{\sl Alegemeines Statistisches Archiv\/}, {\bf 2} (1892), 78--126;
{\sl J. Soc. Statistique de Paris\/}, {\bf 33} (1892), 87--96;
U.~S. Patents 395781 (1889), 685608 (1901), 777209 (1904). їОЛЛЕРИТ И 
ДРУГОЙ БЫВШИЙ СЛУЖАЩИЙ сЮРО ПЕРЕПИСИ фЖЕЙМС яАУЭРС В ДАЛЬНЕЙШЕМ 
ОСНОВАЛИ КОНКУРИРУЮЩИЕ КОМПАНИИ, КОТОРЫЕ В КОНЦЕ КОНЦОВ ВОШЛИ 
СООТВЕТСТВЕННО В КОРПОРАЦИИ IBM И Remington Rand.

ёОРТИРОВАЛЬНАЯ МАШИНА їОЛЛЕРИТА---ЭТО, КОНЕЧНО, ОСНОВА МЕТОДОВ 
ПОРАЗРЯДНОЙ СОРТИРОВКИ, ИСПОЛЬЗУЕМЫХ В ЦИФРОВЫХ ¤ть. т ЕГО ПАТЕНТЕ 
УПОМИНАЕТСЯ, ЧТО ЧИСЛОВЫЕ ЭЛЕМЕНТЫ, СОДЕРЖАЩИЕ ДВА СТОЛБЦА, ДОЛЖНЫ 
СОРТИРОВАТЬСЯ "ПО ОТДЕЛЬНОСТИ ДЛЯ КАЖДОГО СТОЛБЦА", НО ОН НЕ ГОВОРИТ, 
КАКОЙ СТОЛБЕЦ (ЕДИНИЦ ИЛИ ДЕСЯТКОВ) ДОЛЖЕН РАССМАТРИВАТЬСЯ ПЕРВЫМ. 
фАЛЕКО НЕ ОЧЕВИДНАЯ ИДЕЯ СОРТИРОВКИ СНАЧАЛА ПО СТОЛБЦУ ЕДИНИЦ БЫЛА, 
ПО-ВИДИМОМУ, ОТКРЫТА КАКИМ-ТО НЕИЗВЕСТНЫМ ОПЕРАТОРОМ И ПЕРЕДАНА 
ОСТАЛЬНЫМ (СМ. П.~5.2.5); ОНА ИМЕЕТСЯ В САМОМ РАННЕМ СОХРАНИВШЕМСЯ 
РУКОВОДСТВЕ IBM ПО СОРТИРОВКЕ (1936~Г.). яЕРВЫМ ИЗВЕСТНЫМ УПОМИНАНИЕМ 
ЭТОГО МЕТОДА "СПРАВА НАЛЕВО" ЯВЛЯЕТСЯ СЛУЧАЙНОЕ ЗАМЕЧАНИЕ, ВСТРЕТИВШЕЕСЯ 
В СТАТЬЕ ы. фЖ. ъОМРИ, 
{\sl Trans. of the Office Machinery Users' Assoc\/}. (London, 1930), 25--37. 
эЕЧАЯННО ъОМРИ ОКАЗАЛСЯ ПЕРВЫМ, КТО СДЕЛАЛ ВАЖНОЕ НАБЛЮДЕНИЕ, ЧТО
%% 458
ТАБУЛЯТОРЫ МОЖНО ПЛОДОТВОРНО ПРИМЕНЯТЬ В НАУЧНЫХ ВЫЧИСЛЕНИЯХ, ХОТЯ 
ПЕРВОНАЧАЛЬНО ОНИ СОЗДАВАЛИСЬ ДЛЯ СТАТИСТИЧЕСКИХ И БУХГАЛТЕРСКИХ 
ПРИЛОЖЕНИЙ. хГО СТАТЬЯ ОСОБЕННО ИНТЕРЕСНА, ПОСКОЛЬКУ, СОДЕРЖИТ 
ПОДРОБНОЕ ОПИСАНИЕ ТАБУЛЯТОРОВ, ИМЕВШИХСЯ В рНГЛИИ В 1930~Г. 
ёОРТИРОВАЛЬНЫЕ МАШИНЫ В ТО ВРЕМЯ ОБРАБАТЫВАЛИ ОТ~360 ДО~400 КАРТ В 
МИНУТУ И СДАВАЛИСЬ В АРЕНДУ ЗА 9 ФУНТОВ СТЕРЛИНГОВ В МЕСЯЦ.

шДЕЯ СЛИЯНИЯ ВОСХОДИТ К ДРУГОМУ УСТРОЙСТВУ ДЛЯ ОБРАБОТКИ 
КАРТ---\emph{ПОДБОРОЧНОЙ МАШИНЕ}, КОТОРАЯ БЫЛА ИЗОБРЕТЕНА ЗНАЧИТЕЛЬНО ПОЗДНЕЕ 
(В 1938~Г.). ёНАБЖЕННАЯ ДВУМЯ ПОДАЮЩИМИ МЕХАНИЗМАМИ, ОНА МОГЛА СЛИТЬ 
ДВЕ ОТСОРТИРОВАННЫЕ КОЛОДЫ КАРТ В ОДНУ ВСЕГО ЗА ОДИН ПРОХОД; МЕТОД 
ВЫПОЛНЕНИЯ ЭТОГО СЛИЯНИЯ ХОРОШО ОПИСАН В ПЕРВОМ РУКОВОДСТВЕ IBM ПО 
МЕТОДАМ ПОДБОРКИ (АПРЕЛЬ 1939~Г.). [ёР. С James W. Bryce. U.~S. Patent 
2189024 (1940).]

чАТЕМ НА СЦЕНЕ ПОЯВИЛИСЬ ¤ть И РАЗРАБОТКА МЕТОДОВ СОРТИРОВКИ ТЕСНО 
ПЕРЕПЛЕЛАСЬ С ИХ РАЗВИТИЕМ. эА САМОМ ДЕЛЕ ИМЕЮТСЯ СВИДЕТЕЛЬСТВА ТОГО, 
ЧТО ПРОГРАММА СОРТИРОВКИ БЫЛА ПЕРВОЙ КОГДА-ЛИБО НАПИСАННОЙ ДЛЯ 
ВЫЧИСЛИТЕЛЬНЫХ МАШИН С ЗАПОМИНАЕМОЙ ПРОГРАММОЙ. ъОНСТРУКТОРЫ 
ВЫЧИСЛИТЕЛЬНОЙ МАШИНЫ EDVAC ОСОБЕННО ИНТЕРЕСОВАЛИСЬ СОРТИРОВКОЙ, 
ПОСКОЛЬКУ ОНА ВЫСТУПАЛА КАК НАИБОЛЕЕ ХАРАКТЕРНЫЙ ПРЕДСТАВИТЕЛЬ 
ПОТЕНЦИАЛЬНЫХ НЕЧИСЛЕННЫХ ПРИЛОЖЕНИЙ ¤ть. юНИ ПОНИМАЛИ, ЧТО 
УДОВЛЕТВОРИТЕЛЬНАЯ СИСТЕМА КОМАНД ДОЛЖНА ГОДИТЬСЯ НЕ ТОЛЬКО ДЛЯ 
СОСТАВЛЕНИЯ ПРОГРАММЫ РЕШЕНИЯ РАЗНОСТНЫХ УРАВНЕНИЙ; В НЕЙ ДОЛЖНА БЫТЬ 
ДОСТАТОЧНАЯ ГИБКОСТЬ, ЧТОБЫ СПРАВИТЬСЯ С КОМБИНАТОРНЫМИ АСПЕКТАМИ 
"ВЫБОРА РЕШЕНИЙ" В АЛГОРИТМАХ. яОЭТОМУ фЖОН ФОН эЕЙМАН ПОДГОТОВИЛ В 
1945 Г. ПРОГРАММЫ ДЛЯ ВНУТРЕННЕЙ СОРТИРОВКИ СЛИЯНИЕМ, ЧТОБЫ УБЕДИТЬСЯ В 
НЕОБХОДИМОСТИ НЕКОТОРЫХ КОДОВ КОМАНД, КОТОРЫЕ ОН ПРЕДЛАГАЛ ДЛЯ 
МАШИНЫ EDVAC; СУЩЕСТВОВАЛИ ЭФФЕКТИВНЫЕ СОРТИРОВАЛЬНЫЕ МАШИНЫ 
СПЕЦИАЛЬНОГО НАЗНАЧЕНИЯ, И ОНИ СЛУЖИЛИ ТЕМ ЕСТЕСТВЕННЫМ СТАНДАРТОМ, В 
СОПОСТАВЛЕНИИ С КОТОРЫМ МОЖНО БЫЛО ОЦЕНИТЬ ДОСТОИНСТВА ПРЕДЛАГАЕМОЙ 
ОРГАНИЗАЦИИ ВЫЧИСЛИТЕЛЬНОЙ МАШИНЫ. яОДРОБНО ЭТО ИНТЕРЕСНОЕ 
ИССЛЕДОВАНИЕ ОПИСАНО В СТАТЬЕ 
ф.~¤.~ъНУТА [{\sl Computing Surveys\/}, {\bf 2} (1970), 247--260]; ПЕРВУЮ 
ПРОГРАММУ СОРТИРОВКИ ФОН эЕЙМАНА В ОКОНЧАТЕЛЬНОМ, "ОТПОЛИРОВАННОМ" 
ВИДЕ СМ. В ЕГО Collected Works, {\bf 5} (New York, Macmillan, 1963), 
196--214.

шЗ-ЗА ОГРАНИЧЕННОГО ОБоЕМА ПАМЯТИ В РАННИХ МАШИНАХ ПРИХОДИЛОСЬ 
ДУМАТЬ О ВНЕШНЕЙ СОРТИРОВКЕ НАРАВНЕ С ВНУТРЕННЕЙ, И В ДОКЛАДЕ "Progress 
Report on the EDVAC", ПОДГОТОВЛЕННОМ фЖ. я. ¤ККЕРТОМ И фЖ є. ьОЧЛИ 
ДЛЯ ШКОЛЫ ьУРА ПО ЭЛЕКТРОТЕХНИКЕ [Moore school of Electrical Engineering 
(September 30, 1945)], УКАЗЫВАЛОСЬ, ЧТО ¤ть, ОСНАЩЕННАЯ УСТРОЙСТВОМ С 
МАГНИТНОЙ ПРОВОЛОКОЙ ИЛИ ЛЕНТОЙ, МОГЛА БЫ МОДЕЛИРОВАТЬ
%% 459
ДЕЙСТВИЯ КАРТОЧНОГО ОБОРУДОВАНИЯ, ДОСТИГАЯ ПРИ ЭТОМ БОЛЬШЕЙ СКОРОСТИ 
СОРТИРОВКИ. ¤ТОТ ДОКЛАД ОПИСЫВАЛ СБАЛАНСИРОВАННУЮ ДВУХПУТЕВУЮ 
ПОРАЗРЯДНУЮ СОРТИРОВКУ И СБАЛАНСИРОВАННОЕ ДВУХПУТЕВОЕ СЛИЯНИЕ С 
ИСПОЛЬЗОВАНИЕМ ЧЕТЫРЕХ УСТРОЙСТВ С МАГНИТНОЙ ПРОВОЛОКОЙ ИЛИ ЛЕНТОЙ, 
ЧИТАЮЩИХ ИЛИ ЗАПИСЫВАЮЩИХ "НЕ МЕНЕЕ 5000 ИМПУЛЬСОВ В СЕКУНДУ".

фЖОН ьОЧЛИ ВЫСТУПИЛ С ЛЕКЦИЕЙ О "СОРТИРОВКЕ И СЛИЯНИИ" НА 
СПЕЦИАЛЬНОЙ СЕССИИ ПО ВЫЧИСЛЕНИЯМ, СОЗЫВАВШЕЙСЯ В ШКОЛЕ ьУРА В 1946 Г., 
И В ЗАПИСЯХ ЕГО ЛЕКЦИИ СОДЕРЖИТСЯ ПЕРВОЕ ОПУБЛИКОВАННОЕ ОБСУЖДЕНИЕ 
СОРТИРОВКИ С ПОМОЩЬЮ ВЫЧИСЛИТЕЛЬНЫХ МАШИН [Theory and techniques for 
the design of electronic digital computers, ed. by G. W. Patterson, 
{\bf 3} (1946), 22.1--22.20]. 
ьОЧЛИ НАЧАЛ СВОЕ ВЫСТУПЛЕНИЕ С ИНТЕРЕСНОГО ЗАМЕЧАНИЯ: 
"ЄРЕБОВАНИЕ, ЧТОБЫ ОДНА МАШИНА ОБоЕДИНЯЛА ВОЗМОЖНОСТИ ВЫЧИСЛЕНИЙ И 
СОРТИРОВКИ, МОЖЕТ ВЫГЛЯДЕТЬ КАК ТРЕБОВАНИЕ, ЧТОБЫ ОДИН ПРИБОР 
ИСПОЛЬЗОВАЛСЯ КАК КЛЮЧ ДЛЯ КОНСЕРВОВ И КАК АВТОРУЧКА". чАТЕМ ОН ЗАМЕТИЛ, 
ЧТО МАШИНЫ, СПОСОБНЫЕ ВЫПОЛНЯТЬ СЛОЖНЫЕ МАТЕМАТИЧЕСКИЕ ПРОЦЕДУРЫ, 
ДОЛЖНЫ ТАКЖЕ ИМЕТЬ ВОЗМОЖНОСТЬ СОРТИРОВАТЬ И КЛАССИФИЦИРОВАТЬ 
ДАННЫЕ; ОН ПОКАЗАЛ, ЧТО СОРТИРОВКА МОЖЕТ БЫТЬ ПОЛЕЗНА ДАЖЕ В СВЯЗИ С 
ЧИСЛЕННЫМИ РАСЧЕТАМИ. юН ОПИСАЛ ПРОСТЫЕ ВСТАВКИ И БИНАРНЫЕ ВСТАВКИ, 
ЗАМЕТИВ, ЧТО В ПЕРВОМ МЕТОДЕ В СРЕДНЕМ ТРЕБУЕТСЯ ОКОЛО $N^2/4$ 
СРАВНЕНИЙ, В ТО ВРЕМЯ КАК В ПОСЛЕДНЕМ ИХ НИКОГДА НЕ ТРЕБУЕТСЯ БОЛЕЕ 
$N\log_2N$. юДНАКО БИНАРНЫЕ ВСТАВКИ ТРЕБУЮТ ВЕСЬМА СЛОЖНОЙ СТРУКТУРЫ 
ДАННЫХ, И ьОЧЛИ ЗАТЕМ ПОКАЗАЛ, ЧТО ПРИ ДВУХПУТЕВОМ СЛИЯНИИ ДОСТИГАЕТСЯ 
СТОЛЬ ЖЕ МАЛОЕ ЧИСЛО СРАВНЕНИЙ, НО ИСПОЛЬЗУЕТСЯ ТОЛЬКО ПОСЛЕДОВАТЕЛЬНОЕ 
ПРОХОЖДЕНИЕ СПИСКОВ. яОСЛЕДНЯЯ ЧАСТЬ ЗАПИСЕЙ ЕГО ЛЕКЦИЙ ПОСВЯЩЕНА 
РАЗБОРУ МЕТОДОВ ПОРАЗРЯДНОЙ СОРТИРОВКИ С ЧАСТИЧНЫМИ ПРОХОДАМИ, 
КОТОРЫЕ МОДЕЛИРУЮТ ЦИФРОВУЮ КАРТОЧНУЮ СОРТИРОВКУ НА ЧЕТЫРЕХ ЛЕНТАХ, 
ЗАТРАЧИВАЯ МЕНЕЕ ЧЕТЫРЕХ ПРОХОДОВ НА ЦИФРУ (СР. С П. 5.4.7).

тСКОРЕ ПОСЛЕ ЭТОГО ¤ККЕРТ И ьОЧЛИ ОРГАНИЗОВАЛИ КОМПАНИЮ, КОТОРАЯ 
ВЫПУСКАЛА НЕКОТОРЫЕ ИЗ САМЫХ РАННИХ ЭЛЕКТРОННЫХ ВЫЧИСЛИТЕЛЬНЫХ 
МАШИН BINAC (ДЛЯ ВОЕННЫХ ПРИЛОЖЕНИЙ) И. UNIVAC (ДЛЯ КОММЕРЧЕСКИХ 
ПРИЛОЖЕНИЙ). тНОВЬ сЮРО ПЕРЕПИСИ ё°р СЫГРАЛО РОЛЬ В ЭТОМ РАЗВИТИИ, 
ПРИОБРЕТЯ ПЕРВЫЙ UNIVAC. т ЭТО ВРЕМЯ ВОВСЕ НЕ БЫЛО ЯСНО, ЧТО ¤ть 
СТАНУТ ЭКОНОМИЧЕСКИ ВЫГОДНЫМИ: ВЫЧИСЛИТЕЛЬНЫЕ МАШИНЫ МОГЛИ 
СОРТИРОВАТЬ БЫСТРЕЕ, НО ОНИ ДОРОЖЕ СТОИЛИ. яОЭТОМУ ПРОГРАММИСТЫ 
UNIVAC ПОД РУКОВОДСТВОМ ЇРАНСИС ¤. уОЛЬБЕРТОН ПРИЛОЖИЛИ 
ЗНАЧИТЕЛЬНЫЕ УСИЛИЯ К СОЗДАНИЮ ПРОГРАММ ВНЕШНЕЙ СОРТИРОВКИ, 
РАБОТАЮЩИХ С ВЫСОКОЙ СКОРОСТЬЮ, И ИХ ПЕРВЫЕ ПРОГРАММЫ ПОВЛИЯЛИ ТАКЖЕ 
НА РАЗРАБОТКУ ОБОРУДОВАНИЯ. яО ИХ ОЦЕНКАМ, 100 МИЛЛИОНОВ ЗАПИСЕЙ ПО 10 
СЛОВ МОГЛИ БЫТЬ .ОТСОРТИРОВАНЫ НА UNIVAC ЗА 9000 Ч (Т. Е. 375 ДНЕЙ).
%% 460

UNIVAC I, ОФИЦИАЛЬНО ОБоЯВЛЕННАЯ В ИЮЛЕ 1951 Г., ИМЕЛА ВНУТРЕННЮЮ 
ПАМЯТЬ В 1000 12-ЛИТЕРНЫХ (72-БИТОВЫХ) СЛОВ. т НЕЙ ПРЕДУСМАТРИВАЛОСЬ 
ЧТЕНИЕ И ЗАПИСЬ НА ЛЕНТУ БЛОКОВ ПО 60 СЛОВ СО СКОРОСТЬЮ 500 СЛОВ В 
СЕКУНДУ; ЧТЕНИЕ МОГЛО БЫТЬ ПРЯМЫМ ИЛИ ОБРАТНЫМ, ДОПУСКАЛОСЬ 
ОДНОВРЕМЕННОЕ ЧТЕНИЕ /ЗАПИСЬ/ ВЫЧИСЛЕНИЯ. т 1948~Г. МИССИС уОЛЬБЕРТОН 
ПРИДУМАЛА ИНТЕРЕСНЫЙ СПОСОБ ВЫПОЛНЕНИЯ ДВУХПУТЕВОГО СЛИЯНИЯ С ПОЛНЫМ 
СОВМЕЩЕНИЕМ ЧТЕНИЯ, ЗАПИСИ И ВЫЧИСЛЕНИЙ С ИСПОЛЬЗОВАНИЕМ ШЕСТИ 
БУФЕРОВ ВВОДА. яУСТЬ ДЛЯ КАЖДОГО ВВОДНОГО ФАЙЛА ИМЕЮТСЯ ОДИН "ТЕКУЩИЙ 
БУФЕР" И ДВА "ВСПОМОГАТЕЛЬНЫХ БУФЕРА"; СЛИВАТЬ МОЖНО ТАКИМ ОБРАЗОМ, ЧТО 
ВСЯКИЙ РАЗ, КОГДА ПРИХОДИТ ВРЕМЯ ВЫВЕСТИ ОДИН БЛОК, ДВА ТЕКУЩИХ БУФЕРА 
ВВОДА .СОДЕРЖАТ ВМЕСТЕ КОЛИЧЕСТВО ДАННЫХ, РАВНОЕ ОДНОМУ БЛОКУ. ЄАКИМ 
ОБРАЗОМ, ЗА ВРЕМЯ ФОРМИРОВАНИЯ КАЖДОГО ВЫВОДНОГО БЛОКА РОВНО ОДИН 
БУФЕР ВВОДА СТАНОВИТСЯ ПУСТЫМ, И МЫ МОЖЕМ УСТРОИТЬ ТАК, ЧТОБЫ ТРИ ИЛИ 
ЧЕТЫРЕ ВСПОМОГАТЕЛЬНЫХ БУФЕРА БЫЛИ ЗАПОЛНЕНЫ ВСЯКИЙ РАЗ, КАК МЫ ЧИТАЕМ 
В ОСТАВШИЙСЯ БУФЕР. ¤ТОТ МЕТОД ЧУТЬ БЫСТРЕЕ МЕТОДА ПРОГНОЗИРОВАНИЯ 
АЛГОРИТМА 5.4.6F, ТАК КАК НЕТ НЕОБХОДИМОСТИ ПРОВЕРЯТЬ РЕЗУЛЬТАТ ОДНОГО 
ВВОДА ПЕРЕД НАЧАЛОМ СЛЕДУЮЩЕГО. [ёР. С Collation Methods for the UNIVAC 
System (Eckert-Mauchly Computer Corp., 1950) vol. 1,2.]

ъУЛЬМИНАЦИОННОЙ ТОЧКОЙ В ЭТОЙ РАБОТЕ СТАЛ ГЕНЕРАТОР ПРОГРАММ 
СОРТИРОВКИ, КОТОРЫЙ БЫЛ ПЕРВОЙ КРУПНОЙ ПРОГРАММОЙ, РАЗРАБОТАННОЙ ДЛЯ 
АВТОМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ. яОЛЬЗОВАТЕЛЬ УКАЗЫВАЛ РАЗМЕР ЗАПИСИ, 
ПОЗИЦИИ КЛЮЧЕЙ (ДО ПЯТИ) В ЧАСТИЧНЫХ ПОЛЯХ КАЖДОЙ ЗАПИСИ И "КОНЦЕВЫЕ" 
КЛЮЧИ, ОТМЕЧАЮЩИЕ КОНЕЦ ФАЙЛА, И ГЕНЕРАТОР СОРТИРОВКИ ПОРОЖДАЛ 
ТРЕБУЕМУЮ ПРОГРАММУ СОРТИРОВКИ ДЛЯ ФАЙЛОВ НА ОДНОЙ БОБИНЕ. яЕРВЫМ 
ПРОХОДОМ ЭТОЙ ПРОГРАММЫ БЫЛА ВНУТРЕННЯЯ СОРТИРОВКА БЛОКОВ ПО 60 СЛОВ С 
ИСПОЛЬЗОВАНИЕМ МЕТОДА СРАВНЕНИЯ И ПОДСЧЕТА (АЛГОРИТМ 5.2ё); ЗАТЕМ 
ВЫПОЛНЯЛСЯ РЯД СБАЛАНСИРОВАННЫХ ДВУХПУТЕВЫХ ПРОХОДОВ СЛИЯНИЯ С 
ОБРАТНЫМ ЧТЕНИЕМ, ИСКЛЮЧАЮЩИХ СЦЕПЛЕНИЕ ЛЕНТ, КАК ОПИСАНО ВЫШЕ. [ёМ. 
Master Generating Routine for 2-way Sorting (Eckert---Mauchly Div. of 
Remington Rand, 1952). яЕРВЫЙ НАБРОСОК ЭТОГО ДОКЛАДА БЫЛ ОЗАГЛАВЛЕН 
"юСНОВНАЯ СОСТАВЛЯЮЩАЯ ПРОГРАММА ДВУХПУТЕВОГО СЛИЯНИЯ" (Master 
Prefabrication Routine for 2-way Collation)! ёМ. ТАКЖЕ F. E. Holberton, 
Symposium on Automatic Programming (Office of Naval Research, 1954), 
34--39.]

ъ 1952~Г. МНОГИЕ МЕТОДЫ ВНУТРЕННЕЙ СОРТИРОВКИ ПРОЧНО ВОШЛИ В 
ПРОГРАММИСТСКИЙ ФОЛЬКЛОР, НО ТЕОРИЯ БЫЛА РАЗВИТА СРАВНИТЕЛЬНО СЛАБО. 
фАНИЭЛЬ уОЛДЕНБЕРГ [Time analises of various methods of sorting data, Digital 
Computer Lab. memo M-1680 (Mass. Inst. of Tech.,. October 17, 1952)] 
ЗАПРОГРАММИРОВАЛ ДЛЯ МАШИНЫ Whirlwind ПЯТЬ РАЗЛИЧНЫХ МЕТОДОВ И ПРОВЕЛ 
АНАЛИЗ
%% 461
НАИЛУЧШЕГО И НАИХУДШЕГО СЛУЧАЕВ ДЛЯ КАЖДОЙ ПРОГРАММЫ. юН НАШЕЛ, ЧТО 
ДЛЯ СОРТИРОВКИ СОТНИ 15-БИТОВЫХ ЗАПИСЕЙ ПО 8-БИТОВОМУ КЛЮЧУ НАИЛУЧШИЕ 
ПО СКОРОСТИ РЕЗУЛЬТАТЫ ПОЛУЧАЮТСЯ В ТОМ СЛУЧАЕ, ЕСЛИ ИСПОЛЬЗУЕТСЯ 
ТАБЛИЦА ИЗ 256 СЛОВ И КАЖДАЯ ЗАПИСЬ ПОМЕЩАЕТСЯ В ЕДИНСТВЕННУЮ 
СООТВЕТСТВУЮЩУЮ ЕЕ КЛЮЧУ ПОЗИЦИЮ, А ЗАТЕМ ЭТА ТАБЛИЦА СЖИМАЕТСЯ. 
юДНАКО ЭТОТ МЕТОД ИМЕЛ ОЧЕВИДНЫЙ НЕДОСТАТОК, ИБО ОН УНИЧТОЖАЛ ЗАПИСЬ, 
ЕСЛИ ПОСЛЕДУЮЩАЯ ИМЕЛА ТОТ ЖЕ КЛЮЧ. юСТАЛЬНЫЕ ЧЕТЫРЕ 
ПРОАНАЛИЗИРОВАННЫХ МЕТОДА БЫЛИ УПОРЯДОЧЕНЫ СЛЕДУЮЩИМ ОБРАЗОМ:
ПРЯМОЕ ДВУХПУТЕВОЕ СЛИЯНИЕ ЛУЧШЕ ПОРАЗРЯДНОЙ СОРТИРОВКИ С ОСНОВАНИЕМ 
2, КОТОРАЯ ЛУЧШЕ ПРОСТОГО ВЫБОРА, КОТОРЫЙ В СВОЮ ОЧЕРЕДЬ ЛУЧШЕ МЕТОДА 
ПУЗЫРЬКА.

¤ТИ РЕЗУЛЬТАТЫ ПОЛУЧИЛИ ДАЛЬНЕЙШЕЕ РАЗВИТИЕ В ДИССЕРТАЦИИ уАРОЛЬДА 
X. ёЬЮВОРДА В 1954~Г. [Information sorting in the application of electronic 
digital computers to business operations, Digital Computer Lab. report R-232 
(Mass. Inst. of Tech.. May 24, 1954), 60 pp.]. ёЬЮВОРД ВЫСКАЗАЛ ИДЕИ 
РАСПРЕДЕЛЯЮЩЕГО ПОДСЧЕТА И ВЫБОРА С ЗАМЕЩЕНИЕМ. юН ПОКАЗАЛ, ЧТО ПЕРВЫЙ 
ОТРЕЗОК СЛУЧАЙНОЙ ПЕРЕСТАНОВКИ ИМЕЕТ СРЕДНЮЮ ДЛИНУ $e-1$, И 
АНАЛИЗИРОВАЛ НАРЯДУ С ВНУТРЕННЕЙ СОРТИРОВКОЙ И ВНЕШНЮЮ КАК НА 
РАЗЛИЧНЫХ ТИПАХ МАССОВОЙ ПАМЯТИ, ТАК И НА ЛЕНТАХ.

хЩЕ БОЛЕЕ ДОСТОЙНАЯ ВНИМАНИЯ ДИССЕРТАЦИЯ---НА ЭТОТ РАЗ ДОКТОРСКАЯ---
БЫЛА НАПИСАНА уОВАРДОМ с. фЕМУТОМ В 1956~Г. [Electronic Data Sorting 
(Stanford University, October, 1956), 92 pp.]. ¤ТА РАБОТА ПОМОГЛА ЗАЛОЖИТЬ 
ОСНОВЫ ТЕОРИИ СЛОЖНОСТИ ВЫЧИСЛЕНИЙ. т.НЕЙ РАССМАТРИВАЛИСЬ ТРИ 
АБСТРАКТНЫЕ МОДЕЛИ ЗАДАЧИ СОРТИРОВКИ: С ИСПОЛЬЗОВАНИЕМ ЦИКЛИЧЕСКОЙ 
ПАМЯТИ, ЛИНЕЙНОЙ ПАМЯТИ И ПАМЯТИ С ПРОИЗВОЛЬНЫМ ДОСТУПОМ; ДЛЯ КАЖДОЙ 
МОДЕЛИ БЫЛИ РАЗРАБОТАНЫ ОПТИМАЛЬНЫЕ ИЛИ ПОЧТИ ОПТИМАЛЬНЫЕ МЕТОДЫ. 
(ёР. С УПР. 5.3.4--62.) їОТЯ НЕПОСРЕДСТВЕННО ИЗ ДИССЕРТАЦИИ фЕМУТА НЕ 
ВЫТЕКАЕТ НИКАКИХ ПРАКТИЧЕСКИХ СЛЕДСТВИЙ, В НЕЙ СОДЕРЖАТСЯ ВАЖНЫЕ ИДЕИ О 
ТОМ, КАК СВЯЗАТЬ ТЕОРИЮ С ПРАКТИКОЙ.

ЄАКИМ ОБРАЗОМ, ИСТОРИЯ СОРТИРОВКИ БЫЛА ТЕСНО СВЯЗАНА СО МНОГИМИ 
ИСХОЖЕННЫМИ ТРОПАМИ В ВЫЧИСЛЕНИЯХ: С ПЕРВЫМИ МАШИНАМИ ДЛЯ ОБРАБОТКИ 
ДАННЫХ, ПЕРВЫМИ ЗАПОМИНАЕМЫМИ ПРОГРАММАМИ, ПЕРВЫМ ПРОГРАММНЫМ 
ОБЕСПЕЧЕНИЕМ, ПЕРВЫМИ МЕТОДАМИ БУФЕРИЗАЦИИ, ПЕРВОЙ РАБОТОЙ ПО АНАЛИЗУ 
АЛГОРИТМОВ И СЛОЖНОСТИ ВЫЧИСЛЕНИЙ.

эИ ОДИН ИЗ ДОКУМЕНТОВ ОТНОСИТЕЛЬНО ¤ть, УПОМЯНУТЫХ ДО СИХ ПОР, НЕ 
ПОЯВЛЯЛСЯ В "ОТКРЫТОЙ ЛИТЕРАТУРЕ". ЄАК УЖ СЛУЧИЛОСЬ, ЧТО БОЛЬШАЯ ЧАСТЬ 
РАННЕЙ ИСТОРИИ ВЫЧИСЛИТЕЛЬНЫХ МАШИН СОДЕРЖИТСЯ В СРАВНИТЕЛЬНО 
НЕДОСТУПНЫХ ДОКЛАДАХ, ПОСКОЛЬКУ ОТНОСИТЕЛЬНО НЕМНОГИЕ ЛИЦА БЫЛИ В ТО 
ВРЕМЯ СВЯЗАНЫ С ¤ть. эАКОНЕЦ В 1955--1956~ГГ. ЛИТЕРАТУРА О СОРТИРОВКЕ 
ПРОНИКАЕТ В ПЕЧАТЬ В ВИДЕ ТРЕХ БОЛЬШИХ ОБЗОРНЫХ СТАТЕЙ.
%% 462
яЕРВАЯ СТАТЬЯ БЫЛА ПОДГОТОВЛЕНА фЖ. ъ. їОСКЕНОМ [Proc. Eastern Joint. 
Computer Conference, 8 (1955), 39---55]. юН НАЧИНАЕТ С ТОНКОГО НАБЛЮДЕНИЯ: 
"ўТОБЫ СНИЗИТЬ СТОИМОСТЬ ЕДИНИЦЫ РЕЗУЛЬТАТА, ЛЮДИ ОБЫЧНО УКРУПНЯЮТ 
ОПЕРАЦИИ. эО ПРИ ЭТИХ УСЛОВИЯХ СТОИМОСТЬ ЕДИНИЦЫ СОРТИРОВКИ НЕ 
УМЕНЬШАЕТСЯ, А ВОЗРАСТАЕТ". їОСКЕН ОПИСАЛ ВСЕ ОБОРУДОВАНИЕ СПЕЦИАЛЬНОГО 
НАЗНАЧЕНИЯ, ИМЕВШЕЕСЯ В ПРОДАЖЕ, А ТАКЖЕ МЕТОДЫ СОРТИРОВКИ НА ¤ть. хГО 
БИБЛИОГРАФИЯ ИЗ 54 ПУНКТОВ ОСНОВАНА БОЛЬШЕЙ ЧАСТЬЮ НА БРОШЮРАХ 
ФИРМ-ИЗГОТОВИТЕЛЕЙ.

яОДРОБНАЯ СТАТЬЯ ¤. X. ЇРЭНДА [Sorting on Electronic Computer Systems, 
{\sl JACM\/}, {\bf 3} (1956), 134--168] ЯВИЛАСЬ ВАЖНОЙ ВЕХОЙ В РАЗВИТИИ 
СОРТИРОВКИ. їОТЯ ЗА ПРОШЕДШЕЕ С 1956 Г. ВРЕМЯ БЫЛИ РАЗРАБОТАНЫ 
МНОГОЧИСЛЕННЫЕ МЕТОДЫ, ЭТА СТАТЬЯ ВСЕ ЕЩЕ НЕОБЫЧНО СОВРЕМЕННА ВО 
МНОГИХ ОТНОШЕНИЯХ. ЇРЭНД ДАЛ ТЩАТЕЛЬНОЕ ОПИСАНИЕ ВЕСЬМА БОЛЬШОГО 
ЧИСЛА АЛГОРИТМОВ ВНУТРЕННЕЙ И ВНЕШНЕЙ СОРТИРОВКИ И ОБРАТИЛ ОСОБОЕ 
ВНИМАНИЕ НА МЕТОДЫ БУФЕРИЗАЦИИ И ХАРАКТЕРИСТИКИ МАГНИТНЫХ 
ЛЕНТОПРОТЯЖНЫХ УСТРОЙСТВ. юН ВВЕЛ НЕКОТОРЫЕ НОВЫЕ МЕТОДЫ (НАПРИМЕР, 
ВЫБОР ИЗ ДЕРЕВА, МЕТОД ДВУГЛАВОГО ЗМИЯ И ПРОГНОЗИРОВАНИЕ) И РАЗРАБОТАЛ 
НЕКОТОРЫЕ МАТЕМАТИЧЕСКИЕ СВОЙСТВА СТАРЫХ МЕТОДОВ.

ЄРЕТИЙ ОБЗОР ПО СОРТИРОВКЕ, КОТОРЫЙ ПОЯВИЛСЯ В ТО ВРЕМЯ, БЫЛ 
ПОДГОТОВЛЕН ф. є. фЭВАЙСОМ [{\sl Proc. Inst. Elect. Engineers\/}, {\bf 103т}, 
supplement 1 (1956), 87--93]. т ПОСЛЕДУЮЩИЕ ГОДЫ ЕЩЕ НЕСКОЛЬКО 
ВЫДАЮЩИХСЯ ОБЗОРОВ БЫЛО ОПУБЛИКОВАНО ф. р. сЕЛЛОМ [{\sl ёОmp. J.\/}, 
{\bf 1} (1958), 71--77]; р. °. фУГЛАСОМ 
[{\sl Comp. J.\/}, {\bf 2} (1959), 1--9]; ф. ф. ьАК-ъРАКЕНОМ, у. тЕЙССОМ И 
Ў. ыИ [Programming Business Computers (New York: Wiley, 1959), chapter~15, 
298--332]; р. ЇЛОРЕСОМ [{\sl JACM\/}, {\bf 8} (1961) 41--80];
ъ. ¤. рЙВЕРСОНОМ [A programming language (New York: Wiley, 1962), 
chapter 6, 176---245]; ъ. ъ. уОТЛИБОМ [{\sl CACM\/}, {\bf 6} (1963), 194--201]; 
Є. э. їИББАРДОМ [{\sl CACM\/},{\bf  6} (1963), 206--213];
ь. р. уОТЦЕМ [Digital Computer User's Handbook ed. by M. Klerer and G. 
A. Korn (New York, McGraw-Hill, 1967), chapter~1.10, 1.292--1.320]. т 
НОЯБРЕ 1962~Г. ACM ОРГАНИЗОВАЛА СИМПОЗИУМ ПО СОРТИРОВКЕ (БОЛЬШАЯ 
ЧАСТЬ РАБОТ, ПРЕДСТАВЛЕННЫХ НА ЭТОМ СИМПОЗИУМЕ, ОПУБЛИКОВАНА В МАЕ 1963 
Г. В ВЫПУСКЕ {\sl CACM\/}). юНИ ДАЮТ ХОРОШЕЕ ПРЕДСТАВЛЕНИЕ О СОСТОЯНИИ 
ЭТОЙ ОБЛАСТИ В ТО ВРЕМЯ. юБЗОР ъ.~ъ.~уОТЛИБА О СОВРЕМЕННЫХ ГЕНЕРАТОРАХ 
СОРТИРОВКИ, ОБЗОР Є.~э.~їИББАРДА О ВНУТРЕННЕЙ СОРТИРОВКЕ С 
МИНИМАЛЬНОЙ ПАМЯТЬЮ И РАННЕЕ ИССЛЕДОВАНИЕ фЖ.~р.~їАББЭРДА О 
СОРТИРОВКЕ ФАЙЛОВ НА ДИСКАХ---НАИБОЛЕЕ ЗАСЛУЖИВАЮЩИЕ ВНИМАНИЯ СТАТЬИ В 
ЭТОМ СОБРАНИИ.

чА ПРОШЕДШИЙ ПЕРИОД БЫЛИ ОТКРЫТЫ НОВЫЕ МЕТОДЫ СОРТИРОВКИ: 
ВЫЧИСЛЕНИЕ АДРЕСА~(1956), СЛИЯНИЕ С ВСТАВКОЙ~(1959), ОБМЕННАЯ 
ПОРАЗРЯДНАЯ СОРТИРОВКА~(1959), КАСКАДНОЕ СЛИЯНИЕ~(1959), МЕТОД °ЕЛЛА С 
УБЫВАЮЩИМ ШАГОМ~(1959), МНОГОФАЗНОЕ
%% 463
СЛИЯНИЕ (1960), ВСТАВКИ В ДЕРЕВО (1960), ОСЦИЛЛИРУЮЩАЯ СОРТИРОВКА (1962), 
БЫСТРАЯ СОРТИРОВКА їОАРА (1962), ПИРАМИДАЛЬНАЯ СОРТИРОВКА єИЛЬЯМСА 
(1964), ОБМЕННАЯ СОРТИРОВКА СО СЛИЯНИЕМ сЭТЧЕРА (1964). шСТОРИЯ КАЖДОГО 
ОТДЕЛЬНОГО АЛГОРИТМА ПРОСЛЕЖИВАЕТСЯ В ТЕХ РАЗДЕЛАХ НАСТОЯЩЕЙ ГЛАВЫ ГДЕ 
ЭТОТ МЕТОД ОПИСЫВАЕТСЯ. ъОНЕЦ 60-Х ГОДОВ НАШЕГО СТОЛЕТИЯ ОЗНАМЕНОВАЛСЯ 
ИНТЕНСИВНЫМ РАЗВИТИЕМ СООТВЕТСТВУЮЩЕЙ ТЕОРИИ.

яОЛНАЯ БИБЛИОГРАФИЯ ВСЕХ РАБОТ, ИЗУЧЕННЫХ АВТОРОМ ПРИ НАПИСАНИИ 
ЭТОЙ ГЛАВЫ, ИМЕЕТСЯ В [{\sl Computing Reviews\/}, {\bf 13} (1972), 283--289].

\excercises
\ex[05] яОДВЕДИТЕ ИТОГ ЭТОЙ ГЛАВЕ; СФОРМУЛИРУЙТЕ ОБОБЩЕНИЕ ТЕОРЕМЫ 5.4.6р.

\ex[20] ёКАЖИТЕ, ОСНОВЫВАЯСЬ НА ТАБЛ.~1, КАКОЙ ИЗ МЕТОДОВ СОРТИРОВКИ СПИСКОВ 
ДЛЯ ШЕСТИЦИФРОВЫХ КЛЮЧЕЙ БУДЕТ НАИЛУЧШИМ ДЛЯ МАШИНЫ \MIX.

\ex[47]\exhead(єСТОЙЧИВАЯ СОРТИРОВКА С МИНИМАЛЬНОЙ ПАМЯТЬЮ.) уОВОРЯТ, ЧТО 
АЛГОРИТМ СОРТИРОВКИ ТРЕБУЕТ \emph{МИНИМАЛЬНОЙ ПАМЯТИ}, ЕСЛИ ОН ИСПОЛЬЗУЕТ ДЛЯ 
СВОИХ ПЕРЕМЕННЫХ ТОЛЬКО $O((\log N)^2)$ БИТОВ ПАМЯТИ СВЕРХ ПРОСТРАНСТВА, 
ТРЕБУЕМОГО ДЛЯ РАЗМЕЩЕНИЯ $N$ ЗАПИСЕЙ. рЛГОРИТМ ДОЛЖЕН БЫТЬ ОБЩИМ В ТОМ СМЫСЛЕ, 
ЧТО ДОЛЖЕН РАБОТАТЬ ПРИ ЛЮБЫХ $N$, А НЕ ТОЛЬКО ПРИ ОПРЕДЕЛЕННОМ ЗНАЧЕНИИ $N$, 
ЕСЛИ, КОНЕЧНО, ПРЕДПОЛАГАЕТСЯ, ЧТО ПРИ ВЫЗОВЕ АЛГОРИТМА ДЛЯ СОРТИРОВКИ ЕМУ 
ОБЕСПЕЧИВАЕТСЯ ДОСТАТОЧНОЕ КОЛИЧЕСТВО ПАМЯТИ С ПРОИЗВОЛЬНЫМ ДОСТУПОМ. тО МНОГИХ 
ИЗ ИЗУЧЕННЫХ НАМИ АЛГОРИТМОВ СОРТИРОВКИ ЭТО ТРЕБОВАНИЕ МИНИМАЛЬНОЙ ПАМЯТИ 
НАРУШАЕТСЯ; В ЧАСТНОСТИ, ЗАПРЕЩЕНО ИСПОЛЬЗОВАНИЕ $N$ ПОЛЕЙ СВЯЗИ. сЫСТРАЯ 
СОРТИРОВКА (АЛГОРИТМ 5.2.2Q) УДОВЛЕТВОРЯЕТ ТРЕБОВАНИЮ МИНИМАЛЬНОЙ ПАМЯТИ, НО 
ЕЕ ВРЕМЯ РАБОТЫ В НАИХУДШЕМ СЛУЧАЕ ПРОПОРЦИОНАЛЬНО $N^2$. яИРАМИДАЛЬНАЯ 
СОРТИРОВКА (АЛГОРИТМ 5.2.3э) ЯВЛЯЕТСЯ ЕДИНСТВЕННЫМ СРЕДИ ИЗУЧЕННЫХ НАМИ 
АЛГОРИТМОВ ТИПА $O(N\log N)$, КОТОРЫЙ ИСПОЛЬЗУЕТ МИНИМАЛЬНУЮ ПАМЯТЬ, ХОТЯ МОЖНО 
СФОРМУЛИРОВАТЬ И ЕЩЕ ОДИН ПОДОБНЫЙ АЛГОРИТМ, ЕСЛИ ИСПОЛЬЗОВАТЬ ИДЕЮ ИЗ 
УПР.~5.2.4--18.

ёАМЫМ БЫСТРЫМ ОБЩИМ АЛГОРИТМОМ, ИЗУЧЕННЫМ НАМИ, КОТОРЫЙ \emph{УСТОЙЧИВО} 
СОРТИРУЕТ КЛЮЧИ, ЯВЛЯЕТСЯ МЕТОД СЛИЯНИЯ СПИСКОВ (АЛГОРИТМ 5.2.4L), ОДНАКО ОН 
ИСПОЛЬЗУЕТ НЕ МИНИМАЛЬНУЮ ПАМЯТЬ. ЇАКТИЧЕСКИ ЕДИНСТВЕННЫМИ УСТОЙЧИВЫМИ 
АЛГОРИТМАМИ СОРТИРОВКИ С МИНИМАЛЬНОЙ ПАМЯТЬЮ, КОТОРЫЕ МЫ ВИДЕЛИ, БЫЛИ МЕТОДЫ 
ТИПА $O(N^2)$ (ПРОСТЫЕ ВСТАВКИ, МЕТОД ПУЗЫРЬКА И ВАРИАНТЫ ПРОСТОГО ВЫБОРА).

ёУЩЕСТВУЕТ ЛИ УСТОЙЧИВЫЙ АЛГОРИТМ СОРТИРОВКИ С МИНИМАЛЬНОЙ ПАМЯТЬЮ, ТРЕБУЮЩИЙ 
МЕНЕЕ $O(N^2)$ ЕДИНИЦ ВРЕМЕНИ В НАИХУДШЕМ СЛУЧАЕ ИЛИ В СРЕДНЕМ?

\epigraph
▀ ДОСТИГ СВОЕЙ ЦЕЛИ., ЕСЛИ. РАССОРТИРОВАЛ И ПРИВЕЛ В ЛОГИЧЕСКИЙ 
ПОРЯДОК ХОТЯ БЫ ЯДРО ТОГО ОГРОМНОГО МАТЕРИАЛА О СОРТИРОВКЕ, 
КОТОРЫЙ ПОЯВИЛСЯ ЗА ПОСЛЕДНИЕ НЕСКОЛЬКО ЛЕТ.
\signed фЖ. ъ. їОСКЕН (1955)

%% 464
\chapter{яОИСК}
\epigraph
яОИЩЕМ ЗАПИСЬ
\signed {¤Л ёМИТ (1928)%
\note{1}{ёМИТ, рЛЬФРЕД ¤ММАНУЭЛЬ (1873--1944) --- АМЕРИКАНСКИЙ 
ПОЛИТИЧЕСКИЙ ДЕЯТЕЛЬ.---{\sl яРИМ. ПЕРЕВ.}}
}

¤ТУ ГЛАВУ МОЖНО БЫЛО НАЗВАТЬ ИНАЧЕ: ИЛИ ПРЕТЕНЦИОЗНО---"їРАНЕНИЕ И ВЫБОРКА 
ИНФОРМАЦИИ", ИЛИ ПРОСТО---"яОИСК ПО ТАБЛИЦАМ". эАС БУДЕТ ИНТЕРЕСОВАТЬ ПРОЦЕСС 
НАКОПЛЕНИЯ ИНФОРМАЦИИ В ПАМЯТИ ВЫЧИСЛИТЕЛЬНОЙ МАШИНЫ С ПОСЛЕДУЮЩИМ ВОЗМОЖНО 
БОЛЕЕ БЫСТРЫМ ИЗВЛЕЧЕНИЕМ ЭТОЙ ИНФОРМАЦИИ. шНОГДА МЫ СТАЛКИВАЕМСЯ СО СТОЛЬ 
БОЛЬШИМ ОБоЕМОМ ДАННЫХ, ЧТО РЕАЛЬНО ИСПОЛЬЗОВАТЬ ИХ ВСЕ НЕ МОЖЕМ. т ЭТОМ СЛУЧАЕ 
САМЫМ МУДРЫМ БЫЛО БЫ ЗАБЫТЬ И РАЗРУШИТЬ БОЛЬШУЮ ИХ ЧАСТЬ; НО НЕРЕДКО БЫВАЕТ 
ВАЖНО СОХРАНИТЬ И ТАК ОРГАНИЗОВАТЬ ИМЕЮЩИЕСЯ ФАКТЫ, ЧТОБЫ ОБЕСПЕЧИТЬ 
НАИБЫСТРЕЙШУЮ ИХ ВЫБОРКУ.

¤ТА ГЛАВА ПОСВЯЩЕНА В ОСНОВНОМ ИЗУЧЕНИЮ ОЧЕНЬ ПРОСТОЙ ПОИСКОВОЙ ЗАДАЧИ: КАК 
НАХОДИТЬ ДАННЫЕ, ХРАНЯЩИЕСЯ С ОПРЕДЕЛЕННОЙ ИДЕНТИФИКАЦИЕЙ. эАПРИМЕР, В 
ВЫЧИСЛИТЕЛЬНОЙ ЗАДАЧЕ НАМ МОЖЕТ ПОНАДОБИТЬСЯ НАЙТИ $f(x)$, ИМЕЯ $x$ И ТАБЛИЦУ 
ЗНАЧЕНИЙ ФУНКЦИИ $f$; В ЛИНГВИСТИЧЕСКОЙ МОЖЕТ ИНТЕРЕСОВАТЬ АНГЛИЙСКИЙ 
ЭКВИВАЛЕНТ ДАННОГО РУССКОГО СЛОВА.

тООБЩЕ БУДЕМ ПРЕДПОЛАГАТЬ, ЧТО ХРАНИТСЯ МНОЖЕСТВО ИЗ $N$ ЗАПИСЕЙ И НЕОБХОДИМО 
ОПРЕДЕЛИТЬ ПОЛОЖЕНИЕ СООТВЕТСТВУЮЩЕЙ ЗАПИСИ. ъАК И В СЛУЧАЕ СОРТИРОВКИ, 
ПРЕДПОЛОЖИМ, ЧТО КАЖДАЯ ЗАПИСЬ СОДЕРЖИТ СПЕЦИАЛЬНОЕ ПОЛЕ, КОТОРОЕ НАЗЫВАЕТСЯ 
\emph{КЛЮЧОМ}, ВОЗМОЖНО, ПОТОМУ, ЧТО МНОГИЕ ЛЮДИ ЕЖЕДНЕВНО ТРАТЯТ МАССУ ВРЕМЕНИ 
НА ПОИСК СВОИХ КЛЮЧЕЙ. ьЫ ОБЫЧНО ТРЕБУЕМ, ЧТОБЫ $N$ КЛЮЧЕЙ БЫЛИ РАЗЛИЧНЫ, ТАК 
ЧТО КАЖДЫЙ КЛЮЧ ОДНОЗНАЧНО ОПРЕДЕЛЯЕТ СВОЮ ЗАПИСЬ. ёОВОКУПНОСТЬ ВСЕХ ЗАПИСЕЙ 
НАЗЫВАЕТСЯ \dfn{ТАБЛИЦЕЙ} ИЛИ \dfn{ФАЙЛОМ}, ПРИЧЕМ ПОД ТАБЛИЦЕЙ, КАК ПРАВИЛО, 
ПОДРАЗУМЕВАЕТСЯ
%% 465
НЕБОЛЬШОЙ ФАЙЛ, А ФАЙЛОМ ОБЫЧНО НАЗЫВАЮТ БОЛЬШУЮ ТАБЛИЦУ. сОЛЬШОЙ ФАЙЛ, ИЛИ 
ГРУППА ФАЙЛОВ, ЧАСТО НАЗЫВАЕТСЯ \dfn{БАЗОЙ ДАННЫХ}.

т АЛГОРИТМАХ ПОИСКА ПРИСУТСТВУЕТ ТАК НАЗЫВАЕМЫЙ \dfn{АРГУМЕНТ ПОИСКА $K$}, И 
ЗАДАЧА СОСТОИТ В ОТЫСКАНИИ ЗАПИСИ, ИМЕЮЩЕЙ $K$ СВОИМ КЛЮЧОМ. ёУЩЕСТВУЮТ ДВЕ 
ВОЗМОЖНОСТИ ОКОНЧАНИЯ ПОИСКА: ЛИБО ПОИСК ОКАЗАЛСЯ \dfn{УДАЧНЫМ}, Т. Е. ПОЗВОЛИЛ 
ОПРЕДЕЛИТЬ ПОЛОЖЕНИЕ СООТВЕТСТВУЮЩЕЙ ЗАПИСИ, СОДЕРЖАЩЕЙ $K$, ЛИБО ОН ОКАЗАЛСЯ 
\emph{НЕУДАЧНЫМ}, Т. Е. ПОКАЗАЛ, ЧТО АРГУМЕНТ $K$ НЕ МОЖЕТ БЫТЬ НАЙДЕН НИ В 
ОДНОЙ ИЗ ЗАПИСЕЙ. яОСЛЕ НЕУДАЧНОГО ПОИСКА ИНОГДА ЖЕЛАТЕЛЬНО ВСТАВИТЬ В ТАБЛИЦУ 
НОВУЮ ЗАПИСЬ, СОДЕРЖАЩУЮ $K$; АЛГОРИТМ, КОТОРЫЙ ДЕЛАЕТ ЭТО, НАЗЫВАЕТСЯ 
АЛГОРИТМОМ "ПОИСКА С ВСТАВКОЙ". эЕКОТОРЫЕ ТЕХНИЧЕСКИЕ УСТРОЙСТВА, ИЗВЕСТНЫЕ КАК 
"АССОЦИАТИВНАЯ ПАМЯТЬ", РЕШАЮТ ПРОБЛЕМУ ПОИСКА АВТОМАТИЧЕСКИ АНАЛОГИЧНО 
ТОМУ, КАК ЭТО ДЕЛАЕТ ЧЕЛОВЕЧЕСКИЙ МОЗГ; МЫ ЖЕ БУДЕМ ИЗУЧАТЬ МЕТОДЫ ПОИСКА НА 
ОБЫЧНОЙ УНИВЕРСАЛЬНОЙ ВЫЧИСЛИТЕЛЬНОЙ МАШИНЕ.

їОТЯ ЦЕЛЬЮ ПОИСКА ЯВЛЯЕТСЯ ИНФОРМАЦИЯ, КОТОРАЯ СОДЕРЖИТСЯ В ЗАПИСИ, 
АССОЦИИРОВАННОЙ С КЛЮЧОМ $K$, В АЛГОРИТМАХ ЭТОЙ ГЛАВЫ ОБЫЧНО ИГНОРИРУЕТСЯ ВСЕ, 
КРОМЕ СОБСТВЕННО КЛЮЧЕЙ. т САМОМ ДЕЛЕ, ЕСЛИ ПОЛОЖЕНИЕ $K$ ОПРЕДЕЛЕНО, 
СООТВЕТСТВУЮЩИЕ ДАННЫЕ МОЖНО НАЙТИ. эАПРИМЕР, ЕСЛИ $K$ ВСТРЕТИЛСЯ В 
ЯЧЕЙКЕ~$|TABLE|+i$, АССОЦИИРОВАННЫЕ ДАННЫЕ (ИЛИ УКАЗАТЕЛЬ НА НИХ) МОГУТ 
НАХОДИТЬСЯ ПО АДРЕСУ $|TABLE|+i+1$, ИЛИ $|DATA|+i$ И Т. Д. ЄАКИМ 
ОБРАЗОМ, ПОДРОБНОСТИ, КАСАЮЩИЕСЯ ТОГО, ЧТО НУЖНО ДЕЛАТЬ, КОГДА НАЙДЕН КЛЮЧ $K$, 
МОЖНО СПОКОЙНО ОПУСТИТЬ.

тО МНОГИХ ПРОГРАММАХ ПОИСК ТРЕБУЕТ НАИБОЛЬШИХ ВРЕМЕННЫХ ЗАТРАТ, ТАК ЧТО ЗАМЕНА 
ПЛОХОГО МЕТОДА ПОИСКА НА ХОРОШИЙ ЧАСТО ВЕДЕТ К СУЩЕСТВЕННОМУ УВЕЛИЧЕНИЮ СКОРОСТИ 
РАБОТЫ. фЕЙСТВИТЕЛЬНО, НЕРЕДКО УДАЕТСЯ ТАК ОРГАНИЗОВАТЬ ДАННЫЕ ИЛИ СТРУКТУРУ 
ДАННЫХ, ЧТО ПОИСК ПОЛНОСТЬЮ ИСКЛЮЧАЕТСЯ, Т. Е. МЫ ВСЕГДА ЗНАЕМ ЗАРАНЕЕ, ГДЕ 
НАХОДИТСЯ НУЖНАЯ НАМ ИНФОРМАЦИЯ. ёВЯЗАННАЯ ПАМЯТЬ ЯВЛЯЕТСЯ ОБЩЕПРИНЯТЫМ МЕТОДОМ 
ДОСТИЖЕНИЯ ЭТОГО; НАПРИМЕР, В СПИСКЕ С ДВУМЯ СВЯЗЯМИ НЕТ НЕОБХОДИМОСТИ ИСКАТЬ 
ЭЛЕМЕНТ, СЛЕДУЮЩИЙ ЗА ДАННЫМ ИЛИ ПРЕДШЕСТВУЮЩИЙ ЕМУ. фРУГОЙ СПОСОБ ИЗБЕЖАТЬ 
ПОИСКА ОТКРЫВАЕТСЯ ПЕРЕД НАМИ, ЕСЛИ ПРЕДОСТАВЛЕНА СВОБОДА ВЫБОРА КЛЮЧЕЙ. 
ёДЕЛАЕМ ИХ ЧИСЛАМИ $\{1,2, \ldots, N\}$, И ТОГДА ЗАПИСЬ, СОДЕРЖАЩАЯ $K$, МОЖЕТ 
БЫТЬ ПРОСТО ПОМЕЩЕНА В ЯЧЕЙКУ $|TABLE|+K$. юБА ЭТИ СПОСОБА ИСПОЛЬЗОВАЛИСЬ ДЛЯ 
УСТРАНЕНИЯ ПОИСКА ИЗ АЛГОРИТМА ТОПОЛОГИЧЕСКОЙ СОРТИРОВКИ, ОБСУЖДАВШЕГОСЯ В 
П.~2.2.3. ЄЕМ НЕ МЕНЕЕ ВО МНОГИХ СЛУЧАЯХ ПОИСК НЕОБХОДИМ (НАПРИМЕР, КОГДА 
ОБоЕКТАМИ ТОПОЛОГИЧЕСКОЙ СОРТИРОВКИ ЯВЛЯЮТСЯ СИМВОЛИЧЕСКИЕ ИМЕНА, А НЕ ЧИСЛА), 
ТАК ЧТО ВЕСЬМА ВАЖНО ИМЕТЬ ЭФФЕКТИВНЫЕ АЛГОРИТМЫ ПОИСКА.

ьЕТОДЫ ПОИСКА МОЖНО КЛАССИФИЦИРОВАТЬ НЕСКОЛЬКИМИ СПОСОБАМИ. ьЫ МОГЛИ БЫ 
РАЗДЕЛИТЬ ИХ НА ВНУТРЕННИЙ И ВНЕШНИЙ
%% 466
ПОИСК В СООТВЕТСТВИИ С РАЗДЕЛЕНИЕМ АЛГОРИТМОВ СОРТИРОВКИ В ГЛ.~5 НА ВНУТРЕННЮЮ 
И ВНЕШНЮЮ СОРТИРОВКУ. шЛИ МЫ МОГЛИ БЫ РАЗЛИЧАТЬ СТАТИЧЕСКИЙ И ДИНАМИЧЕСКИЙ 
МЕТОДЫ ПОИСКА, ГДЕ "СТАТИЧЕСКИЙ" ОЗНАЧАЕТ, ЧТО СОДЕРЖИМОЕ ТАБЛИЦЫ ОСТАЕТСЯ 
НЕИЗМЕННЫМ (ТАК ЧТО ВАЖНО МИНИМИЗИРОВАТЬ ВРЕМЯ ПОИСКА, ПРЕНЕБРЕГАЯ ЗАТРАТАМИ НА 
ПЕРЕСТРОЙКУ ТАБЛИЦЫ), А "ДИНАМИЧЕСКИЙ" ОЗНАЧАЕТ, ЧТО ТАБЛИЦА ЯВЛЯЕТСЯ ОБоЕКТОМ 
ЧАСТЫХ ВСТАВОК (И, МОЖЕТ БЫТЬ, УДАЛЕНИЙ). ЄРЕТЬЯ ВОЗМОЖНАЯ СХЕМА КЛАССИФИЦИРУЕТ 
МЕТОДЫ ПОИСКА В СООТВЕТСТВИИ С ТЕМ, ОСНОВАНЫ ЛИ ОНИ НА СРАВНЕНИИ КЛЮЧЕЙ ИЛИ НА 
ЦИФРОВЫХ СВОЙСТВАХ КЛЮЧЕЙ, АНАЛОГИЧНО ТОМУ, КАК РАЗЛИЧАЮТСЯ СОРТИРОВКА С 
ПОМОЩЬЮ СРАВНЕНИЯ И СОРТИРОВКА С ПОМОЩЬЮ РАСПРЕДЕЛЕНИЯ. эАКОНЕЦ, МЫ МОГЛИ БЫ 
РАЗДЕЛИТЬ МЕТОДЫ ПОИСКА НА МЕТОДЫ, ИСПОЛЬЗУЮЩИЕ ИСТИННЫЕ КЛЮЧИ, И НА МЕТОДЫ, 
РАБОТАЮЩИЕ С ПРЕОБРАЗОВАННЫМИ КЛЮЧАМИ.

юРГАНИЗАЦИЯ ДАННОЙ ГЛАВЫ ЕСТЬ. В СУЩНОСТИ, КОМБИНАЦИЯ ДВУХ ПОСЛЕДНИХ СПОСОБОВ 
КЛАССИФИКАЦИИ. т \S~6.1 РАССМАТРИВАЮТСЯ МЕТОДЫ ПОСЛЕДОВАТЕЛЬНОГО ПОИСКА "В ЛОБ", 
А В \S~6.2 ОБСУЖДАЮТСЯ УЛУЧШЕНИЯ, КОТОРЫЕ МОЖНО ПОЛУЧИТЬ НА ОСНОВЕ СРАВНЕНИЙ 
МЕЖДУ КЛЮЧАМИ С ИСПОЛЬЗОВАНИЕМ АЛФАВИТНОГО ИЛИ ЧИСЛОВОГО ПОРЯДКА ДЛЯ УПРАВЛЕНИЯ 
РЕШЕНИЯМИ. т \S~6.3 РАССМАТРИВАЕТСЯ ЦИФРОВОЙ ПОИСК, А В \S~6.4 ОБСУЖДАЕТСЯ 
ВАЖНЫЙ КЛАСС МЕТОДОВ, НАЗЫВАЕМЫХ ХЕШИРОВАНИЕМ И ОСНОВАННЫХ НА АРИФМЕТИЧЕСКИХ 
ПРЕОБРАЗОВАНИЯХ ИСТИННЫХ КЛЮЧЕЙ. т КАЖДОМ ИЗ ЭТИХ ПАРАГРАФОВ РАССМАТРИВАЕТСЯ 
КАК ВНУТРЕННИЙ, ТАК И ВНЕШНИЙ ПОИСК, И ДЛЯ СТАТИЧЕСКОГО И ДЛЯ ДИНАМИЧЕСКОГО 
СЛУЧАЕВ; В КАЖДОМ ПАРАГРАФЕ ОТМЕЧАЮТСЯ СРАВНИТЕЛЬНЫЕ ДОСТОИНСТВА И НЕДОСТАТКИ 
РАЗЛИЧНЫХ АЛГОРИТМОВ.

ьЕЖДУ ПОИСКОМ И СОРТИРОВКОЙ СУЩЕСТВУЕТ ОПРЕДЕЛЕННАЯ ВЗАИМОСВЯЗЬ. эАПРИМЕР, 
РАССМОТРИМ СЛЕДУЮЩУЮ ЗАДАЧУ:
$$
\displaylines{
\hbox{фАНЫ ДВА МНОЖЕСТВА ЧИСЕЛ:}\cr
\hbox{$A=\{a_1, a_2, \ldots, a_m\}$ И $B=\{b_1, b_2, \ldots, b_n\}$;}\cr
\hbox{ОПРЕДЕЛИТЬ, ЯВЛЯЕТСЯ ЛИ $A$ ПОДМНОЖЕСТВОМ $B$, 
Т.~Е. $A\subseteq B$.}\cr
}
$$
эАПРАШИВАЮТСЯ ТРИ РЕШЕНИЯ, А ИМЕННО:
\enumerate
\li ёРАВНИВАТЬ КАЖДОЕ $a_i$ ПОСЛЕДОВАТЕЛЬНО СО ВСЕМИ $b_j$ ДО УСТАНОВЛЕНИЯ 
    СОВПАДЕНИЯ.
\li ёВЕСТИ ВСЕ $b_j$ В ТАБЛИЦУ, ЗАТЕМ ИСКАТЬ КАЖДОЕ $a_i$ ПО ТАБЛИЦЕ.
\li єПОРЯДОЧИТЬ $A$ И~$B$, ЗАТЕМ СОВЕРШИТЬ ОДИН ПОСЛЕДОВАТЕЛЬНЫЙ ПРОХОД ПО 
    ОБОИМ ФАЙЛАМ, ПРОВЕРЯЯ СООТВЕТСТВУЮЩИЕ УСЛОВИЯ.
\enumend
\noindent ъАЖДОЕ ИЗ ЭТИХ РЕШЕНИЙ ИМЕЕТ СВОИ ПРИВЛЕКАТЕЛЬНЫЕ СТОРОНЫ ДЛЯ 
РАЗЛИЧНЫХ ДИАПАЗОНОВ ЗНАЧЕНИЙ $m$ И $n$. фЛЯ РЕШЕНИЯ 1 ПОТРЕБУЕТСЯ 
ПРИБЛИЗИТЕЛЬНО $c_1mn$ ЕДИНИЦ ВРЕМЕНИ, ГДЕ $c_1$---НЕКОТОРАЯ КОНСТАНТА, А 
РЕШЕНИЕ 3 ЗАЙМЕТ ОКОЛО $c_2(m \log_2m+n\log_2n)$ ЕДИНИЦ, ГДЕ $c_2$---НЕКОТОРАЯ 
(Б\'ОЛЬШАЯ) КОНСТАНТА. яРИ ПОДХОДЯЩЕМ
%% 467
МЕТОДЕ ХЕШИРОВАНИЯ РЕШЕНИЕ 2 ПОТРЕБУЕТ ПРИМЕРНО $c_3m+c_4n$ ЕДИНИЦ ВРЕМЕНИ, ГДЕ 
$c_3$ И~$c_4$---НЕКОТОРЫЕ (ЕЩЕ Б\'ОЛЬШИЕ) КОНСТАНТЫ. ёЛЕДОВАТЕЛЬНО, РЕШЕНИЕ 1 
ХОРОШО ПРИ ОЧЕНЬ МАЛЫХ $m$ И~$n$, А ПРИ ВОЗРАСТАНИИ $m$ И $n$ ЛУЧШИМ БУДЕТ 
РЕШЕНИЕ 3. чАТЕМ, ПОКА $n$ НЕ ДОСТИГНЕТ РАЗМЕРОВ ВНУТРЕННЕЙ ПАМЯТИ, БОЛЕЕ 
ПРЕДПОЧТИТЕЛЬНО РЕШЕНИЕ 2; ПОСЛЕ ЭТОГО ОБЫЧНО РЕШЕНИЕ 3 СНОВА СТАНОВИТСЯ ЛУЧШЕ, 
ПОКА $n$ НЕ СДЕЛАЕТСЯ ЕЩЕ ГОРАЗДО БОЛЬШИМ. чНАЧИТ, МЫ ИМЕЕМ СИТУАЦИЮ, ГДЕ 
СОРТИРОВКА ИНОГДА ХОРОШО ЗАМЕНЯЕТ ПОИСК, А ПОИСК---СОРТИРОВКУ.

чАЧАСТУЮ СЛОЖНЫЕ ЗАДАЧИ ПОИСКА МОЖНО СВЕСТИ К БОЛЕЕ ПРОСТЫМ СЛУЧАЯМ, 
РАССМАТРИВАЕМЫМ ЗДЕСЬ. эАПРИМЕР, ПРЕДПОЛОЖИМ, ЧТО В РОЛИ КЛЮЧЕЙ ВЫСТУПАЮТ СЛОВА, 
КОТОРЫЕ МОГЛИ БЫТЬ СЛЕГКА ИСКАЖЕНЫ; МЫ ХОТЕЛИ БЫ НАЙТИ ПРАВИЛЬНУЮ ЗАПИСЬ, 
НЕСМОТРЯ НА ЭТУ ОШИБКУ. хСЛИ СДЕЛАТЬ ДВЕ КОПИИ ФАЙЛА, В ОДНОЙ ИЗ КОТОРЫХ КЛЮЧИ 
РАСПОЛОЖЕНЫ В ОБЫЧНОМ АЛФАВИТНОМ ПОРЯДКЕ, А В ДРУГОЙ ОНИ УПОРЯДОЧЕНЫ СПРАВА 
НАЛЕВО (КАК ЕСЛИ БЫ СЛОВА БЫЛИ ПРОЧИТАНЫ НАОБОРОТ), ИСКАЖЕННЫЙ АРГУМЕНТ ПОИСКА 
В БОЛЬШИНСТВЕ СЛУЧАЕВ СОВПАДАЕТ ДО ПОЛОВИНЫ СВОЕЙ ДЛИНЫ ИЛИ ДАЛЬШЕ С ЗАПИСЬЮ 
ОДНОГО ИЗ ЭТИХ ДВУХ ФАЙЛОВ. ьЕТОДЫ ПОИСКА, СОДЕРЖАЩИЕСЯ В \S~6.2 И~6.3, МОЖНО, 
СЛЕДОВАТЕЛЬНО, ПРИСПОСОБИТЬ ДЛЯ НАХОЖДЕНИЯ КЛЮЧА, КОТОРЫЙ БЫЛ, ВЕРОЯТНО, 
ИСКАЖЕН.

яОХОЖИЕ ЗАДАЧИ ПРИВЛЕКЛИ К СЕБЕ ЗАМЕТНОЕ ВНИМАНИЕ В СВЯЗИ С СОЗДАНИЕМ СИСТЕМ 
ПРЕДВАРИТЕЛЬНОГО ЗАКАЗА АВИАБИЛЕТОВ И В СВЯЗИ С ДРУГИМИ ПРИЛОЖЕНИЯМИ, КОГДА 
СУЩЕСТВУЕТ ЗНАЧИТЕЛЬНАЯ ВЕРОЯТНОСТЬ ИСКАЖЕНИЯ ИМЕНИ ЧЕЛОВЕКА ИЗ-ЗА 
НЕРАЗБОРЧИВОГО ПОЧЕРКА ИЛИ ПЛОХОЙ СЛЫШИМОСТИ. эУЖНО БЫЛО НАЙТИ ПРЕОБРАЗОВАНИЕ 
АРГУМЕНТА В НЕКИЙ КОД, СОБИРАЮЩЕЕ ВМЕСТЕ ВСЕ ВАРИАНТЫ ДАННОГО ИМЕНИ. ьЕТОД 
"Soundex", ОПИСЫВАЕМЫЙ НИЖЕ В ВИДЕ, В КОТОРОМ ОН ПРИМЕНЯЕТСЯ СЕЙЧАС, БЫЛ 
ПЕРВОНАЧАЛЬНО РАЗВИТ ьАРГАРЕТ ъ.~юУДЕЛЛ И ЁОБЕРТОМ ъ.~ЁАССЕЛОМ 
[СМ. U.~S.~Patents 1261167 (1918), 1435663 (1922)]; ОН НАШЕЛ ШИРОКОЕ ПРИМЕНЕНИЕ 
ДЛЯ КОДИРОВАНИЯ ФАМИЛИЙ.
\enumerate
\li юСТАВИТЬ ПЕРВУЮ БУКВУ; ВСЕ БУКВЫ А, Е, h, i, О, u, w, У, СТОЯЩИЕ НА ДРУГИХ 
    МЕСТАХ, ВЫЧЕРКНУТЬ.
\li юСТАВШИМСЯ БУКВАМ (КРОМЕ ПЕРВОЙ) ПРИСВОИТЬ СЛЕДУЮЩИЕ ЗНАЧЕНИЯ:
$$\matrix{ 
b, f, p, v \to 1; \hfill & l \to 4;\hfill \cr 
c, g, j, k, q, s, x, z \to 2; &  m, n \to 5;\cr
d, t \to 3; \hfill & r \to 0.\hfill\cr
}
$$
\li хСЛИ В ИСХОДНОМ ИМЕНИ (ПЕРЕД ШАГОМ 1) РЯДОМ СТОЯЛИ НЕСКОЛЬКО БУКВ С 
    ОДИНАКОВЫМИ КОДАМИ, ПРЕНЕБРЕЧЬ ВСЕМИ, КРОМЕ ПЕРВОЙ ИЗ ЭТОЙ ГРУППЫ.
\li фОПИСЫВАЯ В СЛУЧАЕ НАДОБНОСТИ НУЛИ ИЛИ ОПУСКАЯ ЛИШНИЕ ЦИФРЫ, ПРЕОБРАЗОВАТЬ 
    ПОЛУЧЕННОЕ ВЫРАЖЕНИЕ В ФОРМУ "БУКВА, ЦИФРА, ЦИФРА, ЦИФРА".
%% 468
\enumend
\noindent эАПРИМЕР, ФАМИЛИИ Euler, Gauss, Hilbert, Knuth, Lloyd 
И~{\L}ukasiewicz ИМЕЮТ КОДЫ СООТВЕТСТВЕННО х460, G200, H416, K530, L300, L222. 
ЁАЗУМЕЕТСЯ, ТАКАЯ СИСТЕМА СОБИРАЕТ ВМЕСТЕ НЕ ТОЛЬКО РОДСТВЕННЫЕ, НО И 
ДОСТАТОЧНО РАЗЛИЧНЫЕ ИМЕНА. яРИВЕДЕННЫЕ ВЫШЕ ШЕСТЬ КОДОВ МОГЛИ БЫТЬ ПОЛУЧЕНЫ ИЗ 
ФАМИЛИЙ Ellery, Ghosh, Heilbronn, Kant, Ladd И Lissajous. ё ДРУГОЙ СТОРОНЫ, 
ТАКИЕ РОДСТВЕННЫЕ ИМЕНА, КАК Rogers И Rodgers, Sinclair И St.~Clair ИЛИ 
Tchebysheff И Chebyshev, ИМЕЮТ РАЗНУЮ КОДИРОВКУ. эО, ВООБЩЕ ГОВОРЯ, СИСТЕМА 
"Soundex" НАМНОГО УВЕЛИЧИВАЕТ ВЕРОЯТНОСТЬ ОБНАРУЖИТЬ ИМЯ ПОД ОДНОЙ ИЗ ЕГО 
МАСОК. [фЛЯ ДАЛЬНЕЙШЕГО ОЗНАКОМЛЕНИЯ, СМ. 
ё. Ё. Bourne, D. F. Ford, {\sl JACM\/}, {\bf 8} (1961), 538--552; 
Leon Davidson, {\sl CACM\/}, {\bf 5} (1962), 169--171; 
Federal Population Censuses, 1790--1890 (Washington, D. ё.: National Archives, 
1971), 90.]

ъОГДА МЫ ИСПОЛЬЗУЕМ СИСТЕМЫ ТИПА "Soundex", НЕТ НЕОБХОДИМОСТИ ПРЕДПОЛАГАТЬ, ЧТО 
ВСЕ КЛЮЧИ РАЗЛИЧНЫ; МОЖНО СОСТАВИТЬ СПИСКИ ИЗ ЗАПИСЕЙ С СОВПАДАЮЩИМИ КОДАМИ, 
РАССМАТРИВАЯ КАЖДЫЙ СПИСОК КАК ОБоЕКТ ПОИСКА.

яРИ ИСПОЛЬЗОВАНИИ БОЛЬШИХ БАЗ ДАННЫХ ВЫБОРКА ИНФОРМАЦИИ НАМНОГО УСЛОЖНЯЕТСЯ, 
ТАК КАК ЧАСТО ЖЕЛАТЕЛЬНО РАССМАТРИВАТЬ РАЗЛИЧНЫЕ ПОЛЯ КАЖДОЙ ЗАПИСИ КАК 
ПОТЕНЦИАЛЬНЫЕ КЛЮЧИ. чДЕСЬ ВАЖНО УМЕТЬ НАХОДИТЬ ЗАПИСИ ПО НЕПОЛНОЙ КЛЮЧЕВОЙ 
ИНФОРМАЦИИ. эАПРИМЕР, ИМЕЯ БОЛЬШОЙ ФАЙЛ АКТЕРОВ, РЕЖИССЕР МОГ БЫ ПОЖЕЛАТЬ 
НАЙТИ ВСЕХ НЕЗАНЯТЫХ АКТРИС В ВОЗРАСТЕ 25--30 ЛЕТ, ХОРОШО ТАНЦУЮЩИХ И ГОВОРЯЩИХ 
С ФРАНЦУЗСКИМ АКЦЕНТОМ; У СПОРТИВНОГО ЖУРНАЛИСТА МОЖЕТ ВОЗНИКНУТЬ ЖЕЛАНИЕ 
ПОДСЧИТАТЬ С ПОМОЩЬЮ ФАЙЛА БЕЙСБОЛЬНОЙ СТАТИСТИКИ ОБЩЕЕ ЧИСЛО ОЧКОВ, НАБРАННЫХ 
ПОДАЮЩИМИ-ЛЕВШАМИ КОМАНДЫ "ъРАСНОНОГИЕ ИЗ ЎИНЦИНАТТИ" В ТЕЧЕНИЕ СЕДЬМЫХ 
ПЕРИОДОВ ВЕЧЕРНИХ ИГР ЗА 1964~Г. шМЕЯ БОЛЬШОЙ ФАЙЛ ДАННЫХ О ЧЕМ-ЛИБО, 
ЛЮДИ ЛЮБЯТ ЗАДАВАТЬ ВОПРОСЫ ПРОИЗВОЛЬНОЙ СЛОЖНОСТИ. эА САМОМ ДЕЛЕ МЫ МОГЛИ БЫ 
РАССМАТРИВАТЬ ПОЛНУЮ БИБЛИОТЕКУ КАК БАЗУ ДАННЫХ, В КОТОРОЙ НЕКТО ЖЕЛАЕТ НАЙТИ 
ВСЕ ПУБЛИКАЦИИ О ВЫБОРКЕ ИНФОРМАЦИИ. тВЕДЕНИЕ В МЕТОДЫ 
\emph{ПОИСКА ПО МНОГИМ ПРИЗНАКАМ} ПОМЕЩЕНО В \S~6.5.

яРЕЖДЕ ЧЕМ ПЕРЕХОДИТЬ К ДЕТАЛЬНОМУ ИЗУЧЕНИЮ ПОИСКА, ПОЛЕЗНО РАССМОТРЕТЬ 
ИСТОРИЮ ДАННОГО ВОПРОСА. т ДОКОМПЬЮТЕРНЫЙ ПЕРИОД БЫЛО СОСТАВЛЕНО МНОЖЕСТВО 
ТОМОВ ЛОГАРИФМИЧЕСКИХ, ТРИГОНОМЕТРИЧЕСКИХ И ДРУГИХ ТАБЛИЦ, ТАК ЧТО 
МАТЕМАТИЧЕСКИЕ ВЫЧИСЛЕНИЯ МОГЛИ БЫТЬ ЗАМЕНЕНЫ ПОИСКОМ. яОТОМ ЭТИ ТАБЛИЦЫ БЫЛИ 
ПЕРЕНЕСЕНЫ НА ПЕРФОКАРТЫ И ИСПОЛЬЗОВАЛИСЬ ДЛЯ НАУЧНЫХ ЗАДАЧ ПОСРЕДСТВОМ 
РАСПОЗНАЮЩИХ, СОРТИРОВАЛЬНЫХ И ДУБЛИРУЮЩИХ ПЕРФОРАТОРНЫХ МАШИН. юДНАКО ПОСЛЕ 
ПОЯВЛЕНИЯ ¤ть С ЗАПОМИНАЕМОЙ ПРОГРАММОЙ СТАЛО ОЧЕВИДНО, ЧТО ДЕШЕВЛЕ КАЖДЫЙ РАЗ 
ВЫЧИСЛЯТЬ $\log x$ И~$\cos x$, НЕЖЕЛИ ИСКАТЬ ОТВЕТ ПО ТАБЛИЦЕ.

эЕСМОТРЯ НА ТО, ЧТО ЗАДАЧА СОРТИРОВКИ ПРИВЛЕКЛА ПРИСТАЛЬНОЕ
%% 469
ВНИМАНИЕ УЖЕ НА ЗАРЕ РАЗВИТИЯ ¤ть, ДЛЯ РАЗРАБОТКИ АЛГОРИТМОВ ПОИСКА БЫЛО 
СДЕЛАНО СРАВНИТЕЛЬНО МАЛО. ЁАСПОЛАГАЯ НЕБОЛЬШОЙ ВНУТРЕННЕЙ ПАМЯТЬЮ И ТОЛЬКО 
ПОСЛЕДОВАТЕЛЬНЫМИ УСТРОЙСТВАМИ ТИПА ЛЕНТ ДЛЯ ХРАНЕНИЯ БОЛЬШИХ ФАЙЛОВ, 
ОРГАНИЗОВАТЬ ПОИСК БЫЛО ЛИБО СОВЕРШЕННО ТРИВИАЛЬНО, ЛИБО ПОЧТИ НЕВОЗМОЖНО.

эО РАЗВИТИЕ ВСЕ БОЛЬШЕЙ И БОЛЬШЕЙ ПАМЯТИ СО СЛУЧАЙНЫМ ДОСТУПОМ В ТЕЧЕНИЕ 50-Х 
ГОДОВ ПРИВЕЛО К ПОНИМАНИЮ ТОГО, ЧТО ПОИСК КАК ТАКОВОЙ ЯВЛЯЕТСЯ ИНТЕРЕСНОЙ 
ЗАДАЧЕЙ. яОСЛЕ ПЕРИОДА ЖАЛОБ НА ОГРАНИЧЕННЫЕ РЕСУРСЫ ПРОСТРАНСТВА В РАННИХ 
МАШИНАХ ПРОГРАММИСТЫ ВДРУГ СТОЛКНУЛИСЬ С ТАКИМ ОБоЕМОМ ПАМЯТИ, КОТОРЫЙ ОНИ НЕ 
УМЕЛИ ЭФФЕКТИВНО ИСПОЛЬЗОВАТЬ.

яЕРВЫЕ ОБЗОРЫ ЗАДАЧ ПОИСКА БЫЛИ ОПУБЛИКОВАНЫ 
р.~ш.~фУМИ [{\sl Computers \& Automation\/}, {\bf 5}, 12 (December 1956), 6--9], 
є.~є.~яЕТЕРСОНОМ [{\sl IBM J. Research \& Development}, {\bf 1}  (1957), 130--146], 
¤.~ф.~сУТОМ [{\sl Information and Control\/}, {\bf 1} (1958), 159--164], 
р.~°.~фУГЛАСОМ [{\sl Comp. J.\/}, {\bf 2} (1959), 1--9]. 
сОЛЕЕ ПОДРОБНЫЙ ОБЗОР СДЕЛАН ПОЗДНЕЕ 
ъ.~¤.~рЙВЕРСОНОМ [A Programming Language (New York: Wiley, (1962)), 133--158] И 
т.~сУХХОЛЬЦЕМ [{\sl IBM Systems J.\/}, {\bf 2} (1963), 86--111].

т НАЧАЛЕ 60-Х ГОДОВ БЫЛО РАЗРАБОТАНО НЕСКОЛЬКО НОВЫХ АЛГОРИТМОВ ПОИСКА, 
ОСНОВАННЫХ НА ИСПОЛЬЗОВАНИИ ДРЕВОВИДНЫХ СТРУКТУР; С НИМИ МЫ ПОЗНАКОМИМСЯ НИЖЕ. 
ш В НАШЕ ВРЕМЯ ВЕДУТСЯ АКТИВНЫЕ ИССЛЕДОВАНИЯ ПО ПРОБЛЕМАМ ПОИСКА.
%% 470
\subchap{яОСЛЕДОВАТЕЛЬНЫЙ ПОИСК}
"эАЧНИ С НАЧАЛА И ПРОДВИГАЙСЯ, ПОКА НЕ НАЙДЕШЬ НУЖНЫЙ КЛЮЧ; ТОГДА ОСТАНОВИСЬ". 
ЄАКАЯ ПОСЛЕДОВАТЕЛЬНАЯ ПРОЦЕДУРА ЯВЛЯЕТСЯ ОЧЕВИДНЫМ СПОСОБОМ ПОИСКА; УДОБНО 
НАЧАТЬ НАШИ РАССМОТРЕНИЯ С НЕЕ, ТАК КАК НА НЕЙ ОСНОВАНЫ МНОГИЕ БОЛЕЕ СЛОЖНЫЕ 
АЛГОРИТМЫ. эЕСМОТРЯ НА СВОЮ ПРОСТОТУ, ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК СОДЕРЖИТ РЯД 
ОЧЕНЬ ИНТЕРЕСНЫХ ИДЕЙ.

ёФОРМУЛИРУЕМ АЛГОРИТМ БОЛЕЕ ТОЧНО.
\alg S.(яОСЛЕДОВАТЕЛЬНЫЙ ПОИСК.) шМЕЕТСЯ ТАБЛИЦА ЗАПИСЕЙ 
$R_1$, $R_2$, \dots, $R_3$, СНАБЖЕННЫХ СООТВЕТСТВЕННО КЛЮЧАМИ 
$K_1$,  $K_2$, \dots, $K_n$ рЛГОРИТМ ПРЕДНАЗНАЧЕН ДЛЯ 
ПОИСКА ЗАПИСИ С ДАННЫМ КЛЮЧОМ $K$. яРЕДПОЛАГАЕТСЯ, ЧТО $N\ge 1$.
\st [эАЧАЛЬНАЯ УСТАНОВКА.] єСТАНОВИТЬ $i \asg 1$.
\st [ёРАВНЕНИЕ.] хСЛИ $K=K_i$, АЛГОРИТМ ОКАНЧИВАЕТСЯ УДАЧНО.
\st [яРОДВИЖЕНИЕ.] єВЕЛИЧИТЬ $i$ НА 1.
\st [ъОНЕЦ ФАЙЛА?] хСЛИ $i\le N$, ТО ВЕРНУТЬСЯ К ШАГУ \stp{2}.
т ПРОТИВНОМ СЛУЧАЕ АЛГОРИТМ ОКАНЧИВАЕТСЯ НЕУДАЧНО. 
\algend

чАМЕТИМ, ЧТО У ЭТОГО АЛГОРИТМА МОЖЕТ БЫТЬ ДВА РАЗНЫХ ИСХОДА: \emph{УДАЧНЫЙ} 
(КОГДА НАЙДЕНО ПОЛОЖЕНИЕ НУЖНОГО КЛЮЧА) И 
\picture{яОСЛЕДОВАТЕЛЬНЫЙ ПОИСК}
\emph{НЕУДАЧНЫЙ} (КОГДА, УСТАНОВЛЕНО, ЧТО ИСКОМОГО АРГУМЕНТА НЕТ В ТАБЛИЦЕ). 
¤ТО СПРАВЕДЛИВО ДЛЯ БОЛЬШИНСТВА АЛГОРИТМОВ ДАННОЙ ГЛАВЫ.

ЁЕАЛИЗАЦИЯ В ВИДЕ ПРОГРАММЫ ДЛЯ МАШИНЫ MIX ОЧЕВИДНА.
\prog S.(яОСЛЕДОВАТЕЛЬНЫЙ ПОИСК.) яРЕДПОЛОЖИМ, ЧТО $K_i$ ХРАНИТСЯ ПО АДРЕСУ 
$|KEY|+i$, А ОСТАВШАЯСЯ ЧАСТЬ ЗАПИСИ $R_i$---ПО АДРЕСУ $|INFO|+i$. 
яРИВОДИМАЯ НИЖЕ ПРОГРАММА ИСПОЛЬЗУЕТ $|rA|\equiv K$, $|rI1|\equiv i-N$.
%% 471
\code
START     &  LDA     & K           & 1    & S1. эАЧАЛЬНАЯ УСТАНОВКА. 
          &  ENT1    &             & 1    & $i\asg 1$.
2H        &  ёьЁр    & KEY+N, 1    & ё    & S2. ёРАВНЕНИЕ.
          &   JE     & SUCCESS     & ё    & тЫХОД, ЕСЛИ $K=K_i$. 
          & INC1     & 1           & C-S  & S3.яРОДВИЖЕНИЕ.
          & J1NP     & 2т          & C-S  & S4. ъОНЕЦ ФАЙЛА? 
 FAILURE  &  EQU     & *           &1-S   & тЫХОД, ЕСЛИ НЕТ В ТАБЛИЦЕ. 
\endcode
яО АДРЕСУ |SUCCESS| РАСПОЛОЖЕНА КОМАНДА "|LDA INFO+N,1|";
ОНА ПОМЕЩАЕТ НУЖНУЮ ИНФОРМАЦИЮ В |rA|.
\progend
рНАЛИЗ ДАННОЙ ПРОГРАММЫ НЕ ПРЕДСТАВЛЯЕТ ТРУДА; ВИДНО, ЧТО ВРЕМЯ РАБОТЫ 
АЛГОРИТМА S ЗАВИСИТ ОТ ДВУХ ПАРАМЕТРОВ:
$$
\eqalign{
C=&\hbox{ (КОЛИЧЕСТВО СРАВНЕНИЙ КЛЮЧЕЙ)};\cr
S=&1\ \hbox{ПРИ УДАЧЕ И 0 ПРИ НЕУДАЧЕ}.\cr
}\eqno (1)
$$
яРОГРАММА S ТРЕБУЕТ $5C-2S+3$ ЕДИНИЦ ВРЕМЕНИ. хСЛИ МЫ НАШЛИ $K=K_i$, 
ТО $C=i$, $S=1$; ЗНАЧИТ, ПОЛНОЕ ВРЕМЯ РАВНО $(5i+l)u$. хСЛИ ЖЕ ПОИСК 
ОКАЗАЛСЯ НЕУДАЧНЫМ, ТО $C=N$, $S=0$, А РАБОТАЛА ПРОГРАММА РОВНО $(5N+3)u$. 
хСЛИ ВСЕ КЛЮЧИ ПОСТУПАЮТ НА ВХОД С РАВНОЙ ВЕРОЯТНОСТЬЮ, ТО СРЕДНЕЕ 
ЗНАЧЕНИЕ~$C$ ПРИ УДАЧНОМ ПОИСКЕ СОСТАВЛЯЕТ
$$
{1+2+\cdots+N\over N}={N+1\over 2};
\eqno(2)
$$
СРЕДНЕКВАДРАТИЧНОЕ ОТКЛОНЕНИЕ $C$, РАЗУМЕЕТСЯ, ДОВОЛЬНО БОЛЬШОЕ---ПРИМЕРНО 
$0.289N$ (СМ. УПР. 1).

яРИВЕДЕННЫЙ, АЛГОРИТМ, НЕСОМНЕННО, ЗНАКОМ ВСЕМ ПРОГРАММИСТАМ. эО МАЛО КТО 
ЗНАЕТ, ЧТО ЭТОТ СПОСОБ РЕАЛИЗАЦИИ ПОСЛЕДОВАТЕЛЬНОГО ПОИСКА НЕ ВСЕГДА САМЫЙ 
ЛУЧШИЙ! юЧЕВИДНОЕ ИЗМЕНЕНИЕ УБЫСТРЯЕТ РАБОТУ АЛГОРИТМА (ЕСЛИ ТОЛЬКО ЗАПИСЕЙ 
НЕ СЛИШКОМ МАЛО):

\alg Q.(сЫСТРЫЙ ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК). т ОТЛИЧИЕ ОТ АЛГОРИТМА S ЗДЕСЬ ЕЩЕ 
ПРЕДПОЛАГАЕТСЯ, ЧТО В КОНЦЕ ФАЙЛА СТОИТ ФИКТИВНАЯ ЗАПИСЬ $R_{N+1}$.
\st [эАЧАЛЬНАЯ УСТАНОВКА.] єСТАНОВИТЬ $i\asg 1$  И~$K_{N+1}\asg K$.
\st [ёРАВНЕНИЕ.] хСЛИ $K=K_i$, ТО ПЕРЕЙТИ НА \stp{4}.
\st [яРОДВИЖЕНИЕ.] єВЕЛИЧИТЬ $i$ НА 1 И ВЕРНУТЬСЯ К ШАГУ \stp{2}.
\st [ъОНЕЦ ФАЙЛА?] хСЛИ $i\le N$, АЛГОРИТМ ОКАНЧИВАЕТСЯ УДАЧНО;
В ПРОТИВНОМ СЛУЧАЕ---НЕУДАЧНО $(i=N+1)$.
\algend

\prog Q.(сЫСТРЫЙ ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК.) чНАЧЕНИЯ РЕГИСТРОВ: 
$|rA| \equiv K$, $|rI1|\equiv i-N$.
%%472
\code
 BEGIN   & LDA   & ъ       & 1     & Q1. эАЧАЛЬНАЯ УСТАНОВКА
         & STA   & KEY+N+1 & 1     & $K_{N+1}\asg K$.
         & ENT1  & -N      & 1     & $i\asg 0$.
         & INC1  & 1       & C+1-S & Q3. яРОДВИЖЕНИЕ.
         & ёьЁр  & KEY+N, 1& C+l-S & Q2. ёРАВНЕНИЕ.
         & JNE   & *-2     & C+1-S & эА Q3, ЕСЛИ $K_i\ne K$.
         & J1NP  & SUCCESS &   1   & Q4. ъОНЕЦ ФАЙЛА?
 FAILURE & EQU   & *       & 1-S   & тЫХОД, ЕСЛИ НЕТ В ТАБЛИЦЕ.
\endcode\progend
шСПОЛЬЗУЯ ПАРАМЕТРЫ $C$ И~$S$, ВВЕДЕННЫЕ ПРИ АНАЛИЗЕ 
ПРОГРАММЫ $S$, МОЖНО ЗАКЛЮЧИТЬ, ЧТО ВРЕМЯ РАБОТЫ ПРОГРАММЫ 
УМЕНЬШИЛОСЬ ДО $(4C-4S+10)u$; ЭТО ДАЕТ УЛУЧШЕНИЕ ПРИ $C\ge5$ 
(ДЛЯ УДАЧНОГО ПОИСКА) И ПРИ $N\ge 8$ (ДЛЯ НЕУДАЧНОГО ПОИСКА).
яРИ ПЕРЕХОДЕ ОТ АЛГОРИТМА S К АЛГОРИТМУ Q ИСПОЛЬЗОВАН ВАЖНЫЙ УСКОРЯЮЩИЙ 
ПРИНЦИП: ЕСЛИ ВО ВНУТРЕННЕМ ЦИКЛЕ ПРОГРАММЫ ПРОВЕРЯЮТСЯ ДВА ИЛИ БОЛЕЕ УСЛОВИЯ, 
НУЖНО ПОСТАРАТЬСЯ ОСТАВИТЬ ТАМ ТОЛЬКО ОДНО СРАВНЕНИЕ.
ёУЩЕСТВУЕТ СПОСОБ СДЕЛАТЬ ПРОГРАММУ Q \emph{ЕЩЕ} БЫСТРЕЕ.
\prog Q'.(ёВЕРХБЫСТРЫЙ ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК.) чНАЧЕНИЯ 
РЕГИСТРОВ: $|rA|=K$,  $|rI1|\equiv i-N$.
\code	
 BEGIN   &LDA   &ъ           &1        & Q1. эАЧАЛЬНАЯ УСТАНОВКА.
         &STA   &KEY + N +1  &1        &$K_{N+1}\asg K$. 
         &ENT1  &-1-N        &1        &$i\asg -1$. 
3H       &INC1  &2           &\lfloor(C-S+2)/2\rfloor & Q3. яРОДВИЖЕНИЕ. (фВОЙНОЕ.) 
         &ёьЁр  &KEY+N, 1    &\lfloor(C-S+2)/2\rfloor & Q2. ёРАВНЕНИЕ.
         &JE    &4F          &\lfloor(C-S+2)/2\rfloor & эА Q4, ЕСЛИ $K=K_i$. 
         &ёьЁр  &KEY+N+1,1   &\lfloor(C-S+1)/2\rfloor & Q2. ёРАВНЕНИЕ. (ёЛЕДУЮЩЕЕ.) 
         &JNE   &3B          &\lfloor(C-S+1)/2\rfloor & эА Q3, ЕСЛИ $K\ne K_{i+1}$. 
         &INC1  &1           &(C-5)\bmod 2            &яРОДВИНУТЬ $i$.	
4H       &J1NP  &SUCCESS     &       1                & Q4. ъОНЕЦ ФАЙЛА? 
FAILURE  &EQU   &*           &1-S                     &тЫХОД, ЕСЛИ НЕТ В ТАБЛИЦЕ. 
\endcode
\progend
шНСТРУКЦИИ ВНУТРЕННЕГО ЦИКЛА ВЫПИСАНЫ ДВАЖДЫ; ЭТО ИСКЛЮЧАЕТ ПРИМЕРНО ПОЛОВИНУ 
ОПЕРАТОРОВ "$i\asg i+1$". ЄАКИМ ОБРАЗОМ, ВРЕМЯ ВЫПОЛНЕНИЯ ПРОГРАММЫ УМЕНЬШИЛОСЬ 
ДО
$$
3.5C-3.5S+10{(C-S)\bmod 2\over 2}
$$
ЕДИНИЦ. яРИ ПОИСКЕ ПО БОЛЬШИМ ТАБЛИЦАМ ПРОГРАММА Q' НА 30\% БЫСТРЕЕ 
ПРОГРАММЫ S; ПОДОБНЫМ ОБРАЗОМ МОГУТ БЫТЬ УЛУЧШЕНЫ МНОГИЕ СУЩЕСТВУЮЩИЕ 
ПРОГРАММЫ. хСЛИ ИЗВЕСТНО, ЧТО КЛЮЧИ РАСПОЛОЖЕНЫ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ, 
ПОЛЕЗНО НЕСКОЛЬКО ИЗМЕНИТЬ АЛГОРИТМ.

%% 473
\alg Є.(яОСЛЕДОВАТЕЛЬНЫЙ ПОИСК В УПОРЯДОЧЕННОЙ ТАБЛИЦЕ.) шМЕЕТСЯ ТАБЛИЦА 
ЗАПИСЕЙ $R_1$, $R_2$, \dots, $R_N$, ПРИЧЕМ КЛЮЧИ УДОВЛЕТВОРЯЮТ НЕРАВЕНСТВАМ 
$K_1<K_2<\ldots<K_N$. рЛГОРИТМ ПРЕДНАЗНАЧАЕТСЯ ДЛЯ ПОИСКА ДАННОГО КЛЮЧА $K$. 
т ЦЕЛЯХ УДОБСТВА И УВЕЛИЧЕНИЯ СКОРОСТИ РАБОТЫ ПРЕДПОЛАГАЕТСЯ, ЧТО В КОНЦЕ 
ТАБЛИЦЫ РАСПОЛОЖЕНА ФИКТИВНАЯ ЗАПИСЬ $R_{N+1}$, КЛЮЧ КОТОРОЙ 
$K_{N+1}=\infty>K$.
\st [эАЧАЛЬНАЯ УСТАНОВКА.] єСТАНОВИТЬ $i\asg1$.
\st [ёРАВНЕНИЕ.] хСЛИ $K\le K_i$, ТО ПЕРЕЙТИ НА \stp{4}.
\st [яРОДВИЖЕНИЕ.] єВЕЛИЧИТЬ $i$ НА 1 И ВЕРНУТЬСЯ К ШАГУ \stp{2}.
\st [ЁАВЕНСТВО?] хСЛИ $K=K_i$, ТО АЛГОРИТМ ОКАНЧИВАЕТСЯ УДАЧНО.
т ПРОТИВНОМ СЛУЧАЕ---НЕУДАЧНО, НУЖНОЙ ЗАПИСИ В ТАБЛИЦЕ НЕТ.
\algend

хСЛИ ВЕЛИЧИНА $K$ С РАВНОЙ ВЕРОЯТНОСТЬЮ ПРИНИМАЕТ ВСЕ ВОЗМОЖНЫЕ ЗНАЧЕНИЯ, ТО В 
СЛУЧАЕ УДАЧНОГО ПОИСКА АЛГОРИТМ T, ПО СУЩЕСТВУ, НЕ ЛУЧШЕ АЛГОРИТМА Q. юДНАКО 
ОТСУТСТВИЕ НУЖНОЙ ЗАПИСИ АЛГОРИТМ Є ДОЗВОЛЯЕТ ОБНАРУЖИТЬ ПРИМЕРНО В ДВА РАЗА 
БЫСТРЕЕ.

яРИВЕДЕННЫЕ ВЫШЕ АЛГОРИТМЫ В ЦЕЛЯХ УДОБСТВА ИСПОЛЬЗОВАЛИ ИНДЕКСНЫЕ ОБОЗНАЧЕНИЯ 
ДЛЯ ЭЛЕМЕНТОВ ТАБЛИЦЫ; АНАЛОГИЧНЫЕ ПРОЦЕДУРЫ ПРИМЕНИМЫ И К ТАБЛИЦАМ В СВЯЗАННОМ 
ПРЕДСТАВЛЕНИИ, ТАК КАК В НИХ ДАННЫЕ ТОЖЕ РАСПОЛОЖЕНЫ ПОСЛЕДОВАТЕЛЬНО. 
(ёМ. УПР.~2, 3 И 4.)

\section ўАСТОТА ОБРАЩЕНИЙ. фО СИХ ПОР ПРЕДПОЛАГАЛОСЬ, ЧТО С РАВНОЙ 
ВЕРОЯТНОСТЬЮ МОЖЕТ ПОТРЕБОВАТЬСЯ ПОИСК ЛЮБОГО АРГУМЕНТА, ОДНАКО ЧАСТО ТАКОЕ 
ПРЕДПОЛОЖЕНИЕ НЕ ПРАВОМЕРНО; ВООБЩЕ ГОВОРЯ, КЛЮЧ $K_j$ БУДЕТ РАЗЫСКИВАТЬСЯ С 
ВЕРОЯТНОСТЬЮ $p_i$, ГДЕ $p_1+p_2+\cdots+p_N=1$. тРЕМЯ УДАЧНОГО ПОИСКА ПРИ 
БОЛЬШИХ $N$ ПРОПОРЦИОНАЛЬНО ЧИСЛУ СРАВНЕНИЙ $C$, СРЕДНЕЕ .ЗНАЧЕНИЕ КОТОРОГО 
РАВНО
$$
\overline{C}_N=p_1+2p_2+\cdots+Np_N.
\eqno(3)
$$
яУСТЬ ЕСТЬ ВОЗМОЖНОСТЬ ПОМЕЩАТЬ ЗАПИСИ В ТАБЛИЦУ В ЛЮБОМ ПОРЯДКЕ; ТОГДА 
ВЕЛИЧИНА $\overline{C}_N$  МИНИМАЛЬНА ПРИ
$$
p_1\ge p_2\ge \ldots \ge p_N,
\eqno (4)
$$
Т. Е. КОГДА НАИБОЛЕЕ ЧАСТО ИСПОЛЬЗУЕМЫЕ ЗАПИСИ РАСПОЛОЖЕНЫ В НАЧАЛЕ ТАБЛИЦЫ.

яОСМОТРИМ, ЧТО ДАЕТ НАМ ТАКОЕ "ОПТИМАЛЬНОЕ" РАСПОЛОЖЕНИЕ ПРИ РАЗЛИЧНЫХ 
РАСПРЕДЕЛЕНИЯХ ВЕРОЯТНОСТЕЙ. хСЛИ $p_1=p_2=\ldots=p_N=1/N$,  ТО ФОРМУЛА (3) 
СВОДИТСЯ К $\overline{C}_N=(N+1)/2$, ЧТО УЖЕ БЫЛО ПОЛУЧЕНО НАМИ В (2). 
яРЕДПОЛОЖИМ ТЕПЕРЬ, ЧТО
$$
p_1={1\over2}, p_2={1\over 4}, \ldots, p_{N-1}={1\over2^{N-1}}, p_{N}={1\over2^{N-1}}
\eqno(5)
$$
%% 474
ёОГЛАСНО УПР. 7, $\overline{C}_N=2-2^{1-N}$; СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ 
МЕНЬШЕ ДВУХ, ЕСЛИ ЗАПИСИ РАСПОЛОЖЕНЫ В НАДЛЕЖАЩЕМ ПОРЯДКЕ. фРУГИМ 
НАПРАШИВАЮЩИМСЯ РАСПРЕДЕЛЕНИЕМ ЯВЛЯЕТСЯ
$$
p_1=N_c, p_2=(N-1)c, \ldots, p_N=c,
$$
ГДЕ
$$
c=2/N(N+1).
\eqno(6)
$$
¤ТО "КЛИНОВИДНОЕ" РАСПРЕДЕЛЕНИЕ ДАЕТ БОЛЕЕ ПРИВЫЧНЫЙ РЕЗУЛЬТАТ
$$
\overline{C}_N=c\sum_{1\le k\le N} k\cdot(N+1-k)={N+2\over 2};
\eqno(7)
$$
ОПТИМАЛЬНОЕ РАСПОЛОЖЕНИЕ ЭКОНОМИТ ОКОЛО ТРЕТИ ПОИСКОВОГО ВРЕМЕНИ, 
ТРЕБУЮЩЕГОСЯ ДЛЯ ЗАПИСЕЙ В СЛУЧАЙНОМ ПОРЯДКЕ.

ЁАЗУМЕЕТСЯ, РАСПРЕДЕЛЕНИЯ (5) И~(6) ДОВОЛЬНО ИСКУССТВЕННЫ, И ИХ НЕЛЬЗЯ 
СЧИТАТЬ ХОРОШИМ ПРИБЛИЖЕНИЕМ К ДЕЙСТВИТЕЛЬНОСТИ. сОЛЕЕ ТИПИЧНУЮ КАРТИНУ 
ДАЕТ "ЗАКОН чИПФА":
$$
p_1=c/1, p_2=c/2, \ldots, p_N=c/N, \rem{ГДЕ $c=1/H_N$}.
\eqno (8)
$$

¤ТО РАСПРЕДЕЛЕНИЕ ПОЛУЧИЛО ИЗВЕСТНОСТЬ БЛАГОДАРЯ 
фЖ.~ъ~чИПФУ, КОТОРЫЙ ЗАМЕТИЛ, ЧТО $n$-Е НАИБОЛЕЕ УПОТРЕБИТЕЛЬНОЕ В ТЕКСТЕ 
НА ЕСТЕСТВЕННОМ ЯЗЫКЕ СЛОВО ВСТРЕЧАЕТСЯ С ЧАСТОТОЙ, ПРИБЛИЗИТЕЛЬНО ОБРАТНО 
ПРОПОРЦИОНАЛЬНОЙ $n$. 
[The Psicho-Biology of Language (Boston, Mass.: Houghton Miffling, 1935);
Human Behavior and the Principle of Least Effort (Reading, Mass.: 
Addison-Wesley, 1949).] рНАЛОГИЧНОЕ ЯВЛЕНИЕ ОБНАРУЖЕНО ИМ В ТАБЛИЦАХ 
ПЕРЕПИСИ; ТАМ СТОЛИЧНЫЕ РАЙОНЫ РАСПОЛОЖЕНЫ В ПОРЯДКЕ УБЫВАНИЯ НАСЕЛЕНИЯ. т 
СЛУЧАЕ, ЕСЛИ ЧАСТОТА КЛЮЧЕЙ В ТАБЛИЦЕ ПОДЧИНЯЕТСЯ ЗАКОНУ чИПФА, ИМЕЕМ
$$
\overline{C}_N=N/H_N;
\eqno(9)
$$
ПОИСК ПО ТАКОМУ ФАЙЛУ ПРИМЕРНО В ${1\over2}\ln N$ РАЗ БЫСТРЕЕ, ЧЕМ ПО
НЕУПОРЯДОЧЕННОМУ. [ёР. С A.~D.~Booth et al. Mechanical Resolution of 
Linguistic Problems (New York: Academic Press, 1958), 79.)

фРУГОЕ РАСПРЕДЕЛЕНИЕ, БЛИЗКОЕ К РЕАЛЬНОМУ, ДАЕТ ПРАВИЛО "80--20", КОТОРОЕ 
ЧАСТО ВСТРЕЧАЕТСЯ В КОММЕРЧЕСКИХ ПРИЛОЖЕНИЯХ [СР. С W. P. Heising, 
{\sl IBM Systems J.\/}, {\bf 2} (1963), 114--115]. ¤ТО ПРАВИЛО ГЛАСИТ, ЧТО 80\% 
РАБОТЫ ВЕДЕТСЯ НАД НАИБОЛЕЕ АКТИВНОЙ ЧАСТЬЮ ФАЙЛА ВЕЛИЧИНОЙ 20\%; ОНО 
ПРИМЕНИМО И К ЭТИМ 20\%, ТАК ЧТО 64\% РАБОТЫ ВЕДЕТСЯ С НАИБОЛЕЕ АКТИВНЫМИ 
4\% ФАЙЛА, И Т. Д. шНЫМИ СЛОВАМИ,
$$
{p_1+p_2+\cdots+p_{.20n}\over p_1+p_2+p_3+\cdots+p_n}
\approx 0.80 \rem{ДЛЯ ВСЕХ $n$}.
\eqno (10)
$$
%% 475
тОТ ОДНО ИЗ РАСПРЕДЕЛЕНИЙ, ТОЧНО УДОВЛЕТВОРЯЮЩИХ ПРИВЕДЕННОМУ ПРАВИЛУ 
ПРИ $n$, КРАТНЫХ 5:
$$
p_1=c, p_2=(2^\theta-1)c, p_3=(3^\theta-2^\theta)c, \ldots, 
  p_N=(N^\theta-(N-1)^\theta)c,
\eqno(11)
$$
ГДЕ
$$
c=1/N^\theta; \theta={\log 0.80 \over \log 0.20}=0.1386.
\eqno(12)
$$
фЕЙСТВИТЕЛЬНО, $p_1+p_2+\cdots+p_n=cn^\theta$  ПРИ ЛЮБОМ $n$. ё 
ВЕРОЯТНОСТЯМИ (11) НЕ ТАК ПРОСТО РАБОТАТЬ; ИМЕЕМ, ОДНАКО, 
$n^\theta-(n-1)^\theta)=\theta n^{\theta-1}(1 + O(1/n))$, Т.Е. СУЩЕСТВУЕТ 
БОЛЕЕ ПРОСТОЕ РАСПРЕДЕЛЕНИЕ, ПРИБЛИЖЕННО УДОВЛЕТВОРЯЮЩЕЕ ПРАВИЛУ "80--20":
$$
p_1=c/1^{1-\theta}, p_2=c/2^{1-\theta}, \ldots, p_N=c/N^{1-\theta},
\rem{ГДЕ $c=1/H_N^{1-\theta}$}.
\eqno (13)
$$
чДЕСЬ, КАК И РАНЬШЕ, $\theta= \log 0.80/\log 0.20$, a $H_N^{(s)}$ ЕСТЬ 
$N$-e ГАРМОНИЧЕСКОЕ ЧИСЛО ПОРЯДКА $s$, Т. Е. $1^{-s}+2^{-s}+\cdots+N^{-s}$. 
чАМЕТИМ, ЧТО ЭТО РАСПРЕДЕЛЕНИЕ ОЧЕНЬ НАПОМИНАЕТ РАСПРЕДЕЛЕНИЕ чИПФА (8); 
КОГДА $\theta$ ИЗМЕНЯЕТСЯ ОТ 1 ДО 0, ВЕРОЯТНОСТИ МЕНЯЮТСЯ
ОТ РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ К ЗИПФОВСКИМ. (т САМОМ ДЕЛЕ,
чИПФ НАШЕЛ, ЧТО $\theta\approx {1\over 2}$ В РАСПРЕДЕЛЕНИИ ЛИЧНЫХ ДОХОДОВ.)
яРИМЕНЯЯ (3) К (13), ПОЛУЧАЕМ ДЛЯ ПРАВИЛА "80--20" СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ
$$
\overline{C}_N=H_N^{(-\theta)}/H_N^{(1-\theta)}
 ={\theta N \over \theta+1}+O(N^{(1-\theta)})\approx 0.122N
\eqno (14)
$$
(СМ. УПР. 8).

■. ё. °ВАРЦ, ИЗУЧАВШИЙ ЧАСТОТЫ ПОЯВЛЕНИЯ СЛОВ [СМ. ИНТЕРЕСНЫЙ ГРАФИК НА 
СТР. 422 В {\sl JACM\/}, {\bf 10} (1963)], ПРЕДЛОЖИЛ БОЛЕЕ ПОДХОДЯЩЕЕ 
ВЫРАЖЕНИЕ ДЛЯ'ЗАКОНА чИПФА:
$$
p_1=c/1^{1+\theta}, p_2=c/2^{1+\theta}, \ldots, p_N=c/N^{1+\theta},
\rem{ГДЕ $c=1/H_N^{1+\theta}$},
\eqno (15)
$$
ПРИ МАЛЫХ \emph{ПОЛОЖИТЕЛЬНЫХ} $Q$. [яО СРАВНЕНИЮ С (13) ЗДЕСЬ ИЗМЕНЕН 
ЗНАК $\theta$.] т ЭТОМ СЛУЧАЕ
$$
\overline{C}_N=H_N^\theta/H_N^{(1+\theta)}
  =N^{1-\theta}/(1-\theta)\zeta(1+\theta)+O(N^{1-2\theta}),
\eqno (16)
$$
ЧТО ЗНАЧИТЕЛЬНО МЕНЬШЕ, ЧЕМ (9) ПРИ $N\to\infty$.
\section "ёАМООРГАНИЗУЮЩИЙСЯ" ФАЙЛ. яРЕДЫДУЩИЕ ВЫЧИСЛЕНИЯ ХОРОШИ, НО В 
БОЛЬШИНСТВЕ СЛУЧАЕВ РАСПРЕДЕЛЕНИЕ ВЕРОЯТНОСТЕЙ НАМ НЕ ИЗВЕСТНО. ьЫ МОГЛИ 
БЫ В КАЖДОЙ ЗАПИСИ ЗАВЕСТИ СЧЕТЧИК ЧИСЛА ОБРАЩЕНИЙ, ЧТОБЫ НА ОСНОВАНИИ 
ПОКАЗАНИЙ СЧЕТЧИКОВ ПЕРЕУПОРЯДОЧИТЬ ЗАПИСИ. тЫВЕДЕННЫЕ ФОРМУЛЫ 
ПОКАЗЫВАЮТ, ЧТО ТАКАЯ ПРОЦЕДУРА МОЖЕТ ПРИВЕСТИ К ЗАМЕТНОЙ ЭКОНОМИИ. эО НЕ
ВСЕГДА
%% 476
ЖЕЛАТЕЛЬНО ОТВОДИТЬ МНОГО ПАМЯТИ ПОД СЧЕТЧИКИ, ТАК КАК ЕЕ МОЖНО 
ИСПОЛЬЗОВАТЬ БОЛЕЕ РАЦИОНАЛЬНО (НАПРИМЕР, ПРИМЕНЯЯ ДРУГИЕ МЕТОДЫ ПОИСКА, 
ИЗЛАГАЕМЫЕ НИЖЕ В ДАННОЙ ГЛАВЕ).

яРОСТАЯ СХЕМА, ПРОИСХОЖДЕНИЕ КОТОРОЙ НЕ ИЗВЕСТНО, ИСПОЛЬЗУЕТСЯ УЖЕ 
МНОГИЕ ГОДЫ. юНА ПОЗВОЛЯЕТ ДОВОЛЬНО ХОРОШО УПОРЯДОЧИТЬ ЗАПИСИ БЕЗ 
ВСПОМОГАТЕЛЬНЫХ ПОЛЕЙ ДЛЯ СЧЕТЧИКОВ:
КОГДА МЫ НАХОДИМ НУЖНУЮ ЗАПИСЬ, МЫ ПОМЕЩАЕМ ЕЕ В НАЧАЛО ТАБЛИЦЫ. яОДОБНЫЙ 
МЕТОД ЛЕГКО РЕАЛИЗОВАТЬ, КОГДА ТАБЛИЦА ПРЕДСТАВЛЕНА В ВИДЕ СВЯЗАННОГО 
ЛИНЕЙНОГО СПИСКА: ВЕДЬ ЧАСТО НАМ БЫВАЕТ НУЖНО ЗНАЧИТЕЛЬНО ИЗМЕНИТЬ 
НАЙДЕННУЮ ЗАПИСЬ.

шДЕЯ "САМООРГАНИЗУЮЩЕГОСЯ" МЕТОДА СОСТОИТ В ТОМ, ЧТО ЧАСТО ИСПОЛЬЗУЕМЫЕ 
ЭЛЕМЕНТЫ БУДУТ РАСПОЛОЖЕНЫ ДОВОЛЬНО БЛИЗКО К НАЧАЛУ ТАБЛИЦЫ. яУСТЬ $N$ 
КЛЮЧЕЙ РАЗЫСКИВАЮТСЯ С ВЕРОЯТНОСТЯМИ $\{p_1, p_2, \ldots, p_N\}$ 
СООТВЕТСТВЕННО, ПРИЧЕМ КАЖДЫЙ ПОИСК СОВЕРШАЕТСЯ АБСОЛЮТНО 
\emph{НЕЗАВИСИМО} ОТ ПРЕДЫДУЩИХ. ьОЖНО ПОКАЗАТЬ, ЧТО СРЕДНЕЕ ЧИСЛО 
СРАВНЕНИЙ ПРИ НАХОЖДЕНИИ ЗАПИСИ В ТАКОМ САМООРГАНИЗУЮЩЕМСЯ ФАЙЛЕ СТРЕМИТСЯ 
К ПРЕДЕЛЬНОМУ ЗНАЧЕНИЮ
$$
\overline{C}_N=1+2\sum_{1\le i < j \le N}{p_ip_j\over p_i+p_j}
={1\over 2}+\sum_{i, j}{p_ip_j\over p_i+p_j}.
\eqno (17)
$$
(ёМ. УПР. 11.) эАПРИМЕР, ЕСЛИ $p_i=1/N$ ПРИ $1\le i \le N$, 
САМООРГАНИЗУЮЩАЯСЯ ТАБЛИЦА ВСЕГДА НАХОДИТСЯ В СЛУЧАЙНОМ ПОРЯДКЕ, А 
(17) СВОДИТСЯ К ЗНАКОМОМУ ВЫРАЖЕНИЮ $(N+1)/2$, ПОЛУЧЕННОМУ РАНЕЕ.

яОСМОТРИМ, КАК САМООРГАНИЗУЮЩАЯСЯ ПРОЦЕДУРА РАБОТАЕТ ПРИ РАСПРЕДЕЛЕНИИ 
ВЕРОЯТНОСТЕЙ ПО ЗАКОНУ чИПФА (8). шМЕЕМ
$$
\eqalign{
\overline{C}_N&={1\over 2}+\sum_{1\le i, j\le N}{(c/i)(c/j)\over c/i+c/j}
    ={1\over2}+c\sum_{1\le i, j\le N}{1\over i+j}=\cr
&={1\over2}+c\sum_{1\le i\le N}(H_{N+i}-H_i)
   ={1\over2}+c\sum_{1\le i\le 2N}H_i-2c\sum_{1\le i\le N}H_i=\cr
&={1\over2}+c((2N+1)H_{2N}-2N-2(N+1)H_N+2N)=\cr
&={1\over2}+c(N\ln 4-\ln N+O(1))\approx\cr
&\approx 2N/log_2N.\cr
}
$$
(СМ. ФОРМУЛЫ (1.2.7--8,3)). ¤ТО ГОРАЗДО ЛУЧШЕ, ЧЕМ У $N$ ПРИ ДОСТАТОЧНО 
БОЛЬШИХ $N$, И ЛИШЬ В $\ln4\approx 1.386$ РАЗ ХУЖЕ, ЧЕМ ЧИСЛО СРАВНЕНИЙ 
ПРИ ОПТИМАЛЬНОМ РАСПОЛОЖЕНИИ ЗАПИСЕЙ (СР. С (9)).

¤КСПЕРИМЕНТЫ, ПРИВОДИВШИЕСЯ С ТАБЛИЦАМИ СИМВОЛОВ В КОМПИЛЯТОРАХ, 
ПОКАЗАЛИ, ЧТО САМООРГАНИЗУЮЩИЙСЯ МЕТОД РАБОТАЕТ ДАЖЕ ЛУЧШЕ, ЧЕМ 
ПРЕДСКАЗЫВАЕТ (18), ТАК КАК УДАЧНЫЕ ПОИСКИ
%% 477
НЕ НЕЗАВИСИМЫ (НЕБОЛЬШИЕ ГРУППЫ КЛЮЧЕЙ ЧАСТО ПОЯВЛЯЮТСЯ ВМЕСТЕ).

ёХЕМУ, ПОДОБНУЮ САМООРГАНИЗУЮЩЕЙСЯ, ИЗУЧИЛИ у. °АЙ И Ї.~т.~фАУЭР 
[{\sl SIAM J.  Appl. Math.\/}, {\bf 15} (1967), 874--888.]

\section яОИСК НА ЛЕНТЕ СРЕДИ ЗАПИСЕЙ РАЗЛИЧНОЙ ДЛИНЫ. ЁАССМОТРИМ ТЕПЕРЬ 
НАШУ ЗАДАЧУ В ИНОМ РАКУРСЕ. яУСТЬ ТАБЛИЦА, ПО КОТОРОЙ ПРОИЗВОДИТСЯ ПОИСК,
 ХРАНИТСЯ НА ЛЕНТЕ И ЗАПИСИ ИМЕЮТ РАЗЛИЧНЫЕ ДЛИНЫ. ыЕНТА С СИСТЕМНОЙ 
БИБЛИОТЕКОЙ В СТАРЫХ ОПЕРАЦИОННЫХ СИСТЕМАХ СЛУЖИТ ПРИМЕРОМ ТАКОГО ФАЙЛА. 
ёТАНДАРТНЫЕ ПРОГРАММЫ СИСТЕМЫ, ТАКИЕ, КАК КОМПИЛЯТОРЫ, КОМПОНОВЩИКИ, 
ЗАГРУЗЧИКИ, ГЕНЕРАТОРЫ ОТЧЕТОВ И Т. П., ЯВЛЯЛИСЬ "ЗАПИСЯМИ" НА ЛЕНТЕ, А 
БОЛЬШИНСТВО ПОЛЬЗОВАТЕЛЬСКИХ РАБОТ ДОЛЖНО БЫЛО НАЧИНАТЬСЯ С ПОИСКА НУЖНОЙ 
ПРОГРАММЫ. ЄАКАЯ ПОСТАНОВКА ЗАДАЧИ ДЕЛАЕТ НЕПРИМЕНИМЫМ ПРЕДЫДУЩИЙ 
АНАЛИЗ АЛГОРИТМА S: ТЕПЕРЬ ШАГ S3 ВЫПОЛНЯЕТСЯ ЗА РАЗЛИЧНЫЕ ПРОМЕЖУТКИ 
ВРЕМЕНИ. чНАЧИТ, НАС БУДЕТ ИНТЕРЕСОВАТЬ НЕ ТОЛЬКО ЧИСЛО СРАВНЕНИЙ.

юБОЗНАЧИМ ЧЕРЕЗ $L_i$ ДЛИНУ ЗАПИСИ $R_i$, А ЧЕРЕЗ $p_i$, ВЕРОЯТНОСТЬ ТОГО, 
ЧТО ЭТА ЗАПИСЬ БУДЕТ ОТЫСКИВАТЬСЯ. тРЕМЯ ПОИСКА ТЕПЕРЬ ПРИМЕРНО 
ПРОПОРЦИОНАЛЬНО ВЕЛИЧИНЕ
$$
p_1L_1+p_2(L_1+L_2)+\cdots+p_N(L_1+L_2+\cdots+L_N).
\eqno (19)
$$
яРИ $L_1=L_2=\ldots=L_N=1$ ЭТО, ОЧЕВИДНО, СВОДИТСЯ К ИЗУЧЕННОМУ СЛУЧАЮ (3).

ъАЖЕТСЯ ЛОГИЧНЫМ ПОМЕСТИТЬ НАИБОЛЕЕ НУЖНЫЕ ЗАПИСИ В НАЧАЛО ЛЕНТЫ, НО ЗДЕСЬ 
ЗДРАВЫЙ СМЫСЛ ПОДВОДИТ НАС. фЕЙСТВИТЕЛЬНО, ПУСТЬ НА ЛЕНТЕ ЗАПИСАНЫ РОВНО 
ДВЕ ПРОГРАММЫ---$A$ И $B$. яРОГРАММА $A$ ТРЕБУЕТСЯ В ДВА РАЗА ЧАЩЕ $B$, НО 
ДЛИННЕЕ $B$ В ЧЕТЫРЕ
РАЗА, Т. Е. $N=2$, $p_A={2\over3}$, $L_A=4$, $p_B={1\over3}$, $L_B=1$. 
хСЛИ МЫ, СЛЕДУЯ "ЛОГИКЕ", ПОСТАВИМ $A$ НА ПЕРВОЕ МЕСТО, ТО СРЕДНЕЕ ВРЕМЯ
ПОИСКА СОСТАВИТ ${2\over 3}\cdot4+{1\over3}\cdot 5={13\over3}$; НО ЕСЛИ 
ПОСТУПИТЬ "НЕЛОГИЧНО",
РАСПОЛОЖИВ В НАЧАЛЕ $B$, ТО ПОЛУЧИТСЯ 
${1\over3}\cdot1+{2\over3}\cdot5={11\over 3}$.
ёЛЕДУЮЩАЯ ТЕОРЕМА ПОЗВОЛЯЕТ ОПРЕДЕЛИТЬ ОПТИМАЛЬНОЕ РАСПОЛОЖЕНИЕ 
БИБЛИОТЕЧНЫХ ПРОГРАММ НА ЛЕНТЕ.
\proclaim ЄЕОРЕМА S. яУСТЬ $L_i$ И $p_i$, ОПРЕДЕЛЕНЫ, КАК И РАНЬШЕ. 
яОРЯДОК ЗАПИСЕЙ НА ЛЕНТЕ ОПТИМАЛЕН ТОГДА И ТОЛЬКО ТОГДА, КОГДА
$$
p_1/L_1\ge p_2/L_2\ge \ldots \ge p_N/L_N.
\eqno (20)
$$

шНЫМИ СЛОВАМИ, МИНИМУМ ВЫРАЖЕНИЯ
$$
p_{a_1}L_{a_1}+p_{a_2}(L_{a_1}+L_{a_2})+\cdots
 +p_{a_N}(L_{a_1}+\cdots+L_{a_N})
$$
%% 478
ПО ВСЕМ ПЕРЕСТАНОВКАМ $a_1$ $a-2$ \dots $a_N$ ЧИСЕЛ $\{1,2,\ldots, N\}$ 
РАВЕН (19) ТОГДА И ТОЛЬКО ТОГДА, КОГДА ВЫПОЛНЯЕТСЯ (20).

\proof яРЕДПОЛОЖИМ, ЧТО $R_i$ И $R_{i+1}$ ПОМЕНЯЛИСЬ МЕСТАМИ; ВЕЛИЧИНА 
(19), РАНЕЕ РАВНАЯ
$$
\cdots+p_i(L_1+\cdots+L_{i-1}+L_i)+p_{i+1}(L_1+\cdots+L_{i+1})
+\cdots,
$$
ТЕПЕРЬ ЗАМЕНИТСЯ НА
$$
\cdots+p_{i+1}(L_1+\cdots+L_{i-1}+L_{i+1})+p_i(L_1+\cdots+L_{i+1})
+\cdots.
$$
шЗМЕНЕНИЕ РАВНО $p_iL_{i+1}-p_{i+1}L_i$. ЄАК КАК РАСПОЛОЖЕНИЕ 
(19) ОПТИМАЛЬНО, ТО $p_iL_{i+1}-p_{i+1}L_i\ge 0$. чНАЧИТ, $p_i/L_i\ge 
p_{i+1}/L_{i+1}$, Т. Е. (20) ВЫПОЛНЯЕТСЯ.

фОКАЖЕМ ТЕПЕРЬ ДОСТАТОЧНОСТЬ УСЛОВИЯ (20). ЁАЗУМЕЕТСЯ, "ЛОКАЛЬНАЯ" 
ОПТИМАЛЬНОСТЬ РАСПОЛОЖЕНИЯ (19) ВИДНА СРАЗУ:
ЕСЛИ МЫ ПОМЕНЯЕМ МЕСТАМИ ДВЕ ЗАПИСИ, ВРЕМЯ ПОИСКА ИЗМЕНИТСЯ НА 
$p_iL_{i+1}-p_{i+1}L_i\ge 0$. юДНАКО "ГЛОБАЛЬНАЯ" ОПТИМАЛЬНОСТЬ ТРЕБУЕТ 
ОБОСНОВАНИЯ. ьЫ РАССМОТРИМ ДВА ДОКАЗАТЕЛЬСТВА: ОДНО ИЗ НИХ ИСПОЛЬЗУЕТ 
ДИСКРЕТНУЮ МАТЕМАТИКУ, А ДРУГОЕ ПРЕДПОЛАГАЕТ НЕКОТОРУЮ МАТЕМАТИЧЕСКУЮ 
ИЗВОРОТЛИВОСТЬ.

\proof\ 1. яУСТЬ (20) ВЫПОЛНЯЕТСЯ. ьЫ ЗНАЕМ, ЧТО ЛЮБУЮ ПЕРЕСТАНОВКУ 
ЗАПИСЕЙ МОЖНО "ОТСОРТИРОВАТЬ", Т. Е. ПРИВЕСТИ К РАСПОЛОЖЕНИЮ $R_1$, 
$R_2$, \dots,  $R_N$, ПОСЛЕДОВАТЕЛЬНО МЕНЯЯ МЕСТАМИ ЛИШЬ СОСЕДНИЕ ЭЛЕМЕНТЫ.
 ъАЖДОЕ ТАКОЕ ИЗМЕНЕНИЕ ПЕРЕВОДИТ \dots$R_j$ $R_i$\dots В \dots$R_i$ 
$R_j$\dots ДЛЯ НЕКОТОРЫХ $i<j$, 
Т. Е. УМЕНЬШАЕТ ВРЕМЯ ПОИСКА НА НЕОТРИЦАТЕЛЬНУЮ ВЕЛИЧИНУ 
$p_iL_j-p_jL_i$. чНАЧИТ,  ПОРЯДОК $R_1$  $R_2$ \dots $R_N$ ОПТИМАЛЕН.

\proof\ 2. чАМЕНИМ ВЕРОЯТНОСТИ $p_i$ НА
$$
p_i(\varepsilon)=p_i+\varepsilon^i-(\varepsilon^1+\varepsilon^2+\cdots
+\varepsilon^N)/N,
$$
ГДЕ $\varepsilon$---МАЛАЯ ПОЛОЖИТЕЛЬНАЯ ВЕЛИЧИНА. ЁАВЕНСТВО 
$x_1p_1(\varepsilon) +\cdots+x_Np_N(\varepsilon)
=y_1p_1(\varepsilon)+\cdots+y_Np_N(\varepsilon)$ ВЫПОЛНЯЕТСЯ ДЛЯ 
ДОСТАТОЧНО МАЛЫХ $\varepsilon$ ЛИШЬ ПРИ $x_1=y_1$, \dots, $x_N=y_N$;
 В ЧАСТНОСТИ, В (20) СТАНУТ НЕВОЗМОЖНЫМИ РАВЕНСТВА 
${p_i\over L_i}={p_j\over L_j}$ ЁАССМОТРИМ $N!$
ПЕРЕСТАНОВОК ЗАПИСЕЙ. ёРЕДИ НИХ ЕСТЬ ПО КРАЙНЕЙ МЕРЕ ОДНА ОПТИМАЛЬНАЯ; В 
СИЛУ ПЕРВОЙ ЧАСТИ ТЕОРЕМЫ ОНА УДОВЛЕТВОРЯЕТ (20), НО В СИЛУ ОТСУТСТВИЯ 
РАВЕНСТВ УСЛОВИЮ (20) УДОВЛЕТВОРЯЕТ ЛИШЬ ОДНА ПЕРЕСТАНОВКА. ЄАКИМ 
ОБРАЗОМ, (20) ОДНОЗНАЧНО ОПРЕДЕЛЯЕТ ОПТИМАЛЬНОЕ РАСПОЛОЖЕНИЕ ЗАПИСЕЙ В 
ТАБЛИЦЕ ДЛЯ ВЕРОЯТНОСТЕЙ $p_i(\varepsilon)$ ПРИ ДОСТАТОЧНО МАЛЫХ 
$\varepsilon$. яО НЕПРЕРЫВНОСТИ ЭТОТ ЖЕ ПОРЯДОК ОПТИМАЛЕН И ПРИ 
$\varepsilon$. (ЄАКОЙ МЕТОД ДОКАЗАТЕЛЬСТВ ЧАСТО ИСПОЛЬЗУЕТСЯ В 
КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ.)
\proofend

ЄЕОРЕМА S ПРИНАДЛЕЖИТ є. ¤. ёМИТУ [{\sl Naval Research Logistics 
Quarterly\/}, {\bf 3} (1956), 59--66]. єПРАЖНЕНИЯ СОДЕРЖАТ 
ДОПОЛНИТЕЛЬНЫЕ РЕЗУЛЬТАТЫ ПО ОПТИМАЛЬНОЙ ОРГАНИЗАЦИИ ТАБЛИЦ.
%% 479
\section єПЛОТНЕНИЕ ФАЙЛОВ. яОСЛЕДОВАТЕЛЬНЫЙ ПОИСК НА ЛЕНТЕ И ДРУГИХ 
ВНЕШНИХ ЗАПОМИНАЮЩИХ УСТРОЙСТВАХ ПРОТЕКАЕТ БЫСТРЕЕ;
ЕСЛИ ДАННЫЕ ЗАНИМАЮТ МЕНЬШЕ МЕСТА, ПОЭТОМУ ПОЛЕЗНО РАССМОТРЕТЬ НЕСКОЛЬКО 
РАЗЛИЧНЫХ СПОСОБОВ ПРЕДСТАВЛЕНИЯ ДАННЫХ В ТАБЛИЦЕ. эЕ ВСЕГДА НУЖНО 
ЗАПОМИНАТЬ КЛЮЧИ В ЯВНОМ ВИДЕ.

яУСТЬ, НАПРИМЕР, ТРЕБУЕТСЯ ТАБЛИЦА ПРОСТЫХ ЧИСЕЛ ДО МИЛЛИОНА ДЛЯ 
РАЗЛОЖЕНИЯ НА МНОЖИТЕЛИ 12-ЗНАЧНЫХ ЧИСЕЛ. (ёР. С П.~4.5.4.) ЄАКИХ ЧИСЕЛ 
ИМЕЕТСЯ 78498; ИСПОЛЬЗУЯ 20 БИТОВ ДЛЯ КАЖДОГО ИЗ НИХ, МЫ ПОЛУЧИМ ФАЙЛ 
ДЛИНЫ 1\ 569\ 960 БИТОВ. ¤ТО ЯВНОЕ РАСТОЧИТЕЛЬСТВО, ТАК КАК МОЖНО ИМЕТЬ 
МИЛЛИОН-БИТОВУЮ ТАБЛИЦУ, В КОТОРОЙ РАЗРЯДЫ, СООТВЕТСТВУЮЩИЕ ПРОСТЫМ ЧИСЛАМ,
 РАВНЫ 1. яОСКОЛЬКУ ВСЕ ПРОСТЫЕ ЧИСЛА (КРОМЕ ДВОЙКИ) НЕЧЕТНЫ, ДОСТАТОЧНО 
ИМЕТЬ ТАБЛИЦУ В 500000 БИТОВ.

фРУГИМ СПОСОБОМ УМЕНЬШЕНИЯ ДЛИНЫ ФАЙЛА ЯВЛЯЕТСЯ ХРАНЕНИЕ НЕ САМИХ 
ПРОСТЫХ ЧИСЕЛ, А ИНТЕРВАЛОВ МЕЖДУ НИМИ. т СООТВЕТСТВИИ С ТАБЛ.~1 ВЕЛИЧИНА 
$(p_{k+1}-p_k)/2$ МЕНЬШЕ 64 ДЛЯ ВСЕХ ПРОСТЫХ ЧИСЕЛ В ПРЕДЕЛАХ 1\ 357\ 201, 
Т. Е. НАМ ДОСТАТОЧНО ЗАПОМНИТЬ 78\ 496 ШЕСТИРАЗРЯДНЫХ ЧИСЕЛ (РАЗМЕР 
ИНТЕРВАЛА)/2. ЄАКАЯ ТАБЛИЦА ИМЕЕТ ДЛИНУ ПРИМЕРНО 471\ 000 БИТОВ. 
фАЛЬНЕЙШЕГО УПЛОТНЕНИЯ МОЖНО ДОБИТЬСЯ, ИСПОЛЬЗУЯ ДЛЯ 
ПРЕДСТАВЛЕНИЯ ИНТЕРВАЛОВ ДВОИЧНЫЕ КОДЫ ПЕРЕМЕННОЙ ДЛИНЫ (СР. С П~ 6.2.2).
\htable{ЄАБЛИЦА 1}%
{ЄАБЛИЦА ИНТЕРВАЛОВ МЕЖДУ ПОСЛЕДОВАТЕЛЬНЫМИ ПРОСТЫМИ ЧИСЛАМИ}%
{\strut\hfill#\hfill&\hfill#\hfill&\vrule\hfill#\hfill&\hfill#\hfill\cr
шНТЕРВАЛ $(p_{k+1}-p_k)$ & $p_k$  & шНТЕРВАЛ $(p_{k+1}-p_k)$ & $p_k$ \cr
 1 &     2 &  52 &    19609 \cr
 2 &     3 &  72 &    31397 \cr
 4 &     7 &  86 &   155921 \cr
 6 &    23 &  96 &   360653 \cr
 8 &    89 & 112 &   370261 \cr
14 &   113 & 114 &   492113 \cr
18 &   523 & 118 &  1349533 \cr
20 &   887 & 132 &  1357201 \cr
23 &  1129 & 148 &  2010733 \cr
34 &  1327 & 154 &  4652353 \cr
36 &  9551 & 180 & 17051707 \cr
44 & 15683 & 310 & 20831323 \cr
}
т ТАБЛИЦЕ ПОМЕЩЕНЫ ИНТЕРВАЛЫ $p_{k+1}-p_k$, ПРЕВЫШАЮЩИЕ $p_{j+1}-p_j$ 
ДЛЯ ВСЕХ $j<k$. сОЛЕЕ ПОДРОБНО СМ. F. Gruenberger, G. Armerding, 
"Statistics on the first six million prime numbers", RAND Corp. report 
P-2460 (October, 1961).

\bye