/
Text
Д.Грин, Д.Кнут
Математические
методы
анализа
алгоритмов
Издательство «Мир»
Progress in Computer Science
Vol. 1
Edited by
E. Coffman,
R. Graham,
D, Kuck
Daniel H, Greene, Donald E. Knuth
Mathematics for the Analysis
of Algorithms
Second Edition
1982
Birkhauser
Boston ♦ Basel Stuttgart
Д.Грин, Д.Кнут
Математические
методы
анализа
алгоритмов
Перевод со второго английского
издания
Б. Б. ПОХОДЗЕЯ
под редакцией
Ю. В. МАТИЯСЕВИЧА
Москва «Мир» 1987
ББК 22.18
Г 85
УДК 519.6 + 681.142,2
Грин Д., Кнут Д.
Г85 Математические методы анализа алгоритмов. — М.;
Мир, 1987. — 120 с., ил.
ОршKii.MbHOi II нссгин.'ыргное изложение известных методов анализа
алгоритмов, написанное крупным американским специалистом Д. Кнутом в
соавторе!не с Д. I рином В мине представлены; комбинаторные тождества,
рскурреи |ные 1-оот ношения, ас и митотические представления. От читателя тре-
б\етсн звакомст (о . п. н >ij..im.i корни вероятностей, комбинаторного анализа и
теории функций комн.ц Kt нт о переменного.
Для сис|синих программистов, математиков-прикладников, аспирантов и
студентов университетов
Г .11020.700.00-051
041(01)—87 ’
ББК 22,18
Редакция литературы по математическим наукам
УЧЕБНОЕ ИЗДАНИЕ
Дэниел X. Грин, Дональд Э. Кнут
МАТЕМАТИЧЕСКИЕ МЕТОДЫ АНАЛИЗА АЛГОРИТМОВ
Ст, научи, ред. И. А, Маховая. Мл, научи, рсд. Н. С. Полякова.
Художник А. Д. Смеляков, Художественный редактор В. И. Шаповалов.
Технический редактор В. II. Сизова, Н. И. Манохина, Корректор М. А. Смирнов
ИБ № 5591
Сдано в набор 16.04.86. Подписана к печати 05.01.87. Формат бумаги 60X90 */»•
Бумага типографская № 2. Печать высокая, Гарнитура литературная. Объем 3,75 бум, л.
Усл печ. л. 7,50. Усл. кр,-отт, 7,90. Уч.-изд, л. 6,85, Изд, №1/1326, Тираж 10 000 экз.
Зак, № 259, Цена 55 к.
ИЗДАТЕЛЬСТВО «МИР» 129820, ГСП, Москва. И-ЛО. 1-й Рижский пер., 2
Ленинградская типография № 2 головное предприятие ордена Трудоного Красного
Знамени Ленинградского объединения «Техническая книга» им. Евгении Соколовой
Союзнойиграфпрома при Государственном комитете СССР по делам издательств, по-
лиграфии и книжной торговли. 198052, г. Ленинград, Л-52, Измайловский проспект, 29,
© Birkhauser Boston, 1982
© перевод на русский язык, с до-
полнениями, «Мир», 1987
От редактора и переводчика
Издательство «Мир» сочло целесообразным в дополнение
к ранее изданным у нас трем томам Искусства программиро-
вания для ЭВМ Д. Кнута перевести на русский язык учебник
Математические методы анализа алгоритмов, написанный
Дональдом Э. Кнутом в соавторстве с его молодым коллегой
Дэниелом X. Грином. Данный компендиум интересен прежде
всего тем, что он составлен из конспектов лекций и экзаме-
национных задач по курсу математического анализа алго-
ритмов, который был введен профессором Д. Э, Кнутом на
факультете информатики Стамфордского университета в
1974 г. По-видимому, именно о таком учебнике по анализу
алгоритмов размышлял Д. Кнут в предисловии к третьему
тому своего Искусства,,. .
Книга написана чрезвычайно сжато и содержит массу
языковых эллипсов: зачастую авторы ограничиваются лишь
набросками математических выводов и сопровождают их
весьма лаконичными комментариями. Другой особенностью
книги является нестандартность изложения в общем-то тра-
диционного материала1) и обилие вольностей речи, которые
мы в меру наших литературных способностей старались со-
хранить в переводе.
Одно из правил, которым руководствуется Д. Кнут при
написании своих книг, состоит в том, что «автору, который
заинтересован в доходчивости излагаемого им материала,
следует всячески избегать сносок, поскольку последние отвле-
кают внимание читателя» (D. Knuth, The T^Xbook.— Reading:
Addison-Wesley, 1984, p. 117). Вследствие этого в переводе
(и, разумеется, в оригинале) Математических методов ана-
лиза алгоритмов сносок нет: большая часть примечаний ре-
дактора и переводчика (отмеченных в тексте цифрами) вы-
несена в отдельный раздел, а меньшая размещена в тексте
самого перевода. Список литературы дополнен ссылками на
имеющиеся у нас переводы и некоторыми комментариями к
оригинальным изданиям. В конце книги помещено также
написанное переводчиком дополнение «Д. Э. Кнут и его «фаб-
рика книг»».
Автор принял живое участие в подготовке русского изда-
ния его книги, и мы приносим ему за это свою глубокую
признательность.
10. В, М. и Б. Б. IL
К русскому изданию
Мне очень приятно, что эта небольшая книжка издаетст
на русском языке, поскольку я надеюсь, что математики, где
бы они ни находились, разделят мой энтузиазм относительно
анализа алгоритмов. Цель книги состоит в рассмотрении воз-
можностей, которые дает соединение дискретной и непрерыв-
ной математики, ибо, как показал опыт, это очень плодотвор-
но при исследовании машинных программ. Может ли это
быть чисто случайным совпадением, что подобное соединение
оказывается весьма плодотворным само по себе? Мы нахо-
димся в таком благоприятном положении, когда можем
создавать математику, являющуюся одновременно и краси-
вой, и полезной.
Дональд Э. Кнут
Станфорд, Калифорния
20 мая 1986 г.
Предисловие
Настоящая монография возникла из лекций по анализу
алгоритмов для студентов старших курсов факультета инфор-
матики Станфордского университета. В этом курсе представ-
лены примеры основных приемов, используемых при деталь-
ном анализе алгоритмов, с выделением некоторых наиболее
трудных из них. Значительная часть материала взята из от-
меченных звездочкой разделов третьего тома Искусства про-
граммирования для ЭВМ Д. Кнута.
Анализ алгоритмов как дисциплина по сути своей опи-
рается и на информатику, и на математику. Данный курс —
это взгляд на их синтез с математической точки зрения, но
с мотивировками и примерами из информатики. Он охваты-
вает биномиальные тождества, рекуррентные соотношения,
операторные методы и асимптотические представления. Мы
надеемся, что материал изложен достаточно сжато, чтобы
книгой можно было пользоваться как справочником, и вместе
е тем достаточно подробно, чтобы книгу смогли читать те,
кто не посещал лекций. Тем не менее предполагается, что
читатель знаком с основами теории функций комплексного
переменного и комбинаторного анализа.
Зимой 1980 г, курс анализа алгоритмов читался в четвер-
тый раз2), в связи с чем следует отдать должное предыду-
щим лекторам и ассистентам — Лео Гюибе, Скотту Драйсдей-
лу, Сэму Бенту, Энди Яо и Филлис Уинклер — за их суще-
ственный вклад в конспектирование курса; часть их записей
вошла в настоящую монографию. Полезные замечания и по-
правки сделали также Гарри Мэйрсон, Эцдрью Бродер, Кен
Кларксон и Джефф Виттер, При подготовке рукописи книги
использовалось оборудование корпорации Xerox и финансо-
вая помощь Фонда стипендий Херца. Национальный научный
фонд и Отделение военно-морских исследований щедро суб-
сидировали исследования, сделавшие возможным данный
курс. Сама книга была подготовлена к печати с помощью
наборной системы ТдХ с использованием семейства шрифтов
COMPUTER MODERN, разработанного недавно посредством
системы METAFONT3).
Во втором издании частично улучшено изложение мате-
риала и исправлен ряд незначительных ошибок. Кроме того,
добавлены экзаменационные задачи зимнего семестра 1982 г.
Д. X. Г. и Д. Э, К.
Глава 1
Биномиальные тождества
1.1. Сводка полезных тождеств
Чтобы тождества не затерялись
ных страницах, соберем их вместе.
на ничем не примечатель*
(х Ч- у)п = У ) хь!Г~к, целое или
А;
п вещественное и \х/у\< I, (1.1)
( г \ ( г ~ \ ( г ~ \
1^1 = 1 + I £ _ J J • г вещественное, k целое, (1.2)
/ п \ / п \
\ k, ) = 1 п _ & 1, п целое ^0, k целое, (1.3)
( г \ г (г — 1 \
\ k , / —vl^_i/‘ г сещетвенное, k целое #= 0, (1.4)
п ZI fc = Q + /г + п + 1 \ .1 — 1 1, г вещественное, п целое ^0, Ас / \ Hf /
п ZI А^О (1-5) f k \ / п + 1 \ 1 = 1 ,11. т, п целые ^0, (1.6) ^tn J \т 1 J v 7
г вещественное, k целое, (1.7)
г вещественное, tn, k целые,
(1-8)
п целое, (1.9)
п целое,
п целое, г целое ^0,
(МО)
г целое 0, (1.11)
1,2. Вывод тождеств
9
ьо
г + S + 1
т + п + 1 /
п, т> г, s целые О,
(1.12)
Та легкость, с которой знакомое биномиальное тождество
может измениться до неузнаваемости после нескольких пре-
образований, несколько сбивает с толку. Из-за подобной из-
менчивости внешней формы соотношений с биномиальными
коэффициентами ничто не может заменить практических на-
выков обращения с ними. Объяснение приведенных выше
формул и полезные упражнения читатель найдет в книге
Кнута [I, разд. 1,2.6].
1.2. Вывод тождеств
Существует простой способ запомнить многие из тождеств,
в которых нет перемены знака. Число путей, проходящих
через прямоугольную решетку со сторонами m и п, равно
Разрезая решетку в различных направлениях и под-
считывая число путей4) в соответствии с тем, где они пере-
секают линию разреза, мы будем получать то или иное тож-
дество. На приведенных ниже рисунках показаны различные
способы группировки путей и указан индекс суммирования k.
Группируя пути по месту попадания на
верхнюю сторону, получаем тождество
(1.5).
Подсчитывая пути в соответствии с тем,
где оии пересекают вертикальную линию,
получаем тождество (1.12).
Аналогично, группируя пути по месту пе-
ресечения с наклонной линией, получаем
тождество (1.9).
Последовательно применяя тождества (1.1)—(1.12), можно
получить более сложные соотношения. Один из таких приме-
ров содержится в статье Йонассена и Кнута [78], где сумма
£(?)(-<*)
й
(1.13)
10
I. Биномиальные тождества
вычисляется с помощью длинной серии элементарных преоб-
разований, Вместо того чтобы приводить здесь этот вывод,
воспользуемся подходом, который предложил А. Гос сель, при-
писывая соответствующую элегантную технику-—«метод ко-
эффициентов^ — Г. II. Егорычеву5).
Заменим вначале /? на т — k, получая
гц X z [ ч т~ k / 2m — 2k \
k ) \ 2 / \ m — k }'
(1.14)
Используя обощачение <л’’)Нх) для коэффициента при хп в
разложении /(а), можно выразить части суммы через произ-
водящие ф\нкции:
(т\ z I ч - ft .
*)(-{) = <х*>(1 — 2х)"*. (115)
/ 2m — 2fe X
( m k (Мб)
\ tTl гС У
В целом сумма принимает вид
S= -2Н"(Г-‘>(1 +</)2m*aS. (1.17)
k
Замечая, что {ут~к} = {ут')ук, мы можем вынести (ут) за знак
суммы:
s=(-|Г <л (1 + </)!n 2 <**><1 -2х|'" (лгт^-У с 18>
X У X и "f iff /
£
Наконец, эти на первый взгляд бесцельные преобразования
приводят к блестящему финалу. Сумма в последней формуле
есть простая подстановка вместо х, поскольку
X &k) f W g (У)к = f (g Ш (1-19)
когда f — аналитическая функция. Решение следует
леино:
S = (—2)_'n ((/“)(! +</Г (1
= (—2)“"(i/m)(l + г/2)"1,
так что
/ tn X
2 ( I, если
\ т/2 /
О, если
немед-
(1.20)
(1.21)
2у y?I
(1 + У)2 ) "
т четно,
m нечетно.
Более простой подход к этой задаче был указан С, К. Рус-
со: замечая, что (2*) является коэффициентом при х° в раз-
1,3- Обратимые соотношения
11
Ложении (х -J- х-1)2\ получаем, что S есть коэффициент при
х° в разложении (1 —(% + х"1)2/2),?l.
С теоретической точки зрения было бы заманчиво объеди-
нить подобные тождества в одну согласованную схему, по-
добно тому как физики пытаются создать единую теорию
поля. К сожалению, единственной схемы, охватывающей все
тождества, нет, но имеется несколько «мета»-понятий, кото-
рые объясняют существование обширных классов биномиаль-
ных тождеств. Изложим вкратце три из них: обратимые соот-
ношения, операторное исчисление и гипергсометрпческий ряд.
1.3. Обратимые соотношения
Вот одна пара из простейшего множества обратимых соот-
ношений:
(ft \ / ft \
, К 6„=У(-1)‘ U, (1.22)
и? У \ гС у
R k
которая следует из ортогонального соотношения
(1.23)
А это соотношение является всего лишь конкретизацией ра-
венства (1.11) с s, равным 0. В общем случае обратимое со-
отношение будет объединять два ряда так, что отдельные
члены одного из них могут быть вычислены по членам дру-
гого и всегда будет существовать связывающее их ортого-
нальное соотношение.
В своей книге Комбинаторные тождества Джон Риордан
[68] посвящает несколько глав обратимым соотношениям.
Поскольку обратимые соотношения имеют еще большую
склонность к изменению внешней формы по сравнению с би-
номиальными тождествами (что мы уже видели), надо уметь
распознавать соотношения, в сущности одинаковые. С этой
целью Риордан описывает несколько преобразований и затем
распределяет эквивалентные обратимые пары по обширным
классам. Ниже приводятся его преобразования и классифи-
кация.
Поскольку каждый раз мы имеем дело с парой равенств,
с помощью подстановки типа bfk — {—можно переме-
стить члены одного из равенств в другое и получить новую
пару;
<L24>
fl /а
12
I. Биномиальные тождества
Обратимое соотношение соответствует паре нижних треуголь-
ников матриц, произведением которых является единичная
матрица. Отражая элементы матриц относительно диагонали,,
можно вывести еще одну пару:
X(*)"•• *»= Zt-WJU- о-25>
k ' П ' k '^п
За моим, наконец, чл> оби чисти ортогонального соотношения
(1.23) можно умцнжип, на почти любую функцию, которая
равна единице при п не изменяя ортогонального харак-
тера равенства.
Последнее равенство (1.25) имеет исключительно полез-
ный комбинаторный смысл. Предположим, что имеется боль-
шая совокупность случайных событий, Пусть Ъп — вероятность
того, что произошло ровно н событий, и пусть ап— сумма ве-
роятностей п одновременных событий, взятая по всевозмож-
ным комбинациям из п событий. Грубо говоря, ап может рас-
сматриваться как небрежный способ вычисления вероятности
того, что произошло ровно п событий, поскольку при этом не
учитывается возможность осуществления более чем п собы-
тий6). Левая часть (1.25) показывает, как растут значения ап.
Однако зачастую ап вычислить легче, и правая часть равен-
ства (1.25) — «принцип включения и исключения» — пред-
ставляет собой практичный способ вычисления Ьп.
Равенства (1.22), (1.24) в (1.25) принадлежат простей-
шему классу обратимых соотношений. Риордан [68] пере-
числяет несколько других классов обратимых соотношений,
в частности соотношений чебышевского типа:
L ^/2 J , ч L п/2 J / . .
1 \ т—, 1 fi I ‘ К" 1
= X ( У Х''1’22’ X ( п — ft ( fy Jan-2lr
k = (J fe = 0
(1,26>
Неудивительно, что обратимые соотношения часто связаны с
одноименными ортогональными многочленами, которые ис-
пользуются при интерполяции.
Класс обратимых соотношений Гульда
Z, /и \/а4- bk\
(-4Д п )е„. (1.27>
k
fa + bn\ +ьь _ ь f aJr bn —k\
Ц „ )=£<-»*„_fc )b (1.28)
k
обладает любопытным свойством. Недавно китайский мате-
матик Л, Сю обнаружил, что для справедливости обращения
L3. Обратимые соотношения
13
здесь не обязательны биномиальные коэффициенты с а и Ъ.
Действительно, если в качестве {а,} и {&J выбрать любые
две последовательности чисел, такие, что
п
ф(х, п) — Ц (а(- + bi*) ¥= 0 при целых х, п^О, (1.29)
то получится общее правило обращения:
= Ч k n)gt, (1.зо)
(/7 \
Jte+1 + ^+i)4>(«. 6 + irX (i.3i)
ft
В другой хорошо известной паре обратимых соотношений
используются числа Стирлинга:
R гл
а^УУ-1)"-" 1 Ьь,
fe=0
ГДС [*]“ числа Стирлинга первого рода;
(1.32)
(1.33)
где {fe} —числа Стирлинга второго рода, Обычно в качестве
ап используется х- (обозначение х- разъясняется в начале
следующего раздела. — Ред.), а в качестве Ьп используется
хя, так что эти формулы обращают факториалы в степени х
и наоборот.
Мы не в состоянии исследовать здесь все обратимые соот-
ношения, отмстим лишь, что многие производящие функции
могут быть преобразованы в обратимые соотношения. Пара
степенных рядов г(х) и г*(х), таких, что z(x)z*(x)=l, дает
пару соотношений
а (х) = z (х) b (х) и b (х) — z (х) а(х). (1-34)
Например, можно положить г(х) — (1 —-х)_р и г* (х) =
= (1—х)₽; ясно, что z(x)z*(x)= 1, поэтому можно выписать
формулы для коэффициентов в а(х) и Ь(х):
Данная пара является представителем класса обратимых со-
отношений Гульда,
м
1. Биномиальные тождества
Ответственность за разнобразпе биномиальных тождеств
частично ложится на обратимые соотношения. Если один член
пары обрашмых соотношений может быть выражен в виде
биномиального тождества, то другой член этой пары, как
правило, будет представлять собой уже иное тождество. Об-
р; гимые соотношения могу; и непосредственно использовать-
ся при нна.нне aan)pin\i.i Например, при изучении пораз-
р?дной обменной о»рпри<вьи используется простое множе-
ство соотношении ( 1 22). ши ,н иных в начале настоящего раз-
дела (подробнее см Кн\л |1П. vnp. 5.2.2.-36 и 5.2.2-38] ).
1.4. Операторное исчисление
С) щсств\ет пора пыи.п.Н'к сходство между интегралом
ь
xr dx = -Лгт (1-36) П + 1 а 4 '
и суммой а а С х< b п+1 & = 7Г+Г ’ <Ь37> n i 1 а
где х с подчеркнутым верхним индексом означает убываю-
щий факториал х- = х (х — 1) ... (х — п 1). Последняя сум-
ма является попросту приведением равенства (1.6) к легкому
для запоминания виду. Его, несомненно, легче запомнить, чем
формулу для сумм степеней (4.17).
Сходство равенств (1.36) и (1.37) является следствием
того факта, что Dxn — пх71"1 и Лх- = «х—где D и Л — диф-
ференциальный и разностный операторы, которые обратны
операторам J и Dp (х) = pf (х) и Лр (х) = р (х + 1) — р (х).
Подобную аналогию можно продолжить еще дальше;
например, Джан-Карло Рота предлагает следующее обобще-
ние теоремы Тейлора.
Определения. Пусть Еа — оператор сдвига, Еар{х) =
= р(хф-а). Оператор Q является дельта-оператором, если он
инвариантен относительно сдвига (QEa = EaQ) и если Qx —
отличная от нуля константа. Такой оператор имеет последо-
вательность базисных многочленов, определяемых следующим
образом:
1) р0(х)= 1,
2) Рге(О)=О При
3) Qprt(x) = rtpw_1(x).
1.5. Гипергеометрический ряд
15
Третье свойство означает, что всякий раз, когда Q действует
на свои базисные многочлены, результат аналогичен действию
оператора D на последовательность 1, х, х2.....Например,
А является дельта-оператором с базисными многочленами
х- = х (х — 1) ... (х — п ф-1).
Теорема Тейлора
(1-38)
k
где Т — любой инвариантный относительно сдвига оператор,
Q — любой дельта-оператор с базисными многочленами
Р><(х),
= (х)]Л=0.
При Т = Еа и Q = D эта формула сводится к хорошо извест-
ной формуле Тейлора. Заменяя Q на разностный оператор А,
получаем ньютоново разложение
р(х + а) = £-£д‘р(х). (1.39)
k
Разложение Ньютона весьма полезно при доказательстве би-
номиальных тождеств. Например, равенство (1.9) является
разложением величины р (s ф г) = (а ф- г) .
Полное изложение операторного исчисления в его связи
с биномиальными тождествами можно найти в книге Рота
и др; [75]. Тесную связь между дискретным и непрерывным
случаями читатель заметит также в гл, 2, где разностные
уравнения напоминают дифференциальные, и в разд. 4.2, по-
священном интегрированию по Стилтьесу, где с целью вычис-
ления сумм «интегрируются» функции «пол» и «потолок».
1.5, Гипергеометрический ряд
Геометрический ряд 1 ф г ф г2 ф ... =1/(1—г) может
быть обобщен до гипергеомстрического ряда
„Г t. 1 1 I ab z . а (а ф 1) b (Ь ф 1) г2 .
&;с;г] = 1 + 7--гг+ e-(--+7j----...
zn
а-4°)
с л!
где надчеркнутый верхний индекс обозначает возрастающий
факториал ал — а (а ф 1) ,.. (а ф п — 1), а нижние индексы
у F указывают на то, что существуют два параметра (а, Ь)
16
1,- Биномиальные тождества
в числителе и один параметр (с) в знаменателе. Гипергео-
мстричсский ряд можно обобщить на случай произвольного
числа параметров в числителе и знаменателе.
Много света на теорию биномиальных тождеств пролила
их стандартизация, обеспеченная гипергеометрическим рядом.
Например, тождества (1.5), (1.10) и (1.11) все являются след-
ствием теоремы Вандермонда:
з/7! [ci, — п; с; 1 ] ~--- при целом п > 0. (1.41)
Наличие отрицательного аргумента обрывает ряд, который
в противном случае был бы бесконечным, позволяя выразить
(1,10) как видоизменение угон формулы:
srt с . , tin s~ ($4-if + Z1
— a/7] L— Г, - s + «+ 1; 1] = -— ' = 1 I. (1.42)
n? n! (n + l)r \ Г -p n /
Дальнейшую информацию по гипергеометрическому ряду
можно найти в книгах Бейли [35], Слейтер [66] и Хенричи
174].
1.6. Тождества с гармоническими числами
При анализе алгоритмов часто встречаются любопытные
тождества, которые включают в себя как биномиальные коэф-
фициенты, так и гармонические числа. Ниже дается сводка
таких тождеств:
п
Hn-Yi- <k43>
ы
п
£ Н„ = (п+1)Нп-п,
k=l
(1.44)
Д (k \ М+1 X / 1ч
Z-j V m 7 й \m + 1/\ m + I ) 4 1
jfe=i
X (Иед4 = (х+1)я(я„-1п(| +-L)) + s, (1.46)
A = 1 4 '
x > 0, 1 < e < 1/(х(« + 1)),
1 / 1 \ П ( “I- TM \
|п(тдт)=Х (^+т-/Ц)( „ )у. пл?)
1.6. Тождества с гармоническими числами
17
и _‘г+, 1п(ттД = Z ^нп+т-нту-
Два последних тождества вместе с их обобщением на слу-
чай более высоких степеней приведены в статье Зэйва [76].
Их можно рассматривать как тождества, справедливые
при комплексных значениях tn с Нп+т — Нт — \/{т + 1)4-
4- 1/(щ 4- 2) 4- ... 4- 1/(т4- «); см- решение задачи 9g.
Глава 2
Рекуррентные соотношения
2.1. Линейные рекуррешные соотношения
При классификации .тнгпных рекуррентных соотношений
будет испили u main с я следующая терминология. Рекуррент-
ная цоследона и-льность с «частичной предысторией» зависит
от некотороги фиш иронални] о числа предыдущих членов:
xfi = / хГ1-2, .... Хл-г), п L (2.1)
Нелн хп зависит' о г всех предшествующих членов, то последо-
вательность имеет «полную предысторию».
Простейшим рекуррентным соотношением будет соотноше-
ние с частичной предысторией, имеющее «постоянные» коэф-
фициенты, Здесь проводится терминологическая параллель
с теорией дифференциальных уравнений; мы будем различать
«однородный» и «неоднородный» случаи в зависимости от
отсутствия или наличия дополнительного члена g(n) в соот-
ношении
CQXn + С[Хп-~1 + ... + CiXn~i — g (n). (2.2)
Имеются две классические работы по исчислению конечных
разностей: одна — книга Йордана [60], другая — Милн-Том-
сона [ЗЗ]7). Хотя главными темами этих старых работ были
приближение и решение дифференциальных уравнений —
темы, лежащие скорее в русле численного анализа, а не ана-
лиза алгоритмов, — из этой теории можно почерпнуть много
полезного, Мы также рекомендуем недавний обзор Шпигеля
[71] и Введение в вычислительную комбинаторику, которое
написали Пейдж и Уилсон [79],
В настоящем разделе даны ссылки на дополнительные
примеры решения рекуррентных соотношений из книг Кнута
[I, III]. Излагаемый в последней части раздела «репертуар-
ный» подход к соотношениям с полной предысторией был вве-
ден в статье Кнута и Шёнхаге [78].
2.1J. Частичная предыстория
2.1.1.1. Постоянные коэффициенты
Соотношения с постоянными коэффициентами представ-
ляют собой прекрасный пример использования производящих
функций для решения рекуррентных уравнений. Вместо того
2.1. Линейные рекуррентные соотношения
19
чтобы пытаться найти хп непосредственно, образуем функ-
цию G(z) с коэффициентами хп в сс разложении в степенной
ряд:
G(z)=Ex,z'. (2.3)
Рекуррентное соотношение преобразуется в уравнение относи-
тельно G (г), которое разрешается любым приемлемым спо-
собом. Лучше всего объяснить это на примере соотношения
ху1+2 —Зхи+1 + 2лу = д, x0 = Xj = 1. (2.4)
Умножим вначале (2.4) на гп^2 и просуммируем по всем п,
получая
Е xn+2zn+2 — 3z X xfl + izn+] + 2z' X xnzn = X nzn+2. (2.5)
л > О /I _> 0 n > 0 n > О
Первая сумма есть G(z) без двух начальных членов. Подобно
первой, две другие суммы также близки к G(z), а правая
часть данного равенства может быть выражена в замкнутой
форме как г3/(1 —г')2. (Это следует нз «биномиальной теоре-
мы»— уравнения (1.1), когда (х-|-г/)л = (1—2)~2, Список
стандартных выражений для производящих функций в замк-
нутом виде приведен в книге Кнута [I, разд. 1.2.9].)
Собирая предыдущие результаты вместе в одну формулу
для G(z), получаем, что
G (2) - z - 1 - 3z (G (2) - 1) + 2z3G (2) . (2.6)
А это уравнение легко разрешается относительно G (2):
О (г) = (1 _ г)2{1 _ 3, + 2г2) + 1 _ з2 + 2г2 ' (2'7)
Нам хотелось бы выяснить, чему равен коэффициент при zn
в разложении G(z). Если бы знаменатели дробей в выраже-
нии для G(a) были линейными функциями, то задача реша-
лась бы просто: каждый член был бы геометрическим рядом.
В данном случае это не так, но представляя найденное ре-
шение для G(z) в виде элементарных дробей, можно полу-
чить удобную для работы форму:
G (2) = т-Ц: F п 1 - 7Г-Цт ' (2.8)
у ’ 1 —2г 1 (1 — г)2 (1 — г)3 v 7
Заметьте, что нелинейные знаменатели—это всего лишь сте-
пени линейного двучлена. Такне члены могут быть разложены
в биномиальный ряд, и хп легко вычисляется:
х„ = 2'‘--^Ур-. (2.9)
20
2. Рекуррентные соотношения
Элементарные дроби представляют собой достаточно мощ-
ный инструмент для решения широкого круга уравнений с по-
стоянными коэффициентами. Для простоты мы включили в
последующее изложение другой подход, который можно най-
ти в обзоре Шпигеля [71] и большом числе более старых
источников. Этот подход основан на пробных решениях и
аналогичен решению дифференциальных уравнений. В неко-
торых случаях он обеспечивает быстрое получение ответов,
однако способы их получения зачастую подобны «черной ма-
гии», и озадаченный читатель будет вынужден обратиться к
лежащей в их основе теории элементарных дробей для того,
чтобы понять, почему подобные «правила буравчикам ра-
ботают.
А) Однородные уравнения:
с^хп + + + C'Xn-i = 0, (2.10)
Попробовав положить хп~гп, получим многочлен i-й сте-
пени от переменной л Пусть гь г2, ,,,, гг- — корни этого мно-
гочлена. Тогда «общим решением» уравнения (2.10) будет
Хп = М + W + +kirl С2-11)
где ki — постоянные, определяемые начальными условиями.
Случай кратных корней учитывается введением в члены
общего решения степеней п. Предположим, что и — г2 == с3;
тогда подправленное решение будет таким:
= + k^n-r1^ (2.12)
В) Неоднородные уравнения:
+ ... + срсп^ = ё(п). (2.13)
Вначале удалим g(n) и найдем общее решение однородного
уравнения. Затем к полученному решению прибавим любое
«частное» решение неоднородного уравнения.
Частное решение может быть найдено методом «неопре-
деленных коэффициентов». Суть этого метода состоит в ис-
пользовании пробного решения с неизвестными коэффициен-
тами с последующим их определением. Характер пробного
решения зависит от вида g(n):
Вид g (п)
Пробное решение
ап kan (умноженное на п., если а — корень)
р (п) многочлен той же степени
2.1. Линейные рекуррентные соотношения
2!
2.1.1.2. Переменные коэффициенты
Гарантированного способа решения задачи с переменны-
ми коэффициентами пе существует, однако имеется несколько
методов, которые следует попытаться применить.
А) Суммирующие множители. Если уравнение является
уравнением «первого порядка»:
а (п) хп — b (п) хп^} -Г с (п), (2.14)
то оно может быть решено суммированием8). Умножим вна-
чале обе части уравнения на суммирующий множитель
/Чл) = П(2.15}
i=l /=1
Тогда рекуррентное соотношение примет вид
Уп = Уп-\ + F (я) с (н), (2.16)
где уп — b(n “Е 1)Е(п + 1)х„. Последнее рекуррентное соотно-
шение позволяет выразить хп в виде суммы:
Хп= (м-р 1) Д(п + 1) ' (2-17)
Другие иллюстрации этой техники см. в книге Кнута [Шг
разд. 5.2.2] и в обзоре Люксра [80].
В) Производящие функции. Задачи с переменными коэф-
фициентами иногда поддаются решению с помощью произво-
дящих функций. Если коэффициентами являются многочле-
ны, то с целью получения желаемой изменчивости произво-
дящая функция дифференцируется. Чтобы получить представ-
ление об этом подходе, рассмотрим сравнительно простую
задачу
(t-E 1)х/+] — = (2-18)
Умножение на zl и суммирование по всем i приближает нас
к формуле, содержащей G(z):
У, (Z + 1) xf L — У, (Z + Й — О- (2-19)
i i
Используя производную функции (?(z) и умножение на z
с целью сдвига, получаем дифференциальное уравнение
(1 — z) G' (?) — rG (z) = 0. (2.20)
Вообще любое рекуррентное соотношение с коэффициентами,
которые являются многочленами от (, может быть сведено к
Дифференциальному уравнению типа (2.20). В нашем случае
09
2, Рекуррентные соотношения
ьоэффициснты решения G (г) = (1 —z)~r могут быть найдены
с помощью биномиальной теоремы:
/ г — 1 -J- п \
п }. (2.21)
Более трудные задачи будут давать исследователю боль-
шое разнообразна \ равнений, содержащих <7(г). Хотя по-
следние не всегда являилея дифференциальными, читатель
отсылается к монографии Бойса и Ди Прима [691 по поводу
тех дифференциальных \равнений, которые могут при этом
встретиться.
С) Понижение порядка Если нам немного повезет с раз-
ложением разностного уравнения на множители, можно по-
пытаться найти решения для каждого сомножителя в отдель-
ности. Например, разностное уравнение
—(k + 2)^+i“H^fe = /e (2.22)
может быть записано в операторной форме как
(tf + (k^2)E^k}yk = k. (2.23)
А этот оператор допускает разложение на множители:
(E-\)(E~k}y^k. (2.24)
Если вначале решить уравнение
(Е- l)zfe = /e, (2.25)
которое имеет простое решение = то искомое уравне-
ние сведется к уравнению первого порядка:
(Я -Й)У4 = (*}. (2.26)
Полученное уравнение можно решить, используя суммирую-
щий множитель F(n) — 1/nl:
п—3
^=-^4^X4-- (2-27>
1 = 1
Для простоты мы опустили начальные условия. Этот же
пример с начальными условиями у\ = 0 и у% — 1 решен Шпи-
гелем [71, с. 176].
Все три подхода к задаче с переменными коэффициентами
имеют серьезные недостатки. Метод суммирующих множи-
телей может привести к непостижимой для нашего ума сум-
ме, а метод производящих функций может доставить столь же
трудно поддающееся решению дифференциальное уравнение.
2.1. Линейные рекуррентные соотношения
23
И, увы, не существует надежного способа разложения на мно-
жители операторного уравнения при применении техники по-
нижения порядка. Уравнения с переменными коэффициента-
ми—это серьезная проблема; мы будем вынуждены вернуться
к ним позже при исследовании асимптотических приближе-
ний.
2.1,2, Полная предыстория
2.1.2.1. Вычитание
Этот подход сокращает предысторию путем вычитания
подходящих комбинаций близких формул. Например, в книге
Кнута [III, разд. 5.2.2] уравнение
л-1
<2-28>
fe=0
решается путем вычитания
п— I
пхп = nfa + 2 X хк (2.29)
fc=0
из
п
(п + 1) xtt + 1 = (п + 1) fn+1 “И 2 X (2.30)
в результате чего получается уравнение первого порядка с пе-
ременными коэффициентами. Обратите внимание, как акку-
ратно должны быть перегруппированы члены обеих формул,
чтобы освободиться от суммы, В более сложных ситуациях
для устранения предыстории может потребоваться несколько
вычитаний (в качестве примера см, Кнут [Ш, упр, 6,2.2-7] ).
2.1.2.2. Из репертуара
В этом подходе мы пользуемся линейностью рекуррентной
зависимости и составляем требуемое решение из «репертуара»
простых решений. Типичная рекуррентная зависимость, встре-
чающаяся при анализе алгоритмов, имеет вид
Хп — Un -р X Pnk “F Xп— &)’ S Pnk 1 ‘ (2.31)
0 fe < л fe
Если, кроме того, известно, что
Уп = Ьц Н- 52 Pnk (.Ук Н- Уп-kb (2,32)
о < k д п
24
2. Рекуррентные соотношения
то в силу линейности уравнение с аддитивным членом аал +
+ fib,t будет иметь решение ах„ 4- $уп.
Вот решающая идея: вначале хп выбирается так, чтобы
сделать сумму удобной для работы, а затем мы смотрим, ка-
кой аддитивный член а,, соответствует выбранному хп. Это
в точности обратно исходной задаче, когда ап задано, а хп
ищется. Однако, как только нами составлен достаточный ре-
пертуар аддитивных членов, искомая величина ап может быть
построена в виде их линейной комбинации.
В качестве примера рассмотрим рекуррентную зависимость
(Ч-i + xn-fe)>
(2.33)
связанную с вариантом «меднана-из-трех быстрой сорти-
ровки». Это вариант известного алгоритма «быстрой сорти-
ровки», который модифицирован так, что на стадии разделе-
ния выбирается медиана из трех элементов. В обычном ва-
рианте «быстрой сортировки» выбор каждого разделяющего
элемента равновероятен. Рассматриваемая модификация де-
лает несколько более вероятным то, что разделяющий эле-
мент будет разбивать массив примерно на равные части, как
это следует из распределения вероятностей рп^, фигурирую-
щего в приведенном выше рекуррентном соотношении. (По-
дробнее см. Кнут 1Ш, разд. 5,2,2]. — Перев.)
Вначале заметим, что сумма в (2,33) симметрична, и за-
меним аддитивный член на ап, подготовляя репертуар-
ный подход:
<_k<Zn
(2.34)
Выбор хп равным убывающему факториалу (л — 1)~ делает
сумму в уравнении (2.34) легкой для вычисления:
s 19 <?
g--^-l)--(7-+W + 3) 3Г- (2,36>
2.1. Линейные рекуррентные соотношения
25
Итак, мы имеем семейство решений, параметризованное ин-
дексом s:
хп
s = 0 I -1
S — 1 п — 1 2
5 = 2 (п- 1) (я-2) (2л3 4- 6/г — 26)/5
Однако данное семейство не достаточно полно — в нем от-
сутствует решение с линейным ап. Значения ап скачут от кон-
станты до 0(л2), но, к сожалению, нам нужна величина ап
порядка 0(н) (по поводу обозначения 0 см. разд. 4.1.1.—
Ред.}. Впрочем, это и не удивительно. Ожидается, что резуль-
тат подобного итерирования типа «разделяй и властвуй» бу-
дет иметь порядок О (л log л), и тем не менее мы ограничи-
лись возможными значениями x,t, которые являются много-
членами от л. Чтобы расширить наше семейство решений,
введем гармонические числа Нп, которые также легко сум-
мируются и внесут в решения множители порядка О (log и).
Подставляя хп — (п — Нп в уравнение (2.34) и разрешая
его относительно ап, находим новое семейство решений:
(л—!)-#„ = «„ +-у £ (л — k) (k — 1)— Hk_x =
t<t<«
। 12 Z V i?+l и
= ^ + —( 2^ л(/г — 1)~ —
n \l<fe<n
- % b-fh+ X
1<&<п l<A<n z
_ , 12 ( п— 1 X
“ art + + 2 V /4-2 J
t+3 / . X /
__ Л I 17 L— 1 _L 0 ] /0
/4-3________________________________t 4- 3 J /4-2 /
(Здесь для вычисления сумм, содержащих Нп, нами было ис-
пользовано тождество (1.45).) Полученный результат может
быть упрощен:
ап = Нп ((л — 1)“ — + 3) (п — 3) ) 4-
12 (2/+5? , __ ooy
+ (/ 4- 2)а (/ 4- З)2 V1 ’ (2-38>
•26
2. Рекуррентные соотношения
Ня этот раз, проверни начальные члены семейства решений,
мы обнаруживаем удачное выравнивание:
ап
t = o /д, + А
О
t~lj „ 1(//гг 2Hrt + -^-(n-3)
Оба на а .i л'.a i j х pi i.а ннч для an имеют своим главным
членом //. । п<>м'п 1 , -> родящей линейной комбинации
можно исключи! >. // и П'Иччигь величину ал, порядок роста
которой равен ч:
=(«т 1 i //., “ «„=-^4^ <2-39>
Чтобы подогнать постоянный член и получить ап, требуемое
в исходной задаче, используем решение из первого семейства
при s = 0;
х„ = -^-((л4-1)//„ + 1)«-а. = я+1. (2.40)
Полученное решение для хп может не согласовываться с на-
чальными значениями и х%. Для того чтобы сделать воз-
можными произвольные начальные значения, надо подыскать
две дополнительные «степени свободы» в этом решении. Одна
степень свободы может быть выявлена из первого семейства
решений. Объединяя решения прн 5 = 0 и при $ = 1, получаем
x,i = n + 1 ^ап= 0. (2.41)
Таким образом, в решение (2.40) может быть добавлена лю-
бая величина, кратная п -ф 1.
Вторая степень свободы не столь очевидна, Поскольку
ап =0, мы имеем упрощенную рекуррентную зависимость
ДЛЯ Хп".
п-хя=12 X (л — — 1)Ха,_|. (2.42)
i
Используя производящую функцию С (г) для последователь-
ности х„, свертку в правой части (2.42) можно представить
в виде произведения величины 1/(1 — г)2, соответствующей
п — k, и производной 6rz{2), соответствующей (k~~ 1)х^3. Та-
ким образом, получаем дифференциальное уравнение
О'" (г) = 714^7 О' (г). (2.43)
S.2. Нелинейные рекуррентные соотношения
27
Характер полученного уравнения подсказывает решение вида
G(z) = (l—z)a, и проверка этого решения дает а =—2 пли
а = 5. Возможность а — —2 уже отмечалась раньше; мы
знаем, что любое кратное п -р 1 не влияет на решение. При
а ~ 5 получаем необычное решение, которое есть 0, за исклю-
чением первых пяти членов:
Xj = — 5, х2~10, х3= —10, х4 = 5, х3= — 1. (2.44)
Это доставляет вторую степень свободы и дает окончатель-
ное решение;
12 /5\
х„ = у.((п+1)Я„ + 1) + с,(п+ 1)+ с2(-1)’(п ). (2.45)
где С] и с2 определяются начальными условиями.
2.2. Нелинейные рекуррентные соотношения
Нелинейные рекуррентные соотношения более трудны для
понимания, чем их линейные аналоги, а используемая тех-
ника, как правило, менее систематична, что требует проявле-
ния интуиции и находчивости вместо простого применения
шаблонных приемов. В данном разделе изучаются два типа
нелинейных рекуррентных соотношений: соотношения с функ-
циями максимума и минимума и соотношения со скрыто или
приближенно линейными рекуррентными зависимостями.
2.2.1. Соотношения с функциями максимума или минимума
При решении рекуррентного соотношения с шах- или min-
функциями прежде всего важно знать, где достигается мак-
симум или минимум. Это не всегда очевидно, поскольку max-
или min-функции могут зависеть от предыдущих членов по-
следовательности, вид которых первоначально неизвестен. Ти-
пичный подход состоит в вычислении с помощью рекуррент-
ного соотношения первых членов последовательности до тех
пор, пока мы не сможем сделать предположение о местопо-
ложении максимума (или минимума) на каждой итерации.
Сделанное предположение используется для решения рекур-
рентного соотношения, а полученное решение — для индук-
тивности доказательства правильности предположения.
Проиллюстрируем этот подход следующим примером ана-
лиза алгоритма перестановки на том же месте (Кнут [72];
см. также Кнут [I, разд, 1.3.3]. — Перев.). Кратко говоря,
данная задача возникает при анализе одного варианта алго-
ритма, который с целью выявления лидеров цикла осущест-
вляет поиск одновременно в двух направлениях. Для некото-
рого у алгоритм вначале рассматривает р(у') и Р'Ч/), затем
28
2. Рекуррентные соотношения
рЧ]) и р~Ч1) и т. Д‘ до тех пор, пока не встретится либо эле-
мент, меньший чем j (в этом случае / не является лидером
цикла (и отклоняется. — Ped.))t либо само / (в этом случае /
является лидером цикла, поскольку весь цикл уже про-
смотрен).
Вычислим стоимость /(я) алгоритма в наихудшем случае,
т, е, стоимость отклонения всех элементов, не являющихся
лидерами цикла длины п. Составление рекуррентного соот-
ношения основывается па том обстоятельстве, что второй наи-
меньший элемент цикла разбивает исходную задачу на от-
дельные подзадачи. Для удобства поместим лидера (наимень-
ший элемент) в начало цикла и предположим, что второй
наименьший элемент находится на fe-м месте:
(лидер) cic2c?j ...
...Ck-i (второй наименьший элемент) Ck+iC^ <^-1. (2.46)
Граница поиска при проверке па лидерство элементов ...
..., Cfe-i являются лидер и второй наименьший элемент цикла,
так что наихудший случай для этого сегмента идентичен наи-
худшему случаю для цикла длины /г. Аналогично, стоимость
наихудшего случая для сегмента c*+i, ..., сп-\ равна Чп— ^),
а стоимость отклонения второго наименьшего элемента равна
min (fe, п— k). Это дает рекуррентное соотношение
f (n) = max (f (k) — f(n — k) + min (0, n — /e)). (2.47)
k
Согласно намеченному выше подходу, первый шаг сво-
дится к составлению таблицы, в которой представлены зна-
чения [(я) при малых п вместе со списком значений k, при
которых достигается максимум:
п f (ч)
Значения k
I О
2 1
3 2
4 4
5 5
6 7
7 9
8 12
1
1, 2
2
1, 2, 3, 4
2, 3, 4
3, 4
4
На некоторых итерациях максимум достигается при многих
значениях k, но похоже, что при ^:=[я/2] он достигается
всегда. Исходя из этого предположения, рекуррентное соот-
2.2. Нелинейные рекуррентные соотношения
29
ношение (2.47) можно свести к следующим соотношениям:
f (2т) = 2f (т) + т
f (2т + 1) = f (m) + f (т + 1) + m. (2'48>
формулы для четных и нечетных членов близки друг к другу,
что наводит на мысль произвести вычитание:
Д/ (2п) = f (2п + 1) - f (2п) = f(n + 1) - f(n) = bf (n),
bf(2n+ l) = f(2n + 2)-f(2n+l)-
= f (n + 1) - f (n) + 1 = Д/ (n) + 1. (2.49)
В разностной форме становится ясным смысл A/(rt) и f(n):
Д)’(п) просто подсчитывает число единиц в двоичном пред-
ставлении п, а
f(n) = v (k) = у п log п + О (п), (2.50)
0 < &<п
где v(fe) — число единиц в двоичном разложении k, (Суммы
цифр, подобные данной, играют важную роль в теории рекур-
рентных соотношений, когда соответствующие последователь-
ности разбиваются примерно на равные части. Асимптотиче-
ское поведение f(n) имеет запутанную историю его независи-
мого нахождения несколькими авторами (Столарски [77]).
(См, Деланж [75] по поводу детального анализа этой асимп-
тотики, а также Кнут [III, упр. 5,2.2-15] по поводу сходной
задачи, решение которой связано с двоичным представлением
соответствующего аргумента.)
Для завершения решения уравнения (2.47) надо доказать
справедливость сделанного выше предположения о местопо-
ложении максимума или, что эквивалентно, показать, что
Функция от двух переменных
g (т, п) = f (т + п)— т — f(m) — f(ri), п^т, (2.51)
всегда неотрицательна. Записывая эту функцию отдельно для
четных и нечетных переменных и используя равенства (2.48)
Для f(i), получаем:
g(2m, 2n)~2g(m> п),
g(2m+ 1, 2n) = g(m, n)-\-g(m^-lt n),
g (2m, 2n 4- 1) = g (m, n) + g (m, n 4- 1),
g(2m 4-1, 2n 4-1) = 1 4~ g (m + 1, «) 4- g (m> «4-1)*
Тогда можно, используя граничные условия
g (n, n) =- О,
g(n— 1, n) = 0,
(2.53)
30
2, Рекуррентные соотношения
которые вытекают из определения соотношения для f, дока*
зать по индукции, что g(m, п)^ 0.
Сделанное в рассмотренном примере предположение о
местоположении максимума очевидно: интуитивно ясно, что
напхудшая ситуация имеет место, когда второй наименьший
элемент отстоит от лидера цикла настолько далеко, что on
делит цикл прпблв шгельно пополам. Приведем пример более
сложного предположен ня. Рассмотрим рекуррентное сооъ
ношение
До-- 1 -г iniri {--/(/- 1) + -^-/(п-о}, (2.5-JJ
которое возникает при анализе игры «отгадай задуманное
число», когда один из щрающих пытается отгадать задуман-
ное другим игроком целое число между 1 и п. После того как
один игрок называет предполагаемое число, другой сообщает
ему — больше, меньше или равно задуманиому названное
число. Величина /(«) представляет собой среднее число отга-
дываний в случае применения наилучшей из возможных стра-
тегий.
Интуиция вновь подсказывает нам, что лучше всего вы-
бирать I посередине интервала, но это, как ни странно, нс
всегда верно. Правильным решением с целью локализации
минимума является деление интервала 1, .,,, п на части не-
четной длины. Например, в случае п = 5 следовало бы начать
отгадывание с 4, а не с 3.
Имеется несколько общих результатов, которые могут
помочь в локализации минимума, Ниже приводится ряд
утверждений из статьи Фредмэна и Кнута [74], которые при-
менимы к рекуррентным соотношениям типа
/(«+ !) = £(«+ l) + min(«f(ft) + mn-k)) (2.55)
k
с положительными акр. Уравнение (2,54), умноженное на н.
также является членом этого обширного класса соотношений,
Определение. Вещественнозначная функция g(n) является
выпуклой, если A2g(n)^0 при всех п. Это означает, что
g(n + 2) — g(ft+ l)>g(n+ 1) — g(n), У/г>0. (2.56)
Лемма. Пусть а(п) и Ь(п) — выпуклые функции. Тогда
«минпозиция» с(п), определяемая как
с(п) = min (a (ft) + 6 (n — ft)), (2.57)
0< k
также выпукла. Кроме того, если с (н) = а (ft) b (п — k}, то
с(п + l) = min(a(/e) + 6(/i4- 1 — k), a (ft 4- 1) + b (п — ft)).
2.2. Нелинейные рекуррентные соотношения 31
{Другими словами, по мере увеличения п местоположение
минимума существенно не меняется. Термин «минпозиция»,
придуманный М. Ф. Плассом, подчеркивает сходство форму-
лы (2.57) с формулой композиции двух последовательностей.)
Доказывается эта сильная лемма очень просто. На про-
цедуру построения последовательности с{п) можно смотреть
как на слияние двух последовательностей
Да(0), Да(1), Да(2), ... (2.58)
и
\Ь (0) \b (1), \Ь (2), ... . (2.59)
По предположению члены этих двух последовательностей не
убывают. Тогда члены результирующей последовательности
Дс(0), Дс(1), Дс(2), ... (2.60)
также не убывают, откуда следует выпуклость с(п).
При каждом п элемент с(л) является суммой а-х наи-
меньших членов двух последовательностей (2.58) и (2.59).
Для определения следующего значения с(а+1) требуется
еще один член либо последовательности Да, либо последова-
тельности Д6, при этом вопрос о том, сдвигается ли место-
положение минимума из k в А-ф 1, определяется тем, в какой
из них находится наименьший элемент,
Теорема. Функция f, определяемая соотношением (2.55),
является выпуклой при условии, кто выпуклы g(n) и резуль-
тат первой итерации (2.55), т. е.
f(2)-f(l)54(l)-f(0). (2.61)
Теорема доказывается по индукции: предполагается, что
последовательность f(l), ..., f(n) выпукла, и с помощью
предыдущей леммы показывается, что добавление f(«4- 1)
будет сохранять выпуклость.
2.2.2. Непрерывные дроби и другие скрытые линейные
рекуррентные соотношения
Если рекуррентное соотношение похоже на непрерывную
дробь, то простым преобразованием нелинейную задачу мож-
но свести к линейному рекуррентному соотношению.
Рассмотрим, например, задачу подсчета числа Апь де-
ревьев с п узлами и высотой, не превосходящей п. При за-
данной высоте h для установления рекуррентного соотноше-
ния можно воспользоваться производящей функцией
MJ-EV1. (2.62)
32
2. Рекуррентные соотношения
Дерево высоты, не превосходящей Л 4-1, имеет корень и нс-
которое число поддеревьев высоты, меныпей или равной ht
так что
ЛЛ+, (г) = г (1 4- А (?) 4- Л (г)2 + Л (г)3 + ...) = ?/( 1 - А к (г)),
(2.631
«Непрерывно дробный» оттенок данного рекуррентного со-
отношения
ЛЛ+1 =-------—z----- (2.64)
наводит на мысль воспользоваться преобразованием
zP. (z)
л‘<г,=^> (2-65)
что приводит к линейному рекуррентному соотношению
P^) = Ph{z)~zPh_^ PQ(z) = 0, Л (г)=1. (2.66)
С помощью стандартной техники решения линейных соотно-
пгений 2-го порядка получаем
Л, (г) = (! - 4г) -‘4(' t У - ( ’ . (2.67)
Дальнейший анализ упорядоченных деревьев, связанный с
исследованием коэффициентов в выражении для Рк(г), не
имеет непосредственного отношения к нелинейным рекуррент-
ным соотношениям, поэтому за исчерпывающими подробно-
стями этого анализа читатель отсылается к работе де Брёйна,
Кнута и Райса [72].
Стоит заметить, что поиск преобразования, соответствую-
щего «непрерывно дробной» природе рекуррентного соотно-
шения, привел нас к преобразованию (2,65), являющемуся
отношением многочленов. В рассмотренном выше примере за-
кономерность, присущая рекуррентному соотношению (2,64),
позволила ограничиться только одним семейством многочле-
нов—многочленами Phiz}. В общей теории непрерывных
дробей, которая обеспечивает решение и в случае менее за-
кономерных непрерывных дробей, используются два семей-
ства многочленов. Вообще «n-я подходящая дробь»
Ь = «о +---------\-------- (2.68)
“ +-------—ТГ~
а2 4- ... 4- ——
«я
2.2. Нелинейные рекуррентные соотношения
33
представляется в виде отношения
f п Pnltfrii
(2.69)
где рп и qn удовлетворяют линейным рекуррентным соотно-
шениям
Рп &пРп- \ Н“ ^пРп-2>
Ро = аа, р]=а]а3-\-Ь1,
9о —1> ( J
Соответствующая теория, которую можно найти, например,
в книге Харди и Райта [79, гл. 10], гарантирует, что к задаче
с двумя линейными рекуррентными соотношениями можно
свести более сложное рекуррентное соотношение типа
Ш -
(2.71)
Кроме непрерывных дробей имеется много других типов
нелинейных рекуррентных соотношений, которые являются
всего лишь слегка замаскированными линейными соотноше-
ниями. Вот примеры некоторых из них:
Исходное рекуррентное соотношение
Линейный вариант
>п >п— 1 6гЩ-1
U = 7/й(2 ’l’ ге2
_L = -L-!
[n =
, ( 4 V
Последняя разновидность рекуррентного соотношения осо-
бенно часто встречается при анализе алгоритмов типа «раз-
деляй и властвуй».
2.2,3. Дважды экспоненциальные последовательности
В предыдущем разделе были исследованы нелинейные ре-
куррентные соотношения, которые содержали в себе скрытые
линейные зависимости. Обратимся теперь к несколько иной
ситуации, когда нелинейное рекуррентное соотношение со-
2 Зак. 259
34
2. Рекуррентные соотношения
держит очень хорошее приближение к линейной рекуррентной
зависимости.
Удивительно большое число нелинейных рекуррентных со-
отношений может быть подогнано под соотношение типа
*п+1 = х’ + ?„. (2.72)
где gn — медленно возрастающая функция п, возможно зави-
сящая от предыдущих элементов последовательности. Более
точные требования к функции gn станут ясны по мере нахож-
дения решения уравнения (2,72); при этом мы будем следо-
вать статье Ахо и Слоана |73].
Начнем с того, чго прологарифмируем уравнение (2,72),
получая почти линейное соотношение
Уп+1 ~ ^Уп. + (2.73)
где Хп и gn заменены на
Z/« = lnxtt (2.74)
и
+г„/4)- (2-75)
Используя логарифмы, мы тем самым делаем наше первое
допущение, состоящее в том, что хп больше нуля.
Если «развернуть» рекуррентное соотношение для уП) то
получим
У» = 2“(</<, + т- + >+ ••• +-^)- (2.76)
Далее удобно расширить ряд с а/ до бесконечного:
1'п = 2“й+ £ 2"-'-'а(> (2.77)
1=0
так что
r„ = Y„~y„= Ёг’-'-'а,. (2.78)
Подобное расширение полезно только тогда, когда ряд
быстро сходится. Поэтому мы принимаем второе допущение:
функция gn такова, что
|ав1>|ап+1| при (2.79)
Благодаря второму допущению ряд для сходится, а оста-
ток | Гп | не превосходит | ап |; поэтому, потенцируя, можно
получить решение исходного уравнения:
= = й2 . (2.80)
2.2. Нелинейные рекуррентные соотношения
35
где
k = х0 exp I X 2 1 [а(-
\г=и
(2.81)
Поскольку а/, как правило, зависят от хг-, равенство .(2.80)
не является решением в полностью замкнутой форме. Тем не
менее данное решение показывает, что существует константа
Л, возможно трудная для вычисления, которая характеризует
последовательность хп- В некоторых случаях можно устано-
вить значение k точно.
Любопытной стороной равенства (2.80) является близость
сомножителя k2n к точному решению (как мы вскоре увидим,
множитель е~Гп дает пренебрежимо малый вклад), Для того
чтобы показать это, необходимо принять третье допущение:
lgnl<Tx« и ПРИ (2.82)
Поскольку | гп | -С I «л I, то имеем следующую оценку близости
Х„ = &2 к точному решению:
(2.83)
Раскрывая правую часть этого неравенства (используя нера-
венство (1 — u)-1 1 + 2и при 0 и 1/2 в случае, когда
ап<0, и последнее допущение), получаем новую оценку:
Х„<хя + -^Л. (2.84)
лп
Аналогично
Х„>жяе-|“»1>Хп/'1—Ы.. (2.85)
\ X I X
\ п z лп
Окончательно допущение о том, что | gn 1 < -^-хп, позволяет
утверждать, что
(2.86)
Значит, если известно, что хп — целые числа, то искомое ре-
шение таково:
хп = ближайшее целое к яг при п п0. (2.87)
Вот некоторые рекуррентные соотношения, которые вписы-
ваются в общую схему — уравнение (2.72).
1) Нелинейные рекуррентные соотношения Голомба
Un+i = У$У± • * • Уп+п Уч “ (2,88)
36
2, Рекуррентные соотношения
или, в эквивалентной форме,
Уп+1 = (Уп — г)Уп + г, у0=С V, = г + 1. (2.89)
Если с помощью подстановки
^п = Уп — (2-9°j
выделить квадрат,
*»+i = + Т-Т’ <2'91>
то становится очевидным, что данное рекуррентное соотноше-
ние является членом только что рассмотренного семейства
соотношений. Поскольку член, соответствующий есть кон-
станта, легко проверить, что принятые выше допущения про-
ходят и в этом случае.
Известно, что в частных случаях г = 2 и г ~4 константа
k равна д/2 и величине «золотого сечения» соответственно,
В других случаях эту константу можно оценить, итерируя
рекуррентное соотношение и разрешая его относительно k.
Дважды экспоненциальный порядок роста элементов после-
довательности обеспечивает быструю сходимость таких оце-
нок, но вместе с тем делает неточными оценки далеких чле-
нов последовательности.
2) Сбалансированные деревья, Следующее рекуррентное
соотношение, приведенное в книге Кнута [III, разд. 6.2,3],
связано с подсчетом числа сбалансированных бинарных де-
ревьев высоты п:
Уп+1 = У2 + ^УпУ„-Г (2.92)
Если сделать преобразование хп = уп + Уп-\, то рекуррентное
соотношение станет менее простым, но зато более удобным
для решения:
*л+1 = ^+2»«-Л-2- (2.93)
В данном случае член, соответствующий gn, не является кон-
стантой, но возрастает достаточно медленно (2y„_[_i/„_2
С уп < х«), что удовлетворяет требованиям, наложенным
выше на gn. Теперь можно утверждать, что существует такое
k, что
хп = L fe2" J (2.941
и
sB-L**“j-Le“-,J+... ±L4JTl. (2.95)
2.2, Нелинейные рекуррентные соотношения 37
(Использование функции -гпол» вместо ближайшего целого
оправдано тем, что gn, будучи положительным, всегда делает
k несколько большим, чем истинное значение,)
Завершим раздел двумя рекуррентными соотношениями,
фигурирующими в статье Ахо и Слоана [73]:
Уп+, = А~3^ (2.96)
Уп+1 ~УпУп~1 + !• (2.97)
Строго говоря, эти соотношения не вписываются в схему ре-
куррентного соотношения, решенного в начале данного раз-
дела. Однако изложенная при этом техника решения в равной
степени применима и к этим соотношениям, поскольку после
логарифмирования оба рекуррентных соотношения становятся
близкими к линейному. В частности, уравнение (2.97) имеет
решение фибоначчиевого типа:
= (2.98)
где Fn^Fn_l + Fn_2.
Глава 3
Операторные методы
Последующий анализ хеширования, принадлежащий
Майклу Патерсону, но ника не опубликованный, опирается
на дна понятия: собственные операторы и то, что он назы-
вает «индукцией с другого конца». Приводимый ниже пример
с монстром — пожирателем печенья иллюстрирует пользу на-
хождения собственного оператора. «Индукция с другого кон-
ца» появится позже, когда эти методы будут применяться к
различным схемам хеширования (по поводу последних см,
также Кнут [III, разд. 6.4]. — Перев>).
3.1. Монстр — пожиратель печенья
Рассмотрим монстра, способность которого поглощать пе-
ченье пропорциональна его текущему объему. Когда мы швы-
ряем ему печенье, а монстр уже имеет k печений в своем
брюхе, с вероятностью pk объем монстра увеличивается до
k 1. (Мы предполагаем, что pk I,)
Пусть gnk является вероятностью того, что объем монстра
равен k после того, как на съеденье было отдано п печений.
Образуем производящую функцию
§П (^) §nkf (3.1)
й
которая соответствует распределению объема монстра после
n-го швыряния печенья. Первоначально монстром было ка-
ким-то образом съедено одно печенье, так что goU) — х,
Некий «оператор» будет обеспечивать возможность полу-
чения £м-1(*) по заданной функции gn(x). Сначала посмот-
рим, как воздействует печенье на отдельное слагаемое:
До После
xk pkxk+] + (I - pk) xk
или xk -p P (* — I) kxk
Это изменение описывается оператором Ф == 1 +р(х—1)х7Э,
где D — производная. Многократное применение Ф дает
3.1, Монстр — пожиратель печепьй
39
Прежде чем двигаться дальше, полезно дать обзор неко-
торых фактов об операторах. При этом будем использовать
следующие обозначения:
D — производная,
U — вычисление в точке х = 1,
/—вычисление в точке х =0,
UD— получение среднего значения f(l),
Un — сокращенное обозначение для UDn}
хп — умножение на хп.
Важно представлять, как операторы коммутируют друг с
другом. Например,
Dxnf (х) = nxn~lf(x) + xnDf (х); (3,2)
поэтому можно переместить оператор D за хп по правилу
Dxn — xnD + /гх"'1. (3.3)
Это правило обобщается на произвольный многочлен r(x)i
Dr (х) ~ г (х) Dг'(х). (3.4)
Другим полезным фактом, касающимся операторов, является
соотношение
UnX = Un + nUn^ (3.5)
или
ип(х-1) = пип^. (3.6)
Это может быть показано перестановкой х с каждым из опе-
раторов D в Unx.
Возвращаясь к монстру — пожирателю печенья, хотелось
бы установить средний объем монстра после п швыряний пе-
Ui§n (х) = /71Ф^0(х). (3.7)
Вот где важна перестановочность, поскольку было бы заман-
чиво иметь возможность поместить U\ после Ф. Применение
кФ дает
UD® = UD (1 + р (х - 1) xD) =
= щр + р(х- 1)х£»2 + р(2х- 1)/)) =
— (l-\-p)UD. (3.8)
Значит, UD является собственным оператором оператора Ф,
и в силу подобной самовоспроизводимости можно вычислить
среднее значение:
(*) = (!+ РГ (х) = (1 + рЛ (3.9)
40
3. Операторные методы
Дисперсия устанавливается с помощью £/2> поскольку
var (g) = g"(l) +/(1) — (g'(l))2 н U2gn (х) = g"(l). К сожа-
лению, Сд не имеет такого привлекательного достояния, как
собственный оператор, которым обладает £Л, поскольку
6'2Ф — U(D2 + p(x- 1) х£)3 + 2р (2х — 1)£>2 + 2р£>) =
= UD2 + 2pUD2 + 2pUD =
= (1 + 2р) U2 + 2р/7г (ЗЛО)
Тем не менее, используя подходящую линейную комбинацию
U2 с U\, мы все же получаем собственный оператор:
(U2 + 2UJ Ф = (I + 2р) (U2 + 24/,). (3.11}
На самом деле существует целое семейство собственных опе-
раторов, задаваемых следующей схемой:
7,Ф = (1 +р) Н, =
72Ф = (1 + 2р) V2, V2 = U2 + 24/,,
У3ф = (1 + Зр) V3, Из = + 64/ j,
И„Ф = (1 + np) Vn, И„ = Unxn~l.
Это можно показать с помощью соотношений (3.6) и (3.3)1
И„Ф = (1 + р (х - 1) xD) =
“ 1/„ + 4/„р(х — 1)хиД =
= Vn + pnUn^ (Dx11 — пхп-') =
» Vn + рп (Unx — х"-1 =
= ИпЛ-р/гИй. (3.12)
Используя Vi, в принципе можно вывести все моменты рас*
пределения и более высоких порядков, В частности, дисперсш
вычисляется с помощью V2:
И2Ф^0 (х) = (1 + 2р)п у2х = 2(1 + 2р)й,
£72Ф^о (х) = (И2 - 27J Ф^о (х) = (3.13:
= 2(1 + 2р)« - 2(1 +/>Л
так что
var(g„) = ^(l) + O)-(g;(l))2 =
= 2(1 4- 2р)" - (1 4- р)" - (1 4- рр.
3.2. Срастающееся хеширование
Минутное размышление подсказывает, что поведение мой
стра—пожирателя печенья очень тесно связано с определен
3.2. Срастающееся хеширование
41
ным видом хеширования. Когда возникает коллизия ключей,
образуется длинная цепочка, и возможность попадания в нее
возрастает. Предположим, что мы разрешаем коллизию, на-
ходя первое свободное место на левом конце таблицы н свя-
зывая это место с концом цепочки. По мере выполнения алго-
ритма мы будем иметь распределение монстров различного
объема. Пусть
gn(x)=Yi (среднее число цепочек длины A) *xfe. (3.14)
Хотелось бы снова найти оператор, который описывает при-
бавление одного печенья, но на этот раз мы думаем о клю-
чах, а не о печенье.
Поскольку мы имеем дело со средними значениями, общий
член (3.14) будет вести себя подобно одному монстру, хотя
вклад в него вносят несколько монстров. В данном случае
р=1/т, где т —число «щелей» (slots. — Переа.} в хеш-таб-
лице. Поэтому вероятность увеличения цепочки длины k до
k + 1 равна рА-вероятности попадания в цепочку. Однако
вычисление свободного члена в производящей функции пре-
подносит новые трудности. Среднее число пустых цепочек
попросту равно т — п, поэтому оператор должен быть таким:
Т = ф + (некий свободный член к tn — п). (3.15)
Вместо того чтобы строить догадки, заметим, что оператор Ф,
примененный к свободному члену функции gn (х), есть
Ф(л?— п) — т — п. Следовательно, правильное изменение
должно быть таким:
До После
т — п (т — п — 1) -|-
-|- (1 — пр) х
Можно подправить Ф, используя оператор вычисления в
нуле Z:
Т = Ф + р(х- l)Z-pt/p (3.16)
Заметим, что Z, примененный к gn(x), дает т — п, a Ui дает
п, поэтому Y действует на свободный член надлежащим об-
разом:
lF(/?? — п.) — т — п + р (х — 1) (т — п) ~ рп —
— п —m — mp + (l —пр)х. (3.17)
(Напомним, что тр = 1.) Использование Z и U\ в этой стряп-
не вначале может показаться подобным «стрельбе из пушек
42
3. Операторные методы
по воробьям», но здесь важно то, что данное изменение сде-
лано исключительно с помощью линейных операторов.
Итак, grt(x) задается формулами
Я„(х) = Г£|((х}, ga(x) = m. (3.18)
Как и прежде, попылаемся найти собственный оператор опе-
ратора Т; применение L'i к Т даст
С/Лг -- <1 + + (3.19)
Систематического способа нахождения собственных операто-
ров не существует, но присутствие Z подсказывает попытаться
так:
ZT = (1 -p)Z~pUit (3.20)
Теперь видно, что следующая линейная комбинация является
собственным оператором:
(Г, + Z)Y = (<Л + Z). (3.21)
«Среднее» в этой задаче не особенно интересно, поскольку
применение оператора Ui к gn(x) дает просто п, и собствен-
ный оператор только подтверждает этот факт:
+ (3.22)
Zgn (х)---=т — п. (3.23)
Напротив, сила собственного оператора проявляется в случае
вычисления среднего числа коллизий при (пф-1)-й вставке,
Пусть
hn(x) = X (вероятность k коллизий при (пф- 1)-й вставке) х*.
k
(3-24)
Член xk в grt(x) будет давать (xfe ф- х^1 ф- ... фх)р в йфх),
поскольку попадание в каждый элемент ^-цепочки равно-
вероятно, несмотря на то что они находятся на разном рас-
стоянии от конца цепочки.
Мы хотим вычислить U^hn(x)t исходя из gn(x). Применяя
Ur+i к многочлену и не церемонясь со свободным членом,
получаем
гг+1О4+1) = г,+1О‘+1-1) =
= <7г+,(х- 1)(1 + х+ ... +/) =
= (/•+ 1)(7Д1 + х + ... +/) =
= (г + 1) U, (х + хг + ... + Xs)- (3.25)
(Подобные вольности оправданны, поскольку мы применяем
U к полиномиальному аргументу а не переставляем U
3.2 Срастающееся хеширование
43
с оператором как в уравнении (3,3).) Полагая г = 1, по-
лучаем зависимость между g и h:
UMx) = -^U2xgM- (3.26)
Поскольку U2x — U2 + 2L/j, a легко вычисляется, попыта-
емся теперь найти собственный оператор оператора Ф1, кото-
рый содержал бы V2. Вот подходящее семейство собственных
операторов:
С2Т = (1 + 2р)С2, C2=V2-|(£/,-Z).
С3>К = (1 + Зр)Сз, C3 = V3-|(l/,-2Z).
СЛ = (1 + пр) с„, c„ = vn — (и, _ _ 1) Z).
Это семейство позволяет найти все моменты распределения
коллизий, неизбежных при вставке (^4-1)-го элемента. На-
пример, среднее число коллизий выводится с помощью опе-
ратора С2:
УЛ(х) = -^-(C/a+2l/1)g„(x) =
-f(c2+^-A)e„w=
=^((1+1)т~г + л)- (3'27)
Читатель, должно быть, заметил, что в предыдущем ана-
лизе не учитывалось время, необходимое для нахождения пер-
вой свободной ячейки на левом конце массива. Предположим,
что алгоритм хеширования использует указатель, который по-
зволяет следить за последней, бывшей до этого свободной
ячейкой. При каждой коллизии указатель передвигается впра-
во до обнаружения новой свободной ячейки.
Этот алгоритм моделируется следующей игрой, которая
начинается с пустого массива и указателя на нуль. Игра тре-
бует п «/?-шагов», после выполнения которых вычисляется
расстояние от указателя до ближайшей свободной ячейки.
Когда имеется i незанятых ячеек, «/?-шаг» с вероятностью pi
занимает пустую ячейку и с вероятностью 1—pi — самую
левую свободную ячейку. Второй случай соответствует кол-
лизии, при этом указатель устанавливается на только что за-
нятую ячейку. Окончательный счет игры — расстояние между
указателем и ближайшей свободной ячейкой — дает стоимость
нахождения пустой ячейки при будущей коллизии,
44
3. Операторные методы
Воспользуемся еще раз производящей функцией. Пусть
Gmn(z) есть
£ (вероятность того, что счет равен k для массива
размера т после п /?-шагов) г*. (3.28)
Будем искать оператор для построения Gmfh рассматривая
задачи меньшего размера и используя «индукцию» другого
типа. Предположим, что имеется последовательность Алпатов:
3 1 4 С 7
Числа означают занятые ячейки, а С символизирует колли-
зию, когда занимаемся самая левая свободная ячейка и на
нее устанавливается указатель. Каждая такая последователь-
ность шагов встречается с некоторой вероятностью и приво-
дит к некоторому счету, как определено выше.
Вместо того чтобы добавлять новый элемент в конец по-
следовательности, будем помещать его в начало — отсюда
выражение «индукция с другого конца». Точнее, будем до-
бавлять новый ключ н новую ячейку к массиву. Ключ может
быть вставлен в старый массив где угодно, поэтому можно
К ' А ( 1 3
рассматривать это как добавление элемента /г е , -5-, ...
2т + 1 М
.... —2—1 | в начало последовательности с ее перенуме-
рацией для того, чтобы снова сделать последовательность
целой.
Например, рассмотрим указанные выше /?-шагн и предпо-
ложим, что размер массива ?п=7. Когда происходит колли-
зия С, ячейка 1 занята, так что занимается ячейка 2, В конце
игры ближайшей свободной ячейкой оказывается 5, поэтому
счет равен 3. Ниже перечислены возможные изменения в за-
висимости от того, какой новый Л*-шаг мы помещаем в на-
чало последовательности.
Вероятность Новый начальный элемент Получающаяся последователь- ность Счет
Р 1 425С8 3
Р 2 415С8 3
Р 3 . 415С8 4
Р 4 315С8 4
Р 5 314С8 4
Р 6 314С8 3
Р 7 314С8 3
Р 8 314С7 3
1 — 8р С 425С8 3
Как это будет влиять на окончательный счет? Счет равен
длине области между указателем и ближайшей свободной
3.3, Открытая адресация: равномерное хеширование
45
ячейкой. Если новый ключ вставляется в эту область, счет
увеличивается на единицу; в противном случае счет остается
неизменным. Поскольку вероятность попадания в эту область
пропорциональна ее размеру, монстр — пожиратель печенья
поднимает свою безобразную голову и с помощью знакомого
оператора Ф поглощает остаток этого анализа:
= (3-29)
3.3. Открытая адресация: равномерное хеширование
Внесем небольшое изменение в предыдущую игру. Вместо
/?-шага будем использовать Т-шаг, который наугад заполняет
пустую ячейку и устанавливает указатель на левый конец
массива. Окончательный счет равен расстоянию от левого
конца массива до первой свободной ячейки.
Поводом для этой новой игры является несколько нереа-
листическое предположение, что каждый ключ обладает слу-
чайной перестановкой последовательности проб. Ключ сле-
дует своей последовательности проб, пока не находит пустую
ячейку. Это допущение, обычно называемое «равномерным
хешированием», будет уточнено позже при обсуждении «вто-
ричного скучивания».
Хотелось бы установить среднее число записей, с которыми
должен быть сверен (л + 1)-й элемент в своей последователь-
ности проб. Без потери общности можно считать, что в каче-
стве последовательности проб этот элемент имеет последова-
тельность 1, 2, 3, переупорядочивая, если необходимо,
массив так, чтобы это стало справедливым. Тогда для вставки
(л 4- 1)-го элемента требуется найти самую левую свободную
ячейку, и это равно счету описанной выше Т-шаговой игры.
Используя «индукцию с другого конца», мы снова натал-
киваемся на монстра. На этот раз ои занял ячейки в начале
массива. Тем не менее следует быть внимательными по отно-
шению к вероятности р: вероятность попадания в данную
ячейку равна \/т, поэтому оператор Ф есть
Фт=1+^-(*-1)*0. (3.30)
Вспомним, что «индукция с другого конца» добавляет как
новый ключ, так и новую щель в массив, так что эта вероят-
ность меняется и мы должны параметризовать оператор Ф
индексом т.
В случае параметризованного оператора производящая
функция для объема монстра задается формулой
= ... Фот_п+1х. (3,31)
Операторы Vj и Уг по-прежнему являются собственными опе-
раторами; они дают произведения, которые замечательно сво-
46
3. Операторные методы
рачиваются. Например, среднее число проб, используемых
для вставки (п ф- 1)-го элемента, есть
W = 0 + ’фр) (1 + ТГ^т) • • • 0 ~ + 1 ) =
А поскольку вес V, сворачиваются, вот вам систематический
способ вычисления среднего и дисперсии числа проб, необ-
ходимых для вставки (п + 1)-го элемента,
3.4, Открытая адресация: вторичное скучивание
В модели вторичного скучивания каждый ключ отобра-
жен в единственное хеш-значение, и это хеш-значение до-
ставляет случайную перестановку последовательности проб.
Вместо того чтобы каждый ключ имел свою собственную слу-
чайную последовательность проб, ключи разделяют последо-
вательности проб с теми ключами, которые отображаются в
то же самое хеш-зиачение. Хеш-значения и последователь-
ности проб по-прежнему являются случайными, но общ-
ность последовательности проб делает коллизии более вероят-
ными.
На этот раз игра, в которую мы играем, содержит S-npa-
вило: если самая левая ячейка не занята — используется пра-
вило SO, в противном случае — правило S1. По правилу SO
пустая ячейка занимается наугад. Правило S1 включает вы-
бор; с вероятностью р занимается самая левая пустая ячейка
и с вероятностью q = 1—р наугад занимается любая пустая
ячейка.
S-правило охватывает явление вторичного скучнвания. Без
потери общности можно предполагать, что каждый ключ, по-
падающий в крайнюю левую ячейку, имеет последователь-
ность проб 1, 2, 3, ... . Тогда по правилу S1 с вероятностью
р мы хешируем до крайней левой ячейки, повторно исполь-
зуем ту же самую хеш-последовательность 1, 2, 3, ... и зани-
маем самую левую пустую ячейку.
Счетом игры является расстояние до первой свободной
ячейки и имеются две «производящие счет» функции для этих
двух правил: Нтп(х) для правила SO и для правила
S1. Рассмотрим вначале функцию Gmn(x):
Gmn (х) = (рх + <7Ф) (х). (3.33)
Оператор для G устанавливается с использованием «индукции
с другого конца». С вероятностью р ключ вставляется в по-
зицию 1 и увеличивает объем монстра иа единицу; с вероят-
3.4. Открытая адресация: вторичное скучивание
47
иостью q мы играем в прежнюю игру «монстр — пожиратель
печенья», присоединяя ключ наугад.
Существует тонкое различие между вероятностями в этом
операторе: вероятность р зафиксирована в \/т л,о индукцион-
ного шага и остается фиксированной при уменьшении т.
Однако оператор Фте параметризован индексом т, так что
вероятность в этом операторе увеличивается с уменьшением
т. Данное различие является именно тем, что нам надо, по-
скольку вероятность разделения новым ключом одной и той
же последовательности проб с определенным старым ключом
зафиксирована в \/т на протяжении всего процесса.
Величина = рх Д- дфт в (3.33) не имеет собственного
оператора, но имеет «скользящий» оператор
|)£/0)Яго = (1 (3.34)
Скользящий оператор Am—U[— mUQ изменяет свой пара-
метр на единицу, когда он переставляется с а если тре-
буется вычислить СУ], подобное обстоятельство так же ценно,
как и наличие собственного оператора:
W = (' + Д) (* + m!_ | '
•••(1+^Д+т)^-«Л (3.35)
о».»w=(i + Д) (i + ।) • •
•••(» + + 1 )(»-'") + И - »)• (3-36)
Теперь можно обратить свое внимание на функцию Нтп(х)
и правило SO. Пока первая ячейка не занята, ситуация схожа
с поведением монстра. Как только достигнута первая ячейка,
мы переключаемся на Gmn(x). Используя «индукцию с дру-
гого конца», получаем рекуррентное соотношение
^тп (-*) == /х—I (%) т-1, п-1 (-О Н“
{3.37)
Средний член соответствует ошибочному использованию Я
оператором Фт в случае занятой первой ячейки.
Поскольку игра начинается с правила SO, функция Нтп
является требуемой производящей функцией для всей игры, и
48
3. Операторные методы
хотелось бы найти среднее значение UtHmn(x):
utnmn(X)=h +4-) +
+ = G,(3.38)
Аналогичное рекуррентное соотношение для Gmn может быть
выведено из уравнения (3.34):
(х) — (j + Л~1 + Р- (3.39)
Сложившаяся ситуация требует нового операторного трюка.
Заметим, что линейная комбинация Н и G воспроизводит
себя:
Щ (Нт - у Gm„) = и, - 3. Gm_, n_i) _ JL. (ЗЛО)
К тому же член p/q не зависит от т. Поэтому
Ut (нтп - Л G„„) = и, 0 - у G„_„. о) - . (3.4 Г)
При заданных граничных условиях Нт10 = Gm, о = х и ранее
вычисленном G\Gmn можно определить
= 1 +j-(m-np + (n~m) ЭД (1 +-*-))• (3-42)
\ k=m—«4-1 z
(Интересно сравнить полученное решение с традиционным
подходом к хешированию из книги Кнута [III, упр. 6.4-44].)
Последний операторный трюк имеет сильное сходство с
собственными и скользящими операторами, которые исполь-
зовались ранее. Во всех этих случаях мы двигались по рекур-
рентной последовательности с помощью самовоспроизводя-
щегося процесса. Сила операторных методов заключается в
их способности скрадывать несущественные детали, так что
соответствующая самовоспроизводимость становится явной;
поэтому величины типа средних и дисперсий становятся срав-
нительно легкими для вычисления.
Глава 4
Асимптотический анализ
4.1. Основные понятия
Нельзя ручаться, что возникающие при исследовании алго-
ритмов суммы и рекуррентные соотношения будут иметь про-
стые решения в замкнутой форме. На самом деле азарт ана-
лиза алгоритмов во многом вызывается разнообразием мате-
матических методов, к которым (порой рыдая и стеная) при-
бегают исследователи в своих попытках разобраться в алго-
ритмах, Зачастую исследователи вынуждены обращаться к
асимптотическому анализу.
Цель асимптотического анализа состоит в нахождении хо-
рошего приближения к точному решению. Часто при боль-
ших значениях входящих в него параметров относительная
ошибка такого приближения становится малой. Мы будем
пытаться искать как можно более точное асимптотическое
приближение; например, гораздо существеннее знать, что
время выполнения некоторого алгоритма есть 3n2+7« + O(1),
а не просто О (и2).
Внимательное отношение к асимптотическим членам по-
лезно по нескольким причинам. Зачастую приближения схо-
дятся настолько быстро, что для подтверждения правиль-
ности своего решения исследователю достаточно проверить
лишь несколько первых приближений. В практических зада-
чах важно знать не только поведение главного члена реше-
ния; к примеру, 1.8 Inn+ 20 будет меньше, чем 2.01пп+Ю,
лишь при п > е50. Кроме того, погоня за дополнительными
асимптотическими членами обычно приводит к более общим и
мощным математическим методам.
Цель настоящей главы — ознакомить читателя с основным
аппаратом асимптотического анализа, в частности с О-оцени-
ванием и методами раскрутки и расчленения. Эта техника
будет бегло изложена в ближайших разделах. В последнем
разделе выводится один асимптотический результат; каждый
этап этого в целом трудного вывода демонстрирует основные
приемы асимптотического анализа.
Обозначения
Определение символа О (или <): говорят, что f(n)==
= O(g(n)) (или если существуют целые N а
Такие, что |f(n) |С Kg(n) при всех п N,
50
4. Асимптотический анализ
Символ й (или определяется в том же духе: f(n)~
— Q(g(/i)) (или /(ч) > g(n)), если существуют целые /V и
К, такие, что f(/i) -Э? Kg (л) при всех п №).
В случае, когда выполнены оба условия, соответствующее
отношение обозначается как f(fO = ©(g(rc)) или f(n)Xg(n}
(см. Кнут [76а]).
Для символа «о малое» имеются аналогичные определе-
ния. Так, например, говорят, что / (л) = o(g (ч)) (или
<g(n)), если Нпк—Л(/i)/g(и) = 0. Имеется также обозна-
чение для отношения эквивалентности: f(n) ~ g(n), если
lim^xJOO Л? (f0 — 1. Тем не менее мы будем стараться избе-
гать этих обозначений, поскольку в них не содержится ин-
формации о скорости сходимости к соответствующим преде-
лам. К примеру, мы будем отдавать предпочтение оценке
типа О(п-1/2) вместо более слабой оценки о(1).
4,1.2, Раскрутка 10)
Метод раскрутки полезен в тех случаях, когда анализи-
руемая функция удовлетворяет некоторому неявному урав-
нению. Последовательно подставляя в это уравнение асимп-
тотическое приближение к функции, полученное на предыду-
щем шаге, мы тем самым все время будем улучшать искомое
приближение. Вот пример из книги Де Брейна [701 •
= (4.1)
Это уравнение может быть переписано в виде
= In t - In fit}. (4.2)
Для «затравки» (prime the pump — Перев.) заметим, что
f(f)> 1 прн t > e. Учитывая это в уравнении (4.2), получаем,
что
/ (/) = О (In/). (4.3)
Подстановка этого приближения обратно в (4.2) дает более
точный результат:
f(f) = ln/-|-O(lnlnZ). (4.4)
Для дальнейшего улучшения полученного результата снова
подставим его в уравнение (4.2):
f(0 = ln/-lnln/-ln(l+o(-^y)) =
= In I - In In t + О (-^Jt^) • (4.5)
Продолжая подобное «раскручивание», можно получить иско-
мое приближение с любой степенью точности.
4.1, Основные понятий
51
4.1.3. Расчленение
Метод расчленения применяется главным образом к сум-
мам и интегралам. В типичной ситуации область суммирова-
ния является большой, а выражение под знаком суммы
состоит из нескольких компонент. Никакая из компонент сла-
гаемого не является малой на всей области суммирования,
но если область «расчленить» на части, то каждая часть
суммы станет (по разным причинам) малой и таким образом
показывается, что в целом сумма также мала.
Продемонстрируем технику расчленения на примере
суммы
н«)= У —Цг- <4-6)
3< а С п/2
Разобьем область суммирования на три интервала. Сумма по
первому интервалу, 3 d 8, меньше, чем
Е <4-7>
Обратите внимание, что буквы d в исходной формуле заме-
няются на 3 и 8 в зависимости от того, какое из этих значе-
ний приводит к большей величине слагаемого. Так как число
слагаемых фиксировано, то сумма ограничена величиной по-
рядка О(п~3). _
На втором интервале, переменная d также
заменяется ее экстремальными значениями, так что в этом
случае сумма меньше, чем
X (4-8)
8< d < V«"
Здесь О (п 4 д/й) есть результат суммирования О(д/«) чле-
нов, порядок каждого из которых не превышает О(гг*).
Сумма, вычисленная по последнему интервалу, л/п
С d н/2, совсем мала, поскольку она меньше, чем
(4.9)
Объединяя результаты для каждого из трех интервалов, по-
лучаем, что в целом f(n) есть О (я-3).
Из рассмотренного примера видно, что самое трудное в
методе расчленения — это выбор интервалов, В частности,
выбранные нами границы второго интервала 8_и д/« не яв-
ляются «неприкосновенными»—выбор Ю и 'у/п столь же хо-
52
4. Асимптотический анализ
рош. Тем не менее выбор 8 и уп-—это своего рода искус-
ство, требующее проникновения в характер поведения слагае-
мых па всей области суммирования.
4.1.4. Пределы пределов
Случается, что асимптотический анализ приводит к двум
и более предельным переходам. При этом часто важен поря-
док пределов, и полезно знать, когда возможна их переста-
новка. В простом случае, типа
от г»о
Е Е атп, (4.1о)
Л =Н -= J
абсолютная сходимость последовательности атп позволяет как
угодно переставлять ее члены; например, можно вначале сум-
мировать по /I, а затем по т.
Позже в данной главе нам придется менять порядок преде-
лов в более деликатных ситуациях. В частности, нам потре-
буется обращение следующей теоремы.
Абелева теорема. Если
Нт Е <Ц — А,
п-+<х> Л=0
ТО
п
lim lim Е А.
г-> I гг-> оо k=Ci
(Здесь в дальнейшем предполагается,, что г стремится к еди-
нице снизу.)
Однако обратное утверждение справедливо не всегда.
Не-теорема, Если
lim lim Е akzk==A,
г->1 n->oo й-О
ТО
lim Е ak — А
П->оо <> = (}
Де Брейн [70] в своей книге Асимптотические методы в
анализе приводит следующий контрпример. Пусть
Нг)=4т7 = 1-2г + 2г2-2гэ+ .... (4.11)
и обозначим через а* коэффициенты разложения функции
f(z) в степенной ряд. Этот ряд сходится абсолютно внутри
4.1. Основные понятия
53
круга единичного радиуса с центром в начале координат, и
lim f (z) = 0. (4.12)
Z->1
Тем не менее частичные суммы
41 + ^1+ + ап = (—О'1 (4.13)
к нулю не сходятся.
Таубер предложил дополнительное требование, гаранти-
рующее обращение теоремы Абеля. Его условие состояло в
том, что коэффициенты а* должны быть порядка о(&-1).
Позже Харди и Литлвуд ослабили это условие до а* > —Ck~}
при некотором С > 0, но теорема по-прежнему именуется
тауберовой в силу ее общего характера: тауберовы теоремы
дают условия обращения абелевых теорем.
Тауберова теорема. Если
п
lim lim У, akzk = А
2->1 П-*оо k—0
и если ak>— Ck~[ при некотором С>0, то
Ит £ ^ = Л.
Собрание более глубоких тауберовых теорем содержится
в книге Харди [49].
4J.5. Сводка полезных асимптотических разложений
В приведенных ниже асимптотических формулах п стре-
мится к бесконечности, а е — к нулю.
W» = ln« + v--^--^r+O(«-4). (4.U)
(Напомним, что Нп~ — РедЛ
i с п '
«' = V2^ (4)41 + ^г+28к+0 ("”))’ <4-15»
1п(1+в) = Е-4 + 4+ ••• +(-!)''4-+ О (е<+1), (4.16)
[ В (Л)~в .
п I — • , ,—1211 при целых z, п > 0,
£*' = ! ж , (4-17)
|tm+4 + 2V+°0‘-!) при ,->1.
4. Асимптотический анализ
{Здесь Bt(x) и Д — соответственно многочлены и числа Бер-
нулли; см. разд. 4.2.2,)
(Последнее соотношение устанавливает «точку поворота»
для сумм: сели е — О, то coojbcici вующих сумм не суще-
ствует. Например, ряды
k 1 <Zj А‘ hi А A’ l:t k In In k
расходятся.)
Имеется несколько способов получения грубых оценок.
Один из них состоит в замене пмм их интегральными ана-
логами. В разд. 4,2.2, посвященном формуле суммирования
Эйлера, мы выясним, когда возможна подобная замена и как
можно уточнить получаемый при этом приближенный резуль-
тат, Другой способ получения грубых оценок применим к
случайной величине X со средним значением ц и дисперсией
а2: неравенство Чебышева утверждает, что
Вер(|Х-и|>/Хо7^
(4.19)
В разд, 4.3.3 будет подробно рассмотрен случай, когда X яв-
ляется суммой независимых случайных величин.
4.1.6. Пример
Обратимся теперь к задаче вычисления вероятности того,
что многочлен степени п разложим на неприводимые множи-
тели попарно различных степеней, рассматриваемых по мо-
дулю большого простого числа р,— задаче, которая встре-
чается при анализе некоторых алгоритмов разложения на
множители (Кнут [II, разд. 4,6,2]). Вероятность того, что
многочлен n-й степени сам неприводим по модулю р, равна
±+О(р-»Д. (4.20)
(Этот результат фигурирует в качестве упр. 4.6.2-4 во втором
томе Искусства программирования для ЭВМ Д. Кнута.) Ве-
личина модуля р не представляет интереса, поэтому устремим
р к бесконечности и примем 1 /п из предыдущей формулы в
качестве основы для рассмотрения более трудной задачи
разложения многочленов на миожители различных степеней.
Решение этой задачи основано на использовании одной
производящей функции для разбиений. Искомым решением
4.1, Основные понятия
55
(т. е. вероятностью разложения на сомножители) является
коэффициент при zn в производящей функции
Л(г)=П(1+4)- (4'21)
Для того чтобы показать это, заметим, что если hn— коэффи-
циент при гк, то hnzn будет суммой членов вида
г^1 z2 zm
О й 1т
(4.22)
где все й> i2, ..., im различны между собой. Каждый член
вида (4.22) соответствует разбиению числа п на различные
слагаемые й> й, ..., im. Предположим, что мы собираемся
представить многочлен степени п в виде произведения много-
членов, имеющих степени й, й, •••> im. (Считается, что как
эти «малые» многочлены, так и «большой» многочлен норми-
рованы; впрочем, значения старших коэффициентов ие
влияют на последующие результаты.) Всего имеется р1’ мно-
гочленов степени й, из которых pZ|/Zj неприводимы. Подсчи-
тывая аналогичным способом число неприводимых многочле-
нов других степеней, получаем общее число
р1' /й р1,п рп
й й >tn
(4.23)
многочленов с неприводимыми множителями соответствую-
щих степеней. Поскольку всего имеется рп многочленов сте-
пени п, это означает, что величина
1
‘ irn
(4.24)
из выражения (4.22) является вероятностью разложения мно-
гочлена на неприводимые составляющие соответственно сте-
пеней i}, Й» . • ,
В целом hn состоит из всех возможных разбиений, каж-
дое из которых вносит вклад вида (4.22), и поскольку эти
события между собой не пересекаются, то нх вероятности
суммируются. Таким образом, коэффициент hn в производя-
щей функции h(z) действительно является вероятностью
того, что многочлен степени п разложим на неприводимые
множители различных степеней.
Однако производящая функция (4.21) не позволяет выра-
зить Лм в замкнутом виде, и, скорее всего, это и невозможно.
Поэтому попробуем найти асимптотическое выражение для
hn при л->оо. Логарифмируя А (г) и разлагая каждый лога^
56
4. Асимптотический анализ
рифм в ряд, получаем
Л(г>=ехр(£(4-<+^-•••)) <4-25>
При z <Z I этот ряд сходится абсолютно, что позволяет про-
изводить необходимую перестановку его членов. Наша стра-
тегия будет состоять в выделении больших членов из начала
ряда с последующим раздельным суммированием полученных
рядов. Начнем с выделения членов г* }k-.
4+ Г (—+ ••)) = 7^7
\k > 1 k 1 /
(4.26)
где
g(z) = expf £(-< + <-..•)} Н.27)
Xfe >3 /
В этих обозначениях h„ является частичной суммой коэффи-
циентов gi в разложении g(z):
Л„ = £ gt. (4.28)
о < j < n
Как мы увидим позже, к й« применима тауберова теорема;
следовательно,
.'™ * - S • W - ( Е (" -Jr + -SF - •)) -
4)-т))-
— exp (lim (In (n + 1) — Яп)) = c-v. (4.29)
Таинственно появившаяся здесь константа у — это постоянная
Эйлера из асимптотики для гармонических чисел
Нп In п + у -f- + О (л~2). (4.30)
Впрочем, действительная тайьа кроется в том, насколько
быстро hn сходятся к «странней» постоянной е~\ Для уста-
новления скорости сходимости тауберова предельная теорема
не особенно полезна. Следовательно, необходимо выделить
еще один член ряда из равенства (4.25) и продолжить более
детальный анализ:
= (4.31)
4.1. Основные понятия
57
(1 V'' * \
L PJ’
z v-i (z3S 2« Ч\ (4-32)
?(г) = ехр( X (-Ь-^г+ ••))•
Вначале возьмемся за функцию р(г),
р'(г) = р(г)(-4 £-4-Y (4-33)
\ /
и выведем рекуррентное соотношение для ее коэффициентов:
-2«Р"= Z Н-34)
0< k<n
Имея это неявное уравнение, можно воспользоваться методом
раскрутки и получить хорошую оценку для рп. В качестве
«затравки» выберем —0(1) (справедливость этой оценки
легко проверить по индукции). Подставляя это грубое при-
ближение в уравнение (4.34), имеем
-2"р»= Е <4-35>
О С k<.n
и, заменяя правую часть равенства (4.35) на O(logn) —
асимптотику гармонических чисел, — получаем улучшенную
оценку для рп-
(4.36)
Еще одно повторение «раскрутки» дает оценку
Р» = 0(-^у. (4.37)
На сей раз полученная оценка рп достаточно хороша для
того, чтобы приступить к расчленению суммы в уравнении
(4.34). Хотелось бы иметь в асимптотическом выражении для
рп ие только 0-член; поэтому выделим доминирующую часть
ряда в виде, удобном для суммирования:
-2пр„= £ 2 p*G=*-t) =
О fe <fi 0<;&<n
=тЕ P‘~v X Р‘X P‘Gt=t)-
OCk<fl
=±р(1)_1 у 0 f>2|iy + ± у =
П r v n L—i \ k / 1 П Z-J \ ft (n — k) J
= e”1712 + ° (—J—) (4.38)
5в
4. Асимптотический анализ
На последнем шаге мы вычислили р(1), суммируя ряд
<4'39)
I
второй член, X О (log оценили посредством его инте-
k и
трального аналога
= (4.40)
п
и, наконец, последнюю cxmimv мы вычислили с помощью эле-
ментарных дробей:
У (dog^y—I ) =
Z_i \ k (п — А) ) х ь ! L~i k (л — k) )
k<n
= + • )) =
V n £—i\k 1 n — kJ)
= e(M). (4.41)
Возвращаясь к равенству (4.38), имеем уточненную оцен-
ку Рп: Mi
р.-^ + о(^)>. (4.42)
Опуская детали, отметим, что еще одно повторение «раскрут-
ки» приводит полученное выражение для рп к виду
Р„ = ^^+О(-!^). (4.43)
Поскольку с функцией p(z) мы благополучно покончили,
обратим теперь внимание на оставшуюся часть равенства
(4.31) — функцию q(z). На этот раз мы выделим в разложе-
нии для q(z) члены при А= 1, получая
q (z) *=* s (г) г (г), (4.44)
где
/ \ ( z3 z4 । г5 \
4(z) = exPpr--i- + -5-- ...).
! X (v (г'к г’4 , М (4'45)
г(г) = ехрП
Выражение для s(z) может быть переписано в виде
s(z) == exp (In (1 4- z) — г + г2/2) = (1 + г) е~г^г'^\ (4.46)
4,1. Основные понятия
59
откуда мы заключаем, что коэффициенты sn этой производя-
щей функции экспоненциально малы.
В выражении для r(z) соберем вместе члены с одинако-
выми показателями степеней:
г(2) = ехр(Хг‘ X 7W)' (447)
3<d<kr2\d]k ' /
Здесь внутренняя сумма есть О (/г3) (это следует из при-
мера, которым в разд, 4,1.3 был проиллюстрирован метод рас-
членения сумм). Дифференцируя выражение (4.47),
г' (г) = г (г) £ /?г4"' О (*’’), (4.48)
k >3
и приравнивая коэффициенты при zk, получаем рекуррентное
соотношение для гп\
пга= х '‘ДтгЬД- <4-49>
О k < п
А это рекуррентное соотношение можно «раскрутить», полу-
чая для гп последовательно оценки 0(1), 0(п-1), 0(п-2) и
О(п^).
После того как исходная задача была раздроблена на
многочисленные подзадачи, мы наконец успешно расправи-
лись с каждой из них, и теперь можем приступить к сборке
окончательного результата.
Вначале из функций r(z) и s(z) составим функцию q(z)
с коэффициентами
^n== Е (4.50)
о < к
Это свертка двух рядов, члены которых имеют порядок
О (/г-3), так что результат также равен О (/г-3). (Для того
чтобы увидеть это, надо разбить область суммирования на
две части: 0 k п/2 и 0 п — k <: п/2. Читатель может
попытаться выяснить условия, которые необходимо наложить
на /(«), для того чтобы свертка двух рядов, члены которых
имеют порядок О(/(/?)), имела такой же порядок.)
Затем из функций q(z} и p(z) составим функцию g(z):
g(2!) = p(22)^(2) (4.51)
с коэффициентами
gn = Е Ptfi (4.52)
2k + L-n 4 ’
и просуммируем полечая
= Z Prf!. (4.53)
60
4. Асимптотический анализ
Мы уже йаем, что сумма ряда в правой части равенства
(4.53), если ряд расширить до бесконечного, равна е~у. По-
этому сосредоточим наше внимание на «хвосте» суммы ряда
A^e-v - РМ =
— e-Y Г Е <h ( Е Pte + Е Р*)¥ (4-54)
М ^'1 \_’te>/i Г1-/ <2k / /
Внутренние суммы можно оценить, используя результаты
предыдущих вычислений Первая сумма:
jte > п
= ~?Л> + 0 (^). (4.55)
Здесь мы не заменяем функцию р(1) ее значением е-"'12:
это окажется полезным для объединения р(1) и ?(1) с целью
получения e-v. На последнем шаге к обеим суммам была при-
менена формула суммирования Эйлера.
Другую сумму в равенстве (4.54) можно оценить, разби-
вая область суммирования на две части:
Е Pi X Pk= X Я1 Е Рл+ Е Е Pfe =
^^0 п— I п и п— Z<2fe<« n—l^2k^n
= 0( £ ?,-/|р„,4|+ Е ?;.|р(1)|) =
ко </<ге/2 1 1 1^п/2 /
= О(/Г2). (4-56)
Теперь, опенив все части равенства (4.54), можно наконец
вычислить hn-
h^e-i + l^+0(^) =
= е-, + Г1+0(^). (4.57)
С помощью похожих, но более простых методов можно
показать, что gn = О (м'1), так что использование выше тау-
беровой теоремы было действительно оправданно.
4.2, Интегрирование по Стилтьесу и асимптотики
Интегралы служат полезным инструментом асимптотиче-
ского анализа, поскольку их можно использовать для прибли-
женного вычисления сумм; при этом полезно иметь представ-
ление о том, как интеграл взаимодействует с символом О. По
4.2, Интегрирование по Стилтьесу
61
этой причине мы и будем изучать интеграл Стилтьеса.
В книге Апостола [57] приведены следующее определение и
его немедленные следствия.
Определение. Пусть f и g— вещественнозначные функции,
определенные на интервале [а, Ь], и пусть Р — некоторое раз-
биение интервала [а, Ь] точками а — Хо < < ... <Zx>?—b,
Определим сумму
3 (?) = £ f (U (g Сч+1) — g СЧ)). * е= [xft, xfe+1]. (4.58)
k<n
b
Величина А называется интегралом Стилтьеса ^f(t)dg(t)
а
тогда и только тогда, когда при любом е > 0 существует раз-
биение такое, что каждое измельчение (refinement. —
Иерее.) Р разбиения Ре дает сумму, близкую к Л, а именно
|S(P) —Д|<е.
Следствия.
1) Интеграл Стилтьеса имеет не более одного значения.
2) Интеграл Стилтьеса линеен no f и g.
b сс
3) (Аддитивность.) •
aba
b
4) (Интегрирование по частям.) Если \^f(i)dg(t) суще-
а
b
ствует, то g (/) df (/) также существует и сумма этих ин-
а
тегралов равна f (/) g (/)
5) (Замена переменной.) Если h — непрерывная неубы-
вающая функция, то
b h (&)
\f(h(t)dg(h(i))^ (4.59)
a h. (а)
b
6) Если J f (t) dg (t) существует, а производная g' (f) непре-
a
рывна на [a, Z>], то
b b
\fWdg(t)=\lfWs'Wdt. (4.69)
а а
62
4. Асимптотический анализ
7) Еслц, а и b — целые числа, а функция f непрерывна
справа от целых точек интервала [а, £>], то
ь
$ Г (О (Г f 1) = У f(/e)Agr(fe), (4.61)
a ai£lli£b
где &g(k)--= g(k + \)~ g(k).
7') Если а и b —- целые числи, а функция f непрерывна
слева от Целых точек интервала [и, Ь], то
ь
f U) dg IL / J) £ /(/c)Vg(fe), (4.62)
а а < k < h
где Vg(k)'^ g(k) — g(k — I).
8) Если a и b — целые числа, а функция g непрерывна
слева от Целых точек интервала [а, 6], то
ь
\f(\.U')dg4)= £ (4-63)
а а < £<£>
9) {Производная от интеграла.)
ь t ь
\t(t)d\g {и) dh (и) = f (/) g (Z) dh (Z). (4.64)
а а а
10) Если f (Z) dg(Z) существует на интервале [а, 6], то
f (О dg (t) существует на любом подынтервале интервала
[а, Ь].
ь
11) Интеграл ^f(t)dg{t) существует, если f—непрерыв-
а
ная функция, a g —функция ограниченной вариации на (а, £>],
Под ограниченностью вариации функции g понимается
ь
существование интеграла 1 dg (Z) |. Интуитивно это озна-
а
чает, что вариация |g(Xfe+i) — g{x&) I уменьшается по мерс
измельчения разбиения Р. Одной непрерывности здесь недо-
статочно; например, для функций f{t) = g (Z) = *J7 cos(l/Z)
интеграла Стилтьеса не существует.
12) (Суммирование по частям.) Сопоставление следствий
4. 7 и 7’ при целых а и b дает очень полезную формулу;
Е f до Ag tk) = W g (< - Eg (k) V/ (fe).
a<A<b й<А<6
4.2. Интегрирование по Стйлтьесу
63
4.2.1. Символ О и интегралы
Приведенные выше основные свойства интеграла Стил-
тьеса позволяют доказать две теоремы, которые обусловли-
вают возможность вынесения символа О за знак интеграла.
Теорема 1. Если -g — монотонно возрастающая функция,
а функция f положительна, то
Ь , b \
J О (f (0) dg (/) = О И f (Z) dg (Z)) (4.65)
a \a /
при условии, что оба интеграла существуют.
Доказательство. Напомним, что запись а (Z) — ll)
означает существование постоянной М, такой, что |а(/)|<
Поскольку по предположению f(t) и dg(t) неотри-
b ь
цательны, то | а (/) \dg (/) < Mf (/) dg (Z), н, вынося М за
а а
знак интеграла, получаем утверждение теоремы,
Теорема 2. Если f и g — монотонно возрастающие поло-
жительные функции, то
р 0 do (g W) = О (f (a) g (а)) + О (f (6) g (i)) + О ( J / (Z) dg (Z) )
(4.66)
при условии, что все интегралы существуют.
Доказательство. Обозначим через b(t) функцию, которая
есть 0{g(t)). Интегрируя по частям, получаем, что
ь ь
J / (/) db (Z) = f (Z) b (Z) £ - р (Z) df (fi. (4.67)
a a
Применяя к последнему интегралу теорему 1, имеем
ь > ъ .
$ ИО do (g «)) = О (f (a) g (а)) + О (f (Ь) g (&)) + О ( ( g (() df(t))
« Ха /
(4.68)
Повторное использование формулы интегрирования по ча-
стям с целью перестановки fag завершает доказательство
теоремы.
64
4. Асимптотический анализ
4.2.2. Формула суммирования Эйлера
Интегрирование по Стилтьесу обеспечивает теоретическую
основу для аппроксимации сумм интегралами. Допустим, что
требуется приближенно просуммировать значения /(/г). Нач-
нем со свойства 7 интеграла Стилтьеса;
ь
У f |А-) = J (4.69)
п k < b л
Используя свойство л инейное ти интеграла Стилтьеса, правую
часть равенства (4.69) можно расписан. в виде
ь ь ь
(fWd(/-fO + 4) + $f(0rf(+4). (4.70)
а а а
Первый интеграл представляет собой грубое приближение к
искомой сумме, которое мы уточним, вычислив второй инте-
грал, а третий интеграл равен нулю.
Вывод других членов формулы суммирования Эйлера нач-
нем с интегрирования по частям второго члена в выражении
(4,70):
Ь b lb
а а
b b
+ $б~ГЛ + 4) df(t) = \f(t)dt-
а а
b
-4/Ш+$ (4.71)
а
На интервале [п, п-f-l] последний интеграл может быть
приведен к виду
п+1 n+f
J (/ - п -1) df(f) = J /' (/) d (('- «)-('-'») +W) _ (4<72)
м п
А эту процедуру можно повторить, снова интегрируя по ча-
стям и меняя ролями f и g во вновь полученном интеграле
$ gdf.
Однако для законности применения подобной итеративной
процедуры необходимо выполнение нескольких требований, н
если мы выясним, что это за требования, то заодно раскроем
секрет появления в (4.72) констант 1/2 и 1/6. Прежде всего
4,2, Интегрирование по Стилтьесу
65
предполагается, что существует производная f'(t) (в действи-
тельности на каждой итерации требуется существование про-
изводных f(t) все более высоких порядков). Второе требова-
ние возникает, когда мы «интегрируем» (/— п— 1/2), полу-
чая ((/ — и2) —(/— п) 4* 1/6)/2 (подобная замена делается на
каждом интервале [п, п+ 1], из которых «монтируется» весь
интервал [а, &]). К счастью, ((/ — «)2— (/ — п) + 1 /6)/2 при-
нимает одинаковые значения при t = п и t — п + 1; следова-
ь
тельно, на месте £(0 в интеграле ^f'{tydg(t) стоит непре-
а
рывная функция. Любые разрывы функции g давали бы су-
щественные и нежелательные вклады в интеграл Стилтьсса.
Таким образом, константа «1/2» в левой части равенства
(4.72) несет ответственность за непрерывность подынтеграль-
ной функции так же, как и константа «1/6» в правой части
(4.72), которая обеспечивает аналогичную непрерывность,
когда мы вновь интегрируем многочлен на последующей ите-
рации.
Итак, имеется семейство многочленов B(t—[/J), сохра-
няющих непрерывность при целочисленных значениях /, по-
скольку ВД0) = В((1) при I, и связанных дифференциаль-
ным соотношением В\(х) = iBt_{ (х). Этим двум требованиям
удовлетворяют многочлены Бернулли:
В] (х) = х — 1/2,
В, (х) = х3 — х + 1/6,
(х) = х3 - (3/2) х2 + (1/2) х, (4.73)
k
Постоянные В% в последней сумме называются числами Бер*
ну л л и,
во=1, = В2 = |, В3 = 0, В4=--К ... (4.74)
(в других обозначениях Во— 1, В3 —— ...
—Рад.), и именно они являются коэффициентами окончатель-
ной формулы суммирования:
а<А<6 а
(4.75)
1/23 Зак. 259
66
4, Асимптотический анализ
4.2,3. Теоретико-числовой пример
Предположим, что целое п выбрано «случайно» из интер-
вала [1, х]. Тогда среднее число различных простых сомно-
жителей п задается формулой
4Z Е ’-4
П < X р | П
(4.76)
(Здесь и далее р обозначает простое число.) В приведенной
формуле интересующая нас величина является (если игнори-
ровать некоторое отклонение, вызванное функцией «пол»)
суммой чисел, обратных простым. На примере решения этой
упрощенной задачи мы продемонстрируем несколько приме-
нений интеграла Стилтьеса.
Сначала выразим сумму в виде интеграла:
Г 7“ $
р<х 1.5
(4.77)
где л(/)= 2 1 — ступенчатая функция, изменяющая свое
значение только на простых t. Хорошим приближением к л(х)
служит функция А(х), определяемая формулой
1.5
(4.78)
поскольку
я(х)-£(х) 4- О (4.79)
(Это усиленный вариант «теоремы о простых числах»12), по-
лученный Валле-Пуссеном в XIX в.; ср. Кнут, Траб Пардо
[76].) Подставляя в (4.77) вместо л(/) функцию
+ О (/6> -cCio« *) и вынося по теореме 2 символ О за знак ин-
теграла, получаем асимптотическую оценку:
Е 7= \-пЬ+ Ud0(ie’e^*)=
1.5 1.5
= In In х 4- О (1).
(4.80)
Хотя аналог формулы суммирования Эйлера для сумм по
простым числам неизвестен, существует окольный путь усо-
вершенствования этой оценки. Рассуждая по аналогии с пре-
4.2. Интегрирование по Стилтьесу
67
дыдущнм, можно вычислить сумму общего типа:
Ст(х) = £ Иг^. = 11!!Л^+О(1), т>1. (4.81).
Тогда, используя 9-е свойство интеграла Стилтьеса, сумму
Со (я) можно представить в виде
А последний интеграл
С (In и)т dn (и)
J л
1.5
С dcm (О
J (In/)"1
(4.82>
1.5
вычисляется интегрированием по ча-
стям:
С0(х)
Ст (О Iх । С Ст (0 dt
(1л /Г к.5 A * (1П
Lb
X
4- tn
1.5
О (1) dt
t (In 0m+l
= In In t 4- M 4- О ((logx)"”1).
(4.83)
Поскольку этот вывод справедлив при всех tn > 0, нами до-
казан довольно сильный результат об асимптотическом пове-
дении суммы чисел, обратных простым. Однако сила получен-
ного результата делает задачу выяснения точного значения*
константы М сродни танталовым мукам.
Для вычисления М придется воспользоваться дзета-функ-
цией Римана и формулой обращения Мебиуса. Дзета-функ-
ция связана с простыми числами тождеством
JW - z Д=п - п (1 + p-+p-*+ ...),
п>1 Р Р
s > 1. (4.84);
Вслед за Эйлером нам будет удобнее иметь дело с логариф-
мом дзета-функции:
|" ш = У + .. .)=
р
= S(s) + (2s) + у 2(3S) + ..., (4.85)
где 2(s) = Ep-s. В этих обозначениях нас интересуют ча-
р
стичные суммы расходящегося ряда 2(1), информацию о ко-
торых можно получить, рассматривая сходящийся ряд 2(s)
при s > 1.
>/33*
68
4. Асимптотический анализ
Для обращения рядов типа (4.85) может использоваться
функция Мёбиуса, определяемая как
ц (п) =
1,
0.
(-1Л
если /г = 1,
если п делится на квадрат целого числа,
отличного от единицы,
если п есть произведение k различных
простых чисел.
(4.86)
Наиболее употребительна следующая формула обращения
.Мёбиуса:
£(«) = £ ПЛ —/О) = £ n(d)g(y.y (4.87)
d l n d | n
Однако для наших целей потребуется «бесконечный» вариант
этой формулы
gW = £ f ОМ f (х) = £ (4-88)
771=1 П=[
которая позволяет выразить S ($) через функцию £($):
= (4.89)
ZZ
Поскольку £(s)— 1 4* O(2-s), то последний ряд сходится к
S(s) довольно быстро. Таким образом, мы располагаем эф-
фективным способом вычисления S(s), который окажется по-
лезным, когда мы выразим константу М через сумму рядов
S(s) при з2>1. (Отмеченные выше свойства дзета-функции
и функции Мёбиуса можно найти, например, в книге Харди
и Райта [79].)
Давайте теперь остановимся на минутку, чтобы наметить
план дальнейших действий. Как уже отмечалось, нас интере-
сует 2(1), однако формула (4.89) справедлива только при
5 > 1. Вместо 2(1) мы могли бы взять 2(1 -ф е) и устремить
е к нулю в равенстве
2(1 + 8) = !п£(1 +e)-rs(2 + 2e)-js(3 + 3e)+ ... . (4.90)
Стандартные руководства типа Введения в теорию чисел
Харди и Райта [79] дают для £(1-фе) вблизи единицы
асимптотическую оценку е_|фО(1), что упрощает предыду-
щую формулу:
S(1 + в) = —lire—Z(n + '1'!> + O(e). (4.91)
п—2
4.2. Интегрирование по Стилтьссу
69
К сожалению, этот ряд «разбухает» с ростом другого пара-
метра, отличного от параметра нашего исходного выражения,
С„ (*) = £ У =111 In х + М + О ((log x)-m). (4.92)
Значит, для получения информации о константе М мы не мо-
жем просто сократить главные члены в предыдущих форму-
лах— вместо этого надо сделать выражение для Со завися-
щим от 8.
С этой целью введем в выражение для Со величину е так,
чтобы х можно было устремить к бесконечности:
СО OQ
(4-93)
р t.a L5
(при замене dji(t) на tdC0(t) здесь снова использовано 9-е
свойство интеграла Стилтьеса). Интегрируя по частям, по-
лучаем
У(1 + в)= lim (CoWd(r')Y (4.94)
\ L5 /
Теперь заменим величину Со(О в интеграле ее асимптотиче-
ским выражением (4.92). В соответствии с этой. асимптоти-
кой С0(х)/х£ стремится к нулю; поэтому остается выражение
(оз \
5 (In In I + М + О (log О’1) -Д- ) (4.95)
1,5 J
Затем, подставляя вместо i, получим
00
^-Mlnu-lne+M+Ofe/u))^ (4.96)
е In 1,5
Интегрирование большинства полученных членов не вызы-
вает затруднений, за исключением члена е_“1пи, интеграл от
которого можно выразить через интегральную показательную
функцию:
Ь <»
С Г е~а
\ е~“1п и du = е~а In a -J- \ —— du. (4.97)
а а
При малых значениях а асимптотическое поведение инте-
гральной показательной функции хорошо изучено:
оо
г
£1 (а) — \ —— du = — In а — у + О (а). (4.98)
70
4. Асимптотический анализ
Использование этой информации в равенстве (4.96) дает
£ (1 + е) = (1.5)“е (In е + In 1п 1.5) -j- £[ (е 1п 1.5) —
- (I -5)-е in 8 + (1.5)“е Л1 + О (е£\ (е In 1.5)) =
= - In 8 - у + Л1 + О (е In . (4.99)
Теперь остается сравнить переработанную формулу с перво-
начальным выражением (4.91) для S(1 + е) и получить фор-
мулу для М:
/M = y-Tv(2)-ls(3)- ... . (4.100)
Поскольку S(s) = O(2~s), этот ряд сходится весьма быстро;
точное значение константы М равно 0,26149 72128 47643...
(Кнут, Траб Пардо [76]).
Возвращаясь к поставленному в начале настоящего раз-
дела вопросу, мы приходим к заключению, что среднее число
различных простых сомножителей п равно
ЖШОФ
= Х7 + 0(ьТТ>
Р<Х
= In In х + М + О (1/log х). (4.101)
4.3. Асимптотики из производящих функций
Довольно часто результатом комбинаторных рассуждений
является производящая функция G(z), интересующие нас
коэффициенты которой не выражаются в простой замкнутой
форме. Настоящий раздел посвящен двум широко используе-
мым способам установления асимптотик для подобных коэф-
фициентов gr. при большом п по заданной функции G(z) =
= Ygnzn. Выбор того или другого способа зависит от харак-
тера G(z), Если G (?) имеет особенности, то используется ме-
тод Дарбу для установления, исходя из этих особенностей,
асимптотического поведения gn. С другой стороны, если ряд
для G (z) всюду сходится13), то применяется метод перевала
для нахождения контура и вычисления соответствующего кон-
турного интеграла.
4.3,1, Метод Дарбу
Когда ряд для б?(г) сходится в круге радиуса Д ряд
SI SrXn I сходится абсолютно при г < /?, а это возможно, если
только gn ~ О(г~п). Этот фундаментальный факт (см.
4.3. Асимптотики из производящих функций
71
разд. 4.1.4 — Перев.) из теории рядов наводит на мысль о
следующем (несколько идеализированном) подходе к асимп-
тотическому оцениванию gn. Если G (г) имеет особенность на
границе круга радиуса R, то отыскивается функция H(z)
с известными коэффициентами, которая имеет ту же особен-
ность. Тогда ряд для G(z)—Н (г) будет иметь больший ра-
диус сходимости S, a gn будут достаточно близки к коэффи-
циентам hn’
gn = hn + O(s-”\ s<S. (4.102)
Этот процесс повторяется до тех пор, пока 5 не увеличится
настолько, что ошибка приближения станет малой.
Данный метод существенно зависит от выбора функции
сравнения /7 (г), имеющей известные коэффициенты. Для
устранения обыкновенного полюса функции G(z) в точке
z — a функцию H(z) легко построить, поскольку G (г) будет
иметь разложение Лорана вида
G (2)= (г — а)т "Ь * • * (Z — д) 4" (z — а) • •
(4.103)
В качестве функции H(z) из этого разложения используются
члены с отрицательными степенями (г — а):
Н (г) = - + —С~т+2_, + ... + ---1 . (4.104)
(z — а)т (z—a)m ’ (г — а) }
Коэффициенты H\z} можно получить с помощью биномиаль-
ного разложения:
(г —а)-' —(—a)-'2Z ( (4.105)
(В качестве иллюстрации применения метода Дарбу к функ-
ции, особыми точками которой являются полюсы, см. Кнут
[III, разд. 5.1.3],)
Значительно труднее устранить алгебраические особенно-
сти; в действительности такую особенность можно только
«улучшить» в некотором смысле, который вскоре станет ясен.
Алгебраичность особенности означает, что G(z) можно пред-
ставить конечной суммой членов вида
(г-аГ^г), (4.106)
где w— комплексное число, а функция g(z) аналитична в
точке 2 = а. Например, функция
УГ^=^(^2)(-г)’ (4.107)
72
4. Асимптотический анализ
имеет алгебраическую особенность при г = 1, однако в дан-
ном случае она разлагается в биномиальный ряд, так что в
применении метода Дарбу нет необходимости.
Проиллюстрируем метод Дарбу на примере функции
G (г) = V(1 “ z) (1 — а2)> а < 1. (4.108)
Нам нужна функция сравнения, которая будет «бороться» с
особенностью в точке z — 1, поэтому сначала разложим в ряд
функцию
Vn^7z=.VF™a + Cl(l-z) + C2(l-г)2+ .... (4.109)
Первый член разложения подсказывает нам выбор
Н (г) = V1 — гл/\ — а (4,110)
в качестве функции сравнения, а дальнейшие члены разложе-
ния (4.109) можно будет использовать для улучшения полу-
чаемой Оценки, Посмотрим, насколько хороша функция G(z)
сама по себе без дополнительных членов:
G (z) — H(z) = Vl — z (Vl — az — Vl — a) =
/1 _Л3/2 I _
— a (1 — z) —... ---------- =
д/l — az -p Vl — a
= A(z)B(z), (4,111)
где
4(z) = a(l -г)3,г.
В(г)=1/(л/Г^ + л/Г^Т). (4.112)
Заметьте, что мы не устранили особенность при z = l, а
только «улучшили» ее, получив (1—z)3/2 вместо (1 — г)1/2.
Подобное улучшение достаточно убедительно показывает, что
Н(z) может служить хорошим приближением к функции G(z).
Ошибкой этого приближения является коэффициент при
zn в разложении A (z)B(z). Радиус сходимости степенного
ряда для функции B(z) больше 1, н, следовательно, Ьп =
= О(г~я) при некотором г > 1. Далее, функцию X(z) можно
разложить в ряд
„ / 3/2 \ (п — 5/2 \
Л<*) = а £( ' )(-*)” = «£( (4.113)
n^O п >0
/ п — 5/2 \
что дает ап —а( 1 = О(п~5/2). Чтобы оценить ошибку
4.3. Асимптотики из производящих функций
73
приближения, разобьем, как в разд, 4.1.3, свертку рядов для
Л (г) и B(z) на две части:
Е аЛ-» = О(г-'2), (4.114)
(f /z Г2у 2
Е а,Л-4=О(П-5'2).
а/2<£ < п
Следовательно, можно утверждать, что
.________________________ ( 1/2 \
g„ = л/1 -а(-1)"1 1 + О(п-5'2). (4.115)
Оглядываясь назад, мы обнаруживаем, что вывод оценки
для gn свелся просто к разложению С (г) в окрестности точки
г = 1. Оценка же остаточного члена — это просто ловкий
трюк, использующий возрастание показателя степени (1—г)
с 1/2 до 3/2. И действительно, подобная зависимость от по-
казателя степени присутствует в условии приводимой ниже
теоремы Дарбу, в которой вводится понятие «веса» особен-
ности, уменьшая который, мы «улучшаем» особенность.
Теорема. Предположим, что функция G (г) — X ёпг^ ана~
литична в окрестности нуля и имеет только алгебраические
особенности на границе круга сходимости этого ряда. Весами
особенностей
(1 -г/аГ^Н*) (4.116)
будем называть вещественные части чисел w. Пусть W— мак-
симальный вес таких особенностей. Обозначим через аь,
и hit(z) значения а, ш и h(z} тех членов вида (4.116), особен-
ности которых имеют вес IF. Тогда
п V г (а,д %
где s — | «ь | — радиус сходимости ряда для б(г), а Г (г) —
гамма-функция.
Этот вариант теоремы Дарбу, приведенный в работе Бен-
дера [74], позволяет получить первый асимптотический член,
ослабляя все особенности-тяжеловесы.
Данную процедуру можно повторить, получая в резуль-
тате чуть более громоздкое утверждение теоремы, которое
приведено в книге Конто [74]. Поскольку обыкновенному по-
люсу соответствует целочисленный вес w в формулировке тео-
ремы, повторное применение процедуры сведет в конце кон-
цов w к нулю, устраняя особенность полностью, ибо веса
ш — 0, —1, —2, ... не соответствуют особенностям.
4 Зак, 259
74
4. Асимптотический анализ
4.3.2. Метод вычетов
Теорема о вычетах утверждает, что интеграл по замкну-
тому контуру в комплексной плоскости может быть вычис-
лен" по вычетам в охваченных контуром полюсах:
2“у*ф / (2) ~ X (вычеты в охваченных полюсах)* (4.118)
с
При этом вычет функции Пг) в точке г —а равен коэффи-
циенту С-] в разложении Лорана
и*)+ , с-;у_, + +-7^- +
(г—а) (г ~ a) (г — а)
+ ^, + ^(2-0)+ .... (4.119)
Вычислять вычеты сравнительно легко. Если tn — 1, то точка
г = а есть полюс первого порядка и вычет относительно этой
точки дается равенством
C_r ~ lim (z — а)/ (г). (4.120)
г->а
Обычно предел поддается вычислению с помощью многократ-
ного применения правила Лопиталя:
lim -f = lim
г->а
g' (г)
fl' (z) '
(4.121)
Считается, что полюс имеет порядок пг, если Нтг-^а(г—
есть константа, но это определение не годится для вычисле-
ния вычета при m > 1. Поэтому для выделения требуемого
коэффициента надо использовать производную:
t Atn—i
<4-122)
На практике, однако, зачастую быстрее разложить состав-
ляющие /(г) выражения в ряды в окрестности точки г —а и
затем собрать коэффициенты при {г—а)-1.
Теорема о вычетах традиционно рассматривается как про-
стой способ вычисления интеграла по замкнутому контуру.
При нахождении асимптотических оценок мы часто будем
применять эту теорему «задом наперед», помещая интересую-
щую нас комбинаторную величину на место вычета и вычис-
ляя затем интеграл,
Предположим, например, что имеется двойная производя-
щая функция
F(w, г)= £ (4.123)
tn, п
4,3. Асимптотики из производящих функций 75
н мы хотим вычислить производящую функцию для диаго-
нальных элементов
О(г)= (4.124)
п
Соберем члены с п = т в коэффициенте при Z-1, где они ста-
нут вычетами:
= £»rl,/ = fi(z) (4.125)
Если ряд сходится равномерно, то сумму и интеграл можно
поменять местами, поэтому путь интегрирования выбирается
так, чтобы сделать как [/|, так и |г//| достаточно малыми.
Классический пример диагонализации степенных рядов на-
чинается с разложения
т-ч f т -|— мА 1
г)= £ ( „ = <4-126>
т, п О
требуется найти выражение для производящей функции
Используя выведенную выше формулу, имеем
^=2^ 1' <4-128)
С
В качестве С выберем контур, охватывающий начало коорди-
нат и полюс первого порядка в точке
с вычетом (1 —4г)-1/2; поэтому интеграл равен
0(г)=----7f=~- (4.130)
VI — 4г
В качестве второй иллюстрации процедуры диагонализа-
ции рассмотрим задачу почленного перемножения двух сте-
пенных рядов
= и £ Ьлг\ (4.131)
4»
76
4. Асимптотический анализ
Ис пол ьзуя установленную выше формулу (4,125), получаем
произведение Лдамара:
G (г) = £ anbnz" = Щ § А (/) В (у) £ • (4.132)
4.3,3. Метод перевала
В нашем следующем примере используется несколько
стандартных приемов, которым следует уделить внимание,
прежде чем приступить к решению конкретной задачи. Сна-
чала мы будем применять теорему о вычетах «задом напе-
ред»:
1 с G[z)dz
= <4-133>
Предполагается, что производящая функция известна и не
имеет особенностей (в противном случае асимптотическое
поведение gn можно было бы установить с помощью метода
Дарбу). Поэтому единственное ограничение, накладываемое
на контур интегрирования, состоит в том, что он охватывает
начало координат. Удачный выбор этого контура облегчает
оценивание интеграла, а хорошей эвр стикой для его выбора
служит метод перевала. Идея метода перевала состоит в про-
ведении пути интегрирования через седловую точку, в которой
производная подынтегральной функции обращается в нуль,
в то время как в соседних точках функция круто падает. По-
добно ленивому путешественнику, мы выбираем путь, прохо-
дящий через низкую точку перевала, но в отличие от этого
путешественника мы выбираем наиболее крутой путь на пе-
ревал— для наших целей крутизна гораздо важнее, чем пере-
сечение перевала в самой низкой точке.
После того как контур интегрирования выбран, зачастую
оказывается полезным другой прием — метод Лапласа для
оценки интегралов. Допустим, что подынтегральная функция
почти целиком сосредоточена па сравнительно малом интер-
вале, имея незначительные хвосты, растянутые по всей об-
ласти интегрирования, Метод Лапласа заменяет эти хвосты
другими малыми функциями, ингеграл от которых легко вы-
числяется. При этом должно быть показано, что как старые,
гак н новые хвосты незначительно влияют на окончательный
результат.
В выбранной нами для иллюстрации этих приемов задаче
будет выведен усиленный вариант центральной предельной
теоремы, которая утверждает, что сумма большого числа
реализаций случайной величины с произвольным распределе-
4.3. Асимптотики из производящих функций
77
нием распределена асимптотически нормально:
Bep ( ц--------------------3L_«. < ц + ) =
\ n ynJ
p
= ? e-^dz{\ + O(n-')Y (4.134)
V2n J
— a
Здесь Xi — произвольные, но одинаково распределенные слу-
чайные величины со средним ц и стандартным отклонением
о. Вводя несколько незначительных ограничений, можно по-
лучить еще более сильный результат, который полностью про-
ясняет вопрос о том, насколько быстро сходится к нормаль-
ному распределению сумма целочисленных случайных вели-
чин с произвольным распределением.
Предположение 1. являются целочисленными случай-
ными величинами, распределение вероятностей которых pk =
= Bep(Xj — k) имеет производящую функцию
g(z)= Z PkZk- (4.135)
Будем считать, что функция g(z) аналитична в круге |z|<
< 1 + 6, и, поскольку g(l)= 1 для любого распределения ве-
роятностей, функция 1п£(е9 аналитична при t~0. Это по-
зволяет выразить g(0 через разложение Тиле:
ё(?) = ехр(н + 41+-Зг + 2^-+ ••) <4Л36)
где Xj является t-м семиинвариантом распределения вероятно-
стей р^.
Предположение 2. g(0) должно быть отлично от нуля, т. е.
Рп =У= 0. Это предположение ие является обременительным, по-
скольку вместо g(z) можно взять z~mg(z), где т — номер
первого ненулевого коэффициента рт.
Предположение 3. Наибольший общий делитель всех k,
таких, что должен быть равен 1. Это допущение так-
же необременительно, поскольку вместо g{z} можно взять
^(г1/т), где т— наибольший общий делитель таких k, что
рь 0.
Сумме п реализаций случайной величины, имеющей рас-
пределение с производящей функцией g(z), соответствует про-
изводящая функция g(z)n. Мы намерены изучить поведение
этой суммы вблизи ее среднего рл, для чего определим
Л„,г = коэффициент при zyvi+r в разложении g(z)nt (4.137)
78
4. Асимптотический анализ
где г выбрано так, чтобы р/г 4" г было целым. По теореме
о вычетах
А».
1 £ g ^)п dz
2л! J Д1«+г+1
(4.138)'
Поскольку точка перевала лежит в окрестности точки 2 = 1,
выберем в качестве контура интегрирования окружность еди-
ничного радиуса с центром в начале координат и подставим
z = ei( в (4.138):
•<,=-4 S"'XX • и-139)
—л
В силу предположения 3 все члены функции g(eif) будут на-
ходиться «в фазе» лишь при / = 0; следовательно, ^(е^) | <
< 1, за исключением случая i = 0, когда g(1) — 1. Возведе-
ние gie11) в /г-ю степень делает хвосты интеграла экспонен-
циально малыми, так что основной вклад в интеграл вносит
окрестность точки t = 0. В частности, при любом выборе бЗ>0
найдется такое ае(0, 1], что |g(eu) | < а при б^|^|^ л,
а это означает, что
л'-=дг S + ° (°")- <414°)
-б
Метод Лапласа предполагает замену хвостов более прием-
лемыми функциями. Прежде чем присоединять новые хвосты,
проделаем несколько манипуляций с исходными хвостами,
сужая (refining. — Перев.) каждый раз промежуток интегри-
рования, Вначале выберем б] настолько малым, чтобы сде-
лать законным разложение Тило для функции gf(^), н раз-
ложим в ряд подынтегральную функцию
g (еи)п
git (цп+о
= ехр{ — irt —
a2i2n
2!
i-K3t3ib , x4f4«
Затем выберем бг, меньшее чем бц так, чтобы первые два
члена этого разложения преобладали над остальными:
I />Щ3/г . к^п . I . а2|/21п . ,, . . /лллпх
|----+ —6“ ПРИ 1^<б2- (4.142)
Эти два сужения промежутка интегрирования делают воз-
можным третье, состоящее в замене интервала [— ба, б2] на
[—tt"1;2+e, я-1'146]. (Роль таинственного е вскоре станет
очевидна.) Ошибка, вносимая последним сужением проме-
4.3. Асимптотики из производящих функций
79
жутка, есть сумма двух выражений вида
ба
С I ( • 1 (f2t2n \ I I ( lK3t3n . \ I j,
J |ехр(_- irt---------2Г~)|. ехр(----------jj— + .) j dt.
и-1/2+е
(4.143)
Величина —irt в первом сомножителе представляет собой не-
существенную для нас фазу, а второй сомножитель в силу
неравенства (4,142) ограничен; следовательно, эта ошибка
экспоненциально мала:
61
$ ехр(_ ^ + 2^L^/<62e-o^/.\ (4144)
B-I/2+*
Теперь должна быть ясна причина выбора ± п”,/2+е в каче-
стве пределов интегрирования, На последнем шаге мы оце-
пили интеграл его наибольшим значением, подставив в подын-
тегральное выражение rc “12+s вместо i, В результате уничто-
жается nt стоящее в подынтегральном выражении рядом с t2,
так что е оказывается «последней соломинкой, сломавшей
спину верблюда» и устремившей этот интеграл к нулю.
Подводя итог проделанному, можно утверждать, что су-
ществует такое к >0, что при любом е >• О
п~ 1/2+е
А*.' = ± $ +0 (о"2')- (4-145>
—п~ 1/2+е
В пределах такого малого интервала существенны только два
первых члена в разложении Тиле:
п~ 1/2+В
А„.г = Ш J exp (- irt - + О dt + О (а»а).
—м 1/24" в
(4.146)
Теперь мы готовы присоединить к интегралу новые хво-
сты, используя в качестве последних два первых члена раз-
ложения Тиле, Новые хвосты экспоненциально малы:
\ exp ( — irt---------—1 di
л-1/2+«
exp
== О (exp (
80
4. Асимптотический анализ
Дополнив показатель экспоненты до полного квадрата, легко
вычислить интеграл на [—оо, оо]:
ОС
Л.г=-2~- $ ехр(-/г/--^)(1 + О(п3'-'е))^ + О(а'>!е)=
“ оо
= —^=ехр(^)+ (4.147)
о -\/2лп \ 2егп /
Заметьте, что константа, связанная с полученной О-оценкой,
зависит от g(t) и е, но не от п пли г.
Полученный результат можно улучшить, используя боль-
шее, чем в равенстве (4.146), число членив разложения Тиле.
Это потребует интегрирования членов типа
J eiat-b^tkdL (4.148)
Дополнив показатель экспоненты до полного квадрата и раз-
ложив tk в биномиальный ряд, получим несколько членов
вида
сю
e~~u'uJ du. (4.149)
"-00
При нечетном / этот интеграл обращается в нуль, а прн чет-
ном / его можно свести к гамма-функции с помощью подста-
новки v ~ и2. Используя подобную процедуру, нашу преды-
дущую оценку можно усовершенствовать и получить, к при-
меру,
= Ж “р (т) + 77 О+°
(4.150)
Коэффициент при общем члене rR/nN этого разложения за-
дается выражением
с 9S
У (-1) (/? + 2S)-
2L а2 </?+S)2SS! 74
S >0
х Е w(ir №)’•••• «151>
Pi+Pl+Ps + ... = Д-Л’+.$
3pj-f-4p4-f-JPs-f-• • • "Д-Ь 23
з
подобные члены отличны от нуля при О А1 у A\
Это весьма сильный результат, из которого суммирова-
нием (4.150) по г можно немедленно получить центральную
предельную теорему; более того, если потребуется, то у нас
4.3. Асимптотики из производящих функций
81
есть исчерпывающее описание асимптотического поведения
отдельных членов последовательности распределений, К со-
жалению, полученная выше формула страдает недостатком,
который характерен для центральных предельных теорем, а
именно ограниченностью интервала значений г. Обратите
внимание, что поскольку остаточный член в (4.150) является
многочленом от п, то оценка полезна только при г =
Это н не удивительно, поскольку мы довольно
небрежно выбрали контур интегрирования. Наш путь прохо-
дит вблизи самой низкой точки перевала только при г=0,
все более и более удаляясь от нее по мере увеличения г. Оче-
видным средством от подобного недуга мог бы служить выбор
иного контура интегрирования в случае, когда г превышает
Однако можно сдвинуть и само распределение, что за-
частую сделать проще, нежели повторять предыдущий вывод
для другого контура интегрирования, хотя оба способа в сущ-
ности одинаковы.
Коэффициент при zm в производящей функции g(z)n по-
лучается по формуле
Ю (g (г)") = (гт) (^-)" • (4.152)
Правая часть этого равенства может показаться ненужным
усложнением его левой части, поскольку в обеих частях тре-
буется выделить коэффициент при zm\ тем не менее правая
часть обладает дополнительной «степенью свободы», пред-
ставленной величиной ос, что позволяет сдвинуть среднее рас-
пределения, соответствующего g(az), поближе к tnjn. Это
можно сделать, выбирая а так, чтобы
g' (а) а = т
g (а) « ’
Установим в качестве простого примера коэффициент при
^.я/3
(4.154)
в производящей функции для биномиального распределения.
Интересующий нас коэффициент находится на расстоянии
много большем, чем л/п от среднего значения п/2; поэтому
равенство (4,150) бесполезно для пашей цели, если мы не
сдвинем среднее к п/3 посредством надлежащего выбора а:
g' (а) а _____ а 1
g (а) — 1 + а — 3 ’
(4.155)
откуда
1/2.
(4.156)
82
4. Асимптотический анализ
Распределение, соответствующее новой производящей функ-
ции
+ { г). (4.157)
имеет среднее р = 1 /2, стандартное отклонение с = '\/2/3
и последующие семиинварианты х3=2/27 и х$ =—2/27. Те-
перь можно воспользоваться равенствами (4.150) и (4.151)
при г — 0, получая
--/-)+ О О'6'2). (4.158)
\ •’ о / 2 v лп \ 24ч /
Умножая этот результат на присутствующий в равенстве
(4.152) множитель g(a)rt/rxrr-, в качестве решения исходной
задачи получаем оценку вероятности выпадения «орла» ровно
п/3 раз при п бросаниях монеты:
2я/3(|Г-4=.(1 --^ + 0(^)1 (4.159)
\ 4 J 2 д/яп V 24п /
Чтобы у читателя не создалось впечатления, что сдвиг
распределения по среднему является панацеей от всех интер-
вальных бед14), отмстим некоторые трудности, связанные с
его применением, В уравнении (4.155) нам повезло в том, что
а оказалась константой, В общем же случае а будет некото-
рым образом зависеть от п, что в свою очередь поставит в
зависимость от п среднее, стандартное отклонение и прочие
семиинварианты распределения. Установленный выше уси-
ленный вариант центральной предельной теоремы не допу-
скает подобной зависимости и должен быть видоизменен для
приведения его в соответствие с конкретными условиями.
В частности, весьма вероятно, что применение метода Лап-
ласа (отсекающего старьте и присоединяющего новые хвосты
к интегралу) будет создавать иные трудности. Тем не менее
сдвиг среднего все же полезен как ориентир при выводе
асимптотик, и читателю, возможно, будет интересно вывести
на этом пути асимптотическую формулу для чисел Стирлинга.
Задачи15)
1. [Задание на дом.] Покажите, что «перестановка, получаемая с по-
мощью стека» (а именно перестановка множества {1, 2, л},
такая, что нет таких индексов i <Z } <Z k, для которых а,- < < аг, см.
Кнут ,[1, упр, 2,2,1-5]), может быть охарактеризована в терминах таблиц,
инверсий. Найдите и докажите простое свойство таблиц инверсий С]С2...
... Сл, которое имеет место ттогда1Г‘), когда перестановка получается с по-
мощью стека.
2. (а) [10 очков] Сколько перестановок множества {1, 2, л} мож-
но отсортировать «методом пузырька», используя при этом не более двух
просмотров перестановки? Например;
исходная перестановка 3
первый просмотр 1
второй просмотр 1
1 2 9 6 4 5 8 7
23645879
23456789
(При пузырьковой сортировке на каждом просмотре Ki переставляется с
Л',-+1 ттогда, когда Кл > Ki+i при г #= 1, 2, ..,. п— 1.)
(Ь) [40 очков] Сколько перестановок множества {1, 2, л} можно
отсортировать с помощью «шсйкср-сортировки» за один двойной проход?
Например:
исходная перестановка 2
проход слева направо 2
проход справа налево I
7 3 1 4 6 9 8 5
3 1 4 6 7 8 5 9
2 3 4 5 6 7 8 9
(При шеикер-сортировке перестановка сортируется методом пузырька по-
переменно в обоих направлениях.)
3. Схема Дэйва Фергюсона для представления бинарных деревьев
(Кнут [I, упр. 2,3.1-37] 17)) потребовала бы хранения изображенного ниже
бинарного дерева поиска в пяти ячейках памяти, например, следующим об-
разом:
LOC INFO LINK
1 а 2
2 Ъ Л
3 с 4
4
5 d Л
Стандартную процедуру поиска со вставкой по дереву (Кнут [III, алго-
ритм 6.2.2Т]) можно очевидным образом приспособить для использования
и этого представления.
Пусть — вероятность того, что дерево бинарного поиска, построен-
ное путем вставки в первоначально пустое дерево п ключей в случайном,
порядке, будет занимать 2п-j- 1 —2k ячеек при представлении его по схе-
84
Задачи
ме Фергюсона. Обозначим через P,i{z) — X QpnkZ* соответствующую про-
2
изводящую функцию; в час]пости, Pi (z) = Р2 (г) = z и Р3 (z) ~ — z +
। I о
3
(а) [10 очков] Найдите дифференциальный оператор Ф„, такой, что
”п+1(г) = ф,.рт|(2) црл BiV4 п J.
(М [15 очков) [ I \ с гь Р> — !HiepaT(jp diiz, a U — оператор, который
полагает z равным 1, j;ik ч I DP/(iz)-= PF. {11 есть среднее значение ве-
личину k Покажите, чю >i-> ..рсдш-е качение можно выразить в виде
простой функции от л
(с) [25 очков) В при.юна-.спие Чен ги (Ь) <адачи найдите дисперсию
величии),। k как функцию о: ч
4- [100 очков] Расс мо! рим ,.шьл рцче>км<; пишущую машинку, которая
имеет ровно 40 клавиш иК и12 .0 i-i'jk.i' -'.пробел) (обратный ход)
(возврат каретки} и бесконечно длинную каретку Обезьяна печатает на-
обум с начала строки до тех гор. пока вдр\г не ударяет по клавише (воз-
врат Каретки) ; напуганная, она удирает доедать свой банан.
(а) Найдите производящую функцию G (z) = gn,zn, где —
число последовательностей из п ударов по клавишам, отпечатывающих
слово «аре» (обезьяна. — Персе.) в начале строки (и никаких других сим-
волов, кроме пробела и обратного хода). Вот, к примеру, одна из таких
последовательностей, состоящая из 12 ударов «ох> означает (обратный
ход)):
(пробел) р (ох) (ох) (ох) а (пробел) е<ох><ох>р<возврат каретки) ,
(Заметим, что нажатие на клавишу (обратный ход) в начале строки не
приводит ни к какому результату и что знаки могут многократно печа-
таться на одном и том же месте.) Не обязательно устанавливать G(z) в
явном виде —достаточно указать уравнения, которые однозначно опреде-
ляют эту функцию.
(Ь) Какова вероятность того, что обезьяна напечает подобным об-
разом слово «аре»? (Если удастся, дайте ваш ответ в виде явного вещест-
венного числа и объясните, как вы его получили.) [Пели вас не устраи-
вает подобная формулировка задачи, можете рассмотреть вероятность
того, что обезьяна напечатает некое четырехбуквенное слово.]
5. [50 очков] Найдите асимптотическое значение произведения
^0^n ( fe) с от1]осительной ошибкой порядка О(1/п) при п^-оо.
[Другими словами, ваш ответ должен иметь вид f(n) (1 4- О(1/п)) с «яв-
но» заданной функцией f.]
6- [100 очков] Будем называть положительное целое число п необыч-
ным (unusual. —Персе.), если его наибольший простой делитель не меньше
Таким образом, все простые числа необычны, так же как и произведе-
ния двух простых. (Число 1 в высшей степени необычно, поскольку это —
положительное целое число, для которого даггиое определение лишено вся-
кого смысла.)
Установите асимптотику количества необычных целых чисел п в ин-
тервале 1<п<Л' при У->ос с абсолютной ошибкой порядка
OW/(Iog#)2).
Указание. Посчитайте раздельно количество необычных целых чисел
в указанном интервале, наибольший простой делитель которых не превос-
ходит -у/у [за решение этой части задачи присуждается 35 очков] и пре-
восходит V-У [за решение этой части задачи присуждается 65 очков].
За правильное решение задачи с ошибкой порядка O(/V/(IogV)3) при-
суждаются дополнительные очки; однако, прежде чем пытаться их зарабо-
тать, советуем вначале решить задачу 7.
Задачи 85-
7. [150 очков-] Следующий алгоритм прохождения бинарного дерева
в прямом порядке (в оригинале «preorder»,—Перев.) идентичен алгоритму
2.3.1Т (Кнут [I]) для прохождения дерева во внутреннем порядке (inor-
der. — Перев.) с тем лишь отличием, что в данном случае в стек поме-
щается меньшее число элементов.
Р1. [Нач альная установка.] Очистить стек А и установить переменную свя-
зи Р Т.
Р2. [Р = А?] Если Р = А, то перейти к шагу Р5.
РЗ. [Попадание в Р.] (Сейчас Р указывает на непустое бинарное дерево,,
которое нужно пройти.) «Попасть» в NODE(P).
Р4. [Стек<^= RLINK(Р).] Если RLINK(P) А, то положить А
<=RL1NK.(P). т, е. поместить величину RLINK(P) в стек А, Затем
установить Р <^= LLINK(P) и вернуться к шагу Р2.
Р5. [Р<=стек.] Если стек А пуст, то выполнение алгоритма заканчивается;
в противном случае установить Р<|=А и вернуться к шагу РЗ. Ц
Задача аналогична упр. 2.3.1-11 из книги Кнута [I]: каково среднее
значение наибольшего размера стека, который может встретиться при вы-
полнении приведенного выше алгритма Р, считая, что все бинарные де-
ревья с п узлами равновероятны? Дайте ответ в виде функции от п с точ-
ностью до О (л_,/2 log п).
8. [50 очков] Продолжая анализ вторичного окучивания из разд. 3.4,
найдите «скользящий оператор» для который позволит вычислить
tAG^x). Кроме того, найдите аналог формулы (3.40), которая позволит
вычислить U2.П. Выразите Gmn (1) и Нтп(\) в виде «простых» функ-
ций от т, n, Pi и Р2, где
р i = (i + аа (i + .Ala ... (i + j£-TY
fe X. т ) \ т — 1 J \ m — п 4- 1 )
9. [Всего 150 очков, распределенных неодинаково по отдельным под-
задачам 18).] Однажды утром студент по имени Смышленый проснулся
с мыслью о новой разновидности бинарного дерева поиска. Из занятий
по информатике он знал о преимуществах «связывания в конце» (late bin-
ding. — Перев.), в связи с чем подумал: «Почему, собственно, я должен
использовать первый ключ для решения вопроса о том, как следует раз-
бивать остальные ключи? Не лучше ли отложить на время решение этого
вопроса и посмотреть вначале, каковы будут другие ключи?» Подбежав
К своему терминалу, студент быстренько подготовил файл с описанием но-
вой структуры данных, которую он решил назвать связанными в конце де-
ревьями (СК-деревьями), и отправился завтракать.
К сожалению, здесь пе место описывать дальнейшие похождения
Смышленого, в том числе историю (которая, вероятно, уже никогда не бу-
дет рассказана) о его роковой встрече в закусочной с любопытными се-
страми, которые поклялись нс останавливаться ни перед чем до тех пор,
пока не узнают его секрет. Давайте вместо этого сосредоточим паше вни-
мание на особенностях СК-деревьев, опуская подробности того, как нами
была получена эта информация.
В СК-дереве имеется два типа узлов: узлы разветвления и листья.
Узел разветвления содержит два ключа а и Ь, причем a<b, а также два
указателя Z и г на поддеревья. Все ключи в дереве I меньше или равны а,
а все ключи в дереве г больше или равны Ь. Такой узел можно обозначить
через (а : Ь) и подрисовать к нему поддеревья. Лист состоит из полной
записи, содержащей ключ о; такой узел можно обозначить через [а].
СК-деревья никогда не бывают пустыми — они «вырастают» из оди-
ночного узла (ростка). Левое поддерево узла разветвления (о : Ь) содер-
жит лист [а], а правое поддерево — лист [6]. Если необходимо вставить
в имеющееся С К-дере во новую запись с ключом х (предполагая, что ключ
86
Задачи
х отличен от ключей, уже вставленных в дерево), то надо действовать по
следующему правилу.
(1) Если СК-дерево состоит из листа [а] и если а С х, то заменить
Йна узел (а : х) с левым поддеревом [а] и правым поддеревом
. В случае х < а осуществить аналогичное перестроение, меняя
местами а и х.
(2) Если СК-дерево имеет корневой узел (а : Ь) и если х <Z а, то вста-
вить новую запись в левое поддерево, используя рекурсивно дан-
ное правило.
(3) Если СК-дерепо имеет корневой узел (а; Ь) и если х > Ь, то
вставить новую запись в правое поддерево, используя рекурсивно
данное правило.
(4) Если СК-дерево имеет корневой узел (а . Ь) и если а С х < Ь,
то надо подбросить «правильную» монетку. Если выпадет «орел»,
то заменить корень на узел Ь\ и вставить новую запись в ле-
вое поддерево; в противном случае заменить корень на узел
(о: х) и вставит!, новую запись в правое иодерево.
Таким образом, основная идея СК-Дерева состоит в слежении за диапазо-
ном ключей, по которым возможно разделение в корне, вместо того, чтобы
принимать поспешные решения по каждому отдельному ключу.
Цель настоящей задачи — научить кое-чему из анализа алгоритмов на
примере анализа средней суммарной длины внешних путей СК-деревьев;
при этом предполагается, что СК-деревья «вырастают» путем вставки в них
записей в случайном порядке. Суммарная длина внешних путей — это взя-
тая по всем листьям сумма расстояний от корня дерева до листа. Пусть
число листьев равно п; тогда при п = 1 суммарная длина внешних путей
равна всегда 0, при п 2 — всегда 2, при п = 3 — всегда 5, а при п = 4
она равна либо 8, либо 9.
(а) [15 очков] Предположим, что после вставки п ключей Xi,.. хп,
которые образуют случайную перестановку множества {1, ..., п), корнем
СК-Дерева является узел (ft: 6 4-1). (Другими словами, вначале СК-де-
рево состоит из узла [xj, потом вставляется ключ х2 и т, д., пока после
вставки ключа хч дерево не «обрастет» п листьями.) Левое поддерево кор-
ня представляет собой СК-дерево, которое образовано перестановкой
уг... уп множества {], k}, состоящей яз ключей Xi fe, а правое под-
дерево образовано перестановкой множества {k 4- Е «}, со-
стоящей из остальных ключей хн
Докажите, что t/j ... уь не являются равномерно распределенными слу-
чайными перестановками множества {1, .k}-. если иерастановка У\..,уь
содержит t левосторонних максимумов, то ее вероятность равна вероятно-
сти тождественной перестановки умноженной на 2*~*. Аналогично
перестановки гч ... также не являются равномерно распределенными:
их распределение зависит от левосторонних минимумов.
(Ь) [15 очков] Пусть рпь — вероятность того, что после вставки л
ключей в порядке, соответствующем равномерному распределению, кор-
нем СК-дерева будет узел (k : k1). Найдите формулу для pnfe,
(с) [20 очков] Будем говорить, что перестановки множества {I, ...
.п} являются ^-распределенными. если нее перестановки равновероят-
ны; что эти перестановки являются ^-распределенными, если их вероятно-
сти пропорциональны 2_/, где t — число левосторонних максимумов; что
эти перестановки являются ^-распределенными, если их вероятности про-
порциональны 2’л. где s — число левосторонних минимумов; наконец, что
они являются В-распределенными, если их вероятности пропорциональны
2-s-<
Подзадача (а) показывает, что левые и правые поддеревья СК-де-
ревьев, построенные по ^-распределенным перестановкам ключей, являются
соответственно L- и ^-распределенными. Докажите, что если мы начинаем
Задачи
87
с L-t R- или В-распределенпых перестановок ключей, то поддеревья будут
соответствовать (L, В)-, (В, /?) или (В, В)-распределенным перестанов-
кам ключей,
(d) [5 очков] Пусть Urt, Ln, Rn и Вп— средние суммарные длины
внешних путей СК-дсревьев, построенных по (J-, L-, R- и В-распределен-
ным перестановкам ключей. Докажите, что при 2
1 С %<га
Ln = " + X ^nk (Lk + Bn-k)’
1 k<n
i k •<«
В„="+ X 'nk(Bk+B «-!.)•
I fe <n
где qnk и rnk — соответственно вероятности того, что L- и В-распределен-
ные СК-деревья имеют своим корнем узел (fe ; k 4- 1),
(е) [20 очков] Докажите, что qnk = ( ) ( П~_У% ) ” rnk =
= l/(rt — 1) при 1 k < п.
(f) [5 очков] Докажите, что Вп = 2пНп — '2п,
(g) ,[20 очков] Докажите, что
У, ^nkBn-k ='5 (Л+ ~2 ) (^+1/2 ~ /ZS/2)‘
I < k<in
{Указание, Покажите, что равенство (1.47) справедливо и при неце-
лых т.]
(h) [25 очков] Найдите решение рекуррентного соотношения для
которое фигурирует в подзадаче (d), используя «репертуарный» метод ре-
шения рекуррентных уравнений видах^ = ап~{ Ei< k^n ^nkxk‘
(i) [25 очков] Докажите, что Un = 4- II п 4- п ——.
10, [75 очков] Найдите асимптотическое значение суммы Srt =
= — k) с точностью до членов порядка О(я“3/2).
11. [Всего 100 очков] Пусть ап — число путей из точки (0, 0) в точку
(п, п) решетки, причем на каждом шаге допускается переход из точки
(1, /) в одну из точек (t. /4- I), (i 4~ h /) или (г 4- 1, /4- 1)- Таким обра-
зом, (йс„ й], а2, йз, ,.= (1,3, 13, 63, .,,),
(а) [50 очков] Пусть Д (а) = Используя формулу (4.125), до-
кажите, что Д (z) = 1/V1 — 62 4- г2,
(Ь) [50 очков] Найдите асимптотическое выражение для коэффициен-
тов ай при п ^-оо с явным указанием констант с, р и 0, таких, что ап =
= ст:р№ 4- О(гф~|0'1).
12. [Всего 125 очков] Некий профессор принимает экзамен, состоящий
из бесконечного числа задач. Прежде чем приступить к решению очеред-
ной задачи, студент должен полностью решить все предшествующие за-
дачи, ибо профессор прекращает экзаменовать, как только обнаруживает
ошибку. Каждый студент независимо от других студентов и номера задачи
может с вероятностью р правильно решить любую отдельную задачу.
Например, при р = 1/2 вероятность правильного решения ровно п 0
задач равна 2-л-1.
88
Задачи
Решившему наибольшее число задач профессор ставит А+ в том слу-
чае, если только один студент набирает максимальное число очков; в про-
тивном случае никто из сдающих экзамен не получает /4+.
(а) [25 очков] Выпишите выражение для вероятности получения 4+
кем-то из /? студен ген, с азюшит экзамен. (Ваше решение может быть
представлено в виде суммы, i а к как, по-видимому, требуемая вероятность
не выражается в «замкнутой форме».)
(Ь) [300 очков] Установите при фиксированном 0 < р < 1 и п ос
асимптотическое поведение вероятности получения А+ кем-то из п студен-
тов, сдаюших экзамен.
Важное замечание Для того чтобы вам было зачтено какое-нибудь
решение части (М за инн. необходимо правильно решить часть (а). Пре-
жде чем вы воз в метео, за асимптотическое решение, удостоверьтесь, что
при а = 2 ваша формула дает значение 2р(1 -ф р) ~*, а при п = 3 — значе-
ние Зр(1 -ф р2) (1 4- р) (1 -4- Р -ф рД
13. Как показал результат решения одной из задач недавнего средне-
семестрового экзамена, средняя длина пути СК-деревьев примерно такая
же, как и у обычных бинарных деревьев поиска.
Однако вскоре после экзамена из наших источников стало известно,
что студента Смышленого не разочаровали результаты анализа СК-де-
ревьев. Согласно заслуживающим доверия сообщениям, он решил попы-
таться спасти свое детище путем включения в каждый узел дополнитель-
ной информации.
Узлы новой структуры данных Смышленого, которую он назвал УСЛ-
деревьями (усовершенствованные связанные в конце деревья), содержат
поле «размера», информирующее о числе листьев поддерева с корнем в
данном узле. В случае раздвоения дерева в корне ключ вставляется в
меньшее на данный момент поддерево. (Если размеры поддеревьев одина-
ковы, то, как и на шаге 4 построения СК-деревьев, принимается случайное
решение).
Цель настоящей задачи—провести анализ нового алгоритма Смышле-
ного «на самом высоком уровне». Пусть pqk есть вероятность того, что по-
сле вставки ключей, являющихся перестановкой множества {1, ..., л), кор-
нем дерева будет узел (k: k -ф 1). (Предполагается, что все перестановки
значений х равновероятны: вначале УСК-дерево состоит из одного ключа
Xi, в которое затем один за другим вставляются ключи х2> х„). Пусть
Рпь = n\pnk\ тогда нетрудно убедиться, что при 1 < л и 1 п 6
числа Рпц принимают следующие значения;
п = 2: 2
п = 3: 3
д =- 4: 6 12 6
и = 5: 18 42 42 18
п = 6: 72 162 52 162 72
(а) Установите рекуррентное соотношение, которому удовлетворяют
числа Pnk.
(b) Пусть = 2Рпк max (А, п — k)/(k} (п — &)!), так что имеем сле-
дующую треугольную таблицу значений Q„k’.
п = 2-. 4
п = 3: 6 6
п = 4; 6 12 6
и = 5: 6 21 21
п = 6: 6 27 42
6
27
6
Задачи
89
Покажите, что для большинства значений п и k числа Qr,tt удовлетворяют
тому же рекуррентному соотношению, что и числа, составляющие тре-
угольник Паскаля, т. е. С/.,* = ,) Найдите все исключе-
ния из этого правила и установите рекуррентное соотношение, справедли-
вое при исключенных значениях.
(с) Пусть ah = Q(2k)k, Покажите, что при k > 1
Е2/ + 1
/
1 <k
afk-r
где Ck—число бинарных деревьев с п внешними узлами,
d) Пусть В (z) = у (1 + V1 ~ 4г) и С (г) = у (1 — V1 — 4г), так что
В (г) 4- С (г) =1, В (г) — С (г) = дЛ — 4г, В (г) С (г) = z и С (г)2 =
= С (z) — z; напомним, что С (г) = с2г 4- сгг2 4- сгг3 4- • • • является про-
изводящей функцией для числа бинарных деревьев. Пусть Д = a^k, и
введем в рассмотрение производящую функцию F{z] = fxz 4- f2z2 4- ... .
Преобразуйте рекуррентное соотношение из части (с) задачи в дифферен-
циальное уравнение для F и решите последнее с получением гц в «замк-
нутой форме». [Подсказка'. покажите, что производная В(г)/?(г) имеет
простой вид.]
(е) Примените рекуррентное соотношение из части (Ь) задачи к про-
изводящей функции Q (w, г) Qnkwkzn~k и воспользуйтесь значе-
ниями ай, найденными в части (d) задачи, чтобы вывести формулы для
Q(w, г) в виде явной функции от ж и г.
(f) Найдите «простое» выражение для коэффициента при &|'1г'1+г в сте-
пенном разложении функции л/\ — 4жг/(1 — w — z) при г>0.
[Указание. Рассмотрите эту задачу при фиксированном г и перемен-
ном п. Можно по желанию воспользоваться тождеством С (z)s/Vl — 4г =
= zEj ( 0 zfl+S И Фактами 0 ФУ}1КЫИЯХ В(г} ч С(г)> установлен-
ными в части (d) задачи.]
(g) Исходя из решения предыдущих частей задачи, покажите, что
1 / k 4- 1 k
2 \п — k п~ k + \
1 , 2k . 1
----р ------ при 1 < k < — ц,
2п п (ц — I) 2
Замечание. НЕдостаточно доказать эту или эквивалентную ей формулу
просто по индукции. НАДО пояснить, как вы могли бы самостоятельно
найти это решение некоторым систематическим путем без счастливых оза-
рений.
5 ЗлК. 259
Решения задач
1. Данную задачу предполагалось поместить в книгу Кнута [III] в
качесчве упр. 5 1.1-21; на самом же деле в этой книге вместо упражнения
содержится ее решение!
2. (а) В соответствии с авали юм «метода пузырька», приведенным в
разд. 5.2.2 книги Кнута [111], надо подсчитать, сколько имеется таблиц
инверсий bi... b„, таких, что все b < 2 Ясно, что при каждом п. 2 су-
ществует 3';~2'2 таких таблиц
(Ь) Назовем таблицу инверсий b . h идийной (easy. — Перев.), если
соответствующую нерест а ковку мол. ио отсортировать за одип двойной
шейкер-проход. Оказывает с я. ч го имеете я весьма привлекательный способ
описания подобных таблиц. Таблица инверсий Ь\ . -. Ь.г1 является удобной
ттогда, когда выполняется одно m слоях юшнх условий:
bt =0 и ь2 •. bn удобна,
&t = 1 и Ьг . ьп удобна,
bi =2 и Ьг $ 2 1 и Ь3 ... Ьп удобна,
&t = 3 и ь2 % 1 и Ь3 1 ... Ьп удобна,
hj = п — 1 и 1 и ... и bn-\ 1 и Ьп удобна,
[Набросок доказательства. Допустим, что b} = k > 0. После первого
прохода перестановки слева направо имеется k—I инверсий элемента 1,
и на этом этапе перестановка должна начинаться с 2...&1, чтобы ее мож-
но было отсортировать за один обратный проход.]
Итак, мы получаем, что при 2 число удобных перестановок удо-
влетворяет рекуррентному соотношению
Xfi =^= Хп—1 4~ x.i-j 4~ 2хц—2 4" 4хд—з 4“ > > -»
где X] = 1 и Xj = 0 при / < 0. Отсюда следует, что xn+i—xn^xn—xn_lt
т. е, Хц+| = 4хп — 2xn~i. Решением этого лилейного рекуррентного соот-
ношения является хп =-£- ((2 4- V2 1 + (2 — д/2 )” '),
Другое решение данной задачи содержится в упражнениях 5.4.8-8, 9
из книги Кнута [III].
3. Если дерево содержит k «узлов-почек», т. е. узлов, каждый из кото-
рых имеет по два внешних узла-листа, то для представления дерева по
схеме Фергюсона требуется 2п 4- 1 — 2k ячеек: одна — для хранения корня
и 2(л — k) —для узлов-листьев. При переходе от Рп к РлП значение k не
изменяется, если новый узел заменяет один из 2k листьев k узлов-почек;
в противном случае k увеличивается на единицу. Следовательно,
k
Соответствующим дифференциальным оператором является оператор
2
Фд = г]—" >, ; г (1 — z) Dt так что
п -р 1
Рд (г) = Фл_! ... Ф0Р0 (г), где Ро (z) « 1.
Решения задач
91
Для установления среднего значения хп достаточно заметить, что
о
/)(!>„==[ +—__((1 _22) D±z(\ -z)D*),
U D®n = U + UD + —(- UD) = U + -Ц4- UD,
«4-1 п 4* I
Отсюда хя+1 = U DPn + i (z) = (U 4- ---j -у Ud) Рп (г) — 1 4- Д 7 ! хп,
\ « 4" 1 / «. 4” 1
а эго рекуррентное соотношение имеет решение хп = (« 4- П/З при 0 2.
Аналогично для установления дисперсии мы находим, что
= 2 UD _j_ UD2r
п 4' i n 4“ i
Положим !/n = P/i (1), так что
_ н — I , « — 3 2 ., . « — 3
= 2 Д+Тx" + тгг9* = T<" ~ '> + Д+Г»»'
Применяя, как на с. 21, суммирующий множитель, получаем zn-^.I =»
4 2 , 4 42,54 4
= (л 4-1) г/К4-1=лг (« 4- 0 (« — I) 4- п (AI + 1) 4--г («4-1) 4-’п
О DO
2 б 4 5 2
и z3 — 0. Поэтому zK = ——(д 4- 1)“ 4--р-(« 4- 1)~иуГ1=Тй («4-1) («—4)+
1о 10 1о
4 „
-Ь-гё-(« 4-1) при п > 4. Итак, дисперсия равна уГ1 -|- хп — х^ — (« + 1) X
L О
(9 4 11 \ 9
78 («-«l+fg +Т-д-(» + 1))—45 («+!) при »>4.
.[Замечание. Среднее и дисперсию можно было бы также установить
с. помощью совершенно иного подхода, используя то, что может быть на-
звано «индукцией с другого конца». Рассматривая различные варианты
выбора корневых узлов, получаем рекуррентное соотношение
РЛ(г)=~(Р0(г)Рп_1(г) + Р, (?) Ра_г (г) 4- ... 4- Pn—i (г) Ра (г))
при п > 2, Пусть Р (да) = >0 ®прп (г)'> тогда данное рекуррентное со-
отношение сводится к дифференциальному уравнению Р' = Р2 4- Р\ (д) —
— Ро (г)2 = Рг 4- -s — 1, которое имеет решение
----- / ----- ] \ 1 — (г — 1) Г (да)
Р (и,) = - 1 tg [ да д/z — I + arctg ---•) =-----------—-------,
\ д/z — 1 / 1 — Т (да)
где Г (да) = (tg да д/г — 1)/д/г — 1- Переписывая это решение так, чтобы
избавиться от радикалов, получаем
1+ Е |)‘+,<о’Л+1
П t , fe >0_______________
i-Е ^+iO-i>s®“+l
fe>0
где /2ft+1x2A4'1 = tg х.Полученное решение мож:но разложить вряд
>0 1 2
по степеням 1; зная значения ti= 1, /а —др получаем
92
Решения задач
','Я-т^-(ж-^+М!2-" +
+ (•_1_____!_+ J _ <L~j
к 9(1 - к-р 5(1 - К‘12 9 45
Итак, £/>„(1)^= 1/(1 - Гг). £ Р/; = - и)*2 + -1-(ш- 1),
а 2*2 7f?'п является коэффициентом при (г—I)3, и, сделав еще
несколько тагов, мы иго дем д ь лерсич) Однако этот подход не исполь-
зует операторов, как пин ipiooH.iaa гыс1,;uhhjk,i задачи,]
4. Удобнее itvicib дело ; j ( ь т не i , s«ц t функцией G(Xj, Хз, %з), которая
допускает леча и, н по шпни i т <ц,цмщ помимо знаков обратного
хода и возврата каретки. 'I о; да, vOia.K. ,» пцпг- ицп включения и исключе-
ния, производящая функция
G = </(2,2,2) — G(2.2,l) - G(2.1,2) - G(1.2,2) + G(2,1,l) ф- G(1,2,1) ф-
ф-G(l,1,2) — G( 1,1,1)
перечисляет последовательности знаков, которые включают в себя все три
буквы — «а», «рз>, «ез>.
Чтобы избежать бесконечного числа уравнений, рассмотрим вначале
множество всех последовательностей знаков пробела и обратного хода,
которые начинаются в некоторой позиции i>3 и заканчиваются в пози-
ции i—lc переходом левее i-й позиции только на самом последнем ударе.
Подобные последовательности однозначно описываются бесконтекстной
грамматикой
L <- (обратный ход) ] (пробел) LL,
Следовательно, функция
£(z) = г4- г£(г)г
является производящей функцией {z'°^jos£} и
£ (г) = (1 - V1 - 4z2)/(2z) = г ф- г3 + 2г; + 5z7 ф- ... .
Аналогично пусть производящая функция Q(z) перечисляет последо-
вательности знаков пробела и обратного хода, которые начинаются в не-
которой позиции I > 3, но никогда не переходят левее i-й позиции. Рас-
смотрение однозначной грамматики
Q (пусто) | (пробел) Q | (пробел) LQ
показывает, что
Q (z) = 1 ф- zQ (z) ф- zL (z) Q (z),
Q(z) = 1/(1 -z-zL (z))r= 1 + z _j_ 2z3 + 3z3 + 6z4 4- ....
[Между прочим, с помощью простых алгебраических преобразований
можно установить формулу
Q{z) = (1 — £(г) )/(1 — 2г),
которая эквивалентна равенству Q(z) ф-£(г) = I 4-2zQ(z). Последнее ра-
венство непосредственно следует из того факта, что каждая последователь-
ность из Q или L либо пуста, либо имеет вид о (пробел) или ст (обратный
ход), где о е Q.]
Пусть теперь Gj(z)—производящая функция, соответствующая слу-
чаю, когда на пишущей машинке начинают печатать с i-й позиции от ле-
вого края, так что искомая функция G(z} — Go(z). Рассматривая после-
довательности знаков4 которые начинаются со знака (возврат каретки),
Решения задач
93
(обратный ход) или с какого-нибудь другого, имеем
Go (z) = г 4- zGo (z) + x^Gj (г),
Gi (z) = z + zG i (z) 4- x2zG2 (z),
G2 (z) = z -j- zGj (z) + x3zG3 (z).
Кроме того,
Gs(z) = L(z)Gt(z) +Q(z)z,
поскольку каждая последовательность знаков, начинающаяся в 4-й пози-
ции, либо возвращается в 3-ю позицию, либо нет. Решением этой трех-
диагопалъной системы линейных уравнений и является требуемая произво-
дящая функция G(xu Л'г, х3).
Вероятность любой заданной последовательности, состоящей из п уда-
ров но клавишам и закапчивающейся первым ударом по клавише (возврат
каретки), равна 1/40’\ и такие последовательности являются взаимно ис-
ключающими, Поэтому вероятность отпечатывания слова «аре» равна
G(1/40),
Теперь мы получили все, чю необходимо для ответов иа поставлен-
ные вопросы, однако представляется полезным продвинуться дальше и
упростить полученные формулы, обратившись к системе MACSYMA (см.
прилагаемый листинг),
[Система MACSYMA разработана группой Math lab в МТИ по контрак-
ту с агентствами U.S. Energy Research and Development (контракт E (11-
l)-3070) и National Aeronautic and Space Administration (субсидия NSG
1323) l9).]
Оказывается, что
= XjX2x3z* 4Q (z) — (x,z 4- 1) x3z2L (z) 4- (Xi — 1) x2z3 + xYz3 + z
(xtz3 4- z2 — z) x3L (z) 4- x2z3 — (xj 4- x2) z2 — z 4- 1 *
и после устранения x, методом включеия и исключения производящая
функция для «аре»-последовательностей начинается так:
z4 + 3z5 4- 14- 44z7 4- 163z8 4- 472z9 4- 1550z’° 4-,.. .
Точное значение искомой вероятности
299960985906139337267285127509.9904646499040221 д/399
— 59877588713530290411629940237569556287667865416
93355082549464520980187663115368403895040545354710
что приблизительно равно 0000004238793706620676.
Как указал Жорж Столфи, можно было бы предусмотреть возмож-
ность печати во второй позиции буквы «о», поскольку па многих машинках
она входит в начертание буквы «р». В этом случае ответ был бы таким:
G = G (2, 3, 2) - G (2, 3, 1) — G (2, 2, 2) - G (1, 3, 2) 4-
4- G (2, 2, 1) 4- G (1, 3, 1) 4- G (1, 2, 2) - G (I, 2, 1) =
= z4 4- 3z5 4- 17z6 4- 52zr 4- 2l5zs 4- 664z9 4- 24O6z10 + .. *
и вероятность отпечатывания слова «аре» увеличилась бы, став приблизи-
тельно равной ,0000004244.
5. Итак, In ГТ f 2 1 ~ (In л! — In fe! — In (л — *)!) =
\ « / *-Jo<k^n
По Ф°РмУле суммирования
94
Решения задач
васвулва
This is MACSYMA 292
FIX292 14 DSK UACSYW being loaded
Loading dona
(Cl) solve(Lsi*z*L**2,L) ;
SOLVE FASL DSK MACSYW being loaded
Loading done
Solution.
2
SQRT(1 -42) - i
(El) L -------------------------
* 2 Z
2
SQRT(1 - 4 Z ) ♦ 1
(E2) L ------------------"
2 Z
(02) [El, E2J
CC3) solve(Q=l+z*Q*z*L*Q,Q);
Solution:
(E3)
(D3)
(C4) algebraic:true;
(D4)
(СБ) gO=z4z*gO+xi+z*gl;
(D6)
(Св) gl=z+z»g0+x2*Z*g2;
(D6)
(C7) g2=z+z*gl*x3*z*g3;
(07)
(C8) g3=L»g2+z*Q;
(D8)
(C9) 5ь1¥е([а5,<Ю,Й7,<18]
Q =-----------------
(L ♦ 1) Z - 1
[E3]
TRUE
GO a G1 Xi Z + CO Z + 2
G1 = C2 X2 Z * CO Z + Z
C2 = G3 X3 Z + G1 Z ♦ Z
G3 = Q Z + G2 U
[g0,glrg2,g3]>
95
Решения задач
Solution
4 3 2
Q Х2 Z + ((- Q - L) XI Q X2) Z ~ QZ ♦ (Q ♦ L) Z
(E9) G3 = -----------------------------------------------------
3 2
(L XI X3 + X2) Z 4 (L X3 - X2 - XI) Z + (- L X3 - 1) Z + 1
4 3 2
Q X2 X3 Z + X2 (1 - Q X3) Z + (L X3 - X2) Z - Z
(E10) Cl -- - —--------------------------------------------------
3 2
(L XI X3 4 X2) Z + (L X3 - X2 - XI) Z + (- L X3 - 1) Z + i
4 3 2
Q XI X3 Z + (Q X3 + XI) Z ~ Q X3 Z - Z
(Ell) G2 -------------------------------------------------------------
3 2
(L Xi X3 + X2) Z * (L X3 - X2 - XI) Z + (- L X3 - 1) Z + i
4 3 2
Q Xi X2 X3 Z * CXI (X2 - L X3) - X2) Z + (XI - L X3) Z + Z
(E12) GO = —---------------------------------------——...............
3 2
(L XI X3 + X2) Z + (L X3 - X2 - XI) Z + (- L X3 - 1) Z + i
(D12) t[E9, E1O, Ell, E12)] f
(C13) g(jd,x2,x3);=([t],t:ratsimp(ev(gO,e!2,e3,eval)),ratBimp(flv(t,ei)));
(D13) G(X1. X2, X3) := С[T], T : RATSIMPfEV(GO, E12, E3, EVAL)),
RATSIMP(EY(L El))>
(C14> g (1,1,1);
Z
(Di4) ---------
2 Z - 1
(С1Б) buBwer: g(2,2,2)-g(2,2,1)-gC2,1,2)-g(l,2,2)
*g(2,1,1)+g(l,2,1)+g(l,1,2)-g(i,l,i);
<015)
7 264 65432
8 Z 4 SORt’CI - 4 Z ) (8 Z - 4 Z ) - 12 Z "4Z - 4 Z + 6Z + Z - Z
7 6 5 4 3 2
40 Z - 4 Z - 32 Z "12Z *26Z -32 - 4Z + 1
96
Решения задач
7 2654 6,543
* (18 2 * SQRTC1 - 4 Z ) (2 2 + 22 - 2 2 ) + 5 Z - 19 Z - 6 Z +8Z
2 7 6 5 * 3 2
+ 2 - 2)/(34 Z + 11 2 -44Z - 92 + 26 2 - 3 Z “42 + 1)
2 F 4 65432
8 (1 - 4 2 ) (4 2 - 2 Z ) 8Z+4Z-9Z+4Z+2Z-Z
7 6 5 4 3 2
16 2 -82 -22 -19 2 +20 2 - Z -4Z+1
7 2654 65 432
- (6 Z + SQRTC1 - 4 Z ) (Z + 2 - Z ) + 5 2 - 42 - 10 2 + 5 Z + 2 Z
7 5 ч 3 2
- 2)/(10 2 + 7 -14 2 -16 Z + 20 2 - Z -42+ il
5 2 4 3 4 3 2
4 Z + SQRT(1 -42) (Z - Z ) - 8 2 +32 +2Z - Z
5 4 3 2
10 Z *21 2 +14 2 + Z - 4Z + 1
3 2,432 2 23
2 Z 8037(1 -4Z)+4Z-4Z-Z+Z 2 SQRT(1 - 4 Z ) - 4 Z + Z
- +--------------------------------------------.-------------------
5 4 3 2 3 2
16 Z -24Z + 14 Z + Z -42 + 1 10 Z - 5 Z - 2Z + 1
Z
+ -------
2 Z * 1
(016) taylor («ew«r, z.0,10);
HAYAT FASL DSK MACSYM being loaded
Loading done
4 5 6 7 8 9 1&
(D16)/T/ Z + 3 Z + 15 Z + 44 Z + 163 2 + 472 Z + 1550 2 + , . .
(C17) ratainp (av (anawer, 51=1/40)) ;
(017) (2999609859061393872672851275099904646499040221 SORT(399)
* 59877588713530290411629940237569556267667865416)
/$3355082549464520960187663115368403895040545354710
(018) factor(dtnwOQ) j
Решения задач
97
<В1‘8) 2 3 5 И 17 19 23 29 S3 S9 79 167 Й11 4S7 6673 7019-9199 20773 28559
1294357X41
(С19) bfloat(dl7);
FLOAT FASL DSK MACSYM being loaded
Loading done
(919) 4.2337937066200766-7
(C20) tlme(dl4,dl5,dl7) ;
TIME or [TOTALTIME, GCTIME] in msecs.;
(020) [[1813, 914], [13204, Б191], [ISM, 537]J
Эйлера (ср. Кнут [I], улр, 1,2.11,2-7 и равенство 1.2.11,2-18) это равно
2 Q-n2ln п 4-у nln п + -^1п п — у^2+ 1п А + О (^)) —
— (л+ 1)(л1пл 4-у In п — n + In У‘2л +-4— 4-0 “
= 4- п2 —п In п + (1 — In а —т 'п д------------пт 4* 2 1° Л —
2 2 о 12
— In л/Ол + О (л-1),
где А — постоянная Глейшера, Поскольку 1п .4 —(у — (2) (£ (2) 4~
4- In 2л)) — выражение, которое может быть установлено с помощью
«формулы Абеля — Плана», приведенной в книге Олвера [74, § 8.3.3] — , то
ответ таков:
ехр
—-п1 —^-п In п 4- Q —In 2л
" - 4 |П П -12 +
+1V - ?' (2)/п! - 1 In 2п) (1 + О (1 /л)).
6. (а) Необычные числа n<LN с наибольшим простым делителем
p<^N суть р чисел р, 2р, р2. Следовательно, имеется р
необычных чисел типа (а). Это равно
л/n л/n л/n
$ idn(t') = t dO 0/(log/)10 :J),
Vr уг л/т
t
где L (f) = du/ln и. Второй интеграл есть
2
O(V?V V^/(log Vjv)10M)) 4- 0
ЛГ1/3
J (*/(logf)1000) dt
V7
4- о
4-
Wl/2
0/(logO,Gt)0)^
Wl/3
98
Решения задач
что составляет О Л/) 100°), Первый интеграл равен
$ i d//In t = dH/ln и = L (TV)
VT 2
(так что имеет место любопытное соотношение Хр^^/дг Р
Вычислением по частям этот интеграл сводится к хорошо известной асим-
птотической формуле
JV/ln Л' + A7(ln .V)2 4- 2! .'V/(ln Л')3 4- . •.
,.. + 998! N/( In Л/)909 -j- о (tf/dog Д')1000).
(b) Необычные числа п V с наибольшим простым делителем р > л/N
суть [V/pJ чисел р, 2р, , . [V/nj р. Следовательно, имеется
со
необычных чисел типа (Ь), что равно J lA'7/р/л, (/) == [N/t\ dL (t)-\-
ОО ‘'J’N •y/N
+ J LW/^l dO (Z/log 0im. Второй интеграл есть
00
о (/v/Oog VaO!00°) 4- о
Г dt
t (log O'000
,v
что составляет О (/V/(Iog jV)999), Первый интеграл равен
где {х} = х — [х] и и = JV/Л Поскольку In In N — In In = In 2, получаем
выражение
.. С ( Inu \'2 j
Интеграл \ I —-—1 au существует, поэтому О-член можно отбросить,
1
Вычислим
N it-j- 1
f <«) _ V С (« - k) du , „ f 1
J »2 _ L } 1? +uV/vJ"'
i k
= Z (!n^ + ,)-"lft-T^r) + 0(^) =
icfe<v7v
— In Vw — H1 + О (l/V^) = 1 — у + О (Л'-1''2).
Решения задач
99
Аналогично вычисляется (за решение этой части задачи мы обещали «до-
полнительную плату», которую никто не получил)
f {«} In и du
j ~~
= ‘ 1„аулг+1пулг_я +,_ у М* + В +о7Де^
2 л/л fe j- 1 \ a/jV
1 V^v
Пусть
£ (1 + е) = — 4- уо + YiS + —Ь ..
в соответствии с формулой из ответа к упр. 6,1-8 (Кнут [Ш])
Е -го+е)+^-+О(»,--).
1 k т
Разлагая обе части этого равенства в ряд по степеням е и приравнивая
коэффициенты при одинаковых степенях, получаем
V (In й)г _ (In ш)г+1 , , п ((1П т)г>|
L ~I-----------7+Т~ + (-1) ^+0(—)
1 fn
Таким образом, \ {«} In и du/u? = 1 4- Y1 — у0 4- О (Л^ 1/2 log -V), и сле-
довательно, имеется N In 2 — (у — 1) W/ln /V4-(y - I - Yi) Л/7(1п А)2 4-
4- О (A//(Iog Д')3) необычных целых чисел типа (Ь); теперь мы видим, что
необычные числа не столь уж необычны!
7. Назовем максимальный размер стека, необходимый для прохожде-
ния бинарного дерева с помощью алгоритма Р, «вышиной» (hite.— Пе-
рев.), а аналогичную величину дчи алгоритма Т ~ «высотой» (в оригинале
height. — Перев.), Обозначим через a!ik число бинарных деревьев с п уз-
лами, вышина которых не превосходит k. Если gk (г) = то
go (г) = 1/(1—г) и gk (?) = 1 + zgk-i (г) gk (г) 4* zgk (г) — zgk~i (z).
(Первый член в этом выражении соответствует пустому бинарному дереву,
следующий член соответствует бинарному дереву, левое поддерево кото-
рого имеет вышину <zk, а правое поддерево имеет вышину и, наконец,
два последних члена соответствуют бинарному дереву, левое поддерево
которого имеет вышину ~ k, а правое поддерево пусто.) Таким образом,
5Ь (2} = l-zgfe-l(z) =3_________!_______
1 — Zgk-i \Z) — z z
1 — Zgk-1 (Z)
откуда немедленно следует, что g(z) = (z), Исходя из этого удиви-
тельного соотношения, можно сделать вывод, что число бинарных деревьев
вышины k такое же, как и число бинарных деревьев высоты 2k или 2А4- !
[Интересно найти взаимно однозначное соответствие между этими двумя
множествами деревьев; см. замечание в конце решения задачи. Нам не
хотелось бы лишать вас удовольствия найти данное соответствие само-
стоятельно, что представляет собой весьма изящную небольшую задачку.]
Бинарное дерево высоты h соответствует бинарному дереву вышины h
100
Решения задач
или А—д’- Поэтому следует ожидать, что средняя вышина будет со-
ставлять приблизительно половину сродней высоты, минус 1/4. На самом
доле так оно и есть, однако целью нашей задачи является строгое анали-
тическое доказательство этого факта.
Согласно улр. 2.3 1-11 из книги Киста [I] и статье де Брейна. Кнута
и Райса (72[ = щ...,, , нть коэффициент при ця в разложении
_ ч ! J
(!-«)(] + ——--^77,
] — и 1
а ЬП!г = a-tn есть коэффициент при и’’*1 в разложении
(1 — и)! (1 ф г/)а” —-———
1 - и-к + 1
Таким образом, = £ к {k (ank - ап _ h) = £ k п bnk есть коэффи-
циент при un+1 в
гЪмТ'
k 5=0
Для удобства добавим коэффициент = апп, так что sn ф- йлп есть
коэффициент при иГ1+1 в разложении
(1-и)2(1 + йГ У —
Z-J 1 — t?
k нечетно
Последняя сумма совпадает с суммой в уравнении (23) из цитированной
выше статьи, за исключением того, что d(k) теперь заменено на г? (А) —
число нечетных делителей k. Имеем
У d [k)!kz = г (г) С £ 1/&4 = 5 (г) (5 (г) - 2~*г (г));
k 1 \А нечетно /
следовательно, sn + апп можно получить методом из указанной выше
статьи, за исключением того, что там в интеграле (29) присутствует до-
полнительный множитель (1 — 26-2г), Поэтому вычет в точке двойного по-
люса становится равным
п0+п/2г (4<г>+1)(4 (4(6+i))+^v+Tin2))’
а в точке г = —A oei равен значению формулы (31) статьи, умноженному
на 1 — 22А+6. Искомый ответ таков:
— 1 4- (ft + 1) ((—2/ft) go (n) 4- (4/ft2) g2 (п) + О (n~312 log ft)) =
= 7j- -у/nn —14-0 (ft-1'*2 log re).
Обещанное выше соответствие описывается следующей рекурсивной
процедурой:
Решения задач
101
ref (node; procedure transform (ref (node) value p);
begin ref (node) q,r;
If p = null then return(null);
r- left(p). lcft(jp) * transform(right(p)); right (p)null;
if v null then return (p);
9 «- r. while true do
begin left (q) * transform (left (9));
if right (q) = null then done;
q* right (/? I;
end;
right (q) 1- p; return (r):
end
Можно показать, что преобразованное дерево обладает следующим
сильным свойством Пусть s — высота стека в тот момент, когда алгоритм
Т помещает в свой стек указатель на некоторый узел дерева В, и пусть
s' —- высота стека после шага Р4, выполняемого сразу после того, как ал-
горитм Р попал в тот же самый узел в преобразованном дереве В'. Тогда
s' = [s/2'l. Таким образом, размер стека при прохождении дерева В' в
прямом порядке почти в точности равен половине размера стека при про-
хождении дерева В во внутреннем порядке, и нами установлено соотноше-
ние как между средними, так и между максимальными размерами стека,
8. Согласно формуле (3.9), 1!{х = 77; 4- Un и U3x = U2 -j- 2С7 следо-
вательно, U0Qm = Ua, (1 4- U{ 4- U2Qm~ (1 +“)^+
4- 2 4- Обозначим через Вт оператор {72 — 2mOr14~(^4-l) mU0;
оказывается, что =^14- &т- Поэтому Bm+iGmn (х) =»
— PsBm-H4jV = (т — п 4- О (,п ~ п) ^2- Кроме того, согласно (3.36Х
Вт+&тп (л) = U2Gmn (х) — 2 (m 4- 1) (m-H — (m — n}Pi)+(m+$) (m-M).
откуда следует, что
U2Gmn (х) = (т — п — 1) (т — п) Р3 — 2 (т 4- 1) (т — п) Р( 4~ w (м + О-
А как насчет функции //? Л вот как:
UzHmn~ f 1 + л-i 4“ (~ G2 4" ~ С/Л п-1
и оказывается, что
+ 7777^^) -7-— w™=
=Т7 + 7—7^’" *-’) ”7ТТ7
Uifim— 1, n-i>
Таким образом, ^+1 ^(^«4- p_q Gmn
= ! и ( т, — п 4- 1 3 \ д Gm_n, 0^ и и р ~ q ’ D — q
102
Решения задач
и, подключая сюда нашу формулу для U-zGmn, получаем
U2Hmn - т+ (т — пр — 2 (щ — n) Л) +
(т + !) (т — п) / р tnп 4- 1 \
+ V7—^+Т“?2/
Заметим, что при р = q ~ 1/2 последний член принимает вид 0/0, так что
в этом случае нужна отдельная формула. Дифференцируя Р2 »о q, нахо-
дим, что ~ — т-т -1 Р2 == (1 — 2q}{ffm+i — Нт-п-+ !+2>4-О(1 — 2q)2
при q -> 1/2; следовательно, при q = 1/2 величина игНтп выражается
через гармонические числа,
9. Вместо терминов «левосторонний максимум» и «левосторонний ми-
нимум» будем использовать соответственно сокращения «л. максимум» и
«л. минимум».
(а) Для того чтобы получить у( . .. уь и z}... zn~k, надо, чтобы Х|Х2 —
= y\Z} или Х[Х2 — zYyu а остальные Xj должны содержать у2... У* и
zt., , zn-h, слитые вместе в каком-нибудь порядке. Если при вставке лу
этот ключ есть у,, то с вероятностью 1/2 мы помещаем его в левое под-
дерево, при условии что у- является л, максимумом; если же этот ключ
есть z,, то с вероятностью 1/2 мы помещаем его в правое поддерево, при
условии что Zj является л, минимумом, В противном случае соответствую-
щая вероятность равна 1; если же монета упадет неудачно, то мы не полу-
чим в качестве корня узел (fe:£+J). Таким образом, вероятность пере-
становки У\ .,. Ук пропорциональна 2~/.
(Ь) Для каждой пары перестановок у\..,ук н zlr..zn-k, имеющих
соответственно t л, максимумов нал. минимумов, и для каждого из
2(“J) способов слияния этих перестановок в перестановку xi...xn ве-
роятность пересылки yi., , yk влево, а г, , ,. вправо равна По-
этому рпк есть 2 21 )’ умноженное на г2г^(Ю“г(г) и деленное на ft!.
Рассматривая таблицы инверсий, мы видим, что производящей функ-
цией л. максимумов является функция
£^'^=2(14-2) ... {k — 1 4-z);
Е. I X — I
2l-/^)=(A—. Отсюда заключаем, что
—ЧГ7-
f k — 1/2 \ / n — k — \/2 \ /f n\
e k k - 1 ) V n - k - 1 j'\2j‘
Кен Кларксон нашел другую любопытную формулу:
(с) Все л. минимумы перестановок Xi...xn встречаются в перестановке
i/i . .. t/й, а все л. максимумы — в перестановке ,за исключением,
возможно, самых первых из них. Таким образом, вероятность получения от-
дельной у-перестаповки равна произведению 2 ( ) на 22~£
Хр(х), где р(х)—вероятность исходной перестановки X],.. х,71 Если
предположить (что мы можем сделать), что X] < хг, то р(х) пропорций-
Решения задач
103
нальна вероятностям 2-t<*\ 2~(t*>-*sw распределений L, R, В. В ре-
зультате вероятность пропорциональна поэто-
му левые поддеревья имеют распределения L, R, В. Правые поддеревья
распределены аналогично,
(d) Суммарная длина путей равна п плюс суммарная длина путей ле-
вого поддерева плюс суммарная длина путей правого поддерева, Значит,
с вероятностью рпи мы получаем вклад в величиву средвей суммарной
длины путей, равный п 4- Ln + В силу двойственности левого и пра-
вого qk{n-k) есть вероятность того, что ^-распределенное СК-дерево имеет
своим корнем узел (А;й-|-1). Отсюда следует равенство Ln = Rn {что
было очевидно).
(е) Согласно ответу к подзадаче (с), вероятность qnn пропорциональ-
на S !А z 2~* ( fe-iO’ где константы нормировки при фикси-
рованном п не зависят от k. Производящая функция £ paQ.
на (г2) (2г) (1 -ф 2г) ,.. (fc — 2 -|- 2г), следовательно, £ 2-s =
=-^-(fe — 1)1. Таким образом, пропорциональна а вероятность
rnk нс зависит oi k. Осталось только найти нормирующие константы, та-
кие, что k = 1- См. ниже равенство (1).
(f) В„ = Ся-1, где Сп определены формулами 5.2.2-18 и 5.2.2-24
(Кнут [IIIJ) при М = 0,
(g) По биномиальной теореме (1 — z)~1“m== £гг zn при
всех комплексных значениях т. Дифференцируя это равенство по т (пред-
ложено Джоном Хобби), получаем тождество (1.47):
(1 - In (1 - г)“' = £ (Нп+т_
гад о 4 п 7
Соберем теперь вместе формулы, которые непосредственно вытекают
из данного тождества, поскольку они пригодятся нам в дальнейшем.
В этих формулах суммирование осуществляется по множеству 1 k <Z п
. 14 3 fk-U2\ „ Z 1/24
и используются те факты, что " 1) ~ д-2 )’ а )
есть коэффициент при гй_| в разложении (1—г)-3/2 и т. д,
zG=;/2w:==/2)- <*>
Z ( 1 Z J/2 ) (^-1/2 - ”" Z У2 ) 1/2 - ад, О)
Z {^;/2)о-ч(ад6-^)=(^2/2)(ад1/2-ад). w
£ (*Z )/2) № -»(/д-,/2-н312-)=|(“zJ/2)(»л-1/2-ад, (6)
2(:д11/2)с=:д:/2)<‘-п“4(я1з)-
х(^;у2)(^^;/2)^-/м=[п:2)(^-^.<7>
104
Решения задач
=4 (Дз) <*»-"’>
(8}
Каждое из этих тождеств получено из рассмотрения коэффициентов в про-
изведении двух производящих функций.
Решение подзадачи (g) сводится к умножению тождества (4) на
некие
(h) Необходимо найти решение соотношения Ln = п 4- — j X
X (^п+1/2 ~~ + У qnkLk ПРИ 2, Подстановка хп = п — 1 в урав-
Е2 1
qnk%k в силу тождества (2) дает при
п — 1/2 \/Z п — 1/2 \
л-3 )/(„-2 )=“' +
Аналогично подстановка ~~ в СИЛУ тожДе‘
поскольку п — 1 = ап
+ 4(п-2).
□
ства (5) дает ап = а подстановка = (л — 1) (Яя„1/2 — ff^2) в СИЛУ
2 / 1 \ 2
тождества (5) дает ап = у-1 п 4- уJ — Н-!2) 4- у (п — I). Состав-
ляя надлежащую линейную комбинацию, получаем искомое решение
Ln ~ (2ft + тг) (^ге—1/2 — ^Л/з) _"ё‘ (я ”
(i) Имеем {/„ = п 4- 2 PnkLk- Записывая Lk в виде £/г = 2 (fe — i) X
9 1
+ *> и используя тожде-
ства (8), (7) и (6), получаем
Un = и + 2 (я - 2) 4- у (Яп - 4) + у & ” 2}.
Таким образом, можно сделать вывод, что СК-деревья не заслуживают
реализации; они дают нам поучительные представления о методах дискрет-
ной математики и анализа алгоритмов, но никогда нс будут названы «де-
ревьями поиска Смышленого» 2а), Несколько неожиданно, что Un Ln
В„, поскольку откладывание вставки «экстремальных» ключей могло бы
создать впечатление, что знаки неравенств должны быть обратными.
10. Суммируя но частям, получаем равенство
2\.= Е Нк/(2п-Ь)-Н*,
0<Л<2п
правая часть которого, согласно упр. 1.2,7-21 (Кнут [I]) или тождеству
(1.48), равна ——tfj. Далее
"й - н'п - (,п" +1"2 + V + 4г + 0 “
— (1л п. + V + 2^- + О и ’)) ,
Решения задач
105
и, согласно упр. 6,1-8 (Кнут [Ш]), /^==2 яа — 4 О (ц“2). Раскры-
вая скобки и приводя подобные члены, получаем ответ:
(In 2) (In п) 4- У 1п 2 + 2 (In 2)2 - -2- < -2 1п п 4
+ у гг~! (In 2 4- 1 — у) + О («~2 log л).
[Эта задачка была слишком простой. Лучше было бы поставить вопрос
об асимптотике, скажем, суммы КОТОРУЮ было
бы легче всего установить, используя тождество
т ^к!^п ~~ = S|
11. Положим F (w, г) = amnwmzn, где amn — число путей из точки
(0, 0) в точку (т, и). Тогда F = 1 4- 4 zF 4 wzF, так что F (да, z) =
= (l-w-2-wz) 1. Производящей функцией для диагональЕЕЫх коэф-
фициентов служит функция
4 (г) - -2_ ф р (/, z/t) ~ = -тг~ <6 д--------------Г-
2ш J / 2л;' J t — t2 — z — zt'
Знаменатель дроби в подынтегральном выражении можно представить
в виде — (/ — г (z)) (t — з {z))t где г (г) =2 (| _ 2 4 и/1 — 6г 4 гг) и
и s (г) = 2 (1 — г — дЛ ~ 6г 4 г2).
Пусть г по модулю мало, так что функция г(г) близка к 1, а з(г)—
к 0. Будем интегрировать вдоль контура с малым |/|, который окружает
точку s(z)\ затем выберем |z| столь малым, чтобы [гД( стало мало и
обеспечивало абсолютную сходимость ряда У*д атп tm(z/t)n. (Ясно,
что атп 4 3^+4 так что подобный контур интегрирования существует,)
Окончательно, Л(г) есть вычет в точке s(г), равный l/(r(z) — s(x)).
Итак, А (г) = 1/д/(1 — 0г)’( 1 — qp2), где 8 = 3 4 Уз и ср = 3 — д/8.
Пусть w — 02 и а == <р/0, так что А (г) = В (ш) =: 1/д/( I — w) (1 — aw) =
“ X Следовательно, еезшя задача сводится к нахождению
асимптотики коэффициентов производящей функции, обратной к функции
(4.108). Имеем 1/т/1 — = 1/дЛ — a “ u (— Ч= a) 1,2 4“
4 (а» — 1) R (щ), гДе функция R аналитична при [ w | < а~1, поэтому коэф-
фициенты гп в се разложении имеют порядок О при некотором р > 1.
Таким образом, В (w) = (1 — a) (1 — 1,2 4 (1 — w)l,_ R (w), где по-
следнее слагаемое равно ( Т) S rmw>n'’ 0ТСЮДа- как и в (4.114),
следует, что n-й коэффициент этого разложения имеет порядок О (п 3/2).
В разложении же первого слагаемого n-й коэффициент равен
(1 _ 1)« = (I - что имеет порядок
О поэтому ап = О'1 (1 -• aKi,/2 ( ) + О (°м//г)-
106
Решения задач
Имеем ( —1)п — 2 2,1 (2«), что по формуле Стирлинга есть
1/д/яя 4“ О (л~3'2)- Таким образом, требуемый ответ таков;
а„ = 1+У1 (3 + <8 У + О ((3 + <8 У п-^}.
2‘4 V яп
Между прочим, числа атп возникают в самых различных ситуациях.
Например,
__ /т \ / n -ф k Л (/п — п + А)! __
а™п “ \ т ) L (т — Л)! (п — й)! А!
Кроме того, атг1 есть число различных гс-ок целых чисел (хь х,0, та-
ких, что |х,| 4-...+ 1А'я| это равно объему сферы радиуса т в п-
мерной «метрике Ли».
12. Вероятность того, что некоторый студент получит А+, решив при
этом правильно т задач, равна вероятности ровно т удач (а именно
рт{\—р)), умноженной на вероятность того, что любой другой студент
оплошает при решении одной из первых т задач (а именно (1 — р”1)'1-1).
Умножая эту вероятность па п, поскольку у каждого студента есть шанс
заработать Л+, получаем, что = п (1 — р) рт (1 — р™) - (По-
добные формулы при р = 1/2 возникают при анализе обменной поразряд-
ной сортировки (Кнут [III, разд. 5.2.2]) и в более общей постановке в
упр. 6.3-19.)
Пусть Qn = пЛ++] (я 4- I)"’ (1 -р)-1 = ~Рт)П- Поло-
жим х = пр™; тогда слагаемое принимает вид х (1 — х/п)п, что есть хе~х X
X (i + О (Z/n)) при х ^ns. Пусть Тп = 22^ Пртепр . Тогда Qn — Тп =
= Хп + Уя, где величина
Х„ = Z n/H(l-pm)"-e<) =
ш >0, прт > пе
— £ пр™о(е пр ) = О (я log я-д "Е)
т >0, прт >
экспоненциально мала, поскольку 1— р р и сумма состоит из
O(logm) членов. Другая величина
т ^0, прП1<«е
m>0, npm<n?
имеет порядок О(п38-1)> поскольку она оценивается сверху суммой геоме-
трической прогрессии с учетом очевидного неравенства е~п^т 1, При-
меняя «метод гамма-фуикции», получаем
1/2+ too 1/2+ioo
i/2-fw 1/2-fw r
Решения задач
107
(ср. Кнут [Ш, равенство 5.2.2-45]), Последний интеграл может быть выра-
жен в виде взятой со знаком минус суммы вычетов подынтегральной
функции относительно ее полюсов в правой половине плоскости. Таким об-
разом,
1 2
£ W(l+2™*/lnp))X
k .> i
X exp (-— 2ш'А In njIn p) -j- О (n“M)
при произвольном M. Величина под знаком суммы ограничена, поскольку
она периодична по п (заметьте, что эта величина принимает то же значе-
ние, если п заменить на пр).Поэтому можно утверждать, что А„ = (1 —
— р)/1п (1/р) + / (и) 4- О (1/я), где /(л) — некоторая периодическая функ-
ция. Поскольку Г (1 4- Н) — О то абсолютная величина ?(п)
очень мала, если только р не слишком мало, к среднее значение f(n) рав-
но нулю, так как среднее значение каждого слагаемого есть 0. Однако
f(n) о(1), и 1(п) не может быть отброшено. Ожидалось, что А* будет
стремиться к 0 или 1, так что полученный результат несколько неожидан.
В упр. 5.2,2-54 (Кнут [III]) содержится другой подход к решению
данной задачи, с помощью которого мы получаем сходящийся ряд
л+ = 1 7/ А 4- У (л, 14--^-Ц\
П \ fe а К \ Inp JJJ
Асимптотическое значение фигурирующей в этой сумме бета-функции рав-
но
ft_j_/bfer(1 + ibk} ^2)^1 +0(„“2)у
где b = 2л/1п р; таким образом, мы получаем встречавшуюся выше пе-
риодическую функцию, а также коэффициент при и-1. (В связи с этим
нам представляется, что в последующем издании книги Кнута [III] упраж-
нению 5,2.2-54 следует уделить значительно больше места.)
13. (а) Если х\. .. хп— перестановка множества {1, .... и}, то пусть
xi.,.xB-i— перестановка множества {1, .,,, п — 1}, являющаяся резуль-
татом уменьшения па единицу тех элементов xi.,,xn-i, которые превосхо-
дят хп. Вставка ключей х,. .. хп приводит к получению дерева с корнем
(А: А 4- I) ттогда, когда: I) хп < h и вставка ключей х! ... x,i-I приводит
к получению корня (k— 1 ; А); 2) хп = k и вставка ключей Х] ... xn-i при-
водит к получению корня (k — 1 : А) и либо k — 1 < я — k, либо А — 1 =
= п—k (и при случайном подбрасывании монеты выпадает «орел»);
3) хп = k 4- 1 и вставка ключей приводит к получению корня
(A: k 4-1) и либо А п — 1 — А, либо k = n—1-— А (и при случайном
подбрасывании монеты выпадает «решетка»); 4) хл>-А4-1 и вставка
ключей X] ....«„-j приводит к получению корня (А: А 4-1). Поэтому при
1 sC А < п и п > 2
Pnk = Л«-О (*-1> (А - 1 + (л + 1 > 2А) 4- + 1 = 2*)) +
+ («“ k — 1 4- (п ~ 1 < 2£) + у *“ 1 = 2^)
(Ъ) Легко видеть, что Р^ = Рп (n_k}, значит Qnk = С}п(п^ку Таким
образом, достаточно рассмотреть случай А п — А. Если А < и — А — 1,
108
Решения задач
го предыдущее рекуррентное соотношение показывает, что
Qnkkl(n-kY _
2 (л —А) 2 (re — А)
Qf„ nJfeAI (п - 1 - А)!
+ (пХ-а-1Г
т. е. Qnk = <?(„_!, + <?(„_!)k- Если же А - п - 1, то
QafeA!Af Qfre_j) (ft_i) (А — I)! А!
—Tk-------------------й-----------(* - 1 + 'Н
и снова имеет место «соотношение Паскаля», Однако если А = и — А 4-1, то
QnfeA! (А 4- 1)1 _
2 (А 4-1)
-----------2[k+T)-----------(^ - 1 + 1) +------jj----
следовательно, Qnk = (*_(} 4- Q(rt_n л + 8 СНЛУ
симметрии QnA, = Q(„_1((fe_l)4-Qfn_1)fe + -^-j-Q(tt_1Hft_I) при А == ге -
— А 4" 1. «Соотношение Паскаля» выполняется снова, за исключением
случаев, когда (п, А) = (2, 1) или | п — 2А | = L
(с) Удобнее положить треугольник «на бок» и связать с точкой
решетки (А, п — А), Величину Q,tk можно интерпретировать как взятую по
всем путям из точки (], 1) в точку (А, п—А) учетверенную сумму произве-
дений весов всех отрезков пути; из точки ({, /) путь идет в точку (i 4- 1,
/) или (t, /4- 1), и вес каждого такого отрезка пути равен 1, за исключе-
нием случая I = j, когда он равен 1 4- 1/(2/). Тогда ak есть учетверенная
сумма, взятая по всем путям из точки (1, 1) до точки (А, А); поэтому
слагаемые этой суммы можно сгруппировать в подсуммы в соответствии
с наибольшей величиной диагональной точки (/, /) пути, такой, что / < А.
При этом /-я подсумма равна величине а/, умноженной на 14-1/(2/) и
умноженной на число путей из точки (/, /) в точку (А, А), которые не со-
прикасаются с диагональю, поскольку веса отрезков всех таких путей, за
исключением первого отрезка, равны 1. Всего имеется 2с*_/ таких путей.
(d) Поскольку kfk = (2/ 4* 1) 4- 4 (А = I), имеем уравнение
zFf (z) = 4z~'C (z) (SzF' (z) 4- F (z)), которое упрощается до уравнения
z V1 - 4zF' (z) = 4z + C (z) F (z).
Следуя нашей подсказке, в соответсвии с общим правилом отыскания ин-
тегрирующего множителя для дифференциальных уравнений первого по-
рядка, получаем, что
(В (z) F (z))' = В (z) F' (г) - F =
= ~4== (г VT^4^Z (г) - С (z) F (г)) =
2 у 1 — 4г
в 4В (г)/дЛ — 4г = 2/V1 — 4г 4- 2
Решения задач
109
Таким образом, В (z) F (г) = 2С (г) -|- 2г, и еще через несколько шагов
мы находим решение ап = 2я (сп + cft+l) = п (J1*') ~ п f )
при п 1.
(е) Поскольку
(1 — да — г) Q (г) = wk2(-n {Qnk ~ Q(n~ I) k Q(n-1) (A-i)) =
-- 4даг + 4-z) (ftwz 4- /2да2гг 4-/3да3га 4-
имеем
Q (w, z) => (1 — w — z)"1 X
X ^4даг 4- ~ (w~] — w 4- г-1 — z — (to-1 4- + г~' + г) л/1 — 4шг)^.
(f) Если hr (х) = У aB(m4.dx'1 и h(w, z) =* '£jamriwmzn, то коэффи-
циент при wnzn^r в разложении g (wz) h (w, z) совпадает с коэффициен-
том при х” в разложении g (х) ЛГ (г), поскольку при умножении на g (wz)
группируются вместе только члены, имеющие одну и ту же разность
степеней z и да. Следовательно, коэффициент при wnzr>'^r в разложении
Vi ~ 4wz/(l — ш — z) равен коэффициенту при х в разложении
V1 — 4х ( 2П^Г ) хп = (С (х)/х)Г = С (х)г (В (х) — С (х)) x^yVl — 4х =>
= (C(x)/x)r-l/Vl —4х- * (С (x)/x)f+I/Vl “4х = У ^2« + г-1 ) _
(g) В случае г > 0 коэффициент при w z в производящей функ-
ции Q (да, г) может быть вычислен из рассмотрения различных членов
в выражении для Q (да, z) из части (е) задачи, Пусть br == (2,*^+r)- Тогда
Ф(2м+г)п = (^г_] — &г_2) + ту (( rt + J ) ~ 4" ^г~\ + &r.{-i “ Ьг_{ —
(Он _1_ г \
Xi ) + ЬГ - »г-1 + 6r-2 + br- 2fv-i + ьг-г - 6г+ »г+1 -
— br_2 — br-1 — Ьг_2) ~ Ьг+1 4- “ 4^г-2- Умножая на -^-(гс4~
4-г--!)! «.!/(2п 4~ г)!, получаем выражение для Р(2п+Г)п, Из-за наличия
членов да"1 и z~1 при г = 0 используется другая формула.
Заключительное замечание (для студента Смышленого), «При х =
«= k/n < 1/2 имеем pnk да — ((1 — х)~2 — 0 4~ 2х: следовательно, УСК-де-
ревья достаточно хорошо выполняют свои функции. Распределение пере-
становок ключей в левых и правых поддеревьях не является равномер-
ным, и можно было бы продолжить наш анализ с целью нахождения сред-
ней длины пути УСК-деревьев, Тем не менее, г-н Смышленый, Ваш алго-
ритм все же не годится для практического использования: средняя длина
пути дерева будет где-то между 2п 1п п и (1/1п 2) п In п, однако дополни-
тельное время, которое требует Ваш метод для обработки каждого узда,
настолько замедляет выполнение программы, что сводит на нет незначи-
тельный выигрыш в длине пути. С самого начала было ясно, что УСК-де-
ревья будут уступать другим методам по всем характеристикам (объему
памяти, быстродействию, простоте реализации и т, п,), Единственным по-
ложительным качеством Ваших алгоритмов является то, что их анализ
приводит к поучительной математике, которую когда-нибудь можно будет
применить к анализу действительно полезных методов. Вы, несомненно,
также это понимаете, поэтому спасибо Вам за идеи».
Примечания редактора и переводчика
1. Ср.: Итоги науки и техники, сер, Современные проблемы матема-
тики. Фундаментальные направления. Т. 13.—М,; ВИНИТИ АН СССР, 1986.
2. В 1974, 1976 и 1980 гг. курс математического анализа алгоритмов
читался Д, Кнутом, а в 1978 г. — Э. Яо.
3. См, новую серию книг Д, Кнута под названием Computer and Type-
setting (Vol. Л: The TeXbook, Vo!. В: Tex. The Program, Vol. C: ME-
TAFONTbook, Vol, D; METAFONT. The Program, Vol, E: COMPUTER
MODERN Typefaces.— Reading, Mass.; Addison-Wesley, 1985).
4. Имеются в виду кратчайшие пути из левого нижнего угла в пра-
вый верхний угол (подробнее см. Ежов И. И., Скороход А. В., Ядрен-
ко М. И. Элементы комбинаторики. — М.; Наука, 1977).
5. См, Егорычев Г. П. Интегральное представление и вычисление ком-
бинаторных сумм. — Новосибирск: Наука, 1977 (в частности, с. 42).
6. Подробнее см., папример, Сачков В. Н. Вероятностные методы в
комбинаторном анализе. — ,М.: Наука, 1978.
7. Из отечественных работ отметим книгу А. О. Гельфонда Исчисление
конечных разностей (М.: Физматгиз, 1959).
8. Речь идет о методе решения разностных уравнений, аналогичном
методу решения дифференциальных уравнений с помощью «интегрирующего
множителя» — отсюда термин «суммирующий множитель».
9. Подобное определение символа fi не эквивалентно первоначальному
определению, введенному Харди и Литлвудом.
10. В оригинале bootstrapping (буквально; натягивание сапога на ногу
за лямки).
11, Хотя запись п(0 = О(/(/)) похожа на запись /(н) = O(g(n)) из
разд. 4.1.1, переменная t здесь не играет роли п.
12. Иначе называемая «асимптотическим законом распределения про-
стых чисел» (см. Гельфопд А О., Линник 10. В. Элементарные методы в
аналитической теории чисел. — М,: Физматгиз, 1962).
13, То есть G(z) является целой функцией (см. также Евграфов М. А.
Асимптотические оценки и целые функции. — М.; Физматгиз, 1979).
14. Имеются в виду так называемые большие отклонения; см, Фел-
лер В. Введение в теорию вероятностей и се приложения, т. 2. — М.; Мир,
1984, с. 615.
15, «Число очков» в квадратных скобках отражает, по-видимому, срав-
нительную степень трудности каждой задачи, которые составлены из зада-
ний среднесеместрового, заключительного и квалификационного экзаменов,
принятых в университетах США.
16. Ттогда (Ш)—сокращение от «тогда и только тогда» (И and only if).
17. В первом издании I тома Искусства программирования для ЭВМ
Д. Кнута и соответственно в переводе этого упражнения нет.
18 Данная задача перепечатана в разделе Problems журнала Journal
of Algorithms (1983, v. 4, Кв 4, p. 385—388). Там же (р. 388—393) поме-
щено предложенное Р. V. Poblete решение этой задачи, отличное от при-
веденного в настоящей книге решения Д. Кнута.
19. Имеется несколько руководств по системе MACSYMA. Краткое
описание содержится в сб. Introductory MACSYMA Documentation, A Col-
lection of Papers, изданном в МТИ в 1982 г., а полное описание — в двух-
томном руководстве MACSYMA Reference Manual, изданном в МТИ годом
позже. Однако, более удачной представляется книга Rand R. II Compu-
ter Algebra in Applied Mathematics; An Introduction to MACSYMA. — Bos-
ton: Pitman, 1984. (См. также: Компьютерная алгебра, Символьные и ал-
гебраические вычисления. Под ред. Б. Бухбергера, Д. Коллинза и Р. Ло-
оса. — М.: Мир, 1986.)
20. В оригинале «Quicksearch», что обыгрывает название известного
алгоритма Quicksort и фамилию студента Quick.
21. В этой и последующей формулах фигурируют логические выраже-
ния, значения которых суть 1, если соответствующие отношения истинны, и
О в противном случае.
Литература
Амбле. Кнут (Amble О., Knuth D. Е.)
[74] Ordered hash tables,— The Computer Journal, 1974, v. 17, N 2,
p. 135—142.
Апостол (Apostol T.)
[57] Mathematical analysis: a modern approach to advanced calculus. —
Reading, Mass- Addison-Wesley, 1957, [См, также: Рудин У. Ос-
новы математического анализа, — М.: Мир, 1976.]
Ахо, Слоан (Aho А. V., Sloane N. J, А.)
[73] Some doubly exponential sequences. — Fibonacci Quarterly, 1973,
v. 11, N 4, p. 429—437.
Бейли (Bailey W. N.)
[35] Generalized hypergeometric series.— London: Cambridge Univer-
sity Press, 1935
Бендер (Bender E, A.)
[74] Asymptotic methods in enumeration. — SIAM Review, 1974, v. 16,
N 4, p. 485—515
Бойс, Ди Прима (Boyce W., DiPrima R.)
[69] Elementary differential equations and boundary value problems, —
New York: Wiley, 1969.
Гульд, Сю (Gould H., Hsu L )
[73] Some new inverse relations. — Duke Mathematical Journal, 1973,
v. 40, N 4, p. 885—892.
Де Брёйн (De Bruijn N. G )
[70] Asymptotic methods in analysis. — Amsterdam: North-Holland,
1970. [Имеется перевод первоЕ'о издания: Де Брейн Н. Г. Асим-
птотические методы ь анализе, — М.: ИЛ, 1961.]
Де Брёйн, Кнут, Райс (De Bruijn N G., Knuth D. E., Rice S. O.)
[72] The average height of planted plane trees. — In: Graph theory and
computing ed. R. C. Read. — New York: Academic Press, 1972,
p, 15-22.
Деланж (Delange H.)
[75] Sur la fonction sommatoire de la fonction «somme des chiffres». —
Enseignement Mathemaliquc, 1975, v. 21, N I, p. 31—47.
Зэйв (Zave D, A.)
[76] A series expansion involving the harmonic numbers. — Information
Processing Letters, 1976, v. 5, N 1, p. 75—77.
Йонассен, Кнут (Jonassen A., Knuth D. E.)
[78] A trivial algorithm whose analysis isn’t. — Journal of Computer
and System Sciences, 1978, v. 16, N 3, p. 301—322.
Йордан (Jordan K.)
[60] Calculus oi finite differences. — New York; Chelsea, 1960,
Кнут (Knuth D. E.)
[I] The art of computer programming Vol. 1. Fundamental algo
rithms Second edition. — Reading. Mass.: Addison-Wesley, 1973.
[Имеется перевод первого издания: Кнут Д. Искусство програм-
мирования для ЭВМ. Т, 1, Основные алгоритмы,—М.; Мир,
1976.]
[II] The art of computer programming. Vol. 2. Seminumerical algo-
rithms. Second edition. — Reading, Mass.: Addison-Wesley, 1981.
[Имеется перевод первого издания: Кнут Д. Искусство програм-
мирования для ЭВ/М. Т 2. Получисленные алгоритмы. — М
Мир, 1977 ]
[П1] The art of computer programming. Vol. 3. Sorting and sear-
ching, — Reading, Mass.: Addison-Wesley, 1973. [Имеется пере-
112
Литература
вод: Кнут Д, Искусство программирования для ЭВМ. Т. 3. Сор-
тировка и поиск. — М.: Мир, 1978.]
[72] Mathematical analysis of algorithms. — In: Information Proces-
sing 71. Proceedings of IFIP congress 71. Vol, 1. Foundations
and systems.—Amsterdam; North-Holland, 1972, p. 19—27.
[76a] Big omicron and big omega and big theta, — SIGACT News, 1976,
v. 8, N 2, p. 18—24,
[76b] Manages stables et leurs relation avec d’autres problemes combi-
natoire — Montreal: Les Presses de rUniversile de Montreal,
1976.
Кнут, Траб Пардо (Knuth D, E., Trabb Pardo L.)
[76] Analysis of a simple factorization algorithm. — Theoretical Compu-
ter Science, 1976, v. 3, N 3, p. 321—348,
Кнут, Шёнхаге (Knuth D. E., Schonhage A.)
[78] The expected linearity of a simple equivalence algorithm. — Theo-
retical Computer Science, 1978, v. 6, N 3, p. 281—-315,
Конте (Comtet L.)
[74] Advanced combinatorics. — Dordrecht: Reidel, 1974.
Люкер (Luker G. S.)
[80] Some techniques for solving recurrences. — Computing Surveys,
1980, v. 12, N 4, p. 419—436.
Милн-Томсон (Milne-Thomson L. M.)
[33] The calculus of finite differences. — London: Macmillan, 1933,
Олвер (Olver F. W, J.)
[74] Asymptotics and special functions. — New York: Academic Press,
1974. {Имеется перевод сокращенного варианта; Олвер Ф, Введе-
ние в асимптотические методы и специальные функции, — М,;
Наука, 1978.]
Пейдж, Уилсон (Page Е., Wilson L.)
[79] An introduction to computational combinatorics — London; Cam-
bridge University Press, 1979.
Риордан (Riordan J.)
[68] Combinatorial identities. — New York: Wiley, 1968. .[Имеется пере-
вод: Риордан Дж. Комбинаторные тождества. — М.: Наука,
1982.]
Рота и др. (Rota G.-C. et al,)
[75] Finite operator calculus. — New York; Academic Press, 1975.
Седгевик (Sedgewick R.)
[80] Quicksort. — New York: Garland, 1980.
Слейтер (Slater L, J.)
[66] Generalized hypergeometric functions, — London: Cambridge Uni-
versity Press, 1966, [См. также: Слейтер Л. Дж. Вырожденные
гипергеометрическне функции.— М.: Изд. ВЦ АН СССР, 1966.]
Столарски (Stolarsky К- В.)
[77] Power and exponential sums of digital sums related to binomial
coefficient parity. — SIAM Journal on Applied Mathematics, 1977
v. 32, N 4, p, 717—730.
Уиттекер, Ватсон (Whittaker E. T., Watson G. N.)
[40] A course of modern analysis, — Cambridge: Cambridge University
Press, 1940, [Имеется перевод: Уиттекер Э. Т., Ватсон Дж. И,
Курс современного анализа. Ч. 1, II, — М.: Физматгиз, 1963.]
Фредмэн, Кнут (Fredman М. L., Knuth D. Е.)
[74] Recurrence relations based on minimization.—'Journal of Mathe-
matical Analysis and Applications, 1974, v. 48, N 2, p. 534—559.
Харди (Hardy G. H.)
[49] Divergent series. — London: Oxford University Press, 1949. [Имеет-
ся перевод: Харди Г. Расходящиеся ряды.— М.: ИЛ, 195L]
Литература
113
Харди, Райт (Hardy G. Н., Wright Е, М.)
[79] An introduction to the theory of numbers. — London; Oxford Uni-
versity Press, 1979.
Хенричи (Henrici P,)
[74] Applied and computational complex analysis. Vol, 1. — New York:
Wiley, 1974.
Шпигель (Spiegel M.)
[71] Calculus of finite differences and difference equations. — New
York; McGraw-Hill, 1971.
Эрдёш, Репьи (Erdos P„ Renyi A.)
[59] On random graphs, I. — Publicationes Mathematicae, 1959. v, .6,
N 2, p. 290—297.
[60] On the evolution of random graphs. — Matematikai Kutato Inteze-
tenek Kozlemenyei, 1960, v. 5, N 1, p. 17—61. [Материал этой и
предыдущей статей можно найти в книге: Эрдёш П., Спенсер
Дж., Вероятностные методы в комбинаторике.—М.; Мир, 1976.]
Д. Э. Кнут и его «фабрика книг»
(Дополнение переводчика)
Известный американский математик ДоналЕ-д Эрвин Кнут (род, в
1938 г.) окончил в 1960 г. отделение математики Кейсовского технологи-
ческого института и в 1963 г, получил докторскую степень в Калифорний-
ском технологическом институте. С 1968 г. он профессор, а в настоящее
время — почетный профессор (Fletcher Jones Professor of CompEiter Science)
Стэнфордского университета. Основные области его научных интересов:
теоретическое программирование, математический анализ алгоритмов,
история и методология информатики.
Д, Кнут является главным редактором выходящего с 1980 г, журнала
Journal of Algorithms и входит в состав редакций большого числа других
международных журналов. Он состоит членом Национальной академии
наук США, Американского математического общества, Ассоциации по вы-
числительной технике. Института инженеров по электротехнике и радио-
электронике, Общества промышленной и прикладной математики и мно-
гих других научных обществ и организаций (в частности, Американской
гильдии органистов),
В 1971 г, ему была присуждена премия Ассоциации по вычислитель-
ной технике (ACM Grace Murray Hopper Award), в 1974 г.— премия име-
ни Тьюринга (ACM Alan М. Turing Award), в 1984 г, — премия Математи-
ческой ассоциации США (МАЛ Lester R, Ford Award), а в 1982 г. — пре-
мия ИИЭР (IEEE Computer Pioneer Award). В 1979 г. Д. Кнут был на-
гражден Национальной медалью пауки (National Medal of Science).
В том же году он приезжал в нашу страну в качестве сопредседателя
международного симпозиума «Алгоритмы в современной математике и ее
приложениях», который проходил в г. Ургенче Узбекской ССР на родине
аль-Хорезми. Перевод его доклада на этом симпозиуме опубли[<ован
в одноименном сборнике (Новосибирск; ВЦ СО АН СССР, 1982, ч. I,
с, 64—98).
Наибольшую известность Д. Кнуту принесла монументальная серия
его монографий The Art of Computer Programming, выпускаемая издатель-
ством «Эддисон-Уэсли», из запланированных семи томов которой изданы
первые три (Vol. 1; Fundamental Algorithms, 1st ed. 1968, 2nd ed. 1973;
Vol. 2: Seminumerical Algorithms, 1st ed. 1969, 2nd ed, 1981; Vol. 3: Sorting
and Searching, 1973) и готовится к изданию четвертый том. В виде от-
дельной брошюры MIX (Reading; Addison—Wesley, 1970) издан одно-
именный раздел из первого тома этой серии книг.
В связи с необходимостью проведения большой работы по переизда-
нию выпушенных и изданию новых томов серии Искусства программиро-
вания для ЭВМ Д. Кнутом была создана «компьютерная типография»,
состоящая из систем ТеХ и METAFONT, прячем с помощью последней
Кнут разработал для своих книг новое семейство шрифтов COMPUTER
MODERN. Работа над одной серией книг породила другую — Computers
and Typesetting (Vol. Ar The TeXbook, Vol. B: TcX. The Program, Vol. C;
The METAFONTbook, Vol. D: METAFONT. The Program. Vol, E: COM-
PUTER MODERN Typefaces. — Reading: Addison-Wesley, 1986). В виде от-
дельных кгеиг меньшего объема выпущены The TeXbook и The METAFONT-
book (Reading ; Addison-Wesley, 1984 и 1986). Данной серии книг пред-
шествовало несколько брошюр, в частности ТеХ and METAFONT, New
Directions in Typesetting (Bedford: Digital Press, 1979).
И наконец, третью серию книг. проф. Кнута составляют курсы лек-
ций по математическому анализу алгоритмов, прочитанные им в Монреаль-
ском университете (Knuth D. Е. Marriages stables et leurs relations avec
Д, Э, Кнут и его «фабрика книг»
115
d'autrcs problemes comb in a to ires.Montreal: Les Presses de I’Universite
de Montreal, 1976), Стэнфордском университете (Greene D. H., Knuth D. E,
Mathematics for the Analysis of Algorithms. — Boston: Birkhauser, 1st ecL
1981, 2nd ed. 1982) и университете г. Осло (к сожалению, точной ссыл-
кой на это издание мы не располагаем). К учебной серии книг примы-
кает его «математическая повесть» Surreal Numbers (Reading: Addison-
Wesley, 1974).
В настоящее время Д. Кнут работает над- новым учебником (Gra-
ham R,r Knuth D,, Patashnik О. Concrete Mathematics. — Reading: Addison-
Wesley, in preparation) и возвращается к работе над следующими томами.
The Art of Computer Pragramming (Vols 4A, 4B, 4C: Combinatorial Algo-
rithms.— Reading: Addison—Wesley, in preparation).
О высоком международном авторитете Д, Кнута свидетельствуют
переводы его трудов на многие языки мира. На русском языке имеются
следующие переводы книг и статей Д, Кнута, выпущенные издательством
«Мир»:
— Кнут Д. Искусство программирования для ЭВМ. Том 1: Основные
алгоритмы, Том 2: Получислепные алгоритмы, Том 3: Сортировка и по-
иск.— М.: Мир. 1976, 1977, 1978.
— Грин Д,г Кнут Д. Математические методы анализа алгоритмов.-—
М.: Мир, 1987.
— Кнут Д. О трансляции языков слева направо. В сб.: Языки и авто-
маты, с. 9—42, — М,: Мир, 1975.
— Кнут Д. Нисходящий синтаксический анализ. Кпберн. сб., нов. сер,,
выл. 15, с, 101 — 142. — М-: Мир, 1978.
— Кнут Д., Яо Э. Сложность моделирования неравномерных распре-
делений Кибсрн, сб., нов. сер., вып. 19, с. 97—158.—М.: Мир, 1983.
— Кнут Д. Исчезновения. Сверхъестественные числа. В кн.: Матема-
тический цветник, с. 329, 388—408. — М.: Мир, 1983.
— Кнут Д, Алгоритм Хаффмэна: алгебраический подход. Киберн.
сб., нов. сер., вып. 22, с. 159—169. — М.: Мир, 1985.
С увлекательной историей создания Д. Кнутом своих книг и планами
на будущее (по образному выражению самого автора) его «фабрики книг»
можно познакомиться в статье Albers D. J,, Steen L., A. A conversation
with Don Knuth, опубликованной в журнале Annals of the History of Com-
puting, 1982, v. 4, № 3, p. 257—274 и перепечатанной в сборнике Mathe-
matical People. Profiles and Interviews.—Boston; Birkhauser, 1985.
Б. Б. П,
Указатель
Алгебраические особенности (al-
gebraic singularities) 71—73
А моле (Amble Ole) Ill
Апостол (Apostol Tom Mike) 61,
111
Асимптотический анализ (asympto-
tic analysis) 48—82, 84—85, 87—
88, 93—101, 104—107
Axo (Aho Alfred Vaino) 34, 37, 111
Банан (banana) 84
Бейли (Baily Wilfred Norman) 16,
111
Бендер (Bender Edward Anton) 73,
111
Бент (Bent Samuel Watkins) 7
Бета-функция (beta function) 107
Биномиальные тождества (binomial
identities) 8—17
Бойс (Boyce William Edward) 22,
HI
Бродер (Broder Andrei) 7
Валле-Пуссен (de la Vallee Poussin
Charles Louis Xavier Joseph) 66
Ватсон (Watson George Neville)
112
Виттер (Vltter Jeffrey Scott) 7
Гамма-функция (gamma function)
80
— метод (gamma function method)
107
Гармонические числа (harmonic
numbers)
-----асимптотики (asymptotics) 53,
56
— — примеры (examples) 25—26,
56, 87
-----тождества (identities) 16 — 17
Гессель (Gessel Ira M.) 10
Гипергеометрическин ряд (hyper-
geometric series) 15—16
Голомб (Golomb Solomon Wolf) 35
Грамматика (grammar)
— бесконтекстная (context free) 92
— однозначная (unambiguous) 92
Грин (Greene Daniel Hill) 3
Гульд (Gould Henry Wadsworth)
12, 13
Гюиба (Guibas Leonidas loannis) 7
Дважды экспоненциальные после-
довательности (doubly exponen-
tial sequences) 33—37
Де Брейн (de Bruijn Nicolaas Go-
vert) 32, 50, 52, 100, 111
Деланж (Delange Hubert) 29, 111
Дерево (tree)
— бинарное сбалансированное (ba-
lanced binary) 36
— бинарного поиска (binary se-
arch) 85—87, 88—89, 102—104,
107—109
— длина внешних путей (external
path length) 86—87
— представление в виде бинарного
дерева (representing binary) 83—
84, 90
— прохождение бинарного дерева
(traversing binary) 85, 99—101
— связанное в конце (late binding)
85—87, 88—89, 102—104, 107—
109
— суммарная длина путей (total
path length) 103
— упорядоченное ориентированное
(ordered oriented) 31
Дзета-функция Римана (Riemann
zeta function) 58, 67—68
Диагонализация ряда (diagonaliza-
tion of series) 75, 105
Ди Прима (DiPrima Richard Clyde)
111
Указатель
117
Дифференциальные уравнения (dif-
ferential equations) 21, 26, 89, 91,
108
Драйсдейл (Drysdale Robert Le-
wis (Scot) 1I.I) 7
Дробь (fraction)
— непрерывная (continued) 31—33
— подходящая (convergent) 32
— элементарная (partial) 19—20, 58
Егорычев Георгий Петрович 10
— метод коэффициентов (method of
coefficients) 10—11
Золотое сечение (golden ratio) 36
Зэйв (Zavc Derek Alan) 17, 111
Индукция с другого конца (indu-
ction from the other end) 38, 44—
47, 91
Интеграл контурный (contour inte-
gral) 70, 74—76, 78
— Стилтьеса (Stieltjes integral) 60—
70
Интегральная показательная функ-
ция (exponential integral) 69
Информатика (Computer Science) 7
Метод операторов (operator met-
hods) 14—15
— перевала (saddle point method)
70, 76—82
Метрика Ли (Lee metric) 1,06
Милн-Томсон (Milne-Thom son Lou-
is Melville) 18, 112
Минпозиция (minvolution) 30—31
Многочлены (polynomials)
— базисные (basic) 14—15
— Велла (Bell) 80
— Бернулли (Bernoulli) 54, 65
— неприводимые (irreducible) 54
Множители (factors)
— простые необычные (prime unu-
sual) 84, 97—99
— — различные (distinct) 66—70
— суммирующие (summation) 21,
22, 9]
Монстр — пожиратель печенья (coo-
kie monster) 38—47
Мэйрсон (Mairson Harry George) 7
Наибольший общий делитель (grea-
test common divisor) 77
Неопределенные коэффициенты (un-
determined coefficients) 20
Неравенство Чебышева (Chebyshev’s
inequality) 54
Неявные уравнения (implicit equa-
tions) 50
Ионассен (Jonassen Arne Tormod)
9, 111
Йордан (Jordan Karoly) 18, 111
Кларксон (Clarkson Kenneth Lee) 7,
102
Кнут (Knuth Donald Ervin) 3—112
Конте (Comtet Louis) 73, 112
Обезьяна (ape) 84
Обращение Мёбиуса (Mobius inver-
sion) 68
Ограниченная вариация (bounded
variation) 62
Олвер (Olver Frank William John)
97, 112
Операторы собственные (cigcnopera-
tors) 38—48
— скользящие (sliding operators)
46—48, 85, 101—102
Лидеры цикла (cycle leaders) 27
Дюкер (Lueker George Schick) 21,
112
Метод Дарбу (Darboux’s method)
70—73, 76
— Лапласа (Laplace’s method) 76—
80, 82
Патерсон (Paterson Michael Ste-
wart) 38—48
Пейдж (Page Ewan Stafford) 18,
112
Перестановка (permutation) 86—88,
102—104
— на том же месте (in situ permu-
tation) 27
118
Указатель
Перестановка, получаемая с помо-
щью стека (obtainable with а
stack) 83
— пузырьковая сортировка (bubble
sort) 83, 90
— шейкер-сортировка (coctail sha-
ker) 83, 90
Пласе (Plass Michael Frederick) 31
Постоянная Г лейшера (Glaisher’s
constant) 97
— Эйлера (Euler’s constant) 53,56
Правило Лопиталя (i’Hospital’s
rule) 74
Принцип включения и исключения
(inclusion and exclusion) 12
— разделяй к властвуй (divide and
conquer) 33
Произведение Адамара (Hadamard
product) 76
Производящая функция (generating
function) 10, 13, 19, 21—22, 26,
31, 38—48, 70—82, 83-84, 89,
90—93, 99—100, 102- -104
Разбиение (partition) 54
Разложение Лорана (Laurent expan-
sion) 71, 74
— Ньютона (Newton’s expansion) 15
— Тейлора, обобщенное (Taylor’s
expansion, general) 15
— Тиле (Thiele expansion) 77—80
Разложение на множители (facto-
ring) 54—55
--------различных степеней (di-
stinct degree) 54—55
Райс (Rice Stepham Oswald) 32, 111
Райт (Wright Edward Maitland) 33,
68, 113
Раскрутка (bootstrapping) 49, 50,
57, 58, 59
Расчленение суммы (dissecting a
sum) 51, 57—60
Рекуррентные соотношения (recur-
rence relations)
-----вычитание (differencing) 23
-----линейные (linear) 18—27
-----нелинейные (nonlinear) 27—
37
— — с полной предысторией (full
history) 18, 23—27
— — с частичной предысторией (fi-
nite history) 18, 18—23
Реньи (Renyi Alfred) 113
Репертуарный подход (repertoire
approach) 23—27, 87
Решеточные пути (grid paths, lat-
tice paths) 9, 87, 105, 108
Pud (Read Rohald Cedric) Ill
Риордан (Riordan John) 11, 12, 112
Рота (Rota Gian—Carlo) 14, 15, 112
Руссо (Rousseau Cecil Clyde) 10
Сдвиг среднего (shifting the mean)
81—82
Седгевик (Sedgewick Robert) 112
Семиинварианты (semi-invariants)
77, 82
Символ C (O-notation) 49
Система MACSYMA 93—97
— METAFONT 7
- т X 7
b
Слейтер (Slater Lucy Joan) 16, 112
Слияние последовательностей (mer-
ging sequences) 31
Слоан (Sloane Neal James Alexan-
der) 34, 37. Ill
Смышленый (Quick Jonathan Hora-
tio) 85, 88, 104, 109
Соотношения обратимые (inverse
relations) 11—14
— — чебышевского типа (Cheby-
shev's inverse relation) 12
— ортогональные (orthogonal re-
lations) 11
Сортировка быстрая, вариант ме-
диана из трех (median-of-three
quicksort) 24
— поразрядная обменная (radix
exchange sort) 14, 106
Столарски (Stolarsky Kenneth Bar-
ry) 29, 112
Столфи (Stolfi Jorge) 93
Суммирование по частям (summa-
tion by parts) 62, 104
— формула Эйлера (Euler’s summa-
tion formula) 54; 60, 64—65, 93
Суммы цифр (digital sums) 29
Сю (Hsu Li-Che) 12, 111
Таблица инвеоенн (inversion table)
90
Теорема абелева (Abelian theorem)
52
— Вандермонда (Vandermonde’s
theorem) 16
— о вычетах (residue theorem) 74,
78, 100, 105—107
— тауберова (Tauberian theorem)
53. 56, 60
<— центральная предельная (central
limit) 76—81
Указатель
119
Траб Пардо (Trabb Pardo Luis Isi-
doro) 70, 112
Треугольник Паскаля (Pascal’s tri-
angle) 89, 108
Уилсон (Wilson Leslie Blackett) 18,
112
Уинклер (Winkler Phyllis Astrid
Benson) 7
Уиттекер (Whittaker, sir Edmund
Taylor 112
Факториальные степени (factorial
powers) 13—16
Фергюсон (Ferguson David Elton)
83-84
Формула Абеля—Плана (Abel—Pla-
na formula) 97
— Стирлинга (Stirling’s approxima-
tion) 53, 106
— суммирования Эйлера (Euler's
summation formula) 54, 60, 64—
65, 93
Фредмэн (Fredman Michael Lawren-
ce) 30 112
Хенричи (Henrici Peter) 16, 113
Хеширование, вторичное скучива-
иие (haghing, secondary cluster-
ing) 46—48, 85, 101—102
— равномерное (uniform) 45—46
— срастающееся (coalesced) 40—45
Хобби (Hobby John Douglas) 103
Числа (numbers)
— Бернулли (Bernoulli) 65
— гармонические (harmonic) cm.
Гармонические числа
— простые, асимптотика (prime,
asymptotics) 66
— Стирлинга (Stirling) 13, 82
— Фибоначчи (Fibonacci) 37
Шёнхаге (Schonhage Arnold) 18,
112
Шпигель (Spiegel Murray R.) 18,
20, 22, 113
Эрдёш (Erdos Pal) 113
Харди (Hardy Godfrey Harold) 33,
53, 68, 112—113
Яо (Yao Andrew Chi—Chin) 7
Оглавление
От редактора и переводчика , ............................ . . . 5
К русскому изданию ..............................................6
Предисловие .....................................................7
1. БИНОМИАЛЬНЫЕ ТОЖДЕСТВА
1.1, Сводка полезных тождеств................................ 8
1.2. Вывод тождеств.......................................... 9
1.3. Обратимые соотношения .................................. И
1.4. Операторное исчисление ................................ 14
1.5. Гипергеометрический ряд..................................15
1.6. Тождества с гармоническими числами.......................16
2. РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ
2.1. Линейные рекуррентные соотношения........................18
2.1.1. Частичная предыстория .............................. 18
2.1.1.1. Постоянные коэффициенты ...........................18
2.1.1.2. Переменные коэффициенты............................21
2.1.2. Полная предыстория ...................................23
2.1.2.1. Вычитание . .......................................23
2.1.2.2. Из репертуара......................................23
2.2. Нелинейные рекуррентные соотношения..................... 27
2,2,1. Соотношения с функциями максимума или минимума , . 27
2,2,2. Непрерывные дроби и другие скрытые линейные рекуррентные
соотношения .................................................31
2.2.3. Дважды экспоненциальные последовательности............33
3. ОПЕРАТОРНЫЕ МЕТОДЫ
3.1. Монстр—пожиратель печенья................................38
3.2. Срастающееся хеширование............................... 40
3.3. Открытая адресация: равномерное хеширование .............45
3.4. Открытая адресация: вторичное скучивапие.................46
4. АСИМПТОТИЧЕСКИЙ АНАЛИЗ
4.1. Основные понятия.........................................49
4,1,1. Обозначения ..........................................49
4.1.2. Раскрутка .......................... . ...............50
4.1.3. Расчленение .................................... ... 51
4.1.4. Пределы пределов ............................ 52
4.1.5. Сводка полезных асимптотических разложений............53
4.1,6, Пример ...............................................54
4.2. Интегрирование по Стилтьесу и асимптотике 60
4,2.1. Символ О и интегралы .................................63
4.2,2, Формула суммирования Эйлера...........................64
4.2.3. Теоретико-числовой пример........................... 66
4.3. Асимптотики из производящих функций......................70
4.3.1, Метод Дарбу ..........................................70
4.3,2. Метод вычетов.........................................74
4,3.3, Метод перевала ............................ .76
ЗАДАЧИ 83
РЕШЕНИЯ ЗАДАЧ 90
ПРИМЕЧАНИЯ РЕДАКТОРА И ПЕРЕВОДЧИКА ИО
ЛИТЕРАТУРА И!
д. э. кнут и его «фабрика книг» (дополнение переводчика) . . . .114
Указатель.................................................... 116