-Ня о о 1

Е 1 1

О О 1 О

Е 1 о о

Но о о 1

о 1 1 оК

Е 1 1 1

24 29

Е О 1 1

Рис. А-5. Ориентированный граф из упр. 30.

31. Используйте алгоритм W с правилом TZ\ выбора полной последовательности. [Для обобщения этого типа неслучайного поведения в Е5-последовательностях обратитесь к работе Jean Ville, Etude Critique de ia Notion de Collectif (Paris, 1939), 55-62. Возможно, определение R6 также слишком слабое с этой точки зрения, однако такой контрпример неизвестен.]

32. Если TZ, TZ - исчисляемые правила подпоследовательностей, то существует TZ" = TZTZ, определенное такими функциями: /(жо,..., z„-i) = 1 тогда и только тогда, когда TZ определяет подпоследовательность Xri, Хг из последовательности жо, x„-i, где

fe>0, 0<г1<---<Г*,<ПИ /j(,(Zri,...,XrJ = 1.

Тогда {Хп)ТП1 равна {{Хп)Т1)Л. Результат следует незамедлительно.

33. Зададим б > О и найдем такое No, при котором неравенство N > No влечет оба неравенства \ir{N)/N - pj < б и \i/i(N)/N - р < б. Затем найдем такое Ni, при котором из N > Ni следует, что tN равно гм или sm для какого-либо М > No- Пз N > Ni следует, что

UriNr)+Us{Ns)

N Nr+Ns

Vr(Nr) -pNr + is(Ns) -pNs

< б.

34. Например, если двоичным представлением t является (1 0*" 1 О" 11 0" 1 ... 1 О" )2, где "0°" - обозначение последовательности из а нулей. Пусть правило TZt принимает Un тогда и только тогда, когда [bUn-k\ = «1, • , Ln-iJ = "fc-

35. Пусть ао = So и am+i = max{sjt j О < fe < 2°"}. Построим правило подпоследовательностей, выбирающее элемент Х„ тогда и только тогда, когда п = sjt для некоторого к < 2""", когда п принадлежит интервалу am < п < am+i- Тогда Ишт-юо i{am)/am = \-

36. Пусть Ъ и к - произвольные, однако фиксированные целые числа, больщие, чем 1. Пусть Уп = \bUn\- Для произвольной бесконечной подпоследовательности {Zn) = {Ys„)R., определенной алгоритмами 5 и 72. (как в доказательстве теоремы М), существует простое, но трудно записываемое соответствие алгоритмам 5 и VJ, которые просматривают Xt,

Xt+i, Xt+s и/или выбирают Xt, Xt+i, Xt+min(k-i.s) из (Xn) тогда и только тогда, когда 5 и 72. просматривают и/или выбирают У, где t/j = {O.XtAt+i... ,Yf+s)2. Алгоритмы S и TJ определяют бесконечную 1-распределенную подпоследовательность (Хп), и фактически (как в упр. 32) эта подпоследовательность является оо-распределенной, поскольку она (к, 1)-распределена. Таким образом, мы определили, что Pr(Z„ = а) и Pr(Zn = а) отличаются от 1 /Ь менее чем на 1 /2*.

[Результат этого упражнения справедлив, если "R6" заменить последовательно на "R4" или "R5", но он не верен, если использовать "R1," так как может быть

тождественно равен нулю.]

37. Для п>2 замените t/„2 на (Un2 +<5„), где 6п = О или 1 в зависимости от того, четное или нечетное число элементов, меньших , содержит множество {t/(n-i)2+i, • , f/n-i}-[Acfvances in Math. 14 (1974), 333-334; см. также Ph. D. thesis Томаса H. Герцога (Thomas N. Herzog, Univ. of Maryland, 1975).]

39. Cm. Acta Arithmetica 21 (1972), 45-50. Наилучшее возможное значение с неизвестно.

40. Так как Fk зависимы только на Bi... В*,, получим P(Af, $n) = 5. Пусть q(Bi... Bk) = Рт(Вк+1 = 1 I Bi ... Bfc), где вероятность берется по всем элементам S, имеющим Bi... В* в качестве первых к двоичных разрядов. Аналогично пусть qb(Bi... B)t) = Pr(Fjt = 1 и Bk+i = b\Bi... Bk). Тогда получим Рг(А;Г=1 Bi... В0=Рг((Р+В+1+В;+,) mod 2=1 Bi...Bjt) = 5 - (i - 50 +gi) + (1 - 5) (50 -(-1 -gi) = I - (go + gi) + 2(551 +(l -9)50) = i - Pr(Fjt = 1 I Bi...Bjt) -(-2Pr(Ffc = 1 и Bk+i = Bjt+i I Bi...Bk). Следовательно, Рг(АГ = 1) = Ев,..в, Pr(Si ---Bk) Pr(Af = 1 I Bi... Bfc) = i - Pr(F, = 1) + Pr(F,+i = 1). [Cm. теорему 4 в работе Goldreich, Goldwasser, and Micali, JACM 33 (1986), 792-807.]

41. Выберите к равномерно из {О,..., N- 1} и воспользуйтесь построением из доказательства леммы Р1. Тогда из доказательства Р1 будет следовать, что А равно 1 с вероятностью Eko(l-Pk+Pk+i)/N.

42. (а) Пусть А = Ai Н-----1- А„. Очевидно, что Е(А) = пр, и мы имеем Е((А - пр)) =

ЕХ - пр = nEXj + 2Ei<i<j<„(EAi)(EA;) - пр = nEXf - пр = па. Также Е((А - пр)) = Е.>о = Рг(( - пр) =х)> E.>tn.2 X Рг((А -пр) = х)> E.>tn. tna х Рг((А - пр) = х) = tna Рт((Х - пр) > tna).

(b) Существует индекс г, такой, что Ci ф с,, скажем, с; = О и с(- = 1. Тогда существует такой индекс j, что Cj =1. Для любого фиксированного набора из А; - 2 строк в матрице В, номер которых не равен i или j, получим (сВ,сВ) = (d,d) тогда и только тогда, когда строки i и j имеют частные значения (это происходит с вероятностью 1/2").

(c) в обозначениях алгоритма L возьмем п = 2* - 1 и Ас = (-1)<(=+), тогда р = s и а = 1 - s. Вероятность, что X = Ес#о отрицательна, не больше вероятности того, что (X - пр) > пр. Согласно (а) это не больше, чем а/(пр).

43. Заключение для фиксированного М не представляет интереса, так как, очевидно, существует алгоритм для нахождения множителей любого фиксированного М (т. е. алгоритм для нахождения множителей). Теория применима ко всем алгоритмам, имеющим короткое время счета, а не только к алгоритмам, которые эффективно находят множители.

44. Если каждое изменение одного числа в случайной таблице приводит к случайной таблице, то все таблицы случайны (или ни одна не существует). Если мы не допускаем степеней случайности, то ответ должен, следовательно, быть "Не всегда".

2. Помещение генератора случайных чисел в программу дает, по существу, непредсказуемый для программиста результат. Если бы поведение машины в каждой задаче было известно заранее, немногие программы были бы когда-нибудь написаны. Как говорил Тьюринг (Turing), действия компьютера очень часто преподносят сюрприз программисту, в особенности при отладке.

Так что мир должен быть более бдительным.

7. Фактически вам необходимо только 2 двуразрядных значения [A„/2®J mod 4; см. D. Е. Knuth, IEEE Trans. IT-31 (1985), 49-52. J. Reeds, Cryptoiogia 1 (1977), 20-26, 3 (1979), 83-95. Д. Рид первым начал изучать родственные задачи. (См. также L. Blum, М. Blum, and М. Shub, SICOMP 15 (1986), 364-383; J. Boyar, J. Cryptoiogj 1 (1989), 177-184.) В своей работе Фрииз, Хастед, Кеннан, Лагарис и Шамир (Frieze, Hastad, Kannan, Lagarias, and Shamir, SICOMP IT (1988), 262-280) обсуждают общие технические приемы, используемые в аналогичных задачах.

8. Можно, допустим, генерировать Аюооооо, произведя миллион последовательных вызовов программы, и сравнивать с точным значением (a°°°°°°Ao + (а°°°°°° - 1)с/ (а - 1)) mod m, которое также можно выразить в виде ((a°°°°°°(Ao(a - 1) + с) - с) mod (а - 1)т)/(а - 1). Последний можно быстро оценить независимым методом (см. алгоритм 4.6.3А), например 48271°°°°°° mod 2147483647 = 1263606197. Большая часть ошибок обнаруживается, так как рекуррентное соотношение (1) не является самокорректирующимся.

9. Значения Ао, Ai, ..., А99 не все четные. z°° + z + 1 - первообразный полином (см. раздел 3.2.2); следовательно, существует число h{s) такое, что Ро(г) = г** (по модулю2 иг°°+г" + 1). Тогда гР„+1(г) = Р„(г)-А„г"-А„4.бз+А„4.бзг°°+А„+1оог" = P„{z) + Хп+вз{г°° + z + 1) (по модулю 2), так что результат получается по индукции.

(b) Операции "возведение в квадрат" и "умножение на г" в ran.start меняют р(г) = жддг + •+ x\z + Хо на р{гУ и zp{z) соответственно по модулю 2 и z°° + z + 1, так как p{zY = p{z)- (Мы рассмотрели здесь только младшие двоичные разряды. Другие двоичные разряды преобразуются специальным методом, который стремится сохранить и/или увеличить тот беспорядок, в котором они находятся.) Следовательно, если s = (Isj .., siso)2, то получим h{s) = (Isosi ... Sj 1)2 2®*.

(c) г*)"" = (по модулю 2 и z°° + + 1) подразумевает, что h{s) - п = h(s)-n (по модулю 2i°° - 1). Так как 2** < h[s) < 2°° - 2", имеем п - п\ > \h{s)-h{s)\>2°.