74
правки
Изменения
→Доказательство корректности
== Доказательство корректности ==
{{Лемма
|statement=Вероятность получить в процессе работы алгоритма некоторый перфикс префикс <tex> P </tex> равна <tex> S(P)\over{C(n)} </tex>, где <tex> C(n) </tex> {{---}} число различных комбинаторных объектов данного типа длины <tex> n </tex>, а <tex> S(P) </tex> {{---}} число различных комбинаторных обьектов длины <tex> n </tex> с таким префиксом.
|proof=Докажем по [[Математическая индукция|индукции]]:
'''База:''' Заметим, что любой комбинаторный объект имеет пустой перфикс префикс (<tex> \varnothing </tex>), следовательно <tex> S(\varnothing)=C(n) </tex>.
Вероятность получить некоторый префикс <tex> P </tex> длины <tex> 1 </tex> равна <tex> S(P)\over{S(\varnothing)} </tex>, что равно <tex>
S(P)\over{C(n)} </tex> .
