Антон и гейзеры

Задание 1

Антон – большой любитель путешествий. Прошлым летом он добрался до долины Хёйкадалюр в Исландии. В долине находятся $N$ гейзеров, каждый из которых извергается ровно раз в $x_i$ минут, $1 \le i \le N$. Точный момент, когда начал извергаться конкретный гейзер, Антону неизвестен, поэтому будем считать, что время с момента появления Антона в долине до извержения $i$-го гейзера непрерывно равномерно распределено на отрезке $[0; x_i]$. Гейзеры при этом извергаются независимо друг от друга (то есть, времена первых извержений после появления Антона независимы). Антона интересует, с какой вероятностью каждый из гейзеров начнёт своё извержение первым среди остальных.

Баллы

Баллы зависят от трудоемкости по $N$.

Любая трудоемкость: 2 курс - 15 баллов, 1 курс – 30 баллов.
Трудоемкость (по порядку) не больше $O(N^3)$*: 2 курс – 20 баллов, 1 курс – 40 баллов.
Трудоемкость (по порядку) не больше $O(N^2)$*: 2 курс – 30 баллов, 1 курс – 60 баллов.

* – здесь сделано чрезмерно оптимистичное предположение о том, что арифметические операции над рациональными числами выполняются за $O(1)$.

Подготовка

Нужно написать программу, где на вход поступает $N$, затем $N$ периодов извержения гейзеров $x_i$, где $x_i$ — рациональные (для начала можно написать реализацию с $x_i$ типа double). Результатом программы являются $N$ рациональных вероятностей. Требуется также объяснить полученное решение.

Задача предполагает ознакомление с элементарной теорией вероятностей (например, Ширяев А.Н., Вероятность-1, третье издание, Москва, МЦНМО, 2004, гл. 1 пар. 1-4, гл. 2 пар 1-4).

Руководитель

Никита Звонарев

research/prob_geysers.txt · Последнее изменение: 2018/09/15 00:46 — nikita
Наверх
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0