AOP_Tom1 (1021736), страница 50
Текст из файла (страница 50)
[10] В тексте раздела показано, как можно присвоить (а,Ь,с,д,е, 1) +- (с,4,1,6,е,а), выполнив ряд операций замены (х +- у) и введя одну вспомогательную переменную б Покажите, как сделать то же самое с помощью ряда операций взаимного обмена (х еэ у) и без вспомогательных переменных. 3. [08] Вычислитецроизведение(' з; ~ ' 1)х( л ' ~; ~~) изапишитерезультатв виде двухстрочной записи. (Ср.
с соотношением (4).) 4. [10] Выразите (а60)(е г)(ас1)(60) в виде произведения непересекающихся циклов. ° б. [М10] В (3) приведено несколько эквивалентных способов представления одной и той же перестановки в циклической форме Сколько существует таких представлений перестановки, в которых вообще нет единичных циклов? б. [МЯУ] Как мзменится время выполнения программы А, если отказаться от предположения, что все пустые слова появляются у правого края ввода? 7.
[10] Если на вход программы А подается произведение перестановок (б), то чему равны величины Х, г', М, ?г', П и Г из (19)? Каким будет время выполнения программы А без учета ввода-вывода? 8. [ЗЮ] Можно ли модифицировать алгоритм В так, чтобы просматривать входные данные слева направо., а не справа налево? 9. [10] Программы А и В воспринимают одинаковые входные данные и ответ дают, в сущности, в одинаковой форме.
Дают ли обе программы е гвачкосшк один и тот же вывод? ь 10. [М30] Рассмотрите характеристики времени выполнения программы В, а мменно— величины А, В, ..., 2, о которых шла речь в тексте раздела, Выразите общее время выполнения через величины Х, 1', М, А?, 11, 1', определенные в (19), и через Г.
Сравните общее время выполнения программ А и В для ввода (б), проведя вычисления, как в упр. 7. 11. [10] Найдмте простое правило, по которому можно записать к в цмклмческой форме, если перестановка я задана в циклической форме. 12. [М27] (Тракспокировакие врлмораолькоб машркпм.) Пусть матрица (а„) размера гл х и, гл ~ и, хранится в памяти, как описано в упр. 1.3.2 — 10, так что значение ао находится в ячейке б + п(1 — 1) + (1 — 1), где Š— это ячейка, в которой содержится а~к Необходимо найти способ пцикспокоровакил этой матрицы, чтобы получить матрицу (Ьч) размера п х т, где Ь„= а„хранится в ячейке б+ ш(1 — 1) + (1 — 1). Таким образом, наша матрица должна быть транспонирована "на себя". (а) Покажите, что преобразование транспонирования переводит значение из ячейки б + х в ячейку Ь + (глх шоп А') для всех х из промежутка О < х <?у = глп — 1.
(Ь) Обдумайте методы выполнения такого транспонмрования с помощью компьютера. ь 13. [М24] Докажите справедливость алгоритма Л. ° 14. [М04] Найдите среднее значение величины А, которая является одной из составляющих времени выполнения алгоритма Л. 1б. (М12] Существует ли.перестановка, для которой каноническая циклическая форма без скобок и линейяая форма совпадают? 16. (М1б] Пусть задана перестановка 1324 в линейной форме. Преобразуйте ее в каноническую циклическую форму, а затем удалите скобки. Повторяйте зту процедуру до тех пор, пока не придете к исходной перестановке. Какие перестановки получатся в ходе выполнения этого пропесса? 17.
(ЬЩ] (а) В тексте раздела показано, что среди всех перестановок из и элементов существует всего и! Н„циклов. Если эти циклы (включая единичные) записать по отдельности на и! Н листочках бумаги, а затем выбрать наугад один из этих листочков, то чему будет равна средняя длина выбранного таким образом цикла? (Ь) Запишем и! перестановок на и! листочках бумаги, наугад выберем число й и таким же случайным образом вытинем один из листочков. Чему равна вероятность того, что цикл, содержащий элемент й, является т-циклом? Чему равна средняя длина цикла, содержащего элемент й? ь 18. (М27] Чему равна р„з, вероятность того, что перестановка и объектов имеет ровно к циклов длины си? Какой будет соответствующая производящая функция О (г)? Чему равно среднее число т-пиклов и каким будет среднее квадратичное отклонение? (В тексте раздела рассматривается только случай, когда т = 1.) 19.
(НМ21] Пользуясь обозначениями из (25), покажите, что число перестановок Р е в точности равно значению и!1е, округленному с!о блнзссайшего целого, для всех и > 1. 20. (МЯО] Пусть все единичные циклы выписаны явно. Сколько существует различных способов представления в виде циклов перестановки, имеющей оз циклов длины 1, пз циклов длины 2, ... (см. упр. З)? 21. (М22] Чему равна вероятность Р(и;с>паз,...) того, что перестановка и объектов имеет ровно сп циклов длины 1, аз циклов длины 2 и т.
д.? з' 22. ]НМЗЦ] (Следующий подход, предложенный Л. Шеппом (Ь. БЬерр) и С. ср. Ллойдом (Б. Р Ь!оус(), дает удобный и мощный метод решения задач, имеющих отношение к циклическим представлениям случайных перестановок. Вместо того чтобы считать число объектов и Фиксированным, а число перестановок — переменным, будем предполагать, что мы независимо выбираем величины пз,оз, аз..., рассмотренные в упр. 20 и 21, в соответствии с некоторым распределением вероятностей. Пусть ш — любое действительное число между О и 1. а) Предположим, что выбраны случайные переменные онпз, оз,...
согласно правилу, которое гласит: "Вероятность того, что и = )с, рвана ((ш,т,?с)", где 1(ш,т,к)— некоторая функция. Определите функцию 1(ш, т,?с) так, чтобы выполнялись следующие два условия: (!) 2 г>е1(ш, т, к) = 1, где О < ш < 1 и т > 1; (й) вероятность того, что ис + 2оз + Заз + = и н что сч = ?сп пг = кз, пз = кз....., равна (1 ш)ш Р(и; Йп 1з 1сз,... ), где Р(и; кс, )сз, кз,... ) определяется в упр. 21. Ь) Очевидно, что перестановка, циклическая структура которой имеет вид ос, оз, оз,..., переставляет ровно оз + 2оз + Заз + объектов. Покажите, что если ап з > 1, выбираются случайно в соответствии с распределением вероятностей из п, (а), то вероятность того, что аз + 2аз + Заз + = и, равна (1 — ш)ш", а вероятность того, что сумма пз + 2пз+ Заз+ бесконечно, равна нулю.
с) Пусть ф(пи из,... ) — произвольная функция от бесконечного числа аргументов пм аз,.... Покажите, что если ан з > 1, выбираются в соответствии с распределением вероятностей нз п. (а), то среднее значение ф равно (1 — ш) )с „>е ш"ф . Здесь ф обозначает среднее значение ф для всех перестановок и объектов, а переменная а, представляет число 1-циклов в перестановке. (Например, если ф(ас, ог,. ) = пз то значением ф„будет сречнее число единичных циклов в случайной перестановке и объектов. Из (28) следует, что ф„= 1 для всех и.] д) Используйте этот метод для нахождения среднего числа циклов чегпной длины в случайной перестановке п объектов.
е) Используйте этот метод для решения упр. 18. 23. [НМ42] (Голомб (Со!ошЬ), Шепп (БЬерр) и Ллойд (Ыоуд) ) Обозначим через 1 среднюю длину самого длинного цикла в перестановке п объектов. Покажите, что 1 Лп+ —.Л, 1 где Л 0.62433 — константа. Докажите, что 1пп„(1„— Лп — -'Л) = О. 24. [М41] Найдите дисперсию величины А, которая является одной из характеристик времени выполнения алгоритма 5 (см.
упр. 14). 25. [МЭЭ] Докажите соотношение (29). ° 26. [МЙ4] Обобщмте принцип включения и исключения, чтобы получить формулу для числа элементов, которые имеются ровно в г из подмножеств ЭыЭг,...,ом. (В тексте раздела рассматривается только случай г = 0.) 27. [М80] Используйте принцип включения н исключения для подсчета количества таких целых чисел и в интервале 0 < п < атгтг... тб которые не делятся нн на одно из тытг,,ть Здесь тп тг, ..., тг и а — положмтельные целые числа, такие, что т, Лтыесли1фк. 28. [М81] (И. Каплански (1. Кар!апзйу).) Если "перестановку Иосифа", определенную в упр. 1.3.2-22, выразить в циклической форме, то получим (1 5 3 6 8 2 4)(7), где п = 8 и т = 4.
Покажите, что в общем случае эта перестановка представляет собой произведение (п п-1 ... 2 1) '(п п — 1 ... 2) '... (и и — Ц 29. [МЭ5] Докажите, что циклическую форму перестановки Иосифа при т = 2 можно получить, сначала выразив "двойную" перестановку (1, 2,..., 2п), которая переводит 1 в (21) шог((2п + 1), в циклической форме, а затем рассмотрев циклы в обратном порядке и убрав все числа, которые больше п. Например, при п = 11 двоймая перестановка будет иметь вид (1 2 4 8 16 9 18 13 3 6 12)(5 10 20 17 11 22 21 19 15 7 14), а перестановка Иосифа — (7 11 10 5)(6 3 9 8 4 2 1).
30. [М34] Используя упр. 29, покажите, что фиксированными элементами перестановки Иосифа при т = 2 будут в точности числа (2г г — 1)(2п + 1)/(2 — 1) для всех таких положительных д, прн которых это выражение дает целые числа. 31. [НМЭЭ] Обобщая упр. 29 и 30, докажмте, что к-м казненным для произвольных пг и п будет тот, кто находится в позиции х, где х можно вычислить гледующмм образом: положить х+- кт, а затем присваивать х г — [(гп(х — и) — 1)/(т — 1)] до тех пор, пока х < и. В результате среднее число фиксированных элементов для 1 < п < г1 н фиксированного гп прм Х -+ оо будет стремиться к 2 „>,(т — 1)"/(тгч' — (т — 1)) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
