74
правки
Изменения
Нет описания правки
*Вероятность получить из <tex> P </tex> любой префикс <tex> P' </tex> длины <tex> l+1 </tex> равна <tex> S(P')\over{S(P)} </tex> , следовательно вероятность получить префикс <tex> P' </tex> равна <tex> S(P)\over{C(n)} </tex><tex>\cdot</tex><tex> S(P')\over{S(P)} </tex> что равно <tex> S(P')\over{C(n)} </tex>
Результат работы алгоритма является префиксом <tex> P </tex> размера <tex> n </tex> и для любого такого префикса существует только один комбинаторный объект размера размера <tex> n </tex> , следовательно вероятность получения одинакова для всех различных результатов и равна <tex> 1\over{C(n)} </tex>.
== Доказательство корректности ==
{{Утверждение
|id=идентификатор (необязательно), пример: proposal1.
|author=Автор утверждения (необязательно)
|about=О чем утверждение (необязательно)
|statement=утверждение
|proof=доказательство (необязательно)
}}
== Примеры решения задач ==