\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