\input style
\hyphenation{АВ-ТО-МО-БИ-ЛЕЙ}
%% 4
\UDC{681.142.2}
\vfill

тРЕТИЙ ТОМ ИЗВЕСТНОЙ МОНОГРАФИИ ОДНОГО ИЗ КРУПНЕЙШИХ АМЕРИКАНСКИХ СПЕЦИАЛИСТОВ ПО 
ПРОГРАММИРОВАНИЮ д. кНУТА (ПЕРВЫЙ ТОМ ВЫШЕЛ В ИЗДАТЕЛЬСТВЕ \rlq{}мИР\rrq{} В 1976 Г., 
ВТОРОЙ---В 1977 Г.) СОСТОИТ ИЗ ДВУХ ЧАСТЕЙ: \rlq{}сОРТИРОВКА\rrq{} И \rlq{}пОИСК\rrq{}. в НИХ 
ПОДРОБНО ИССЛЕДУЮТСЯ РАЗЛИЧНЫЕ АЛГОРИТМЫ ВНУТРЕННЕЙ И ВНЕШНЕЙ СОРТИРОВКИ, ИЗУЧАЮТСЯ 
МЕТОДЫ ПОИСКА ИНФОРМАЦИИ В ТАБЛИЦАХ НА ОСНОВЕ СРАВНЕНИЕ ИЛИ ПРЕОБРАЗОВАНИЯ КЛЮЧЕЙ, 
ДАЮТСЯ ОЦЕНКИ ЭФФЕКТИВНОСТИ ПРЕДЛАГАЕМЫХ АЛГОРИТМОВ. кНИГА СНАБЖЕНА БОЛЬШИМ 
КОЛИЧЕСТВОМ ЗАДАЧ И ПРИМЕРОВ РАЗНОЙ СТЕПЕНИ ТРУДНОСТИ, СУЩЕСТВЕННО ДОПОЛНЯЮЩИХ 
ОСНОВНОЙ ТЕКСТ.

оТ ДРУГИХ РУКОВОДСТВ ПО ПРОГРАММИРОВАНИЮ КНИГА ВЫГОДНО ОТЛИЧАЕТСЯ СТРОГОСТЬЮ 
ИЗЛОЖЕНИЯ И ШИРОКИМ ПРИМЕНЕНИЕМ МАТЕМАТИЧЕСКОГО АППАРАТА. вМЕСТЕ С ТЕМ ОНА ДОСТУПНА 
СТУДЕНТАМ ПЕРВОГО КУРСА. зНАКОМСТВО С ДВУМЯ ПЕРВЫМИ ТОМАМИ ЖЕЛАТЕЛЬНО, НО НЕ 
ОБЯЗАТЕЛЬНО. кАЖДЫЙ, КТО ХОЧЕТ НАУЧИТЬСЯ КВАЛИФИЦИРОВАННО ПРОГРАММИРОВАТЬ, НАЙДЕТ В 
НЕЙ МНОГО ПОЛЕЗНОГО.

рАССЧИТАНА НА ШИРОКИЙ КРУГ ПРОГРАММИСТОВ.
\vfill
\vfill
\centerline{{\it рЕДАКЦИЯ ЛИТЕРАТУРЫ ПО МАТЕМАТИЧЕСКИМ НАУКАМ}}

\line{$к{20204-022\over 041(01)-78}22-78$   \hfill   \copyright\ пЕРЕВОД НА РУССКИЙ 
ЯЗЫК, \rlq{}мИР\rrq{}. 1978}
\eject
%% 5
\chapter{предисловие редакторов перевода}
д. э. кНУТ ХОРОШО ЗНАКОМ СОВЕТСКОМУ ЧИТАТЕЛЮ ПО ПЕРЕВОДАМ ДВУХ ПЕРВЫХ ТОМОВ ЕГО 
ОБШИРНОЙ МОНОГРАФИИ "иСКУССТВО ПРОГРАММИРОВАНИЯ ДЛЯ эвм" И НЕ НУЖДАЕТСЯ В 
АТТЕСТАЦИИ. нАСТОЯЩАЯ КНИГА ПРЕДСТАВЛЯЕТ СОБОЙ ТРЕТИЙ ТОМ И ПОСВЯЩЕНА АЛГОРИТМАМ 
СОРТИРОВКИ И ПОИСКА ИНФОРМАЦИИ.

иСТОРИЧЕСКИ ЗАРОЖДЕНИЕ МЕТОДОВ МАШИННОЙ СОРТИРОВКИ МОЖНО ОТНЕСТИ ЕЩЕ К ПРОШЛОМУ 
СТОЛЕТИЮ, И ЗА СТОЛЬ ДЛИТЕЛЬНОЕ ВРЕМЯ МНОГИЕ СПЕЦИАЛИСТЫ УСПЕЛИ ИСПРОБОВАТЬ СВОИ СИЛЫ В 
ЭТОЙ ОБЛАСТИ. нАПИСАНО НЕМАЛО ОТЧЕТОВ, СТАТЕЙ, МОНОГРАФИЙ. и ДАЖЕ В ЭТИХ УСЛОВИЯХ КНИГА 
д. кНУТА СТАЛА СОБЫТИЕМ. пО СУЩЕСТВУ ЭТО ЭНЦИКЛОПЕДИЯ, В КОТОРОЙ МОЖНО НАЙТИ ЛЮБУЮ 
СПРАВКУ, КАСАЮЩУЮСЯ АЛГОРИТМОВ, МЕТОДОВ ИХ ОЦЕНОК, ИСТОРИИ ВОПРОСА И НЕРЕШЕННЫХ 
ПРОБЛЕМ.    

нЕТ НУЖДЫ ГОВОРИТЬ О ВАЖНОСТИ САМОЙ ОБЛАСТИ. пРАКТИЧЕСКИ СОРТИРОВКА И ПОИСК В ТОЙ 
ИЛИ ИНОЙ МЕРЕ ПРИСУТСТВУЮТ ВО ВСЕХ ПРИЛОЖЕНИЯХ; В ЧАСТНОСТИ, ПРИ ОБРАБОТКЕ БОЛЬШИХ 
ОБЎЕМОВ ДАННЫХ ЭФФЕКТИВНОСТЬ ИМЕННО ЭТИХ ОПЕРАЦИЙ ОПРЕДЕЛЯЕТ ЭФФЕКТИВНОСТЬ, А ИНОГДА И 
РАБОТОСПОСОБНОСТЬ ВСЕЙ СИСТЕМЫ. пОЭТОМУ, КАК СПРАВЕДЛИВО ОТМЕЧАЕТ АВТОР, КНИГА 
АДРЕСОВАНА НЕ ТОЛЬКО СИСТЕМНЫМ ПРОГРАММИСТАМ, ЗАНИМАЮЩИМСЯ РАЗРАБОТКОЙ ПРОГРАММ 
СОРТИРОВКИ И ПОИСКА ИНФОРМАЦИИ. мОЖНО СКАЗАТЬ, ЧТО ДОСТАТОЧНО ЧЕТКИЕ ПРЕДСТАВЛЕНИЯ ОБ 
ЭТОЙ ОБЛАСТИ НУЖНЫ ПРИ РЕШЕНИИ ЛЮБОЙ ЗАДАЧИ НА эвм КАК ОБЯЗАТЕЛЬНЫЕ ЭЛЕМЕНТЫ 
ИСКУССТВА ПРОГРАММИРОВАНИЯ.

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

пЕРЕВОД ВЫПОЛНЕН ПО ИЗДАНИЮ 1973 Г. (ПЕРВАЯ РЕДАКЦИЯ) С ВНЕСЕНИЕМ МНОГИХ (ОКОЛО 700) 
ИСПРАВЛЕНИЙ И ДОБАВЛЕНИЙ, ЛЮБЕЗНО ПРЕДОСТАВЛЕННЫХ АВТОРОМ. рАЗДЕЛЫ С 5.1 ПО 5.3.2 ПЕРЕ-
ВЕДЕНЫ. н. и. вЬЮКОВОЙ; РАЗДЕЛЫ С 5.3.3 ПО 5.5 И ПРЕДИСЛОВИЕ--- а. б. хОДУЛЕВЫМ; ГЛАВУ Б 
ПЕРЕВЕЛ в. а. гАЛАТЕНКО.
\rightline{ю. м. бАЯКОВСКИЙ}
\rightline{ в. с. шТАРКМАН}
%% 6
\chapter{предисловие}
\epigraph
кУЛИНАРИЯ СТАЛА ИСКУССТВОМ, ВЫСОКОЙ НАУКОЙ;\nl
ПОВАРА ТЕПЕРЬ---БЛАГОРОДНЫЕ ЛЮДИ.
\signed
тИТ лИВИЙ, аь Urbe Condita, XXXIX.vi\nl
(рОБЕРТ бЕРТОН, Anatomy of Melancholy, 1.2.2.2)%
\note{1}{ рОБЕРТ бЕРТОН (1577--1640) --- АНГЛИЙСКИЙ УЧЕНЫЙ, ПИСАТЕЛЬ И ТЕОЛОГ.  
{\sl пРИМ. пЕРЕВ.\/}}

мАТЕРИАЛ ЭТОЙ КНИГИ ЛОГИЧЕСКИ ПРОДОЛЖАЕТ МАТЕРИАЛ ПО ИНФОРМАЦИОННЫМ СТРУКТУРАМ, 
ИЗЛОЖЕННЫЙ В ГЛ. 2, ПОСКОЛЬКУ ЗДЕСЬ К УЖЕ РАССМОТРЕННЫМ КОНЦЕПЦИЯМ СТРУКТУР ДОБАВЛЯЕТСЯ 
ПОНЯТИЕ ЛИНЕЙНО УПОРЯДОЧЕННЫХ ДАННЫХ. пОДЗАГОЛОВОК "сОРТИРОВКА И ПОИСК" МОЖЕТ 
ПРИВЕСТИ К МЫСЛИ, ЧТО ЭТА КНИГА ПРЕДНАЗНАЧЕНА ЛИШЬ ДЛЯ СИСТЕМНЫХ ПРОГРАММИСТОВ, 
ЗАНИМАЮЩИХСЯ ПОСТРОЕНИЕМ УНИВЕРСАЛЬНЫХ ПРОГРАММ СОРТИРОВКИ ИЛИ СВЯЗАННЫХ С ВЫБОРКОЙ 
ИНФОРМАЦИИ. оДНАКО В ДЕЙСТВИТЕЛЬНОСТИ ПРЕДМЕТ СОРТИРОВКИ И ПОИСКА ДАЕТ НАМ ПРЕКРАСНУЮ 
ОСНОВУ ДЛЯ ОБСУЖДЕНИЯ ШИРОКОГО КЛАССА ВАЖНЫХ ОБЩИХ ВОПРОСОВ:

кАК НАХОДИТЬ ХОРОШИЕ АЛГОРИТМЫ? 

кАК УЛУЧШАТЬ ДАННЫЕ АЛГОРИТМЫ И ПРОГРАММЫ? 

кАК ИССЛЕДОВАТЬ ЭФФЕКТИВНОСТЬ АЛГОРИТМОВ МАТЕМАТИЧЕСКИ? 

кАК РАЗУМНО ВЫБРАТЬ ОДИН ИЗ НЕСКОЛЬКИХ АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ КОНКРЕТНОЙ ЗАДАЧИ?

в КАКОМ СМЫСЛЕ МОЖНО ДОКАЗАТЬ, ЧТО НЕКОТОРЫЕ АЛГОРИТМЫ ЯВЛЯЮТСЯ "НАИЛУЧШИМИ ИЗ 
ВОЗМОЖНЫХ"? 

кАК ТЕОРИЯ ВЫЧИСЛЕНИЙ СОГЛАСУЕТСЯ С ПРАКТИЧЕСКИМИ СООБРАЖЕНИЯМИ?

кАК ЭФФЕКТИВНО ИСПОЛЬЗОВАТЬ РАЗЛИЧНЫЕ ВИДЫ ВНЕШНЕЙ ПАМЯТИ---ЛЕНТЫ, БАРАБАНЫ, 
ДИСКИ---ДЛЯ БОЛЬШИХ БАЗ ДАННЫХ?
%% 7
я ДУМАЮ, ЧТО НА САМОМ ДЕЛЕ В КОНТЕКСТЕ СОРТИРОВКИ И ПОИСКА ВСТРЕЧАЕТСЯ ПРАКТИЧЕСКИ 
\emph{ЛЮБОЙ} ВАЖНЫЙ АСПЕКТ ПРОГРАММИРОВАНИЯ.

нАСТОЯЩИЙ ТОМ СОСТОИТ ИЗ ГЛ.~5 И~6 МОНОГРАФИИ. в ГЛ.~5 РАССМАТРИВАЕТСЯ СОРТИРОВКА 
(УПОРЯДОЧЕНИЕ); ЭТО ОЧЕНЬ БОЛЬШАЯ ТЕМА, ОНА РАЗБИТА НА ДВЕ ГЛАВНЫЕ ЧАСТИ---ВНУТРЕННЮЮ И 
ВНЕШНЮЮ СОРТИРОВКУ. в ЭТУ ГЛАВУ ВХОДЯТ ТАКЖЕ ДОПОЛНИТЕЛЬНЫЕ РАЗДЕЛЫ, РАЗВИВАЮЩИЕ 
ВСПОМОГАТЕЛЬНУЮ ТЕОРИЮ ПЕРЕСТАНОВОК (\S~5.1) И ТЕОРИЮ ОПТИМАЛЬНЫХ АЛГОРИТМОВ 
СОРТИРОВКИ (\S~5.3). в ГЛ.~6 МЫ ИМЕЕМ ДЕЛО С ПОИСКОМ ОПРЕДЕЛЕННОГО ЭЛЕМЕНТА В ТАБЛИЦЕ ИЛИ 
ФАЙЛЕ; СОДЕРЖИМОЕ ЭТОЙ ГЛАВЫ ПОДРАЗДЕЛЯЕТСЯ НА МЕТОДЫ ПОСЛЕДОВАТЕЛЬНОГО ПОИСКА, МЕТОДЫ 
ПОИСКА СО СРАВНЕНИЕМ КЛЮЧЕЙ, ПОИСКА С ИСПОЛЬЗОВАНИЕМ СВОЙСТВ ЦИФР, ПОИСКА С ПОМОЩЬЮ 
"ХЕШИРОВАНИЯ"; ЗАТЕМ РАССМАТРИВАЕТСЯ БОЛЕЕ СЛОЖНАЯ ЗАДАЧА ВЫБОРКИ ПО ВТОРИЧНЫМ КЛЮЧАМ. 
оБЕ ГЛАВЫ ПОРАЗИТЕЛЬНО ТЕСНО ПЕРЕПЛЕТАЮТСЯ МЕЖДУ СОБОЙ, МЕЖДУ ИХ ПРЕДМЕТАМИ ИМЕЮТСЯ 
БЛИЗКИЕ АНАЛОГИИ. в ДОПОЛНЕНИЕ К ГЛ. 2 РАССМАТРИВАЮТСЯ ДВА ВАЖНЫХ ВИДА ИНФОРМАЦИОННЫХ 
СТРУКТУР, А ИМЕННО ПРИОРИТЕТНЫЕ ОЧЕРЕДИ (П.~5.2.3) И ЛИНЕЙНЫЕ СПИСКИ, ПРЕДСТАВЛЯЕМЫЕ 
ПОСРЕДСТВОМ СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ (П.~6.2.3).

чИТАТЕЛЮ, НЕ ЗНАКОМОМУ С ПЕРВЫМ ТОМОМ ЭТОЙ МОНОГРАФИИ, РЕКОМЕНДУЕТСЯ ОБРАЩАТЬСЯ К 
УКАЗАТЕЛЮ ОБОЗНАЧЕНИЙ (ПРИЛОЖЕНИЕ в), ТАК КАК НЕКОТОРЫЕ ИЗ ВСТРЕЧАЮЩИХСЯ В КНИГЕ 
ОБОЗНАЧЕНИЙ НЕ ЯВЛЯЮТСЯ ОБЩЕПРИНЯТЫМИ.

эТА КНИГА БЕЗ БОЛЬШЕЙ ЧАСТИ МАТЕМАТИЧЕСКОГО МАТЕРИАЛА БЫЛА ИСПОЛЬЗОВАНА МНОЙ В 
КАЧЕСТВЕ УЧЕБНИКА ПО ВТОРОМУ КУРСУ ЛЕКЦИЙ "сТРУКТУРЫ ДАННЫХ" ДЛЯ СТУДЕНТОВ
МЛАДШИХ И 
СРЕДНИХ КУРСОВ. мАТЕМАТИЧЕСКИЕ ЧАСТИ ЭТОЙ КНИГИ, ОСОБЕННО \S~5.1,
П.5.2.2, \S~6.3 И 6.4,  МОГЛИ БЫ СОСТАВИТЬ УЧЕБНИК ПО АНАЛИЗУ АЛГОРИТМОВ
ДЛЯ СТУДЕНТОВ СРЕДНИХ И СТАРШИХ КУРСОВ.  кРОМЕ ТОГО, НА ОСНОВЕ П.~4.3.3,
4.6.3, 4.6.4, \S~5.3 И П.~5.4.4 МОЖНО ПОСТРОИТЬ КУРС ЛЕКЦИЙ 
"сЛОЖНОСТЬ ВЫЧИСЛЕНИЙ" ДЛЯ СТАРШЕКУРСНИКОВ.

бЫСТРОЕ РАЗВИТИЕ ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНЫХ НАУК ЗАДЕРЖАЛО ВЫХОД В СВЕТ ЭТОЙ 
КНИГИ ПОЧТЯ НА ТРИ ГОДА, ПОСКОЛЬКУ ОЧЕНЬ МНОГИЕ АСПЕКТЫ СОРТИРОВКИ И ПОИСКА ПОДВЕРГАЛИСЬ 
ДЕТАЛЬНОЙ РАЗРАБОТКЕ. я ОЧЕНЬ БЛАГОДАРЕН нАЦИОНАЛЬНОМУ НАУЧНОМУ ФОНДУ, оТДЕЛЕНИЮ 
ВОЕННО-МОРСКИХ ИССЛЕДОВАНИЙ, иНСТИТУТУ ОБОРОНЫ, ФИРМАМ IBM И Norges 
Almemitenskapelige Forskningsrad ЗА ПОСТОЯННУЮ ПОДДЕРЖКУ МОИХ
ИССЛЕДОВАНИЙ.

%% 8
в ПОДГОТОВКЕ ЭТОГО ТОМА К ПЕЧАТИ МНЕ ОКАЗАЛИ ПОМОЩЬ МНОГИЕ ЛИЦА, ОСОБЕННО эДВАРД а. 
бЕНДЕР, кЛАРК э. кРЭЙН, дЭВИД э. фЕРГЮСОН, рОБЕРТ у. фЛОЙД, рОНАЛЬД л. гРЭХЕМ, лЕОНИДАС 
гЮИБА, дЖОН хОПКРОФТ, рИЧАРД м. кАРП, гЭРИ д. кНОТТ, рУДОЛЬФ а. кРУТАР, шЕНЬ лИНЬ, 
вОГАН р. пРАТТ, сТЕФАН о. рАЙЕ, рИЧАРД п; сТЭНЛИ, я. а. ВАН ДЕР пУЛ И дЖОН у. рЕНЧ МЛ., А 
ТАКЖЕ СТУДЕНТЫ сТЭНФОРДА И бЕРКЛИ, КОТОРЫМ ПРИШЛОСЬ ИСКАТЬ ОШИБКИ В РУКОПИСИ.

\line{оСЛО, нОРВЕГИЯ, \hfill {\sl д. э. кНУТ\/} СЕНТЯБРЬ 1972}
\vskip 1 cm
\epigraph
пИСАТЕЛЬ ПОЛЬЗУЕТСЯ ИЗВЕСТНЫМИ ПРИВИЛЕГИЯМИ, В БЛАГОДЕТЕЛЬНОСТИ КОТОРЫХ, 
НАДЕЮСЬ, НЕТ НИКАКИХ ОСНОВАНИЙ СОМНЕВАТЬСЯ. тАК, ВСТРЕТИВ У МЕНЯ НЕПОНЯТНОЕ 
МЕСТО, ЧИТАТЕЛЬ ДОЛЖЕН ПРЕДПОЛОЖИТЬ, ЧТО ПОД НИМ КРОЕТСЯ НЕЧТО ВЕСЬМА ПОЛЕЗНОЕ 
И ГЛУБОКОМЫСЛЕННОЕ%
\note{1}{пЕРЕВОД а. а. фРАНКОВСКОГО.---{\sl пРИМ. пЕРЕВ.\/}}).
\signed (дЖОНАТАН сВИФТ, сКАЗКА БОЧКИ, ПРЕДИСЛОВИЕ, 1704)

%% 9
\chapter{замечания об упражнениях}
уПРАЖНЕНИЯ, ПОМЕЩЕННЫЕ В КНИГАХ НАСТОЯЩЕЙ СЕРИИ, ПРЕДНАЗНАЧЕНЫ 
КАК ДЛЯ САМОСТОЯТЕЛЬНОЙ ПРОРАБОТКИ, ТАК И ДЛЯ СЕМИНАРСКИХ ЗАНЯТИЙ. 
тРУДНО, ЕСЛИ НЕ НЕВОЗМОЖНО ИЗУЧИТЬ ПРЕДМЕТ, ТОЛЬКО ЧИТАЯ ТЕОРИЮ И НЕ 
ПРИМЕНЯЯ ПОЛУЧЕННУЮ ИНФОРМАЦИЮ ДЛЯ РЕШЕНИЯ СПЕЦИАЛЬНЫХ ЗАДАЧ И ТЕМ 
САМЫМ НЕ ЗАСТАВЛЯЯ СЕБЯ ОБДУМЫВАТЬ ТО, ЧТО БЫЛО ПРОЧИТАНО. кРОМЕ ТОГО, 
МЫ ЛУЧШЕ ВСЕГО ЗАУЧИВАЕМ ТО, ЧТО САМИ ОТКРЫВАЕМ ДЛЯ СЕБЯ. пОЭТОМУ 
УПРАЖНЕНИЯ ОБРАЗУЮТ ВАЖНУЮ ЧАСТЬ ДАННОЙ РАБОТЫ; БЫЛИ ПРЕДПРИНЯТЫ 
ОПРЕДЕЛЕННЫЕ ПОПЫТКИ, ЧТОБЫ ОТОБРАТЬ УПРАЖНЕНИЯ, В КОТОРЫХ БЫ 
СОДЕРЖАЛОСЬ КАК МОЖНО БОЛЬШЕ ИНФОРМАЦИИ И КОТОРЫЕ БЫЛО БЫ ИНТЕРЕСНО 
РЕШАТЬ.

вО МНОГИХ КНИГАХ ЛЕГКИЕ УПРАЖНЕНИЯ ДАЮТСЯ ВПЕРЕМЕШКУ С 
ИСКЛЮЧИТЕЛЬНО ТРУДНЫМИ. зАЧАСТУЮ ЭТО ОЧЕНЬ НЕУДОБНО, ТАК КАК ПЕРЕД ТЕМ, 
КАК ПРИСТУПАТЬ К РЕШЕНИЮ ЗАДАЧИ, ЧИТАТЕЛЬ ОБЯЗАТЕЛЬНО ДОЛЖЕН 
ПРЕДСТАВЛЯТЬ СЕБЕ, СКОЛЬКО ВРЕМЕНИ УЙДЕТ У НЕГО НА ЭТО РЕШЕНИЕ (ИНАЧЕ ОН 
МОЖЕТ РАЗВЕ ТОЛЬКО ПРОСМОТРЕТЬ ВСЕ ЗАДАЧИ). кЛАССИЧЕСКИМ ПРИМЕРОМ ЗДЕСЬ 
ЯВЛЯЕТСЯ КНИГА рИЧАРДА бЕЛЛМАНА "дИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ"; ЭТО 
ВАЖНАЯ ПИОНЕРСКАЯ РАБОТА, В КОТОРОЙ В КОНЦЕ КАЖДОЙ ГЛАВЫ ПОД РУБРИКОЙ 
"уПРАЖНЕНИЯ И ИССЛЕДОВАТЕЛЬСКИЕ ПРОБЛЕМЫ" ДАЕТСЯ ЦЕЛЫЙ РЯД ЗАДАЧ, ГДЕ 
НАРЯДУ С ГЛУБОКИМИ ЕЩЕ НЕРЕШЕННЫМИ ПРОБЛЕМАМИ ВСТРЕЧАЮТСЯ 
ИСКЛЮЧИТЕЛЬНО ТРИВИАЛЬНЫЕ ВОПРОСЫ. гОВОРЯТ, ЧТО ОДНАЖДЫ КТО-ТО 
СПРОСИЛ Д-РА бЕЛЛМАНА, КАК ОТЛИЧИТЬ УПРАЖНЕНИЯ ОТ ИССЛЕДОВАТЕЛЬСКИХ 
ПРОБЛЕМ, И ТОТ ОТВЕТИЛ: "еСЛИ ВЫ МОЖЕТЕ РЕШИТЬ ЗАДАЧУ, ЭТО---УПРАЖНЕНИЕ; 
В ПРОТИВНОМ СЛУЧАЕ ЭТО---ПРОБЛЕМА".

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

\halign{
# & \vtop{\hsize=15cm \noindent#\par} \cr
\bf оЦЕНКА & оБЎЯСНЕНИЕ \cr
00 & чРЕЗВЫЧАЙНО ЛЕГКОЕ УПРАЖНЕНИЕ, НА КОТОРОЕ МОЖНО ОТВЕТИТЬ СРАЗУ   
ЖЕ, ЕСЛИ ПОНЯТ МАТЕРИАЛ ТЕКСТА, И КОТОРОЕ ПОЧТИ ВСЕГДА МОЖНО РЕШИТЬ "В 
УМЕ". \cr
%% 10
10 & пРОСТАЯ ЗАДАЧА, КОТОРАЯ ЗАСТАВЛЯЕТ ЗАДУМАТЬСЯ НАД 
ПРОЧИТАННЫМ МАТЕРИАЛОМ, НО НЕ ПРЕДСТАВЛЯЕТ НИКАКИХ 
ОСОБЫХ ТРУДНОСТЕЙ. нА РЕШЕНИЕ ТАКОЙ ЗАДАЧИ ТРЕБУЕТСЯ НЕ 
БОЛЬШЕ ОДНОЙ МИНУТЫ; В ПРОЦЕССЕ РЕШЕНИЯ МОГУТ 
ПОНАДОБИТЬСЯ КАРАНДАШ И БУМАГА. \cr
20 & зАДАЧА СРЕДНЕЙ ТРУДНОСТИ, ПОЗВОЛЯЮЩАЯ ПРОВЕРИТЬ, НАСКОЛЬКО 
ХОРОШО ПОНЯТ ТЕКСТ. нА ТО ЧТОБЫ ДАТЬ ИСЧЕРПЫВАЮЩИЙ ОТВЕТ, ТРЕБУЕТСЯ 
ПРИМЕРНО 15--20 МИНУТ.\cr
30 & зАДАЧА УМЕРЕННОЙ ТРУДНОСТИ И/ИЛИ СЛОЖНОСТИ, ДЛЯ 
УДОВЛЕТВОРИТЕЛЬНОГО РЕШЕНИЯ КОТОРОЙ ТРЕБУЕТСЯ БОЛЬШЕ ДВУХ ЧАСОВ. \cr
40 & оЧЕНЬ ТРУДНАЯ ИЛИ ТРУДОЕМКАЯ ЗАДАЧА, КОТОРУЮ, ВЕРОЯТНО, СЛЕДУЕТ 
ВКЛЮЧИТЬ В ПЛАН ПРАКТИЧЕСКИХ ЗАНЯТИЙ. пРЕДПОЛАГАЕТСЯ, ЧТО СТУДЕНТ МОЖЕТ 
РЕШИТЬ ТАКУЮ ЗАДАЧУ, НО ДЛЯ ЭТОГО ЕМУ ПОТРЕБУЕТСЯ ЗНАЧИТЕЛЬНЫЙ ОТРЕЗОК 
ВРЕМЕНИ; ЗАДАЧА РЕШАЕТСЯ НЕТРИВИАЛЬНЫМ ОБРАЗОМ. \cr
50 & иССЛЕДОВАТЕЛЬСКАЯ ПРОБЛЕМА, КОТОРАЯ (НАСКОЛЬКО ЭТО БЫЛО ИЗВЕСТНО 
АВТОРУ В МОМЕНТ НАПИСАНИЯ) ЕЩЕ НЕ ПОЛУЧИЛА УДОВЛЕТВОРИТЕЛЬНОГО 
РЕШЕНИЯ. еСЛИ ЧИТАТЕЛЬ НАЙДЕТ РЕШЕНИЕ ЭТОЙ ЗАДАЧИ, ЕГО НАСТОЯТЕЛЬНО 
ПРОСЯТ ОПУБЛИКОВАТЬ ЕГО; КРОМЕ ТОГО, АВТОР ДАННОЙ КНИГИ БУДЕТ ОЧЕНЬ 
ПРИЗНАТЕЛЕН, ЕСЛИ ЕМУ СООБЩАТ РЕШЕНИЕ КАК МОЖНО БЫСТРЕЕ (ПРИ УСЛОВИИ, 
ЧТО ОНО ПРАВИЛЬНО).\cr
}
иНТЕРПОЛИРУЯ ПО ЭТОЙ "ЛОГАРИФМИЧЕСКОЙ" ШКАЛЕ, МОЖНО ПРИКИНУТЬ, 
ЧТО ОЗНАЧАЕТ ЛЮБАЯ ПРОМЕЖУТОЧНАЯ ОЦЕНКА. нАПРИМЕР, ОЦЕНКА 17 ГОВОРИТ О 
ТОМ, ЧТО ДАННОЕ УПРАЖНЕНИЕ ЧУТЬ ЛЕГЧЕ, ЧЕМ УПРАЖНЕНИЕ СРЕДНЕЙ 
ТРУДНОСТИ. зАДАЧА С ОЦЕНКОЙ 50, ЕСЛИ ОНА БУДЕТ РЕШЕНА КАКИМ-ЛИБО 
ЧИТАТЕЛЕМ, В СЛЕДУЮЩИХ ИЗДАНИЯХ ДАННОЙ КНИГИ МОЖЕТ ИМЕТЬ УЖЕ ОЦЕНКУ 
45.

аВТОР ЧЕСТНО СТАРАЛСЯ ДАВАТЬ ОБЎЕКТИВНЫЕ ОЦЕНКИ, НО ТОМУ, КТО 
СОСТАВЛЯЕТ ЗАДАЧИ, ТРУДНО ПРЕДВИДЕТЬ, НАСКОЛЬКО ТРУДНЫМИ ЭТИ ЗАДАЧИ 
ОКАЖУТСЯ ДЛЯ КОГО-ТО ДРУГОГО; К ТОМУ ЖЕ У КАЖДОГО ЧЕЛОВЕКА СУЩЕСТВУЕТ 
ОПРЕДЕЛЕННЫЙ ТИП ЗАДАЧ, КОТОРЫЕ ОН РЕШАЕТ БЫСТРЕЕ. нАДЕЮСЬ, ЧТО 
ВЫСТАВЛЕННЫЕ МНОЙ ОЦЕНКИ ДАЮТ ПРАВИЛЬНОЕ ПРЕДСТАВЛЕНИЕ О СТЕПЕНИ 
ТРУДНОСТИ ЗАДАЧ, НО В ОБЩЕМ ИХ НУЖНО ВОСПРИНИМАТЬ КАК ОРИЕНТИРОВОЧНЫЕ, 
А НЕ АБСОЛЮТНЫЕ.

эТА КНИГА НАПИСАНА ДЛЯ ЧИТАТЕЛЕЙ САМЫХ РАЗНЫХ СТЕПЕНЕЙ 
МАТЕМАТИЧЕСКОЙ ПОДГОТОВКИ И ИСКУШЕННОСТИ, ПОЭТОМУ НЕКОТОРЫЕ 
УПРАЖНЕНИЯ ПРЕДНАЗНАЧЕНЫ ТОЛЬКО ДЛЯ ЧИТАТЕЛЕЙ С МАТЕМАТИЧЕСКИМ 
УКЛОНОМ. еСЛИ В КАКОМ-ЛИБО УПРАЖНЕНИИ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ ИЛИ 
РЕЗУЛЬТАТЫ ИСПОЛЬЗУЮТСЯ БОЛЕЕ ШИРОКО, ЧЕМ ЭТО НЕОБХОДИМО ДЛЯ ТЕХ, КОГО 
В ПЕРВУЮ ОЧЕРЕДЬ ИНТЕРЕСУЕТ ПРОГРАММИРОВАНИЕ АЛГОРИТМОВ, ТО ПЕРЕД 
ОЦЕНКОЙ ТАКОГО УПРАЖНЕНИЯ СТАВИТСЯ БУКВА \rlq{}м". еСЛИ ДЛЯ РЕШЕНИЯ 
УПРАЖНЕНИЯ ТРЕБУЕТСЯ ЗНАНИЕ ВЫСШЕЙ МАТЕМАТИКИ В БОЛЬШЕМ ОБЎЕМЕ, ЧЕМ 
ЭТО ДАНО В НАСТОЯЩЕЙ
%%11
КНИГЕ, ТО СТАВЯТСЯ БУКВЫ "вм". пОМЕТКА "вм" ОТНЮДЬ НЕ 
ЯВЛЯЕТСЯ СВИДЕТЕЛЬСТВОМ ТОГО, ЧТО ДАННОЕ УПРАЖНЕНИЕ 
ТРУДНОЕ.

пЕРЕД НЕКОТОРЫМИ УПРАЖНЕНИЯМИ СТОИТ СТРЕЛКА "\btr"; ЭТО ОЗНАЧАЕТ, 
ЧТО ДАННОЕ УПРАЖНЕНИЕ ОСОБЕННО ПОУЧИТЕЛЬНО И ЕГО РЕКОМЕНДУЕТСЯ 
ОБЯЗАТЕЛЬНО ВЫПОЛНИТЬ. сАМО СОБОЙ РАЗУМЕЕТСЯ, НИКТО НЕ ОЖИДАЕТ, ЧТО 
ЧИТАТЕЛЬ (ИЛИ СТУДЕНТ) БУДЕТ РЕШАТЬ ВСЕ ЗАДАЧИ, ПОТОМУ-ТО НАИБОЛЕЕ 
ПОЛЕЗНЫЕ ИЗ НИХ И ВЫДЕЛЕНЫ. эТО СОВСЕМ НЕ ЗНАЧИТ, ЧТО ДРУГИЕ ЗАДАЧИ НЕ 
СТОИТ РЕШАТЬ! кАЖДЫЙ ЧИТАТЕЛЬ ДОЛЖЕН ПО КРАЙНЕЙ МЕРЕ ПОПЫТАТЬСЯ 
РЕШИТЬ ВСЕ ЗАДАЧИ С ОЦЕНКОЙ 10 И НИЖЕ; СТРЕЛКИ ЖЕ ПОМОГУТ ВЫБРАТЬ, КАКИЕ 
ЗАДАЧИ С БОЛЕЕ ВЫСОКИМИ ОЦЕНКАМИ СЛЕДУЕТ РЕШИТЬ В ПЕРВУЮ ОЧЕРЕДЬ.

к БОЛЬШИНСТВУ УПРАЖНЕНИЙ ПРИВЕДЕНЫ ОТВЕТЫ; ОНИ ПОМЕЩЕНЫ В 
СПЕЦИАЛЬНОМ РАЗДЕЛЕ В КОНЦЕ КНИГИ. пОЛЬЗУЙТЕСЬ ИМИ МУДРО; В ОТВЕТ 
СМОТРИТЕ ТОЛЬКО ПОСЛЕ ТОГО, КАК ВЫ ПРИЛОЖИЛИ ДОСТАТОЧНО УСИЛИЙ, ЧТОБЫ 
РЕШИТЬ ЗАДАЧУ САМОСТОЯТЕЛЬНО, ИЛИ ЖЕ ЕСЛИ ДЛЯ РЕШЕНИЯ ДАННОЙ ЗАДАЧИ У 
ВАС НЕТ ВРЕМЕНИ. еСЛИ ПОЛУЧЕН СОБСТВЕННЫЙ ОТВЕТ, ЛИБО ЕСЛИ ВЫ 
ДЕЙСТВИТЕЛЬНО ПЫТАЛИСЬ РЕШИТЬ ЗАДАЧУ, ТОЛЬКО В ЭТОМ СЛУЧАЕ ОТВЕТ, 
ПОМЕЩЕННЫЙ В КНИГЕ, БУДЕТ ПОУЧИТЕЛЬНЫМ И ПОЛЕЗНЫМ. кАК ПРАВИЛО, 
ОТВЕТЫ К ЗАДАЧАМ ИЗЛАГАЮТСЯ ОЧЕНЬ КРАТКО, СХЕМАТИЧНО, ТАК КАК 
ПРЕДПОЛАГАЕТСЯ, ЧТО ЧИТАТЕЛЬ УЖЕ ЧЕСТНО ПЫТАЛСЯ РЕШИТЬ ЗАДАЧУ 
СОБСТВЕННЫМИ СИЛАМИ. иНОГДА В ПРИВЕДЕННОМ РЕШЕНИИ ДАЕТСЯ МЕНЬШЕ 
ИНФОРМАЦИИ, ЧЕМ СПРАШИВАЛОСЬ, ЧАЩЕ---НАОБОРОТ. вПОЛНЕ ВОЗМОЖНО, ЧТО 
ПОЛУЧЕННЫЙ ВАМИ ОТВЕТ ОКАЖЕТСЯ ЛУЧШЕ ОТВЕТА, ПОМЕЩЕННОГО В КНИГЕ, ИЛИ 
ВЫ НАЙДЕТЕ ОШИБКУ В ЭТОМ ОТВЕТЕ; В ТАКОМ СЛУЧАЕ АВТОР БЫЛ БЫ ОЧЕНЬ 
ОБЯЗАН, ЕСЛИ БЫ ВЫ КАК МОЖНО СКОРЕЕ ПОДРОБНО СООБЩИЛИ ЕМУ ОБ ЭТОМ. в 
ПОСЛЕДУЮЩИХ ИЗДАНИЯХ НАСТОЯЩЕЙ КНИГИ БУДЕТ ПОМЕЩЕНО УЖЕ 
ИСПРАВЛЕННОЕ РЕШЕНИЕ ВМЕСТЕ С ИМЕНЕМ ЕГО АВТОРА.

\halign{
# & # \hfill\cr
\span \bf \hfill сВОДКА УСЛОВНЫХ ОБОЗНАЧЕНИЙ \cr
\btr & рЕКОМЕНДУЕТСЯ \cr
 м  & с МАТЕМАТИЧЕСКИМ УКЛОНОМ \cr
вм & тРЕБУЕТ ЗНАНИЯ "ВЫСШЕЙ МАТЕМАТИКИ"\cr
 00& тРЕБУЕТ НЕМЕДЛЕННОГО ОТВЕТА \cr
10 & пРОСТОЕ (НА ОДНУ МИНУТУ) \cr
20 & сРЕДНЕЙ ТРУДНОСТИ (НА ЧЕТВЕРТЬ ЧАСА) \cr
30 & пОВЫШЕННОЙ ТРУДНОСТИ. \cr
40 & дЛЯ "МАТПРАКТИКУМА" \cr
50 & иССЛЕДОВАТЕЛЬСКАЯ ПРОБЛЕМА\cr
}

\excercises
\rex[00] чТО ОЗНАЧАЕТ ПОМЕТКА "м20"?

\ex[10] кАКОЕ ЗНАЧЕНИЕ ДЛЯ ЧИТАТЕЛЯ ИМЕЮТ УПРАЖНЕНИЯ, ПОМЕЩАЕМЫЕ В 
УЧЕБНИКАХ?

\ex[м50] дОКАЖИТЕ, ЧТО ЕСЛИ $n$---ЦЕЛОЕ ЧИСЛО, $n > 2$, ТО УРАВНЕНИЕ 
$x^n+y^n=z^n$ НЕРАЗРЕШИМО В ЦЕЛЫХ ПОЛОЖИТЕЛЬНЫХ ЧИСЛАХ $Х$, $У$,$z$.

%% 13
\chapnotrue
\chapno=4
\chapter{сОРТИРОВКА}

\epigraph
нЕТ ДЕЛА БОЛЕЕ ТРУДНОГО ПО ЗАМЫСЛУ, БОЛЕЕ СОМНИТЕЛЬНОГО ПО УСПЕХУ, 
БОЛЕЕ ОПАСНОГО ПРИ ОСУЩЕСТВЛЕНИИ, ЧЕМ ВВОДИТЬ НОВЫЕ ПОРЯДКИ.
\signed нИККОЛО мАКЬЯВЕЛЛИ, "гОСУДАРЬ" (1513)

\epigraph
"нО МЫ НЕ УСПЕЕМ, ПРОСМОТРЕТЬ ВСЕ НОМЕРА АВТОМОБИЛЕЙ",---ВОЗРАЗИЛ 
дРЕЙК. "а НАМ И НЕ НУЖНО ЭТОГО ДЕЛАТЬ. пОЛ. мЫ ПРОСТО РАСПОЛОЖИМ ИХ ПО 
ПОРЯДКУ И ПОИЩЕМ ОДИНАКОВЫЕ".
\signed пЕРРИ мЕЙСОН%
\note{1}{ пЕРРИ мЕЙСОН---ГЕРОЙ СЕРИИ ДЕТЕКТИВНЫХ РОМАНОВ ПОПУЛЯРНОГО 
АМЕРИКАНСКОГО ПИСАТЕЛЯ эРЛА сТЕНЛИ гАРДНЕРА.--- {\sl пРИМ. ПЕРЕВ.\/}}. 
иЗ "The Case of Angry Mourner"  (1951)

\epigraph
сОРТИРОВКА ДЕРЕВЬЕВ С ИСПОЛЬЗОВАНИЕМ эвм.\nl
пРИ ТАКОМ НОВОМ, "МАШИННОМ ПОДХОДЕ" К ИЗУЧЕНИЮ ПРИРОДЫ ВЫ ПОЛУЧИТЕ 
ВОЗМОЖНОСТЬ БЫСТРО РАСПОЗНАВАТЬ БОЛЕЕ 260 РАЗЛИЧНЫХ ДЕРЕВЬЕВ сша, 
аЛЯСКИ, кАНАДЫ, ВКЛЮЧАЯ ПАЛЬМЫ, ДЕРЕВЬЯ ПУСТЫНЬ И ПРОЧУЮ ЭКЗОТИКУ. 
чТОБЫ ОПРЕДЕЛИТЬ ПОРОДУ ДЕРЕВА, ДОСТАТОЧНО ПРОСТО ВСТАВИТЬ СПИЦУ.
\signed кАТАЛОГ "Edmund Scientific Company" (1964)

в ЭТОЙ ГЛАВЕ МЫ ИЗУЧИМ ВОПРОС, КОТОРЫЙ ЧАСТО ВОЗНИКАЕТ В 
ПРОГРАММИРОВАНИИ: ПЕРЕРАЗМЕЩЕНИЕ ЭЛЕМЕНТОВ В ВОЗРАСТАЮЩЕМ ИЛИ 
УБЫВАЮЩЕМ ПОРЯДКЕ. пРЕДСТАВЬТЕ, НАСКОЛЬКО ТРУДНО БЫЛО БЫ ПОЛЬЗОВАТЬСЯ 
СЛОВАРЕМ, ЕСЛИ БЫ СЛОВА В НЕМ НЕ РАСПОЛАГАЛИСЬ В АЛФАВИТНОМ ПОРЯДКЕ. 
тОЧНО ТАК ЖЕ ОТ ПОРЯДКА, В КОТОРОМ ХРАНЯТСЯ ЭЛЕМЕНТЫ В ПАМЯТИ эвм, ВО 
МНОГОМ ЗАВИСИТ СКОРОСТЬ И ПРОСТОТА АЛГОРИТМОВ, ПРЕДНАЗНАЧЕННЫХ ДЛЯ ИХ 
ОБРАБОТКИ.

хОТЯ В СЛОВАРЯХ СЛОВО "СОРТИРОВКА" (sorting) ОПРЕДЕЛЯЕТСЯ КАК 
"РАСПРЕДЕЛЕНИЕ, ОТБОР ПО СОРТАМ; ДЕЛЕНИЕ НА КАТЕГОРИИ, СОРТА, РАЗРЯДЫ", 
ПРОГРАММИСТЫ ТРАДИЦИОННО ИСПОЛЬЗУЮТ ЭТО СЛОВО В ГОРАЗДО БОЛЕЕ УЗКОМ 
СМЫСЛЕ, ОБОЗНАЧАЯ ИМ СОРТИРОВКУ ПРЕДМЕТОВ В ВОЗРАСТАЮЩЕМ ИЛИ 
УБЫВАЮЩЕМ ПОРЯДКЕ. эТОТ ПРОЦЕСС, ПОЖАЛУЙ, СЛЕДОВАЛО БЫ НАЗВАТЬ НЕ 
СОРТИРОВКОЙ, А \emph{УПОРЯДОЧЕНИЕМ} (ordering), НО ИСПОЛЬЗОВАНИЕ ЭТОГО 
СЛОВА ПРИВЕЛО БЫ К ПУТАНИЦЕ ИЗ-ЗА ПЕРЕГРУЖЕННОСТИ ЗНАЧЕНИЯМИ СЛОВА 
"ПОРЯДОК". рАССМОТРИМ, НАПРИМЕР, СЛЕДУЮЩЕЕ ПРЕДЛОЖЕНИЕ: "тАК КАК 
ТОЛЬКО ДВА НАШИХ ЛЕНТОПРОТЯЖНЫХ УСТРОЙСТВА В ПОРЯДКЕ, МЕНЯ ПРИЗВАЛИ К 
ПОРЯДКУ И ОБЯЗАЛИ В СРОЧНОМ ПОРЯДКЕ ЗАКАЗАТЬ ЕЩЕ НЕСКОЛЬКО УСТРОЙСТВ, 
ЧТОБЫ МОЖНО БЫЛО УПОРЯДОЧИВАТЬ ДАННЫЕ РАЗНОГО ПОРЯДКА НА НЕСКОЛЬКО 
ПОРЯДКОВ БЫСТРЕЕ%
\note{2}{в ОРИГИНАЛЕ "Since only two of our tape drives were in working 
order I was ordered to order more tape units in short order, in order to order the 
data several orders of magnitude faster".--- {\sl пРИМ. ПЕРЕВ.\/}}. 
в МАТЕМАТИЧЕСКОЙ ТЕРМИНОЛОГИИ
%% 14
ЭТО СЛОВО ТАКЖЕ ИЗОБИЛУЕТ ЗНАЧЕНИЯМИ (ПОРЯДОК ГРУППЫ, ПОРЯДОК 
ПЕРЕСТАНОВКИ, ПОРЯДОК ТОЧКИ ВЕТВЛЕНИЯ, ОТНОШЕНИЕ ПОРЯДКА И Т. П.). иТАК, 
СЛОВО "ПОРЯДОК" ПРИВОДИТ К ХАОСУ.

в КАЧЕСТВЕ ОБОЗНАЧЕНИЯ ДЛЯ ПРОЦЕССА УПОРЯДОЧЕНИЯ ПРЕДЛАГАЛОСЬ ТАКЖЕ 
СЛОВО "РАНЖИРОВАНИЕ"%
\note{1}{в ОРИГИНАЛЕ "sequencing".---{\sl пРИМ. ПЕРЕВ.\/}}, 
НО ОНО ВО МНОГИХ СЛУЧАЯХ, ПО-ВИДИМОМУ, НЕ ВПОЛНЕ ОТРАЖАЕТ СУТЬ ДЕЛА, 
ОСОБЕННО ЕСЛИ ПРИСУТСТВУЮТ РАВНЫЕ ЭЛЕМЕНТЫ, И, КРОМЕ ТОГО, ИНОГДА НЕ 
СОГЛАСУЕТСЯ С ДРУГИМИ ТЕРМИНАМИ. кОНЕЧНО, СЛОВО "СОРТИРОВКА" И САМО 
ИМЕЕТ ДОВОЛЬНО МНОГО ЗНАЧЕНИЙ%
\note{2}{эТО В БОЛЬШЕЙ СТЕПЕНИ ОТНОСИТСЯ К АНГЛИЙСКОМУ СЛОВУ 
"sorting". зДЕСЬ АВТОР ПРИВОДЯТ ПРИМЕР: "нЕ was sort of out sorts after sorting 
that sort of data". (оН БЫЛ КАК БУДТО НЕ В ДУХЕ ПОСЛЕ СОРТИРОВКИ ТАКОГО СОРТА 
ДЕННЫХ), КОТОРЫЙ В РУССКОМ ПЕРЕВОДЕ НЕ СТОЛЬ ВЫРАЗИТЕЛЕН.--- {\sl пРИМ. 
ПЕРЕВ.\/}}, 
НО ОНО ПРОЧНО ВОШЛО В ПРОГРАММИСТСКИЙ ЖАРГОН. пОЭТОМУ МЫ БЕЗ 
ДАЛЬНЕЙШИХ ИЗВИНЕНИЙ БУДЕМ ИСПОЛЬЗОВАТЬ СЛОВО "СОРТИРОВКА" В УЗКОМ 
СМЫСЛЕ "СОРТИРОВКА ПО ПОРЯДКУ".
\medskip
вОТ НЕКОТОРЫЕ ИЗ НАИБОЛЕЕ ВАЖНЫХ ПРИМЕНЕНИЙ СОРТИРОВКИ:
\item{a)} рЕШЕНИЕ ЗАДАЧИ "ГРУППИРОВКИ", КОГДА НУЖНО СОБРАТЬ ВМЕСТЕ 
ВСЕ ЭЛЕМЕНТЫ С ОДИНАКОВЫМ ЗНАЧЕНИЕМ НЕКОТОРОГО ПРИЗНАКА. дОПУСТИМ, 
ИМЕЕТСЯ 10000 ЭЛЕМЕНТОВ, РАСПОЛОЖЕННЫХ В СЛУЧАЙНОМ ПОРЯДКЕ, ПРИЧЕМ 
ЗНАЧЕНИЯ МНОГИХ ИЗ НИХ РАВНЫ; И ПРЕДПОЛОЖИМ, НАМ НУЖНО 
ПЕРЕУПОРЯДОЧИТЬ ФАЙЛ ТАК, ЧТОБЫ ЭЛЕМЕНТЫ С РАВНЫМИ ЗНАЧЕНИЯМИ 
ЗАНИМАЛИ СОСЕДНИЕ ПОЗИЦИИ В ФАЙЛЕ. эТО, ПО СУЩЕСТВУ, ЗАДАЧА "СОРТИРОВКИ" 
В ШИРОКОМ СМЫСЛЕ СЛОВА, И ОНА ЛЕГКО МОЖЕТ БЫТЬ РЕШЕНА ПУТЕМ СОРТИРОВКИ 
ФАЙЛА В УЗКОМ СМЫСЛЕ СЛОВА, А ИМЕННО РАСПОЛОЖЕНИЕМ ЭЛЕМЕНТОВ В 
НЕУБЫВАЮЩЕМ ПОРЯДКЕ $v_1\le v_2 \le \ldots \le v_{10000}$. 
эФФЕКТИВНОСТЬЮ, КОТОРАЯ МОЖЕТ БЫТЬ ДОСТИГНУТА В ЭТОЙ ПРОЦЕДУРЕ, И 
ОБЎЯСНЯЕТСЯ ИЗМЕНЕНИЕ ПЕРВОНАЧАЛЬНОГО СМЫСЛА СЛОВА "СОРТИРОВКА".

\item{b)} еСЛИ ДВА ИЛИ БОЛЕЕ ФАЙЛА ОТСОРТИРОВАТЬ В ОДНОМ И ТОМ ЖЕ 
ПОРЯДКЕ, ТО МОЖНО ОТЫСКАТЬ В НИХ ВСЕ ОБЩИЕ ЭЛЕМЕНТЫ ЗА ОДИН 
ПОСЛЕДОВАТЕЛЬНЫЙ ПРОСМОТР ВСЕХ ФАЙЛОВ, БЕЗ ВОЗВРАТОВ. эТО ТОТ САМЫЙ 
ПРИНЦИП, КОТОРЫМ ВОСПОЛЬЗОВАЛСЯ пЕРРИ мЕЙСОН ДЛЯ РАСКРЫТИЯ ДЕЛА ОБ 
УБИЙСТВЕ (СМ. ЭПИГРАФЫ К ЭТОЙ ГЛАВЕ). оКАЗЫВАЕТСЯ, ЧТО, КАК ПРАВИЛО, 
ГОРАЗДО ЭКОНОМНЕЕ ПРОСМАТРИВАТЬ СПИСОК ПОСЛЕДОВАТЕЛЬНО, А НЕ 
ПЕРЕСКАКИВАЯ С МЕСТА НА МЕСТО СЛУЧАЙНЫМ ОБРАЗОМ, ЕСЛИ ТОЛЬКО СПИСОК НЕ 
НАСТОЛЬКО МАЛ, ЧТО ОН ЦЕЛИКОМ ПОМЕЩАЕТСЯ В ОПЕРАТИВНОЙ ПАМЯТИ. 
сОРТИРОВКА ПОЗВОЛЯЕТ ИСПОЛЬЗОВАТЬ ПОСЛЕДОВАТЕЛЬНЫЙ ДОСТУП К БОЛЬШИМ 
ФАЙЛАМ В КАЧЕСТВЕ ПРИЕМЛЕМОЙ ЗАМЕНЫ ПРЯМОЙ АДРЕСАЦИИ.

\item{c)} кАК МЫ УВИДИМ В ГЛ. 6, СОРТИРОВКА ПОМОГАЕТ И ПРИ ПОИСКЕ, С ЕЕ 
ПОМОЩЬЮ МОЖНО СДЕЛАТЬ ВЫДАЧИ эвм БОЛЕЕ УДОБНЫМИ ДЛЯ ЧЕЛОВЕЧЕСКОГО 
ВОСПРИЯТИЯ. в САМОМ ДЕЛЕ, ЛИСТИНГ (НАПЕЧАТАННЫЙ 
%% 15
МАШИНОЙ ДОКУМЕНТ), ОТСОРТИРОВАННЫЙ В АЛФАВИТНОМ ПОРЯДКЕ, ЗАЧАСТУЮ 
ВЫГЛЯДИТ ВЕСЬМА ВНУШИТЕЛЬНО, ДАЖЕ ЕСЛИ СООТВЕТСТВУЮЩИЕ ЧИСЛОВЫЕ 
ДАННЫЕ БЫЛИ РАССЧИТАНЫ НЕВЕРНО.

хОТЯ СОРТИРОВКА ТРАДИЦИОННО И БОЛЬШЕЙ ЧАСТЬЮ ИСПОЛЬЗОВАЛАСЬ ДЛЯ 
ОБРАБОТКИ КОММЕРЧЕСКИХ ДАННЫХ, НА САМОМ ДЕЛЕ ОНА ЯВЛЯЕТСЯ 
ИНСТРУМЕНТОМ, ПОЛЕЗНЫМ В САМЫХ РАЗНЫХ СИТУАЦИЯХ, И ПОЭТОМУ О НЕМ НЕ 
СЛЕДУЕТ ЗАБЫВАТЬ; в УПР. 2.3.2--17 МЫ ОБСУДИЛИ ЕЕ ПРИМЕНЕНИЕ ДЛЯ 
УПРОЩЕНИЯ АЛГЕБРАИЧЕСКИХ ФОРМУЛ. уПРАЖНЕНИЯ, ПРИВЕДЕННЫЕ НИЖЕ, 
ИЛЛЮСТРИРУЮТ РАЗНООБРАЗИЕ ТИПИЧНЫХ ПРИМЕНЕНИЙ СОРТИРОВКИ.

оДНОЙ ИЗ ПЕРВЫХ КРУПНЫХ СИСТЕМ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ, 
ПРОДЕМОНСТРИРОВАВШИХ БОГАТЫЕ ВОЗМОЖНОСТИ СОРТИРОВКИ, БЫЛ КОМПИЛЯТОР 
Larc Scientific Compiler, РАЗРАБОТАННЫЙ ФИРМОЙ Computer Sciences 
Corporation В 1960~Г. в ЭТОМ ОПТИМИЗИРУЮЩЕМ КОМПИЛЯТОРЕ ДЛЯ 
РАСШИРЕННОГО фортранА СОРТИРОВКА ИСПОЛЬЗОВАЛАСЬ ВЕСЬМА ИНТЕНСИВНО, 
ТАК ЧТО РАЗЛИЧНЫЕ АЛГОРИТМЫ КОМПИЛЯЦИИ РАБОТАЛИ С ОТНОСЯЩИМИСЯ К НИМ 
ЧАСТЯМИ ИСХОДНОЙ ПРОГРАММЫ, РАСПОЛОЖЕННЫМИ В УДОБНОЙ 
ПОСЛЕДОВАТЕЛЬНОСТИ. пРИ ПЕРВОМ ПРОСМОТРЕ ОСУЩЕСТВЛЯЛСЯ ЛЕКСИЧЕСКИЙ 
АНАЛИЗ, Т. Е. ВЫДЕЛЕНИЕ В ИСХОДНОЙ ПРОГРАММЕ ЛЕКСИЧЕСКИХ ЕДИНИЦ (ЛЕКСЕМ), 
КАЖДАЯ ИЗ КОТОРЫХ СООТВЕТСТВУЕТ ЛИБО ИДЕНТИФИКАТОРУ (ИМЕНИ 
ПЕРЕМЕННОЙ), ЛИБО КОНСТАНТЕ, ЛИБО ОПЕРАТОРУ И Т. Д. кАЖДАЯ ЛЕКСЕМА 
ПОЛУЧАЛА НЕСКОЛЬКО ПОРЯДКОВЫХ НОМЕРОВ. в РЕЗУЛЬТАТЕ СОРТИРОВКИ ПО 
ИМЕНАМ И СООТВЕТСТВУЮЩИМ ПОРЯДКОВЫМ НОМЕРАМ ВСЕ ИСПОЛЬЗОВАНИЯ 
ДАННОГО ИДЕНТИФИКАТОРА ОКАЗЫВАЛИСЬ СОБРАННЫМИ ВМЕСТЕ. "оПРЕДЕЛЯЮЩИЕ 
ВХОЖДЕНИЯ", СПЕЦИФИЦИРУЮЩИЕ ИДЕНТИФИКАТОР КАК ИМЯ ФУНКЦИИ, ПАРАМЕТР 
ИЛИ МНОГОМЕРНУЮ ПЕРЕМЕННУЮ, ПОЛУЧАЛИ МЕНЬШИЕ НОМЕРА, ПОЭТОМУ ОНИ 
ОКАЗЫВАЛИСЬ ПЕРВЫМИ В ПОСЛЕДОВАТЕЛЬНОСТИ ЛЕКСЕМ, ОТВЕЧАЮЩИХ ЭТОМУ 
ИДЕНТИФИКАТОРУ. тЕМ САМЫМ ОБЛЕГЧАЛАСЬ ПРОВЕРКА ПРАВИЛЬНОСТИ 
УПОТРЕБЛЕНИЯ ИДЕНТИФИКАТОРОВ, РАСПРЕДЕЛЕНИЕ ПАМЯТИ С УЧЕТОМ ДЕКЛАРАЦИЙ 
ЭКВИВАЛЕНТНОСТИ И Т. Д. сОБРАННАЯ ТАКИМ ОБРАЗОМ ИНФОРМАЦИЯ О КАЖДОМ 
ИДЕНТИФИКАТОРЕ ПРИСОЕДИНЯЛАСЬ К СООТВЕТСТВУЮЩЕЙ ЛЕКСЕМЕ. пОЭТОМУ НЕ 
БЫЛО НЕОБХОДИМОСТИ ХРАНИТЬ В ОПЕРАТИВНОЙ ПАМЯТИ "ТАБЛИЦУ СИМВОЛОВ", 
СОДЕРЖАЩУЮ СВЕДЕНИЯ ОБ ИДЕНТИФИКАТОРАХ. пОСЛЕ ТАКОЙ ОБРАБОТКИ ЛЕКСЕМЫ 
СНОВА СОРТИРОВАЛИСЬ ПО ДРУГОМУ ПОРЯДКОВОМУ НОМЕРУ; В РЕЗУЛЬТАТЕ В 
ПРОГРАММЕ, ПО СУЩЕСТВУ, ВОССТАНАВЛИВАЛСЯ ПЕРВОНАЧАЛЬНЫЙ ПОРЯДОК, ЕСЛИ 
НЕ СЧИТАТЬ ТОГО, ЧТО АРИФМЕТИЧЕСКИЕ ВЫРАЖЕНИЯ ОКАЗЫВАЛИСЬ ЗАПИСАННЫМИ 
В БОЛЕЕ УДОБНОЙ, "ПОЛЬСКОЙ ПРЕФИКСНОЙ" ФОРМЕ. сОРТИРОВКА 
ИСПОЛЬЗОВАЛАСЬ И НА ПОСЛЕДУЮЩИХ ФАЗАХ КОМПИЛЯЦИИ---ДЛЯ ОБЛЕГЧЕНИЯ 
ОПТИМИЗАЦИИ ЦИКЛОВ, ВКЛЮЧЕНИЯ В ЛИСТИНГ СООБЩЕНИЙ ОБ ОШИБКАХ И Т. Д. 
кОРОЧЕ ГОВОРЯ, КОМПИЛЯТОР БЫЛ УСТРОЕН ТАК, ЧТО ВСЮ ОБРАБОТКУ ФАЙЛОВ, 
ХРАНЯЩИХСЯ НА БАРАБАНАХ, ФАКТИЧЕСКИ МОЖНО БЫЛО ВЕСТИ ПОСЛЕДОВАТЕЛЬНО. 
пОЭТОМУ-ТО ДАННЫЕ И СНАБЖАЛИСЬ ТАКИМИ ПОРЯДКОВЫМИ НОМЕРАМИ,
%% 16
КОТОРЫЕ ПОЗВОЛЯЛИ УПОРЯДОЧИВАТЬ ЭТИ ДАННЫЕ РАЗЛИЧНЫМИ УДОБНЫМИ 
СПОСОБАМИ.

дРУГОЕ, БОЛЕЕ ОЧЕВИДНОЕ ПРИМЕНЕНИЕ СОРТИРОВКИ ВОЗНИКАЕТ ПРИ 
РЕДАКТИРОВАНИИ ФАЙЛОВ, ГДЕ КАЖДАЯ СТРОКА СНАБЖЕНА КЛЮЧОМ. пОКА 
ПОЛЬЗОВАТЕЛЬ ВНОСИТ С КЛАВИАТУРЫ ИЗМЕНЕНИЯ И ДОБАВЛЕНИЯ, НЕОБЯЗАТЕЛЬНО 
ДЕРЖАТЬ ВЕСЬ ФАЙЛ В ОПЕРАТИВНОЙ ПАМЯТИ. вСЕ ИЗМЕНЯЕМЫЕ СТРОКИ МОЖНО 
ПОЗДНЕЕ ОТСОРТИРОВАТЬ (А ОНИ И ТАК ОБЫЧНО В ОСНОВНОМ УПОРЯДОЧЕНЫ) И 
СЛИТЬ С ИСХОДНЫМ ФАЙЛОМ. эТО ДАЕТ ВОЗМОЖНОСТЬ РАЗУМНО ИСПОЛЬЗОВАТЬ 
ПАМЯТЬ В РЕЖИМЕ МУЛЬТИПРОГРАММИРОВАНИЯ. 
[сР. С с. с. Foster, {\sl Comp. J.\/}, {\bf  11} (1968), 134--137].

пОСТАВЩИКИ ВЫЧИСЛИТЕЛЬНЫХ МАШИН СЧИТАЮТ, ЧТО В СРЕДНЕМ БОЛЕЕ 25\% 
МАШИННОГО ВРЕМЕНИ СИСТЕМАТИЧЕСКИ ТРАТИТСЯ НА СОРТИРОВКУ. вО МНОГИХ 
ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ НА НЕЕ УХОДИТ БОЛЬШЕ ПОЛОВИНЫ МАШИННОГО 
ВРЕМЕНИ. иЗ ЭТОЙ СТАТИСТИКИ МОЖНО ЗАКЛЮЧИТЬ, ЧТО ЛИБО (i) СОРТИРОВКА 
ИМЕЕТ МНОГО ВАЖНЫХ ПРИМЕНЕНИЙ, ЛИБО (ii) ЕЮ ЧАСТО ПОЛЬЗУЮТСЯ БЕЗ НУЖДЫ, 
ЛИБО (iii) ПРИМЕНЯЮТСЯ В ОСНОВНОМ НЕЭФФЕКТИВНЫЕ АЛГОРИТМЫ СОРТИРОВКИ. 
пО-ВИДИМОМУ, КАЖДОЕ ИЗ ТРЕХ ПРЕДПОЛОЖЕНИЙ СОДЕРЖИТ ДОЛЮ ИСТИНЫ. вО 
ВСЯКОМ СЛУЧАЕ ЯСНО, ЧТО СОРТИРОВКА ЗАСЛУЖИВАЕТ СЕРЬЕЗНОГО ИЗУЧЕНИЯ С 
ТОЧКИ ЗРЕНИЯ ЕЕ ПРАКТИЧЕСКОГО ИСПОЛЬЗОВАНИЯ.

нО ДАЖЕ ЕСЛИ БЫ СОРТИРОВКА БЫЛА ПОЧТИ БЕСПОЛЕЗНА, НАШЛАСЬ БЫ МАССА 
ДРУГИХ ПРИЧИН ЗАНЯТЬСЯ ЕЮ! иЗОБРЕТАТЕЛЬНЫЕ АЛГОРИТМЫ СОРТИРОВКИ 
ГОВОРЯТ О ТОМ, ЧТО ОНА И САМА ПО СЕБЕ ИНТЕРЕСНА КАК ОБЎЕКТ ИССЛЕДОВАНИЯ. в 
ЭТОЙ ОБЛАСТИ СУЩЕСТВУЕТ МНОЖЕСТВО УВЛЕКАТЕЛЬНЫХ НЕРЕШЕННЫХ ЗАДАЧ 
НАРЯДУ С ВЕСЬМА НЕМНОГИМИ УЖЕ РЕШЕННЫМИ.

рАССМАТРИВАЯ ВОПРОС В БОЛЕЕ ШИРОКОМ ПЛАНЕ, МЫ ОБНАРУЖИМ, ЧТО 
АЛГОРИТМЫ СОРТИРОВКИ ПРЕДСТАВЛЯЮТ СОБОЙ ИНТЕРЕСНЫЙ ЧАСТНЫЙ ПРИМЕР 
ТОГО, КАК СЛЕДУЕТ ПОДХОДИТЬ К РЕШЕНИЮ ПРОБЛЕМ ПРОГРАММИРОВАНИЯ ВООБЩЕ. 
мЫ ПОЗНАКОМИМСЯ СО МНОГИМИ ВАЖНЫМИ ПРИНЦИПАМИ МАНИПУЛИРОВАНИЯ СО 
СТРУКТУРАМИ ДАННЫХ И ПРОСЛЕДИМ ЗА ЭВОЛЮЦИЕЙ РАЗЛИЧНЫХ МЕТОДОВ 
СОРТИРОВКИ, ПРИЧЕМ ЧИТАТЕЛЮ ЧАСТО БУДЕТ ПРЕДОСТАВЛЯТЬСЯ ВОЗМОЖНОСТЬ 
САМОМУ "ОТКРЫВАТЬ" ТЕ ЖЕ ИДЕИ, КАК БУДТО БЫ ДО НЕГО НИКТО С ПОДОБНЫМИ 
ЗАДАЧАМИ НЕ СТАЛКИВАЛСЯ. оБОБЩЕНИЕ ЭТИХ ЧАСТНЫХ МЕТОДОВ ПОЗВОЛИТ НАМ В 
ЗНАЧИТЕЛЬНОЙ СТЕПЕНИ ОВЛАДЕТЬ ТЕМИ СПОСОБАМИ МЫШЛЕНИЯ, КОТОРЫЕ 
ПОМОГУТ СОЗДАВАТЬ ДОБРОТНЫЕ АЛГОРИТМЫ ДЛЯ РЕШЕНИЯ ДРУГИХ ПРОБЛЕМ, 
СВЯЗАННЫХ С эвм.

мЕТОДЫ СОРТИРОВКИ СЛУЖАТ ВЕЛИКОЛЕПНОЙ ИЛЛЮСТРАЦИЕЙ ИДЕЙ 
\emph{ АНАЛИЗА АЛГОРИТМОВ}, Т. Е. ИДЕЙ, ПОЗВОЛЯЮЩИХ ОЦЕНИВАТЬ РАБОЧИЕ 
ХАРАКТЕРИСТИКИ АЛГОРИТМОВ, А ЗНАЧИТ, РАЗУМНО ВЫБИРАТЬ СРЕДИ. КАЗАЛОСЬ БЫ, 
РАВНОЦЕННЫХ МЕТОДОВ. чИТАТЕЛИ, ИМЕЮЩИЕ СКЛОННОСТЬ К МАТЕМАТИКЕ, НАЙДУТ 
В ЭТОЙ ГЛАВЕ НЕМАЛО СПОСОБОВ ОЦЕНКИ СКОРОСТИ РАБОТЫ АЛГОРИТМОВ И 
МЕТОДОВ РЕШЕНИЯ СЛОЖНЫХ РЕКУРРЕНТНЫХ                                        
%% 17
СООТНОШЕНИЙ. с ДРУГОЙ СТОРОНЫ, ИЗЛОЖЕНИЕ ПОСТРОЕНО ТАК, ЧТО ЧИТАТЕЛИ, НЕ 
ИМЕЮЩИЕ ТАКОЙ СКЛОННОСТИ, МОГУТ БЕЗБОЛЕЗНЕННО ПРОПУСКАТЬ ВЫКЛАДКИ.

пРЕЖДЕ ЧЕМ ДВИГАТЬСЯ ДАЛЬШЕ, НЕОБХОДИМО БОЛЕЕ ЧЕТКО ОПРЕДЕЛИТЬ 
ЗАДАЧУ И ВВЕСТИ СООТВЕТСТВУЮЩУЮ ТЕРМИНОЛОГИЮ. пУСТЬ НАДО УПОРЯДОЧИТЬ 
$N$ ЭЛЕМЕНТОВ
$$
 R_1, R_2, \ldots, R_N.
$$
нАЗОВЕМ ИХ \dfn{ЗАПИСЯМИ}, А ВСЮ СОВОКУПНОСТЬ N ЗАПИСЕЙ НАЗОВЕМ 
\dfn{ФАЙЛОМ}. кАЖДАЯ ЗАПИСЬ $R_j$ ИМЕЕТ \dfn{КЛЮЧ} $K_j$, КОТОРЫЙ И 
УПРАВЛЯЕТ ПРОЦЕССОМ СОРТИРОВКИ. пОМИМО КЛЮЧА, ЗАПИСЬ МОЖЕТ СОДЕРЖАТЬ 
ДОПОЛНИТЕЛЬНУЮ, "СОПУТСТВУЮЩУЮ ИНФОРМАЦИЮ", КОТОРАЯ НЕ ВЛИЯЕТ НА 
СОРТИРОВКУ, НО ВСЕГДА ОСТАЕТСЯ В ЭТОЙ ЗАПИСИ.

оТНОШЕНИЕ ПОРЯДКА "$<$" НА МНОЖЕСТВЕ КЛЮЧЕЙ ВВОДИТСЯ ТАКИМ 
ОБРАЗОМ, ЧТОБЫ ДЛЯ ЛЮБЫХ ТРЕХ ЗНАЧЕНИЙ КЛЮЧЕЙ $a$, $b$, $c$ 
ВЫПОЛНЯЛИСЬ СЛЕДУЮЩИЕ УСЛОВИЯ:

\item{i)} СПРАВЕДЛИВО ОДНО И ТОЛЬКО ОДНО ИЗ СООТНОШЕНИЙ $a<b$, 
$a=b$, $b<a$  (ЗАКОН ТРИХОТОМИИ);

\item{ii)} ЕСЛИ $a<b$  И $b<c$, ТО $a<c$ (ЗАКОН ТРАНЗИТИВНОСТИ).

эТИ ДВА СВОЙСТВА ОПРЕДЕЛЯЮТ МАТЕМАТИЧЕСКОЕ ПОНЯТИЕ \dfn{ЛИНЕЙНОГО 
УПОРЯДОЧЕНИЯ}, НАЗЫВАЕМОГО ЕЩЕ \dfn{СОВЕРШЕННЫМ УПОРЯДОЧЕНИЕМ}. лЮБОЕ 
МНОЖЕСТВО С ОТНОШЕНИЕМ "$<$", УДОВЛЕТВОРЯЮЩИМ СВОЙСТВАМ (i) И (ii), 
ПОДДАЕТСЯ СОРТИРОВКЕ БОЛЬШИНСТВОМ МЕТОДОВ, ОПИСАННЫХ В ЭТОЙ ГЛАВЕ, ХОТЯ 
НЕКОТОРЫЕ ИЗ НИХ ГОДЯТСЯ ТОЛЬКО ДЛЯ ЧИСЛОВЫХ И БУКВЕННЫХ КЛЮЧЕЙ С 
ОБЫЧНЫМ ОТНОШЕНИЕМ ПОРЯДКА.

зАДАЧА СОРТИРОВКИ---НАЙТИ ТАКУЮ ПЕРЕСТАНОВКУ ЗАПИСЕЙ 
$Р(1)$ $Р(2)$ \dots\ $Р(N)$, ПОСЛЕ КОТОРОЙ КЛЮЧИ РАСПОЛОЖИЛИСЬ БЫ В 
НЕУБЫВАЮЩЕМ ПОРЯДКЕ:
$$
K_{Р (1)} \le  K_{p (2)} \le \cdots \le K_{p(n)}. \eqno  (1)
$$

сОРТИРОВКА НАЗЫВАЕТСЯ \dfn{УСТОЙЧИВОЙ}, ЕСЛИ ОНА УДОВЛЕТВОРЯЕТ 
ДОПОЛНИТЕЛЬНОМУ УСЛОВИЮ, ЧТО ЗАПИСИ С ОДИНАКОВЫМИ КЛЮЧАМИ ОСТАЮТСЯ В 
ПРЕЖНЕМ ПОРЯДКЕ, Т. Е. 
$$
p(i)<p(j), \rem{ЕСЛИ  $K_{p(i)}=K_{p(j)}$  И $i<j$.} \eqno  (2)
$$

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

нЕКОТОРЫЕ МЕТОДЫ СОРТИРОВКИ ПРЕДПОЛАГАЮТ СУЩЕСТВОВАНИЕ ВЕЛИЧИН 
"$\infty$" И "$-\infty$" ИЛИ ОДНОЙ ИЗ НИХ. вЕЛИЧИНА "$\infty$" СЧИТАЕТСЯ 
БОЛЬШЕ, А ВЕЛИЧИНА "$-\infty$" МЕНЬШЕ ЛЮБОГО КЛЮЧА:
$$
 -\infty < K_j <\infty, \qquad  1\le j \le N. \eqno (3)
$$
%% 18
эТИ ВЕЛИЧИНЫ ИСПОЛЬЗУЮТСЯ В КАЧЕСТВЕ ИСКУССТВЕННЫХ КЛЮЧЕЙ, А ТАКЖЕ КАК 
ГРАНИЧНЫЕ ПРИЗНАКИ. рАВЕНСТВО В (3), ВООБЩЕ ГОВОРЯ, ИСКЛЮЧЕНО. еСЛИ ЖЕ 
ОНО ТЕМ НЕ МЕНЕЕ ДОПУСКАЕТСЯ, АЛГОРИТМЫ МОЖНО МОДИФИЦИРОВАТЬ ТАК, 
ЧТОБЫ ОНИ ВСЕ-ТАКИ РАБОТАЛИ, ХОТЯ НЕРЕДКО ПРИ ЭТОМ ИХ ИЗЯЩЕСТВО И 
ЭФФЕКТИВНОСТЬ ОТЧАСТИ УТРАЧИВАЮТСЯ.

оБЫЧНО СОРТИРОВКУ ПОДРАЗДЕЛЯЮТ НА ДВА КЛАССА: \emph{ВНУТРЕННЮЮ}, 
КОГДА ВСЕ ЗАПИСИ ХРАНЯТСЯ В БЫСТРОЙ ОПЕРАТИВНОЙ ПАМЯТИ, И 
\emph{ВНЕШНЮЮ}, КОГДА ВСЕ ОНИ ТАМ НЕ ПОМЕЩАЮТСЯ. пРИ ВНУТРЕННЕЙ 
СОРТИРОВКЕ ИМЕЮТСЯ БОЛЕЕ ГИБКИЕ ВОЗМОЖНОСТИ ДЛЯ ПОСТРОЕНИЯ СТРУКТУР 
ДАННЫХ И ДОСТУПА К НИМ, ВНЕШНЯЯ ЖЕ ПОКАЗЫВАЕТ, КАК ПОСТУПАТЬ В УСЛОВИЯХ 
СИЛЬНО ОГРАНИЧЕННОГО ДОСТУПА.

дОСТАТОЧНО ХОРОШИЙ ОБЩИЙ АЛГОРИТМ ЗАТРАЧИВАЕТ НА СОРТИРОВКУ $N$ 
ЗАПИСЕЙ ВРЕМЯ ПОРЯДКА $N \log N$; ПРИ ЭТОМ ТРЕБУЕТСЯ ОКОЛО $\log N$ 
"ПРОХОДОВ" ПО ДАННЫМ. кАК МЫ УВИДИМ В П.~5.3.1, ЭТО МИНИМАЛЬНОЕ ВРЕМЯ. 
тАК, ЕСЛИ УДВОИТЬ ЧИСЛО ЗАПИСЕЙ, ТО И ВРЕМЯ ПРИ ПРОЧИХ РАВНЫХ УСЛОВИЯХ 
ВОЗРАСТЕТ НЕМНОГИМ БОЛЕЕ ЧЕМ ВДВОЕ. (нА САМОМ ДЕЛЕ, КОГДА $N$ СТРЕМИТСЯ К 
$\infty$, ВРЕМЯ"РАСТЕТ КАК $N(\log N)^2$, ЕСЛИ ВСЕ КЛЮЧИ РАЗЛИЧНЫ, ТАК КАК И 
РАЗМЕРЫ КЛЮЧЕЙ УВЕЛИЧИВАЮТСЯ С РОСТОМ $N$; НО ПРАКТИЧЕСКИ $N$ ВСЕГДА 
ОСТАЕТСЯ ОГРАНИЧЕННЫМ.)

\excercises  (первая часть)
\ex[м20] дОКАЖИТЕ, ЧТО ИЗ ЗАКОНОВ ТРИХОТОМИИ И ТРАНЗИТИВНОСТИ 
ВЫТЕКАЕТ \emph{ЕДИНСТВЕННОСТЬ} ПЕРЕСТАНОВКИ $Р(1)$, $Р(2)$, \dots, $Р(N)$, 
ЕСЛИ СОРТИРОВКА УСТОЙЧИВА.

\ex[21] пУСТЬ КАЖДАЯ ЗАПИСЬ $R$. НЕКОТОРОГО ФАЙЛА ИМЕЕТ \emph{ДВА} 
КЛЮЧА: "БОЛЬШОЙ КЛЮЧ" $K_j$ И "МАЛЫЙ КЛЮЧ" $k_j$, ПРИЧЕМ ОБА МНОЖЕСТВА 
КЛЮЧЕЙ ЛИНЕЙНО УПОРЯДОЧЕНЫ. тОГДА МОЖНО ОБЫЧНЫМ СПОСОБОМ ВВЕСТИ 
"ЛЕКСИКОГРАФИЧЕСКИЙ ПОРЯДОК" НА МНОЖЕСТВЕ ПАР КЛЮЧЕЙ $(к, k)$:
$$
(K_i, k_i) < (K_j, k_j),
\rem{ ЕСЛИ $K_i<K_j$  ИЛИ ЕСЛИ $K_i=K_j$  И $k_i<k_j$}.
$$

нЕКТО (НАЗОВЕМ ЕГО МИСТЕР $а$) ОТСОРТИРОВАЛ ЭТОТ ФАЙЛ СНАЧАЛА ПО 
БОЛЬШИМ КЛЮЧАМ, ПОЛУЧИВ $n$ ГРУПП ЗАПИСЕЙ С ОДИНАКОВЫМИ БОЛЬШИМИ 
КЛЮЧАМИ В КАЖДОЙ ГРУППЕ:
$$
K_{p(1)}=\cdots=K_{p(i_1)}<K_{p(i_1+1)}=\cdots=K_{p(i_2)}<\cdots 
< K_{p(i_{n-1}+1)} = \cdots = K_{p(i_n)},
$$
ГДЕ $i_n=N$. зАТЕМ КАЖДУЮ ИЗ  $n$ ГРУПП $R_{p(i_{j-1}+1)}$, \dots, 
$R_{p(i_j)}$ ОН ОТСОРТИРОВАЛ  ПО МАЛЫМ КЛЮЧАМ.

тОТ ЖЕ ИСХОДНЫЙ ФАЙЛ ВЗЯЛ МИСТЕР $в$ И ОТСОРТИРОВАЛ ЕГО СНАЧАЛА ПО 
МАЛЫМ КЛЮЧАМ, А ПОТОМ ПОЛУЧИВШИЙСЯ ФАЙЛ ОТСОРТИРОВАЛ ПО БОЛЬШИМ 
КЛЮЧАМ.

вЗЯВ ТОТ ЖЕ ИСХОДНЫЙ ФАЙЛ, МИСТЕР $с$ ОТСОРТИРОВАЛ ЕГО ОДИН РАЗ, 
ПОЛЬЗУЯСЬ ЛЕКСИКОГРАФИЧЕСКИМ ПОРЯДКОМ МЕЖДУ ПАРАМИ КЛЮЧЕЙ 
$(K_j, k_j)$.

пОЛУЧИЛОСЬ. ЛИ У ВСЕХ ТРОИХ ОДНО И ТО ЖЕ?
%% 19
\ex [M25] пУСТЬ НА МНОЖЕСТВЕ $K_1$, \dots, $K_N$  ОПРЕДЕЛЕНО ОТНОШЕНИЕ 
$<$, ДЛЯ КОТОРОГО ЗАКОН ТРИХОТОМИИ ВЫПОЛНЯЕТСЯ, А ЗАКОН ТРАНЗИТИВНОСТИ---
\emph{НЕТ}. дОКАЖИТЕ, ЧТО И В ЭТОМ СЛУЧАЕ ВОЗМОЖНА УСТОЙЧИВАЯ СОРТИРОВКА 
ЗАПИСЕЙ, Т. Е. ТАКАЯ, ЧТО ВЫПОЛНЯЮТСЯ УСЛОВИЯ (1) И (2); НА САМОМ ДЕЛЕ 
СУЩЕСТВУЮТ ПО КРАЙНЕЙ МЕРЕ ТРИ РАСПОЛОЖЕНИЯ ЗАПИСЕЙ, УДОВЛЕТВОРЯЮЩИХ 
ЭТИМ УСЛОВИЯМ!

\ex[15] мИСТЕР тУПИЦА (ПРОГРАММИСТ) ЗАХОТЕЛ УЗНАТЬ, НАХОДИТСЯ ЛИ В 
ЯЧЕЙКЕ |а| МАШИНЫ \MIX\ ЧИСЛО, БОЛЬШЕЕ ЧИСЛА ИЗ ЯЧЕЙКИ |в|, МЕНЬШЕЕ ИЛИ ЖЕ 
РАВНОЕ ЕМУ. оН НАПИСАЛ
$$
\eqalign{
&|LDA а |\cr
&|SUB в|\cr
}
 $$
А ПОТОМ ПРОВЕРИЛ, КАКОЙ РЕЗУЛЬТАТ ПОЛУЧИЛСЯ В |rA|: ПОЛОЖИТЕЛЬНОЕ ЧИСЛО, 
ОТРИЦАТЕЛЬНОЕ ИЛИ НУЛЬ. кАКУЮ СЕРЬЕЗНУЮ ОШИБКУ ОН ДОПУСТИЛ И КАК ДОЛЖЕН 
БЫЛ ПОСТУПИТЬ?

\ex [17] нАПИШИТЕ \MIX-ПОДПРОГРАММУ ДЛЯ СРАВНЕНИЯ КЛЮЧЕЙ, ЗАНИМАЮЩИХ 
НЕСКОЛЬКО СЛОВ, ИСХОДЯ ИЗ СЛЕДУЮЩИХ УСЛОВИЙ:
\ctable{#\hfill\bskip&\hsize=10cm\noindent\vtop{#}\hfill\cr
вЫЗОВ: &   |JMP COMPARE| \cr
сОСТОЯНИЕ ПРИ ВХОДЕ:  &     
$|rI1|=n$; $|CONTENTS|(A+k)=a_k$, $|CONTENTS|(B+k)=b_k$ ПРИ 
$1\le{} k\le{} n$; ПРЕДПОЛАГАЕТСЯ, ЧТО $n \ge{} 1$.\cr
сОСТОЯНИЕ ПРИ ВЫХОДЕ: &      
$|сI|=+1$, ЕСЛИ $(a_n, \dots, a_1) > (b_n, ..., b_1)$; \cr
 & $|сI|=0$, ЕСЛИ $(a_n, \dots, a_1) = (b_n, ..., b_1)$;\cr
& $|CI|=-1$, ЕСЛИ $(a_n, \dots, a_1)< (b_n, ..., b_1)$; \cr
& |rX| И |rI1|, ВОЗМОЖНО, ИЗМЕНИЛИСЬ.\cr
}
зДЕСЬ ОТНОШЕНИЕ $(a_n, \dots, a_1) < (b_n, ..., b_1)$ ОБОЗНАЧАЕТ 
ЛЕКСИКОГРАФИЧЕСКОЕ УПОРЯДОЧЕНИЕ СЛЕВА НАПРАВО, Т. Е. СУЩЕСТВУЕТ ИНДЕКС $j$, 
ТАКОЙ, ЧТО $a_k=b_k$ ПРИ $П\ge{} k > j$, НО $А_j < b_j$.

\ex[30] в ЯЧЕЙКАХ |A| И |в| СОДЕРЖАТСЯ СООТВЕТСТВЕННО ЧИСЛА $А$ И~$b$. 
пОКАЖИТЕ, ЧТО МОЖНО НАПИСАТЬ \MIX-ПРОГРАММУ, КОТОРАЯ БЫ ВЫЧИСЛЯЛА 
$\min (a, b)$ И ЗАПИСЫВАЛА РЕЗУЛЬТАТ В ЯЧЕЙКУ |с|, \emph{НЕ ПОЛЬЗУЯСЬ 
КОМАНДАМИ ПЕРЕХОДА.} (\emph{пРЕДОСТЕРЕЖЕНИЕ:} ПОСКОЛЬКУ АРИФМЕТИЧЕСКОЕ 
ПЕРЕПОЛНЕНИЕ НЕВОЗМОЖНО ОБНАРУЖИТЬ БЕЗ КОМАНД ПЕРЕХОДА, РАЗУМНО ТАК 
ПОСТРОИТЬ ПРОГРАММУ, ЧТОБЫ ПЕРЕПОЛНЕНИЕ НЕ МОГЛО ВОЗНИКНУТЬ НИ ПРИ КАКИХ 
ЗНАЧЕНИЯХ $А$ И~$b$)

\ex[м27] кАКОВА ВЕРОЯТНОСТЬ ТОГО, ЧТО ПОСЛЕ СОРТИРОВКИ В НЕУБЫВАЮЩЕМ 
ПОРЯДКЕ |N| НЕЗАВИСИМЫХ РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ НА ОТРЕЗКЕ $[0, 1]$ 
СЛУЧАЙНЫХ ВЕЛИЧИН $r$-Е ОТ НАЧАЛА ЧИСЛО ОКАЖЕТСЯ $\le{} x$?

\excercises упражнения (вторая часть)
в КАЖДОМ ИЗ ЭТИХ УПРАЖНЕНИЙ ПОСТАВЛЕНА ЗАДАЧА, С КОТОРОЙ МОЖЕТ 
СТОЛКНУТЬСЯ ПРОГРАММИСТ. пРЕДЛОЖИТЕ "ХОРОШЕЕ" РЕШЕНИЕ ЗАДАЧИ, 
ПРЕДПОЛАГАЯ, ЧТО ИМЕЕТСЯ СРАВНИТЕЛЬНО НЕБОЛЬШАЯ ОПЕРАТИВНАЯ ПАМЯТЬ И 
ОКОЛО ПОЛУДЮЖИНЫ, ЛЕНТОПРОТЯЖНЫХ УСТРОЙСТВ (ЭТОГО КОЛИЧЕСТВА ДОСТАТОЧНО 
ДЛЯ СОРТИРОВКИ).

\ex[75] иМЕЕТСЯ ЛЕНТА, НА КОТОРОЙ ЗАПИСАН МИЛЛИОН СЛОВ ДАННЫХ. кАК 
ОПРЕДЕЛИТЬ, СКОЛЬКО НА ЭТОЙ ЛЕНТЕ РАЗЛИЧНЫХ СЛОВ?

\ex[18] вООБРАЗИТЕ СЕБЯ В РОЛИ уПРАВЛЕНИЯ ВНУТРЕННИХ ДОХОДОВ мИНИСТЕРСТВА
ФИНАНСОВ сша. вЫ ПОЛУЧАЕТЕ МИЛЛИОНЫ "ИНФОРМАЦИОННЫХ" КАРТОЧЕК ОТ 
ОРГАНИЗАЦИЙ О ТОМ, СКОЛЬКО, ДЕНЕГ ОНИ ВЫПЛАТИЛИ РАЗЛИЧНЫМ ЛИЦАМ, И 
МИЛЛИОНЫ "НАЛОГОВЫХ" КАРТОЧЕК ОТ РАЗЛИЧНЫХ ЛИЦ ОБ ИХ ДОХОДАХ. кАК БЫ ВЫ 
СТАЛИ ОТЫСКИВАТЬ ЛЮДЕЙ, КОТОРЫЕ СООБЩИЛИ НЕ ОБО ВСЕХ СВОИХ ДОХОДАХ?

%% 20
\ex[м25]{\sl (тРАНСПОНИРОВАНИЕ МАТРИЦЫ.)\/} иМЕЕТСЯ МАГНИТНАЯ ЛЕНТА, 
СОДЕРЖАЩАЯ МИЛЛИОН СЛОВ, КОТОРЫЕ ПРЕДСТАВЛЯЮТ СОБОЙ ЭЛЕМЕНТЫ 
$1000\times1000$-МАТРИЦЫ, ЗАПИСАННЫЕ ПО СТРОКАМ: $a_{1,1}$ $a_{1,2}$ \dots 
$a_{1,1000}$ $a_{2,1}$ \dots $a_{2,1000}$ \dots $a_{1000, 1000}$. вАША 
ЗАДАЧА---ПОЛУЧИТЬ ЛЕНТУ, НА КОТОРОЙ ЭЛЕМЕНТЫ ЭТОЙ МАТРИЦЫ БЫЛИ БЫ 
ЗАПИСАНЫ ПО СТОЛБЦАМ: $a_{1,1}$ $a_{2,1}$ \dots $a_{1000,1}$ $a_{1,2}$\dots 
$a_{1,2}$\dots $a_{1000,2}$ \dots $a_{1000, 1000}$ (пОСТАРАЙТЕСЬ СДЕЛАТЬ НЕ 
БОЛЕЕ ДЕСЯТИ ПРОСМОТРОВ ДАННЫХ.)

\ex[м26] в ВАШЕМ РАСПОРЯЖЕНИИ ДОВОЛЬНО БОЛЬШОЙ ФАЙЛ ИЗ $N$ СЛОВ. 
кАК БЫ ВЫ ЕГО "ПЕРЕТАСОВАЛИ" СЛУЧАЙНЫМ ОБРАЗОМ?

 \rex[24] в НЕКОМ УНИВЕРСИТЕТЕ РАБОТАЕТ ОКОЛО 1000 ПРЕПОДАВАТЕЛЕЙ И 
ИМЕЕТСЯ 500 КОМИТЕТОВ. сЧИТАЕТСЯ, ЧТО КАЖДЫЙ ПРЕПОДАВАТЕЛЬ ЯВЛЯЕТСЯ 
ЧЛЕНОМ ПО КРАЙНЕЙ МЕРЕ ДВУХ КОМИТЕТОВ. вАМ НУЖНО ПОДГОТОВИТЬ С ПОМОЩЬЮ 
МАШИНЫ УДОБОЧИТАЕМЫЕ СПИСКИ ЧЛЕНОВ ВСЕХ КОМИТЕТОВ. вЫ РАСПОЛАГАЕТЕ 
КОЛОДОЙ ИЗ ПРИБЛИЗИТЕЛЬНО 1500 ПЕРФОКАРТ, СЛОЖЕННЫХ ПРОИЗВОЛЬНЫМ 
ОБРАЗОМ И СОДЕРЖАЩИХ СЛЕДУЮЩУЮ ИНФОРМАЦИЮ:

{\it чЛЕНСКИЕ КАРТОЧКИ:\/} КОЛОНКА 1---ПРОБЕЛ; КОЛОНКИ 2--18---ФАМИЛИЯ С 
ПОСЛЕДУЮЩИМИ ПРОБЕЛАМИ; КОЛОНКИ 19--20---ИНИЦИАЛЫ; 
КОЛОНКИ 21--23---НОМЕР ПЕРВОГО кОМИТЕТА; 
КОЛОНКИ 24--26---НОМЕР ВТОРОГО КОМИТЕТА; \dots; 
КОЛОНКИ 78--80--- НОМЕР ДВАДЦАТОГО КОМИТЕТА (ЕСЛИ НУЖНО) ИЛИ ПРОБЕЛЫ.

{\it кОМИТЕТСКИЕ КАРТОЧКИ:\/} КОЛОНКА 1---"*"; КОЛОНКИ 2--77---НАЗВАНИЕ 
КОМИТЕТА; КОЛОНКИ 78--80---НОМЕР КОМИТЕТА. кАК ВЫ ДОЛЖНЫ ДЕЙСТВОВАТЬ? 
(оПИШИТЕ СВОЙ МЕТОД ДОСТАТОЧНО ПОДРОБНО.)

\ex[20] вЫ РАБОТАЕТЕ С ДВУМЯ ВЫЧИСЛИТЕЛЬНЫМИ СИСТЕМАМИ, В КОТОРЫХ 
ПО-РАЗНОМУ УПОРЯДОЧЕНЫ ЛИТЕРЫ (БУКВЫ И ЦИФРЫ). кАК ЗАСТАВИТЬ ПЕРВУЮ 
эвм СОРТИРОВАТЬ ФАЙЛЫ С БУКВЕННО-ЦИФРОВОЙ ИНФОРМАЦИЕЙ, 
ПРЕДНАЗНАЧЕННЫЕ ДЛЯ ИСПОЛЬЗОВАНИЯ НА ВТОРОЙ эвм?

\ex[18] иМЕЕТСЯ ДОВОЛЬНО БОЛЬШОЙ СПИСОК ЛЮДЕЙ, РОДИВШИХСЯ В сша, С 
УКАЗАНИЕМ ШТАТА, В КОТОРОМ ОНИ РОДИЛИСЬ. кАК ПОДСЧИТАТЬ ЧИСЛО ЛЮДЕЙ, 
РОДИВШИХСЯ В КАЖДОМ ШТАТЕ? (пРЕДПОЛАГАЕТСЯ, ЧТО НИ ОДИН ЧЕЛОВЕК НЕ УКАЗАН 
В СПИСКЕ БОЛЕЕ ОДНОГО РАЗА.)

\ex[20] чТОБЫ ОБЛЕГЧИТЬ ВНЕСЕНИЕ ИЗМЕНЕНИЙ В БОЛЬШИЕ ПРОГРАММЫ, 
НАПИСАННЫЕ НА фортранЕ, ВЫ ХОТИТЕ НАПИСАТЬ ПРОГРАММУ, 
ВЫПЕЧАТЫВАЮЩУЮ ТАБЛИЦУ "ПЕРЕКРЕСТНЫХ ССЫЛОК". вХОДНЫМИ ДАННЫМИ ДЛЯ 
НЕЕ СЛУЖИТ ПРОГРАММА НА фортранЕ, А В РЕЗУЛЬТАТЕ ПОЛУЧАЕТСЯ ЛИСТИНГ 
ИСХОДНОЙ ПРОГРАММЫ, СНАБЖЕННЫЙ УКАЗАТЕЛЕМ ВСЕХ СЛУЧАЕВ УПОТРЕБЛЕНИЯ 
КАЖДОГО ИДЕНТИФИКАТОРА (Т. Е. ИМЕНИ) В ПРОГРАММЕ. кАК НАПИСАТЬ ТАКУЮ 
ПРОГРАММУ?

{\def\cell#1{\vtop{\hsize=.49\hsize\noindent #1\par}}
 \def\+#1\cr{\line{\cell{#1}\hfil\cell{#2}}\smallskip}
\ex[33] (сОРТИРОВКА КАТАЛОЖНЫХ КАРТОЧЕК.) сПОСОБЫ СОСТАВЛЕНИЯ 
АЛФАВИТНЫХ КАТАЛОГОВ В РАЗНЫХ БИБЛИОТЕКАХ НЕСКОЛЬКО ОТЛИЧАЮТСЯ ДРУГ ОТ 
ДРУГА. в СЛЕДУЮЩЕМ "АЛФАВИТНОМ" СПИСКЕ СОДЕРЖАТСЯ РЕКОМЕНДАЦИИ, ВЗЯТЫЕ 
ИЗ ПРАВИЛ РЕГИСТРАЦИИ И ХРАНЕНИЯ КАТАЛОЖНЫХ КАРТОЧЕК аМЕРИКАНСКОЙ 
БИБЛИОТЕЧНОЙ АССОЦИАЦИИ (чИКАГО, 1942):
\medskip
\+ \centerline{\bf тЕКСТ КАРТОЧКИ}%
  &\centerline{\bf зАМЕЧАНИЯ}\cr
\+ R. Accademia nazionale dei Lincei, Rome 
  &в НАЗВАНИЯХ ИНОСТРАННЫХ (КРОМЕ БРИТАНСКИХ) УЧРЕЖДЕНИЙ СЛОВО "royalty" 
   (КОРОЛЕВСКИЙ) ИГНОРИРУЕТСЯ\cr
\+ 1812; ein historischer roman.  
  &Achtzehnhundert zw\"olf \cr
\+ Biblioth\`eque d'histoire r\'evolutionnaire. 
  &вО ФРАНЦУЗСКОМ ТЕКСТЕ  АПОСТРОФ РАССМАТРИВАЕТСЯ КАК ПРОБЕЛ \cr
\+ Biblioth\`eque des curiosit\'es.       
  &нАДСТРОЧНЫЕ ЗНАКИ ИГНОРИРУЮТСЯ \cr
\+ Brown, Mrs. J. Crosby       
  &уКАЗАНИЕ ПОЛОЖЕНИЯ (Mrs.) ИГНОРИРУЕТСЯ \cr
\+ Brown, John   
  &фАМИЛИИ С ДАТАМИ СЛЕДУЮТ ЗА ФАМИЛИЯМИ БЕЗ ДАТ~\dots \cr
\+ Brown, John, mathematician   
  &\dots{} КОТОРЫЕ УПОРЯДОЧИВАЮТСЯ ПО \cr
\+ Brown, John, of Boston
  &ОПИСАТЕЛЬНЫМ СЛОВАМ \cr
\+ Brown, John, 1715--1766
  &оДИНАКОВЫЕ ФАМИЛИИ УПОРЯДОЧИВАЮТСЯ ПО ДАТАМ РОЖДЕНИЯ \cr
%% 21
\+ BROWN, JOHN, 1715--1766 
  &рАБОТЫ "О НЕМ" ИДУТ ПОСЛЕ ЕГО РАБОТ \cr
\+ Brown, John, d. 1811
  &иНОГДА ГОД РОЖДЕНИЯ ОПРЕДЕЛЯЕТСЯ ПРИБЛИЗИТЕЛЬНО \cr
\+ Brown, Dr. John, 1810--1882 
  &уКАЗАНИЕ ПОЛОЖЕНИЯ (Dr.) ИГНОРИРУЕТСЯ \cr
\+ Brown-Williams, Reginald Makepeace
  &дЕФИС РАССМАТРИВАЕТСЯ КАК ПРОБЕЛ \cr
\+ Brown America. 
  &нАЗВАНИЯ КНИГ ИДУТ ПОСЛЕ СОСТАВНЫХ ФАМИЛИЙ \cr
\+ Brown \& Dallison's Nevada directory.  
  &\& В АНГЛИЙСКОМ ТЕКСТЕ ПРЕВРАЩАЕТСЯ В "and" \cr
\+ Brownjohn, Alan
  &\cr
\+ Den', Vladimir \'Eduardovich, 1867--
  &аПОСТРОФ В ИМЕНАХ ИГНОРИРУЕТСЯ\cr
\+ The den.  
  &аРТИКЛЬ В НАЧАЛЕ ТЕКСТА ИГНОРИРУЕТСЯ\cr
\+ Den lieben s\"ussen m\"adeln. 
  &\dots{} ЕСЛИ СУЩЕСТВИТЕЛЬНОЕ СТОИТ В ИМЕНИТЕЛЬНОМ ПАДЕЖЕ\cr
\+ Dix, Morgan, 1827--1908  
  &фАМИЛИИ ИДУТ РАНЬШЕ ДРУГИХ СЛОВ \cr
\+ 1812 ouverture.
  &Dix-huit cent douze \cr
\+ Le XIXe si\`ecle fran\c{c}ais.
  &Dix-neuvi\`eme \cr
\+ The 1847 issue of U. S. stamps.
  &Eighteen forty-seven \cr
\+ 1812 overture.
  &Eighteen twelve \cr
\+ I am a mathematician,
  &(by Norbert Weiner)\cr
\+ IBM journal of research and development.
  &аББРЕВИАТУРЫ РАССМАТРИВАЮТСЯ КАК РЯД ОДНОБУКВЕННЫХ СЛОВ \cr
\+ ha-I ha-e\d had.
  &аРТИКЛЬ В НАЧАЛЕ ТЕКСТА ИГНОРИРУЕТСЯ \cr
\+ Ia; a love story.
  &зНАКИ ПРЕПИНАНИЯ В НАЗВАНИЯХ ИГНОРИРУЮТСЯ \cr
\+ International Business Machines Corporation
  &\cr
\+ al-Khuw\={a}rizm\={\i}, Mu\d{h}ammad ibn M\={u}s\={a}, {\it fl.\/} 813--846 
  &нАЧАЛЬНОЕ "Аl-" В АРАБСКИХ ИМЕНАХ ИГНОРИРУЕТСЯ \cr
\+ Labour; a magazine for all workers. 
  &зАМЕНЯЕТСЯ НА "Labor" \cr
\+ Labor research association 
  &\cr
\+ Labour, {\it see\/} Labor
  &сСЫЛКА НА ДРУГУЮ КАРТОЧКУ В КАРТОТЕКЕ \cr
\+ McCall's cookbook 
  &аПОСТРОФ В АНГЛИЙСКОМ ТЕКСТЕ ИГНОРИРУЕТСЯ \cr
\+ McCarthy, John, 1927--
  &Mc = Mac \cr
\+ Machine-independent computer programming. 
  &дЕФИС РАССМАТРИВАЕТСЯ КАК ПРОБЕЛ \cr
\+ MacMahon, Maj. Percy  Alexander, 1854--1929 
  &уКАЗАНИЕ ПОЛОЖЕНИЯ (Maj) ИГНОРИРУЕТСЯ \cr
\+ Mrs. Dalloway. 
  &"Mrs. "= "Mistress" \cr
\+ Mistress of mistresses.
  &\cr
\+ Royal society of London
  &\cr
\+ St. PetersburgerZeitung.
  &"St."= "Saint"   ДАЖЕ  В НЕМЕЦКОМ ТЕКСТЕ \cr
\+ Saint-Sa\"ens, Camille, 1835--1921 
  &дЕФИС РАССМАТРИВАЕТСЯ КАК ПРОБЕЛ \cr
\+ Ste. Anne des Monts, Quebec
  &Sainte \cr
\+ Seminumerical algorithms.
  &\cr
\+ Uncle Tom's cabin.
  &\cr
\+ U.S. Bureau of the census.  
  &"U.S." = "United States" \cr
\+ Vandermonde, Alexander Th\'eophile, 1735--1796
  &\cr
\+ Van Valkenburg, Mac Elwyn, 1921--
  & пРОБЕЛ ПОСЛЕ ПРЕФИКСА В ФАМИЛИЯХ ИГНОРИРУЕТСЯ \cr
\+ Von Neumann, John, 1903--1957
  &\cr
\+ The whole art of legerdemain.
  &\cr
%% 22
\+ Who's afraid of Virginia Woolf?
 & аПОСТРОФ В АНГЛИЙСКОМ ТЕКСТЕ ИГНОРИРУЕТСЯ\cr
\+ Wijngaarden, Adriaan van, 1916--
 & фАМИЛИЯ  НИКОГДА НЕ  НАЧИНАЕТСЯ С МАЛОЙ БУКВЫ \cr
\medskip
\noindent(у БОЛЬШИНСТВА ИЗ ЭТИХ ПРАВИЛ ЕСТЬ ИСКЛЮЧЕНИЯ; КРОМЕ ТОГО, СУЩЕСТВУЕТ 
МНОГО ДРУГИХ ПРАВИЛ, КОТОРЫЕ ЗДЕСЬ НЕ УПОМЯНУТЫ.)
\par
}

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

\ex[м21]\exhead(дИСКРЕТНЫЕ ЛОГАРИФМЫ.) пУСТЬ ИЗВЕСТНО, ЧТО 
$p$---(ДОВОЛЬНО БОЛЬШОЕ) ПРОСТОЕ ЧИСЛО, А $a$---ПЕРВООБРАЗНЫЙ КОРЕНЬ ПО МОДУЛЮ 
$p$. сЛЕДОВАТЕЛЬНО, ДЛЯ ЛЮБОГО $b$ В ДИАПАЗОНЕ $1\le{} b < p$ СУЩЕСТВУЕТ 
ЕДИНСТВЕННОЕ $n$, ТАКОЕ, ЧТО $a^n \bmod p=b$, $1\le{} n < Р$. кАК ПО 
ЗАДАННОМУ $b$ НАЙТИ $n$ МЕНЕЕ ЧЕМ ЗА $о(n)$ ШАГОВ? [уКАЗАНИЕ. пУСТЬ 
$m=\lceil\sqrt p\rceil$. пОПЫТАЙТЕСЬ РЕШИТЬ УРАВНЕНИЕ 
$a^{mn_1}\equiv b a^{-n_2} \pmod{p}$  ПРИ $0 \le{} n_1$, $n_2 < m$.]

\ex[м25] (э. т. пАРКЕР.) эЙЛЕР ВЫДВИНУЛ ПРЕДПОЛОЖЕНИЕ, ЧТО УРАВНЕНИЕ
$$
u^6+v^6+ w^6 + Х^6 + y^6 = z^6
$$
НЕ ИМЕЕТ РЕШЕНИЙ (ЗА ИСКЛЮЧЕНИЕМ ТРИВИАЛЬНЫХ) СРЕДИ ЦЕЛЫХ 
НЕОТРИЦАТЕЛЬНЫХ ЧИСЕЛ $u$, $v$, $w$, $x$, $y$, $z$, КОГДА ПО КРАЙНЕЙ МЕРЕ 
ЧЕТЫРЕ ПЕРЕМЕННЫЕ РАВНЫ НУЛЮ. пОМИМО ЭТОГО, ОН ПРЕДПОЛАГАЛ, ЧТО 
УРАВНЕНИЕ
$$
x_1^n+\cdots+x_{n-1}^n=x_n^n
$$
НЕ ИМЕЕТ НЕТРИВИАЛЬНЫХ РЕШЕНИЙ ПРИ $n\ge 3$, НО ЭТО ПРЕДПОЛОЖЕНИЕ БЫЛО 
ОПРОВЕРГНУТО: С ПОМОЩЬЮ ВЫЧИСЛИТЕЛЬНОЙ МАШИНЫ НАЙДЕНО ТОЖДЕСТВО 
$27^5+84^5+110^5+133^5=144^5$; СМ. л. дЖ. лЭНДЕР, т. р. пАРКИН И дЖ. л. 
сЕЛФРИДЖ, {\sl Math. Comp.\/}, {\bf 21} (1967), 446--459. пРИДУМАЙТЕ, КАК 
МОЖНО БЫЛО БЫ ИСПОЛЬЗОВАТЬ СОРТИРОВКУ ДЛЯ ПОИСКА ПРИМЕРОВ, 
ОПРОВЕРГАЮЩИХ ПРЕДПОЛОЖЕНИЕ эЙЛЕРА ПРИ $n=6$.

\rex[24] фАЙЛ СОДЕРЖИТ БОЛЬШОЕ КОЛИЧЕСТВО 30-РАЗРЯДНЫХ ДВОИЧНЫХ СЛОВ:
$x_1$, \dots $x_N$. пРИДУМАЙТЕ ХОРОШИЙ СПОСОБ НАХОЖДЕНИЯ В НЕМ ВСЕХ 
\emph{ДОПОЛНИТЕЛЬНЫХ} ПАР $(x_i, Х_j)$. (дВА СЛОВА НАЗЫВАЮТСЯ 
ДОПОЛНИТЕЛЬНЫМИ, ЕСЛИ ВТОРОЕ СОДЕРЖИТ 0 ВО ВСЕХ РАЗРЯДАХ, В КОТОРЫХ БЫЛИ 1 
В ПЕРВОМ СЛОВЕ, И ОБРАТНО; ТАКИМ ОБРАЗОМ, ОНИ ДОПОЛНИТЕЛЬНЫ ТОГДА И ТОЛЬКО 
ТОГДА, КОГДА ИХ СУММА РАВНА $(11\ldots1)_2$, ЕСЛИ ОНИ РАССМАТРИВАЮТСЯ КАК 
ДВОИЧНЫЕ ЧИСЛА.) 

\rex[25] иМЕЕТСЯ ФАЙЛ. СОДЕРЖАЩИЙ 1000 30-РАЗРЯДНЫХ ДВОИЧНЫХ СЛОВ 
$x_1$, \dots, $x_{1000}$. кАК БЫ ВЫ СТАЛИ СОСТАВЛЯТЬ СПИСОК ВСЕХ ПАР 
$(x_i, x_j)$, ТАКИХ, ЧТО $x_i$ ОТЛИЧАЕТСЯ ОТ $x_j$  НЕ БОЛЕЕ ЧЕМ В ДВУХ 
РАЗРЯДАХ?

\ex[22] кАК БЫ ВЫ ПОСТУПИЛИ ПРИ ОТЫСКАНИИ ВСЕХ ПЯТИБУКВЕННЫХ АНАГРАММ, 
ТАКИХ, КАК \strong{CARET, CARTE, CATER, CRATE, REACT, 
TRACE; CRUEL, LUCRE, ULCER; DOWRY, ROWDY, WORDY?} [еСЛИ 
БЫ ВЫ, СКАЖЕМ, ЗАХОТЕЛИ УЗНАТЬ, СУЩЕСТВУЮТ ЛИ В АНГЛИЙСКОМ ЯАЫКЕ НАБОРЫ 
ИЗ ДЕСЯТИ ИЛИ БОЛЕЕ АНАГРАММ, КРОМЕ ЗАМЕЧАТЕЛЬНОЙ СЕРИИ:
$$
\vtop{\strong{
APERS, ASPER,PARES,PARSE,PEARS, PRASE, RAPES, REAPS, 
SPARE, SPEAR,
}}
$$
К КОТОРОЙ МОЖНО ДОБАВИТЬ ЕЩЕ ФРАНЦУЗСКОЕ СЛОВО \strong{APRES.}]

\ex[м28] пУСТЬ ДАНЫ ОПИСАНИЯ ВЕСЬМА БОЛЬШОГО ЧИСЛА НАПРАВЛЕННЫХ 
ГРАФОВ. кАКИМ ПУТЕМ МОЖНО СГРУППИРОВАТЬ \emph{ИЗОМОРФНЫЕ} ГРАФЫ? (дВА 
НАПРАВЛЕННЫХ ГРАФА НАЗЫВАЮТСЯ ИЗОМОРФНЫМИ, ЕСЛИ СУЩЕСТВУЕТ ВЗАИМНО 
ОДНОЗНАЧНОЕ СООТВЕТСТВИЕ МЕЖДУ ИХ ВЕРШИНАМИ И ВЗАИМНО ОДНОЗНАЧНОЕ 
СООТВЕТСТВИЕ
%% 23
МЕЖДУ ИХ ДУГАМИ, ПРИЧЕМ ЭТИ СООТВЕТСТВИЯ СОХРАНЯЮТ ИНЦИДЕНТНОСТЬ ВЕРШИН 
И ДУГ.)

\ex[30] в НЕКОТОРОЙ ГРУППЕ ИЗ 4096 ЧЕЛОВЕК КАЖДЫЙ ИМЕЕТ ОКОЛО 100 
ЗНАКОМЫХ. бЫЛ СОСТАВЛЕН СПИСОК ВСЕХ ПАР ЛЮДЕЙ, ЗНАКОМЫХ МЕЖДУ СОБОЙ. (эТО 
ОТНОШЕНИЕ СИММЕТРИЧНО, Т. Е. ЕСЛИ $Х$ ЗНАКОМ С $У$, ТО И $У$ ЗНАКОМ С $Х$. 
пОЭТОМУ СПИСОК СОДЕРЖИТ ПРИМЕРНО 200000 ПАР.) пРИДУМАЙТЕ АЛГОРИТМ, 
КОТОРЫЙ ПО ЗaДaННoМy $k$ ВЫДАВАЛ БЫ ВСЕ \emph{КЛИКИ} ИЗ $k$ ЧЕЛОВЕК. 
(кЛИКА --- ЭТО ГРУППА ЛЮДЕЙ, В КОТОРОЙ ВСЕ МЕЖДУ СОБОЙ ЗНАКОМЫ.) 
пРЕДПОЛАГАЕТСЯ, ЧТО СЛИШКОМ БОЛЬШИХ КЛИК НЕ БЫВАЕТ.

\ex[30] тРИ МИЛЛИОНА ЧЕЛОВЕК С РАЗЛИЧНЫМИ ИМЕНАМИ БЫЛИ УЛОЖЕНЫ 
РЯДОМ НЕПРЕРЫВНОЙ ЦЕПОЧКОЙ ОТ нЬЮ-йОРКА ДО кАЛИФОРНИИ. кАЖДОМУ ИЗ НИХ 
ДАЛИ ЛИСТОК БУМАГИ, НА КОТОРОМ ОН НАПИСАЛ СВОЕ ИМЯ И ИМЯ СВОЕГО 
БЛИЖАЙШЕГО ЗАПАДНОГО СОСЕДА. чЕЛОВЕК, НАХОДИВШИЙСЯ В САМОЙ ЗАПАДНОЙ 
ТОЧКЕ ЦЕПИ, НЕ ПОНЯЛ, ЧТО ЕМУ ДЕЛАТЬ, И ВЫКИНУЛ СВОЙ ЛИСТОК. оСТАЛЬНЫЕ 
2999999 ЛИСТКОВ СОБРАЛИ В БОЛЬШУЮ КОРЗИНУ И ОТПРАВИЛИ В нАЦИОНАЛЬНЫЙ 
АРХИВ, В вАШИНГТОН, ОКРУГ кОЛУМБИЯ. тАМ СОДЕРЖИМОЕ КОРЗИНЫ ТЩАТЕЛЬНО 
ПЕРЕТАСОВАЛИ И ЗАПИСАЛИ НА МАГНИТНЫЕ ЛЕНТЫ.

сПЕЦИАЛИСТ ПО ТЕОРИИ ИНФОРМАЦИИ ОПРЕДЕЛИЛ, ЧТО ИМЕЕТСЯ ДОСТАТОЧНО 
ИНФОРМАЦИИ ДЛЯ ВОССТАНОВЛЕНИЯ СПИСКА ЛЮДЕЙ В ИСХОДНОМ ПОРЯДКЕ. 
сПЕЦИАЛИСТ ПО ПРОГРАММИРОВАНИЮ НАШЕЛ СПОСОБ СДЕЛАТЬ ЭТО МЕНЕЕ ЧЕМ ЗА 
1000 ПРОСМОТРОВ ЛЕНТ С ДАННЫМИ, ИСПОЛЬЗУЯ ЛИШЬ ПОСЛЕДОВАТЕЛЬНЫЙ ДОСТУП К 
ФАЙЛАМ НА ЛЕНТАХ И НЕБОЛЬШОЕ КОЛИЧЕСТВО ПАМЯТИ С ПРОИЗВОЛЬНЫМ ДОСТУПОМ. 
кАК ЕМУ ЭТО УДАЛОСЬ?

[дРУГИМИ СЛОВАМИ, КАК, ИМЕЯ РАСПОЛОЖЕННЫЕ ПРОИЗВОЛЬНЫМ ОБРАЗОМ ПАРЫ 
$(x_i, x_{i+1})$, $1 \le i < N$, ГДЕ ВСЕ $x_i$ РАЗЛИЧНЫ, ПОЛУЧИТЬ 
ПОСЛЕДОВАТЕЛЬНОСТЬ $x_1$, $x_2$, \dots, $x_N$, ПРИМЕНЯЯ ЛИШЬ МЕТОДЫ 
ПОСЛЕДОВАТЕЛЬНОЙ ОБРАБОТКИ ДАННЫХ, ПРИГОДНЫЕ ДЛЯ РАБОТЫ С МАГНИТНЫМИ 
ЛЕНТАМИ? эТО ЗАДАЧА СОРТИРОВКИ В СЛУЧАЕ, КОГДА ТРУДНО ОПРЕДЕЛИТЬ, КАКОЙ ИЗ 
ДВУХ КЛЮЧЕЙ ПРЕДШЕСТВУЕТ ДРУГОМУ; МЫ УЖЕ ПОДНИМАЛИ ЭТОТ ВОПРОС В УПР. 
2.2.3--25.]
%% 24

\subchap{* комбинаторные свойства перестановок}
пЕРЕСТАНОВКОЙ КОНЕЧНОГО МНОЖЕСТВА НАЗЫВАЕТСЯ НЕКОТОРОЕ РАСПОЛОЖЕНИЕ 
ЕГО ЭЛЕМЕНТОВ В РЯД. пЕРЕСТАНОВКИ ОСОБЕННО ВАЖНЫ ПРИ ИЗУЧЕНИИ АЛГОРИТМОВ 
СОРТИРОВКИ, ТАК КАК ОНИ СЛУЖАТ ДЛЯ ПРЕДСТАВЛЕНИЯ НЕУПОРЯДОЧЕННЫХ 
ИСХОДНЫХ ДАННЫХ. чТОБЫ ИССЛЕДОВАТЬ ЭФФЕКТИВНОСТЬ РАЗЛИЧНЫХ МЕТОДОВ 
СОРТИРОВКИ, НУЖНО УМЕТЬ ПОДСЧИТЫВАТЬ ЧИСЛО ПЕРЕСТАНОВОК, КОТОРЫЕ 
ВЫНУЖДАЮТ ПОВТОРЯТЬ НЕКОТОРЫЙ ШАГ АЛГОРИТМА ОПРЕДЕЛЕННОЕ ЧИСЛО РАЗ. 

мЫ, КОНЕЧНО, УЖЕ НЕ РАЗ ВСТРЕЧАЛИСЬ С ПЕРЕСТАНОВКАМИ В ГЛ. 1, 2 И~3. 
нАПРИМЕР, В П. 1.2.5 ОБСУЖДАЛИСЬ ДВА ОСНОВНЫХ ТЕОРЕТИЧЕСКИХ МЕТОДА 
ПОСТРОЕНИЯ $n!$ ПЕРЕСТАНОВОК ИЗ $n$ ОБЎЕКТОВ;
В П. 1.3.3 ПРОАНАЛИЗИРОВАНЫ НЕКОТОРЫЕ АЛГОРИТМЫ, СВЯЗАННЫЕ С ЦИКЛИЧЕСКОЙ 
СТРУКТУРОЙ И МУЛЬТИПЛИКАТИВНЫМИ СВОЙСТВАМИ ПЕРЕСТАНОВОК; В П. 3.3.2 
ИЗУЧЕНЫ ИХ ОТРЕЗКИ МОНОТОННОСТИ. цЕЛЬ НАСТОЯЩЕГО ПАРАГРАФА---ИЗУЧИТЬ 
НЕКОТОРЫЕ ДРУГИЕ СВОЙСТВА ПЕРЕСТАНОВОК И РАССМОТРЕТЬ ОБЩИЙ СЛУЧАЙ, КОГДА 
ДОПУСКАЕТСЯ НАЛИЧИЕ ОДИНАКОВЫХ ЭЛЕМЕНТОВ. пОПУТНО МЫ УЗНАЕМ МНОГОЕ О 
КОМБИНАТОРНОЙ МАТЕМАТИКЕ.

сВОЙСТВА ПЕРЕСТАНОВОК НАСТОЛЬКО КРАСИВЫ, ЧТО ПРЕДСТАВЛЯЮТ И 
САМОСТОЯТЕЛЬНЫЙ ИНТЕРЕС. уДОБНО БУДЕТ ДАТЬ ИХ СИСТЕМАТИЧЕСКОЕ ИЗЛОЖЕНИЕ В 
ОДНОМ МЕСТЕ, А НЕ РАЗБРАСЫВАТЬ МАТЕРИАЛ ПО ВСЕЙ ГЛАВЕ. чИТАТЕЛЯМ, НЕ 
ИМЕЮЩИМ СКЛОННОСТИ К МАТЕМАТИКЕ, А ТАКЖЕ ТЕМ, КТО ЖАЖДЕТ ПОСКОРЕЕ 
ДОБРАТЬСЯ ДО САМИХ МЕТОДОВ СОРТИРОВКИ, РЕКОМЕНДУЕТСЯ ПЕРЕЙТИ СРАЗУ К 
\S~5.2, ПОТОМУ ЧТО НАСТОЯЩИЙ ПАРАГРАФ \emph{НЕПОСРЕДСТВЕННОГО} 
ОТНОШЕНИЯ К СОРТИРОВКЕ ПОЧТИ НЕ ИМЕЕТ.

\subsubchap{*иНВЕРСИИ}
пУСТЬ $a_1$ $a_2$ \dots\ $a_n$ ---ПЕРЕСТАНОВКА МНОЖЕСТВА 
$\{1, 2, \dots, n\}$. еСЛИ $i < j$, a $a_i>a_j$, ТО ПАРА $(А_i, a_j)$ 
НАЗЫВАЕТСЯ 
ИНВЕРСИЕЙ ПЕРЕСТАНОВКИ; НАПРИМЕР, ПЕРЕСТАНОВКА 3 1 4 2 ИМЕЕТ ТРИ ИНВЕРСИИ: 
$(3, 1)$, $(3, 2)$ И $(4, 2)$. кАЖДАЯ ИНВЕРСИЯ---ЭТО ПАРА ЭЛЕМЕНТОВ, 
"НАРУШАЮЩИХ ПОРЯДОК"; СЛЕДОВАТЕЛЬНО, ЕДИНСТВЕННАЯ ПЕРЕСТАНОВКА, НЕ 
СОДЕРЖАЩАЯ ИНВЕРСИЙ,---ЭТО ОТСОРТИРОВАННАЯ ПЕРЕСТАНОВКА 1 2 \dots $n$. 
тАКАЯ СВЯЗЬ С СОРТИРОВКОЙ И ЕСТЬ ГЛАВНАЯ ПРИЧИНА НАШЕГО ИНТЕРЕСА К 
ИНВЕРСИЯМ, ХОТЯ ЭТО ПОНЯТИЕ УЖЕ ИСПОЛЬЗОВАЛОСЬ НАМИ ПРИ АНАЛИЗЕ АЛГОРИТМА 
ДИНАМИЧЕСКОГО РАСПРЕДЕЛЕНИЯ ПАМЯТИ (СМ. УПР. 2.2.2--9).
%% 25

пОНЯТИЕ ИНВЕРСИИ ВВЕЛ г. кРАМЕР В 1750 Г. [Intr. \`a 1'Analyse des Lignes 
Courbes alg\'ebriques (Geneva, 1750), 657--659; СР. С тОМАС мЮИР, тhЕОГУ of 
Determinants, 1 (1906), 11--14] В СВЯЗИ СО СВОИМ ЗАМЕЧАТЕЛЬНЫМ ПРАВИЛОМ 
РЕШЕНИЯ ЛИНЕЙНЫХ УРАВНЕНИЙ. в СУЩНОСТИ, ОН ОПРЕДЕЛИЛ ДЕТЕРМИНАНТ 
$n\times n$-МАТРИЦЫ СЛЕДУЮЩИМ ОБРАЗОМ:
$$
\det\pmatrix{
 x_{11} & x_{12} &\ldots & x_{1n} \cr
\vdots    & \vdots & & \vdots \cr
 x_{n1} & x_{n2} & \ldots & x_{nn} \cr
}=\sum (-1)^{I(a_1 a_2 \ldots a_n)}x_{1a_1}x_{2a_2}\ldots x_{na_n},
$$
ГДЕ СУММА БЕРЕТСЯ ПО ВСЕМ  ПЕРЕСТАНОВКАМ $a_1$ $a_2$ \dots\ $a_n$, А 
$I(a_1 a_2 \ldots a_n)$---ЧИСЛО ИНВЕРСИЙ В ПЕРЕСТАНОВКЕ.

\dfn{тАБЛИЦЕЙ ИНВЕРСИЙ} ПЕРЕСТАНОВКИ $a_1$ $a_2$ \dots\ $a_n$ 
НАЗЫВАЕТСЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ЧИСЕЛ $b_1$ $b_2$ \dots\ $b_n$, 
ГДЕ $b_j$---ЧИСЛО ЭЛЕМЕНТОВ, 
\emph{Б\'ОЛЬШИХ} $j$ И РАСПОЛОЖЕННЫХ \emph{ЛЕВЕЕ} $j$. 
(дРУГИМИ СЛОВАМИ, $b_j$---ЧИСЛО ИНВЕРСИЙ, У КОТОРЫХ ВТОРОЙ ЭЛЕМЕНТ 
РАВЕН~$j$.) нАПРИМЕР, ТАБЛИЦЕЙ ИНВЕРСИЙ ПЕРЕСТАНОВКИ
$$
5\;9\;1\;8\;2\;6\;4\;7\;3 \eqno                     (1)
$$
БУДЕТ
$$
2\;3\;6\;4\;0\;2\;2\;1\;0,\eqno  (2)
$$
ПОСКОЛЬКУ 5 И 9 РАСПОЛОЖЕНЫ ЛЕВЕЕ 1; 5, 9, 8---ЛЕВЕЕ 2 И Т.Д., ВСЕГО 20 
ИНВЕРСИЙ. пО ОПРЕДЕЛЕНИЮ
$$
0\le{} b_1\le{} n-1,  0\le{} b_2 \le{} n-2,\ldots ,0\le{} b_{n-1}\le{} 1, 
b_n=0.\eqno (3)
$$

пОЖАЛУЙ, НАИБОЛЕЕ ВАЖНЫЙ ФАКТ, КАСАЮЩИЙСЯ ПЕРЕСТАНОВОК, И 
УСТАНОВЛЕННЫЙ мАРШАЛЛОМ хОЛЛОМ, ЭТО ТО, ЧТО \emph{ТАБЛИЦА ИНВЕРСИЙ 
ЕДИНСТВЕННЫМ ОБРАЗОМ ОПРЕДЕЛЯЕТ СООТВЕТСТВУЮЩУЮ ПЕРЕСТАНОВКУ.} [сМ. 
Proc. Symp. Applied Math., {\bf 6} (American Math. Society, 1956), 203.] иЗ 
ЛЮБОЙ ТАБЛИЦЫ ИНВЕРСИЙ $b_1$ $b_2$ \dots\ $b_n$, УДОВЛЕТВОРЯЮЩЕЙ УСЛОВИЯМ 
(3), МОЖНО ОДНОЗНАЧНО ВОССТАНОВИТЬ ПЕРЕСТАНОВКУ, КОТОРАЯ ПОРОЖДАЕТ 
ДАННУЮ ТАБЛИЦУ, ПУТЕМ ПОСЛЕДОВАТЕЛЬНОГО ОПРЕДЕЛЕНИЯ ОТНОСИТЕЛЬНОГО 
РАСПОЛОЖЕНИЯ ЭЛЕМЕНТОВ $n$, $n-1$, \dots, $1$ (В ЭТОМ ПОРЯДКЕ). нАПРИМЕР, 
ПЕРЕСТАНОВКУ, СООТВЕТСТВУЮЩУЮ (2), МОЖНО ПОСТРОИТЬ СЛЕДУЮЩИМ ОБРАЗОМ:
ВЫПИШЕМ ЧИСЛО 9; ТАК КАК $b_8=1$, ТО 8 СТОИТ ПРАВЕЕ 9. пОСКОЛЬКУ 
$b_7=2$, ТО 7 СТОИТ ПРАВЕЕ 8 И~9. тАК КАК $b_6=2$, ТО 6 СТОИТ ПРАВЕЕ ДВУХ 
УЖЕ ВЫПИСАННЫХ НАМИ ЧИСЕЛ; ТАКИМ ОБРАЗОМ, ИМЕЕМ
$$
9\; 8\; 6\; 7.
$$
%% 26
пРИПИШЕМ ТЕПЕРЬ 5 СЛЕВА, ПОТОМУ ЧТО $b_5=0$; ПОМЕЩАЕМ 4 ВСЛЕД ЗА 
ЧЕТЫРЬМЯ ИЗ УЖЕ ЗАПИСАННЫХ ЧИСЕЛ, 3---ПОСЛЕ ШЕСТИ ВЫПИСАННЫХ ЧИСЕЛ (Т. Е. 
В ПРАВЫЙ КОНЕЦ) И ПОЛУЧАЕМ
$$
5\;9\;8\;6\;4\;7\;3.
$$
вСТАВИВ АНАЛОГИЧНЫМ ОБРАЗОМ 2 И 1, ПРИДЕМ К (1).

тАКОЕ СООТВЕТСТВИЕ ВАЖНО, ПОТОМУ ЧТО ЧАСТО МОЖНО ЗАМЕНИТЬ ЗАДАЧУ, 
СФОРМУЛИРОВАННУЮ В ТЕРМИНАХ ПЕРЕСТАНОВОК, ЭКВИВАЛЕНТНОЙ ЕЙ ЗАДАЧЕЙ, 
СФОРМУЛИРОВАННОЙ В ТЕРМИНАХ ТАБЛИЦ ИНВЕРСИЙ, КОТОРАЯ, ВОЗМОЖНО, РЕШАЕТСЯ 
ПРОЩЕ. рАССМОТРИМ, НАПРИМЕР, САМЫЙ ПРОСТОЙ ВОПРОС: СКОЛЬКО СУЩЕСТВУЕТ 
ПЕРЕСТАНОВОК МНОЖЕСТВА $\{1, 2, \ldots, n\}$? оТВЕТ ДОЛЖЕН БЫТЬ РАВЕН ЧИСЛУ 
ВСЕВОЗМОЖНЫХ ТАБЛИЦ ИНВЕРСИЙ, А ИХ ЛЕГКО ПЕРЕСЧИТАТЬ, ТАК КАК $b_1$ МОЖНО 
ВЫБРАТЬ $n$ РАЗЛИЧНЫМИ СПОСОБАМИ, $b_2$ МОЖНО НЕЗАВИСИМО ОТ $b-1$ 
ВЫБРАТЬ $n-1$ СПОСОБАМИ, \dots, $b_n$---ОДНИМ СПОСОБОМ; ИТОГО 
$П(П-1)\ldots 1=n!$ РАЗЛИЧНЫХ ТАБЛИЦ ИНВЕРСИЙ. тАБЛИЦЫ ИНВЕРСИЙ ПЕРЕСЧИТАТЬ
ЛЕГЧЕ, 
ПОТОМУ ЧТО $b$ НЕЗАВИСИМЫ, В ТО ВРЕМЯ КАК $А$ ДОЛЖНЫ БЫТЬ ВСЕ РАЗЛИЧНЫ.

в П. 1:2.10 МЫ ИССЛЕДОВАЛИ ЗАДАЧУ О ЧИСЛЕ ЛОКАЛЬНЫХ МАКСИМУМОВ 
ПЕРЕСТАНОВКИ, ЕСЛИ ЧИТАТЬ ЕЕ СПРАВА НАЛЕВО; ИНЫМИ СЛОВАМИ, ТРЕБОВАЛОСЬ 
ПОДСЧИТАТЬ КОЛИЧЕСТВО ЭЛЕМЕНТОВ, КАЖДЫЙ ИЗ КОТОРЫХ БОЛЬШЕ ЛЮБОГО ИЗ 
СЛЕДУЮЩИХ ПОСЛЕ НЕГО. (нАПРИМЕР, ПРАВОСТОРОННИЕ МАКСИМУМЫ В (1)---ЭТО 9, 
8, 7 И 3.) оНО РАВНО КОЛИЧЕСТВУ ИНДЕКСОВ $j$, ТАКИХ, ЧТО $b_j=n-j$. тАК КАК 
$b_1$ ПРИНИМАЕТ ЗНАЧЕНИЕ $n-1$ С ВЕРОЯТНОСТЬЮ $1/n$, $b_2$ (НЕЗАВИСИМО) 
ПРИНИМАЕТ ЗНАЧЕНИЕ $n-2$ С ВЕРОЯТНОСТЬЮ $1/(n-1)$ И Т.Д., ТО ИЗ РАССМОТРЕНИЯ 
ИНВЕРСИЙ ЯСНО, ЧТО СРЕДНЕЕ ЧИСЛО ПРАВОСТОРОННИХ  МАКСИМУМОВ РАВНО
$$
{1\over n}+{1\over n-1}+\cdots+1=H_n.    
$$
аНАЛОГИЧНЫМ СПОСОБОМ ЛЕГКО ПОЛУЧИТЬ И СООТВЕТСТВУЮЩУЮ ПРОИЗВОДЯЩУЮ 
ФУНКЦИЮ.

дРУГИЕ ПРИМЕНЕНИЯ ТАБЛИЦ ИНВЕРСИЙ ВСТРЕТЯТСЯ ДАЛЕЕ В ЭТОЙ ГЛАВЕ В СВЯЗИ 
С КОНКРЕТНЫМИ АЛГОРИТМАМИ СОРТИРОВКИ.

яСНО, ЧТО ЕСЛИ ПОМЕНЯТЬ МЕСТАМИ \emph{СОСЕДНИЕ} ЭЛЕМЕНТЫ 
ПЕРЕСТАНОВКИ, ТО ОБЩЕЕ ЧИСЛО ИНВЕРСИЙ УВЕЛИЧИТСЯ ИЛИ УМЕНЬШИТСЯ НА 
ЕДИНИЦУ. нА РИС. 1 ПОКАЗАНЫ 24 ПЕРЕСТАНОВКИ МНОЖЕСТВА $\{1, 2, 3, 4\}$; 
ЛИНИЯМИ СОЕДИНЕНЫ ПЕРЕСТАНОВКИ, ОТЛИЧАЮЩИЕСЯ ДРУГ ОТ ДРУГА ПОЛОЖЕНИЕМ 
ДВУХ СОСЕДНИХ ЭЛЕМЕНТОВ; ДВИГАЯСЬ ВДОЛЬ ЛИНИИ ВНИЗ, МЫ .УВЕЛИЧИВАЕМ ЧИСЛО 
ИНВЕРСИЙ НА ЕДИНИЦУ. сЛЕДОВАТЕЛЬНО, ЧИСЛО ИНВЕРСИЙ В ПЕРЕСТАНОВКЕ $П$ 
РАВНО ДЛИНЕ НИСХОДЯЩЕГО ПУТИ ИЗ 1 2 3 4 В $n$ НА РИС.~1; ВСЕ ТАКИЕ ПУТИ 
ДОЛЖНЫ ИМЕТЬ ОДИНАКОВУЮ ДЛИНУ.

зАМЕТИМ, ЧТО ЭТУ ДИАГРАММУ МОЖНО РАССМАТРИВАТЬ КАК ТРЕХМЕРНОЕ ТВЕРДОЕ 
ТЕЛО---"УСЕЧЕННЫЙ ОКТАЭДР", ИМЕЮЩИЙ 8 ШЕСТИУГОЛЬНЫХ
%% 27
И 6 КВАДРАТНЫХ ГРАНЕЙ. эТО ОДИН ИЗ РАВНОМЕРНЫХ МНОГОГРАННИКОВ, КОТОРЫЕ 
ОБСУЖДАЛ аРХИМЕД (СМ. УПР.,10).

\picture{
рИС. 1. уСЕЧЕННЫЙ ОКТАЭДР, НА КОТОРОМ ПОКАЗАНО ИЗМЕНЕНИЕ ЧИСЛА 
ИНВЕРСИЙ, КОГДА МЕНЯЮТСЯ МЕСТАМИ ДВА СОСЕДНИХ ЭЛЕМЕНТА ПЕРЕСТАНОВКИ;
}

нЕ СЛЕДУЕТ ПУТАТЬ "ИНВЕРСИИ" ПЕРЕСТАНОВОК С ОБРАТНЫМИ ПЕРЕСТАНОВКАМИ. 
вСПОМНИМ, ЧТО ПЕРЕСТАНОВКУ МОЖНО ЗАПИСЫВАТЬ В ВИДЕ ДВУХ СТРОК
$$
\pmatrix{
1 & 2 & 3 & \ldots & n \cr
a_1 & a_2 & a_3 & \ldots & a_n \cr
};\eqno (4)
$$
\dfn{ОБРАТНОЙ} К ЭТОЙ ПЕРЕСТАНОВКЕ НАЗЫВАЕТСЯ ПЕРЕСТАНОВКА $a'_1$, $a'_2$, 
\dots\ $a'_n$, КОТОРАЯ ПОЛУЧАЕТСЯ, ЕСЛИ В (4) ПОМЕНЯТЬ МЕСТАМИ СТРОКИ, А ЗАТЕМ 
УПОРЯДОЧИТЬ СТОЛБЦЫ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ ПО ВЕРХНИМ ЭЛЕМЕНТАМ: 
$$\pmatrix{
a_1 & a_2 & a_3 & \ldots & a_n \cr
1 & 2 & 3 & \ldots & n \cr
}=\pmatrix{
1 & 2 & 3 & \ldots & n \cr
a'_1 & a'_2 & a'_3 & \ldots & a'_n \cr
};
\eqno(5)
$$
нАПРИМЕР, ОБРАТНОЙ К ПЕРЕСТАНОВКЕ 5 9 1 8 2 6 4 7 3 БУДЕТ ПЕРЕСТАНОВКА
%% 28
3 5 9 7 1 6 8 4 2, ТАК КАК
$$
\pmatrix{
5 & 9 &1 &8 &2 &6 &4 &7 &3\cr
1 & 2 & 3&4 &5 &6 &7 &8 &9\cr
}=\pmatrix{
1 &2 &3 &4 &5 &6 &7 &8 &9\cr
3 &5 &9 &7 &1 &6 &8 &4 &2\cr
}.
$$
   мОЖНО ДАТЬ ДРУГОЕ ОПРЕДЕЛЕНИЕ ОБРАТНОЙ ПЕРЕСТАНОВКИ: $a'_j=k$ ТОГДА И 
ТОЛЬКО ТОГДА, КОГДА $А_k=j$.

оБРАТНУЮ ПЕРЕСТАНОВКУ ВПЕРВЫЕ ВВИЛ X. а. рОТЕ [В к.F.~Hindenburg(ed.)., 
Sammlung combinatorisch-analytischer Abhandlungen, 2 (Leipzig, 1800), 
263--305]; ОН ЗАМЕТИЛ ИНТЕРЕСНУЮ СВЯЗЬ МЕЖДУ ОБРАТНЫМИ ПЕРЕСТАНОВКАМИ И 
ИНВЕРСИЯМИ: \emph{ОБРАТНАЯ ПЕРЕСТАНОВКА СОДЕРЖИТ РОВНО СТОЛЬКО ЖЕ 
ИНВЕРСИЙ, СКОЛЬКО ИСХОДНАЯ}. рОТЕ ДАЛ НЕ САМОЕ ПРОСТОЕ ДОКАЗАТЕЛЬСТВО ЭТОГО 
ФАКТА, НО ОНО ПОУЧИТЕЛЬНО И ПРИТОМ ДОВОЛЬНО КРАСИВО. пОСТРОИМ ТАБЛИЦУ 
РАЗМЕРА $n\times n$ И ПОСТАВИМ ТОЧКИ В $j$-Й КЛЕТКЕ $i$-Й СТРОКИ, ЕСЛИ 
$a_i=j$. пОСЛЕ ЭТОГО РАССТАВИМ КРЕСТИКИ ВО ВСЕХ КЛЕТКАХ, СНИЗУ ОТ КОТОРЫХ (В 
ТОМ ЖЕ СТОЛБЦЕ) И СПРАВА (В ТОЙ ЖЕ СТРОКЕ) ЕСТЬ ТОЧКИ. нАПРИМЕР, ДЛЯ 5 9 1 8 2 
6 4 7 3 ДИАГРАММА БУДЕТ ТАКОЙ:
$$
%%  picture
$$
кОЛИЧЕСТВО КРЕСТИКОВ РАВНО ЧИСЛУ ИНВЕРСИЙ, ТАК КАК НЕТРУДНО ВИДЕТЬ, ЧТО 
$b_j$ РАВНО ЧИСЛУ КРЕСТИКОВ В $j$-М СТОЛБЦЕ. еСЛИ МЫ ТЕПЕРЬ ТРАНСПОНИРУЕМ 
ДИАГРАММУ (ПОМЕНЯВ РОЛЯМИ СТРОКИ И СТОЛБЦЫ), ТО ПОЛУЧИМ ДИАГРАММУ ДЛЯ 
ОБРАТНОЙ ПО ОТНОШЕНИЮ К ИСХОДНОЙ ПЕРЕСТАНОВКИ; ЗНАЧИТ, ЧИСЛО КРЕСТИКОВ 
(ЧИСЛО ИНВЕРСИЙ) ОДИНАКОВО В ОБОИХ СЛУЧАЯХ. рОТЕ ИСПОЛЬЗОВАЛ ЭТОТ ФАКТ ДЛЯ 
ДОКАЗАТЕЛЬСТВА ТОГО, ЧТО ДЕТЕРМИНАНТ МАТРИЦЫ НЕ МЕНЯЕТСЯ ПРИ 
ТРАНСПОНИРОВАНИИ.

дЛЯ АНАЛИЗА НЕКОТОРЫХ АЛГОРИТМОВ СОРТИРОВКИ НЕОБХОДИМО ЗНАТЬ ЧИСЛО 
ПЕРЕСТАНОВОК $П$ ЭЛЕМЕНТОВ, СОДЕРЖАЩИХ РОВНО $k$ ИНВЕРСИЙ. оБОЗНАЧИМ ЭТО 
ЧИСЛО ЧЕРЕЗ $I_n(k)$; В ТАБЛ. 1 ПРИВЕДЕНЫ ПЕРВЫЕ НЕСКОЛЬКО ЗНАЧЕНИЙ ЭТОЙ 
ФУНКЦИИ.
%% 29


\htable{тАБЛИЦА 1}{пЕРЕСТАНОВКИ С $k$ ИНВЕРСИЯМИ}%
{$#$\bskip\hfill&&\hfill\bskip$#$\bskip\hfill\cr
n & I_n(0) & I_n(1) & I_n(2) & I_n(3) & I_n(4) & I_n(5) & I_n(6) & I_n(7) & I_n(8) & 
I_n(9) & I_n(10) & I_n(11)\cr
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr
2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr
3 & 1 & 2 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr
4 & 1 & 3 & 5 & 6 & 5 & 3 & 1 & 0 & 0 & 0 & 0 & 0\cr
5 & 1 & 4 & 9 & 15 & 20 & 22 & 20 & 15 & 9 & 4 & 1 & 0\cr
6 & 1 & 5 & 14 & 29 & 49 & 71 & 90 & 101 & 101 & 90 & 71 & 49 \cr
}

иЗ РАССМОТРЕНИЯ ТАБЛИЦЫ ИНВЕРСИЙ $b_1$ $b_2$ \dots.$b_n$ ЯСНО, ЧТО 
$I_k(0)=1$, $I_n(1)=n-1$  И ЧТО ВЫПОЛНЯЕТСЯ СВОЙСТВО СИММЕТРИИ:
$$
I_n\left(\left({n \atop 2}\right)-k\right)=I_n(k)\eqno (6)
$$
дАЛЕЕ, ТАК КАК ЗНАЧЕНИЯ $b$ МОЖНО ВЫБИРАТЬ НЕЗАВИСИМО ДРУГ ОТ ДРУГА, ТО 
НЕТРУДНО ВИДЕТЬ, ЧТО ПРОИЗВОДЯЩАЯ ФУНКЦИЯ
$$
G_n(z)=I_n(0)+I_n(1)z+I_n(2)z^2+\cdots
\eqno (7)
$$
УДОВЛЕТВОРЯЕТ СООТНОШЕНИЮ $G_n(z) = (1 +z+ \cdots +z^{n-1})G_{n-1}(z)$;
СЛЕДОВАТЕЛЬНО, ОНА ИМЕЕТ ДОВОЛЬНО, ПРОСТОЙ ВИД
$$
(1+z+\cdots+z^{n-1})\ldots(1+z)(1)=(1-z^n)\ldots(l-z^2)(l-z)/(l-z)^n.
\eqno(8)
$$
с ПОМОЩЬЮ ЭТОЙ ПРОИЗВОДЯЩЕЙ ФУНКЦИИ МОЖНО ЛЕГКО ПРОДОЛЖИТЬ ТАБЛ. 1 И 
УБЕДИТЬСЯ, ЧТО ЧИСЛА, РАСПОЛОЖЕННЫЕ ПОД СТУПЕНЧАТОЙ ЛИНИЕЙ В ТАБЛИЦЕ, 
УДОВЛЕТВОРЯЮТ СООТНОШЕНИЮ
$$
I_n(k)=I_n(k-1)+I_{n-1}(k) \rem{ПРИ $k<n$.}
\eqno(9)
$$
(дЛЯ ЧИСЕЛ \emph{НАД} СТУПЕНЧАТОЙ ЛИНИЕЙ ЭТО СООТНОШЕНИЕ \emph{НЕ} 
ВЫПОЛНЯЕТСЯ.) бОЛЕЕ СЛОЖНЫЕ РАССУЖДЕНИЯ (СМ. УПР. 14) ПОКАЗЫВАЮТ, ЧТО НА 
САМОМ ДЕЛЕ ИМЕЮТ МЕСТО ФОРМУЛЫ
$$
\eqalign{
I_n(2)&=\left({ n \atop 2}\right)-1, n \ge{} 2;\cr
I_n(3)&=\left({ n+1 \atop 3}\right) - \left({ n \atop 1}\right), n \ge{} 3;\cr
I_n(4)&=\left({n+2 \atop 4}\right)-\left({ n+1\atop 2}\right), n \ge{} 4;\cr
I_n(5)&=\left({n+3 \atop 5}\right)-\left({ n+2\atop3 }\right)+1, n \ge{} 5.\cr
}
$$
%% 30
оБЩАЯ ФОРМУЛА ДЛЯ $I_n(k)$ СОДЕРЖИТ ОКОЛО $1.6\sqrt k$ СЛАГАЕМЫХ:
$$
\eqalign{
I_n(k)=&\left({ n+k-2\atop k}\right)-\left({ n+k-3\atop k-2 }\right)+
\left({ n+k-6\atop k-5}\right)+\left({ n+k-8\atop k-7}\right)-\cdots\hfill\cr
&+(-1)^j\left(\left({ n+k-u_j-1\atop k-u_j}\right)+ \left({ n+k-u_j-j-1\atop k-u_j-j}\right) 
\right)+\cdots, \rem{$n\ge k$,}\quad\cr
}
\eqno (10)
$$
ГДЕ $u_j=(3j^2-j)/2$ --- ТАК НАЗЫВАЕМОЕ "ПЯТИУГОЛЬНОЕ ЧИСЛО".

рАЗДЕЛИВ $G_n(z)$ НА $n!$, ПОЛУЧИМ ПРОИЗВОДЯЩУЮ ФУНКЦИЮ $g_n(z)$ 
РАСПРЕДЕЛЕНИЯ ВЕРОЯТНОСТЕЙ ЧИСЛА ИНВЕРСИЙ В СЛУЧАЙНОЙ ПЕРЕСТАНОВКЕ $П$ 
ЭЛЕМЕНТОВ. оНА РАВНА ПРОИЗВЕДЕНИЮ
$$
g_n(z)=h_1(z)h_2(z)\ldots h_n(z),\eqno (11)
$$
ГДЕ $h_k (z) = (1 + z + z^2 +\cdots + z^{k-1})/k$ --- ПРОИЗВОДЯЩАЯ ФУНКЦИЯ 
РАВНОМЕРНОГО РАСПРЕДЕЛЕНИЯ СЛУЧАЙНОЙ ВЕЛИЧИНЫ, ПРИНИМАЮЩЕЙ ЦЕЛЫЕ 
НЕОТРИЦАТЕЛЬНЫЕ ЗНАЧЕНИЯ, МЕНЬШИЕ $k$. оТСЮДА
$$
\eqalignno{
\mean (g_n) &= \mean (h_1) + \mean (h_2) + \cdots + \mean (h_n) =\cr
&=0 +{1\over2}+\cdots+{n-1\over 2}={n(n-1)\over 4}; & (12)\cr 
\var (g_n)& = \var (h_1) + \var (h_2)+ \cdots + \var (h_n)=\cr
&=0 +{1\over 4}+\cdots+{n^2-1\over 12}={n(2n+5)(n-1)\over 72}&(13)\cr
}
$$
тАКИМ ОБРАЗОМ, СРЕДНЕЕ ЧИСЛО ИНВЕРСИЙ ДОВОЛЬНО ВЕЛИКО---ОКОЛО 
${1\over 4}n^2$; СТАНДАРТНОЕ ОТКЛОНЕНИЕ ТАКЖЕ ВЕСЬМА ВЕЛИКО---ОКОЛО 
${1\over6}n^{3/2}$.

в КАЧЕСТВЕ ИНТЕРЕСНОГО ЗАВЕРШЕНИЯ ИЗУЧЕНИЯ ИНВЕРСИЙ РАССМОТРИМ 
ОДНО ЗАМЕЧАТЕЛЬНОЕ ОТКРЫТИЕ, ПРИНАДЛЕЖАЩЕЕ 
п. а. мАК-мАГОНУ [{\sl Amer. J. Math.,\/} {\bf 35} (1913), 281--322]. 
оПРЕДЕЛИМ \dfn{ИНДЕКС} ПЕРЕСТАНОВКИ $a_1$ $a_2$ \dots $a_n$ КАК СУММУ 
ВСЕХ $j$, ТАКИХ, ЧТО $А_j>a_{j+1}$, $1 \le < n$. нАПРИМЕР, ИНДЕКС 
ПЕРЕСТАНОВКИ 5 9 1 8 2 6 4 7 3 РАВЕН $2+4+6+8=20$. иНДЕКС СЛУЧАЙНО СОВПАЛ 
С ЧИСЛОМ ИНВЕРСИЙ. еСЛИ СОСТАВИТЬ СПИСОК ВСЕХ 24 ПЕРЕСТАНОВОК МНОЖЕСТВА 
$\{1, 2, 3, 4\}$, А ИМЕННО
%% 31
{
\def|{\,\vrule}
\offinterlineskip
\ctable{
\strut\hfill$#$\bskip\hfill&&\hfill$#$\bskip\hfill\cr
\multispan{4}пЕРЕСТАНОВКА &   иНДЕКС & иНВЕРСИИ & \multispan{4}пЕРЕСТАНОВКА&    иНДЕКС &иНВЕРСИИ \cr
1 & 2 & 3 & 4 &    0  &    0   & 3| & 1 & 2 & 4 &  1  & 2 \cr
1 & 2 & 4|& 3 &    3  &    1   & 3| & 1 & 4|& 2 &  4  & 3 \cr
1 & 3|& 2 & 4 &    2  &    1   & 3| & 2|& 1 & 4 &  3  & 3 \cr
1 & 3 & 4|& 2 &    3  &    2   & 3| & 2 & 4|& 1 &  4  & 4 \cr
1 & 4|& 2 & 3 &    2  &    2   & 3  & 4|& 1 & 2 &  2  & 4 \cr
1 & 4|& 3|& 2 &    5  &    3   & 3  & 4|& 2|& 1 &  5  & 5 \cr
2|& 1 & з & 4 &    1  &    1   & 4| & 1 & 2 & 3 &  1  & 3 \cr
2|& 1 & 4|& 3 &    4  &    2   & 4| & 1 & 3|& 2 &  4  & 4 \cr
2 & 3|& 1 & 4 &    2  &    2   & 4| & 2|& 1 & 3 &  3  & 4 \cr
2 & 3 & 4|& 1 &    3  &    3   & 4| & 2 & 3|& 1 &  4  & 5 \cr
2 & 4|& 1 & 3 &    2  &    8   & 4| & 3|& 1 & 2 &  3  & 5 \cr
2 & 4|& 3|& 1 &    5  &    4   & 4| & 3|& 2|& 1 &  6  & 6 \cr
}
}
ТО ВИДНО, ЧТО \emph{ЧИСЛО ПЕРЕСТАНОВОК, ИМЕЮЩИХ ДАННЫЙ ИНДЕКС $k$, 
РАВНО ЧИСЛУ ПЕРЕСТАНОВОК, ИМЕЮЩИХ $k$ ИНВЕРСИЙ.}

нА ПЕРВЫЙ ВЗГЛЯД ЭТОТ ФАКТ МОЖЕТ ПОКАЗАТЬСЯ ПОЧТИ ОЧЕВИДНЫМ, ОДНАКО 
ПОСЛЕ НЕКОТОРЫХ РАЗМЫШЛЕНИЙ ОН НАЧИНАЕТ КАЗАТЬСЯ ЧУТЬ ЛИ НЕ 
МИСТИЧЕСКИМ, И НЕ ВИДНО НИКАКОГО ПРОСТОГО ПРЯМОГО ЕГО ДОКАЗАТЕЛЬСТВА. 
мАК-мАГОН НАШЕЛ СЛЕДУЮЩЕЕ ОСТРОУМНОЕ КОСВЕННОЕ ДОКАЗАТЕЛЬСТВО: ПУСТЬ 
$J(А_1 А_2 \ldots a_n)$---ИНДЕКС ПЕРЕСТАНОВКИ $a_1$ $a_2$ \dots $a_n$, И 
СООТВЕТСТВУЮЩАЯ ПРОИЗВОДЯЩАЯ ФУНКЦИЯ ЕСТЬ
$$
H_n(z)=\sum z^{J(a_1 a_2 \ldots a_n)}, \eqno (14)
$$
ГДЕ СУММА БЕРЕТСЯ ПО ВСЕМ ПЕРЕСТАНОВКАМ МНОЖЕСТВА $\{1, 2, \ldots., П\}$. 
мЫ ХОТЕЛИ БЫ ДОКАЗАТЬ, ЧТО $H_n(z)=G_n(z)$. дЛЯ ЭТОГО ОПРЕДЕЛИМ 
ВЗАИМНО ОДНОЗНАЧНОЕ СООТВЕТСТВИЕ МЕЖДУ $n$-КАМИ 
$(q_1, q_2, \ldots, q_n)$ НЕОТРИЦАТЕЛЬНЫХ ЦЕЛЫХ ЧИСЕЛ, С ОДНОЙ СТОРОНЫ, И 
УПОРЯДОЧЕННЫМИ ПАРАМИ $n$-ОК
$$
((a_1, a_2, \ldots, a_n), (p_1, p_2, \ldots, p_n)),
$$
С ДРУГОЙ СТОРОНЫ; ЗДЕСЬ $А_1$ $А_2$ \dots\ $a_n$---ПЕРЕСТАНОВКА 
МНОЖЕСТВА $\{1, 2, \ldots, П\}$ И $p_1\ge p_2\ge \ldots \ge p_n \ge 0$.. эТО 
СООТВЕТСТВИЕ БУДЕТ УДОВЛЕТВОРЯТЬ УСЛОВИЮ
$$
q_1+q_2+\cdots+q_n=J(a_1 a_2 \ldots a_n)+(p_1+p_2+\cdots+p_n).
\eqno (15)
$$
пРОИЗВОДЯЩАЯ ФУНКЦИЯ $\sum z^{q_1+q_2+\cdots+q_n}$, ГДЕ СУММА БЕРЕТСЯ 
ПО ВСЕМ $n$-КАМ НЕОТРИЦАТЕЛЬНЫХ ЦЕЛЫХ ЧИСЕЛ $(q_1,  q_2, \ldots, q_n)$, 
РАВНА $Q_n (z) =1/(1-z)^z$; А ПРОИЗВОДЯЩАЯ ФУНКЦИЯ $\sum 
z^{p_1+p_2+\cdots+p_n}$, ГДЕ СУММА БЕРЕТСЯ ПО ВСЕМ $n$-КАМ ЦЕЛЫХ ЧИСЕЛ 
$(Р_1, Р_2, \ldots p_n)$, ТАКИХ, ЧТО $p_1\ge p_2\ge \ldots \ge p_n \ge 0$, РАВНА, 
КАК ПОКАЗАНО В УПР.~15,
$$
P_n(z)=1/(1-z)(1-z^2)\ldots(1-z^n).
\eqno(16)
$$
%% 32
сУЩЕСТВОВАНИЕ ВЗАИМНО ОДНОЗНАЧНОГО СООТВЕТСТВИЯ, КОТОРОЕ УДОВЛЕТВОРЯЕТ 
УСЛОВИЮ (15) И КОТОРОЕ МЫ СОБИРАЕМСЯ УСТАНОВИТЬ, ДОКАЗЫВАЕТ РАВЕНСТВО 
$Q_n(z)=H_n(z) P_n(z)$, Т.Е.
$$
H_n(z)=Q_n(z)/P_n(z)=G_n(z).
$$

тРЕБУЕМОЕ СООТВЕТСТВИЕ ОПРЕДЕЛЯЕТСЯ С ПОМОЩЬЮ АЛГОРИТМА 
"СОРТИРОВКИ". нАЧАВ С ПУСТОГО СПИСКА, ПРИ $k=1$, $2$, \dots, $n$ (В ТАКОМ 
ПОРЯДКЕ) ВСТАВЛЯЕМ В ЭТОТ СПИСОК ЧИСЛА $q_k$ СЛЕДУЮЩИМ ОБРАЗОМ: ПУСТЬ 
ПОСЛЕ $k-1$ ШАГОВ В СПИСКЕ СОДЕРЖАТСЯ ЭЛЕМЕНТЫ
$p_1$, $p_2$, \dots, $p_{k-1}$, ГДЕ $p_1\ge p_2\ge \ldots \ge p_{k-1}$, И 
ОПРЕДЕЛЕНА ПЕРЕСТАНОВКА $a_1$ $a_2$ \dots $a_n$ МНОЖЕСТВА 
$\{n, n-1, \ldots, n-k+2\}$. 
пУСТЬ $j$---ЕДИНСТВЕННОЕ ЦЕЛОЕ ЧИСЛО, ТАКОЕ, ЧТО 
$p_j>q_k\ge p_{j+1}$; ЕСЛИ $q_k\ge p_1$, ТО ПОЛАГАЕМ $j=0$, 
А ЕСЛИ $p_{k-1}>q_k$, ТО 
ПОЛАГАЕМ $j=k-1$. вСТАВИМ ТЕПЕРЬ $q_k$  В СПИСОК МЕЖДУ $p_j$ И $p_{j+1}$, 
А ЦЕЛОЕ ЧИСЛО $(n-k+1)$---В ПЕРЕСТАНОВКУ МЕЖДУ $a_j$, И $a_{j+1}$. 
пРОДЕЛАВ ЭТО ДЛЯ ВСЕХ $k$, ПОЛУЧИМ ПЕРЕСТАНОВКУ $a_1$ $a_2$ \dots  $a_n$ 
МНОЖЕСТВА $\{1,2, \ldots, n\}$ И $n$-КУ ЧИСЕЛ 
$(p_1, p_2, \ldots, p_n)$, ТАКИХ, ЧТО $p_1\ge p_2 \ge \ldots \ge p_n\ge 0$ И 
$$
p_j > p_{j+1}, \rem{ЕСЛИ $a_j>a_{j+1}$.}
$$
нАКОНЕЦ, ДЛЯ $1 \le j < n$ ВЫЧТЕМ ЕДИНИЦУ ИЗ ВСЕХ ЧИСЕЛ $p_1$, \dots, $p_j$ 
ПРИ ВСЕХ $j$, ТАКИХ, ЧТО $a_j>a_{j+1}$. пОЛУЧЕННАЯ ПАРА 
$((А_1, А_2, \ldots, А_n), (p_1, p_2, \ldots, p_n))$ УДОВЛЕТВОРЯЕТ УСЛОВИЮ (15).

пУСТЬ, НАПРИМЕР, $n=6$ И $(q_1, \ldots, q_6)=(3, 1, 4, 0, 0, 1).$ 
пОСТРОЕНИЕ ПРОИСХОДИТ СЛЕДУЮЩИМ ОБРАЗОМ:
{
\offinterlineskip
\ctable{
\strut\hfil$#$\bskip\hfil&&\hfil$#$\bskip\hfil\cr
k & \multispan{6} $p_1\ldots p_k$\hfill & \multispan{5} $a_1\ldots a_k$\hfill \cr
1 & 3 &   &   &   &   &   & 6 \cr
2 & 3 & 1 &   &   &   &   & 6 & 5 \cr
3 & 4 & 3 & 1 &   &   &   & 4 & 6 & 5 \cr
4 & 4 & 3 & 1 & 0 &   &   & 4 & 6 & 5 & 3 \cr
5 & 4 & 3 & 1 & 0 & 0 &   & 4 & 6 & 5 & 2 & 3 \cr
6 & 4 & 3 & 1 & 1 & 0 & 0 & 4 & 6 & 1 & 5 & 2 & 3 \cr
}
}
пОСЛЕ ЗАКЛЮЧИТЕЛЬНОЙ КОРРЕКТИРОВКИ ПОЛУЧАЕМ 
$(p_1, \ldots, p_6)=(2, 1, 0, 0, 0,0)$.

нЕТРУДНО ПРОВЕРИТЬ, ЧТО ЭТОТ ПРОЦЕСС ОБРАТИМ; ТАКИМ ОБРАЗОМ, 
ТРЕБУЕМОЕ СООТВЕТСТВИЕ УСТАНОВЛЕНО И ТЕОРЕМА мАК-мАГОНА ДОКАЗАНА. 
аНАЛОГИЧНОЕ ВЗАИМНО ОДНОЗНАЧНОЕ СООТВЕТСТВИЕ ВСТРЕТИТСЯ НАМ В П.~5.1.4.
\excercises
\ex[10] кАКОВА ТАБЛИЦА ИНВЕРСИЙ ДЛЯ ПЕРЕСТАНОВКИ 2 7 1 8 4 5 9 3 Б? кАКОЙ ПЕРЕСТАНОВКЕ 
СООТВЕТСТВУЕТ ТАБЛИЦА ИНВЕРСИЙ  5  0  1  2  1  2 0  0?

\ex[M15] рЕШЕНИЕМ ЗАДАЧИ иОСИФА, СФОРМУЛИРОВАННОЙ В УПР. 1.3.2--22, ЯВЛЯЕТСЯ 
ПЕРЕСТАНОВКА МНОЖЕСТВА $\{1, 2, \ldots n\}$; РЕШЕНИЕ ДЛЯ ПРИВЕДЕННОГО ТАМ ПРИМЕРА 
$(n=8,m=4)$---ПЕРЕСТАНОВКА 5 4 6 1 3 8 7 2. сООТВЕТСТВУЮЩАЯ ЭТОЙ ПЕРЕСТАНОВКЕ ТАБЛИЦА 
ИНВЕРСИЙ---3 6 3 1 0 0 1 0. нАЙДИТЕ ПРОСТОЕ РЕКУРРЕНТНОЕ
%% 33
СООТНОШЕНИЕ ДЛЯ ЭЛЕМЕНТОВ $b_1$ $b_2$ \dots $b_n$ ТАБЛИЦЫ 
ИНВЕРСИЙ В ОБЩЕЙ ЗАДАЧЕ иОСИФА ДЛЯ $n$ ЧЕЛОВЕК, ЕСЛИ КАЗНЯТ КАЖДОГО $m$-ГО 
ЧЕЛОВЕКА.

\ex[18] пУСТЬ ПЕРЕСТАНОВКЕ $a_1$ $a_2$ \dots $a_n$ СООТВЕТСТВУЕТ ТАБЛИЦА 
ИНВЕРСИЙ $b_1$ $b_2$ \dots $b_n$; КАКОЙ ПЕРЕСТАНОВКЕ $\bar a_1$ $\bar a_2$ 
\dots $\bar a_n$ СООТВЕТСТВУЕТ ТАБЛИЦА ИНВЕРСИЙ
$$
(n-1-b_1) (n-2-b_2) \ldots  (0-b_n)?
$$

\rex[20] пРИДУМАЙТЕ АЛГОРИТМ, ГОДНЫЙ ДЛЯ РЕАЛИЗАЦИИ НА эвм, КОТОРЫЙ ПО 
ДАННОЙ ТАБЛИЦЕ ИНВЕРСИЙ  $b_1$ $b_2$ \dots $b_n$, УДОВЛЕТВОРЯЮЩЕЙ УСЛОВИЯМ 
(3), СТРОИЛ БЫ СООТВЕТСТВУЮЩУЮ ПЕРЕСТАНОВКУ  $a_1$ $a_2$ \dots $a_n$. 
[{\sl уКАЗАНИЕ:\/} ВСПОМНИТЕ МЕТОДЫ РАБОТЫ СО СВЯЗАННОЙ ПАМЯТЬЮ.]

\ex[35] дЛЯ ВЫПОЛНЕНИЯ НА ТИПИЧНОЙ эвм АЛГОРИТМ ИЗ УПР.~4 ТРЕБУЕТ ВРЕМЕНИ, 
ПРИБЛИЗИТЕЛЬНО ПРОПОРЦИОНАЛЬНОГО $n^2$; МОЖНО ЛИ СОЗДАТЬ АЛГОРИТМ, ВРЕМЯ 
РАБОТЫ КОТОРОГО БЫЛО БЫ СУЩЕСТВЕННО МЕНЬШЕ $n^2$?

\rex[26] пРИДУМАЙТЕ АЛГОРИТМ ВЫЧИСЛЕНИЯ ТАБЛИЦЫ ИНВЕРСИЙ $b_1$ $b_2$ \dots 
$b_n$, СООТВЕТСТВУЮЩЕЙ ДАННОЙ ПЕРЕСТАНОВКЕ $a_1$ $a_2$ \dots $a_n$ 
МНОЖЕСТВА $\{1, 2, \ldots, П\}$,, ВРЕМЯ РАБОТЫ КОТОРОГО НА ТИПИЧНОЙ эвм 
БЫЛО БЫ ПОРЯДКА $n\log n$.

\ex[20] пОМИМО ТАБЛИЦЫ $b_1$ $b_2$ \dots $b_n$, ОПРЕДЕЛЕННОЙ В ЭТОМ ПУНКТЕ,
 МОЖНО  ОПРЕДЕЛИТЬ НЕКОТОРЫЕ ДРУГИЕ ТИПЫ ТАБЛИЦ ИНВЕРСИЙ, СООТВЕТСТВУЮЩИХ 
ДАННОЙ ПЕРЕСТАНОВКЕ $a_1$ $a_2$ \dots $a_n$ МНОЖЕСТВА 
$\{ 1, 2, \ldots, n\}$. в ЭТОМ УПРАЖНЕНИИ МЫ РАССМОТРИМ ТРИ ДРУГИХ ТИПА ТАБЛИЦ 
ИНВЕРСИЙ, КОТОРЫЕ ВОЗНИКАЮТ В ПРИЛОЖЕНИЯХ.

пУСТЬ $c_j$---ЧИСЛО ИНВЕРСИЙ, \emph{ПЕРВАЯ} КОМПОНЕНТА КОТОРЫХ РАВНА $j$, 
Т.~Е. ЧИСЛО ЭЛЕМЕНТОВ, МЕНЬШИХ $j$ И РАСПОЛОЖЕННЫХ \emph{ПРАВЕЕ} $j$. 
[пЕРЕСТАНОВКЕ (1) СООТВЕТСТВУЕТ ТАБЛИЦА $0$ $0$ $0$ $1$ $4$ $2$ $1$ $5$ 
$7$; ЯСНО, ЧТО$ 0\le c_j<j$.] пУСТЬ $B_j=b_{a_j}$ И~$C_j=c_{a_j}$.

пОКАЖИТЕ, ЧТО ПРИ $1 \le j \le n$ СПРАВЕДЛИВЫ НЕРАВЕНСТВА $0\le B_j<j$ И 
$0\le C_j\le n-j$; ПОКАЖИТЕ ТАКЖЕ, ЧТО ПЕРЕСТАНОВКУ $a_1$ $a_2$ \dots 
$a_n$ МОЖНО ОДНОЗНАЧНО ОПРЕДЕЛИТЬ, ЕСЛИ ЗАДАНА ИЛИ ТАБЛИЦА $c_1$ $c_2$ 
\dots $c_n$, ИЛИ $B_1$ $B_2$ \dots $B_n$, ИЛИ $C_1$ $C_2$ \dots $C_n$.

\ex[м24] сОХРАНИМ ОБОЗНАЧЕНИЯ УПР.~7; ПУСТЬ $a'_1$ $a'_2$ \dots 
$a'_n$---ПЕРЕСТАНОВКА, ОБРАТНАЯ К  $a_1$ $a_2$ \dots $a_n$ И ПУСТЬ 
СООТВЕТСТВУЮЩИЕ ЕЙ ТАБЛИЦЫ ИНВЕРСИЙ--- $b'_1$ $b'_2$ \dots $b'_n$, $c'_1$ 
$c'_2$ \dots $c'_n$, $B'_1$ $B'_2$ \dots $B'_n$  И $C'_1$ $C'_2$ \dots 
$C'_n$. нАЙДИТЕ КАК МОЖНО БОЛЬШЕ ИНТЕРЕСНЫХ СООТНОШЕНИЙ МЕЖДУ $a_j$, $b_j$,
$c_j$, $B_j$, $C_j$, $a'_j$, $b'_j$, $c'_j$, $B'_j$, $C'_j$.

\rex[м21] дОКАЖИТЕ, ЧТО В ОБОЗНАЧЕНИЯХ УПР.~7 ПЕРЕСТАНОВКА $a_1$ $a_2$ 
\dots $a_n$ ОБРАТНА САМОЙ СЕБЕ ТОГДА И ТОЛЬКО ТОГДА, КОГДА $b_j=C_j$ ПРИ 
$1\le j\le n$.

\ex[вм20] рАССМОТРИТЕ РИС.~1 КАК МНОГОГРАННИК В ТРЕХМЕРНОМ ПРОСТРАНСТВЕ. 
чЕМУ РАВЕН ДИАМЕТР УСЕЧЕННОГО ОКТАЭДРА (РАССТОЯНИЕ МЕЖДУ ВЕРШИНАМИ 1234 И 
4321), ЕСЛИ ВСЕ РЕБРА ИМЕЮТ ЕДИНИЧНУЮ ДЛИНУ?

\ex[м25] (А) пУСТЬ $\pi=a_1\ a_2\ldots a_n$---ПЕРЕСТАНОВКА МНОЖЕСТВА $\{1, 2,
 \ldots, n\}$, $E(x)=\{(a_i, a_j)\vert i<j, a_i>a_j\}$---МНОЖЕСТВО ЕЕ 
ИНВЕРСИЙ, a
$$
\overline{E}(\pi)=\{(a_i, a_j)\vert i>j, a_i>a_j\}
$$
---МНОЖЕСТВО ЕЕ '"НЕИНВЕРСИЙ". дОКАЖИТЕ, ЧТО $E(\pi)$ И~$\overline{E}(\pi)$ 
ТРАНЗИТИВНЫ. [мНОЖЕСТВО $S$ УПОРЯДОЧЕННЫХ ПАР НАЗЫВАЕТСЯ 
\dfn{ТРАНЗИТИВНЫМ}, ЕСЛИ ДЛЯ ЛЮБЫХ $(a, b)$ И~$(b,c)$, ПРИНАДЛЕЖАЩИХ $S$, 
ПАРА $(a, c)$ ТАКЖЕ ПРИНАДЛЕЖИТ $S$.] (b) оБРАТНО, ПУСТЬ $E$---ЛЮБОЕ 
ТРАНЗИТИВНОЕ ПОДМНОЖЕСТВО МНОЖЕСТВА 
$T=\{(x, y)\vert 1\le  y < x\le n\}$, ДОПОЛНЕНИЕ КОТОРОГО $T\backslash E$ 
ТРАНЗИТИВНО. дОКАЖИТЕ, ЧТО СУЩЕСТВУЕТ ПЕРЕСТАНОВКА $\pi$, ТАКАЯ, ЧТО $E(\pi)=E$.

\ex[м28] иСПОЛЬЗУЯ ОБОЗНАЧЕНИЯ ПРЕДЫДУЩЕГО УПРАЖНЕНИЯ, ДОКАЖИТЕ, ЧТО ЕСЛИ 
$\pi_1$ И $\pi_2$---ПЕРЕСТАНОВКИ, А $E$---МИНИМАЛЬНОЕ ТРАНЗИТИВНОЕ МНОЖЕСТВО,
 СОДЕРЖАЩЕЕ $E(\pi_1)\cup E(\pi_2)$, ТО $\overline{E}$---ТОЖЕ ТРАНЗИТИВНОЕ 
МНОЖЕСТВО. [сЛЕДОВАТЕЛЬНО, ЕСЛИ МЫ БУДЕМ ГОВОРИТЬ, ЧТО $\pi_1$ НАХОДИТСЯ 
"НАД" $\pi_2$, КОГДА 
$E(\pi_1)\subseteq E(\pi_2)$, ТО ОПРЕДЕЛЕНА РЕШЕТКА ПЕРЕСТАНОВОК; 
СУЩЕСТВУЕТ ЕДИНСТВЕННАЯ "САМАЯ НИЗКАЯ" ПЕРЕСТАНОВКА, НАХОДЯЩАЯСЯ "НАД" 
ДВУМЯ ДАННЫМИ ПЕРЕСТАНОВКАМИ. дИАГРАММА РЕШЕТКИ ПРИ  $n=4$ ПРЕДСТАВЛЕНА НА 
РИС. 1.]
%% 34

\bye