Д. Кнут - Искусство программирования том 1 (1119450), страница 33
Текст из файла (страница 33)
Дополнительную информацию по этой теме можно найти в прекрасной книге Н. Г. де Брейна (Л!. С. бе Вгп!]и) АэутргоНс Мейобз !и Апа)уз!я (Ашзсегг[аш: ХогСЬ-Но!!апб, 1961) (Н. Г, де Брейн, Асимптотическпе методы в анализе.— Мс Изд-во иностр. лит., 1961). За более свежей информацией обратитесь к работе А. М.
06!ух)со, НапНЬоой о/СотЬтасопсэ 2 (М1Т Ргезз, 1995), 1063-1229, в которой содержится 65 подробных примеров и подробная библиография. УПРАЖНЕНИЯ 1. [НМОО] Докажите формулу (5) индукцней по и. 2. [НМОО] Выведите (7) иэ (6). 3. [МОО] Выведите (8) из (7). ° 4. [НМ1 0] Докажите соотношение (13). 5. [НМ24] Покажите, что в соотношении (21) Н имеет порядок 0(п" е "). б. [НМОО] Докажите соотношение (23). 7. [НМОО] Оценивая 1м мы рассматривали интеграл / е "~1+ -) Ов. Дайте асимптотическое представление о г / е "~1+ -) Ыи с точностью до членов порядка 0(х ~) для фиксированного у и больших х 8.
[НМОО] Пусть /(х) ы 0(х") при х -> оо и 0 ( г ( 1 Покажите. что 1 ( ) =ь'. П'> г вэ ГП*1 у- з з ( — 1) е "~1+ -) Ои = / ехр ~ — + — — + ) Ои+0(х '), х ~ 2в Зхз глх ' / если гп = [(в+ 2г)/(1 — г)]. [Отсюда, как частный случай, следует результат, принадлежа- щий Трикоми (Тпсопп) если /(х) = 0(~/х), то пю, х и НЛ* / е "(1+ — ) с1и = ъ/2х~ е ' (И+0(1)! 9. ]НМЮ6] Как ведет себя функция /(х+ 1, рх)/'Г(х+ 1) при больших ху (Здесь р— действительная константа; и еслй р < О, мы считаем, что х — целое, чтобы Г' было определено и для отрипательных й) Найдите по меньшей мере два члена асимптотического представления, прежде чем использовать символ О.
10. ]НМЯб'] При тех же предположениях, что и в предыдущем упражнении, при р ~ 1, найдите для фиксированного у асимптотическое представление функции З(х+ 1, рх+ ру/(р — 1)) — у(х+ 1, рх) / гб Ю вЂ” -б + 0/ (твб-1К-)/гб-ЗО1 О < / < г/г.~-г /. сч ой.<бб с) Докажите, что как следствие из (Ь) имеем е / "у(й,п) = — -г Ч ~ г б-б -гг/г~ — /гб-б) Е бйо о<~<г<т .ля всех 5 > О.
]Указание, Суммы по й, где и'/бы < й < оо, равны 0(п ") для всех г.] б — бг/гв П Покажите, что асимптотическое пРедставление сУммы 2 ьйо й'е ~ /г" длЯ фиксиРоеанного г > О можно получить с помощью формулы суммирования Эйлера. е) И наконец, покажите, что й е =и е / — — — — о+~ — +-сг+-а ))/ — +0(п ) -~в -б»-)а -~ /яп п1 1 1 1 гг гг -1 ),)/ 2 б 112 2 2 )]/2п зту формулу можно получить с точностью до членов порядка 0(п ") для любого г.
18. (НМ80] Найдите связь между интегралом ]1+ — ) е *6г н функцией Я(п). с точностью до членов того же порядка, что и в предыдущем упражнении. ь 11. ]НМ35] Обобщим функции 0(п) и В(п), введя параметр х: и — 1 и — 1п — 2 г Я,(п) = 1+ — х+ — — х + и и и и и г В,(п) =1+ — х+ — — х +. и+1 и+1п+2 Исследуйте зги функции и найдите для них асимптотические формулы при х Ф 1. -бг/г 12. ]НМ26] Функцию /о*е '/гЖ, которая появляется в связи с нормальным распределением (см.
раздел 1.2.10), можно представить в виде частного случая неполной гаммаг бг/г функции, Найлите значения а, 6 н у, такие, чтоб./(а,у) равно ]о*с '/гЖ, 13. ]НМ/8] (С. Рамануджан.) Докажите, что Я(п) — Я(п) = г + 8/(135(п + В(п))), где 21 < д(п) < б . (Отсюда следует более слабый результат: В(п+1)-Сб(п+1) < Я(п) — Я(п).) ° 14. ]НМур] (Н. Г, де Брейн.) Цель данного упражнения — найти асимптотическое представление суммы ~" й"е е ~ для фиксированного а при и -б оо.
-бг/г а) Заменив й на и — й, покажите, что данная сумма равна и"" е "2 „" е /г"/(й, и), где а /г йб Пй,.)=(1--) -р(- —,— —,— ) Ь) Покажите, что для всех гл > О и е > О величину /(й, п) можно записать в виде 16. [М2а[ Докажите тождество (-1)" ( )к" ~Я(/с) = ( — 1)" (и — 1)', где п > О.
17. [НМ20[ (К. В. Миллер (К. Ч'. М!!!ег).) Из соображений симметрии рассмотрим также четвертый ряд,который является для Р(и) тем,чем Н(п) является для е(п): и и п<Ь1 чз (п+2 — 1).' В(п)ж 1 + + и+1 пч-2 и+2 с (и — 1)1(и+2)" ейо Как выглядит асимптотическое представление этой функции? 16. [М25] Покажите, что суммы 2 (е))гь(п — 'х)™ и 2 (")(!с+1)"(и — 2)" "можно очень просто выразить через функцию 0.. 19.
[НМ90[ (Лемма Ватсона (Ма!еоп).) Покажите, что если интеграл С„= ! е 1(х)ах lо сущегтвует для всех болыпих и и если г(х) = 0(хя) для О < х < г, где г > О и а > — 1, то Св ж 0(п ' "). ь 20. [НМ90[ ПУсть и = ш+йш~+ зев~- — '~ш~+ . = 2 ~, сеш" — степенной Рад, котоРый является решением уравнения ш = (из — зиз+ 1зи4 — зиз+ )Ыз (см. (12)). Покажите, что и — 1 п 1-й/2 Я(п)+1 = ~~~ йсьГЯ2)( — ) +0(п' ч ) мю для всех т > 1. [Указание. Примените лемму Ватсоиа к тождеству из упр. 15.[ Я чувствую, что должна добиться успеха в математике, хотя н не лоннмаю, почему это так важно. — ХЕЛЕН КЕЛЛЕР (НЕьЕй КЕ! 1.Е!ч) (1898) 1.3.
М1Х В этой книги очкнь часто встречаются упоминания о внутреннем машинном языке компьютера. Причем использовать мы будем гипотетический компьютер под названием жй11". И1Х практически ничем не отличается от любого другого компьютера 60-70-х годов, только он, вероятно, более изящен. Прн разработке языка компьютера И1Х преследовалась цель сделать его достаточно мощным, позволяющим для большинства алгоритмов писать короткие программы, и в то же время достаточно простым, чтобы его операции можно было легко запомнить Настоятельно рекомендую читателю внимательно изучить этот раздел, так как язык М1Х исполь:уется в очень многих разделах книги.
Отбросьте все сомнения по поводу того, стоит ли изучать машинный язык. Автор одн. жды понял, что нет ничего необычного в том, чтобы в течение одн й недели заниматься написанием программ на нескольких различных машинных языках! Каждый, кто серьезно интересуется компьютерами, должен рано или поздно изучить по крайней мере один машинный язык. При разработке М1Х были специально сохранены основные черты реальных компьютеров, чтобы его характеристики можно было легко понять и усвоить. Ф Тем не менее нужно признать, что в настоящее время М1Х полностью устарел.
Поэтому в последующих изданиях данной книги он будет заменен новым компьютером под названием ММ1Х (номер 2009). ММ1Х будет представлять собой так называемый компьютер с усеченным набором команд (ШБС), который выполняет арифметические операции над 64-битовыми словами. Будучи более изящным, чем М1Х, он станет аналогом тех компьютеров, которые в 90-х годах завоевалп ключевые позиции на рынке компьютерной техники. Полный и повсеместный переход в данной книге от М1Х к ММ1Х отнлмет много времени, поэтому огромная просьба к добровольцам — окажите посильную помощь в этом деле. Между тем, автор надеется, что читатели согласятся подождать еще несколько лет н пока удовлетворятся устаревшей архитектурой М1Х, которая все еше заслуживает внимания, поскольку обеспечивает среду для дальнейших разработок. 1.3.1.
Описание М1Х И1Х вЂ” это первый в мире полиненасыщенный компьютер~. Как и у большинства компьютеров, у него есть идентификационный номер — 1009. Этот номер получен следующим образом: взяли 16 очень похожих на М1Х реальных компьютеров, на которых можно легко имитировать И1Х, а затем нашли среднее значение их номеров, взятых с равными весовыми коэффициентами: ((360+ 650+ 709+ 7070+ ПЗ+ ББ80+ 1107+ 1604+ 020+ В220 + 82000+ 920+ 601+ Н800+ РПР-4+ П)/16~ = 1009.
(1) Это же число можно получить значительно проще — прочитать слово М1Х как римское число. Характерная особенность компьютера М1Х состоит в том, что он является двоичным и десятичным одновременно. Программисты М1Х на самом деле даже не знают; ' Аналсгин с полннеиасыщеиными жирами, широко рекламируемыми сегодня во всему миру.— Прим, перев. компьютер с какой арифметикой опп программируют — с двоичной пли десятпчпой Поэтому алгоритмы, написанные длн И1Х, с небольшими изменениями можно использовать на любом иэ этих типов компьютеров и И1Х можно легко имитировать на этих компьютерах. Те программисты, которые привыкли к двоичному компьютеру, могут считать И1Х двои гным, а те, которые привыкли к десятичному, могут считать И1Х десятичным.
Программисты же с другой планеты могут считать И1Х троичным компьютером. Слова. Основной единицей информации является байт. Каждый байт должен принимать по меньшей мере 64 различных значения, но реальный объем содержащейся в байте информации может быть разным. Таким образом, в однова байте может содержаться любое число от 0 до 63 включительно. Более того, в каждом байте может содержаться максимум 100 различных значений. Следовательно, в двоичном компьютере байт должен состоять из шести разрядов, а в десятичном— из двух*. Программы на языке И1Х должны быть написаны так, чтобы в байте содержалось не более 64 значений.
Так, для представления числа 80 мы всегда будем выделять два байта, хотя в десятичном компьютере для этого достаточно одного байта. Алгоритм па языке И1Х должен работать правильно независимо от размера байта. Конечно, вполне возможно написать программы, зависящие от размера байта, но в данной книге такие действия осуждаются и допустимыми считаются только те программы, которые дают правильный результат независимо от размера байта Обычно придерживаться этого основного правила совсем нетрудно, и, таким образом, мы обнаружим, что программирование на десятичном компьютере не особенно отличается от программирования на двоичном. С помощью двух соседних байтов можно выразить числа от 0 до 4 095. С помощью трех соседних байтов можно выразить числа от 0 до 262 143.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
