Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 46
Текст из файла (страница 46)
(Ь»2), где 1 < Ь! < у для 1 < у < 2, и составьте алгоритм для вычисления Ь» через а» за О(2) шагов. 13. ]МЯУ] (С. В. Голомб (Я. »1!. Со!ошЬ).) Один из наиболее простых способов тасования игральных карт — разделение колоды карт на две максимально равные части и их тасование вместе. (В правилах Хойла карточных игр при обсуждении профессиональной этики игроков в карты сказано: "'Тасоваиие такого вида можно выпачнить приблизительно трехкратным тщательным перемешиванием игральных карт".) Рассмотрим колоду из 2п — 1 игральных карт Х4, Хз,..., Хз„!. "Идеальное перемешняание" — это разделение э раз этой колоды на части Х„Х2, ..., Ха и Х +», ..., Хз !. Чередуя их, получим Л!, Х .!.», Лз, Х„оз, ..., Х2„4, Х,, Операция "разрезания' с' меняет Х!, Лз,, Хз -! на Хьо», ..., Хз„„Х», ..., Х,, Покажите, что, комбинируя идеальное перемешивание н разрезание, можно получить не более (2п — Ц(2п — 2) различных упорядочений компоновок игральных карт, если и > 1.
14. (68] Разрезав и перетасовав перестановку аоа, ... 9„», можно заменить ее пешедовательностью, содержащей подпоследоватвльности 0*0! +П 4 -ащ-Н «4 и 0»аьо!! ! . 0! -И 4 которые перемешаны определенным способом дчя некоторых х и 9. Таким образом, погледовательность 3890145267 является разрезанием и перетао:екой 0123456769 с х = 3 и 9=6. а) Начав с расположенных обычным образом 52 игральных карт 2 3 4 Ь Ь 7 В 9!03 С1К А 2 3 4 Ь В 7 В 9 »02 ГЗК А 2 3 4 Ь В 7 В 9 »03 Г)К А 2 3 4 Ь В 7 В 9 »03 С) К А аааааааааааааоооооооооооооооооооооооооо ° аааааааааааа мистер Д. Г. Квик (Я.
Н. Оо)сй) (" Студент" ) сделал случайное разрезание и перетасовку, затем убрал крайнюю слева карту и вставил ее в случайное место. Получилась последовательность 920К343АКА2С)3 2 3 4 Ь Ь 7 4 39 34093 7413К9»02!ЗАК2 ЗА42 24 Ь а Ь В 7 379»03 3 *аоааоа*оооааааааоаао ° о ° оао ° ооооаоааоаойоааооооаоооа Какую карту он убрал из крайней слева позиции? Ь) Начав снова с колоды в ее обычном порядке, Квик сделал п»ри разрезания н перетасовки, прежде чем сдвинул крайнюю слева карту на новое место: »0 1»4 3 о 5 е 3 л я о е к А 3 3 к 4 т 8 е с)А 7 8 А 8 т е к к 8 А т 8 9»0 8 то 8 3 8 3 3 3 »1» э 3 3 9»о оааооеооооао*ьааеаоеооаоаоеоаооооаааоеаооооооооеоаоа. Какую карту он сдвинут на этот разУ ь 16.
(ур) (Олс-Йохан Лаял (01е-,)оЬап ПаЫ).) Если Х» = я для 1 < Тс < 1 в начале алго- ритма Р и если остановить алгоритм, когда у достигнет значения 1 — и, последовательность Х» „оы ..., Л» станет случайной перестановкой случайных комбинаций нз и элементов, Покажите, как эффективно смоделировать зту процедуру, используя только О(п) ячеек памяти, ь 16.
(МЯ) Придумайте метод вычисления случайной выборки по и записей из А» при за- данных А' н и, основываясь на идее рапдомнзацни (раздел 6.4). Можете использовать в нем О(п) ячеек для хранения и в среднем О(п) единиц времени. Метод должен предо»валять выборку как упорядоченное множество целых чисел 1 < Х| < Хз « Х~ < Х. 17. (Мел) (Р. В, Флойд (11, '»»'.
Р)оут)).) Докажите, что следующий алгоритм генерирует случайную выборку о нз и целых чисел нз (1,..., йГ). Присвойте сначала Р о- 6, а затем дляу о-1»» — и+1, Х вЂ” и+2, ..., А» (в таком порядке) присвойте й о- (ЯУ) +1 и ( Р О Щ если й й З; ) ЯО (у'), если й Е 5. г3.5. ЧТО ТАКОЕ СЛУЧАЙНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ А. Вводные замечания. Выше в данной главе рассказывалось, как генерировать последовательности (Ьч) ~0~ Н11 Ь21 (1) действительиых чисел в области О ( Ь'„с 1. Эти последовательности назывались случайными, даже несмотря на то, что оии совершепио детерминированные по характеру.
Чтобы оправдать использоваиие этой терминологии, мы утверждали, что числа "ведут себя так, как будто они действительно случайны". Такое утверждение может быть удовлетворительным для практических целей (в настоягцее время), но это шаг в сторону очень важного методического и теоретического вопроса '"Что именно подразумевается под случайным поведением?". Необходимо количественное определение. Нежелательио говорить о понятиях, которых мы на самом деле ие понимаем, главным образом потому, что, по-видимому, можно сделать много парадоксальных утверждений, касающихся случайных чисел. Теория вероятностей и математическая статистика тщательно избегают обсуждения спорных вопросов.
Они воздерживаются от безусловных утверждений и вместо этого выражают все в терминах вералгпиостией, связанных с последовательностью случайных событий. Аксиомы теории вероятностей устаиовлеиы так, что теоретические вероятности можно легко вычислить, но о том, что иа самом деле означает "вероятность" или как зто понятие можно разумно примеиить к действительиости, ничего не говорится. В кииге РгоЬаЬ1И1у, Ягагйбсг, алд Тгпгй (Хе» Уог)с Маспп1(ап, 1957), Р, фон Мизес (В.
хоп МЬег) подробно обсуждает эту ситуацию и предлагает следующую точку зрения: определение вероятностей зависит от того, какое используется определение случайных последовательностей. Процитируем здесь несколько утверждений двух авторов, комментировавших эту тему. Д. Х'. Лехмер (О. Н. ЬеЬшег) (1951); яОлучайиая последовательность является смутным понятием, олицетворяющим идею последовательности, в которой каждый член является непредсказуемым для непосвященных и значения которой проходят ояределеииое количество проверок, традиционных у статистиков и отчасти зависящих от пользователей, которым предложена последовательность".
Д. Н. Фривклии (Х Х ВипЫт) (1962): "Последовательиость (1) случайна, если оиа обладает любыми свойствами, присущими всем бесчисленным последовательностям независимых выборок случайиых равиомерно распределенных величин". Утверждение Франклина, по существу, обобщает высказывание Лехмера о том, что последовательность должна удовлетворять всем статистическим критериям. Его определение не вполне точное, и позже мы убедимся, что разумное объяснение его утверждения приводит к заключению о том, что ие существует такого объекта, как случайная последовательность! Так давайте начнем с менее ограничительного утверждения Лехмера и попытаемся сделать его точным.
Что иам действительно необходимо — так это сравнительно короткий перечень математических свойств, каждое из которых удовлетворяет нашим интуитивным представлениям о случайной последоватшльности. К тому же этого перечня будет вполне достаточно, чтобы согласиться с тем, что любая последовательность, удовлетворяющая этим свойствам, является "'случайной". В данном разделе рассматривается то, что кажется адекватным точному определению случайности согласно этим критериям, хотя много интересных вопросов остается без ответов, Пусть и и и — действительные числа, 0 < и < и < 1. Если à — случайная величина, равномерно распределенная между 0 и 1, вероятность того, что и < Г < щ равна и — и. Например, вероятность, что - < Г < —, равна -. Как можно выразить 1 з х это свойство единственного числа П свойством бесконечной последовательности Пе, Гл, л щ ...
2 Очевидный ответ — подсчитать, сколько раз У„находится между и и и, и сказать, что среднее число попаданий в этот интервал равно и — и. Наше интуитивное понятие вероятности основано, таким образом, на частоте появления события. Точнее, пусть и(п) — число значений /, 0 < у < и, таких, что и < (/1 < и, и отношением и(п)/и необходимо приблизить значение ь — и, когда и стремится к бесконечности: !нп — = и — и. и(п) (2) Если это условие выполняется для всех вариантов и и и, говорят, что последовательность равнороспределена. Пусть утверждение 5(п) относится и к целому числу и, и к последовательности Ущ (/и ..., например Я(п) может быть приведенным выше утверждением "и < Г„< ьз'.
Можно обобщить понятие, используемое в предыдущем разделе, чтобы определять вероятность того, что Я(п) справедливо по отношению к некоторой бесконечной последовательности. Определение А. Пусть р(я) — число значений /, 0 < / < и, таких, что Я(/) верно. Мы говорил|, что Я(п) выполняется с вероятностью Л, если предел и(п)/н, когда п стремятся к бесконечности, равен А. А именно: Рг(5(и)) = Л, если 11т„, р(п)/и = А. В терминах этой записи последовательность Со, Ул,... равнораспределена тогда и только тогда, когда Рг(и < (/„< ь) = и — и для всех действительных чисел и, в при0<п<п<1. Последовательность может быть равнораспределена, даже если она не случайна. Например, если Уо, (/л, ...
и $ш 1'м... — равнораспределенные последовательности, то нетрудно показать, что последовательность (3) также равнораспределена, поскольку подпоследовательность -Ур, 1Уд,... равно- распределена между 0 и у, в то время как промежуточные члены -+ -'га. й+ й 1л,... л равнораспределены между 1 и 1, Но в последовательности И~л,,~ = 0,1,2,..., значения, меньшие —, всегда следуют за значениями, ббльшими илн равными — со- 1 ! ответственно. Значит, последовательность не случайна согласно любому разумному определению.
Необходимы свойства, которые сильнее равнораспределенности. Естественная возможность обобщить свойство равнораспределенности, которое позволяет развеять сомнения предылущего раздела, — рассмотреть смежные пары членов нашей последовательности. Можно потребовать, чтобы последовательность удовлетворяла условиям (4) Рг(и~ < Гь < ег и и2 < У„,+~ < ез) = (е~ — и~)(ия — пе) для любых членов иы ом пх., о~ при 0 < н~ < ег < 1, 0 < нх < св < 1. И вообще, для любого положительного целого /с можно потребовать, чтобы наша последовательность была 6-распределенной в смысле определения В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
