Список заданий по ДМ 2024 весна — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 32: Строка 32:
 
# Дает ли следующий метод равномерную генерацию всех перестановок? ""p = [1, 2, ..., n]; for i from 1 to n: swap(p[i], p[random(1..n)] )""
 
# Дает ли следующий метод равномерную генерацию всех перестановок? ""p = [1, 2, ..., n]; for i from 1 to n: swap(p[i], p[random(1..n)] )""
 
# Дает ли следующий метод равномерную генерацию всех перестановок? ""p = [1, 2, ..., n];  for i from 1 to n: swap(p[random(1..n)], p[random(1..n)] )""
 
# Дает ли следующий метод равномерную генерацию всех перестановок? ""p = [1, 2, ..., n];  for i from 1 to n: swap(p[random(1..n)], p[random(1..n)] )""
# Рассмотрим следующий метод генерации случайной перестановки. Применим алгоритм из задания 31, а затем к получившейся перестановке верный алгоритм из задания 30. Будет ли полученное распределение на перестановках равномерным?# Рассмотрим следующий метод генерации случайной перестановки. Применим верный алгоритм из задания 30, а затем к получившейся перестановке алгоритм из задания 31. Будет ли полученное распределение на перестановках равномерным?
+
# Рассмотрим следующий метод генерации случайной перестановки. Применим алгоритм из задания 31, а затем к получившейся перестановке верный алгоритм из задания 30. Будет ли полученное распределение на перестановках равномерным?
 +
# Рассмотрим следующий метод генерации случайной перестановки. Применим верный алгоритм из задания 30, а затем к получившейся перестановке алгоритм из задания 31. Будет ли полученное распределение на перестановках равномерным?
 
# Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$)
 
# Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$)
 
# Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$), использующий $O(k)$ времени и памяти.
 
# Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$), использующий $O(k)$ времени и памяти.

Версия 13:06, 16 февраля 2024

  1. Чему равна вероятность, что две случайно вытянутые кости домино можно приложить друг к другу по правилам домино?
  2. Чему равна вероятность, что на двух брошенных честных игральных костях выпадут числа, одно из которых делит другое?
  3. Чему равна вероятность, что если вытянуть из 52-карточной колоды две случайные карты, одной из них можно побить другую (одна из мастей назначена козырем, картой можно побить другую, если они одинаковой масти или если одна из них козырь)?
  4. Чему равна вероятность, что на двадцати брошенных честных монетах выпадет поровну нулей и единиц?
  5. Петя и Вася бросают по десять честных монет. Какая вероятность, что они выбросят одинаковое количество единиц?
  6. Используя формулу Стирлинга $n!\approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$ оцените, чему равна вероятность, что на $2n$ брошенных честных монетах выпадет поровну нулей и единиц. Найдите асимптотическое поведение при $n \to \infty$
  7. Петя и Вася три раза бросают по одной честной игровой кости. Вася два раза выкинул строго больше, чем Петя, а один раз строго меньше. При этом Петя в сумме выкинул строго больше, чем Вася. С какой вероятностью такое могло произойти?
  8. Приведите пример трех событий, для которых $P(A \cap B \cap C) = P(A)P(B)P(C)$, но которые не являются попарно независимыми, причем вероятности всех трех событий больше 0
  9. Доказать или опровергнуть, что для независимых событий $A$ и $B$ и события $C$, где $P(C) > 0$ выполнено $P(A \cap B|C) = P(A|C)P(B|C)$
  10. Доказать или опровергнуть, что для независимых событий $A$ и $B$ и события $C$, где $P(A) > 0$, $P(B) > 0$ выполнено $P(C|A \cap B) = P(C|A)P(C|B)$
  11. Доказать или опровергнуть, что если пары событий $A$, $C$ и $B$, $C$ независимы, а $A$ и $B$ не пересекаются, то $A\cup B$ и $C$ тоже независимы.
  12. Доказать или опровергнуть: если $P(A|B) = P(B|A)$, то $P(A) = P(B)$
  13. Доказать или опровергнуть: если $P(A|B) = P(B|A)$, то $A$ и $B$ независимы
  14. Доказать или опровергнуть: если $P(A|C) = P(B|C)$, то $P(C|A) = P(C|B)$
  15. Выразите $P(A|B \cap C)$ через $P(A|B)$, $P(A|C)$, $P(B)$ и $P(C)$, либо обоснуйте, что это невозможно сделать.
  16. Доказать или опровергнуть: если $A$ и $B$ независимы, то $\Omega \setminus A$ и $\Omega \setminus B$ независимы.
  17. Петя собирается смотреть серию матчей финала Флатландской хоккейной лиги. В финале две команды играют до 5 побед, ничьих не бывает, таким образом максимум в финале будет не более 9 матчей. Вася рассказал Пете, что всего в финале было 7 матчей. Петя считает матч интересным, если перед его просмотром он не знает, кто выиграет финал. Пусть все возможные последовательности исходов матчей, удовлетворяющих описанным условиями, равновероятны. Какова вероятность, что будет хотя бы 4 интересных матча?
  18. Петя собирается смотреть серию матчей финала Флатландской хоккейной лиги. В финале две команды играют до 5 побед, ничьих не бывает, таким образом максимум в финале будет не более 9 матчей. Вася рассказал Пете, что всего в финале было 7 матчей. Петя считает матч зрелищным, если перед его просмотром он не знает, кто его выиграет. Пусть все возможные последовательности исходов матчей, удовлетворяющих описанным условиями, равновероятны. Какова вероятность, что будет хотя бы 5 зрелищных матчей?
  19. Найдите распределение и математическое ожидание следующей случайной величины: число бросков нечестной монеты до первого выпадения 1.
  20. Найдите распределение и математическое ожидание следующей случайной величины: число бросков честной монеты до второго выпадения 1.
  21. Найдите математическое ожидание числа инверсий в перестановке чисел от 1 до $n$
  22. Найдите математическое ожидание числа подъемов (таких $i$, что $a[i] < a[i + 1]$) в перестановке чисел от 1 до $n$
  23. Найдите математическое ожидание числа троек $i$, $j$, $k$, где $i < j < k$ и $a[i] < a[j] < a[k]$ в перестановке чисел от 1 до $n$
  24. Верно ли, что если $\xi$ и $\eta$ - независимые случайные величины, то таким будут и $f(\xi)$ и $g(\eta)$ для любых функций $f$ и $g$? Достаточно доказать для конечных вероятностных пространств.
  25. Постройте случайную величину, имеющую конечное математическое ожидание и бесконечную дисперсию.
  26. Постройте случайную величину, имеющую бесконечное математическое ожидание и конечную дисперсию.
  27. Рассмотрим игру. Колода из 52 карт, 26 красных и 26 черных, тасуется, так что все порядки следования карт оказываются равновероятными. Затем карты извлекаются по одной и колоды в открытую до того момента, пока не игрок не скажет ""стоп"". После этого открывается еще одна карта, если она красная, то игрок выигрывает. Какая стратегия максимизирует вероятность выигрыша игрока?
  28. 10 шаров раскладываются по 5 корзинам. Для каждого шара равновероятно выбирается, в какую корзину он помещается. Какое математическое ожидание числа пустых корзин?
  29. 10 шаров раскладываются по 5 корзинам. Для каждого шара равновероятно выбирается, в какую корзину он помещается. Какое математическое ожидание числа корзин, содержащих ровно один шар?
  30. Докажите, что минимум $E(X-\alpha)^2$ достигается при $\alpha = EX$.
  31. Предложите метод генерации случайной перестановки порядка $n$ с равновероятным распределением всех перестановок, если мы умеем генерировать равномерно распределенное целое число от 1 до $k$ для любых небольших $k$ ($k = O(n)$).
  32. Дает ли следующий метод равномерную генерацию всех перестановок? ""p = [1, 2, ..., n]; for i from 1 to n: swap(p[i], p[random(1..n)] )""
  33. Дает ли следующий метод равномерную генерацию всех перестановок? ""p = [1, 2, ..., n]; for i from 1 to n: swap(p[random(1..n)], p[random(1..n)] )""
  34. Рассмотрим следующий метод генерации случайной перестановки. Применим алгоритм из задания 31, а затем к получившейся перестановке верный алгоритм из задания 30. Будет ли полученное распределение на перестановках равномерным?
  35. Рассмотрим следующий метод генерации случайной перестановки. Применим верный алгоритм из задания 30, а затем к получившейся перестановке алгоритм из задания 31. Будет ли полученное распределение на перестановках равномерным?
  36. Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$)
  37. Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$), использующий $O(k)$ времени и памяти.