► 9. [НМ36] Как ведет себя функция 7(х + 1, рх)/Г{х + 1) при больших х? (Здесь р - действительная константа; и если р < О, мы считаем, что х - целое, чтобы было определено и для отрицательных i.) Найдите по меньшей мере два члена асимптотического представления, прежде чем использовать символ О.

10. [НМ34] При тех же предположениях, что и в предыдущем упражнении, при р ф 1, найдите для фиксированного у асимптотическое представление функции

7(х + 1, рх + ру/{р- 1)) -7(х + 1, рх)

с точностью до членов того же порядка, что и в предыдущем упражнении.

► 11. [НМ35] Обобщим функции Q{n) и R{n), введя параметр х:

„ , . , п-1 п- 1п- 2 2 .

Qx(n) = 1 -I--X +--х + ,

п п п

ДЛп) = 1 + -х+ " " хЧ---. п+1 п+1п+2

Исследуйте эти функции и найдите для них асимптотические формулы при х ф 1.

12. [НМ20] Функцию Ц е~* dt, которая появляется в связи с нормальным распределением (см. раздел 1.2.10), можно представить в виде частного случая неполной гамма-функции. Найдите значения а, 6 и г/, такие, что 67(0, у) равно f е~ dt.

13. [НМ42] (С. Рамануджан.) Докажите, что Е{п) - Q{n) = f 4- 8/(135(n 4- в{п))), где il < 9{п) < . (Отсюда следует более слабый результат: R{n+1)-Q{n+1) < R{n)-Q{n).)

► 14. [НМ39] (Н. Г. де Брейн.) Цель данного упражнения - найти асимптотическое представление суммы ,1=0 для фиксированного а при п оо.

a) Заменив к па п - к, покажите, что данная сумма равна п"+°е~"Е(, е""*"/! ")> где

/(.,n)=(l-)%xp(--l-...).

b) Покажите, что для всех m > О и б > О величину f{k, п) можно записать в виде

с.к+п-- + 0{n+-"+), если О < < п"+.

0<t<j<m

c) Докажите, что как следствие из (Ь) имеем

J2e-"f{k,n)= с.,п--к"+е-"+0{п-+)

=0 0<t<j<m it>0

.ля всех 6 > 0. [Указание. Суммы по к, где п+ < А: < оо, равны 0{п~) для всех г.] I) Покажите, что асимптотическое представление суммы I3it>o"* фиксиро-

занного t>0 можно получить с помощью формулы суммирования Эйлера, е) И наконец, покажите, что

gr-.- . „-е-. (У™ - 1 - . . (± + 1. + +

эту формулу можно получить с точностью до членов порядка 0(n~) для любого г. 15. [НМ20] Найдите связь между интегралом

и функцией Q{n).

16. [М24] Докажите тождество

= - 1) где п > 0.

17. 1НМ29] (К. В. Миллер (К. W. Miller).) Из соображений симметрии рассмотрим также четвертый ряд, который является для Р{п) тем, чем R{n) является для Q{n):

"-l+n+l +п + 2 П + -Z.(n-l)(n+fc)=-

Как выглядит асимптотическое представление этой функции?

18. [М25] Покажите, что суммы Y: и (;j)(fc-fl)*(n-fc)"-* можно очень просто выразить через функцию Q.

19. [НМЗО] (Лемма Ватсона (Watson).) Покажите, что если интеграл

Сп = e-f(x)dx

существует для всех больших п и если /(х) = 0(х°) для О < х < г, где г>0иа>-1, то С„=0(п--°).

► 20. [НМЗО] Пусть U = ги + ги + ги-27о""1----= Cjttu*-степенной ряд, который

является решением уравнения w = (и - + - Н----) (см. (12)). Покажите,

тп-1 ч 1 -Jc/2

Q(n) + 1 = Е =с*Г(Л/2) (I j + 0(п-)

для всех m > 1. [Укозокие. Примените лемму Ватсона к тождеству из упр. 15.]

Я чувствую, что должна добиться успеха в математике, хотя и не понимаю, почему это так важно.

- ХЕЛЕН КЕЛЛЕР (HELEN KELLER) (1898)

1.3. MIX

в этой книге ОЧЕНЬ ЧАСТО встречаются упоминания о внутреннем машинном языке компьютера. Причем использовать мы будем гипотетический компьютер под названием "MIX". MIX практически ничем не отличается от любого другого компьютера 60-70-х годов, только он, вероятно, более изящен. При разработке языка компьютера MIX преследовалась цель сделать его достаточно мощным, позволяющим для большинства алгоритмов писать короткие программы, и в то же время достаточно простым, чтобы его операции можно было легко запомнить

Настоятельно рекомендую читателю внимательно изучить этот раздел, так как язык MIX исполь .уется в очень многих разделах книги. Отбросьте все сомнения по поводу того, стоит ли изучать машинный язык. Автор однажды понял, что нет ничего необычного в том, чтобы в течение одной неде]и заниматься написанием программ на нескольких различных машинных языках! Каждый, кто серьезно интересуется компьютерами, должен рано или поздно изучить по крайней мере один машинный язык. При разработке MIX были специально сохранены основные черты реальных компьютеров, чтобы его характеристики можно было легко понять и усвоить.

fTeM не менее нужно признать, что в настоящее время MIX полностью устарел. Поэтому в последующих изданиях данной книги он будет заменен новым компьютером под названием MMIX (номер 2009). MMIX будет представлять собой так называемый компьютер с усеченным набором команд (RISC), который выполняет арифметические операции над 64-битовыми словами. Будучи более изящным, чем MIX, он станет аналогом тех компьютеров, которые в 90-х годах завоевали ключевые позиции на рынке компьютерной техники.

Полный и повсеместный переход в данной книге от MIX к MMIX отнимет много времени, поэтому огромная просьба к добровольцам - окажите посильную помощь в этом деле. Между тем, автор надеется, что читатели согласятся подождать еще несколько лет и пока удовлетворятся устаревшей архитектурой MIX, которая все еще заслуживает внимания, поскольку обеспечивает среду для дальнейших разработок.

1.3.1. Описание MIX

MIX - это первый в мире полиненасыщенный компьютер*. Как и у большинства компьютеров, у него есть идентификационный номер -1009. Этот номер получен следующим образом: взяли 16 очень похожих на MIX реальных компьютеров, на которых можно легко имитировать MIX, а затем нашли среднее значение их номеров, взятых с равными весовыми коэффициентами:

(360 + 650 709 7070 -f U3 -f SS80 + 1107 + 1604 -f G20 + В220

+ S2000 -)- 920 -)- 601 -)- Н800 -)- PDP-4 -)- II)/16j = 1009. (1)

Это же число можно получить значительно проще - прочитать слово MIX как римское число.

Характерная особенность компьютера MIX состоит в том, что он является двоичным и десятичным одновременно. Программисты MIX на самом деле даже не знают,

* Аналогия с полинеиасыщенными жирами, широко рекламируемыми сегодня по всему миру. - Прим. перев.