QUOTE |
Я же писала: если заключённых 100 и выводят их раз в сутки по одному, то среднее время выполнения цикла 28 лет. Строгое математическое доказательство (а также другие варианты решения) в статье по ссылке (инглиш, правда).
|
Вот это ваши слова. Это... ммм... ну просто неверно. И вообще, там в статье всё в предположении, что выборка заключенных равновероятная (uniform), о чём в этой теме (и в ваших же переформулировках задачи) речи вообще не было.
QUOTE |
Моя к.т.н., дальше что? Будем меряться неизвестно чем или внимательно читать?
|
Я сюда не мериться пришел, просто перестаньте мне тыкать что я что-то там невнимательно прочитал. Я все внимательно прочитал, я подумал, пришел к этому же решению, потом еще подумал и пришел к выводу что оно практически неприменимо. Я также прочитал приведенную статью и особенно пункт, там где оценивается матожидание срока выхода заключенных в 28 дней. Так что нечего еще и меня обвинять в невнимательности.
QUOTE |
Это чистой воды математическая задача из теории вероятностей
|
Да-а-а? Может, в статье, на которую вы так старательно ссылаетесь. Но явно не у топикстартера.
QUOTE |
Ограничение по времени это новое условие, которое не имеет отношения к этой задаче.
|
Ну да, ну да. Во-первых, задача про людей все-таки а не про абстрактыне предметы (по крайней мере была сформулирована так). Во-вторых, весь сыр-бор в приведенной статье со множеством алгоритмов как раз из-за того чтобы сократить время. В третьих, ну давайте тогда все практические задачи, для которых есть NP-трудные алгоритмы решения, считать решенными, а чего же ими дальше заниматься, алгоритм же есть?
Практического решения эта конкретная задача не имеет, приведенная вами статья не несет практической пользы. Поэтому и столько формул и выкладок и т.п. (кое-как свели матожидание к O(n(lnn)^2), да и то это только матожидание, которое к конкретной попытке конкретной группы заключенных отношения не имеет).
QUOTE |
Ежу понятно, что для любой сколь угодно длинной случайной последовательности выбора вероятность того, что хотя бы один заключённый так и не посетит камеру отлична от нуля, хоть и близка к нему.
|
Условие равномерной выборки отсутствует в исходных условиях задачи, так что ежу не понятно.
QUOTE |
Ровно тому же ежу понятно, что кроме мат. ожидания есть ещё и дисперсия.
|
Ну да, есть, и что?
QUOTE |
И даже целому стаду ежей понятно, что мат. статистика и теория вероятностей не одно и то же.
|
Ой, ну вот не надо вот этого, умоляю, вы же к.т.н., взрослый человек, что за пустые придирки?
QUOTE |
А если уж очень хочется, так попробуй ответить на вопрос "за какое время (или при какой длине последовательности) данный алгоритм сработает с заданной вероятностью (например, 0,9)?"
|
Это характеризует работу алгоритма в целом, на большом числе случайных последовательностей. И что это даст для решения конкретной проблемы, если в формулировке задачи мы проводим один единственный эксперимент с одной единственной группой заключенных? У НАС НЕТ ВЫБОРКИ!