AOP_Tom2 (1021737), страница 181
Текст из файла (страница 181)
+ 2 щ .а(п)) ~ 2' (г(х) — в(х))и (п) + О (~ ), где х = хп .. хы содержит г(х) нулей иа нечетных позициях и з(х) нулей на четных позициях. Согласно (2Й)-распределенности величина в скобках стремится к й(2е" ')/2 " = Й/2. Оставшаяся сумма, очевидно, максимальна, если и~~(п) = гь(п)> когда г(х) > е(х), а пи(п) = О, когда г(х) < э(х), Так что максимум правой части равен -+ ) (е — з)( )( )/2~" = — +Й( )/2 о<ь<г<Ь Сейчас Рг(Хз = О) < 11шзпр„ ие (2п)(п. Таким образом, доказательство завершено. Заметим,что получено ( )( ) шах(г,з) =2п2" ~+и( ); ) '(")(") ш1п(гга) =гпг'"-'-и( " '). 30.
Постройте диграф с 2ы вершинами, обозначенными (Ехю .. хзь-~) и (Ох~ ... хы — ~), где каждое хз равно либо О, либо 1, Пусть 1 + у(хм хм...,хзь) — ориентированные ребр" из (Ехз хы-з) к (Охз... хы), а 1 — ~(хм хм...,хзь) — ориентировюаные ребра, ведущие из (Ох~... хы-д) к (Ехг... хы), где г(хм хг, хы) = з1йп(х~ — хз + хз — ха + . — хзь). Мы обнаружим, что каждая вершина имеет столько же ребер, ведущих к ней, сколько ребер, ведущих от нее.
Например, (Ехь... хы-~) имеет 1 — з(0,хп,хзь-~) + 1 — г'(1,хм...,хы ~) ведущих к ней ребер, 1+ г'(хм...,хть мб) + 1+У(хм...,хы-м1) ребер, ведущих от нее, и у(х, хп ..,, хаь ~) = -у(хц..., хы мх). Опустим все вершины, не имеющие путей, ведущих к ним либо исходящих из них, т. е. (Ех~... хеь ~), если У(0~хм,хы-~) = +1, или (Ох~ ...хы-~), если 7(1,хм...,хы ~) = -1. Полученный ориентированный граф является связным, так как мы можем добраться из любой вершины к (Е1010... 1) и из этой точки — к любой требуемой вершине.
Согласно теореме 2.3,4.2О существует циклический путь, проходящий через каждое ребро длиной 2 +, и ы4л можно предположить, что он начинается в вершине (Е00...0). Построим циклическую погледовательность с Х~ = = Хзь ~ = 0 и Х„ьы ~ — — хы, если и-е ребро — это путь из (Ехь .. хы ~) к (Охз... хы) или из (Ох~...хы ~) к (Ехз... хы). Например, граф для й = 2 показан на рис. А — 5; ребра циклического пути пронумерованы от 1 до 32 и циклическая последовательность имеет вид (00001000110010101001101110111110) (00001 ... ) .
Заметим, что в этой последователыпкти Рг(Хзь = О) = е. Очевидно, что последовательность (2Й)-распределена, так как каждая строка размерности (2к) х~хю .. хы появляется 1+ 1(хп...,хю) +1 — 1(хп...,хы) = 2 рвз за цикл. Тот факт, что Рг(Хз„= О) имеет требуемое значение, вытекает из факта, что при этом построении достигается максимальное значение правой части равенства в доказательстве предыдущего упражнения. Рис. А-5.
Ориентированный граф из упр. 30, 31. Используйте алгоритм % с правилом Е1 выбора полной последовательности. (Для обобщения етого типа неслучайного поведения в К5-последовательностях обратитесь к работе Леал Ъ'111е, Есауле Спг!Оце де 1а Мог!оп с!е Со!!есс!г" (Рапз, 1939), 55-62. Возможно, определение Кб также слишком слабое с втой точки зрения, однако такой контрпример неизвестен.] 32. Если Е, гс' — исчисляемые правила нодпоследовательностей. то существует Еь = йЯ!, определенное такими функциями; !„"(хе,...,хь ~) = 1 тогда и только тогда, когда гс определяет подпоследовательность х„, ..., х,„ из последовательности хе, ..., х„ и где Ь > О, О < г1 « гь < и и (ь(х„,,..., х„) = 1.
Тогда (Х ) КИ' равна ((Х„) !с) !с . Результат следует незамедлительно. 33. Зададим е > О и найдем такое Хо, при котором неравенство !г' > Ае влечет оба неравенства )и,(!у)/!ц — р! < е и !гч(Х)/Х вЂ” р! < е. Затем найдем такое Хм при котором из 1г' > № следует, что !я равно гм или вм для какого-либо М > 1уе. Из Ю > Х1 следует, что щ(К) ! и„(№) + щ(№) ! ! ь„(№) — р№ + и (Х ) — рХ ! ! ° ' ° ° ! ! ' — ' ° ° — ° ! 34. Например, если двоичным представлением ! является (1 О~ ~ 1 О ' 1 1 О'е 1 ...
1 О"'" ) ю где "О"" — обозначение последовательности из а нулей. Пусть правило Е~ принимает Ь'в тогда и только тогда, когда (ЬСь-ь) = ап ..., (ЬК~-11 = аь 35. Пусть ао = ео и а ~.1 — — щак(аь ! О < Ь < 2~ ). Построим правило подпоследовательностей, выбиракпцее злемент Х„тогда и только тогда, когда и = аь для некоторого Ь < 2"'", когда и принадлежит интервалу а < и < а ьь Тогда 1!щ,ь,ь, и(а,ь)/о 36. Пусть Ь и Ь вЂ” произвольные, однако фиксированные целые числа, больщие, чем 1. Пусть Ль = (ЬГ„). Для произвольной бесконечной подпоследовательности (2„) = (1;„) 12, определенной алгоритмами Б и Ю (как в доказательстве теоремы 51), существует простое, но трудно записываемое соответствие алгоритмам Б' и Я.', которые просматривают Хм Хг+и, Хгег и/или выбирают Ль Хгьп ..., Х,е ~щь цй из (Х„) тогда и только тогда, когда В и гс просматривают и/или выбирают У„где К = (О.ХгЛгег...
Хгег)г. Алгоритмы В' и гс' определяют бесконечную 1-распределенную подпоследовательность (Х ), и фактически (как в упр. 32) зта подпоследовательность является оо-распределенной, поскольку она (Й,1)-распределена, Таким образом, мы определили, что Рг(Я„= а) и Рг(3„= а) отличаются от 1/Ь менее чем на 1/2". ]Результат этого упражнения справедлив, если оКО" заменить последовательно на оК4о или "В.5", но он не верен, если использовать гВ1," так как Хг г может быть (г) тождественно равен нулю.] 37.
Для и > 2 замените Ьг„г на -'(Ьггг+ 5„), где 5 = 0 или 1 в зависимости от того, четное или нечетное число элементов, меньших —,', содержит множество (Ьг1„г!г+м,Ьг„г г). ]Адгапсш ш Масй. 14 (1974), ЗЗЗ -334; см. также Р1г. П. с!гез!э Томаса Н. Герцога (Т1юшаз Н. Неггой, !!шг.
о! Магу!апд, 1975).] 39. См. Асса АНгбшейса 21 (1972), 45 — 50. Наилучшее возможное значение с неизвестно. 40. Так как Рь зависимы только на Вг... Вы получим Р(Аг,, Зя) = -'. Пусть 9(Вг... Вь) = Рг(Вгег = 1 ] Вг ... Вь), где вероятность берется по всем элементам Я, имеющим Вг... Вг в качестве первых Ь двоичных разрядов. Аналогично пусть Оо(Вг... Вг) = Рг(Рь = 1 и В(ь, —— Ь ] Вг... Вь).
Тогда получим Рг(Аг =! ] Вг .. Вг)= Рг((Р„+Вгег+Вгь~г) шоб 2=1 ] Вг . Вг) = Я . (г — Яо + Ог) + (1 — д) . (Оо + -', — Ог) = —,' — (Оо + Ог) + 2(ЧОг + (1 — Ч)йо) = г — Рг(Рь = 1 ] Вг,. Вг) + 2Рг(Рг = 1 и Вгег = Вьег ] Вг... Вг). Следовательно, Рг(Аг — — 1) = 2,в в Рг(Вг, Вь) Рг(Ага = 1 ] Вг... Вг) = -' — Рг(Рь = 1) + Рг(Ра ы = 1). [См. теорему 4 в работе Со!Огегс!ц Со!Оггаэзег, апг! Мгса!Ь 34СМ 33 (1986), 792 — 807.] 41. Выберите )г равномерно из (О,..., Аг — 1) и воспользуйтесь построением из доказательства лемлгы Р1. Тогда нз доказательства Р1 будет следовать, что А' равно 1 с вероятностью Ее=о (г рь + рь+г)/г' 42. (а) Пусть Х = Хг + + Л„.
Очевндно, что Е(Х) = пр, и мы имеем Е((Х вЂ” пр) ) = ЕЛ вЂ” п~д~ = пЕЛг + 22 (ЕХ,)(ЕХ,) — пгрг = пЕХг — и!гр = паг. Также Е((Х вЂ” пд) ) = 2 >о хРг((Х вЂ” пр)г = я) > 2 эг г х Рг((Х вЂ” пд) = х) > ~,>ы г !па х Рг((Х вЂ” пд)г = х) = !наг Рг((Х вЂ” пд)г > !лаг). (Ь) Существует ицдекс г, такой, что сг ф с'„скажем, с, = О и с', = 1. Тогда существует такой индекс /, что с = 1. Для любого фиксированного набора из й — 2 строк в матрице В, номер которых не равен г или /, получим (сВ,с'В) = (г!, г!') тогда и только тогда, когда строки г и / имеют частные значения (зто происходит с вероятностью 1/2 ). гя (с) В обозначениях алгоритма Ь возьмем и = 2 — 1 и Л, = ( — 1)а!'Яэю1, тогда !г = э и а ы 1 — э .
Вероятность,что Х = 2 Х, отрицательна,не больше вероятности того, г г что (Х вЂ” пр) > пгрг. Согласно (а) зто не больше, чем аг/(прг). 43. Заключение для фиксированного М не представляет интереса, так как, очевидно, сушествует алгоритм для нахождения множителей любого фиксированного М (т. е. алгорити для нахождения множителей). Теория применима ко всем алгоритмам, имеющим короткое время счета, а не только к алгоритмам, которые эффективно находят множители.' 44. Если каждое изменение одного числа в случайной таблице приводит к случайной таблице, то все таблицы случайны (или нн одна не существует). Если мы не допускаем степеней случайности, то ответ должен, следовательно, быть "Не всегда".
РАЗДЕЛ 3.6 1, ВАМОХ 371 ВТА ХОА 1ОЛ. 1МСХ 107 5ЬАХ ВТА ИОЬ ТМСА 9Н ХИР ХНАИО СОИ ВН СОИ 7Н СОМ 9Р ВР ХНАМО 75 1009 в+1 5 ХНАИО ВР 1 1 0 3141592621 Запоминание выходной ячейки. Запоминание значения А. гА+- Х. гАХ +- аЛ. гХ з — (аХ + с) глой т. Гарантия, что переполнение выключено. гА+- (аХ+ с) спой гн.
Запоминание Л. гА з- '1)сХ/т). Добавить 1, чтобы 1 < У < А Возврат. Значение Х, .Хе = 1. Быстрое запоминание )з. Множитель а. $ 2. Помещение генератора случайных чисел в программу дает, по существу, непредсказуемый для програиииста результат. Если бы поведение машины в каждой задаче было известно зарюсее, немногие программы были бы когда-нибудь написюсы Как говорил Тьюринг (Твпп5), действии компьютера очень часто преподносят сззрприз программисту, в особенности при отладке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
