AOP_Tom2 (1021737), страница 55
Текст из файла (страница 55)
В течение нескольких лет данный вопрос оставался открытым, поскольку К4 так нли иначе включает в себя Кб. В конце концов, Томас Герцог (ТЬошаэ Неггоб) и Джеймс К. Оуннгс (мл.) (3а>пеэ С. Ож>пйэ, 3г.) сумели построить большое семейство последовательностей, удовлетворяющих К4. но не удовлетворяющих К6. [См. 2е>гэсЬг. Гйг п>агЬ. Х,ок!Ь шк! Сгипг!!айеп г!ег МаГЬ. 22 (1976), 385-389.] Другую важную статью написал Колмогоров [Проблемы передачи >гнформацп>г 1 (1965), 3-11].
В ней он рассмотрел проблему определения "информационного содержимого" последовательности, и эта работа привела к интересному определению Чайтина (СЬай1п) и Мартин-Лефа (Магг!и-Ьо() конечных случайных последовательностей через "хаотичность". [См. 1ЕЕЕ Тгапэ. 1Т-14 (1968), 662-664.] Их идея может быть также прослежена в работах Р. Дж. Соломонова (К. 3. Бо!ошопа!1, 1пуогшаГ!оп апс( Сов!го! 7 (1964), 1-22, 224-254;!ЕЕЕ Тгапэ. 1Т-24 (1978), 422-432; Х Соп>р. Буэгеш бс!.
55 (1997), 73 — 88). Обсуждение случайных последовательностей с философской точки зрения можно найти у К. Р. Поппера (К. К. Роррег, Тйе Бой!с оу бс!ешьбс О!эсогегу (1опбоп> 1959)); особенно интересно построение на с. 162-163, впервые опубликованное в 1934 году. Дальнейшие связи между случайными последовательностями и теорией рекурсивных функций исследовались в работе Б. Ъ'. Ьоче)апг1, Тгапэ.
Ашег. МаГЬ. Бос. 125 (1966), 497 — 510. См. также работу К,-П. Шнорр (С.-Р. 8сЬпогг, 2е!гэсЬг. ИаЬг. гег>г, Себ. 14 (1969), 27 — 35), нашедшего сильные связи между случайными последовательностями и "категориями меры", которые были определены Л. Э. Я. Броуэром (1. Е.
3. Вгоп>гег) в 1919 году. В следующей книге Шнорра, 2оГЙ!!8)ге!Г ппс! ЮнЬгэсЬе!и!>сЬЬезг [йесГиге >х7огеэ ш МагЬ. 218 (Вег)>п: 8рг!пйег, 1971)], дан подробный обзор всей темы случайности и превосходное вступление к новым публикациям по этой теме. Обзор важнейших усовершенствований в течение следующих двух десятилетий можно найти в книге Ап 1пгго>!исГ!оп го Ко!шояогог Сошр!ех!Гу ап>! 1гэ Арр!!саг!опэ (БрПпйег, 1993), М>п8 1д апб Рап1 М.
В. Ъ'>гапуй Основы теории псевдослучайных последовательностей и эффективной информации заложены Мануэлем Блюмом (Малое! В!шп), Сильвио Микали (Бйг>о М>са1>) и Эндре Яо (Алагем >ао) в работах [ГОС5 23 (1982)> 80-91, 112-117; 81СОМР 13 (1984), 850 — 864], в которых построены первые явные последовательности, удовлетворяющие всем возможным статистическим критериям. Блюм и Микали ввели понятие жесткого ядра двоичного разряда, булевой функции 7', такой, что 1(х) и д(х) легко вычисляются, хотя функция 1(д! >)(х)) не вычисляе>ся. В их статье берет начало лемма Р4.
Леонид Левин развил теорию в работе Сошб!лагос!са 7 (1987), 357.-363. Затем он и Одед Голдрейч (0>)е>1 Оо!6ге>сЬ) [БТОС 21 (1989), 25 — 32] проанализировали такие алгоритмы, как смешанно-квадратичный метод, и показали, что, используя маску подобным образом, можно получить жесткое ядро во многих случаях. Наконец, Левин в работе 3. 8угпЬойс 7 о8(с 58 (1993), 1102-1103, усовершенствовал методы предыдущей работы, введя алгоритм Е и цроанвлизировал его.
Свой вклад в теорию внесли многие авторы — особенно Импаглиаззо (1шра811- аязо), Левин, Лаби (ЬоЬу) и Хастад (Назсао) [БТОС 21 (1989), 12-24; 22 (1990), 395- 404), которые показали, что псевдослучайные последовательности можно построить из любой однозначной функции.
Однако такие результаты здесь не рассматриваются, так как они применяютсн, главным образом, в сложной абстрактной теории, а не в практическом генерирования случайных чисел. Практическое применение теоретических работ к псевдослучайности впервые эмпирически исследовано в работе Р. Ь'Еспуег апс1 К. Ргоо1х, Ргот Ят1ег 83ти)айоп Сопб 22 (1989), 467-476. Если числа не случайны, то онн ло кпайней меле е лолном беспорядке. — ДЖОРДЖ МАРСАЛЬЯ (ЕЕОЙЙЕ МАПБАЕША) (1964) УПРАЖНЕНИЯ 1. [10) Может лн периодическая последовательность быть равяораспределенной? 2. [10[ Рассмотрите периодическую двоичную последовательность 0,0, 1, 1,0,0, 1,1,.... Она 1-, 2- нлн 3-раслределенная? 3. [М22) Постройте троичную периодическую 3-распределенную последовательность. 4.
[НМ14) Докажите, что Рг(8(п) нТ(п)) + Рг(8(п) илнТ(п)) = Рг(Н(п)) + Рг(Т(п)) для любых двух утверждений 8(п) н Т(в), предполагая, что по крайней мере три из ятях пределов существуют. Например, если последовательность 2-распределена, то можно найти, что Рг(и~ < П < щ нлн иа < (7 ьг < ег) = щ — и~ + иг — ии — (щ — в~Пса — яг) б. (НМ22[ Пусть 11„= (20М"~'Ц/3) юоб1. Чему равна Рг((? < —,')? 6.
[НМ20[ Пусть 8~(в), й(в), ... — — бесконечная последовательность утверждений о совместных непересеяающнхся событиях, т. е. 8,(п) н 81(п) не могут выполняться одновременно, если 1?Е 1. Предположим, что Рг(5 (и)) существует для каждого 1 > 1. Покажите, что Ргф~(и) выполняется для некоторого 1 > 1) > 2 .>, Рг(8~(в)), н приведите пример, показывающий, что равенство может не выполняться. 7. [НМ27) Пусть (Нч(п)) — семейство утверждений, таких, что Рг(8ч(п)) существует для всех 01 > 1.
Предположим, что для всех и > О 80(н) выполняется для точно одной пары целых чисел 01. Если 2, >, Рг(НО(я)) = 1, то следует ли из зтого, ч>1 что "Рг(5,1(п) выполняется для некоторого 1' > 1)" существует для всех 1 > 1 и равна Е,>, РгФО(п))? 8. [М15) Докажите (13). О.
[НМ20[ Докажите лемму Е. [Указание. Рассмотрите х .,(Ат — о) .] ь 10. [НМ22) Где е доказательстве теоремы С используется тот факт, что т делит д? 11. [М10) Применяя теорему С, докажите, что если последовательность (П,) оо-распределена, то она является подпоследовательностью ((?а ). 12. [НМ20) Покажите, что к-распределенная последовательность удовлетворяет критерию "максимум-й" в следующем смысле: Рг(и < щах(б,(?„чч,...,(? ьь ~) < г) = г~ — и". ь 13. [НМ27[ Покажите, что оо-распределенная [О .. »-последовательность проходит критерий интервалов в следующем смысле: если 0 < а < (3 < 1 и р =, — о, пусть /(О) = 0 и для и > 1 пУсть /(и) — наименьшее целое число т > /(и — », такое, что и < Ьс,о < ~3, тогда 14.
[НМ22[ Покажите,что оо-распределенная последовательность проходит критерий мо- нотонности в следующем смысле: если /(0) = 0 и если для и > 1 /(и) — — наименьшее целое число т > /(и — », такое,что К„ ( > П„, тогда Рг(/(и) — /(и — » = )с) = 2)с/(/с + »! — 2(/с + »/()с + 2)' и 1 = (пп)п(п(( ). о-ооо 2 = 1ппвпрп((~) -ос а) Чем являются Х. и Г для последовательности Ван дер Корпута (уап бег Сотряс) (29)? Ь) Покажите, что 1 ь > 1 для 1 < lс < п. Используйте этот результат для доказа()) (в) тельства того, что Т > 1/1и 2. с) Докажите, что 7 < 1/1п4. [Уха)анне.
Для каждого и существуют такие числа ац ..., аат что 1с„> („у„ддя 1 < )с < 2п. Кроме того, каждое целое число 2,, и (Й) (о(-о*) появляется самое большее дважды в (ац..., ас„).[ с() Покажите, что последовательность (Ис„), определенная равенством И'о = 1б(2п-)- » шо((1, удовлетворяет 1/)п2 > п1о(') > п1(") > 1/)п4 для всех и. Следовательно, она достигает оптимальных значений 7 и б.
ь 15. [НМЭО[ Покажите, что оо-распределенная последовательность проходит критерий собирания купонов, в котором существует только два вида купонов, в следующем смысле: пусть Хц Хс,... — оо-распределенкая двоичная последовательность. Пусть /(0) = 0 и для и > 1 пусть /(и) — наименьшее целое число т > /(и — », такое, что (Х?(„()э(,,,., Хо,) является множеством (0,1). Докажите, что Рг(/(и) — /(и — » =?с) = 2' " для )с > 2 (см. упр. 7), 16.
[НМЭ8[ Выполняется ли критерий собирания купонов для сю-распределенных последовательностей, когда существует больше двух видов купонов? (См. предыдущее упражнение.) 17. [Нар[ Для любого заданного рационального числа г Франклин (РгапЫ)п) доказал, что последовательность (г" шос( 1) не является 2-распределенной. Но существует ли рациональное число г, для которого эта последовательность равнораспределенао В частности, равнораспределена ли последовательность при г = з? [См. К. МаЬ(ег, Масйешасрйа 4 (1957), 122-124.[ ь 16. [НМ22] Докажите, что если 7?е, 17п ... )с-распределена, то такой же будет последовательность Уа> Уц ..., где У = [и(/„)/и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
