Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 73
Текст из файла (страница 73)
° (и) +. + 2, г .,э(п)) -„'2,' (г(х) — е(х))а~'(и) + О („-), где х = хз .. хы содержит г(х) нулей на нечетных позициях и в(х) нулей на четных позициях. Согласно (2х)-распределенности величина в скобках стремится к я(2гь ')/2ы = ху2. Оставшаяся сумма, очевидна, максимальна, если ых(п) = и<(п), когда г(х) > э(х), а и~(п) = О, когда г(х) < е(х). Так что максимум правой части равен — + ~~~ (г — з)( ) ~ )/2гэ = — +й( )/2~ . оба<~<э Сейчас Рг(Хэ„= О) < )ипею„~~ иео(2п)/и. Таким образом, доказательство завершено.
Заметим, что получено ) ( ) шак(г,э) ж 2п2т" +п~ ); ) ~ ) ппп(г,в) =2ц2" — и( ). ° .а 30, Постройте диграф с 2ээ вершинами, обозначенными (Ех~... хэе-т) и (Ох~... хээ-~), где каждое х равно либо О, либо 1. Пусть 1 + у(хм хт,..., хгь) — ориентированные ребра яз (Ех~...хм ~) к (Охт...хэь), а 1-у(хмхм „хть) — ориентированные ребра, ведущие из (Ох~... хэь- ~ ) к (Ехт... хы), где у (хм хт, °, хм ) = з(бв(х~ — хэ + хэ — хэ + — хть) Мы обнаружим, что каждая вершина имеет столько же ребер, ведущих к ней, сколько ребер, ведущих от нее. Например, (Ех~...хм ~) имеет 1 — У(б,хм,хы-~) + 1 — Д1,хц...,хы-~) ведущих к ней ребер, 1+ т(хм...хээ-мб) +1+ у(хц.,хэг-ц1) ребер, везущих от нее, и 1(х, хп . ", хтэ-~) = — у(хм..., хы,, х).
Опустим все вершины, не имеющие путей, ведущих к ним либо исходящих из них, т. е. (Ех~...хть ~). если 1(б,хц °,хээ-~) = +1, или (Ох~...хы ~), если Д1,хц...,хэь ~) = -1, Полученный ориентированный граф является связным, так как мы можем добраться из любой вершины к (Е1010...1) и из этой точки — к любой требуемой вершине. Согласно теореме 2,3,4.2О существует циклический путь, проходящий через каждое ребро длиной 2м+', к можно цредположнть, что он начинается в вершине (Е00...
О). Построим циклическую последовательность с Х~ = . = Хгь ~ = 0 и Ля~та ~ = хэю если и-е ребро — это путь из (Ехт. хэь-~) к (Охэ...хгь) или из (Ох~ *хгь-~) к (Ехэ...хы). Например, граф дэя я = 2 показан на рис. А — $; ребра циклического пути пронумерованы от 1 до 32 и циклическая последовательность имеет вид (0000100011001010100П01110111110)(00001 ...). Заметим, что в этой последовательности Рг(Хт = О) = Ц. Очевидно, что последователь. ность (2<)-распределена, так как каждая строка размерности (2х) х,хэ...хгэ появляет~я 1+ у(хц, хы) + 1 — у(хм, хы) = 2 раз за цикл. Тот факт, что Рг(Хэ„= О) имеет требуемое значение, вытекает из факта, что при этом построении достигается максимальное значение правой части равенства в доказательстве предыдущего упражнения.
Рис. А-б. Ориентированный граф из упр. 30. 31. Используйте алгоритм Ж с правилом «с«выбора полной последовательности, (Для обобщения этого типа неслучайного поведения в М-последовательностях обратитесь к работе Леал Ъ'!!!е, Е«Ые Сг!««Оие с(е !а «кобол «(е Сойесг«Г (Раг(з, 1939), $5-62, Возможно, определение Вб таки«е слишком слабое с этой точки зрения, однако такой контрпример неизвестен.) 32. Коли «с, «с' — исчисляемые правила подпоследовательностей, то существует «с'* = М.«с', определенное такими функциями: у„"(хо,...,х„«) = 1 тогда и только тогда, когда «с определяет подпоследовательность х„, ..., х„из последовательности хе,, х„«, где Й > О, 0 < г«« . г» < и и у»(х„„...,хг») = 1, Тогда (Х„)КЖ' равна ((Х„) с)«ь', Результат слелует незамедлительно.
ЗЗ. Зададим е > 0 и найдем такое д«о, при котором неравенство Ф > !»о~ влечет оба неравенства !«„(!««)/!«« — р( < с и )и»(!««)/«»' — р( < с. Затем найдем такое «»«, при котором из «»' > !««следует, что $л равно гм или эм для какого-либо М' > Ле. Из М > «т«следует, что (») ! 1е«л«Г,~Ж) ! 5,»»)- х.х «к)-р»,5 34.
Например, если двоична«ь«представлением! являеггл (1 0» 1 0" 1 1 0'» 1 ... 1 0" )», где "О'" — обозначение последовательности из а нулей. Пусть правило Я,«принимает У„ тогда и только тогда, когда (Ь««" ») = а«, ..., (ЬУ «! = а». Зб. Пусть ое = »е и а +« = щах(в» ) О < Ь < 2' ). Построим правило подпоследовательностей, выбирающее элемент Х„тогда и только тогда, когда и = »» для некоторого й < 2", когда и прилэдлежит интервалу а < и < а +«.
Тогда !пп,ы и(а )/а Зб. Пусть Ь и Ь вЂ” произвольные, однако фиксированные целые числа, боль«пие, чем 1. Пусть У'„ы '(ЬЬ«). Для произвольной бесконечной подяоследоват«щьности (Я„) = (У,„)Я., определенной алгоритмами 8 и К (как в доказательстве теоремы М), существует простое, но трудно записываемое соответствие алгоритмам 8' и Й', которые просматривают Х«, Хсесс ., Хс»с и/или выбирают Лс, Хсес, Хс»мсыв-с,с! из (Л„) тогда и только тогда, когда 3 и сс просматривают и/нли выбирают сс, где Ус = (О.ХсХсас Хсе )ь Алгоритмы К и сс' определяют бесконечную 1-распределенную подпоследовательность (Л ), и фактически (как в упр. 32) эта полпоследовательность является оо-распределенной, поскольку она (Ь,1)-распределена.
Таким образом, мы определили, что Рг(З„= а) и Рг(З„ы а) отличаются от 1/Ь менее чем на 1/2". [Результат этого упражнении справедлив, если "Вб" заменить посл»донат»льна на "К4" кли '"Ю", но он не верен, если использовать '"111,с так как Х может быть (с) тождественно равен нулю.) 37. Для и > 2 замените У„с на -'((с„с+б ), где б = 0 или 1 в зависимости от того, четное илн нечетное число элементов, меньших -', содержит множество (УС„с!с»„...,У„с [Ассгэпсев !и Магб. 14 (1974), 333-334; см, также РЬ. Гс, ГЬ»в!э Томаса Н. Герцога (ТЬоспэв В.
Негхоб, 1сшг. о( Магуйшб, 1975).[ 39. См. Асса Агсййлсегсса 21 (1972), 48-80. Наилучшее возможное значение с неизвестно. 40. Так как Рв зависимы только наВс... Вв, пачучим Р(Ас, Зл) = -', Пуссь9(Вс... Вв) = Рг(Вв»с = 1 [ Вс... Вс), где вероятность берется по всем элементам Я, имеющим Вс . Вв в качестве первых Ь двоичных разрядов. Аналогично пусть дс(Вс... Вс) = Рг(Рв = 1 и Вь»с — — Ь [ Вс...
Вв). Тогда получим Рг(Ав =! [ Вс... Вв)= Рг((Рв+Ввс с+Во с) шос)2=1 [ В "Вь) = 7 (в-9»+Ос)+(1 — 9) (В+-,'-Ос) = в — (О» 4 Ос)+2(99 +(! — 9)9) = 1 — Рг(Рв = 1 [ Вс... Вв) + 2рг(Рс = 1 и В„'+, —— Вь»с [ Вс... Вв). Следовательно, Рг(Ав — — 1) =~ „, в, Рг(Вс...Вс,)Рг(А, =1[Вс...В„) ы 1в — Рг(Рв =1)+Рг(Рс.„с =1). [См. теорему 4 в работе Со!с)ге!»Ь, Оо!дкавсег, апс! М!са)1, .ГАСМ ЗЗ (1986), 792-807.] 41. Выберите Ь равномерно из (О,..., ссс- 1) и воспользуйтесь построением нз доказательства леммы Р 1.
Тогда из доказательства Р1 будет следовать, что А' равно 1 с вероятностью Е» о (в рв+рв+с)/!сс' 12. (а) Пусть Х = Х, + . + Х». Очевидно, что Е(Х) = псс, и мы илсеем Е((Х вЂ” псс) ) = ЕХ'- 'р' = ЕХ,'+2[-„с„,„(ЕХ)(ЕХ) — '„' = ЕХ,'- П' ', Т Е((Х вЂ” пвс)в) = 2, хРг((Х-пвс)) = х) > ~яйыго х Рг((Х вЂ” пгс)~ = Я) > ~„~,„,о !с~эх Рг((Х вЂ” пр)з = л) = ! в Рг((Х вЂ” )з > ! в).
(Ь) Существует индекс с, такой, что сс ф с';, скажем, с; = О и с'; = 1. Тогда существует такой индекс у, что с ж 1. Для любого фиксированного набора из !с — 2 строк в матрице В, номер которых не равен с или у, получим (сВ, с'В) = (с1,4') тогда и только тогда, когда строки с и у имеют частные значения (это происходит с вероятностью 1/2в ). (с) В обозначениях алгоритма Ь возьмем и м 2" — 1 и Х, = (-1)пы +"", тогда р = в и ав = 1 — вв.
Вероятность, что Х = 2„Л, отрицательна, не больше вероятности того, что (Х вЂ” пд)» > ссзрз. Согласно (а) это не больше, чем а~/(пвс~). 43. Заключение для фиксированного М не представляет янтереса, так как, очевидно, сушествует алгоритм для нахождения множителей любого фиксированного М (т.
е, алгоритм для нахождения множителей). Теория применима ко есем жчгоритмам, имеющим короткое время счета, а не только к алгоритмам, которые эффективно находят множители. 44. Если каждое изменение одного числа в случайной таблице приводит к случайной таблице, то все таблицы случайны (или ни одна не существует). Если мы не допускаем степеней случайности, то ответ должен, следовательно, быть "Не всегда". РАЗДЕЛ 3.6 1.
ИАИО1 571 БТА ЮА ЮЛ, 1ИСН 107 51АХ НТА ЖП. ТИСА 9Н 1ИР ТИАИО СОИ 8Н СОИ 7Н СОИ 99 89 ХНАИО 79 1009 в+1 5 ХИАИР 89 1 в 1 0 3141592621 Запоминание выходной ячейки. Запоминание значение Ь. гА+- Х. гАХ в- аХ. гХ в- (аЛ + с) шоб ш. Гарантия, что перепачнение выключено. гА +- (аХ + с) шоб ш. Запоминание Л'. гА в- (ЬХ/ш), Добавить 1, чтобы 1 < г' < Ь. Возврат.
Значение Х; Хо =- 1. Высгрое запоминание Ь. Множитель а. $ 2. Помещение генератора случайных чисел в программу дает,по существу, непредсказуемый для программиста результат. Если бы поведение мшпины в каждой задаче было известно заранее, немногие программы были бы когда-нибудь написаны. Как говорид Тьюринг (Тпгшб), действия компьютера очень часто преподнослтп сюрприз программисту, в особенности при отладке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
