AOP_Tom2 (1021737), страница 26
Текст из файла (страница 26)
Г. Лаияяепя апй1 Б. (У1ейег, МайЛ. Сайпр. 29 (1975), 827-.833). Несколько других авторов указывают, что спектральный критерий можно было бы объяснять в намного более конкретных терминах, и предлагают изучить решетки и решетчатые структуры соответствующих линейных конгруэнтных последовательностей, что сделает фундаментальные ограничения случайности графически натлядными. (Сль работы Марсалья, Вуда, Ковэю, Беера, Руфа и Вильямсон, Марсалья и Беера: О. Магяа811а, Ргос.
Хай. Асад. Бой 61 (1968), 25-.28; %. %. Ъоаб, .1. СЛеш. РЛуя. 48 (1968), 427, В.. К. Согеуои, Бйий(лея йп АррбеН Майй. 3 (РЬл1аййе!р1па: 81АМ, 1969), 70-111; %'. А. Веуег, К. В. Воо(, апс1 О. %1111ашяоп, МайЛ. Сошр. 25 (1971), 345 — 360; С. Магзаб)(а ап6 ')У. А. Веуег, Арр!)саНопа об ХпгпЬег ТЬеогу ло Ь)пгпег)са! Апл!) шх) ебйе)] Ьу Б. К. ХагещЬа ()зе)и Ъот)с Аса)1ещ1с Ргезз, 1972), 249-285, 361-370.] Р. Дж. Стоунхам (Н. гг. Б)опейа)п), используя оценки экспоненциальных сумлц показал, что р'/г+' или более элементов последовательности а" Ла )поб р имеют асимптотически малый разброс, когда а — примитивный корень по модулю простого числа р ]Ас!а АлбйшеНса 22 (1973), 371 — 389].
У Гаральда Нидеррейтера это объяснение растянулось на несколько статей (см, работы Нага16 %ег]егге(лег, Малй. Сопзр. 28 (1974), 1117. 1132; 30 (1976), 571 — 597; Аг(еапсеа 1п МалЬ, 26 (1977), 99 181; Ви!1. А)пег. Мал)з. Бос. 84 (1978), 957 — 1041. См, также его книгу Н. К(ес1егге!лег, Пап))огп )У)гтЬег Сепега!)оп ап)! 1!паз!-Ъ|опсе Саг!о Мелйобэ (РЬ)!ас)е!рЬ1а) 81АМ, 1992)).
УПРАЖНЕНИЯ 1. ]М!0] Что произойдет со спектральным критерием, если размерность уменьшить до единицы? (Другими словами, что произойдет при ! = 1?) 2. (ЯМ20] Пусть 1зп ..., Н вЂ” линейно независимые векторы в Ьл)ерном пространстве, пусть |а — решетка из точек, определенных в (10), и пусть П) ) ..., 05 определены и (19).
Докажите, что максимальное расстояние между (! — 1)-мериыми гиперплоскостями семейства параллельных гиперплоскастей, покрывающих Ьа; равно 1/щ)п(/(х),..., х)) пг (х),..., х)) ~ (О,..., О)), где / определена в (17). 3. ]М24] Определите иг и щ для всех линейных конгруэнтных генераторов с потенциалач 2 и периодом длиной )и. 4. (МЯЛ] Пусть и)„и)г, иг), игг — элементы матрипы размера 2 х 2, состоящей из целых чисел и такой, чта и ) + аип ш иг) + аигг = — 0 (по модулю ш) и ими)э — имип = т.
а) Докажите, что все целые решения (у), уг) уравнения у, +аул = 0 (по модулю )и) имею г вид (у), уг) = (х) ип+хгиг), хгип ч хгию) для целых х), хг. Ь) Если вдобавок 2]ипил) + и)гигг] < ип + ип < иг, + игг докажите, что (у),уг) = г г г, г (и)), ип) минимизирует у, + уг по всем соответствующим ненулевым решениям этого г, г уравнения 5. ]Мбй] Докажите, что двумерный спектральный критерий на шагах 51-Б3 алгоритма Б выполняется правильно. ]Указание. См. упр.
4: доказательство того, что (Ь + Ь) + г (р' + р)' > Ь" + р, начните с шага Б2.] Та, что указанное неравенство, несомненно, впервые выполняется на шаге 52, являетгя неожиданным. Целое числа )/, минимизирующее (Ь' — у'Ь) + (р' — д'р), согласно (24) равно )/ =- округление((Ь)Ь + рр)/(Ьг + рг)). Если (Ь' — д)Ь)г -л (р' — у'р)г < Ьг + рг, получим )/ ~ О, д' ~ — 1. Следовательно, (р' — у'р)г > рг; отсюда (Ь' — )/Ь) < Ьг, т е. ]Ь' — 4'Ь] < Ь либо )/ равно )? или д + 1. Получим !ги + ри > Ь(Ь' — ОЬ) + р(р' — у р) > — -'(Ьг + р ). Если и, и < г, та на следующей итерапии шага 52 будет сохранено предположение указания. г г Если и +и > к > (и — Ь) +(а — р)', получим 2',Ь(и — Ь)+р(и — р)] = 2(Ь(Ь вЂ” и)+р(р-а)) = (и — Ь)г + (и — р)г + Ьг + рг — (иг + г) < (и — Ь)г + (и — р)) < Ьг + рг Слспавательио, согласно упр.
4 (и — Ь) + (а — р) является минимальным. Наконец, если и и + и, и г, г г (и — Ь) -) (а — р) будут > г, положим и' = Ь' — )/Ь, а' = р' — д'р, тогда согласно упр. 4 2]Ьи'+рлг] < Ь'+р < и' + и' и Ьг -)-р л)инимазьны (Общие правила нахождения кратчайших 2-1Э-векторов относительно других метрик обсужда)от Кэйб и Шнорр в работе Ка)Ь ап)1 Бсйпогг, д.
А18оьч)Ьшз 21 (1996), 565 — 578.] О. (МОО] Пусть аа, а), ..., а) ) -- частичные отношения а/ш, определенные в разделе 3 3 3, и пусть А = шаха«) а,. Докажите, что рг > 2г/(4+ 1+ 1/Л). 7. ]ДМ28] Докажите, что вопросы (а) и (Ь), поставленные после (23), имеют такое же решение для деиствительных чисел а),, аг-), д!+),, )1) (см (24) и (26)) В. [М10] В строке 10 табл. 1 значение?гг очень малб, однако дг совершенно удовлетворительно. Чему равно наиболыпее возможное значение дг, когда дг = 10 е и т = 10'е? 9. [НМЗ2] (Ч. Эрмит (С. Негшйе), 1846,) Пусть /(хы...,хг) — положительно определенная квадратичная форма, определенная матрицей (?, как в (17), и пусть  — минимальное значение / в не равной нулю целой точке.
Докажите, что В < (1)0 М?г]деэ (?]~~'. [Указание. Если И' — любая целочисленная матрица с определителем, равным 1, матрица (4г(/ определена формой, эквивалентной /. Если же 5 — любая ортогональная матрица (т. е. если Я ' = Я~), матрица (/Н определена формой, равной /. Покажите, что существует эквивалентная форма В, минимум которой В достигается в (1,0,...,0). Затем докажите общий результат индукцией по й записывая у(хы,хг) = В(хг + Згхг + + Згхг) + й(хг,..., хг), где?г — положительно определенная квадратичная форма 1 — 1 переменной.) 10. [М20] Пусть уг и уг — взаимно простые чигла, такие, что уг + арг ьл 0 (по модулю гл) и уг + уг < 1Г4/3т, Покажите, что существуют целые числа и, и иг, такие, что г г иг +аиг гн 0 (по модулю т), игрг — игуг = т, 2]и|рг + игре] < ш1п(иг+ из,р]+ рг) и (иг + игг)(рг + угг) > тг, (Следовательно, согласно упр.
4 игг = ш!п(и]+иг3, рг~+уг~).) ь 11. [НМЗВ] (Алан Г. Вотерман (А(ап С. 1рагегпгап), 1974.) Придумайте эффективную процедуру вычисления множителя а гв 1 (по модулю 4), для которой существует относительно пРостое Решение УРавнениЯ У, + аУг = 0 (по мод?лю гп) с У,' + Уг ж з/4/3 т — г, где е > О настолько малб, насколько это возможно при заданном т = 2'. (Согласно упр. 10 такой выбор а гарантирует, что игг > тг/(у,' + ргг) > з/3/4гп, и существует возможность, что ог будет близко к своему оптимальному значению з/4/3 т.
На практике будем подсчитывать несколько таких множителей для малых е, выбирая затем один из них с наилучшими спектральными значениями иг, из, ) 12. [НМВЗ) Не прибегая к использованию графических методов, докажите, что любое решение вопроса (Ь), поставленного после (23), должно удовлетворять уравнениям (26). 13. [НМ22] В лемме А используется факт, что?/ не вырождена, для доказательства того, что положительно определенная квадратичная форма принимает некоторое не равное нулю минимальное значение в точке с целыми не равными нулю координатами. Покажите, что зто предположение необходимо, рассмотрев квагцгатичную форму (19), матрица коэффициентов которой не вырождена и для которой значения /(хи.,.,х,) расположены произвольно в окрестности нуля (по никогда его не достигают) в не равной нулю точке с целыми координатами (хм..., х,).
14. [24] Вручную выполните алгоритм Б для т = 100, а ж 41, Т = 3. ° 15. [М20] Пусть 1? — вектор с целыми координатами, удовлетворяющий (15). Сколь- ко (1 — 1)-мерных гиперплоскостей, определенных 1?, пересекают единичный гиперкуб ((хм...,хг) ] 0 < х„< 1 для 1 < ? < 1)? (Это примерно равно числу гиперплоскостей в семействе, которого досзаточно, чтобы покрыть 1е.) 16. [МЗВ] (У. Дитер (С. Ебегег).) Покажите, как можно преобразовать алгоритм Б, чтобы вычислить минимальное число Хг параллельных гиперплоскостей, пересекающих единич- ный гиперкуб, как в упр. 15 для всех?7, которые удовлетворяют (15).
[Указание. Каким приблизительно будет аналог положительно определенной квадратичной формы и лем- мы А?] 17. [20] Преобразуйте алгоритм Я таким образом, чтобы он не талька вычислял величины мь но и давал на выходе все векторы с целыми координатами (иь..., иг), удовлетворяю- щие (15), и такие, что иг + + и,' = иг при 2 < г < т, 18.
[МЗВ] В этом упражнении рассмотрен наихудпгий случай использования алгоритма 8. а) С помощью "комбинаторной матрицы", элементы которой имеют внд р + хбб (см. упр 1.2.3 — 39), найдите целочисленные матрицы размера 3 х 3 Г/ и 1', удавлю творяющие (29) и такие, что преобразование на шаге 85 ничего не дает для любого у, но соответствующие значения зь в (31) настолько велики, что перебор всех значений невозможен. (Матрица ГУ не обязана удовлетворять (28); нас интересует здесь произеольнал положительно определенная квадратпчная форма с определителем т.) Ь) Хотя преобразование (23) не используется для матриц, построенных в (а), найдите другое преобразование, которое дает значительное сокращение.
ь 19. [11М25[ Предположим, что шаг 85 изменен так, что преобразование с д = 1 осуществляется, когда 2К 1', = Ъ~ Ъ). (Таким образом, д = [(И 1» /Ъ', Р~) + Ц, каково бы ни было» зг /ъ) Возможно ли, что при этом алгоритм Б зациклится? 20. [М22[ Обсудите, как применить подходящий спектральный критерий к линейной конгруэнтной последовательности, у которой с = О, Ле — нечетное, т = 2', о шоб 8 = 3 илн 5 (см. упр. 3.2.1.2-9.) 21. [М20[ (Р. В. Госпер (К. %. Оозрег).) Для некоторых задач случайные числа используются группами па четыре числа, но отбрасывается второе число из каждого множества.
Как можно исследовать структуру решетки (-'(Х», Х» ьз,Х»»».з)), которую производит линейный конгруэнтный генератор периода ш = 2'? 22. [М4б[ Какова наилучшая верхняя грань для рз, если дз очень близко к своему максимальному значению»/4/3 я? Какова наилучшая верхняя грань рз, если пз очень близка к своему максимыгьному значению» х;/2? з 23.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
