\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