AOP_Tom1 (1021736), страница 34
Текст из файла (страница 34)
Дайте аснмпто- Г от и1 тическое представление о 1/4 / е (1+-) Ои с точностью до членов порядка О(х о) для фиксированного р и больших х 8. [НМУО] Пусть г(х) = 0(х") при х о оо и 0 < г < 1 Покажите, что ( ) =~'. 1(Ю г ~ ГГ(Ю Г о я ( 1)т-1 т~ о "(1+ -1 о(и = / ехр ~ — + — — . + ~ Ои+ 0(х '). о ~ 2х Зхо тх если т = [(я+ 21 ) 1'(1 — 1)]. [Отсюда, как частный случай, сле((уст результат, принадлежа- щий трикоми (тг!сот!) если г(х) = 0(угх), то НЫ и л 1(ы/Л7 1 / о "(1+ -) ((и = 1/2х х/ е ' 4(+О(1) ] о о ° 9.
[НМЯР] Как ведет себя функция /[х+ 1, рх)/'Г[х+ 1) при больших ху [Здесь р— действительная константа; и еслй р < О, мы считаем, что х — целое. чтобы З* было определеио и для отрицательных а) Найдите по меньшей мере два члена асимптотического представления, прежде чем использовать символ О. 10. [НМЯ4] При тех же предположениях, что и в предыдущем упражнении, при р ,-З 1, вайд/зте для фиксированного р асимптотическое представление функции .у[х+ 1, рх+ рр/[р — 1)) — 1[х+ 1, рх) о сз /с /[/с,и) = (1 — — ) ехр( — — — — — ).
Ь) Покажите, что для всех си > 0 и с > 0 величину /[/с, и) можно записать в виде 1гсзо — с-з + О[ ( пап/-с/гезю) 0 < / < з/г+с о< б/<ос с) Докажите, что как следствие из [Ь) имеем Е "'"У[ЬЛ)= — — /~у р-цз -з'/з +О[ — /г+з) Е ""' 0<1</ <и =о з>о .ля всех д > О. [Указание. Суммы по 2, где из/г+' < /с < оо, равны О[и ") для всех г.] П Покажите, что асимптотическое представление суммы 2 „>о/с'е з /г" для фиксированного с > 0 можно получить с помощью формулы суммирования Эйлера.
е) И наконец, покажите, что Е /с" 'е = и" е "~~ — — — — о+ ( — + -и+ -а )~) — +О[и )~ 2 б ~12 2 2 /)/2и эту формулу можно получить с точностью до членов порядка 0[и ") для любого г. 13. [НМ2Р] Найдите связь между интегралом / (1+ — ) е 'Рз и функцией Я[и).
с точностью до членов того же порядка, что и в предыдущем упражнении. э 11. [сзз1з25] Обобщим функции Я[и) и Щи), введя параметр х: и — 1 и — 1и — 2 С >[и) = 1+ — х+ — х + и п и и и и г Я,[и) = 1+ — х+ — — х +. и+1 и+1и+2 Исследуйте эти функции и найдите для них асимптотические формулы при х ~ 1. 12. [НМ2Р] Функцию ]о* е ' /г 41, которая появляется в связи с нормальным распределением [см. раздел 1.2.10), можно представить в виде частного случая неполной гамма-с'/г функции. Найдите значения а, 6 и у, такие, что 52[а, у) равно ]о е / с/с. 13. [НМ42] [С.
Рамануджан.) Докажите, что Я[и) — Я[и) = г + 8/'[135[/с+ д[и))), где з г, < Р[и) < —. [Отсюдаследуетболееслабый результат: Н[п+ц — я[и+1) < В[и) — я[и).) ь 14. [НМРР] [Н. Г, де Брейн.) Цель данного упражнения — пайти асимптотическое представление суммы 2 " /с"+ е для фиксированного а при и -з оо.
— з г/ г а) Заменив /с иа п — /с, покажите, что данная сумма равна и"+ е "Я" е /~"~[/с,и), где 16. [Мй,(] Докажите тождество С (-Ц" (п]1"-'д(й) =(-Ц"( — Ц, где. >О. 17. ]НМОО] (К. В. Миллер (К. Ъ7. Мййег).) Из соображений симметрии рассмотрим также четвертый ряд, который является для Р(п) тем, чем Н(п) является для 1е'(п): и и и+1 с (и+к — ц! В(п) = 1+ — + — — + и+ 1 и+ 2 и+ 2 (п — Ц'(и+ lс)ь ьйа Как выглядит асимптотическое представление этой функции? 18.
]М25] Покажите, что суммы 2 (ь))с~(п — /с)" "и 2 (ь)()с-тЦ" (и — )с)" "можно очень просто выразить через функцию Сч'. 19. (НМУО] (Лемма Васпсона (с(гаЬоп).) Покажите, что если интеграл С = / е "~у(х) с(х ао существует для всех больших и и если 1(х) = 0(х ) для О < х ( г, где т > О и о > -1, то — С(п-с"ь) ° 20.
]НМОО] Пусть и = св+ксв~+ — 'есо~ — +аж~+ = ~„~~, се со~ — степенной ряд, который является решением уравнения ш = (и~ — 1и~ + 1и — 1и~ + ) Гс (см. (12)). Покажите, что пс-1 1 — ьгс я(п) + 1 = ~~ )ссьГ(ц2)( — ) +О(п'" гс) ь=с для всех пс > 1. ]Указание. Примените лемму Ватсона к тождеству из упр, 15,] Я чувствую, что должна добиться успеха в математике, котя и не понимаю, почему зто так важно.
— ХЕЛЕН КЕЛЛЕР (НЕьЕН КЕ~~ ЕР) (1898) 1.З. МЕХ В этой книге ОЧЕНЪ ЧАСТО встречаются упоминания о внутреннем машинном яЗыкЕ компьютера. Причем использовать мы будем гипотетический компьютер под названием "М1Х". М1Х практически ничем не отличается от любого другого компьютера 60-70-х годов, только он, вероятно, более изящен. При разработке языка компьютера М1Х преследовалась цель сделать его достаточно мощным, позволяющим для большинства алгоритмов писать короткие програлгмы, н в то же время достаточно простым, чтобы его операции можно было легко запомнить Настоятельно рекомендую читателю внимательно изучить этот раздел, так как язык М1Х нсполь:устоя в очень многих разделах книги.
Отбросьте все сомнения по поводу того, стоит ли изучать машинный язык. Автор одн, жды повял, что нет ничего необычного в том, чтобы в течение одн~ й неде. и заниматься написанием программ на нескольких различных машинных языках! Каждый, кто серьезно интересуется компьютерами, должен рано или поздно изучить по крайней мере один машинный язык. При разработке НЕХ были специально сохранены основные черты реальных компьютеров, чтобы его характеристики можно было легко понять и усвоить.
Тем не менее нужно лрязнать, что в настоящее время МЕХ полностью устарел. Поэтому в последующих изданиях данной книги он будет заменен новым компьютером под названием ММЕХ (номер 2009). ММЕХ будет представлять собой так называемый компьютер с усеченным набором команд (ШЯС), который выполняет арифметические операции над 64-битовыми словамн. Будучи более изящным, чем М1Х, он станет аналогом тех компьютеров, которые в 90-х годах завоевалн ключевые позиции на рынке компьютерной техники. Полный и повсеместный переход в данной книге от МЕХ к ММ1Х отнимет много времени, поэтому огромная просьба к добровольцам — окажите посильную помощь в этом деле.
Между тем, автор надеется, что читатели согласятся лодонСдать еще несколько лет и пока удовлетворятся устаревшей архитектурой М1Х, которая все еще заслуживает внимания, поскольку обеспечивает среду для дальнейших разработок. 1.3.1. Описание МЕХ И1Х вЂ” это первый в мире полиненасыщениый компьютер~. Как и у большинства компьютеров, у него есть идентификационный номер — 1009. Этот номер получен следующим образом: взяли 16 очень похожих на МЕХ реальных компьютеров, на которых можно легко имитировать И1Х, а затем нашли среднее значение их номеров, взятых с равными весовыми коэффициентами: ~(360+ 650+ 709+ 7070+ 1)3 + 8880+ 1107+ 1604+ 620+ В220 + 82000+ 920+ 601+ Н800+ РПР-4+ П)/16~ = 1009. (1) Это же число можно получить значительно проще — прочитать слово м1Х как римское число.
Характерная особенность компьютера МЕХ состоит в том, что он является двоичным и десятичным одновременно. Программисты МЕХ на самом деле даже не знают, ' Аналогия с полнвенасыпееннымн жирами, шкроко рекламируемыми сегодня по всему миру.— Прим. верее. компьютер с какой арифметикой они программируют — с двоичной или десятпчиой Поэтому алгоритмы, написанные для М1Х, с небольшими изменениями можно использовать на любом из этих типов компьютеров и М1Х можно легко имитировать на этих компьютерах. Те программисты, которые привыкли к двоичному компьютеру, могут считать М1Х двоичным, а те, которые привыкли к десятичному, могут считать М1Х десятичным. Программисты же с другой планеты могут считать М1Х троичным компьютером.
Слова. Основной единицей информации является байт. Каждый байт должен принимать по меньшей мере 64 различных значения, но реальный объем содержащейся в байте информации может быть разным. Таким образом, в одном байте может содержаться любое число от 0 до 63 включительно. Более того, в каждом байте может содержаться максимум 100 различных значений. Следовательно, в двоичном компьютере байт должен состоять из шести разрядов, а в десятичном— из двух*. Программы на языке М1Х должны быть написаны так, чтобы в байте содержалось не более 64 значений.
Так, для представления числа 80 мы всегда будем выделить два байта, хотя в десятичном компьютере для этого достаточно одного байта, Алгоритм на языке МЕХ должен работать лрвлпльио независимо от размера байта. Конечно, вполне возможно написать программы, зависящие от размера байта, но в данной книге такие действия осуждаются н допустимыми считаются только те программы, которые дают правильный результат независимо от размера байта Обычно придерживаться этого основного правила совсем нетрудно, и, таким образолг, мы обнаружим, что программирование на десятичном компьютере не особенно отличается от программирования на двоичном.
С помощью двух соседних байтов можно выразить числа от 0 до 4 095. С помощью трех соседних байтов можно выразить числа от 0 до 262 143. С помощью четырех соседних байтов можно выразить числа от 0 до 16 777 215. С помощью пяти соседних байтов можно выразить числа от 0 до 1 073 741 823. Машинное слово состоит нз ляхи байтов и знака. Знак может принимать только два значения: н+н и "— ".
Регистры. В компьютере М1Х всего девять регистров (рис. 13). Регистр А (аккумулятор) содержит 5 байт и знак. Регистр Х (расширение аккумулятора) тоже содержит 5 байт и знак В регистрах 1 Гиндексных регистрах) 11, 12, 13, 14, 15 и 16 содержится по два байта и знак. Регистр Я (адрес перехода) содержит два байта; его знак — всегда '+".
Для обозначения регистра компьютера М1Х будем использовать в качестве приставки к имени регистра строчную букву нг'. Таким образом, нгАн обозначает "регистр А". Регистр А имеет много применений, особенно часто он используется прн выполнении арифметических действий и операций над данными. Регистр Х используется * Приблизительно с 1975 года слово "байт" стало обозначать последовательностгь состоящую ровно из восьми двоичных пнфр, что позволяет представлять числа от О до 255 ГГоэтому размерш бай гон реальных компьютеров больше, чем размеры байтов гипотетической машины М1Х И в самом деле, старомолные байты компьютера М1Х только чуть-чуть больше. чеи половина бай~а реального компьютера Говоря о байтах применительно к М!Х, мы будем придерживаться прежнего згычения этого июва, вновь возвращаясь к тем дням, когда поня~ив байта еще не было так стандартизовано Регистр А Регистр Х Регистр !1 П4 115 О , ° Флаг ® Индикатор переполнения Я © сравнения Регистр 12 Регистр 13 Регистр !4 Регистр 15 Регистр 1б Регистр ! М$ $ Магнитные ленты Диски и барабаны 130 Ш "° 177 138 "° Ш4 Ш5 1716 Ш7 ШЗ Ш9 Рис.
13. Компьютер И1Х. для расширения вправо регистра А и вместе с гА — для хранения 10 байт произведения нли делимого. Он молгет применяться и для хранения информации, сдвинутой вправо из гА. Индексные регистры г11, г12, г!3, Н4, г15 и г16 используются, главным образом, как счетчики и для ссылок на различные адреса памяти. В регистре .1 всегда хранится адрес команды, которая следует за последней операцией "перехода"; этот регистр используется, главным образом, для вызова подпрограмм. Помимо регистров, компьютер 81Х содержит следующие элементы: глриггер переполнения (один бит, который может принимать значение "нуль" или "единица"); флаг сравнения (принимающий одно из трех значений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
