Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [ 30 ] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

более точные часы должны учитываться с большим весом. Так ли обстоит дело при нашем выборе s? Если var [lvar [Tg], то придает ли наш выбор обоим часам равные веса?

Упражнения 2.4

2.4.1. Перерешайте всю мультипроцессорную задачу для случая шести процессоров и программы, которой необходимы четыре процессора. Снова воспользуйтесь равно-вероятньм распределением. Вычислите Е [X] и var [X], где случайная переменная X равна числу свободных процессоров.

2.4.2. Какова вероятность получить в точности 7 выпадений «орла» при 12 бросаниях «правильной» монеты?

2.4.3. Пусть в мультипроцессорной задаче G(X)=X=, где X - случайная переменная, массовая функция вероятности которой приведена на стр. 93. Вычислите Е [G] и var [G].

2.4.4. Сортировка прямым включением (анализ). Каково максимально и минимально возможное число сравнений, затрачиваемых алгоритаом SIS для сортировки Л ключей?

2.4.5. Если все возможные упорядочения Л ключей равновероятны, какова вероятность того, что ключи уже будут отсортированы до начала работы алгоритма SIS?

2.4.6. Игрок полагает, что его стратегия игры в рулетку первоклассная. Он наблю-дает-за появлением черных и красных номеров. Если появляются подряд пять красных (черных) номеров, он поставит 10 долларов на черный (красный) номер при следующем запуске рулетки. Он рассчитывает на то, что вероятность появления подряд шести красных (или черных) номеров очень мала. Проанализируйте эту стратегию.

2.4.7. Если Е - произвольное событие в любом пространстве элементарных событий S, покажите, что Р{Е)<.\.

*2.4.8. Если Е к F - два произвольных события, покажите, что P(E[]F)=P(E)+P(F)-P(EViF).

2.4.9. Покажите, что Р(0)=О, где 0 - пустое множество,

2.4.10. Докажите тождество

N-1 N

Оно применялось при анализе алгоритма SIS.

*2.4.11. Если . . . , Аи-случайные переменные с совместной массовой функцией P(xi, Xz, . . . , x„)=P{Xi=Xi, Х2=Х2, .... Х„=х„) и если Ui, . . . ,а„- произвольные константы, покажите, что

Е [aiXi+a2X2+. . .-j-G]=fli£ Ш+. . .+а„Е [Xj.

что ~ произвольная дискретная случайная переменная, то покажите,

var 1Х]=Е 1ХЦ-(Е [X]f. 2.4.13. Покажите, что для любой случайной переменной X и константы а

var laX]=avar [Х].



*2.4.14. Два самолета летят из города X в город Y. У первого самолета два мотора, в случае аварии он может продолжать полет ка одном моторе. У второго самолета четыре мотора, в случае аварии он может продолжать полет иа двух моторах. Все шесть моторов идентичны, вероятность выхода из строя во время полета для каждого мотора равна р. Предположим, что работа каждого мотора не зависит от состояния остальных. На каком бы самолеге вы предпочли лететь? Рассмотрите все значения р в области 0<р<1.

2.4.15. Бросаются четыре одинаковые кости с равновероятным исходом. Какова вероятность, ч-ю не выпадет ни одной пятерки?

2.4.16. Пусть S- пространство элементарных событий, и пусть (fj, .... F„}

множество событий, которые в S несовместимы и в совокупности исчерпывающие. Если Е - произвольное событие, покажите, что

£= и mFi)-

с - I

2.4.17. Используя результат упр. 2.4.16, покажите, что

Р{Е)= P{E\Fi)P{Fi).

*2.4.18. Еше раз рассмотрите алгоритм МАХ из разд. 1.2. Предположим, что каждое упорядочение N чисел равновероятно. Пусть случайная переменная Y обозначает положение наибольшего числа. Вычислите Е IV] и var [К].

*2.4.19. Какова вероятность того, что случайно выбранный тур в задаче о коммивояжере для /V I ородов будет оптимальным? Какие вам нужно сделать предположения при решении этой задачи?

*2.4.20. Независимые случайные переменные. Две случайные переменные Xi и Х независимы, если

P(.Ci<c и X.2<.b)=P(Xia)-P{X.2b) для всех с и Ь.

Покажите, что если Х и Х независимы, то

£UiX2]=£ {XyVElX.

**2.4.21. Алгоритм SIS (анализ). Как и ранее при обсуждении сортировки методом прямого включения, пусть случайная переменная Y равна числу сравнений, необходимых для сортировки ключей с помощью алгоритма SIS. Вычислите var [К]. Предположите, что все Xi - независимые случайные переменные.

*2.4.22. Биномиальное распределение. Рассмотрим п испытаний в эксперименте, в котором вероятность «успеха» равна р. Пусть случайная переменная X фиксирует число успехов в п испытаниях. Предположим, что исход любого испытания не влияет на исход любого другого испытания. Покажите, что массовая функция вероятности для X задается формулой

P(X=k)="pk(l-p)"-. k = 0. 1, ...,п. Вычислите Е [Х] и var IX].

*2.4.23. Пусть G-- сеть с вершинами, ребра которой выбираются случайно в соответствии со следующей схемой. Для каждой пары вершин i и / ребро (г, /) принадлежит G с вероятностью р независимо от г и / и ие принадлежит G с вероятностью 1-р. Каково ожидаемое число ребер в G? Генерируемые таким образом сети называются р-случайными сетями.

*2.4.24. Реометрическое распределение. Пусть вероятность успеха любого испытания в эксперименте равна р, Кавдое испытание не зависимо от .любого другого испытания.



Будем продолжать эксперимент до тех пор, пока не получим в испытании первый успех. Пусть случайная переменная X равна числу испытаний до первого успешного испытания включительно. Какова массовая функция вероятности для X? Вычислите Е \Х] и var [X].

2.4.25. Сортировка методом прямого включения (слоотость, проверка). Реализуйте алгоритм SIS в форме программы на вычислительную машину. Нужно случайным образом сгенерировать (как?) множества из 20 неотсортированных ключей и зафиксировать число сравнений, произведенных при сортировке каждого множества. Пусть Y - среднее этих значений. Сравните У со значением Е [К], полученным при анализе метода сортировки прямым включением.

*2.4.26. Покажите, что оценка

sHXi, Х„)~1..-У (Xi~Xf 1 = 1

является несмещенной оценкой для var [Х].

2.4.27. Убедитесь, что при нашем выборе s в примере из последней части разд. 2.4 значение var [Н] действительно минимально.



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [ 30 ] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.0009