Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 37
Текст из файла (страница 37)
[НМОО] (Алан П Вотерман (А(ап С. ЪЧасеппап), 1974.) Придумайте эффективную процедуру вычисления множителя а ш 1 (по модулю 4), для которой существует относительно простое решение уравнения щ + арз ж 0 (по модулю гп) с у~~ + Оз = ~/4/3 гп — е, где г > 0 настолько мвлб, насколько зто возможно при заданном щ = 2'. (Согласно упр. 10 такой выбор а гарантирует, что из~ > гп~/(9( + уз) > ~/3/4пз, и существует возможность, что кзз будет близко к своему оптимальному значенню ь/4/3 пь На практике будем подсчитывать несколько таких множителей для малых е, выбирая затем один нз них с наилучшими спектральнмми значениями ьз, из, . ) 12. [НМ23] Не прибегая к использованию графических методов, докажите, что любое решение вопроса (Ь), поставленного после (23), должно удовлетворять уравнениям (2б). 13.
[НИЗ] В лемме А используется факт, что 1/ не вырождена, для доказательства того, что положительно определенна» квадратичная форма принимает некоторое не равное иулю минимальное значение в точке с целыми не равными нулю коорзмнатами. Покажите, что зто предположение необходимо, рассмотрев квадратичную форму (19), матрица коэффициентов которой не вырождена и для которой значения /(хм..., я~) расположены произвольно в окрестности нуля (но никогда его не достигают) в не равной нулю точке с целыми координатами (ям..., я~). 14. [24] Вручную выполните алгоритм Б для гп = 100, о = 41, Т = 3.
ь 15. [МЗО] Пусть (7 — вектор с целыми координатами, удовлетворяющий (15). Сколько (à — 1)-мерных гнперплоскостей, определенных (7, пересекают единичный гиперкуб ((ям...,х~) [ 0 < зг < 1 для 1 < у' < г)7 (Это примерно равно числу гиперплоскостей в семействе, которого достаточно, чтобы покрыть Ее.) 16. [МОО] (У. Дитер (Г Вбегсг).) Покажите, как молсно преобразовать алгоритм Я, чтобы вычислить минимальное число Х~ параллельных гнперплоскостей, пересекающих единичный гиперкуб, как в упр. 15 для всех (7, которые удовлетворяют (15). [Указание.
Каким приблизительно будет аналог положительно определенной квадратичной формы и леммы А7] 17. [20] Преобразуйте алгоритм Я таким образом, чтобы он не только вычислял величины ип но и давал на выходе все векторы с целыми координатами (им.,., п~), удовлетворяющие (15), и такие, что пг[+ .+п,'ми~ при 2 < 1 <Т. 19. [МЮО] В этом упражнении рассмотрен наихудший случай использовании алгоритма Б. а) С помощью "комбинаторной матрицы", элементы которой имеют вид 9 + я50 (см.
упр, 1.2.3-39), найдите целочисленные матрицы размера 3 х 3 У и 1~, удовлетворяющие (29) и такие, что преобразование на шаге 85 ничего не дает для любого /л но соответствующие значения зз в (31) настолько велики, что перебор всех значений невозможен. (Матрица (? не обязана удовлетворять (28); нас интересует здесь щюкзеальнал положительно определенная квадратичная форма с определителем пз.) Ь) Хотя преобразование (23) не используется для матриц, построенных в (а), найдите другое преобразование, которое дает значительное сокращение.
° 19. [НМ25[ Предположим, что шаг 85 изменен так, что преобразование с 9 = 1 осуществляется, когда 2К ~; =!" 1). (Таким образом, 9 = [(!1 г'/11 \')+ Д, каково бы ни было з;4 11) Возможно ли, что при этом алгоритм $ зациклится? 20. [М28[ Обсудите, как применить подходящий спектральный критерий к линейной конгрузнтиой последовательности, у которой с = О, Ле — нечетное, пз = 2', а шад 8 ш 3 или 5 (см. упр, 3.2.1.2-9.) 21. [М20[ (Р, В. Госпер (К.
%. Соврет).) Для некоторых задач случайные числа используются группами по четыре числа, на отбрасывается второе число нз каждого множества. Как можно исследовать структуру решетки ( ~~ (Хы, Хз„+з, Лз +з) ), которую производит линейный конгрузнтный генератор периода т = 2'? 22. [М48[ Какова наилучшая верхняя грань для дз, если дз очень близко к своему максимальному значению з/4/3 х? Какова наилучшая верхняя грань дз, если дз очень близко к своему максимальному значению ~уяЯ? 23, [М48) Пусть ~Л, 1' — векторы, координаты которых являются действительными чигламя с У,. Ъ;. = Бч длв 1 < з,у < 1, и такие, что 55. У~ = 1, 2[!7 Уз[ < 1, 2[К 15[ < 15 Рз для 1 зЗ,~. Насколько большим может быть 11 Ьз? (Этот вопрос имеет отношение к граням на шаге 87, если н (23), и преобразование из упр.
18, (Ь) не производят никаких сокращений. Известно, что максимальное значение равно (1+ 2)/3. Оно достигается, когда Уз = П, Ц = -'1з + 1з/31~, г) = 1~ — (1з + . - + 1 )/Я, 'г) = 21 /Я для 2 < 1 < Ь где (1м,.,, Д) — единичная матрица. Эту схему предложил Б.
В. АлЬксеев.) ° 24. [М28[ Обобщите спектральный критерий для последовательностей второго порядка вида Х„= (аХ -з+ЬХ -з) щоз(р, имеющих длину периода рз — 1 (см. формулу 3 2 2-(8)). Как следует изменить зьчгаритм Б? 25. [НМ24[ Пусть,д — делитель т и пусть О < 4 < И. Докажите, что сумма 2 г(й), где суммирование производится по всем 0 < й < т, таким„гго й шод 8 = д, меньше либо равна (2/йт) (п(т/Ы) + 0(1).
(Здесь г(й) определено формулой (4б) при Ф = 1.) 26. [М22[ Объясните, почему, если использовать метод доказательства (53), можно получить грани, подобные полученным, для оба<Я при 0 < 9 < т. Почему доказательство (53) ничего не дает, когда т = 1? 22. [НМ89) (Э. Хлавка (Е. Н!аиЬа) и Г. Нидеррейтер (Н. №ебегге!Зег).) Пусть з (им...,аз) — функция, определенная в (4б). Докажите, что сумма 2 г(нм..., аз), где суммирование производится по всем О < им, .., из < зл так, что (вм ..,, п~) зЗ (О,..., О), и выполиаетса Равенство (15), меныпе или Равна 2((х + 2з !бт)' г з ), где г — максимальный член г(им..., из) втой суммы, ь 28.
[М28) (Г. Нндеррейтер.) Найдите аналог теоремы Н для случая, когда пз — простое числа, с = О, а — первообразный корень по модулю из, Ха зе 0 (по модулю зп). [Указание. Ваши экспоненпнальные суммы должны включать ь = е~ гд П так же, как ы.~ Докажите, что в этом случае "средний" первообразный корень имеет разброс П„',~, = О (Ф(1об ш)'/~о(пт — 1)), следовательно, хороший первообразный корень существует для всех гп. 29.
[ЯМйй) Докажите, что величина г „из упр. 27 никогда не будет больше 1/~/8 кь 30. [М33[ (С. К, Заремба (3. К. Хатепйа).) Докажите, что г „= О(шах(ам...,а,)/гп) в двумерном случае, когда ам ..., а, — это частичные отношения, полученные в результате применения алгоритма Евклида к гп и а. [Ужьэаиис, В обозначениях нз раздела 4.5.3 справедливо равенство а/гл = //ам..., а,//; примените упр. 4.5,3-42.[ 31. [ВМ47[ (И. Варош (1. Вогоэп),) Докшкнте, что для всех достаточно больших гл сушествует взаимно простое с гп число а, такое, что все частичные отношения а/т меныпе илн равны 3. Кроме того, множество всех гп, удовлетворяющих этому условию„но с частичными отношениями < 2, имеет положительную плотность. ь 32. [М31[ Пусть ш~ ш 2з' -1 и шэ = 2з' -249 — модули генератора (38). а) Покажите, что если (/ = (.Х /пп — у /глэ) шов 1, то У„ш Я„/пп.
Ь) Пусть Ио ш (Хегпз — Уеш~) шойгл и И'„+~ = еИ'„шойпг, где а и гл имеют значения, приведенные в разделе после формулы (38). Докажите, что существует простое соотношение между Ига и (/ . В следующем издании данной книги я планирую ввести новый раздел 3.3.3 под Ф названием "йз-алгоритм".
Это будет отклонение от общей темы ("Случайные числа" ), ио в нем будет продолжено рассмотрение решетчатого базиса, описанного в разделе 3.3.4. Основным предметом изучения станет неоклассический алгоритм А. К. Леметра (А. К. Еепзсга), Н. И'. Ьепзгта, А., апб Е.
ЬоиЬх, Май.Аппа)еп 361 (1933), 313-334„для нахолгдения приближенно оптимального множества базисных векторов н демсистрацэш того, что алгоритм мсокно применять к другим исследованиям. Примеры таких исследований приводятся в следующих статьях и содержвцейся в иих библиографии: Мб Яеузеп, Сгип)хпазог)са 13 (1993), 393-3уб; С. Р.
Ясйпогг апб Н. Н. Нбгпег, Ьесспге г(о1ез 1п Сотр. 5с), 931 (1993), Я-Ю 3.4. ДРУГИЕ ВИДЫ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ В пРедыдущих РАзделлх мы обсуждали, как генерировать на компьютере последовательность чисел Ц>, Пм 11т,..., которые ведут себя так, как если бы каждое число выбиралось независимо и случайно между О и 1 с равномерным распределением. Однако при использовании случайных чисел часто требуются другие виды распреде. лений.
Например, чтобы сделать случайный выбор из и альтернатив, нужны случайные целые числа, лежащие между 1 и к. Если необходимо моделировать случайное время ожидания между появлениями независимых событий, желательно получить случайные числа с показаюельнмм распределением. Иногда в случайных числах нет необходимости, но нужны случайные пересшаноеки (случайное размещение и объектов) нли случайное сочетание (случайный выбор й объектов из совокупности, содержащей и объектов). В принципе, любая из этих случайных величин может быть получена из равномерно распределенных случайных величин Цр, Ом (1з, ....
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
